embedded software boot camp

Effective C Tips #2 – Defining buffer sizes

Sunday, February 22nd, 2009 by Nigel Jones

This is the second in a series of tips on writing what I call effective C. Today I’m addressing something that just about every embedded system has – a buffer whose length is a power of two.

In order to make many buffer operations more efficient, it is common practice to make the buffer size a power of two so that simple masking operations may be performed on them, rather than explicit length checks. This is particularly true of communications buffers where data are received under interrupt. As a result, it is common to see code that looks something like this:

#define RX_BUF_SIZE (32)
static uint8_t Rx_Buf[RX_BUF_SIZE]; /* Receive buffer */

__interrupt void RX_interrupt(void)
{
 static uint8_t RxHead = 0; /* Offset into Rx_Buf[] where next character should be written */
 uint8_t rx_char;

 rx_char = HW_REG;          /* Get the received character */

 RxHead &= RX_BUF_SIZE - 1; /* Mask the offset into the buffer */
 Rx_Buf[RxHead] = rx_char;  /* Store the received char */
 ++RxHead;                  /* Increment offset */
}

The first thing I do to make this code more flexible, is to allow the size of the buffer to be overridden on the command line. Thus my declaration for the buffer size now looks like this:

#ifndef RX_BUF_SIZE
 #define RX_BUF_SIZE (32)
#endif

This is a useful extension because it allows me to control the resources used by the code without having to edit the code per se. However, this flexibility comes at a cost. What happens if someone was to inadvertently pass a non power of 2 buffer size on the command line? Well as it stands – disaster. However, the fix is quite easy.

#ifndef RX_BUF_SIZE
 #define RX_BUF_SIZE (32)
#endif
#define RX_BUF_MASK  (RX_BUF_SIZE - 1)
#if ( RX_BUF_SIZE & RX_BUF_MASK )
 #error Rx buffer size is not a power of 2
#endif

What I’ve done is define another manifest constant, RX_BUF_MASK to be equal to one less than the buffer size. I then test using a bit-wise AND of the two manifest constants. If the result is non zero, then evidently the buffer size is not a power of two and compilation is halted by use of the #error statement. If you aren’t familiar with the #error statement, you’ll find this article I wrote a few years back to be helpful.

Although this is evidently a big improvement, it still isn’t quite good enough. To see, why, consider what happens if RX_BUF_SIZE is zero. Zero is of course a power of two, and so will pass the check. Now most C90 compliant compilers will complain about declaring an array with zero length. However this is legal in C99 compilers in general and GNU compilers in particular. Thus, we also need to protect against this case. Furthermore as Yevheniy was kind enough to point out in the comments, we also have to protect against a buffer size of 1 (as 1 & 0 = 0). So we now get:

#ifndef RX_BUF_SIZE
 #define RX_BUF_SIZE (32)
#endif
#if RX_BUF_SIZE < 2
 #error Rx buffer must be a minimum length of 2
#endif
#define RX_BUF_MASK  (RX_BUF_SIZE - 1)
#if ( RX_BUF_SIZE & RX_BUF_MASK )
 #error Rx buffer size is not a power of 2
#endif

As a final comment, note that the definition of RX_BUF_MASK has an additional benefit in that it can be used in the mask operation in place of (RX_BUF_SIZE – 1), so that my interrupt handler now becomes:

__interrupt void RX_interrupt(void)
{
 static uint8_t RxHead = 0; /* Offset into Rx_Buf[] where next character should be written */
 uint8_t rx_char;

 rx_char = HW_REG;          /* Get the received character */

 RxHead &= RX_BUF_MASK;     /* Mask the offset into the buffer */
 Rx_Buf[RxHead] = rx_char;  /* Store the received char */
 ++RxHead;                  /* Increment offset */
}

So is this effective C? I think so. It’s efficient, it’s flexible and its robustly protected against the sorts of bone headed mistakes that we all make from time to time.

Next Effective C Tip

Previous Effective C Tip

Home

Tags: ,

11 Responses to “Effective C Tips #2 – Defining buffer sizes”

  1. Bruno Santiago says:

    Probably the code you posted is faster and the latency is determinisc, but why not just use a if?++RxHead;if( RxHead >= RX_BUF_SIZE ){ RxHead = 0;}Maybe it´s lack of insinght, but in this case I really don´t see the point of complicating things.

  2. Nigel Jones says:

    Bruno it’s all about speed in this case. If you have a high frequency interrupt, then shaving a couple of op codes off the ISR handler can have a dramatic impact on the CPU utilization. BTW, the code you have suggested also has a potential problem if RX_BUF_SIZE is zero. I say ‘potential’ because most half decent compilers would flag it. The lousy ones would not, and then you’d have a problem.

  3. Miro Samek says:

    Nigel,According to your own teaching (in “writing fast loops” post) the head counter should count down rather than up. Then the comparison for wrap-around would be against zero, which is special and probably as fast as masking the head counter. Additional bonus is that the buffer size does not need to be power of 2 anymore, so you can save some RAM.

  4. Yevheniy says:

    Nigel, when RX_BUF_SIZE is 1 it will also be considered as a valid size by your code. Thus it’s better to check that RX_BUF_SIZE is not 1 as well.

  5. Nigel Jones says:

    Yevheniy – you are quite right. Thanks for pointing this out. I’ve modified the post and of course given you credit for the observation. Now I just have to go and modify my code!

  6. Tom says:

    Zero is most definitely not a power of two.

  7. Faz says:

    Sorry if it’s pedantic.. Do you want to

    s/UART_RX_BUF_SIZE/RX_BUF_SIZE/

    on line 2?

    ps Thanks for this blog.

    Best, Faz

  8. Faz says:

    Hi

    Thanks for this blog. One question about “If the result is non zero, then evidently the buffer size is not a power of two”..

    Is there a simple/obvious way to see why this is true?

    I had to write 3 cases down to convince myself:

    1) Size is power of 2.. that’s a single bit in binary, and less one yields all-ones to the right of that bit => & has no overlap
    2) Size is power of 2 plus some bits set to the right of that bit: Then that bit is set in both arguments so nonzero AND result
    3) Size is power of 2 plus some bits set to the left of that bit: Then those bits are set in both argument so nonzero AND result

    I’d sure be interested in a simpler way to see it’s obvious iff x & (x-1) == 0 then x is power of 2…

    Thanks, Faz

    • Nigel Jones says:

      I expect a mathematician could come up with a formal proof, but I can’t give you one. I’ve used this construct for so many years that it’s been forever since I even thought about it. Evidently it isn’t quite so evident :-). Regardless, I think your approach is along the right lines. To truly convince yourself I’d recommend whipping up a quick program to prove its true – at least for all integers up to 2^64 – 1.

Leave a Reply to Prince George

You must be logged in to post a comment.