Circular buffers

Started by swmcl 2 weeks ago15 replieslatest reply 2 weeks ago112 views

Hi,

I'm not that advanced at C programming but I need to build a circular buffer for my serial data.  The serial data is in a frame that is from 9 bytes to 48 bytes in length.  I was thinking of a buffer that could process up to 16 frames.  Any help in defining the buffer would be greatly appreciated.  I'm using a PIC to process some serial data.

Cheers,

Steve

MPLABX 5.10 and XC8 2.00

[ - ]
Reply by allivFebruary 5, 2019
[ - ]
Reply by dnjFebruary 4, 2019

I am of the mind that I can either write out everything and you won't really learn what is happening or I can steer you in the right direction and let you figure out the fine details. You won't learn unless you make a lot of mistakes in getting to the right solution. You learn what doesn't work. If you get it to work on your first try, then you have no idea what you did right and have no idea where you can be flexible and where you have to be precise.

That said, you implement a circular buffer from a linear buffer where you have to check for an your index every time you increment it so that it gets reset to zero when it goes out of bounds. 

Here is a trick. I like to use lengths which are based on a power of 2. Let's say, a length of 8. Instead of actually checking for a value of 8 and resetting to zero, you perform a logical AND of 7 at each increment. Try it and see what happens. The bit pattern is the key.

For a serial circular buffer, you need two indices. One is the front index and the other one is the rear index. 

When you get a character from the serial port, you place it at the location of the front index and increment the index.

In your program loop, you check to see if there are any available characters. You take characters from the position of the rear index until there are no available characters. Study the relationship of the front and rear indices to figure out that condition.

You will also need to figure out how to determine whether the buffer is full and what to do about that. This can get tricky since you have to consider what happens at the ends of the linear buffer. The power of 2 length will play a part in this.

It isn't difficult at all if you have a couple of simple functions. get, put, available, full

[ - ]
Reply by swmclFebruary 5, 2019

Thanks DNJ,

The examples I've seen only work with a buffer that has single bytes.  Mine would have a byte-array or something that was 48 bytes long.  The other issue for me is how to increment by 48.  I am aware of some of the other functions you speak of also.  

I look forward to the 'not difficult at all' part ... !

Cheers,

Steve

[ - ]
Reply by SolderdotFebruary 5, 2019

So you are using a kind of message protocol, each message consisting of up to 48 bytes.

Surely, inside that message there is some length information. So you can consider all messages as a linear stream and write any incimning data into a linear ring buffer. Later, you read the message out of the buffer byte by byte and check the length information to ensure that only this message's data is moved out of the ring buffer.

If there is no length information but a kind of end-of-message indication, you can do it the very same way.

If the length information is not part of the structure but a kind of side-band information, you can add that info to the ring buffer, by simply writing it into the ring-buffer. When reading the message, of course, this by needs to be extracted.

Another option would be having 16 buffers of 48 bytes. Each buffer is meant to store a single message. You could use a two-dimensional array for that, thus each buffer will be addresses via an index in the range of 0 to 15. Now you have two counters: A write counter and a read counter. Any incoming message you write into the buffer at which the current write counter indicates, then the write counter is incremented. Reading a message takes place from the buffer the read counter indicates, then the read counter is incremented. Of course you need to handle wrapping of the counters and also figure out how to handle buffer overruns and empty conditions. And of course, somehow you need to be able to identify how many bytes in a buffer are actually consumed by a message. So you may want to have services like "is_msg_present", "get_msg" and "get_next_msg_length".


[ - ]
Reply by dnjFebruary 5, 2019

Right. My explanation is for the general. I can't count the number of times that I have implemented a circular buffer for serial communications and other mechanisms. My projects involve reading a automotive CAN network so I use circular buffers with elements large enough to hold a CAN message. Takes too long to build linked lists when hundreds and thousands of messages per second show up.

But, it remains the same. My needs most always require that I get packets or bytes when they are available. Your definition of "available" is the only thing that has changed. For you, "available" means that there are 48 or more bytes and you fetch only 48. There are no changes to the incrementing of the indices.

For known lengths of bytes, I would allow (as has been noted) for a couple of message lengths of buffer space - and still a power of 2. I've been known to have buffers of 1024 or 2048 when the volume of data is high and my ability to process is low. Give yourself some room. Stick with lengths of powers of 2.

[ - ]
Reply by BVRameshFebruary 5, 2019

