Efficiently swapping the first and last five bits in an unsigned 16-bit integer in C

Question

I'm programming on an 8-bit Z80 embedded system, and encountered a problem. The program needs to render some pixels to the screen. The color is stored as RGB565 format as a 16-bit unsigned integer, but the system color is encoded as BGR565, so I've devised the following code to swap the first and last 5 bits in a uint16_t.

Note that flash is uint8_t *, pointed to the flash memory, and each cell is seen as uint8_t.

/* read lower 8-bit */
uint16_t color = flash[idx];

/* read higher 8 bits */
color |= ((flash[idx + 1]) << 8);

/* 
 * This converts RGB565 to BGR565 by swapping the first/last five bits.
 * For the last five bits, we extract and bitshift it to the beginning,
 * and for the first five bits, we extract and bitstift it to the end.
 * Then, we clear the original first and last five bits, and apply the
 * bitshifted version on it to swap them.
 */
uint16_t tmp = (color & 0x001F) << 11;
tmp |= (color & 0xF800) >> 11;
color &= 0xFFE0 & 0x07FF; /* at least the compiler can optimize this as 0x07e0 */
color |= tmp;

If I'm programming with a standard compiler, like GCC or Clang, I would be just happy about my solution. But this embedded platform only supports relatively primitive compilers without advanced optimization techniques to remove duplicate computations.

In fact, the best code optimization to this problem is "no code", just make the stored format to be consistent with the system format. But using it as a chance of learning, I'm curious to know if there is a faster way to do the computation above in pure C, especially when we're dealing with a particularly slow machine, like a Z80.

Answer 1

Programming 8-bitters in C is tricky, particularly when dealing with antique ones like Z80. The things you absolutely must consider are:

• Keep to 8 bit arithmetic whenever possible.
• Ensure that no bitwise arithmetic is done on signed int types. This means that you need to understand the common Implicit type promotion rules of C.
• 32 bit arithmetic should be avoided like the plague. And let's not even mention floating point.

If you don't keep the above in mind, then the theoretic efficiency of the algorithm be damned. Thus you cannot allow a PC programmer to design it, because they don't understand how an 8-bit MCU works.

---

Regarding your posted code:

• It suffers from using lots of 16 bit arithmetic, that the compiler cannot likely optimize well.

• ((flash[idx + 1]) << 8); invokes undefined behavior, if flash is an uint8_t with the MSB set. This is a bug caused by implicit integer promotion to int.

• Using signed hex literals on a 8/16 bit MCU is dangerous, because up to 0x7FFF they are of type int, but above that they are of type unsigned int. Therefore, you should make a habit of always appending an u/U suffix to them.

Assuming that flash is an array of const uint8_t corresponding to something in flash memory, and assuming that the 6 middle bits should be preserved, not zero-out, then you should do something like this:

// assuming Z80 Little Endian:
uint8_t lo = flash[idx];
uint8_t hi = flash[idx+1];

uint8_t lo_shift = (lo & B_MASK) << 3;
uint8_t hi_shift = (hi & R_MASK) >> 3;

lo = (lo & 0xE0u) | hi_shift;
hi = (hi & 0x07u) | lo_shift;

uint16_t color = ((uint16_t)hi<<8) | lo;

This will allow the compiler to perform as much arithmetic as possible on 8 bit integers. There are implicit promotions to int, but such promotions are not dangerous, as we don't shift data in/out of the sign bit of a 16 bit int. And the u suffix will kill off any accidental promotions, since it guarantees uint16_t in case of 16 bit arithmetic.

To get rid of "magic numbers":

#define R_MASK 0xF8u
#define B_MASK 0x1Fu

uint8_t lo = flash[idx];
uint8_t hi = flash[idx+1];

uint8_t lo_shift = (lo & B_MASK) << 3;
uint8_t hi_shift = (hi & R_MASK) >> 3;

lo = (lo & (uint8_t)~B_MASK) | hi_shift;
hi = (hi & (uint8_t)~R_MASK) | lo_shift;

uint16_t color = (uint16_t)hi << 8 | lo;

Answer 2

If it were me, I'd remove the magic numbers and use named constants. I feel like this is a little clearer:

const uint16_t kBlueChannelMask = 0x001F;
const uint16_t kRedChannelMask = 0xF800;
const uint16_t kGreenChannelMask = 0x7e0;
const uint16_t kMoveBlueToRed = 11;
const uint16_t kMoveRedToBlue = 11;

uint16_t tmp = (color & kBlueChannelMask) << kMoveBlueToRed;
tmp |= (color & kRedChannelMask) >> kMoveRedToBlue;
color &= kGreenChannelMask;
color |= tmp;

With this you can likely remove the large comment explaining the code, and you can remove the comment explaining the green channel mask.

Answer 3

As a code alternative to @Lundin good answer: Use ^.

#define LO_MASK 0x1Fu

uint8_t lo = flash[idx];
uint8_t hi = flash[idx+1];
uint8_t eor = (lo & LO_MASK) ^ (hi >> 3);
uint16_t color = ((uint16_t)(hi ^ (eor << 3)) << 8)  |  (lo ^ eor);

Answer 4

Bit shifting and masking is annoying. I'm counting 9 and/or/shift-operations in your implementation.

If you've got 1024 bytes of free space available, here is an implementation with only 1 or-operation, but with 2 extra memory lookups:

First, construct the conversion tables. These can be hard-coded.

#define L(x) (uint16_t)((x & 0xE0) | ((x & 0x1f) << 11))
#define H(x) (uint16_t)(((x & 0x07) << 8 ) | ((x & 0xF8) >> 3))

const uint16_t low[256] = {
    L(0x00), L(0x01), L(0x02), L(0x03) ... L(0x0F),
    L(0x10), L(0x11), L(0x12), L(0x13) ... L(0x1F),
       :        :        :        :           :
    L(0xF0), L(0xF1), L(0xF2), L(0xF3) ... L(0xFF)
};

const uint16_t high[256] = {
    H(0x00), H(0x01), H(0x02), H(0x03) ... H(0x0F),
    H(0x10), H(0x11), H(0x12), H(0x13) ... H(0x1F),
       :        :        :        :           :
    H(0xF0), H(0xF1), H(0xF2), H(0xF3) ... H(0xFF)
};

#undef L
#undef H

When you read the low & high bytes, look up the corresponding bit-swapped values, then OR them together.

uint16_t color = low[flash[idx]] | high[flash[idx+1]];

This works as follows:

flash[idx+0]  -->  GGGR RRRR  -->  RRRR R___ GGG_ ____
flash[idx+1]  -->  BBBB BGGG  -->  ____ _GGG ___B BBBB
    OR'd                      -->  RRRR RGGG GGGB BBBB

Whether the 2 extra memory lookup cycles are faster than the extra 8 masking, shifting and or'ing operations, you'll have to profile to determine.

As opposed to hard-coding the tables, you could generate them at startup.

for (int byte=0; byte<256; byte++) {
   low[byte] = (uint16_t)((byte & 0xE0) | ((byte & 0x1f) << 11));
   high[byte] = (uint16_t)(((byte & 0x07) << 8 ) | ((byte & 0xF8) >> 3));
}