Archive for the ‘Effective C/C++’ Category

Replacing nested switches with multi-dimensional arrays of pointers to functions

Monday, March 17th, 2014 Nigel Jones

It’s been way too long since I’ve written a blog post. To those kind souls that have written to inquire if I’m still alive and kicking – thank you.  The bottom line is that there simply aren’t enough hours in the day. Anyway in an effort to get back in the groove so to speak, I thought I’d answer an email from Francois Alibert who wrote to ask how to replace a nested switch statement with a multi-dimensional array of pointers to functions. Here’s a program that illustrates his conundrum:

#include <stdint.h>
#include <stdio.h>

typedef enum 
{State1, State2, State3, Last_State}
MainState_t;

typedef enum 
    {SubState1, SubState2, SubState3, SubState4, SubState5, SubState6, Last_SubState}
SubState_t;

void demo(MainState_t State,  SubState_t SubState);

/*     Functions called from nested switch statement. 
    First digit is main state, second digit is substate */

void fn11(void);
void fn16(void);

void fn24(void);

void fn32(void);
void fn33(void);
void fn35(void);

void main(void)
{
    MainState_t main_state;
    SubState_t sub_state;
    
    for (main_state = State1; main_state < Last_State; main_state++)
    {
        for(sub_state = SubState1; sub_state < Last_SubState; sub_state++)
        {
            demo(main_state, sub_state);
        }
    }
}

void demo(MainState_t State,  SubState_t SubState)
{
    switch (State)
    {
        case State1:
            switch (SubState)
            {
                case SubState1:
                fn11();
                break;
                
                case SubState6:
                fn16();
                break;
            
                default:
                break;
            }
        break;

        case State2:
            switch (SubState)
            {
                case SubState4:
                fn24();
                break;
    
                default:
                break;
            }
        break;
    
        case State3:
        {
            switch (SubState)
            {
                case SubState2:
                fn32();
                break;
                
                case SubState3:
                fn33();
                break;                
                
                case SubState5:
                fn35();
                break;
    
                default:
                break;
            }
        }
        break;
        
        default:
        break;
    }
}

void fn11(void)
{
    puts("State 1, substate 1");
}

void fn16(void)
{
    puts("State 1, substate 6");
}

void fn24(void)
{
    puts("State 2, substate 4");
}

void fn32(void)
{
    puts("State 3, substate 2");
}

void fn33(void)
{
    puts("State 3, substate 3");
}

void fn35(void)
{
    puts("State 3, substate 5");
}

The key points are that we have nested switch statements and the substate is sparse. That is the number of substates for main state 1 is different to that of the substates for main state 2 and so on. If you’ve ever been in the situation of having to write a nested state machine like this, you’ll rapidly find that the code becomes very unwieldy. In particular functions many of hundreds of lines long with break statements all over the place are the norm. The result can be a maintenance nightmare. Of course if you end up going to three levels, then the problem compounds. Anyway, before looking at a pointer to function implementation, here’s the output from the above code:

State 1, substate 1
State 1, substate 6
State 2, substate 4
State 3, substate 2
State 3, substate 3
State 3, substate 5

In addition, using IAR’s AVR compiler, the code size with full size optimization is 574 bytes and the execution time is  2159 cycles, with the bulk of the execution time taken up by the puts() call.

Let’s now turn this into a pointer to function implementation. The function demo becomes this:

void demo(MainState_t State,  SubState_t SubState)
{
    static void (* const pf[Last_State][Last_SubState])(void) = 
    {
        {fn11, fnDummy, fnDummy, fnDummy, fnDummy, fn16},
        {fnDummy, fnDummy, fnDummy, fn24, fnDummy, fnDummy},
        {fnDummy, fn32, fn33, fnDummy, fn35, fnDummy}
    };
    
    if ((State < Last_State) && (SubState < Last_SubState))
    {
        (*pf[State][SubState])();
    }
}

Note that the empty portions of the array are populated with a call to fnDummy(), which as its name suggests is a dummy function that does nothing. You can of course put a NULL pointer in the array, and then extract the pointer, check to see if its non-NULL and call the function, However in my experience its always faster to just call a dummy function.

