Embedded Buffer

Many of my projects include a microcontroller or digital signal processor of some kind. Because I program these chips in C and use similar chips across projects, I seem to be reusing a lot of code. This isn’t necessarily a problem, but there are better ways to re-use code than simply copy-pasting the source from one file to another, as I have been.

I recently decided to create a source library for commonly used code, such as buffers, filters, and mathematical constants. Armed with such a library, I could then compile against a single, unified version of the source code across all projects (using the #include pre-processor directive). That way, if I find a bug in the code I only have to fix it once. Unfortunately, this requires that I write the library code very carefully – i.e., processor agnostic, versatile, and configurable using function calls rather than #define constants.

Buffers

The highest priority addition to my library was a reliable data buffer implementation, given that I use buffers in virtually every project. When porting my standard code to the library, however, I realised that making versatile and configurable buffers involves some overhead, which is generally a word one avoids when coding for low-power embedded systems. As such, I have split the buffer source code into two separate versions: buffer and bytebuffer, where the former is optimised to be versatile and configurable, and the latter is optimised for bare-metal performance. Here I discuss only buffer, as I am not yet satisfied with the portability of bytebuffer.

I have made the buffer source code public on GitHub. I don’t understand anything about open-sourcing software yet, so the code is technically still under copyright. Furthermore, I have lumped my entire code library into a single git repository (I have only pushed buffer to github), which is not advisable, but because I will #include some library functions in other library functions, it is safer to supply them all as one lumped repository (I know, I know, linked git submodules, blah blah… I can’t be bothered).

Example

Here is an example use of buffer:

#include <stdlib.h>
#include "buffer.h"

void testBuffer() {
  // Define test data to store
  double str[] = {10, 65000, 32000, 1200, 40, 23, 33, 99, 987656, 9};

  // Temporary variable to store data pulled from the buffer
  double tmp;

  // Define a buffer pointer
  buffer_t *b;

  // Initialise buffer
  b = newBuffer(16, sizeof(double), B_FIFO & B_DROP);

  // If buffer was initialised
  if (b) {      
    // Push test data to buffer
    pushToBuffer(b, &str[0], 10);

    // Pop all data from buffer
    while ( !isBufferEmpty(b) ) {
      popFromBuffer(b, &tmp, 1);
    }

    // Deallocate buffer
    freeBuffer(b);
  }
}

As you can see in this example, I refer to the buffer using a pointer, b. As is typical of higher-level object-oriented languages, I prefer to pass pointers to large blocks of data (such as buffers), rather than the data itself, which gives a dramatic speed boost.

Description and Usage

To describe how to use the code, I will refer to the above example. Since b is merely a pointer to a buffer, we first have to allocate and initialise a buffer using newBuffer(), and assign the returned pointer to b. New buffers are stored in heap space so that memory can be dynamically reallocated if necessary; as such, you will probably need to #include <stdlib.h> in your project (which handles the heap).

Note: many embedded compilers (or technically, linkers) have no heap space allocated by default, so you may have to manually assign some by passing an argument to your compiler/linker.

The arguments of newBuffer(depth, width, config) are, respectively, the depth of the buffer (number of elements), the width of the buffer (element size in bytes), and a configuration byte created using a bitwise and (&) of the options1:

B_FIFO and B_FILO are mutually exclusive, but if they are inadvertently combined, B_FIFO will be used. Similarly, B_DROP overrides B_OVERWRITE.

Before proceeding, we must first ensure that b does indeed point to an allocated buffer. This is because the buffers are dynamically allocated in heap space, so allocation is not guaranteed when the heap is full. If newBuffer() fails to allocate a new buffer, it returns a NULL pointer. We test the allocation simply by testing that b is not NULL, e.g., 

if (b) { … }

or 

if (b != NULL)  { … }

for stricter compilers.

When calling pushToBuffer() and popFromBuffer(), the first argument is the pointer to our buffer, b. The second argument is a pointer to a variable or array element used to read/write from the buffer; it must have the same type as the buffer elements (e.g., double). The last argument is the number of elements to push/pop.

Note: The buffer functions work with pointers to data, not the data itself, and the number of elements to be allocated/pushed/popped, not the number of bytes.

If pushToBuffer() or popFromBuffer() fails to push/pop elements, it returns a count of the number of elements that were unsuccessful; i.e., a non-zero return value indicates an error.

The two buffer functions isBufferEmpty() and isBufferFull() accept the buffer pointer b, and return a 1 if the buffer is empty/full, respectively, and 0 otherwise.

I have written the function freeBuffer(b) to deallocate the buffer from the heap space. One might be tempted to call the <stdlib.h> function free(b), but that does not free the data used by the buffer. This is a minor implementation detail that arose because the data type buffer_t had to use up a predictable amount of space, and so could not hold the (variable) amount of data held in the buffer. As such, we must always deallocate the buffer using freeBuffer().

Caveats

While I am generally pleased with the final buffer source, I have only tested it on a Mac with 4 GB of RAM. I suspect there will be some difficulty optimising the heap space for embedded devices.

Furthermore, while I don’t wish to incite a brand war, I mostly use Microchip devices. The low-end Microchip range uses many cycles for multiplication. As a natural consequence of working in multi-byte elements of configurable width, I have used multiplication several times in this code, and so buffer will not be suitable for such low-end devices, particularly with high-throughput buffers. Higher-end Microchip devices typically have single-cycle multiply capability, and so the performance hit is negligible.

Lastly, as I have designed the code to work with pointers to data (and offsets from those pointers), it is entirely possible that you may corrupt unmapped RAM or other variables if your pointer math is incorrect. I opted against providing any safeguards against this problem as it is trivial to avoid for competent programmers, but it does add a vulnerability that may be exploited by malware.

Wrap-up

I understand that, oddly, some folks don’t find buffers sexy. Personally, I appreciate a good buffer, but I am looking forward to implementing buffers using just a few lines of code, instead of reinventing the wheel every time I start a new project. I hope to put this code to the test in my upcoming amplifier re-design. I intend to report back with the (inevitable) changes I have to make to optimise it for embedded applications.

  1. I have prepended all configuration constants with the prefix B_ (for buffer) to minimise name space pollution. ↩