Adding to what dnj has proposed, your circular buffer should be larger than your average packet length, so that even if the processor is caught in some loop, after exiting the whole packet should be available for processing.



[ - ]
Reply by atomqFebruary 5, 2019

Following @dnj it is good practice to check the number of available bytes to fill in the buffer prior to do it.

The best solution is to design a circular buffer of 256 bytes with uint_8 frame_start and same size frame_stop data markers (if both the throughput and the requirements for the the amount of data allow). In this case you don't need to check the buffer's overflow..

Cheers,

Adam.

[ - ]
Reply by swmclFebruary 5, 2019

Thanks guys,

The frame size is fixed by external hardware.  I can't do anything about it.  The frame will vary from 9 to 48 bytes.  It does have start and finishing byte arrays.  This means a power-of-2 size for the frame would be 64 bytes.  So the size of the buffer would be 8 or 16 frames.  For higher activity I'd need to go to the 16 frame size which is 1024 bytes some of which are unused.

Its the way C is written that stumps me.  I speak English !

[ - ]
Reply by mr_banditFebruary 5, 2019

Consider using a struct for one message && use a circular buffer of structs. The struct can actually be a union of several message types.

A struct is just a mapping onto memory. A union is just a set of mappings onto the same memory. Consider:

typedef struct

{

uint8_t   buf_u8[8];

uint16_t  buf_u16[4];

} FOO;

uint8_t  *ptr;

FOO foo = { { 0x12, 0x23, 0x34, 0x45, 0x56, 0x67, 0x78, 0x89 },

            { 0x1223, 0x3445, 0x5667, 0x7889 } };

ptr8 = (uint8_t *) &foo.buf_u8;

ptr16 = (uint8_t *) &foo.buf_u16;

for( int i = 0; i < 8; i++ )

{

    printf( "u8[ %u: %02x]  " i, ptr8[i] );

    printf( "u16[ %u: %02x]\n", i, ptr16[ i ] );

}

//==============

Note this walks both arrays in the struct using a uint8_t pointer. One of two things will happen: either both array values will == each other  (0x12  0x12)  OR they will be flipped (0x12 0x23) - why? (hint: byte sex)


//=================================================

// try:

typedef union

{

uint8_t   buf_u8[8];

uint16_t  buf_u16[4];

} BAR;

uint8_t  *ptr;

BAR bar = { { 0x12, 0x23, 0x34, 0x45, 0x56, 0x67, 0x78, 0x89 } };

// try printing both buffers and see what happens


[ - ]
Reply by swmclFebruary 6, 2019
OK.  So I have tried to digest several online blog type articles.  They are all shying away from actual examples and thus speak in pseudocode as it were ... So here are my early attempts.  This does compile.


In the .h file,

+++++++++++


#define circular_buffer_size 768  // 16 * 48 = 768


typedef struct circular_pointer_buf_t
{
    uint8_t * buffer;
//    size_t head;
//    size_t tail;
//    size_t max; //of the buffer
    uint16_t head;
    uint16_t tail;
    uint16_t max;
    bool full;
};

typedef struct circular_buf_t
{
    uint8_t buffer[circular_buffer_size];
//    size_t head;
//    size_t tail;
//    size_t max; //of the buffer
    uint16_t head;
    uint16_t tail;
    uint16_t max;    
    bool full;
};

extern struct circular_buf_t buf_a;
extern struct circular_buf_t buf_b;

extern struct circular_pointer_buf_t buf_c;
extern struct circular_pointer_buf_t buf_d;

+++++++++++++

In the .c file,

++++++++++++

struct circular_buf_t buf_a;
struct circular_buf_t buf_b;

struct circular_pointer_buf_t buf_c;
struct circular_pointer_buf_t buf_d;

++++++++++++

I can see how the size of buf_a and buf_b are made but I don't understand how to intantiate the buf_c and buf_d types.

I even purchased a book called "Making Embedded Systems" and it also skips over how to instantiate the buffers (In my opinion at this stage..)

I just don't get the pointer !



[ - ]
Reply by mr_banditFebruary 6, 2019

#define NUM_MSG     16      // entries in the circular q

#define MSG_SIZE    48      // a message

typedef struct

{

    uint8_t msg_buf[ MSG_SIZE ];

    uint16_t head;

    uint16_t tail;

    uint16_t max;

    bool full;

} BUF_t;

