Comment by j-pb | Hacker News Reader

Comment by j-pb | Hacker News Reader

> 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.

> 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.

It's somewhere in between. Because these values are hashed into single slots, assuming that hash codes are random, the probability that a value is still in the table after k intervening values is pow(63/64, k).

That means the table is unlikely to contain all 64 values, but it will also retain some older values. Since older values are less likely to be useful in the future the encoding performance is likely somewhat worse than if the algorithm used strictly the last 64 distinct values.

This means that the algorithm is a bit sensitive to hash collisions, which seem particularly likely for primary colors (i.e. with each of the components at value 0 or 255):

  - Slot 0: black, ALL SHADES OF magenta (x ^ 0 ^ x = 0), yellow (etc.) and cyan.
  - Slot 15: white (255 ^ 255 ^ 255 = 255), red (255 ^ 0 ^ 0 = 255), green (etc.), blue.

Except black and white, these are unlikely to occur often in photographic images but could well occur in bitmaps with a handcrafted palette, or when the RGB values are converted from a system with a lower color space. For example, the 16 color CGA palette maps to just 3 different slots.

Yeah, one should probably add a randomisations step for each channel for good measure.

With random byte->byte lookup tables those costs should be hidden by the cache.

so hash = HR[r] ^ HG[g] ^ HB[b] ^ HA[a].

In an image with very limited colors you would have long runs of the same color and it would compress well from just the run-length encoding alone.

Also, it's non-obvious that older values will be less useful. Going through the pixels in order like this doesn't preserve locality well, so older values may actually be closer to a given pixel than more recent ones.

> In an image with very limited colors you would have long runs of the same color and it would compress well from just the run-length encoding alone.

...unless those images are dithered. Which may be a relatively common thing to do in small color spaces!

I was about to post the same idea about a locality preserving pixel order. I was thinking about hilbert curves, never heard of z-curves. Would be nice to see if/how that affects the compression ratios. How surprising that a few simple principles can give quite a good image format

https://en.wikipedia.org/wiki/Z-order_curve

Related to this method, it's sometimes used for texture mapping on GPUs.

After making the edit, I saw that someone made the same suggestion on twitter!

Hilbert curves have slightly better locality than Z-curves, but Z-Curves are trivial to produce.

If you have a N dimensional space over unsigned integers, then you can place each point on a one dimensional Z-Curve by interleaving their bits into a new integer.

So for any point (X, Y) in the X-Y coordinates of an image the Z-Curve coordinate is X_1,Y_1,X_2,Y_2...

Which can be achieved with a bunch of bit shifts and masks, (or a bunch of wires if you happen to use it in an FPGA ^^')

CPUs can do this quickly:

   __m128i src = _mm_set_epi32(0, 0, x, y);
   __m128i res = _mm_clmulepi64_si128(src, src, 0);
   uint64_t zeorder = _mm_extract_epi32(res, 0) | (_mm_extract_epi32(res, 2) << 1);

Though a blocked iteration order should perform better due to better locality.

Thanks for the pointer!

If anybody else want to know how this works:

https://stackoverflow.com/questions/30539347/2d-morton-code-...

https://en.wikipedia.org/wiki/Carry-less_product

I added Z-order curve to a ray tracer many years ago. Rather than using nested loops over X and Y pixel coordinates I used a single loop and de-interleaved the count to get X and Y. My thought was that this would increase the cache hit rate due to the locality of the pixels. It worked and the speedup was on the order of 10 percent. Because images are rarely power of 2 or even the same in both dimensions I opted to make a list of 32x32 blocks and rendered the blocks in Z-order as well as the pixels within (which still helped vs just tiling).

Locality is a good thing to exploit.

Hilbert curves are not that much more complex. Maybe ten or so lines of code. Interleaving bits is already a pretty complicated operations if you don't have builtins for it.

I agree that de-interleaving is fairly complicated, but interleaving can be done fairly easily with a lookup from a table for each dimension and then combining them: xbits[x] | ybits[y] | channelbits[c].

The nice thing about this is that just by changing the tables, you can get things like z-curve, tiles, row-major, or column-major pixel orders (or even combinations), plus swizzled, interleaved, or planar layouts for the color channels.

Do you have a link to discussions about QOI on twitter?

https://twitter.com/WAHa_06x36/status/1463456861978599426?s=...

Based on some quick* testing using z-order instead of going row by row ends up taking 1-10% less space. Most images were on the lower end but I didn't run into any taking more space.

* Swapping to z-order requires about 5 lines of changes if you ignore all the little edge cases like non power-of-two image sizes. Images used in testing may or may not be representative of anything.

I wonder how much worse the compression would be if you just had the last 64 colors, but didn't update when using the run length byte codes. Seems like it would be close to the same, and the decoder wouldn't need to hash the pixels.

Reply on news.ycombinator.com