So how does this stack up to the nested switch statements? Well as written, the code size has increased to 628 bytes and cycles to 2846. This is a significant increase in overhead. However the code is a lot more compact, and in my opinion dramatically more maintainable. Furthermore, if you can guarantee by design that the parameters passed to demo() are within the array bounds (as is the case with this example), then you can arguably dispense with the bounds checking code. In which case the code size becomes 618 bytes and the execution time 2684 cycles. It’s your call as to whether the tradeoff is worth it.

 

Optimizing for the CPU / compiler

Sunday, June 3rd, 2012 Nigel Jones

It is well known that standard C language features map horribly on to the architecture of many processors. While the mapping is obvious and appalling for some processors (low end PICs, 8051 spring to mind), it’s still not necessarily great at the 32 bit end of the spectrum where processors without floating point units can be hit hard with C’s floating point promotion rules. While this is all obvious stuff, it’s essentially about what those CPUs are lacking. Where it gets really interesting in the embedded space is when you have a processor that has all sorts of specialized features that are great for embedded systems – but which simply do not map on to the C language view of the world. Some examples will illustrate my point.

Arithmetic vs. Logical shifting

The C language does of course have support for performing shift operations. However, these are strictly arithmetic shifts. That is when bits get shifted off the end of an integer type, they are simply lost. Logical shifting, sometimes known as rotation, is different in that bits simply get rotated back around (often through the carry bit but not always). Now while arithmetic shifting is great for, well arithmetic operations, there are plenty of occasions in which I find myself wanting to perform a rotation. Now can I write a rotation function in C – sure – but it’s a real pain in the tuches.

Saturated addition

If you have ever had to design and implement an integer digital filter, I am sure you found yourself yearning for an addition operator that will saturate rather than overflow. [In this form of arithmetic, if the integral type would overflow as the result of an operation, then the processor simply returns the minimum or maximum value as appropriate].  Processors that the designers think might be required to perform digital filtering will have this feature built directly into their instruction sets.  By contrast the C language has zero direct support for such operations, which must be coded using nasty checks and masks.

Nibble swapping

Swapping the upper and lower nibbles of a byte is a common operation in cryptography and related fields. As a result many processors include this ever so useful instruction in their instruction sets. While you can of course write C code to do it, it’s horrible looking and grossly inefficient when compared to the built in instruction.

Implications

If you look over the examples quoted I’m sure you noticed a theme:

  1. Yes I can write C code to achieve the desired functionality.
  2. The resultant C code is usually ugly and horribly inefficient when compared to the intrinsic function of the processor.

Now in many cases, C compilers simply don’t give you access to these intrinsic functions, other than resorting to the inline assembler. Unfortunately, using the inline assembler causes a lot of problems. For example:

  1. It will often force the compiler to not optimize the enclosing function.
  2. It’s really easy to screw it up.
  3. It’s banned by most coding standards.

As a result, the intrinsic features can’t be used anyway. However, there are embedded compilers out there that support intrinsic functions. For example here’s how to swap nibbles using IAR’s AVR compiler:

foo = __swap_nibbles(bar);

There are several things to note about this:

  1. Because it’s a compiler intrinsic function, there are no issues with optimization.
  2. Similarly because one works with standard variable names, there is no particular likelihood of getting this wrong.
  3. Because it looks like a function call, there isn’t normally a problem with coding standards.

This then leads to one of the essential quandaries of embedded systems. Is it better to write completely standard (and hence presumably portable) C code, or should one take every advantage of neat features that are offered by your CPU (and if it is any good), your compiler?

I made my peace with this decision many years ago and fall firmly into the camp of take advantage of every neat feature offered by the CPU / compiler – even if it is non-standard. My rationale for doing so is as follows:

  1. Porting code from one CPU to another happens rarely. Thus to burden the bulk of systems with this mythical possibility seems weird to me.
  2. End users do not care. When was the last time you heard someone extoll the use of standard code in the latest widget? Instead end users care about speed, power and battery life. All things that can come about by having the most efficient code possible.
  3. It seems downright rude not to use those features that the CPU designer built in to the CPU just because some purist says I should not.

