Latest news

Circular buffer for embedded systems

No comments

This post is part of the Memory Control Structures series. Also, read the other posts in the series:

Hello dear reader. With this article, we intend to expose a very legal resource to be implemented in embedded software that can be used for the most diverse applications, especially for data management coming from communication controllers, the Circular Buffer.

Circular buffer, let it sort the data for you

The circular buffer is known to experienced developers because it is a data structure that has a FIFO type data insertion and removal policy, which in free translation means: first to enter, first to exit.

In practical terms, the data packets that are inserted into this buffer will be sorted by arrival, so the withdrawal will be done in that order. The large differential of the circular buffer is at the point where there is virtually no overflow of the data area reserved for depositing the variables, because if the insertion control finds the end of the data area, it automatically points to the beginning of the data area overwrite the oldest content.

Hence known problems like processor-generated exceptions that occur when we try to deposit data in a larger memory area than the one previously allocated cease to occur. The figure below demonstrates how an intuitive (and canonical circular buffer) works.

Figure 1: Circular Buffer

The figure also points out that the insertion controllers (indexes) move in the same direction so that the removal index “persecutes” the insert, and both respect the rule, and when they reach the end of the memory area, they return to the start. Additionally, overflow controls of the amount of written or withdrawn data can be implemented to prevent content loss.

Interesting, but where can I use the circular buffer?

The circular buffer behaviour is ideal for implementing any data structure that is statically allocated and behaves like FIFO. As an example, mailboxes and queues can be implemented using the circular buffer as a kernel.

In my articles on DSP and digital control, you, reader, will realize that the implementation of filters and differential equations occur in the form of circular buffers. Applications do not stop there, circular buffers can be used for temporary storage of data coming from communication drivers. The best example of this is the reception of data from a UART, as shown in the figure below:

Figure 2: UART Circular Buffer

With the circular buffer, we can put our UART just to do what it should do, receive data. With this, each byte received is placed in the circular buffer. In this way applications that need UART data can access them or even wait for the buffer to be read to read the data later. In addition, this approach maintains the timeline of the arrival of the data, ie, data that arrives first will be processed first.

I want an example of a Circular Buffer!

The idea of this article is to solve a problem by presenting a resource for this, then talk about the best circular buffer implementations that escape its scope. In the files buffer_circ.c and .h the reader will find a basic implementation of the circular buffer. It contains routines for insertion, removal, and full or empty buffer checking. It also provides a macro to declare an initialized buffer structure. See the files:

/**
 * @brief Simple circular buffer implementation with basic management functions
 */
 
#ifndef __BUFFER_CIRC_H
#define __BUFFER_CIRC_H
 
#define BUFFER_SIZE 128
 
/** circular buffer management structure */
typedef struct {
  unsigned char data[BUFFER_SIZE];
  unsigned int  items;
  unsigned int  wr_ptr;
  unsigned int  rd_ptr;
} buffer_circ_t;
 
/**
 * @brief insert a stream data with size lenght to the buffer
 */
int buffer_insert(buffer_circ_t *b,void *data, unsigned int size);
 
/**
 *  @brief retrieves a stream of dat with specified size
 */
int buffer_retrieve(buffer_circ_t *b, void *data, unsigned int size);
 
/**
 *  @brief check if buffer is already full
 */
int buffer_full(buffer_circ_t *b);
 
/**
 * @brief check if a data stream with specified size will full the buffer
 */
int buffer_will_full(buffer_circ_t *b, unsigned int size);
 
/**
 * @brief makes the buffer empty
 */
int buffer_flush(buffer_circ_t *b);
 
/**
 * @brief  check if buffer is empty
 */
int buffer_empty(buffer_circ_t *b);
 
/** declare a initialized circular buffer */
#define CIRCULAR_BUFFER_DECLARE(name)  \
        buffer_circ_t name = {         \
          .data = {0},                 \
          .items = 0,                  \
          .wr_ptr = 0,                 \
          .rd_ptr = 0,                 \
        }
 
#endif

The BUFFER_SIZE constant determines in bytes the amount of memory reserved for use and can be changed according to the user’s needs.

#include "string.h"
#include "buffer_circ.h"

int buffer_insert(buffer_circ_t *b,void *data, unsigned int size)
{
  int ret = -1;
  unsigned char *ptr = (unsigned char *)data;

  if(b == NULL) {
    /* check your buffer parameter */
    return(ret);
  }

  if(size + b->items <= BUFFER_SIZE){

    /* the buffer has enough room, insert
     * stream.
     */
    unsigned int i;
    for(i = 0; i < size; i++) {
        b->data[wr_ptr] = *ptr++;

        /* increment the input index in form  if it
         * reach the buffer end, its placed in it
         * initial address again
         */
        wr_ptr =  (wr_ptr + 1) % BUFFER_SIZE;
        b->items++;
    }
    ret = 0;
  }

  return(ret);
}
int buffer_retrieve(buffer_circ_t *b,  void *data, unsigned int size)
{
  int ret = 0;
  unsigned char *ptr = (unsigned char *)data;

  if(b == NULL) {
    /* check your buffer parameter */
    return((ret = -1));
  }

  /* if the size requested fits on
   * current contents, extract
   * the data stream
   */
  unsigned int i;
  for(i = 0; (i < size) && (b->items != 0); i++) {
      *ptr++ = b->data[rd_ptr];
      rd_ptr =  (rd_ptr + 1) % BUFFER_SIZE;
      ret++;
      b->items--;
  }

  return(ret);
}
int buffer_full(buffer_circ_t *b)
{
  int ret = 0;
  if(b->items ==  BUFFER_SIZE) {
    ret = 1;
  }
  return(ret);
}

int buffer_will_full(buffer_circ_t *b, unsigned int size)
{
  int ret = 0;

  if(b->items + size > BUFFER_SIZE ) {
    ret = 1;
  }
  return(ret);
}
int buffer_flush(buffer_circ_t *b)
{
  int ret = 0;

  if(b != NULL) {
    b->wr_ptr = b->rd_ptr;
    b->items = 0;
  } else {
    ret = -1;
  }

  return(ret);
}
int buffer_empty(buffer_circ_t *b)
{
  return((b->items == 0? 1: 0));
}

Look at lines 28 and 53 of this file, this operation is called a circular increment. Its function is to increment the index in a unit, and in case of an encounter with the end of the memory area, the result of this operation will be index 0, that is, the beginning of the reserved area.

Conclusion

Circular buffers are interesting, safety features and prevent memory leak problems. For example, they are powerful and can serve as the basis for more complex data structures, they are versatile, their applications range from operating systems to digital signal processing. The above example has basic operations functions and serves as a starting point for more complex implementations.

Click here for example code on Github

FelipeCircular buffer for embedded systems

Leave a Reply

Your email address will not be published. Required fields are marked *