6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Which compiler do you use? SDCC? \$\endgroup\$ – harold Oct 23 '18 at 19:18
  • 1
    \$\begingroup\$ @harold Yep, SDCC. \$\endgroup\$ – 比尔盖子 Oct 23 '18 at 19:27
  • 2
    \$\begingroup\$ This isn't a complete example. What is flash, an array of uint8_t? \$\endgroup\$ – Lundin Oct 24 '18 at 8:18
  • 2
    \$\begingroup\$ Since the quality of the posted answers was pretty depressing, I posted one. Please ignore any answer revolving around 16 bit arithmetic and undefined behavior. \$\endgroup\$ – Lundin Oct 24 '18 at 9:03
  • 1
    \$\begingroup\$ @Lundin: Yes, uint8_t. \$\endgroup\$ – 比尔盖子 Oct 25 '18 at 5:44
4
\$\begingroup\$

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;
\$\endgroup\$
  • 1
    \$\begingroup\$ Could we be more promotion-safe by copying lo as-is, then using &= and <<= to operate on it in-place, at no cost in instruction count? Similarly for hi, of course. \$\endgroup\$ – Toby Speight Oct 24 '18 at 9:30
  • 1
    \$\begingroup\$ @TobySpeight Nope, that doesn't make any difference. The different forms of compound assignment are specified to as a &= b; is equivalent to a = a & b; including any implicit promotions. \$\endgroup\$ – Lundin Oct 24 '18 at 9:45
  • 1
    \$\begingroup\$ Fixed post to preserve the 6 middle bits. It seems I misunderstood the requirements. \$\endgroup\$ – Lundin Oct 24 '18 at 11:23
  • 1
    \$\begingroup\$ Thanks for your answer! I knew the principle of using 8-bit as much as possible and avoiding 32-bit, but implicit promotion was really my blind spot. After applying your optimization, I observed a 12-byte reduction in program size! \$\endgroup\$ – 比尔盖子 Oct 25 '18 at 5:47
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ For a simple byte swap, it might be overly pedantic to use constants, since the code is pretty much self-documenting even with magic numbers. Though of course, magic numbers should be avoided in the general case. That being said, your code is using 16 bit arithmetic so it is fairly inefficient for the target CPU. \$\endgroup\$ – Lundin Oct 24 '18 at 9:00
  • 1
    \$\begingroup\$ Clearly if the author thought it needed a comment, it's not at all clear what the random hex values are for. My code makes it clearer even for readers who aren't familiar with bit shifting or 16-bit RGB values. \$\endgroup\$ – user1118321 Oct 25 '18 at 2:01
  • \$\begingroup\$ @user1118321 Also, an important principle of comments is to explain "what is code trying to accomplish", not just "what operation is the code doing". So I think it is preferable to leave some comments about the general idea. Your solution is clever enough to make the technical details obvious, without the need of comment, but leaving a one-liner comment, like /* converts data RGB565 to system BGR565 */ above the code can make the readability of your solution even better. \$\endgroup\$ – 比尔盖子 Oct 25 '18 at 6:15
  • \$\begingroup\$ IMHO, your answer is clearly the best practice in application programming, but for embedded systems, umm... I agree with @Lundin. The amount of bit-wise operations is simply LARGE, because they're literally designed to do them. It will be painstaking and many cases, unnecessary to give a self-explanatory name for EVERY magic number, especially when the readers are excepted to cross-reference the hardware datasheet, and as most of these are often used ONCE, in an adhoc basis. \$\endgroup\$ – 比尔盖子 Oct 25 '18 at 6:15
2
\$\begingroup\$

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);
\$\endgroup\$
  • \$\begingroup\$ Please note that this code stepped on the implicit promotion mine too. eor << 3 gives implicit promotion to int. A positive int XOR anything with 1 gives a negative int. Left shifting a negative int << 8 invokes undefined behavior. The code is vulnerable and should preferably be split in several lines to ensure no subtle promotions are causing havoc. \$\endgroup\$ – Lundin Nov 27 '18 at 13:58
  • \$\begingroup\$ @Lundin "'A positive int XOR anything with 1 gives a negative int." is unclear. some_positive_int ^ 1 always results in a positive. Perhaps provide a specific example of your thought. There is no left shifting of a negative here. \$\endgroup\$ – chux Nov 27 '18 at 14:53
  • \$\begingroup\$ Well in this specific use-case it might not happen, but what I mean that if the MSB of the raw data is set followed by XOR, you might end up changing the sign of the result. Which is why I'd rather write it as ((uint16_t)hi ^ (uint16_t)eor<<3) << 8, to kill all implicit promotions before they occur. \$\endgroup\$ – Lundin Nov 27 '18 at 15:07
  • \$\begingroup\$ @Lundin In this use-case it does not happen - the MSbit is not set. Such general concerns are worthwhile, even if not needed here. When int is 32-bit, ((uint16_t)hi ^ (uint16_t)eor<<3) << 8 does not kill implicit promotions as hoped for ((uint16_t)hi becomes an int before ^ operation and the left shift of 8 is still an int shift. To accomplish signed-less shift, I would avoid casting to sub-unsigned types. E.g. ((unsigned)hi ^ ((unsigned)eor << 3)) << 8) | (lo ^ eor); or even better gentler methods: (1u*hi ^ (1u*eor << 3)) << 8) | (lo ^ eor); \$\endgroup\$ – chux Nov 27 '18 at 15:27
1
\$\begingroup\$

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));
}
\$\endgroup\$
  • \$\begingroup\$ This will perform poorly on an 8-bitter and has many implicit type promotion bugs such as (byte & 0x1f) << 11. Slaughtering 1024 bytes on a small microcontroller is probably not a good idea, even if it is located in flash. There's unlikely any wait states on a Z80, but the amount of flash will be quite limited. \$\endgroup\$ – Lundin Oct 24 '18 at 8:49
  • \$\begingroup\$ @Lundin Performance of the generation of the tables at startup is likely not an issue. The performance of the color = ... code that is executed per pixel is the critical part. The Z80 based TRS-80’s I used in the ‘80s had 16 kBi of ROM and 48kBi of RAM. The tables only take a little over 1% of that memory. Still, I began with the caveat: “if you’ve got 1024 bytes of free space...”. If they don’t, this isn’t the solution for them; if they do, it should be worth consideration. \$\endgroup\$ – AJNeufeld Oct 24 '18 at 14:05
  • \$\begingroup\$ Using 1kib out of 16 kib is quite a lot? \$\endgroup\$ – Lundin Oct 24 '18 at 14:08
  • \$\begingroup\$ @Lundin The OP never stated what kind of memory pressure they were under. They could have lots of free ROM and little free RAM, in which case the tables could be hard-coded in ROM. Or they could have little free ROM and lots of free RAM, in which case generating the tables at startup would be more appropriate. Or they could be tight on memory, in which case a table-based solution is not the appropriate. \$\endgroup\$ – AJNeufeld Oct 24 '18 at 16:38
  • 1
    \$\begingroup\$ Regardless of "implicit type promotion bugs", I like the idea of your answer. I didn't specify storage constraints because not all embedded system has it. In fact, on my system there is more than enough storage. If this is the most critical operation, and other solutions are not possible, the idea of using a lookup table technique is pretty good! \$\endgroup\$ – 比尔盖子 Oct 25 '18 at 5:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.