Implementing a Circular Buffer in Arduino

In this post, we are going to implement a circular buffer in Arduino. What is a circular buffer and what is it used for?

Let’s imagine that we are going to receive a series of values, but usually, in order to save memory, we do not want to store all of them. We are only interested in storing the last N received values, while maintaining the order of reception.

The first alternative that comes to mind is to use an array of size N, store each received value in position 0, and shift the rest of the values to the right to accommodate the new value.

This first method is inefficient because it requires us to shift N-1 values (when it is full) every time we receive a new value, resulting in an algorithm of O(n).

In case you are wondering, things don’t improve by storing in the last position. Once our buffer is full, we will still have to shift N-1 values, and again we have an algorithm of O(n).

A circular buffer (or ring buffer) is an alternative to achieve an O(1) order in this situation. Again, we use an array of length N, but instead of shifting the stored values, we change the position where we insert the element.

To do this, we only need to store and manage the index of the current position. We will also have to deal with the array limits in the read and write operations, for example, resetting the buffer index to 0 when we exceed the upper limit of the array.

Reading the last M values of a circular buffer is inefficient because the values are not in consecutive memory positions, so we cannot copy them directly.

If this loss of efficiency is a problem and memory is not a critical factor, we could use a buffer of length 2N. Simultaneously recording the values in I and I+N, the last M values are always stored between I-M and I+N-M.

Circular buffers are common in communication systems, storing commands in a system, and sensor filtering. In a future post, we will see how to use a circular buffer to quickly calculate an average filter.

Simple Circular Buffer with Index

Here is a very basic implementation of a circular buffer. We use the variable ‘circularBufferIndex’ to store the current position, and when adding to the buffer, we handle the Array limits.

const int circularBufferLength = 10;
int circularBuffer[circularBufferLength];
int circularBufferIndex = 0;

void appendToBuffer(int value)
{
  circularBuffer[circularBufferIndex] = value;
  circularBufferIndex++;
  if (circularBufferIndex >= circularBufferLength) circularBufferIndex = 0;
}

void getFromBuffer(int* out, int outLength)
{
  int readIndex = (circularBufferIndex - outLength + circularBufferLength) % circularBufferLength;
  for (int iCount = 0; iCount < outLength; iCount++)
  {
    if (readIndex >= circularBufferLength) readIndex = 0;
    out[iCount] = circularBuffer[readIndex];
    readIndex++;
  }
}

void getFromBufferInvert(int* out, int outLength)
{
  int readIndex = circularBufferIndex - 1;
  for (int iCount = 0; iCount < outLength; iCount++)
  {
    if (readIndex < 0) readIndex = circularBufferLength - 1;
    out[iCount] = circularBuffer[readIndex];
    readIndex--;
  }
}

void printArray(int* x, int length)
{
  for (int iCount = 0; iCount < length; iCount++)
  {
    Serial.print(x[iCount]);
    Serial.print(',');
  }
  Serial.println();
}

void setup()
{
  Serial.begin(115200);

  Serial.println("Store 0 - 12");
  for (int iCount = 0; iCount <= 12; iCount++)
  {
    appendToBuffer(iCount);
    printArray(circularBuffer, circularBufferLength);
  }

  Serial.println("");
  Serial.println("Get last 5");
  int data[5];
  int M = sizeof(data) / sizeof(int);
  getFromBuffer(data, M);
  printArray(data, M);

  Serial.println("");
  Serial.println("Get last 5 invert");
  getFromBufferInvert(data, M);
  printArray(data, M);
}

void loop()
{
}

These are the results of running this code. We see that the numbers are stored in the buffer and, when it is full, they start to be overwritten. This way, we can obtain the last N numbers.

Simple Circular Buffer with Pointer

In the previous example, we used the index to access the current position of the buffer because it is suitable for explaining the operation. But generally, it is normal to use a pointer (in fact, it is a code that is asking for a pointer).

So, just to make sure, here is the modified code to use a pointer instead of the index. Basically, the operation is the same as before, and the results you obtain are exactly the same as those shown earlier.

const int circularBufferLength = 10;
int circularBuffer[circularBufferLength];
int* circularBufferAccessor = circularBuffer;

void appendToBuffer(int value)
{
  circularBufferAccessor++;
  if (circularBufferAccessor >= circularBuffer + circularBufferLength) circularBufferAccessor = circularBuffer;
  *circularBufferAccessor = value;
}

int getFromBuffer()
{
  int rst = *circularBufferAccessor;
  circularBufferAccessor--;
  if (circularBufferAccessor < circularBuffer) circularBufferAccessor = circularBuffer + circularBufferLength - 1;
  return rst;
}

void getFromBuffer(int* out, int outLength)
{
  int* readAccessor = circularBufferAccessor - outLength + 1;
  if (circularBufferAccessor < circularBuffer) circularBufferAccessor = circularBuffer + circularBufferLength - 1;

  for (int iCount = 0; iCount < outLength; iCount++)
  {
    if (readAccessor >= circularBuffer + circularBufferLength) readAccessor = circularBuffer;
    out[iCount] = *readAccessor;
    readAccessor++;
  }
}

void getFromBufferInvert(int* out, int outLength)
{
  int* readAccessor = circularBufferAccessor;
  for (int iCount = 0; iCount < outLength; iCount++)
  {
    if (readAccessor < circularBuffer) readAccessor = circularBuffer + circularBufferLength - 1;
    out[iCount] = *readAccessor;
    readAccessor--;
  }
}

void printArray(int* x, int length)
{
  for (int iCount = 0; iCount < length; iCount++)
  {
    Serial.print(x[iCount]);
    Serial.print(',');
  }
  Serial.println();
}

void setup()
{
  Serial.begin(115200);

  Serial.println("Store 0 - 12");
  for (int iCount = 0; iCount <= 12; iCount++)
  {
    appendToBuffer(iCount);
    printArray(circularBuffer, circularBufferLength);
  }

  Serial.println("");
  Serial.println("Get last 5");
  int data[5];
  int M = sizeof(data) / sizeof(int);
  getFromBuffer(data, M);
  printArray(data, M);

  Serial.println("");
  Serial.println("Get last 5 invert");
  getFromBufferInvert(data, M);
  printArray(data, M);
}

void loop()
{
}

Circular Buffer in a Library

What if we put it in a library? Of course! Here is a library that implements a circular buffer in Arduino. The implementation is somewhat more complex than that of this post, but in return, it is easier to use and more powerful. Enjoy!

Download the Code

All the code from this post is available for download on Github.