typedef struct

{

    BUF_t    buf[ NUM_MSG ];

    uint16_t head;

    uint16_t tail;

    uint16_t max;    

    bool full;

} CIRC_Q_t;

// these are not needed unless the .h file is used by other files

// the better way is to define functions that access the queue info

extern CIRC_Q_t circ_q;

+++++++++++++

In the .c file,

++++++++++++

// "instantiate" is a C++ term, not a C term

// this defines/allocates the arrays

// it does not fill in the arrays

CIRC_Q_t circ_q;

int i;

// setup the circ_q

circ_q.head = 0;

circ_q.tail = 0;

circ_q.max = NUM_MSG;

circ_q.full = FALSE;

// now setup each BUF_t struct in the circular buffer array

for( i = 0; i < NUM_MSG; i++ )

{

    circ_q[ i ].head = 0;

    circ_q[ i ].tail = 0;

    circ_q[ i ].max  = MSG_SIZE;

    circ_q[ i ].full = FALSE;

}

// to use

BUF_t   *buf_ptr;

uint8_t *msg_buf;

buf_ptr = circ_q[ circ_q.head ].buf;    // points to the struct BUF_t

msg_buf = buf_ptr->msg_buf;

// this should get you started

// you should draw this out so you can see how the structs interact

// basically, you have BUF_t which is for a particular message buffer

// then you have an array of structs which defines the circular queue

// of the BUF_t structs

[ - ]
Reply by swmclFebruary 6, 2019

Thanks Bandit,

I think I read your post through and understood almost all of it in one pass.  I was wondering how to increment a counter by 48 overnight but now I see you've split it into frame junks.

I'll give it a go.  Thank you for your patience with small grasshopper !

[ - ]
Reply by swmclFebruary 6, 2019

Am I correct in thinking that the uint16_t variables can now be uint8_t as they never get to see a number beyond 256 ?

[ - ]
Reply by swmclFebruary 6, 2019
OK.  I have some code based on Bandit's reply but I have a further question... Why is there a structure within a structure ?  Don't I just need an array within a structure ?  I can't see why I would ever use  BUF_t.head  nor  BUF_t.tail  nor  BUF_t.max  nor  BUF_t.full .  At least I should just have the array msg_buf inside the lower structure surely ?


My .h file is:

++++++++++++++++++++++++++++++++++++++++++

/*
 * File:   
 * Author:
 * Comments:
 * Revision history:
 */

#ifndef FRAMES_AND_BUFFERS_H
#define    FRAMES_AND_BUFFERS_H

/**
  Section: Included Files
*/




#include <xc.h>
#include <stdint.h>
#include <stdbool.h>
#include <stddef.h>
#include <float.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

#include "mcc.h"



/**
  Section: Macro Declarations
*/


#define NUM_MSGS_IN_FIFO_RING_BUFFER  16
#define SIZE_OF_EACH_MSG_IN_FIFO_RING_BUFFER   48

/**
  Section: Data Type Definitions
*/

typedef struct
{
    uint8_t msg_buf[SIZE_OF_EACH_MSG_IN_FIFO_RING_BUFFER];
    uint8_t head;
    uint8_t tail;
    uint8_t max;
    bool full;
}BUF_t;

typedef struct
{
    BUF_t buf[NUM_MSGS_IN_FIFO_RING_BUFFER];
    uint8_t head;
    uint8_t tail;
    uint8_t max;    
    bool full;
}CIRC_Q_t;


/**
 Section: Global variables
*/     

extern CIRC_Q_t incoming_UART1;
extern CIRC_Q_t outgoing_UART1;


/**
  Section: Frames and Buffers APIs
*/

void Initialise_Incoming_UART1_FIFO_Ring_Buffer(void);

void Initialise_Outgoing_UART1_FIFO_Ring_Buffer(void);




#ifdef    __cplusplus
extern "C" {
#endif /* __cplusplus */

#ifdef    __cplusplus
}
#endif /* __cplusplus */

#endif    /* FRAMES_AND_BUFFERS_H */

++++++++++++++++++++++++++++++++++++++++++++


my .c file is:

++++++++++++++++++++++++++++++++++++++++++++


/**
  Section: Included Files
*/


#include <xc.h>
#include "mcc.h"

#include "frames_and_buffers.h"

/**
  Section: Macro Declarations
*/



/**
  Section: Global Variables
*/

