In Defense of the C99 Boolean Type

April 9, 2011 | Embedded Software

I really like a lot of the features in C99, including the new bool type. A lot of people have dismissed it as syntactic sugar or language bloat, but it does bring something new to the table.

First, how do you use bool? The best way is to include the stdbool.h header, which defines the bool type and the constants true and false as follows:

#define bool    _Bool
#define true 1
#define false 0

To maintain compatibility, the actual new keyword added to the language was _Bool. stdbool.h then defines a macro that allows you to use the slightly friendlier bool type. That way code that defines its own, incompatible bool type can continue to work by just not including stdbool.h.

So far, there's nothing special here. The real excitement is buried in the ISO C99 standard. Here's section 6.3.1.2 of the n1256 ISO committee draft (yes, I'm too cheap to shell out $40 for the offical version of the standard).

When any scalar value is converted to _Bool, the result is 0 if the value compares equal to 0; otherwise, the result is 1

Exciting, isn't it? Before the days of C99, programmers would typically represent boolean values as an int. That would cause all kinds of problems such as:

if( somevalue == TRUE )
{
/* do something */
}

This would cause unexpected behavior because TRUE would typically be defined to be 1, but somevalue wasn't guaranteed to just be 0 or 1. Now, if somevalue is a C99 bool, there is that guarantee. Of course, the code above is still dumb because it's excessively verbose.

Another problem was packing "boolean" values into flags. To get around the problem of "booleans" not being limited to 0 and 1, you would end up writing code like

flags = (condition1 ? 1 : 0 ) << 1 | (condition2 ? 1 : 0 ) << 2 | (condition3 ? 1 : 0 ) << 3;

Now, if the three condition variables above all have type bool, you can make this much more compact:

flags = (condition1 << 1) | (condition2 << 2) | (condition3  << 3);

So, does this actually work? Let's give it a whirl! Here's a silly little test function.

#include <stdio.h>
#include <stdbool.h>

bool test( void )
{
return printf( "blah" );
}

Here's the disassembly of that function (compiled for ARM, because I hate reading x86 assembly language). Notice addresses 10 and 14. Address 10 subtracts 0 from r0 and stores the result in r0 (on ARM r0 holds the return value from a function, which is printf in this case). That's setting up a comparison to 0 for address 14, which sets r0 to 1 if the return value from printf was not zero. If the return value from printf was 0, then r0 already has 0 in it, so there's nothing to do (clever optimizer!). Of course, r0 then becomes the return value from the test function, so this does exactly what we expect: It returns 0 if printf returned a value of 0, and 1 otherwise.

 0:   e52de004    push    {lr}        ; (str lr, [sp, #-4]!)
4: e59f0018 ldr r0, [pc, #24] ; 24 <test+0x24>
8: e24dd004 sub sp, sp, #4 ; 0x4
c: ebfffffe bl 0 <printf>
10: e2500000 subs r0, r0, #0 ; 0x0
14: 13a00001 movne r0, #1 ; 0x1
18: e28dd004 add sp, sp, #4 ; 0x4
1c: e49de004 pop {lr} ; (ldr lr, [sp], #4)
20: e12fff1e bx lr

And there you have it. The bool type isn't the most ground-breaking feature in C, but it isn't completely useless either.

Consistent Overhead Byte Stuffing

March 26, 2011 | Embedded Software

Framing packets transmitted on a UART serial link (such as RS-232 or RS-485) is a common problem in embedded programming. The typical approach is to put framing characters at the beginning and end of the packet. If a framing character occurs in the packet, it is escaped using a technique called byte stuffing. This sucks for a few reasons, but there's a better way. The recently developed algorithm called Consistent Overhead Byte Stuffing is a great solution that should be in every embedded software engineer's toolbox.

First, a bit of background. I'm working on a project where I have to transmit data between two microcontrollers using RS-422. RS-422 is a differential signalling standard that is often used in place of RS-232 to connect two UARTs when electrical isolation and/or noise immunity are required.

The question came up, how do we assemble packets on the transmitter and detect packet boundaries on he receiver? Our packets all have the same size and can contain arbitrary binary data. My first thought was to use idle line detection. If our UART detects enough bit times without a start bit, it can give us an idle line interrupt. Because we're feeding the transmitting UART with DMA, we can guarantee that there are no gaps in the middle of the packet that would cause a false idle line to be detected.

My boss pointed out that I was relying on an implementation detail that might not be valid if we ever moved to a really cheap microcontroller. He encouraged me to come up with a solution that put the framing into the packet itself.

The traditional way to do this is with byte stuffing. You designate a character (such as STX, ASCII 0x02) as the start of frame character and another (often ETX, ASCII 0x03) as the end of frame character. If there's a possibility that ETX or STX will occur in your data, you designate a third character as the escape character (ESC, ASCII 0x1F, for example). STX, ETX, and ESC characters in the data are replaced by an ESC followed by mangled version of he character (the character XORed with 0x20 is a popular choice).

There are two problems with this system:

  • It can add a lot of overhead. In the worst case, the encoded data could be twice the size of the original data. Unless you can be sure this won't happen, you have to design your buffers and bandwidth to handle this worst case.

  • The amount of overhead is variable. If you want to use DMA or FIFO buffers to send and receive your data, dealing with variable length data can be annoying. For example, you can't reliably request an interrupt after a frame's worth of data has been received. When you're transmitting at multiple megabits per second, you really don't want to check for a complete frame after each character is received.

Returning to the story above, I was really annoyed. My boss had a good point, but byte stuffing is just a pain. I did a bunch of googling, and finally came across COBS. It has the following great properties:

  • It removes all zero bytes from the original message, allowing the zero byte to be used as a frame delimiter.

  • The worst-case overhead is just 1 byte for every 254 bytes of data, or 0.39%.

  • For messages smaller than 254 bytes, the overhead is constant (exactly 1 byte).

  • The encoding process is fairly efficient (no complicated rearranging of input data across multiple bytes).

There's sample code on the Wikipedia COBS page. I've improved the Wikipedia code in a few ways:

  • My encoder and decoder return the length of the output data, because that size varies depending on the input data.

  • My decoder checks the validity of its input data to protect against corrupted or malicious data. The original Wikipedia code would cause a buffer overflow if an overly high block length code occurred at the end of the input data.

  • My decoder doesn't put the imaginary zero byte at the end of its output.

  • My encoder and decoder use modern C99. For example, specifying the restrict qualifier on the input and output pointers means the code can be more heavily optimized (restrict is a promise that the two buffers do not overlap, which helps the optimizer eliminate unneeded loads and stores).

COBS resources:

Here's my C implementation of COBS:

/* Copyright 2011, Jacques Fortier. All rights reserved.
*
* Redistribution and use in source and binary forms are permitted, with or without modification.
*/
#include <stdint.h>
#include <stddef.h>

/* Stuffs "length" bytes of data at the location pointed to by
* "input", writing the output to the location pointed to by
* "output". Returns the number of bytes written to "output".
*
* Remove the "restrict" qualifiers if compiling with a
* pre-C99 C dialect.
*/
size_t cobs_encode(const uint8_t * restrict input, size_t length, uint8_t * restrict output)
{
size_t read_index = 0;
size_t write_index = 1;
size_t code_index = 0;
uint8_t code = 1;

while(read_index < length)
{
if(input[read_index] == 0)
{
output[code_index] = code;
code = 1;
code_index = write_index++;
read_index++;
}
else
{
output[write_index++] = input[read_index++];
code++;
if(code == 0xFF)
{
output[code_index] = code;
code = 1;
code_index = write_index++;
}
}
}

output[code_index] = code;

return write_index;
}

/* Unstuffs "length" bytes of data at the location pointed to by
* "input", writing the output * to the location pointed to by
* "output". Returns the number of bytes written to "output" if
* "input" was successfully unstuffed, and 0 if there was an
* error unstuffing "input".
*
* Remove the "restrict" qualifiers if compiling with a
* pre-C99 C dialect.
*/
size_t cobs_decode(const uint8_t * restrict input, size_t length, uint8_t * restrict output)
{
size_t read_index = 0;
size_t write_index = 0;
uint8_t code;
uint8_t i;

while(read_index < length)
{
code = input[read_index];

if(read_index + code > length && code != 1)
{
return 0;
}

read_index++;

for(i = 1; i < code; i++)
{
output[write_index++] = input[read_index++];
}
if(code != 0xFF && read_index != length)
{
output[write_index++] = '\0';
}
}

return write_index;
}

Omega HH506RA Serial Protocol

March 22, 2010 | Embedded Software

Today I had to figure out how to read temperature from an Omega HH506RA thermocouple signal conditioner/datalogger. The HH506RA is a nice little unit that reads temperature from two thermocouples (type K, J, N, T, R, S, or E). It can display the temperature on its LCD screen and communicate them to a PC over RS232 or USB. The PC connection is optically isolated, which is very nice because RS232 and USB are both notorious for causing noise problems via ground loops.

I've put information on how to communicate with the unit up here for future reference.

I found some information on an NI forum and on Matlab's file exchange site.. The info on the NI site is a bit hard to read and not quite correct, so here's a quick and clear rundown.

Serial Port Setup

If you're using the USB cable, its actually just a virtual serial port, which will likely show up on your PC as COM1 to COM4. If you're using the RS232 cable, then obviously you need a serial port on the PC. Either way, you need to set the serial port up for 2400 baud, 7 data bits, even parity, 1 stop bit, and no flow control.

Communication Overview

To read the temperatures from the unit, send this string over the serial port: #001Nrn. r means the carriage return character (ASCII 13). n means the newline character (ASCII 10). You'll get back a string that follows this pattern:  TTTTt TTTTtABrn. The first and second  TTTTt groups represent the temperature and thermocouple type for the first and second thermocouple. The AB section is some miscellaneous information.

Temperature

The  TTTT part will be a hexadecimal string representing the temperature in tenths of a degree Celcius. For example,  017A represents 37.8 degrees Celcius. If the number is negative, it will start with a minus sign instead of a space. For example -00C2 means -19.4 degrees C.

Thermocouple Type

The t part represents the thermocouple type (set using the buttons on the HH506RA). The codes go as follows:

Code Type
0 K
1 J
2 T
3 E
4 N
5 R
6 S

Miscellaneous Info

According to the document on the NI site, the A digit above represents Celcius/Fahrenheit while the B character represents battery. I've only ever seen them as 0 in my testing.

Example

Bringing it all together:
You send: #001Nrn
You receive: -00B20 02C1200rn
Decoding: The first thermocouple is a type K that is reading -17.8 degrees C. The second thermocouple is a type T reading 70.5 degrees C.

Errors

If you send a bad command, you'll get a a response of Errrn. I've found that to be a handy way to resynchronize communication in case something goes wrong. Just send rn and read for a response until you see Errrn. Once you get that response, you know the unit is ready to accept a command again.

Other Commands

The document on the NI forum has some additional details. For example, you can read the unit's ID with the command %IDRrn. The ID is the set of digits you send in the read temperature command #001Nrn. You can change the unit's ID so that it responds to #005Nrn by sending a command along the lines of %001I005rn. I don't really see the point of this, so I haven't bothered testing it. The unit can log data, which can then be read back with the command #001Srn.

Watch out for compiler bugs related to volatile variables

February 3, 2010 | Embedded Software

At my new job, I've been diving back into embedded software development. During my time as an industrial automation application engineer, I stopped working quite as close to the hardware. It's definitely fun to be digging around in registers and assembly code again.

I came across this article called on Embedded.com called "When good compilers go bad, or What you see is not what you execute". It talks about all kinds of ways that compilers can end up generating incorrect (or sometimes technically correct but unexpected) source code. I've got a rule of thumb when debugging that in that vast majority of cases "you didn't discover a bug in the compiler/operating system". It's good to keep in mind that that isn't always the case.

One reference that especially caught my eye was to a paper entitled "Volatiles Are Miscompiled, and What to Do about It". They looked at 13 different C compilers and found out that all thirteen of them had issues with volatile variables.

Volatile variables are very frequently used in the embedded world. Memory-mapped hardware registers (used to read digital and analog inputs for example) are often accessed via volatile pointers in C. The volatile qualifier tells the C compiler "this variable could change at any time, so every time I ask you to read or write it, I really mean it!"

The authors of the paper found that every single compiler they tested failed to correctly implement the volatile qualifier in at least a few of their test cases. However, there are a few things you can do to help protect yourself:

  • Don't turn on optimization. They couldn't prove it, but they're pretty sure that all (and definitely most) of these kinds of bugs are caused by the compiler's optimizer.
  • Wrap uses of volatile variables in function calls. Because functions are (obviously) used way more than volatile variables, there tend to be very few bugs related to incorrect optimizations of function calls. Hiding volatile accesses in function calls makes it much less likely the access to a volatile variable will get optimized away (assuming the function isn't inlined).
  • Don't use volatile variables for inter-thread communication, use semaphores instead. This one deserves a post all of its own.
  • When the code just absolutely has to work, verify the assembly or machine code your compiler produces by hand.

One thing I really liked about the paper is that they used valgrind to help automate their testing. When I've run into some really tough to debug memory and pointer issues, valgrind has always been a huge help. I wish it were easier to use it in embedded programming projects.