Having said this, I do of course understand completely if you are in the business of selling software components (e.g. an AES library), where using intrinsic / specialized instructions could be a veritable pain. However for the rest of the industry I say use those intrinsic functions! As always, let the debate begin.

 

Effective C Tip #9 – use #warning

Thursday, September 1st, 2011 Nigel Jones

This is the ninth in a series of tips on writing effective C. Way back in 1999 I wrote an article for Embedded Systems Programming concerning the #error directive. If you aren’t particularly familiar with #error, then I suggest you read the article. While the #error directive has remained one of my most popular tools, I have become an equally big fan of #warning.

Before I delve into the uses of #warning, I must warn you (if you would pardon the pun) that #warning is a non standard directive. However it is supported by IAR, GCC, Microchip’s C18 compiler, Hi-Tech and probably a whole raft of other vendors. In other words, it’s pretty standard for a non-standard feature.

The use of #warning is simple enough:

#warning This is a warning

This will result in the compiler issuing a warning with the text ‘This is a warning’ printed to stderr. Please note that, just as for #error, there is *no* requirement that the text be in quotes. If you insist on putting quotes around the text, then they will be printed to stderr as well.

With the syntax out of the way, here’s some of the ways that I use #warning.

Protecting Incomplete Code

Very often when I’m coding, I like to get the big picture in place without worrying about the minutiae of the implementation details.  As a result I end up with functions or loop bodies that are incomplete. In these cases I simply add a #warning to alert me to the issue. For example

void foo(void)
{
#warning To be completed
}

Thus what happens now is that whenever I compile the module, I get a warning (i.e. reminder) that there is something important still to be done.

Commenting Out Code

I *never* comment code out anymore as part of the debugging process, as it is simply too easy to forget that the code has been removed. Instead I use this construct:

void foo(void)
{
# if 0
   /* Code to be temporarily removed is here */
#else
#warning Temporary debug construct. Fix me!
   /* Experimental code goes here */
#endif
}

In this case whenever I compile the module, I get a warning (i.e. reminder) that I have some experimental code in the image.

The Key Final Step

While the above are useful constructs, the real power of #warning comes if you configure your compiler to treat warnings as errors for the release build. If you do this and you have inadvertently left incomplete or debug code in the image, then your compilation will fail. In short, this technique will guarantee that you never release code that includes / excludes code that shouldn’t / should be there. That’s effective C.

Previous Tip

 

 

Configuring hardware – part 3

Wednesday, January 26th, 2011 Nigel Jones

This is the final part in a series on configuring the hardware peripherals in a microcontroller. In the first part I talked about how to set / clear bits in a configuration register, and in the second part I talked about putting together the basic framework for the driver. When I finished part 2, we had got as far as configuring all the bits in the open function. It’s at this point that things get interesting. In my experience the majority of driver problems fall into three areas:

  1. Failing to place the peripheral into the correct mode.
  2. Getting the clocking wrong.
  3. Mishandling interrupts.

I think most people tend to focus on the first item. Personally I have learned that it’s usually better to tackle the above problems in the reverse order.

Mishandling interrupts

Almost all peripheral drivers need interrupt handlers, and these are often the source of many problems.  If you have followed my advice, then at this stage you should have a skeleton interrupt handler for every possible interrupt vector that the peripheral uses.  You should also have an open and close function. A smart thing to do at this stage is to download your code to your debug environment. I then place a break-point on every interrupt handler and then I call  the open function. If the open function merely configures the peripheral, yet does not enable it, then presumably no interrupts should occur. If they do, then you need to find out why and fix the problem.

At this point I now add just enough code to each interrupt handler such that it will clear the source of the interrupt and generate the requisite interrupt acknowledge. Sometimes this is done for you in hardware. In other cases you have to write a surprising amount of code to get the job done. I strongly recommend that you take your time over this stage as getting an interrupt acknowledge wrong can cause you endless problems.

