Ring Buffer

Character Ring Buffer

Character buffers are often useful in embedded systems for a variety of tasks. This article presents a suggested implementation, which you can download from the articles page.

1. Typical Uses
2. Interface
3. Design
4. Implementation
   1. buffer_put
   2. buffer_get
   3. buffer_size

Typical Uses

Ring buffers are often used in hardware drivers, for example in interrupt-driven UART and SPI. Another use for character buffers is 'task queues': tasks can be represented as non-zero characters and 'queued' in the buffer. An application program then pulls the next task from the buffer and runs the corresponding routine. This can be useful when dealing with asynchronous user input (for example, from buttons). Simple task queues can be used as part of a very basic operating system.

Design

The ring buffer design allows a 'circular queue' data structure to be implemented in a statically allocated array. Dynamic memory allocation is best avoided in most embedded systems in order to reduce code size and performance while ensuring that memory use is 'bounded'.

A queue can be implemented as an array, with each element storing one byte of data (typically a character). 'head' and 'tail' indexes keep track of buffer occupancy. The 'ring' is formed by allowing the indexes to 'wrap' around the end of the array back to the beginning. This is especially useful since these buffers are typically written to and read from at somewhat random times.

Interface

The buffer interface should provide some version of the following routines:

• initialization - set the buffer up in an 'empty' state
• 'put' - insert a character into the buffer
• 'get' - remove a character from the buffer
• 'size' - report the occupancy of the buffer

Implementation

Here is my implementation of the 'ring' buffer, which you can download from the articles page. We begin by defining a simple 'buffer' data structure to hold the buffer array and 'head' and 'tail' indexes. I have chosen to allow array sizes that are powers of 2 because it allows me to use bitwise operations rather than comparisons when 'wrapping' the head and tail. In this case, the BUFFER_BITS must not be larger than 8 (for a buffer size of 256).

struct buffer
{
    unsigned  char data[1<<BUFFER_BITS];
    uint8_t head , tail;
};

There are many possibilities for how to use the head and tail pointers. In my implementation, I chose the following rules:

1. head and tail start at 0, head == tail indicates an 'empty' buffer.
2. to write to the buffer, advance the tail and write at its new location.
3. to read from the buffer, advance the head and then read from it.
4. the head and tail advance to the 'right'

The rules are somewhat arbitrary, as long as you follow them consistently and ensure that your scheme works. I suggest trying it out of a piece of paper before writing any code. My scheme results in one buffer position being 'wasted' due to rule 1 above.

buffer_put

The following function puts a byte into the buffer. Its first step is to attempt to advance the tail pointer, wrapping it if needed. An error code is returned if the next tail position would collide with the head (that is, the buffer is full).

char buffer_put( struct buffer  *b, char c )
{ 
    /* buffer is full if the next tail pointer position is the position of the 
     * head pointer */
    if ( ( b->tail+1  == b->head ) ||
         ( b->head == 0  && ( (b->tail+ 1) & (1<<BUFFER_BITS ) ) )
      )
         return 0; /* failed to put */
    if ( (++(b->tail)) &  (1<<BUFFER_BITS) )  /* adjust the tail pointer */
        b->tail =  0;
    b->data[b-> tail] = c; /* put into buffer at tail */ 
    return c;
}

This function takes advantage of the 2^n size of the buffer. The tail pointer will only have a '1' in the same position as the mask 1<<BUFFER_BITS if it has reached the value of the size of the buffer array. Since we start counting at 0, this means that the tail must be wrapped to 0 because it has exceeded the last allowed value. For example, in an 8-position buffer, an index may have values between 0 and 7. At 7, the next index is 0 rather than 8.

buffer_get

This function adjusts the head and then returns the byte found at its new position. The same 'wrapping' technique is used when moving the head index.

char  buffer_get( struct buffer *b ) 
{
    if( b->head  == b->tail ) /* buffer is empty: nothing to get */ 
        return 0;
    if(  (++(b->head)) &  (1<<BUFFER_BITS) ) /* adjust the head pointer */ 
        b->head = 0; 
    return b->data[b-> head];
}

buffer_size

This function returns the occupancy of the buffer. The buffer is either empty (head == tail) or not. A non-wrapped buffer's size is simply the difference between the tail and head positions. A wrapped buffer's size is the opposite of that.

uint8_t buffer_size( struct buffer * b )
{
    if( b ->head == b->tail )
         return 0;
    return b-> head < b->tail ?
        b->tail  - b->head : (1<< BUFFER_BITS) - b->head +  b->tail;
}