Ok, I hinted at this on Twitter, so I thought I’d explain properly here.
With the Arduboy’s screen, pixels in sprite are one of three options (assuming you’re not doing trying to create any greys):
- Transparent (that is, the sprite shouldn’t change the colour of the pixel)
The typically way of doing this is to have two bitmaps. Essentially, you are using 2 bits to store each pixel value. But, this is actually inefficient!
Say you draw the first one in white, and then draw the second one over the top in black, the bits correspond to:
Look, we’re encoding black twice! What a waste!
How do you not waste this encoding? (Note, it’s not an extra bit, it’s just an extra option). Well, you have to use it to store part of the next pixel.
So for 1 pixel there’s 3 options. If we encode that by itself, we need to use 2 bits.
For two pixels, there’s 9 options, but we still need to use 4 bits to encode that (as 3 bits only gives us 8 options).
But for 3 pixels, we have 27 options, which only take 5 bits to store. If we were using 2 bits for a pixel, this would take 6 bits. So suddenly we’re saving space!
I did a little test, and it works out you get about as good as you can get when you store pixels in groups of 5. There are 243 options, which can be stored in 8 bits, and would normally take 10 bits. So you’re compressing the data by 80%.
The other reason why this is good is because to decode the data it’s much easier if it’s takes up exactly one byte.
Encoding / Decoding
Ok, so how do you actually use 8 bits to store 5 lots of 3 options? Well, you encode the data as a base3 number.
I’ll explain how that works with base10. Say we want to store the number 573. First we start off with 5. Then multiply that by 10, and add 7 to get 57. Then we multiply that by 10 and add the 3 to get 573. This process works even if the numbers are in binary.
So to store 212 in base3, we start with 2. Then we multiply that by 3, and add 1 to get 21 (in base3). Then we multiply that by 3, and add 2 to get 212 in base3, which is 23 in decimal. If you did this in a computer, you’d 10111 in binary, which is 23 in decimal and 212 in base3.
To go backwards, you do the opposite. You divide by the base, and the remainder is your next-lowest digit. Then you repeat it by dividing by the base again and taking the remainder.
In a processor, dividing/multiplying by 2 is super easy. But dividing by 3 is much slower comparatively. Also, if the code to decode this data is too big, then you won’t actually be saving any space!
But yeah. That’s the idea.