The next stage is to write the enable function, download the code and open and enable the peripheral. This time you need to check that you do get the expected interrupts (e.g. a timer overflow interrupt) and that you acknowledge them correctly. Just as importantly you also need to check that you don’t get an unexpected interrupt (e.g. a timer match interrupt). On the assumption that all is well, then you can be reasonably confident that  there are no egregious errors in your setup of interrupts. At this point you will probably have to further flesh out the interrupt handlers in order to give the driver some limited functionality. Although I’m sure you’ll be tempted to get on with the problem at hand, I recommend that you don’t do this, but rather write code to help tackle the next problem – namely that of clocking verification.

Clocking

Most peripherals use a clock source internal to the microprocessor. Now modern processors have multiple clock domains, PLL based frequency multipliers, and of course multi-level pre-scalars. As a result it can be a real nightmare trying to get the correct frequency to a peripheral. Even worse it is remarkably easy to get the approximately correct frequency to a peripheral. This issue can be a real problem with asynchronous communications links where a 1% error in frequency may be OK with one host and fail with another. As a result I now make it a rule to always try and verify that I am indeed clocking a peripheral with the correct frequency. To do this, there is no substitute for breaking out the oscilloscope or logic analyzer and measuring something. For timers one can normally output the signal on a port pin (even if this is just for verification purposes). For communications links one can simply set up the port to constantly transmit a fixed pattern. For devices such as A2D converters I usually have to resort to toggling  a port pin at the start and end of conversion. Regardless of the peripheral, it’s nearly always worth taking the time to write some code to help you verify that the peripheral is indeed being clocked at the correct frequency.

When you are doing this, there are a couple of things to watch out for:

  1. If your processor has an EMI reduction mode, then consider turning it off while performing clocking measurements. The reason for this is that ‘EMI reduction’ is actually achieved by dithering (quasi randomly varying) the clock frequency. Clearly a randomly varying clock isn’t conducive to accurate frequency measurements.
  2. Make sure that your system is indeed being clocked by the correct source. I mention this because some debuggers can provide the clock to the target.

Finally, if you find that you have an occasional problem with a peripheral, then checking that the clocking is precise is always a good place to start.

Mode

At this stage you have done the following:

  1. Considered every bit in every register in your open function.
  2. Verified that you have interrupts set up correctly.
  3. Written the enable function and at least part of the interrupt handler(s).
  4. Verified that you have the correct frequency clocks going to the peripheral.

You should now complete writing the driver. This is where you write the bulk of the application specific code. Clearly this part is highly application specific. Notwithstanding this, I can offer one piece of advice. Probably the single biggest mistake that I have made over the years is to assume that because the driver ‘works’ that it must be correct. I will give you a simple example to demonstrate what I mean.

It’s well known that the popular SPI port found on many devices can operate in one of four modes (often imaginatively called Mode0, Mode1, Mode2 & Mode3). These modes differ based on the phase relationship of the clock and data lines and whether the data are valid on the rising or falling edge of the clock. Thus it’s necessary to study the data sheet of the SPI peripheral to find out its required mode. Let’s assume that after studying the data sheet you conclude that Mode2 operation is called for – and you implement the code and it works. If you then walk away from the code then I humbly suggest you are asking for it. The reason is that it’s possible that a peripheral will ‘work’ in Mode 2, even though it should be operated in Mode 3. The peripheral ‘works’ in Mode 2 even though you are right on the edge of violating the various required setup and hold times. A different temperature or a different chip lot and your code will fall over. It’s for this reason that I strongly recommend that you break out the logic analyzer and carefully compare the signals to what is specified in the data sheet. There is nothing quite like comparing waveforms to what is in the data sheet to give you a warm fuzzy feeling that the driver really is doing its job correctly.

Final Thoughts

Driver writing is hard. Engineers that can take on this task and write clean, fast and correct drivers in a timely manner are immensely valuable to organizations. Thus even if you cringe at the thought of having to write a device driver, you might want to put the effort into learning how to do it – your career will thank you!

Configuring hardware – part 2.

Wednesday, December 15th, 2010 Nigel Jones

