Recent changes in experimental branch

[phoboslab]

With all that we learned through the analysis and ideas of a lot of people here, I refined QOI quite a bit. More than I thought I would.

The current state is in the experimental branch.

First of all, benchmark results for the new test suite using
qoibench 1 images/ --nopng --onlytotals

## Total for images/textures_photo/
        decode ms   encode ms   decode mpps   encode mpps   size kb    rate
master:       8.2        11.6        127.43         90.52      2522   61.6%
experi:       5.9         8.2        178.14        127.56      1981   48.4%

## Total for images/textures_pk01/
master:       0.7         1.0        186.23        126.11       184   36.4%
experi:       0.6         0.9        214.67        145.87       178   35.2%

## Total for images/screenshot_game/
master:       2.7         3.9        231.42        162.40       534   21.6%
experi:       2.6         3.4        245.06        187.25       519   21.0%

## Total for images/textures_pk/
master:       0.3         0.5        138.31         93.64        83   48.1%
experi:       0.3         0.4        159.63        110.87        75   43.5%

## Total for images/textures_pk02/
master:       2.0         2.8        155.27        110.31       504   42.5%
experi:       1.7         2.3        182.73        133.00       479   40.4%

## Total for images/icon_64/
master:       0.0         0.0        251.06        163.38         4   28.3%
experi:       0.0         0.0        343.60        266.60         5   31.3%

## Total for images/icon_512/
master:       0.6         0.9        474.50        308.36        80    7.8%
experi:       0.6         0.7        474.62        378.76       102   10.1%

## Total for images/photo_kodak/
master:       2.9         4.2        137.76         92.77       771   50.2%
experi:       2.4         3.5        166.17        111.66       671   43.7%

## Total for images/textures_plants/
master:       3.8         6.2        281.64        170.37       951   22.9%
experi:       3.3         5.0        324.00        211.07       922   22.2%

## Total for images/screenshot_web/
master:      18.1        28.2        449.27        287.79      2775    8.7%
experi:      17.5        23.2        464.81        350.15      2649    8.3%

## Total for images/pngimg/
master:       6.5        10.0        279.91        180.57      1415   20.0%
experi:       5.9         8.6        307.44        210.93      1445   20.5%

## Total for images/photo_tecnick/
master:      10.1        15.2        142.74         95.00      2710   48.2%
experi:       8.8        13.6        163.36        105.69      2527   44.9%

## Total for images/photo_wikipedia/
master:       7.8        11.7        138.75         92.50      2260   53.4%
experi:       6.7        10.4        161.91        104.37      2102   49.6%

# Grand total for images/
master:       2.1         3.1        220.85        148.50       485   26.8%
experi:       1.9         2.7        245.67        173.24       465   25.7%

As you can see throughput improved a lot, as did the compression ratio for all files without an alpha channel (icon_*/ and pngimg/ suffered a bit, but the overall compression ratio for these files is already quite high. textures_plants/ still saw improvements). For photos or photo-like images QOI now often beats libpng!

What changed? After I switched the tags for QOI_RUN (previously 2-bit tag) and QOI_GDIFF_16 (previously 4-bit tag) I noticed that QOI_GDIFF covered almost all(!) cases that were previously encoded by QOI_DIFF_16/24. So... why not remove them?

#define QOI_OP_INDEX  0x00 // 00xxxxxx
#define QOI_OP_DIFF   0x40 // 01xxxxxx (aka QOI_DIFF_8)
#define QOI_OP_LUMA   0x80 // 10xxxxxx (aka QOI_GDIFF_16)
#define QOI_OP_RUN    0xc0 // 11xxxxxx
#define QOI_OP_RGB    0xfe // 11111110 (aka QOI_COLOR with RGB)
#define QOI_OP_RGBA   0xff // 11111111 (aka QOI_COLOR with RGBA)

(see the experimental file format documentation for the details)

That is, most tags are now 2-bit, while the run-length is limited to 62 and thus leaves some room for the two 8-bit QOI_OP_RGB and QOI_OP_RGBA tags. So QOI would be even simpler than before and (probably?) gain a lot more possibilities for performance improvements:

• there is no multi-byte run
• there are no tags with a variable byte-length
• there are no more values that cross byte boundaries

