Is it just me, or is the compression algorithm not really less than the one in PNG? I will grant the author that if you don't need features like support for color spaces, different bit depths or interlacing you can skip the entire container format. But for reference this is the core part of png:
For each scanline write one byte for the chosen filter method, then $width pixels. There are five filter types. In type 0, write the pixels unmodified. In type 1, write the difference to the previous pixel. In type 2, write the difference to the above pixel. In type 3, write the difference to the average of the above and left pixel. In type 4, write the difference to the Paeth predictor (a simple function calculated from the above, left and left above pixel). Then compress everything with deflate.
Obviously by modern standards that isn't performant, not least because deflate sucks by modern standards. But it's simple, can be implemented in a couple lines of C (if you pull in deflate as dependency), and if you don't do exhaustive searches for the best compression it can certainly run in O(n)
The 64-pixel lookback makes it a bit similar to LZ-style compression like Deflate, but the latter is not O(n) because it can recognize multi-pixel sequences. QOI is just a slightly beefed up run-length encoding.
For each scanline write one byte for the chosen filter method, then $width pixels. There are five filter types. In type 0, write the pixels unmodified. In type 1, write the difference to the previous pixel. In type 2, write the difference to the above pixel. In type 3, write the difference to the average of the above and left pixel. In type 4, write the difference to the Paeth predictor (a simple function calculated from the above, left and left above pixel). Then compress everything with deflate.
Obviously by modern standards that isn't performant, not least because deflate sucks by modern standards. But it's simple, can be implemented in a couple lines of C (if you pull in deflate as dependency), and if you don't do exhaustive searches for the best compression it can certainly run in O(n)