QOI: Lossless Image Compression in O(n) Time

This is pretty neat. A lot like the filtering done in PNG, just without slapping zlib on the result. As far as SIMD goes, I agree with the author and don't see much potential, as instructions are variable-length and most instructions encode deltas. It's probably quite close to optimal by just letting the CPU figure it out on the micro-level.

If each line were encoded independently they could be en- and decoded in parallel (once you add a skip instruction to tell where the next line starts, this does preclude streaming of intra-line output though). The hit to compression ratio should be small as long as images are wide enough for the color buffer reset to not matter.

This is impressive, I was curious if it was just better on simpler images with many duplicate pixels but it's nice to see it working well with photography too

e.g. https://phoboslab.org/files/qoibench/images/wallpaper/EwZDbL...

            decode ms   encode ms   decode mpps   encode mpps   size kb
    libpng:     148.4      3995.5         55.88          2.08     12223
    stbi:       161.0      1858.3         51.50          4.46     19199
    qoi:         60.8        95.6        136.49         86.78     12868

I'm interested if there's a standardized benchmark used in the academic literature this could be tested against

In any case the results are impressive enough that this will 100% be used in projects I work on!

Many thanks to the author for their work <3

> To keep things O(n) when encoding, there's only one lookup into this array. The lookup position is determined by a “hash” of the rgba value (really just r^g^b^a).

Is a bit imprecise. The algorithm would still be O(n) even with a linear search through the "seen pixel array", as it is bounded by 64 length and therefore a constant factor that gets eaten by the Big-O notation.

Because of this hash the algorythm seems to do something else than first described though. Instead of "a running array of the 64 pixels it previously encountered", it's actually the previous 64 pixel _values_ previously encountered, which allows for much bigger jumpback.

By deterministically computing this array during execution it itself seems to act as a kind of compressed jumpback table, allowing for approximated arbitrary jumpback with just 6 bit.

Quite impressive!

Edit: I think there might be an interesting tweak that could increase the effectiveness of the hashing technique used.

If one were to walk and store the pixels in a Z-Curve order, the runtime would stay the same but the locality of the color value pool, might be increased.

tl;dr:

  00xxxxxx          - copy (x+1)-th last EXPLICITLY ENCODED pixel (i.e. ignoring repeats)
  010xxxxx          - repeat the last pixel x+1 times
  011xxxxx xxxxxxxx - repeat the last pixel x+33 times
  10rrggbb          - copy the last pixel and adjust RGB by (r-1, g-1, b-1)
  110rrrrr ggggbbbb - copy the last pixel and adjust RGB by (r-15, g-7, b-7)
  1110rrrr rgggggbb bbbaaaaa
                    - copy the last pixel and adjust RGBA by (r-15, g-15, b-15, a-15)
  1111RGBA [rrrrrrrr] [gggggggg] [bbbbbbbb] [aaaaaaaa]
                    - copy the last pixel and replace RGBA if each bit flag is set

So it is essentially the PNG filter limited by Sub, but offers better delta coding and a larger history window. My guess is that it might not work well if the image has a strong vertical gradient (which would need the vertical context), but nevertheless it's pretty impressive that this simple coding is not as inefficient at all.

This is as cool as it gets.

I have a honest question about the source code, a lot of time since I coded anything meaningful in C, but I remember the header files did not have that much code on it, while here I see most of the code is in the header file. Why is this the case? Inline compilation? What are the advantages?