Steve’s Software Trek

I created a ring buffer library for embedded systems in C some years ago and have been using it when I need to add a simple queue to my software.  I knew it worked correctly since I created unit tests to validate the code.  However, I noticed that it wasn’t interrupt safe since one of the consumer variables is shared by the producer (the count).  This library requires disabling interrupts when consuming.  Not what I wanted.

There are a number of difficulties when designing ring buffers, mostly dealing with efficiencies of code or data, or the struggle between consumers and producers.  My generic ringbuf library had used a single fill count, but the count had to be updated by the interrupt service routine (producer) and by the routine that retrieved the data (consumer).  I tried to use read and write offset indices, but that required that I always keep an element open since the you can’t tell if the ring is empty or full when the head and tail are the same.

Absolute indices appeared to be interrupt safe, although they require that the buffer length be a power of two.  That seemed to be flexible enough for most embedded work.  I modified and tested my ring buffer library using that method, but my ringbuf, which allowed for a fixed length element,  seemed to be overkill for what I was using it for – gathering bytes from a serial interrupt service routine.  Its API also had a slight flaw such that if the consumer retrieved the data (via Pop rather than just viewing the first element), the producer was free to put new data into the buffer, overwriting the data just retrieved.

I had started my ring buffer library as a simple character (one byte) FIFO – first in, first out.  So, I revisited that code, and modified it to use absolute indices.  A simple byte ring buffer, first in, first out.  Now I had interrupt safe code that would work in my serial interrupt service routine.

Why go to the trouble to make a library module to handle a ring buffer when slapping the following quick and dirty ring buffer code (from Stefan) into the serial module would have worked as well?

   #define N 128
   volatile unsigned int head, tail;
   volatile char buffer[N];
   unsigned int inuse() { return head - tail; }
   void put(char c) { if (inuse() != N) { buffer[head++%N] = c; } }
   void get(char* c) { if (inuse() != 0) { *c = buffer[tail++%N]; } }

Because I needed to know that it worked correctly, and I like reusable library modules.  Especially high quality reusable modules.  Especially high quality reusable modules that include unit tests to validate functionality.  Unit tests that also serve as guides for implementers.

The new module files are ringbuf.c and ringbuf.h for the ring buffer with fixed sized elements, and fifo.c and fifo.h for the ring buffer with byte sized elements. All my versions of the ring buffer and the unit testing framework can be found in the ringbuf.zip file.

Every once in awhile, I need a macro to work around a difference in a C compiler.

For example, not every compiler for the Win32 platform has implemented C99 integer and boolean types, so I have stdint.h and stdbool.h files. Fortunately, The Open Group maintains an online definition for stdint.h and stdbool.h so I don’t have to guess about what is supposed to go in there. C99 also defines some new keywords: restrict, inline, _Complex, _Imaginary, _Bool. Since _Bool is used by stdbool.h, it may or may not have been defined by the compiler. What I needed was a macro defined by the compiler that tells me which compiler it is so I can avoid compiler warnings.

Digging up the compiler macros on the internet can be challenging. However, there is a nice project at SourceForge to track Pre-defined C/C++ Compiler Macros.

That makes things a whole lot easier!

I found Technical Drawing, Fifth Edition, by Giesecke, Mitchell, Spencer, and Hill, at a local Goodwill store. It is a wonderful book for those who want to learn about drafting. It is also great for woodworkers since it contains a detailed chapter on Geometric Constructions. It is great for graphic artists as it describes how to construct a large number of geometric shapes. However, the gem that I found that relates to software engineering comes from the beginning of the book in Chapter 2, section 2.3:

2.3 Drafting at Home or School. If a draftsman is to turn out drawings rapidly and accurately, he must work in quiet surroundings without distractions. Technical drawing requires headwork, and the draftsman who is whistling, singing, talking, eating, or smoking, is probably “pushing the pencil” without much mental activity behind it.

Someone knew the secret in 1967, the date the book was published, of how to get headwork done. The same technique for reducing interruptions applies to software engineering. We could say:

If a software engineer is to produce software rapidly and accurately, he must work in quiet surroundings without distractions. Software engineering requires headwork, and the engineer who is whistling, singing, talking, eating, or smoking, is probably “pounding the keyboard” without much mental activity behind it.

I think Joel had this concept of quiet surroundings right when he designed the Bionic Office. Peopleware also came to this same conclusion.

It’s that time of year again. Time to spring forward. Well, not exactly the same time as last year. The formula for daylight savings time changed for this year. That meant that I had to rewrite firmware that used daylight savings time. According to Wikipedia,

Beginning in 2007, DST will start on the second Sunday in March (March 11, 2007), and change back to standard time on the first Sunday in November (November 4, 2007). Under Section 110 of the Energy Policy Act of 2005, the U.S. Department of Energy is required to study the impact of the DST extension no later than nine months after the change takes effect. Congress has retained the right to revert to the DST schedule set in 1986 if it cannot be shown that there are significant energy savings from an extension of DST or if the extension may prove to be unpopular with the American public. One potential issue is that some northern regions on the western edge of time zones will for the first time since the 1974-75 “almost year round” DST experiment have sunrise times that occur after 8am.

In two of my controllers I use, the built in hardware clock of the PC/104 card automatically handles the daylight savings time change. I simply set a bit and it would automatically spring forward or fall back. Well, almost. One of the controllers used a realtime clock chip by Odin which didn’t come out of daylight savings time and got stuck at 1am on the last Sunday of October. Since I could no longer utilize the hardware clock, I had to handle the daylight savings time change in software. There were two cases that I needed to cover. The first case is handling the timer interrupt and springing forward one hour or falling back one hour. The timer interrupt code turned out to be much simpler than I first thought. It is a good thing to be simple in an interrupt. Here is part of the code:

The second case was to determine if the date and time was during daylight savings time or not. This is used when the date and time get set on the controller, and to display the daylight savings time status. The code is more complex than the interrupt routine. Here is part of the code:

Testing the Daylight Savings Time algorithm was fairly routine using Unit Testing:

Hope you are getting used to waking up earlier!