Bit padding and byte stuffing

Determined not to let the fact that the LCD still refuses to switch on stop us, we've been pretty busy over the last few days. Ok, the LCD just sits there, blank and lifeless. But one day it will flicker into life. And when it does, we need to be able to send data to it. So we'll just continue, unabashed, as if everything was working anyway.

So now we're looking at data storage and sending data to the LCD.
Our preferred method is through a 16-bit parallel data bus. The LCD typically uses 18-bit colours for the display, but internally can convert a 5-bit colour value into 6-bits for the red and blue channels (it simply copies the most significant bit into the least significant bit place).



This means that we need a piece of software that can take 24-bit images and convert them to 16-bit. That's easy enough. But we need to make sure that said software stores the data in R5-G6-B5 format. Hmmm. Not quite so easy.

Then we started to think about numbers - a 320x240 image takes up 76,800 bytes. Since we're using 16-bit colour values (i.e. two bytes per pixel) this means a whopping 153,600 bytes for a full screen image. Wow!
So we've opted to use "palletized" images - a bit like GIFs: create a palette of 256 colours, then use a single-byte-per-pixel to point to the palette index. This will keep full-screen images down to *just* 76,800 bytes (plus 512 bytes for the palette).
Storing such an image in Flash memory means taking up about 302 "pages" of data (one page = 256 bytes). And our 4Mbit memory chip has 2,048 pages, so each full-screen image will take up just under 15% of the available memory! It's probably best to keep the number of full screen bitmaps down to a minimum!

We've discussed sprite/tile-based approaches and will investigate these further, but for now, we're concentrating on storing and displaying a full-screen image, in R5-G6-B5 format. So here we go:

Each pixel in the source image is interrogated and it's full colour (24-bit) value is retrieved. This colour value is split into its red, green and blue components (we use the fantastic Freeimage DLL for all our image manipulation tasks.)

Each red, green and blue element of the pixel colour is a single byte (8-bits).
We want a 5-bit value for red, a 6-bit value for green and a five-bit value for blue. To achieve this, we simply bit-shift the red value RIGHT three times (the same can be achieved by dividing by 2, three times, ignoring any remainder values). So a red value of, for example, 186 is binary 10111010. We can see visually that bit-shifting this three positions to the right should give us xxx10111.
Divide by two, three times (or divide by 2^3 = 8) and we get:
186 / 2 = 93
93 / 2 = 46 (ignore the 0.5)
46 / 2 = 23.

The binary representation of 23 is 10111. Perfect!
(if you're not confident with decimal to binary conversions, a quick Google search should get you started, or try this link.)

We repeat this process for the blue element (bit-shift right three places)
For green, for only need to bit-shift two places right (or divide by 4) since we want to keep 6 bits for the green channel. (Why six? Because the LCD specification says a 16-bit interface is mapped to a R5-G6-B5 colour value).

If you look closely at the RGB breakdown (above), you'll also see that the green 6-bit value is split over the two bytes. Bugger.
So we need the 5-bit red value to occupy the upper 5 bits of the first byte, followed by the upper three bits of the green colour. Now listen up, this is where it gets tricky: We want the lower three bits of the green colour to occupy the upper three bits of the second byte. Then the five bits that make up the blue colour to occupy the lower five bits of the second byte. Got that?

Here's what we do:
Bit shift LEFT the red colour value, three times
(yes, we could have just used bit-masking earlier, but I'm trying explain a process here, so bear with it!). To shift right, we divide by 2. It makes sense that to bit-shift left we multiply by two:

The red value xxx10111 becomes 10111000

Let's say we have a green value 42, binary xx101010
We want the first three bits to take the place of the last three zeros in the red colour value. How do we do this? As before, bit-shift right, three-times.
Our green value xx101010 becomes xxxxx101
Now simply add this value to the red value.
For bit-wizards, you can perform an OR operation on the two binary values, the result is the same:

10111000 OR 00000101 = 10111101
184 + 5 = 189
10111101 = 189. Perfect!

The easiest way to get the last three bits of the green value is to use bit-masking.
Simply put, bit-masking compares two values, on a binary level, and where two bits are both set, the resulting bit is set (value=1) otherwise is not set (value=zero).
Here's an example:

1011 AND 01110

first bit of first value: 1, first bit of second value: 0, result = 0
second bit of first value: 0, second bit of second value: 1, result = 0
third bit of first value: 1, third bit of second value: 1, result = 1
fourth bit of first value: 1, fourth bit of second value: 0, result = 0

So 1001 AND 01110 = 0010

If we want to recover just the last three bits of a value, we create a "mask" made up of the bits we want to keep. You might even call it a "bit-mask". The bitmask for the last three digits is 00000111

So, back to our RGB colours - we want the last three bits of the original green value 42, binary xx101010:

00101010 AND 00000111 = 00000010

The first three bits (the ones we're interested in) are: xxxxx010
But we need these three bits to be the first three bits in the second byte value.
This means, as before, bit-shifting LEFT, five-times (multiply by 2, five times- or multiply by 32)

We can see that bit-shifting the value left should give us 01000000
By a happy coincidence, the original value 010 = 2
2 x 2^5 = 64
The binary representation of 64 is 01000000. Perfect!

So we now have the lower three bits of our original green value in the upper three bits of the second byte. All that remains to do is add in the blue bits. As before, a bitwise OR statement would achieve this - or we could simply add the blue value to this new second byte value.

Let's say our blue value is 11, binary 01011.
01000000 OR xxx01011 = 01001011
64 + 11 = 75
75 in binary = 01001011

Right. That's one 24-bit pixel stuffed into a 16-bit (2-byte) value.
Only 76,799 more to go!