This is the second in a series on configuring the hardware peripherals in a microcontroller. In the first part I talked about how to set / clear bits in a configuration register.  Now while setting bits is an essential part of the problem, it is by no means the most difficult task. Instead the real problem is this. You need to configure the peripheral but on examining the data sheet you discover that the peripheral has twenty registers, can operate in a huge number of modes and has multiple interrupt sources. To compound the difficulty, you may not fully understand the task the peripheral performs – and the data sheet appear to have been written by someone who has clearly never written a device driver in their life. If this sounds a lot like what you have experienced, then read on!

When I first started working in embedded systems, I used to dread having to write a device driver. I knew I was in for days, if not weeks of anguish trying to make the stupid thing work. Today I can usually get a peripheral to do what I want with almost no heartache – and in a fraction of the time it used to take me. I do this by following a standard approach that helps minimize various problems that seem to crop up all the time in device drivers. These problems are as follows:

  1. Setting the wrong bits in a register
  2. Failing to configure a register at all.
  3. Setting the correct configuration bits – but in the wrong temporal order.
  4. Interrupts incorrectly handled.

To help minimize these types of problems, this is what I do.

Step 0 – Document *what* the driver is supposed to do

This is a crucial step. If you can’t write in plain English (or French etc) what the driver is supposed to do then you stand no chance of making it work correctly.  This is a remarkably difficult thing to do. If you find that you can’t succinctly and unambiguously describe the driver’s functionality then attempting to write code is futile. I typically put this explanation in the module header block where future readers of the code can see it. An explanation may look something like this.

This is a serial port driver. It is intended to be used on an RS232 line at 38400 baud, 8 data bits, no parity, one stop bit. The driver supports CTS / RTS handshaking. It does not support Xon / Xoff handshaking.

Characters to be transmitted are buffered and sent out under interrupt. If the transmit buffer fills up then incoming characters are dropped.

Characters are received under interrupt and placed in a buffer. When the receive buffer is almost full, the CTS line is asserted. Once the receive buffer has dropped below the low threshold, CTS is negated. If the host ignores the CTS line and continues to transmit then characters received after the receive buffer is full are discarded.

As it stands, this description is incomplete; for example it doesn’t say what happens if a receiver overrun is detected. However you should get the idea.

Incidentally I can’t stress the importance of this step enough. This was the single biggest breakthrough I made in improving my driver writing. This is also the step that I see missing from almost all driver code.

Step 1 – Create standard function outlines

Nearly all drivers need the following functions:

  1. Open function. This function does the bulk of the peripheral configuration, but typically does not activate (enable) the peripheral.
  2. Close function. This is the opposite of the open function in that it returns a peripheral to its initial (usually reset) condition. Even if your application would never expect to close a peripheral it is often useful to write this function as it can deepen your understanding of the peripheral’s functionality.
  3. Start function. This function typically activates the peripheral. For peripherals such as timers, the start function is aptly and accurately named. For more complex peripherals, the start function may be more of an enable function. For example a CAN controller’s start function may start the CAN controller listening for packets.
  4. Stop function. This is the opposite of the start function. Its job is to stop the peripheral from running, while leaving it configured.
  5. Update function(s). These function(s) are highly application specific. For example an ADC peripheral may not need an update function. A PWM channel’s update function would be used to update the PWM depth. A UART’s update function would be the transmit function. In some cases you may need multiple update functions.
  6. Interrupt handler(s). Most peripheral’s need at least one interrupt handler. Even if you aren’t planning on using an interrupt source, I strongly recommend you put together a function outline for it. The reason will become clear!

At this stage, your driver looks something like this:

/*
 Detailed description of what the driver does goes here
*/

void driver_Open(void)
{
}

void driver_Close(void)
{
}

void driver_Start(void)
{
}

void driver_Stop(void)
{
}

void driver_Update(void)
{
}

__interrupt void driver_Interrupt1(void)
{
}

__interrupt void driver_Interrupt2(void)
{
}

Step 2 – Set up power, clocks, port pins

