Jump to content

A more efficient circular FIFO buffer

Recommended Posts

For my purposes I just needed a simple FIFO buffer, but implementations I saw either wasted a byte of buffer space, required extra fields or were not very performant. This implementation provides full and empty conditions, a count (if you need it, I did not test it, just fair warning). You can add/remove bytes efficiently even if your buffer is not a power of 2 size.

#ifndef __REVRING_H__
#define __REVRING_H__

#include <stdint.h>

/** @brief Ring buffer that decrements indices as data is stored. */
struct revring_s {
	unsigned head;
	unsigned tail;
	unsigned buffer_size;
	uint8_t buffer[];

/** @brief Initialize reverse ring buffer. */
void revring_init(struct revring_s* rr, unsigned buffer_size);

static unsigned revring_empty(const struct revring_s* rr);

static unsigned revring_full(const struct revring_s* rr);

static unsigned revring_count(const struct revring_s* rr);

void revring_add_byte(struct revring_s* rr, uint8_t byte);

uint8_t revring_remove_byte(struct revring_s* rr);

static inline unsigned revring_empty(const struct revring_s* rr){
	return rr->head == rr->tail;

static inline unsigned revring_full(const struct revring_s* rr){
	return rr->head == 0;

static inline unsigned revring_count(const struct revring_s* rr){
	unsigned ret = rr->buffer_size;
		ret += rr->tail;
		ret -= rr->head;
		ret %= rr->buffer_size;
	return ret;
#include <assert.h>
#include "revring.h"

void revring_init(struct revring_s* rr, unsigned buffer_size){
	rr->head = buffer_size;
	rr->tail = buffer_size;
	rr->buffer_size = buffer_size;

void revring_add_byte(struct revring_s* rr, uint8_t byte){

	register unsigned idx = rr->head;
	rr->buffer[idx] = byte;

	if(0 == idx)
		idx = rr->buffer_size;
	if(rr->tail == idx)
		idx = 0;

	rr->head = idx;

uint8_t revring_remove_byte(struct revring_s* rr){

	register unsigned idx = rr->tail;
	const uint8_t* ret = rr->buffer + idx;
	if(0 == idx)
		idx = rr->buffer_size;

	/* If full, then point head to where tail is currently. */
		rr->head = rr->tail;
	rr->tail = idx;
	return *ret;

Link to post
Share on other sites

Ring buffers are not good solutions for fast performance.   For that, you want to use an A/B buffer.  Yes, you need double the memory, but that's the tradeoff.  To get "best of both worlds" I've found that, quite often, it is faster to do a DMA memcpy to shift the buffer (only happens when limit is reached) than it is to do the ring-buffer logic on every byte entered or removed.  On MSP430's with DMA you can move 2 bytes in 1 cycle, plus some setup, whereas all those if's probably burn 20-30 cycles for each byte entered/removed.  So do the arithmetic and figure out what is the best choice based on your buffer size.

Link to post
Share on other sites

I'm working on G2553 and below, so I will stick to the ring buffer; not wasting an extra byte is important when you got a dozen buffers. (Note that I am using uglier macro code to cut down on the cycles; I only published cleaner "functional" code to make the concept clearer). The A/B thing sounds good for use on an ARM though.

Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

  • Create New...