Yes, it means that a change in the alpha channel will always be encoded as a 5-byte QOI_OP_RGBA, but using the current test suit of images, this seems to be totally fine. The alpha channel is mostly either 255 or 0. The famous dice.png and FLIF's fish.png seem to be awfully "artificial" uses of PNG. (For comparison, in the experimental branch with the original tag-layout and QOI_DIFF_16/24 still present, the overal compression ratio was at 24.6% - but the win in simplicity and performance is imho worth this 1%).

The hash function changed to the following:

#define QOI_COLOR_HASH(C) (C.rgba.r * 3 + C.rgba.g * 5 + C.rgba.b * 7)

This is seriously the best performing hash function I could find and I tried quite a few. This also ignores the alpha channel, making it even more of a second-class citizen.

You may not like it (and I'm truly sorry for all the work that would need to be done in existent implementations), but I strongly believe that this is The Right Thing To Do™.

Thoughts?

[Wulf0x67E7]

The only nitpick I can think of would be the GRB- instead of RGB-bit-order of QOI_OP_LUMA. Is there any technical reason to use the green channel as the guide instead of the red one?

[phoboslab]

The idea was that changes in lightness (luma) would be most represented in the green channel, since that is the color that the human eye is most sensitive to. I just tried it with a 6-bit red channel instead and got consistently worse results — but not by much. Overall compression rate would be at 25.9%.

Maybe it's worth changing it anyway, for clarity's sake.

[Wulf0x67E7]

Huh, I didn't think that it would have any impact at all on a lossless format and that those human-perception-specific tricks only really matter when compressing lossily.

I'd personally change it, but it really is incredibly nitpicky and doesn't matter too much either way. ¯\_(ツ)_/¯

[oscardssmith]

I think the reason it matters is probably that it is fairly common for images to get subtly lighter or darker while maintaining the same hue, and in those cases, green on average is what changes the most.

[rmn20]

Wouldn't removing DIFF_24 greatly degrade the compression ratio of semi-transparent textures? (like hair textures, or maybe water textures) I think these changes make qoi useless for semi-transparent images. Maybe in that case its better to stop encoding alpha levels at all and only write rgb + 0/1 alpha?

[phoboslab]

Yes, it performs worse for these, but I am not convinced that this is an issue.

From my game dev experience even textures for water, clouds, dust etc. use fairly distinct alpha values. Many of these don't even have an alpha channel at all and are just blended with GL_ONE GL_ONE (fire, flares, etc.) or GL_ZERO GL_SRC_COLOR (water, smoke, etc.).

The two worst performing examples I found are actually the ones most prominently featured by other image formats: dice.png and fish.png. As I said before, I believe these are fairly "artificial" examples.

## images/misc/fish.png size: 1969x1307
        decode ms   encode ms   decode mpps   encode mpps   size kb    rate
libpng:      28.1       207.8         91.44         12.39       520    5.2%
stbi:        18.5       197.8        139.20         13.01       804    8.0%
qoi_master:   5.9         9.2        438.07        280.36       862    8.6%
qoi_experi:   5.6         6.9        457.53        372.52      1148   11.4%

## images/misc/dice.png size: 800x600
        decode ms   encode ms   decode mpps   encode mpps   size kb    rate
libpng:       6.7        51.6         71.92          9.30       237   12.7%
stbi:         5.2        45.8         92.34         10.48       341   18.2%
qoi_master:   1.3         1.8        362.65        263.83       355   19.0%
qoi_experi:   1.2         1.3        414.23        356.69       508   27.1%

Compression rate wasn't really great before (compared to libpng/stbi), but it's still very good compared to uncompressed RGBA.

[oscardssmith]

One last change that might be worth trying is changing QOI_INDEX to actually use a LRU cache. This will probably be a little slower, but it would remove the effect of hash collisions on the file size.

[vsonnier]

Sorry @phoboslab I think there is a mistake in computiing the color differences:

char vr = px.rgba.r - px_prev.rgba.r;
char vg = px.rgba.g - px_prev.rgba.g;
char vb = px.rgba.b - px_prev.rgba.b;

char vg_r = vr - vg;
char vg_b = vb - vg;

You need int to hold [-255; 255] differences in vxxx, else someting funky will happen when differences are beyond +-127. I suppose the computation itself is fine by integer promotion ? Note that the master version indeed holds the differences in ints.

Edit :
Got it the wrap around arithmetic, although the signed char troubled me a loong time: I finally thought of it in terms of

type Wrap_Around_Difference_Type is mod 256; 

in Ada, then everything was clear.

[chocolate42]

Here's a tweak to the index, tested against the old data set because ISP's suck.
qoi-exluma: Experimental branch baseline
qoi-luma61: The index table is reduced to 61 values (prime) and the hash function is simply px.v%61. No other changes. Possible union endian issues that can be resolved with a compiler check (?)
qoi-luma61.run64: The RGB and RGBA tags have been moved to the end of the index chunk so rle has a full 64 values, which seems to help decode speed a surprising amount (something something power of two?). There are still two unused 8 bit codes, but with a 6 bit RUN_8 there's no need for RUN_16 and I didn't want to theorycraft further here.

## Benchmarking ../qoitests/images/tango512/*.png -- 1 runs
## Totals (AVG) size: 0x0
               decode ms   encode ms   decode mpps   encode mpps   size kb
libpng:              3.1        20.5         84.87         12.76        51
stbi:                2.1        20.6        124.21         12.74        69
qoi-exluma:          0.7         0.8        353.49        336.18       102
qoi-luma61:          0.7         0.8        371.70        319.96        86
qoi-luma61.run64:    0.6         0.8        457.27        331.28        86

## Benchmarking ../qoitests/images/kodak/*.png -- 1 runs
## Totals (AVG) size: 0x0
               decode ms   encode ms   decode mpps   encode mpps   size kb
libpng:              9.6       179.6         41.10          2.19       717
stbi:               10.1        98.9         39.05          3.98       979
qoi-exluma:          3.1         4.2        127.20         94.29       671
qoi-luma61:          2.9         4.5        135.15         88.22       675
qoi-luma61.run64:    2.6         4.4        148.52         89.88       675

## Benchmarking ../qoitests/images/misc/*.png -- 1 runs
## Totals (AVG) size: 0x0
               decode ms   encode ms   decode mpps   encode mpps   size kb
libpng:             12.0       102.1         74.30          8.71       283
stbi:               10.4        97.2         85.39          9.14       415
qoi-exluma:          2.8         3.3        316.36        270.04       513
qoi-luma61:          2.8         3.3        322.46        272.58       504
qoi-luma61.run64:    2.4         3.2        364.61        280.07       503

## Benchmarking ../qoitests/images/textures/*.png -- 1 runs
## Totals (AVG) size: 0x0
               decode ms   encode ms   decode mpps   encode mpps   size kb
libpng:              3.0        41.7         42.96          3.12       163
stbi:                2.7        23.3         48.05          5.57       232
qoi-exluma:          0.8         1.1        163.08        120.30       178
qoi-luma61:          0.7         1.1        181.62        115.97       179
qoi-luma61.run64:    0.6         1.1        201.48        119.41       179

## Benchmarking ../qoitests/images/screenshots/*.png -- 1 runs
## Totals (AVG) size: 0x0
               decode ms   encode ms   decode mpps   encode mpps   size kb
libpng:             59.4       620.1        138.56         13.27      2219
stbi:               52.0       755.2        158.20         10.90      2821
qoi-exluma:         28.5        26.1        288.85        315.97      2476
qoi-luma61:         27.2        27.3        302.62        301.02      2478
qoi-luma61.run64:   23.9        27.1        344.47        303.73      2475

## Benchmarking ../qoitests/images/wallpaper/*.png -- 1 runs
## Totals (AVG) size: 0x0
               decode ms   encode ms   decode mpps   encode mpps   size kb
libpng:            191.4      2922.5         48.97          3.21      9224
stbi:              220.4      1814.6         42.53          5.16     13299
qoi-exluma:         76.9        85.8        121.91        109.21      9923
qoi-luma61:         75.4        94.0        124.24         99.72      9965
qoi-luma61.run64:   64.2        85.0        146.09        110.21      9964

qoi.luma61.run64.h.txt

[phoboslab]

Very cool. Reducing the index to 61 is rather clever! And I'd really like to know why a 64 run-length would help that much with performance.

@vsonnier this should be fine, as long as the decoder wraps these values around, too.

Edit: I can't really reproduce these throughput numbers. qoi-luma61.run64 performs slightly worse on my machine.

# Grand total for images
                decode ms   encode ms   decode mpps   encode mpps   size kb    rate
qoi-exluma:           1.9         2.7        244.79        172.72       465   25.7%
qoi-luma61.run64:     1.9         2.7        239.50        169.05       463   25.6%

Compression is better though. Images with alpha suffer quite a bit when the hash doesn't include alpha value. Might be worse to change it to:

#define QOI_COLOR_HASH(C) (C.rgba.r * 3 + C.rgba.g * 5 + C.rgba.b * 7 + C.rgba.a * 11)

(or just C.v % 61 as you proposed)

[nigeltao]

Some numbers vs qoi-demo10. qoi-experi is commit 28954f7. qoi-l61r64 is the luma61.run64 mentioned above.

For compressed size, qoi-demo10 wins on icon_512, icon_64 and pngimg, which all involve alpha. qoi-experi wins everywhere else, including on textures_plants (which also involves alpha). I know simplicity of format is a goal, but perhaps consider having two slightly different sets of opcodes (or opcode bit assignments) depending on whether channels == 3 or channels == 4. Edit: now that I've added the luma61.run64 numbers, the qoi-demo10 vs qoi-l61r64 gap is noticably smaller on icon_512, icon_64 and pngimg.

One more quick request is to raise QOI_PADDING from 4 to 7, so that the decoder can always do an 8 byte (64 bit) read.

        decode ms   encode ms   decode mpps   encode mpps   size kb    rate

## Total for images/icon_512
libpng:       5.0        33.9         52.74          7.74        51    5.0%
stbi:         3.9        32.8         66.47          8.00        69    6.8%
qoi-experi:   1.5         1.2        180.47        224.24       102   10.1%
qoi-demo10:   0.8         1.2        309.23        218.27        76    7.5%
qoi-l61r64:   1.0         1.4        254.71        190.54        86    8.4%

## Total for images/icon_64
libpng:       0.2         0.9         23.26          4.35         3   23.6%
stbi:         0.1         0.9         28.05          4.45         4   27.9%
qoi-experi:   0.0         0.0        103.12        106.03         5   31.3%
qoi-demo10:   0.0         0.0        148.43        110.04         4   27.6%
qoi-l61r64:   0.0         0.0        141.35        106.50         4   28.8%

## Total for images/photo_kodak
libpng:      15.2       295.7         25.88          1.33       717   46.7%
stbi:        16.9       157.8         23.33          2.49       979   63.8%
qoi-experi:   5.7         6.7         69.14         58.89       671   43.7%
qoi-demo10:   4.1         7.1         95.72         55.76       772   50.3%
qoi-l61r64:   4.5         6.6         87.26         59.26       675   44.0%

## Total for images/photo_tecnick
libpng:      44.9      1143.8         32.08          1.26      2414   42.9%
stbi:        57.9       608.3         24.88          2.37      3533   62.8%
qoi-experi:  20.9        26.3         68.99         54.67      2527   44.9%
qoi-demo10:  13.0        25.1        111.04         57.44      2737   48.7%
qoi-l61r64:  17.2        25.3         83.93         57.02      2529   45.0%

## Total for images/photo_wikipedia
libpng:      42.9       865.8         25.28          1.25      2046   48.3%
stbi:        54.6       456.6         19.87          2.38      2893   68.3%
qoi-experi:  15.7        19.9         69.17         54.39      2102   49.6%
qoi-demo10:   9.5        19.2        113.99         56.49      2289   54.0%
qoi-l61r64:  12.8        19.3         84.51         56.30      2103   49.7%

## Total for images/pngimg
libpng:      56.4       533.3         32.08          3.39      1201   17.0%
stbi:        59.6       399.9         30.35          4.52      1751   24.8%
qoi-experi:  15.5        15.7        116.99        114.90      1445   20.5%
qoi-demo10:   9.0        15.7        201.83        114.98      1429   20.2%
qoi-l61r64:  11.7        16.4        154.61        110.63      1437   20.3%

## Total for images/screenshot_game
libpng:      18.6       216.7         34.08          2.92       448   18.1%
stbi:        20.9       150.9         30.24          4.19       634   25.7%
qoi-experi:   6.3         6.3        101.13        100.93       519   21.0%
qoi-demo10:   4.1         6.1        156.06        104.53       535   21.7%
qoi-l61r64:   4.9         6.5        130.18         97.85       517   20.9%

## Total for images/screenshot_web
libpng:      92.0      1060.7         88.33          7.66      2402    7.6%
stbi:        78.8      1210.3        103.12          6.71      3076    9.7%
qoi-experi:  50.5        38.8        160.98        209.22      2649    8.3%
qoi-demo10:  28.3        40.4        287.55        201.06      2680    8.4%
qoi-l61r64:  37.7        44.7        215.30        181.93      2649    8.3%

## Total for images/textures_photo
libpng:      39.6       725.0         26.45          1.45      1977   48.3%
stbi:        46.6       370.7         22.49          2.83      2554   62.4%
qoi-experi:  13.9        15.8         75.30         66.35      1981   48.4%
qoi-demo10:  10.1        18.3        104.22         57.40      2506   61.2%
qoi-l61r64:  11.2        15.1         93.39         69.39      1990   48.6%

## Total for images/textures_pk
libpng:       0.9        24.6         47.24          1.81        89   51.5%
stbi:         0.8        17.0         55.03          2.62       121   70.0%
qoi-experi:   0.7         0.8         61.19         58.01        75   43.5%
qoi-demo10:   0.6         0.7         77.52         60.26        78   45.1%
qoi-l61r64:   0.6         0.8         79.75         58.52        75   43.3%

## Total for images/textures_pk01
libpng:       5.3        66.5         24.65          1.95       163   32.3%
stbi:         5.1        37.1         25.61          3.50       232   45.8%
qoi-experi:   1.6         1.7         81.33         77.75       178   35.2%
qoi-demo10:   1.0         1.6        136.54         81.54       180   35.6%
qoi-l61r64:   1.1         1.6        116.92         78.89       179   35.3%

## Total for images/textures_pk02
libpng:      11.7       205.0         25.97          1.48       427   36.1%
stbi:        12.1       100.1         25.07          3.03       623   52.5%
qoi-experi:   4.2         4.4         71.95         69.25       479   40.4%
qoi-demo10:   2.8         4.3        108.01         70.79       492   41.5%
qoi-l61r64:   3.1         4.3         96.66         70.61       481   40.5%

## Total for images/textures_plants
libpng:      31.9       340.6         33.35          3.12       857   20.6%
stbi:        30.7       241.5         34.66          4.41      1191   28.7%
qoi-experi:   8.0         9.2        132.21        116.02       922   22.2%
qoi-demo10:   4.3         9.5        247.12        111.57       957   23.0%
qoi-l61r64:   6.0         9.4        177.48        113.29       922   22.2%

# Grand total for images
libpng:      13.5       187.9         34.47          2.47       423   23.3%
stbi:        14.7       121.4         31.53          3.82       601   33.2%
qoi-experi:   4.7         5.0         98.37         92.79       465   25.7%
qoi-demo10:   3.0         4.9        156.82         94.45       484   26.7%
qoi-l61r64:   3.7         5.1        127.03         91.58       463   25.6%

        decode ms   encode ms   decode mpps   encode mpps   size kb    rate

This was on a mid-range x86_64 laptop (2016, Skylake):

$ cat /proc/cpuinfo | grep model.name | uniq
model name	: Intel(R) Core(TM) m3-6Y30 CPU @ 0.90GHz

[phoboslab]

Regarding a 7-Byte padding: wouldn't it make sense to put and "end-marker" there, instead of just 0x00 bytes?

If we then use 0xfd = QOI_RGB and 0xfe = QOI_RGBA we could pad the stream with 0xff bytes. Since QOI dosn't allow for more than 4 consecutive 0xff bytes anywhere in the stream, this could be a nice replacement for the now-missing size header, when streaming images.

Edit: thinking about it some more, a 7-byte 0x00 shouldn't occur in a stream either, since repeated QOI_INDEX chunks should be encoded as QOI_RUN instaed.

[phoboslab]

Further changes in experimental:

• QOI_COLOR_HASH now includes the alpha channel: r * 3 + g * 5 + b * 7 + a * 11 - this helps quite a bit with the icons and pngimg from the test suite.
• colorspace in the header is now an enum, where 0 = sRGB with linear alpha, 1 = all channels linear. It seems any other channel configuration does not make much sense (see Add initial support for the QOI image format Tom94/tev#148). The 0 value for sRGB provides a sensible default.
• the data is now padded with 8 0x00 bytes. These also indicate "end of image" to alleviate the absent size header.

[Lokathor]

Just adding a size field to the header would be far mor efficient than making people who want to skip the image iterate every byte looking for a run of four 0xFF or eight 0x00.

[phoboslab]

We've had this discussion (see #28 (comment)) and I believe the benefit of allowing a "streaming" encoder that does not need seeking outweigh the drawbacks of not having the size in the header.