A more efficient circular FIFO buffer

[David Bender 28]

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;
	if(rr->head){
		ret += rr->tail;
		ret -= rr->head;
		ret %= rr->buffer_size;
	}
	return ret;
}
#endif

#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){
	assert(!revring_full(rr));

	register unsigned idx = rr->head;
	--idx;
	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){
	assert(!revring_empty(rr));

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

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

[Rickta59 589]

What did you compile this with? Doesn't seem to be happy in gcc

[David Bender 28]

This isn't actually the original code I used; this is the "cleaned up" version to illustrate the concepts. It seems I copied the wrong file up; I made the edits that should fix it.

[jpnorair 340]

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.

[David Bender 28]

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.