Software circular buffers are data structures used to pass data from one section of code to another, where the code sections usually have no other interaction with each other. One situation that dictates that a “buffer” be used is when it is possible that a burst of data to occur that exceeds the “processing” codes ability to keep up on an item by item basis. Then a separate section of code to buffer (accept from the external source and insert it into a circular buffer) is necessary.
On average, the processing must keep up, or no amount of buffering will prevent an eventual overrun and loss of data. Another situation where you might use a “buffer” is to compartmentalize the functions of your code. For example, if you are using a keypad on a project, you may choose to write one section of code that detects that a key has been pressed, determines what it is, and places the ASCII code for it in a circular buffer.
A completely separate section of code could then process the “stream” of key-presses for the purpose at hand, say a combination lock code. Partitioning the code in this fashion not only makes each section easier to write (each is smaller and you get to focus on a simpler task), but also makes each section more reusable. The combination decoding could easily be used virtually unchanged with the code sequence coming from the SCI instead. The proper view of data in a circular buffer is a “stream” of sequential data items, often characters.
The section of code that sends data to another section inserts each new datum item into the buffer. In general, that code inserts data as fast as it becomes available. The section of code that receives the data removes each item from the buffer. The receiver almost always has some processing task to perform on the received data items, and often processes at a slower instantaneous rate than the insertion code. It is often the case that several circular buffers will exist within a program. It is also often the case that the sending and/or receiving code sections are in interrupt handler routines. A possible point of confusion is that any receiving ISR routine (say an SCI receive ISR) will probably play the role of sender via the circular buffer. Virtually the only SCI receiver ISR I have ever written was to have it read the incoming characters and place them in a circular buffer, and nothing more.
How Do Circular Buffers Work?
A circular buffer is really a linear sequential buffer that is used from beginning to end, over and over. Unlike a STACK which operates as a first-in-last-out (FILO) buffer and naturally keeps reusing memory as items are popped on and later pulled off of the stack, with a circular buffer one must work at reusing memory. This is accomplished by having code to wrap around to the beginning of the buffer whenever the next location gets past the end of the buffer. Picture the buffer as a consecutive set of memory locations that has its last location adjacent to its first location (in effect a circle).
This circular buffer forms an endless queue. The queue functions as an endless first-in-first-out (FIFO) buffer. It is indeed endless as long as the process receiving the data never gets a complete buffer length behind the one sending the data. An evaluation of how far behind the receiver may get is the only way to determine the size one needs for the buffer. If it never gets more than one data value behind then a 2-long buffer is sufficient. If it gets up to 99 behind then a 100 element buffer is needed, and so on. In addition to the memory for the buffer itself, essentially an array of data, a circular buffer requires two markers, one to tell where to insert the next datum and one to tell from where to extract the next datum. Note that a stack required only one marker (called the Stack Pointer). The two markers can take either of two forms – indices or pointers.
Either type tells the next available location to place new data into the buffer and the next location containing data to be taken out of the buffer. If the buffer is four bytes long, an index would have a value from 0 to 3, whereas, a pointer would contain the address from buffer to buffer+3. The out marker chases the in marker around the buffer. Whenever it catches up it means the code receiving data has caught up with the code sending data and so the buffer is empty (has no more data to process at the moment). There is never a conflict between the two code sections in updating the markers as in marker is only updated (incremented) by the code inserting the buffered data, and out marker is only updated (incremented) by the code extracting the data.
Common Uses for Circular Buffers
Probably the most common use of a circular buffer is for storing characters received from an input device. The interrupt handler for the device simply reads the device (usually whenever an interrupt occurs indicating new data has been received), places it in a circular buffer, and exits (returns from the interrupt). There are numerous other uses for circular buffers and no assembly language programmer or high-level language programmer (especially one working with real-time or event-driven systems) should be without this powerful software tool. To implement a circular buffer in any language you need four distinct code sections. First, you must declare the buffer and the two pointer variables that will be used with it. In HCS08 assembler that section will look like this:
There also needs to be an initialization section that is executed before the buffer can be used and must be executed only once in your program. This should exist with the code that is executed almost immediately after reset on any embedded system that uses such buffers. In HC11 assembler it could be:
So if we are using our circular buffers to move data between a sender and a receiver we will need to make a few subroutines to implement our buffers. The next two sections of code are in (or are in a subroutine called by) the sender or receiver, respectively. I will first show example code for buffers containing single byte data values. (The previous examples are independent of data item size.) The examples are in subroutine form.
If the data items are more than one byte then something more than an sta or lda is needed to add or retrieve them, and more than a single increment is needed to advance the pointer in the buffer. Those are the only two changes.
I hope you enjoyed learning about circular buffers! They are truly wonderful.