Circular Buffers

Go To Last Post
12 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hi all,

I'm trying to implement the circular buffers in C for AVR. Any one have good experience?

#define BufferSize 10

unsigned char Buffer[BufferSize]; 
unsigned char *In_Buff_Ptr;
unsigned char In_Buff_cnt; 
unsigned char *Out_Buff_Ptr; 
unsigned char Out_Buff_cnt;
unsigned char GetData[BufferSize]; 


void Put_Buff(unsigned char data)
{
	if(In_Buff_cnt < BufferSize) 
	{			
		*In_Buff_Ptr++ = data;	// load Value and increase pointer  
		In_Buff_cnt++;          // Increase counter
  }
	else
	{ 														  
		In_Buff_Ptr = Buffer; 	// reset pointer
		In_Buff_cnt = 0; 				// clear counter
		*In_Buff_Ptr++ = data;	// load Value and increase pointer 
		In_Buff_cnt++;          // Increase counter
	}
}

int Get_Buff()
{
	if(Out_Buff_cnt == In_Buff_cnt)
	{
		return -1;
	}
	else
	{
		if(Out_Buff_cnt < BufferSize) 
		{ 
			Out_Buff_cnt++;             // increase counter
  	}
		else 
		{
			Out_Buff_Ptr = Buffer; 			// reset pointer
			Out_Buff_cnt = 0;           // clear counter
			Out_Buff_cnt++;             // increase counter
  	}

		return *Out_Buff_Ptr++;
  }
}
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hi,

Check out this doc - it has a useful circular buffer example http://www.ganssle.com/tem/tem110.pdf
Also check out the issue 111 for the bugfix :-)

Regards, Mike.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

If you can use a power of 2 (e.g. 16) for your buffer size it can help, since the wrap-around is reduced to a simple AND.

Four legs good, two legs bad, three legs stable.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

When you roll around ,don't clear the count. Also, using the return value as both status and your data can give grief - especially if the compiler wants to sign extend your return value. Best to pass a pointer for the data and use the return value just as status.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
If you can use a power of 2 (e.g. 16) for your buffer size it can help, since the wrap-around is reduced to a simple AND.
I try to leave from that way. Thanks.
Quote:
When you roll around ,don't clear the count. Also, using the return value as both status and your data can give grief - especially if the compiler wants to sign extend your return value. Best to pass a pointer for the data and use the return value just as status.
Thanks for your help.I'm not understand your suggest, could you more explain ?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0
     In_Buff_Ptr = Buffer;    // reset pointer 
      In_Buff_cnt = 0;             // clear counter 

Why do you clear the counter when you 'wrap' the pointer? You want a circular buffer, it is meant to go around in a circle. You only need to increment the counter when you put something in and decrement it when you take something out.

Say you have a buffer of 10 entries:
put 5 items in
take 5 items out
the in and out pointers are at location 5
put 6 items in (the pointer wraps around). If you reset the count at this point, it will tell you that there is only 1 item in the buffer - not true.

You use the return value of -1 as an empty status as well as the data value. Perfectly legal, but can cause confusion.

something like
char GetBuff(char *ch)

that way you separate data from status. The reasons are many.

Read "Code Complete" for a thorough explanation. Also, do yourself a favour and get a good book on data structures - you're re-inventing code that has been written many times before and you're not understanding how it should work.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Imagine the circular buffer is an array of size N with index 0 to N-1. You put chars in until the 'in' index equals N, then reset to zero. You take things out at the 'out' index starting at zero, and reset at N. If the indices are equal, there are no chars in the buffer.

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

firmware wrote:
I'm trying to implement the circular buffers in C for AVR.
If you're going to have an ISR place data in the queue you'll probably want to disable interrupts when you modify parts of the control information that the ISR will also modify, e.g. the queue counts.

Also, it is typical to encapsulate all of the control data and the buffer in a structure. One advantage of this is that it allows you to use the same code operate on several different queues using a pointer to refer to the queue of interest. It may also result in smaller/faster code that uses the index registers instead of absolute references.

Don Kinzer
ZBasic Microcontrollers
http://www.zbasic.net

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

If you have an 'in index' or an 'in pointer', thats the only thing that gets incremented in the interrupt handler. To get a char out of the interrupt buffer, you use the 'out index' or the 'out pointer', so no need to disable interrupts when getting chars.

Imagecraft compiler user

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Using a pointer AND a counter is redundant; the first can be derivated from the second anyway.

Also, you really /have/ to use a power of two. Using a power of two size remove most of the branches out of this algorythm.

You can also use the 'bit field' C notation and leave the compiler do the whole 'anding' lot for you.

This implementation is an example, I didn't compile it, I typed it as is :D I use this system in hundred of places tho, it;s one of my favourite 'lock free' method :D

#define BUF_SIZE 16

typedef struct SCircular {
	uint8_t buffer[BUF_SIZE];
	uint8_t fill : 4;
	uint8_t done : 4;
} SCircular;

/*
	Note that I /could/ theoricaly have fill/done in one byte, but thats
	creating a potential race condition, which would be silly since the
	purpose of the excercise is to remove a contention point!
 */

/*
	Add a byte to the buffer, presumably from the 'filler' thread/interupt.
 */
void *circular_fill(SCircular *c, uint8_t b)
{
	/*
		fill will 'auto clip' to 4 bits here
	 */
	c->buffer[c->fill++] = b;
}

/*
	Get a byte from the buffer. return non-zero if *b was filled, zero otherwise
 */
int circular_get(SCircular *c, uint8_t *b)
{
	if (c->fill == c->done)
		return 0;
	*b = c->buffer[c->done++];	// free auto clip!
	return 1;
}

Author of simavr - Follow me on twitter : @buserror

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

And just in case you need more examples, there are two (a basic and an advanced version) avalaible for download on my website.

- Dean :twisted:

Make Atmel Studio better with my free extensions. Open source and feedback welcome!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thanks every body.