Increase index locality

[renato-grottesi]

I got an idea to increase the index locality by refreshing the hash table with old values. If you have a big image, the hash table stores values in a fashion that trails the current pixel only on its left:

PPPPPPP
IIIICFF
FFFFFFF

Where P is past pixels, I is an indexed pixel, C current and F future pixels. If, every time you read a new current pixel C (both on encode and decode), you add the previously read C-W+1 pixel to the hash table, it would result into a more likely to match environment:

IIIIIIP
IIIICFF
FFFFFFF

As you can see, the current pixel has now 4 indexed pixels in its 8 pixels neighborhood for the prize of a single hashing operation. It could also be possible to reindex the C-2W+2 for extra chances of getting a vertical match if that's beneficial.

I don't have time to test the idea until next Monday, but if someone wants to give it a try, feel free to do so :-)

[wbd73]

I like the idea. As an alternative you could use a new 5 bit tag with 3 data bits (separate from the index) and store an offset value of 0 - 7

PP76543210PP
IIIIIICFFFFF
FFFFFFFFFFFF

In this case the referenced colors from the previous line are always available without any chance of hash collisions. It will make the encoder slower (maybe vector instructions could help to search for a match) but will be faster for the decoder.

Edit: You can forget about my idea. I did not write a full encode / decode, just some analysis. Based on that, comparing against the pixel exactly above would result in about 1% or so of pixels that could be encoded this way that could not be encoded any other way with only 1 byte. Comparing also for the above left and above right pixels improves things only a little. Maybe the idea above of refreshing the color index cache works better.

[renato-grottesi]

I had some time to hack a patch to test the improvements:

diff --git a/qoi.h b/qoi.h
index 083d532..33de44d 100644
--- a/qoi.h
+++ b/qoi.h
@@ -256,6 +256,8 @@ typedef struct {

 const static qoi_magic_t qoi_magic = {.chars = {'q','o','i','f'}};

+#define INDEX_PREVIOUS(w) if ( (channels == 4) && ( px_pos > 4*(w))) { qoi_rgba_t old_px = *(qoi_rgba_t *)(pixels + px_pos - 4*(w)); index[QOI_COLOR_HASH(old_px) % 64] = old_px; }
+
 void *qoi_encode(const void *data, int w, int h, int channels, int *out_len) {
        if (
                data == NULL || out_len == NULL ||
@@ -325,7 +327,7 @@ void *qoi_encode(const void *data, int w, int h, int channels, int *out_len) {
                                bytes[p++] = QOI_INDEX | index_pos;
                        }
                        else {
-                               index[index_pos] = px;
+                               //index[index_pos] = px;

                                int vr = px.rgba.r - px_prev.rgba.r;
                                int vg = px.rgba.g - px_prev.rgba.g;
@@ -365,6 +367,12 @@ void *qoi_encode(const void *data, int w, int h, int channels, int *out_len) {
                        }
                }
                px_prev = px;
+               INDEX_PREVIOUS(0)
+               INDEX_PREVIOUS(w-6)
+               INDEX_PREVIOUS(2*w-6)
+               INDEX_PREVIOUS(3*w-6)
+               INDEX_PREVIOUS(4*w-6)
+               INDEX_PREVIOUS(5*w-6)
        }

        for (int i = 0; i < QOI_PADDING; i++) {
@@ -447,7 +455,7 @@ void *qoi_decode(const void *data, int size, int *out_w, int *out_h, int channel
                                if (b1 & 1) { px.rgba.a = bytes[p++]; }
                        }

-                       index[QOI_COLOR_HASH(px) % 64] = px;
+                       //index[QOI_COLOR_HASH(px) % 64] = px;
                }

                if (channels == 4) { 
@@ -458,6 +466,12 @@ void *qoi_decode(const void *data, int size, int *out_w, int *out_h, int channel
                        pixels[px_pos+1] = px.rgba.g;
                        pixels[px_pos+2] = px.rgba.b;
                }
+               INDEX_PREVIOUS(0)
+               INDEX_PREVIOUS(header->width-6)
+               INDEX_PREVIOUS(2*header->width-6)
+               INDEX_PREVIOUS(3*header->width-6)
+               INDEX_PREVIOUS(4*header->width-6)
+               INDEX_PREVIOUS(5*header->width-6)
        }

        *out_w = header->width;

I tried it on a big image like images/wallpaper/manouchehr-hejazi-6F0wVthJqL0-unsplash.png and it improves compression by almost 4%: from 31199554 to 30036229 bytes. It's not as good as https://github.com/nigeltao/qoi2-bikeshed/issues/6 but maybe it's something to consider for QOI v1?

[magnus-ISU]

I also had this idea, but didn't bother implementing. 4% better compression is pretty good!

However, this discussion should be moved to https://github.com/nigeltao/qoi2-bikeshed/issues. QOIv1 is set in stone

[renato-grottesi]

Ah! I thought it was still open. Then let's abandon it as nigeltao/qoi2-bikeshed#6 gives already 15% on the same image for less complexity.