The 6×7×6 palette (Coding with fractions of bits, Part I)

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 22=4<6<8=23, 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*23

then

x*6==x*2log26=x<<log26.

Because = works both ways, multiplying by 6 is the same as shifting by log26≈2.58 bits! Indeed, 3×log26≈7.75 bits, just as log2216=log263=3×log26!

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 log26 bits to make room for blue, and red by log242=log27+log26 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).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: