Remember ye olde dayes when we had to be mindful of the so-called “web safe palette“? Once upon a time, screens could display 24-bits colors, but only 256 at a time in some “hi-res” modes. But that’s not what I’m going to tell you about: I’d rather tell you about the encoding of the palette, and about a somewhat better palette. And also about using *fractions of bits* for more efficient encodings.

The web safe palette divides the RGB color cube in 6×6×6 colors. Each color component, r, g, and b, varies from 0 to 5, levels that are expanded for 24-bits colors to 0x00, 0x33, 0x66, 0x99, 0xcc, 0xff (or 0, 51, 102, 153, 204, 255). If we’re to encode the rgb components as we usually do, by using a fixed number of bits per components, we’d need 9 bits. Indeed, since 2^{2}=4<6<8=2^{3}, we will need 3 bits per component. The encoding would then be

`c=(r<<6)|(g<<3)|b;`

And we could decode using similar bit-oriented operations (using >> and & for masking). The problem with that is that we are using 9 bits and 6×6×6=216, so clearly, we would need at most 8 bits!

Using 3 bits per components would be efficient if each component had 8 levels, but they have only six. We can’t shift by bits for 6 levels. Or can we? Well, let’s first redo the encoding:

`c=36*r+6*g+b;`

The inverse is

`b=c%6;`

`g=(c/6)%6;`

`r=c/36;`

So, if…

`x<<3==x*8==x*2 ^{3}`

then

`x*6==x*2 ^{log26}=x<<log_{2}6`.

Because = works both ways, multiplying by 6 is the same as shifting by log_{2}6≈2.58 bits! Indeed, 3×log_{2}6≈7.75 bits, just as log_{2}216=log_{2}6^{3}=3×log_{2}6!

The 6×6×6 palette uses ≈97% of the 8 bits. Can we use the few extra fractions of bits to squeeze in more colors? You could think, well, if I have 216 colors, that leaves 40 other colors, and I could use the codes from 216 to 255 to encode these new colors, and decode as rgb triplets for codes 0 to 215. Yes, that’s an idea. We could also use a 6×7×6 color cube, because 6×7×6=252, and that very nearly all the range of 8 bits—and we should use 7.98 bits out of 8.

So we will use 6 levels for red, 7 for green (because the eye is more sensitive to green), and 6 for blue. The palette now somewhat lost its (pure) grays because colors are now somewhat off the diagonal.

The code looks pretty much as before, but with new values:

`c=42*r+6*g+b;`

Here, we “shift” green by log_{2}6 bits to make room for blue, and red by log_{2}42=log_{2}7+log_{2}6 to make room for green and blue. Using normal shifts, you would have shifted green by enough position to accommodate the bits for blue, then red by enough to accommodate the bits from blue and green. We did the same here, except with fractional bit shifts in the guise of multiplications.

The inverse is

`b=c%6;`

`g=(c/6)%7;`

`r=c/42;`

Isn’t that neat?

*

* *

How do we reduce 0 to 255 on 0 to 6 (or to 7) and back? A very short program does just that:

int pack(int rgb, int k) { return (rgb*k)/256; } int unpack(int v, int k) { return (v*255)/(k-1); }

The `pack` function transforms the rgb (more exactly, r or g or b) component on the interval 0≤x<1 then on the interval 0≤y<k. The fact we are dividing by 256 ensures that 255 doesn’t give one, therefore k. We want to have a value from 0 to k-1. `unpack` reverses the operation and scales back to 0 to 255. Note that the order of the operation isn’t as natural as they might have been, but to preserve precision—thanks to C/C++ integer arithmetic.

*

* *

The important point here isn’t that the 6×7×6 palette is somewhat better than the 6×6×6 web safe palette; nor even that we use 7.98 bits out of 8 instead of merely 7.75, but that shifting left and multiplying *are the same operation*—just as shifting right *is* dividing. That gives us the possibility of shifting left or right by log-values (some of which are integers).

Very interesting post! I will experiment with this concept.