Secondary index cache with two-byte encoding

[chocolate42]

Another possible opcode, QOI_OP_INDEX2. This is a two byte encoding with eight bit opcode, that acts as an index into a secondary index cache with 256 values.

Pro:

• Bigger cache matches more input, allows some pixels to be stored as two bytes instead of 4 or 5 bytes
• Only takes up a single opcode
• Reuses the color hash calculation, getting more mileage from it

Con:

• Requires an extra 1024 bytes of memory for the secondary cache. This seems doable even for microcontrollers/etc but expert eyes may have a different opinion

Comparison to current master build:

• 4700u, gcc 11.2.0, -O3
• index2 takes master91cc, adds the QOI_OP_INDEX2 opcode by making QOI_OP_RUN store 62 values, and rearranges the decode chain slightly

  # Grand total for qoi_benchmark_suite/images
         decode ms   encode ms   decode mpps   encode mpps   size kb    rate
  libpng:        6.582      90.359         70.52          5.14       423   23.3%
  stbi:          6.492      61.252         71.50          7.58       601   33.2%
  qoi-master91cc:2.124       2.584        218.50        179.60       463   25.6%
  qoi-index2:    2.410       2.510        192.60        184.90       456   25.2%

@phoboslab If this or any other opcode change is deemed suitable I'll do proper pull requests as and when

qoi-index2.h.txt

[chocolate42]

Testing some combinations of primary and secondary index cache sizes:

• Baseline is roughly the current master branch (with a max run reduced from 62 to 60 to accomodate secondary index tags). Represented below with qoi-ind64
• indX, where X is the size of the cache for the 1-byte encoding
• .2, secondary index with 256 values (2-byte encoding, 8 bit tag)
• .2a, secondary index with 512 values (2-byte encoding, 7 bit tag)

Grand total for ./qoi/qoi_benchmark_suite/images

         decode  encode  decode   encode  size    rate spare_tags
             ms      ms    mpps     mpps    kb

qoi-ind0: 1.719 2.237 269.99 207.50 509 28.1% 66 qoi-ind2: 2.063 2.423 225.02 191.60 504 27.8% 64 qoi-ind4: 2.103 2.484 220.75 186.89 498 27.5% 62 qoi-ind8: 2.107 2.580 220.25 179.89 492 27.2% 58 qoi-ind16: 2.044 2.509 227.14 185.02 484 26.7% 50 qoi-ind32: 2.165 2.494 214.35 186.12 474 26.2% 34 qoi-ind64: 2.181 2.488 212.83 186.58 463 25.6% 2

qoi-ind0.2: 2.113 2.314 219.71 200.61 486 26.8% 65 qoi-ind2.2: 2.328 2.620 199.40 177.16 484 26.7% 63 qoi-ind4.2: 2.342 2.643 198.21 175.60 480 26.5% 61 qoi-ind8.2: 2.434 2.542 190.70 182.59 475 26.2% 57 qoi-ind16.2: 2.367 2.624 196.12 176.88 469 25.9% 49 qoi-ind32.2: 2.431 2.550 190.94 182.02 463 25.5% 33 qoi-ind64.2: 2.421 2.524 191.70 183.93 456 25.2% 1

qoi-ind0.2a: 2.144 2.287 216.49 203.00 483 26.7% 64 qoi-ind2.2a: 2.426 2.561 191.35 181.23 481 26.5% 62 qoi-ind4.2a: 2.440 2.573 190.20 180.43 477 26.3% 60 qoi-ind8.2a: 2.430 2.586 191.01 179.51 472 26.1% 56 qoi-ind16.2a: 2.406 2.546 192.95 182.35 466 25.7% 48 qoi-ind32.2a: 2.510 2.610 184.91 177.87 460 25.4% 32 qoi-ind64.2a: 2.505 2.591 185.26 179.15 453 25.0% 0

I like the look of ind32.2, compresses on par with the baseline ind64 but uses 31 less tags. There's also something to be said about ind16.2 if those extra 16 ops can be better used elsewhere, maybe in a variant that limits itself to MASK_2 and MASK_4.