CIRC_Q_t incoming_UART1; // declaring incoming as a global variable of type CIRC_Q_t
CIRC_Q_t outgoing_UART1; // declaring outgoing as a global variable of type CIRC_Q_t


/**
  Section: Frames and Buffers APIs
*/

void Initialise_Incoming_UART1_FIFO_Ring_Buffer(void)
{
    uint8_t i,j = 0x00;
    
    incoming_UART1.head = 0x00;
    incoming_UART1.tail = 0x00;
    incoming_UART1.max = NUM_MSGS_IN_FIFO_RING_BUFFER;
    incoming_UART1.full = false;
    
    for(i=0;i<NUM_MSGS_IN_FIFO_RING_BUFFER;i++)
    {
        for(j = 0;j < SIZE_OF_EACH_MSG_IN_FIFO_RING_BUFFER;j++)
        {
            incoming_UART1.buf[i].msg_buf[j] = 0x00;
        }
        
        incoming_UART1.buf[i].head = 0x00;
        incoming_UART1.buf[i].tail = 0x00;
        incoming_UART1.buf[i].max  = SIZE_OF_EACH_MSG_IN_FIFO_RING_BUFFER;
        incoming_UART1.buf[i].full = false;
    }
    
}

void Initialise_Outgoing_UART1_FIFO_Ring_Buffer(void)
{
    uint8_t i,j = 0x00;
    
    outgoing_UART1.head = 0x00;
    outgoing_UART1.tail = 0x00;
    outgoing_UART1.max = NUM_MSGS_IN_FIFO_RING_BUFFER;
    outgoing_UART1.full = false;
    
    for(i=0;i<NUM_MSGS_IN_FIFO_RING_BUFFER;i++)
    {
        for(j = 0;j < SIZE_OF_EACH_MSG_IN_FIFO_RING_BUFFER;j++)
        {
            incoming_UART1.buf[i].msg_buf[j] = 0x00;
        }
        
        outgoing_UART1.buf[i].head = 0x00;
        outgoing_UART1.buf[i].tail = 0x00;
        outgoing_UART1.buf[i].max  = SIZE_OF_EACH_MSG_IN_FIFO_RING_BUFFER;
        outgoing_UART1.buf[i].full = false;
    }
    
}

/**
  End of File
*/

+++++++++++++++++++++++++++++++++++++++++++++


[ - ]
Reply by mr_banditFebruary 6, 2019

There are many different ways of doing circular buffers. in my example, I defined a BUF_t that assumed a circular buffer - I threw it together quickly. In reality, you only need the buffer and its max length (good practice) and the actual count.

The second struct CIRC_Q_t has the set of BUF_t structs and the head/tail/max/full of the circular queue. This is the actual circular queue.

Why use a struct in a struct? I did it as an example for you. There are cases where you want/need to do so. For example, the Linux kernel state struct has nested structs in order to keep track of various things, where each thing is best handled via a struct.

Take your case. You need to handle a circular buffer of buffers. If you can guarantee that a message will NEVER have a 0x00, and you can guarantee the buffer length is fixed, you could use

uint8_t my_buffers[ NUM_BUFFERS ][ BUF_LEN ];

but - you did not specify the message format. And - even if a message is a text string, you need to re-init the buffer once you "take it off the queue" as good practice - meaning you set the buffer to all 0's. Personally, setting a "msg.msg_len = 0;" is easier

Did you try the union example?

To the subject of style: you will encounter various coding styles and coding standards as you progress in this field. There are several reasons for them (not falling off cliffs, consistency of code across a group of developers, etc). Two of these are about names & their length, and the other about white space.

First, you have pretty good majic and variable names. A bit wordy for me, but you have majic number names - much better than many new programmers!

You have a good start on white space && put the "{" in the right place (que flame wars).. and you have spaces around your operators. (where to put braces is one of the perennial flame wars in C - I put the { and } on the same indent level so i can see a code block at a glance.

Consider

for(j = 0;j < SIZE_OF_EACH_MSG_IN_FIFO_RING_BUFFER;j++)

for( j = 0; j < SIZE_OF_EACH_MSG_IN_FIFO_RING_BUFFER; j++ )

Glance at these. Which is easier for you to pick out the individual operations, like j++ ??

READ CODE. READ LOTS OF CODE. Decide what you want your style to be. Good style will save your ass and prevent bugs.