Why Buffer? Because buffers cut you some slack.
Inevitably, in our recent series on microcontroller interrupts, the question of how to deal with actual serial data came up. In those examples, we were passing one byte at a time between the interrupt service routine (ISR) and the main body of code. That works great as long as the main routine can handle the incoming data in time but, as many people noted in the comments, if the main routine takes too long the single byte can get overwritten by a new one.
The solution? Make some storage room for multiple bytes so that they can stack up until you have time to process them. And if you couple this storage space with some simple rules for reading and writing, you’ve got yourself a buffer.
So read on to see how to implement a simple, straightforward circular buffer in C for microcontrollers (or heck, for anything). Buffers are such a handy tool to have in your programming toolkit that you owe it to yourself to get familiar with them if you’re not already.
Buffers
Generally speaking, you’ll want a buffer between two processes whenever they generate or handle data asynchronously or at different instantaneous rates. If data comes in slowly in individual bytes (as letters) but it’s more convenient to handle the data in bigger chunks (as words), a buffer is just what you need. Conversely, you might want to queue up a string from your main routine all at once and let the serial sending routine handle splitting it up into bytes and shuttling them along when it can.
In short, a buffer sits between two asynchronous routines and makes sure that either of them can act when they want without forcing the other routine to wait for it. If one process is a slow and steady tortoise, but the other is a bursty hare that needs to take frequent breaks to catch its breath, the buffer is the place where the data stacks up in the meantime.
The family of buffers that we’ll be interested in are buffers that makes sure that the data comes in and leaves in the same order. That is, we’ll be looking at first-in, first-out (FIFO) buffers. For a simple FIFO you can store your incoming data in the last free slot in an array, and read the data back out from the beginning of that array until you run out of data.
Note what’s great about even this simplest buffer; one process can be reading data off of the front of the array while the other is adding data on the back. They don’t overwrite each other and can both access the array in turns or in bursts. But eventually you run out of space at the end of the array, because the buffer only resets the writing position back to the first array element when it’s been fully read out.
This kind of linear buffer works great for situations where you’re likely to read out everything at once, but when the reading and writing are interleaved as shown here, you can run out of space in the array before it gets cleared out, while at the same time there’s “empty” space that’s already been read out in the front of the array.
The solution is a circular buffer, where the data can wrap back around to the beginning again to use up the extra space. Circular buffers are great because they make use of more of the allocated memory than the linear buffer and still preserve the FIFO ordering.
To make a circular buffer, we’ll need to keep track of the beginning (red) and end (green) of the buffer, and make up some simple rules to deal with wraparound and to keep us from overwriting existing data, but that’s about the gist of it.
Circular Buffers: Empty or Full?
With a linear buffer, it’s easy to tell when the buffer is empty or full. If the last available slot is the last byte in the array, it’s full. If it’s the first slot in the array, it’s empty. But things are a little bit more complicated with the circular buffer because the wrapping around often leaves us in situations where the newest data is being written into a slot that’s numerically lower than the oldest data.
So we’ll create two additional variables (indexes) to keep track of where the newest and oldest data elements are in our array. When the two indexes are the same, we’ll say that the buffer is empty. Each time we add data to the buffer, we’ll update the “newest” data index, and each time we pull data out, we’ll update the “oldest”.
If the buffer is empty when both of the indexes are the same, when is it full? This gets tricky, because when the array is completely full — every slot is filled — the oldest index and the newest index are equal to each other, which is just exactly the condition we wanted to use to test for it being empty. The easiest way, in my opinion, to deal with this is just to leave one slot empty at all times.
Watch the animation again, and notice that we declare the array “full” when it’s actually got one free space left in it just before the newest (green) index reaches the oldest (red). That is, we declare the buffer to be full when the newest index plus one is equal to the oldest, which keeps them from ever overlapping except when the buffer is empty. We lose the use of one slot in our buffer array, but it makes the full and empty states easy to distinguish.
There are a bunch of other ways to implement a circular buffer. In all, unless you’ve got seriously pressing optimization constraints, any of them are just fine. We’ll stick with “newest index / oldest index” because I find it most intuitive, but feel free to try them all out on your own. Let’s see it in action.
Code
So here’s what we need our code to do:
- Set aside some memory (we’ll use an array) to use for the buffer
- Keep track of the beginning (oldest entry) and the end (newest entry) of the data in our buffer
- Provide functions for storing and retrieving data from the buffer:
- Simplest methods use bytewise access
- Need to update the buffer indexes on read or write
- Nice to pass error codes when full / empty if trying to write / read
Off we go! First, we’ll set up the data.
#define BUFFER_SIZE 16
struct Buffer {
uint8_t data[BUFFER_SIZE];
uint8_t newest_index;
uint8_t oldest_index;
};
If structs are new to you, don’t fret. They just enable us to keep our three important bits of data together in one container, and to give that container a name, “Buffer”. Inside, we’ve got an array to store the data in, and two variables for the first and last active entries, respectively. Besides the obsessive-compulsive joys of keeping all our data in a nice, tight package, we’ll see that this pays off when we generalize the code a little bit later.
Writing
Now let’s write some data into the buffer. To do so, we first check to see if we’ve got space for a new entry: that is, we make sure that the newest_index+1 doesn’t run into the oldest_index. If it does, we’ll want to return a buffer full error. Otherwise, we just store the data in the next slot and update the newest_index value.
enum BufferStatus bufferWrite(uint8_t byte){
uint8_t next_index = (buffer.newest_index+1) % BUFFER_SIZE;
if (next_index == buffer.oldest_index){
return BUFFER_FULL;
}
buffer.data[buffer.newest_index] = byte;
buffer.newest_index = next_index;
return BUFFER_OK;
}
Here you’ll see the first of two ways to refer to elements within a struct, the . (“member”) operator. If we want to refer to the data array within our buffer struct, we just write buffer.data, etc.
Note that when we’re calculating the next_index, we take the modulo with BUFFER_SIZE. That does the “wrapping around” for us. If we have a 16-byte buffer, and we are at position fifteen, adding one gives us sixteen, and taking the modulo returns zero, wrapping us around back to the beginning. As we mentioned above, as long as we’re using a power-of-two buffer length, this modulo is actually computed very quickly — even faster than an if statement would be.
OK, there’s one more (stylistic) detail I’ve swept under the rug. I like to handle the return codes from the buffer as an enum, which allow us to assign readable names to the return conditions. Using an enum doesn’t change anything in the compiled code in the end, but it makes it easier to follow along with the program logic.
enum BufferStatus {BUFFER_OK, BUFFER_EMPTY, BUFFER_FULL};
Internally, the compiler is substituting a zero for BUFFER_OK, a one for BUFFER_EMPTY, and a two for BUFFER_FULL, but our code can use the longer text names. This keeps us from going insane trying to remember which return code we meant when returning a two.
Now notice what the return type of our bufferWrite function is: a BufferStatus enum. This reminds us that whenever we call that function, we should expect the same enum — the same mapping from the underlying numbers to their text symbols. Unfortunately, GCC doesn’t typecheck enum values for us, so you’re on your honor here to do the right thing. (Other compilers will throw a warning.)
Reading
The bufferRead function just about as straightforward. First we check if the newest_index is the same as the oldest_index, which signals that we don’t have any data in the buffer. If we do have data, we
enum BufferStatus bufferRead(uint8_t *byte){
if (buffer.newest_index == buffer.oldest_index){
return BUFFER_EMPTY;
}
*byte = buffer.data[buffer.oldest_index];
buffer.oldest_index = (buffer.oldest_index+1) % BUFFER_SIZE;
return BUFFER_OK;
}
This brings up an important C programming idiom. We want to get two things back from our bufferRead function: the oldest byte from the buffer and a return code to go along with it. For reasons lost to time, probably having something to do with efficient programming on prehistoric PDP-8s or something, a C function can only really return a single value. If your function wants to return multiple values (as we do here), you’ve got to get crafty.
We haven’t really dug into pointers in Embed with Elliot, but here’s another standard use case. (For the first, see our post on pointer-based State Machines) The bufferRead function returns a status code. So where does it store the data it read out of the buffer? Wherever we tell it to!
A pointer can be thought of as a memory address with a type attached to it. When we pass the pointer uint8_t *byte to our function, we’re passing the memory address where we’d like the function to store our new data. Our main program declares a variable, and then when we call the bufferRead function, we pass it the address of that variable, and the function then stores the new data into the memory address that corresponds to the variable in main.
enum BufferStatus status; uint8_t byte_from_buffer; status = bufferRead(&byte_from_buffer); /* and now byte_from_buffer is modified */
The only potentially new thing here is the “address-of” operator, &. So we call bufferRead with the location in memory that our main routine is calling byte_from_buffer, for instance, and the function writes the new byte into that memory location. Back in the calling function, we get our two variables: the status value that’s passed explicitly, and the byte_from_buffer that’s written directly into memory from inside the bufferRead function.
And that’s about it. To recap: we used a struct to combine the array and its two indices into one “variable”, mostly for convenience. Then we defined an enum to handle the three possible return conditions from the reader and writer functions and make the return values readable. And finally, we wrote some simple reader and writer functions that stored or fetched data from the buffer, one byte at a time, updating the relevant index variable as necessary.
Refinements and Generalizations
As it stands right now, we’re storing the buffer as a global variable so that it can be accessed by our main routine and the read and write routines. As a result we can’t re-use our code on more than one buffer at a time, which is silly. For instance, if we were using the buffers for USART serial communication, we’d probably want a transmit and receive buffer. And once you get used to buffers, you’ll want them between any of your asynchronous code pieces. So we’ll need to generalize our functions a little bit so that we can define multiple buffers that will work with our reader and writer functions..
Fortunately, it’s easy. Two simple changes will allow us to re-use our bufferRead and bufferWrite functions on an arbitrary number of different buffers.
enum BufferStatus bufferWrite(volatile struct Buffer *buffer, uint8_t byte){
uint8_t next_index = (((buffer->newest_index)+1) % BUFFER_SIZE);
if (next_index == buffer->oldest_index){
return BUFFER_FULL;
}
buffer->data[buffer->newest_index] = byte;
buffer->newest_index = next_index;
return BUFFER_OK;
}
enum BufferStatus bufferRead(volatile struct Buffer *buffer, uint8_t *byte){
if (buffer->newest_index == buffer->oldest_index){
return BUFFER_EMPTY;
}
*byte = buffer->data[buffer->oldest_index];
buffer->oldest_index = ((buffer->oldest_index+1) % BUFFER_SIZE);
return BUFFER_OK;
}
In both instances, instead of relying on a buffer variable defined in the global namespace, we’re passing it to the function as an argument. Or, more accurately, we’re passing a pointer to a Buffer structure to the function. We declare the buffer volatile because we want to update the buffers using interrupt routines later. (See our article on volatile if you need a refresher.)
The other change is how we refer to the buffer struct‘s elements. The problem is that we don’t pass the struct itself, but a pointer to that struct. So what we need is to get (“dereference”) that struct first, and then access the data element within it. The cumbersome way to to that goes like this: (*buffer).data, but since this pattern occurs so often in C, a shortcut notation was developed: buffer->data.
Receiving
Those two changes aside, the logic of the read and write code is exactly the same. So how do we use these functions? Glad you asked. Let’s take the example of setting up receive and transmit buffers for an AVR microcontroller to shuttle data in and out using its built-in hardware USART and interrupt routines. Once you’ve got a good circular buffer at hand, handling incoming serial data becomes child’s play.
volatile struct Buffer rx_buffer = {{}, 0, 0};
ISR(USART_RX_vect){
bufferWrite(&rx_buffer, UDR0);
}
int main(void){
uint8_t received_byte;
enum BufferStatus status;
initUSART();
initUSART_interrupts();
while (1) {
status = bufferRead(&rx_buffer, &received_byte);
if (status == BUFFER_OK) { /* we have data */
do_something(received_byte);
}
}
}
This isn’t a full-fledged example, but it hits the main elements. The code defines an interrupt service routine (ISR) that simply stashes the received byte into the circular buffer when anything comes in over the serial line. Note that the bufferWrite function is pretty short, so we’re not going to spend too much time in the ISR, which is what we want. The combination of the interrupt and the chip’s hardware serial peripheral take care of filling up the buffer for us. All that’s left to do in main() is try to read some data from the buffer, and check the return code to see if we got something new or not.
Because the buffer is shared between the main() routine and the ISR, it needs to be defined outside of either function, in the global namespace. Note that since we write to one end of the buffer, and read from the other, there’s not as much need to worry about race conditions and atomicity here. As long as the ISR is the only routine that’s writing to our buffer, and we only read from the buffer in main(), there’s no chance of conflict.
That said, if you want to be doubly sure that your shared volatile variable isn’t getting accessed twice at the same time, or if you’re writing a more general-purpose circular buffer routine, it wouldn’t hurt to wrap up the sections with access to shared variables in an ATOMIC_BLOCK macro.
Transmitting
Finally, setting up a transmit buffer is a little bit more complicated on the AVR platform, because we’ll need to enable and disable the USART’s data-ready interrupt when the transmit buffer has data or is empty, respectively. Defining a couple convenience functions and checking for the buffer status in the interrupt routine take care of that easily:
static inline void enable_transmission(void){
UCSR0B |= (1<<UDRIE0);
}
static inline void disable_transmission(void){
UCSR0B &= ~(1<<UDRIE0);
}
ISR(USART_UDRE_vect){
uint8_t tempy;
enum BufferStatus status_tx;
status_tx = bufferRead(&tx_buffer, &tempy);
if (status_tx == BUFFER_EMPTY){
disable_transmission();
} else {
UDR0 = tempy; /* write it out to the hardware serial */
}
}
The UDRE interrupt fires every time the USART data register is empty (“DRE”) so that the ISR pulls a new character off the transmit buffer as soon as it’s able to handle it. Your calling code only needs to pack all the data into the transmit buffer and enable the interrupt one time, without having to wait around for the actual transmission to take place, which takes a long time relative to the fast CPU speed. This is, not coincidentally, a lot like what the Arduino’s “Serial” library functions do for you.
Peeking Inside the Buffer
Finally, there’s one very common use case that we haven’t addressed yet. It’s often the case that you’d like your code to assemble data out of multiple bytes. Maybe each byte is a letter, and you’d like your code to process words. On the reading side, you’d like to stack up data in the buffer until a space character arrives. For this, it’s very convenient to have a function that looks at the most recently added character, but doesn’t change either of the index variables.
We’ll call this function bufferPeek() and it’ll work like so:
enum BufferStatus bufferPeek(volatile struct Buffer *buffer, uint8_t *byte){
uint8_t last_index = ((BUFFER_SIZE + (buffer->newest_index) - 1) % BUFFER_SIZE);
if (buffer->newest_index == buffer->oldest_index){
return BUFFER_EMPTY;
}
*byte = buffer->data[last_index];
return BUFFER_OK;
}
The code should be, by now, basically self-explanatory except for the one trick in defining the last_index. When the buffer has just wrapped around, newest_index can be equal to zero. Subtracting one from that (to go back to the last written character) will end up with a negative number in that case. Adding another full BUFFER_SIZE to the index prevents the value from ever going negative, and the extra factor of BUFFER_SIZE gets knocked out by the modulo operation anyway.
Once we’ve got this “peek” function, assembling characters into words is a snap. For instance, this code snippet will wait for a space in the incoming data buffer, and then queue up the word as quickly as possible into the output buffer, turning on the transmit interrupt when it’s done.
// Check if the last character typed was a space
status = bufferPeek(&rx_buffer, &input_byte);
if (status == BUFFER_OK && input_byte == ' '){
while(1) {
status = bufferRead(&rx_buffer, &input_byte);
if (status == BUFFER_OK){
bufferWrite(&tx_buffer, input_byte);
} else {
break;
}
}
enable_transmission();
}
Code and Conclusions
All of this demo code (and more!) is available in a GitHub repository for your perusal and tweaking. It’ll work as written on any AVR platform, but the only bits that are specific are the mechanics of handling the interrupts and my serial input/output library. The core of the circular buffer code should work on anything that you can compile C for.
There are all sorts of ways to improve on the buffer presented here. There are also many possible implementations of circular buffers. This article is far too long, and it could easily be three times longer!
But don’t get too bogged down in the details. Circular buffers are an all-purpose tool for dealing with this common problem of asynchronous data creation and consumption, and can really help to decouple different parts of a complex program. Implementing buffers isn’t black magic either, and I hope that this article has whetted your appetite. Go out and look through a couple more implementations, find one you like, and then keep those files tucked away for when you need it. You’ll be glad you did.
If you’ve got favorite bits of buffer code, or horror stories from the trenches, feel free to post up in the comments. We’d love to hear about it.
Filed under: Hackaday Columns
No comments:
Post a Comment