In most modern processors, a peripheral does not exist in isolation. Many times peripherals need to be powered up, clocks need to routed to the peripheral and port pins need to be configured. This step is separate from the configuration of the peripheral. Furthermore documentation on these requirements is often located in non-obvious places – and thus this step is often overlooked. This is an area where I must give a thumbs-up to NXP. At the start of each of their peripherals is a short clear write up documenting the ancillary registers that need to be configured for the peripheral to be used. An example is shown below:

Basic Configuration Steps for the SSP

Personally, I usually place the configuration of these registers in a central location which is thus outside the driver. However there is also a case for placing the configuration of these registers in the driver open function. I will address why I do it this way in a separate blog post.

Step 3 – Add all the peripheral registers to the open function

This step is crucial. In my experience a large number of driver problems come about because a register hasn’t been configured. The surest way to kill this potential problem is to open up the data sheet at the register list for the peripheral and simply add all the registers to the open function. For example, here is the register list for the SSP controller on an NXP ARM processor:

Ten registers are listed.  Even though one register is listed as read only, I still add it to the driver_Open function as I may need to read it in order to clear status flags. Thus my open function now becomes this:

void driver_Open(void)
{
 SSP0CR0 = 0;
 SSP0CR1 = 0;
 SSP0DR = 0;
 SSP0SR;            /* Status register - read and discard */
 SSP0CPSR = 0;
 SSP0IMSC = 0;
 SSP0RIS = 0;
 SSP0MIS = 0;
 SSP0ICR = 0;
 SSP0DMACR = 0;
}

At this stage all I have done is ensure that my code is at least aware of the requisite registers.

Step 4 – Arrange the registers in the correct order

For many peripherals, it is important that registers be configured in a specific order. In some cases a register must be partially configured, then other registers must be configured, and then the initial register must be completely configured. There is no way around this, other than to read the data sheet to determine if this ordering exists. I should note that the order that registers appear in the data sheet is rarely the order in which they should be configured. In my example, I will assume that the registers are correctly ordered.

Step 5 – Write the close function

While manufacturer’s often put a lot of effort into telling you how to configure a peripheral, it’s rare to see information on how to shut a peripheral down. In the absence of this information, I have found that a good starting point is to simply take the register list from the open function and reverse it. Thus the first pass close function looks like this:

void driver_Close(void)
{
 SSP0DMACR = 0;
 SSP0ICR = 0;
 SSP0MIS = 0;
 SSP0RIS = 0;
 SSP0IMSC = 0;
 SSP0CPSR = 0;
 SSP0DR = 0;
 SSP0CR1 = 0;    
 SSP0CR0 = 0;
}

Step 6 – Configure the bits in the open function

This is the step where you have to set and clear the bits in the registers. If you use the technique that I espoused in part 1 of this series, then your open function will now explicitly consider every bit in every register.  An example of a partially completed open function is shown below:

void driver_Open(void)
{
 SSP1CR0 = ((4 - 1) << 0) |    /* DSS = 4 bit transfer (min value allowed) */
            (0U << 4) |        /* SPI format */
            (1U << 6) |        /* CPOL = 1 => Clock idles high */
            (1U << 7) |        /* CPHA = 1 => Output data valid on rising edge */
            (5U << 8);         /* SCR = 5 to give a division by 6 */

 SSP1CR1 =  (0U << 0) |        /* LPM = 0 ==> no loopback mode */
            (1U << 1) |        /* SSE = 1 ==> SSP1 is enabled */
            (0U << 2) |        /* MS = 0 ==> Master mode */
            (0U << 3);         /* SOD = 0 (don't care as we are in master mode */

 SSP0DR = 0;
 SSP0SR;            /* Status register - read and discard */
 SSP0CPSR = 0;
 SSP0IMSC = 0;
 SSP0RIS = 0;
 SSP0MIS = 0;
 SSP0ICR = 0;
 SSP0DMACR = 0;
}

Clearly this is the toughest part of the exercise. However at least if you have followed these steps, then you are guaranteed not to have made an error of omission.

This blog posting has got long enough. In the next part of this series, I will address common misconfiguration issues, interrupts etc.