What’s a Circular Buffer, Anyway?
A data buffer is just a region of memory used to store data temporarily while being moved from one place to another. The most obvious way of creating a buffer is using an array. Typically, in a linear buffer, a write index marks the location of the next data to be stored and gets increased on each write. After reading data from the buffer, the remaining unread data are shifted to the left and the write index is decreased accordingly. The whole process can be quite time consuming and as input speed increases, the chance of an occurring data loss also increases.
On the other hand, a circular buffer (aka ring buffer) uses a different approach. Both ends of the buffer are connected creating a seamless loop. In other words, when the write index exceeds the upper bound of the array, it wraps around to the beginning, just like a runner on a track. As long as reading is done in a consistent basis, there is always room for new data.
This is achieved using two indices:
- the Write Index which indicates the location where the next data item should be written.
- the Read Index which indicates the location from which the next piece of data will be retrieved.
By automatically recycling space, circular buffers simplify memory management, reduce the risk of data loss, and make handling fluctuating or continuous data streams much easier.
How Do Circular Buffers Work?
The mechanism is quite straight forward:
- When a data item is added to the buffer, the write index advances. If it matches the read index, then the buffer is full.
- When a data item is removed from the buffer, the read index advances. If it matches the write index, then the buffer is empty.
Both indexes maintain the wraparound mechanism, thus returning to the beginning when exceeding the end. This system ensures a continuous flow of data with minimal complexity
Why Circular Buffers Are Ideal for Embedded Systems?
Embedded systems often suffer from harsh constraints, e.g., limited memory and requirement of real-time response. These impose the hardships of using a linear buffer.
Suppose that 64 bytes are consumed from a 128-byte linear buffer and there are 64 bytes of unprocessed data left. Those 64 bytes need to be shifted to the start of the buffer to make room for new incoming data. In the worst-case scenario where the entire buffer is filled and nothing yet has been consumed, the number of bytes to be shifted could be as high as the total buffer size.
One could develop a clever way of consuming and shifting data and enhance the above process but still one thing will become obvious: Linear buffers suffer from fluctuating latency and significant overhead for each reading cycle. This of course has a negative impact on their overall effective bandwidth. During bursts of input data or delay in processing, data loss will probably occur. To mitigate that risk, the linear buffer must be significantly oversized.
Circular buffers are addressing these challenges with their fixed latency. As there is fixed minimal overhead for each reading or wrapping around, their effective bandwidth gets greatly increased when comparing to an equally sized linear buffer. No data shifting is involved during the reading process but rather just the reading index is increased. That’s really all! Even in the case that they find it hard cope with a very high-speed input stream, their need for additional space allocation will be definitely lower than than that of their linear competitor.
One could synopsize it to this: they offer better decoupling between data reception and data consumption at a lower cost.
This makes them extremely efficient at processing sensor inputs, serial communication like UART, SPI, I2C or audio/video buffering—operations ubiquitous throughout embedded systems.
Creating a Circular Buffer in C
Let’s walk through how to design and implement a circular buffer in C... Well, actually it’s a really straightforward process and the code bellow, tailored for a PIC18F, is almost self explicable so I won’t go into many details.
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#define BUFFER_SIZE 16
typedef enum {
BUFFER_EMPTY = 0,
BUFFER_OK,
BUFFER_FULL
} buffer_status_t;
typedef struct {
uint8_t data[BUFFER_SIZE];
uint8_t write_index;
uint8_t read_index;
buffer_status_t status;
} circular_buffer_t;
void init_buffer(circular_buffer_t *buffer) {
buffer->write_index = 0;
buffer->read_index = 0;
buffer->status = BUFFER_EMPTY;
}
buffer_status_t get_buffer_status(const circular_buffer_t *buffer) {
return buffer->status;
}
bool write_to_buffer(circular_buffer_t *buffer, uint8_t value) {
// Return false if the buffer is FULL
if (buffer->status == BUFFER_FULL) return false;
buffer->data[buffer->write_index] = value;
// avoid modulo operation on PIC mcus
// buffer->write_index = (buffer->write_index + 1) % BUFFER_SIZE;
// try this instead:
buffer->write_index++;
if (buffer->write_index==BUFFER_SIZE){
buffer->write_index=0;
}
if (buffer->write_index == buffer->read_index) {
buffer->status = BUFFER_FULL;
} else {
buffer->status = BUFFER_OK;
}
// Write successful
return true;
}
bool read_from_buffer(circular_buffer_t *buffer, uint8_t *value) {
// Return false if the buffer is EMPTY
if (buffer->status == BUFFER_EMPTY) return false;
*value = buffer->data[buffer->read_index];
// avoid modulo operation on PIC mcus
// buffer->read_index = (buffer->read_index + 1) % BUFFER_SIZE;
// try this instead:
buffer->read_index++;
if (buffer->read_index==BUFFER_SIZE){
buffer->read_index=0;
}
if (buffer->write_index == buffer->read_index) {
buffer->status = BUFFER_EMPTY;
} else {
buffer->status = BUFFER_OK;
}
// Read successful
return true;
}
void main(void) {
circular_buffer_t buffer;
init_buffer(&buffer);
for (uint8_t i;i<=BUFFER_SIZE;i++){
if (write_to_buffer(&buffer, i)) {
printf("Successfully written value \"%d\"\n",i);
}else {
printf("Writing was unsuccessful - Buffer is full!\n");
}
}
uint8_t chr;
for (uint8_t i;i<=BUFFER_SIZE;i++){
if (read_from_buffer(&buffer, &chr)) {
printf("Successfully read value \"%d\".\n",chr);
}else {
printf("Reading was unsuccessful - Buffer is empty!\n");
}
}
}
Simple and effective, isn’t it? The functions handle adding, removing, and managing the buffer’s state with straightforward pointer logic. While the modulus operator adds clarity to the code, it can be resource-intensive on PIC18F microcontrollers. For better understanding, I’ve left it commented as a reference to the original approach.