UPDATE (a year later)
Since this post the code has turned into a small library called fifofast and is hosted on github under the MIT License. This note is meant for anyone who stumbled across this post in search of a fast fifo.
Thanks again for your help guys!
Objective
I'm totally aware that there are dozens of FIFO implementations, but on small, low power microcontrollers every processor cycle and byte of RAM can matter significantly. Because it is used very commonly, I've written a small, macro-based library with the following requirements:
- generic implementation (any data type, any size, any amount of FIFOs)
- fast (from ISR's function calls take very long)
- low overhead RAM usage
- user-friendly, all macros should work just like normal C functions (or at least throw errors at compile time)
Details on the implementation
On embedded systems typically all memory is allocated static at compile time. With macros this can be abused to omit to store any pointers or array lengths, as the compiler knows where which data element is.
With _fff_create(_type, _depth, _id)
a anonymous structure is created and access by its identifier _id
. Although each of these structures may have an arbitrary amount of data storage included, this information can be extracted at compile time with the macro _sizeof_array(_id.data)
. The _depth
may only be 2^n to avoid the slow %
operator.
Naming conventions are as follows:
/*
Example: Description:
_name() Function-like macro. Unlike preprocessor macros these macros are intended to be used
like any other C function. The _ differentiates it from a normal function and hints
to possible subtle problems in use.
_name(id) Any normally written parameter of a function-like macro can be any C expression of
the correct type (such as uint8_t, uint16_t, ...)
_name(_id) Any parameter starting with _ is taken literally and must follow exact guidelines.
See description of macro in question for details.
type_t _tmp All local variables of a function like macro are marked with _ to prevent conflicts
substituted C names for the parameter. DO NOT pass any C identifier starting with _
_return Is used within compound statements as a label for the return value.
*/
Why I'm here (Problems, Questions, ...)
This kind of code is rather uncommon to see, and although I've worked with the pre-processor before, I've likely missed a few pitfalls.
Some things in particular are IMHO not ideal and I'd like your thoughts on them:
- I'm not quite sure whats the best way to access such a FIFO from varies .c files. How would you do this?
- The _function
_fff_read_safe(_id)
seems to be slightly bloated. When empty I want to pass the last element instead of a 0 to prevent unexpected behavior when storing typedef'd structs. - Currently there is a second _function for longer FIFOs
_fff_create_deep(_type, _depth, _id)
but I'd rather selectuint8_t
oruint16_t
automatically, depending on_depth
. The GCC extentiontypeof
would be great for this, but only returnsint
orlong
- What is the best way to limit the _depth parameter to 2^n values?
- both
_fff_read
macros require compound statements, which forcces use of a GCC compiler. Is there any way around this? - Are there any Best Practices with macros or their naming conventions I'm missing?
System Info
The library is meant primarily for use on 8bit AVR microcontrollers (<=20MHz, typically <=2kB RAM, <=32kB Flash) and has been written in AVR Studio 7 and compiled with GCC 4.9.2. The code has been tested with the built-in simulator and seems to be working fine.
Code
#ifndef __GNUC__
#error fifofast.h requires "compound statements" and "typeof" offered by a GNU C/ GCC compiler!
#endif
#ifndef __OPTIMIZE__
#pragma message "fifofast.h is intended to be compiled with optimization and will run VERY SLOWLY without!"
#endif
#define _sizeof_array(_array) (sizeof(_array)/sizeof(_array[0]))
// all function-like macros are suitable for ANY fifo, independent of data type or size.
// creates and initializes an anonymous _fifofast_t structure.
// _id: C conform identifier
// _type: any C type except pointers and structs. To store pointers or structs use typedef first
// _depth: maximum amount of elements, which can be stored in the FIFO. The value must be 2^n,
// n=2..8 for the normal version, n=2..16 for the "_deep" version.
// The actual depth is always 1 count less than specified in as this byte
// is required to distinguish a "full" and "empty" state
#define _fff_create(_type, _depth, _id) \
struct {uint8_t read; uint8_t write; _type data[_depth];} _id = {0,0,{}}
#define _fff_create_deep(_type, _depth, _id) \
struct {uint16_t read; uint16_t write; _type data[_depth];} _id = {0,0,{}}
// returns the maximum amount of data elements which can be stored in the fifo
// The returned value is always 1 count less than specified in _fifofast_create(...) as it is
// required to distinguish a "full" and "empty" state
// _id: C conform identifier
#define _fff_mask(_id) (_sizeof_array(_id.data)-1)
// allows accessing the data of a fifo as an array without removing any elements
// Like any array this function can be used as a right or left site operand. Attempting to access
// more elements than currently in the buffer will return undefined data on read and will have no
// effect on write. Accidental read/write operations outside the assigned data space are not possible.
// _id: C conform identifier
// index: Offset from the first element in the buffer
#define _fff_data(_id, index) _id.data[(_id.read+(index))&_fff_mask(_id)]
// returns the current fill level of the fifo (the amount of elements that can be read)
// _id: C conform identifier
#define _fff_used(_id) ((_id.write-_id.read)&_fff_mask(_id))
// returns the current free space of the fifo (the amount of elements that can be written)
// Function is slightly slower than _fifofast_used()
// _id: C conform identifier
#define _fff_free(_id) ((_id.read-_id.write-1)&_fff_mask(_id))
// returns true (any value != 0) if the fifo is full and (might) be faster that !_fifofast_free()
//#define _fff_is_full(_id) (_id.write == ((_id.read-1)&_fff_mask(_id))
// returns true (any value != 0) if the fifo is empty and is slightly faster that !_fifofast_used()
#define _fff_is_empty(_id) (_id.write == _id.read)
// flushes/ clears buffer completely
// _id: C conform identifier
#define _fff_flush(_id) do{_id.read=0; _id.write=0;} while (0)
// removes a certain number of elements
// MUST be ONLY used when enough data to remove is in the buffer! This function is especially
// useful after data has been used by _fff_data(...)
// _id: C conform identifier
// amount: Amount of elements which will be removed
#define _fff_remove(_id, amount) (_id.read = (_id.read+(amount))&_fff_mask(_id))
// removes a certain number of elements or less, if not enough elements is available
// _id: C conform identifier
// amount: Amount of elements which will be removed
#define _fff_remove_safe(_id, amount) \
do{ \
if(_fff_used(_id) >= (amount)) \
_fff_remove(_id, (amount)); \
else \
_fff_flush(_id); \
}while(0)
// returns the next element from the fifo and removes it from the memory
// MUST be used only when fifo is NOT empty, useful for repeated reads
#define _fff_read(_id) \
({ \
typeof(_id.data[0]) _return = _id.data[_id.read]; \
_id.read = (_id.read+1)&_fff_mask(_id); \
_return; \
})
// returns the next element from the fifo and removes it from the memory
// If no elements are stored in the fifo, the last one is repeated.
// _id: C conform identifier
#define _fff_read_safe(_id) \
({ \
typeof(_id.data[0]) _return; \
if(_fff_is_empty(_id)) \
_return = _id.data[(_id.read-1)&_fff_mask(_id)]; \
else \
{ \
_return = _id.data[_id.read]; \
_id.read = (_id.read+1)&_fff_mask(_id); \
} \
_return; \
})
// adds an element to the fifo
// MUST be used only when fifo is NOT full, useful for repeated writes
#define _fff_write(_id, newdata) \
do{ \
_id.data[(_id.write)&_fff_mask(_id)] = (newdata); \
_id.write = (_id.write+1)&_fff_mask(_id); \
}while(0)
// adds an element to the fifo
// If fifo is full, the element will be dismissed instead
#define _fff_write_safe(_id, newdata) \
do{ \
typeof(_id.write) _next = (_id.write+1)&_fff_mask(_id); \
if(_next != _id.read) \
{ \
_id.data[_next] = (newdata); \
_id.write = _next; \
} \
}while(0)
EDIT:
This code is meant to be a library for future projects and thus I can't show any "real" application code. To test the macros I just tossed them into a simple (and pointless) main.c file. All macros compile without any warnings. Variables are declared volatile to read them out in simulation (run step-by-step).
#include "Data/fifofast.h"
int main(void)
{
// create a fifo with 1024 elements of type uint8_t
_fff_create_deep(uint8_t, 1024, dbg_fifo);
// Check used/ free amount
volatile uint16_t dbg_used = 0;
volatile uint16_t dbg_free = 0;
dbg_used = _fff_used(dbg_fifo);
dbg_free = _fff_free(dbg_fifo);
// write some data to it (_safe version not required, we know there is enough space)
_fff_write(dbg_fifo, 17);
_fff_write(dbg_fifo, 19);
_fff_write(dbg_fifo, 23);
// Check used/ free amount again
dbg_used = _fff_used(dbg_fifo);
dbg_free = _fff_free(dbg_fifo);
volatile uint8_t dbg1 = 0;
volatile uint8_t dbg2 = 0;
volatile uint8_t dbg3 = 0;
// array-like access without removing elements
dbg1 = _fff_data(dbg_fifo, 0);
dbg2 = _fff_data(dbg_fifo, 1);
dbg3 = _fff_data(dbg_fifo, 2);
// remove first element
_fff_remove(dbg_fifo, 1);
// read 3 times, last read fails and returns previous element
dbg1 = _fff_read(dbg_fifo);
dbg2 = _fff_read_safe(dbg_fifo);
dbg3 = _fff_read_safe(dbg_fifo);
// Check used/ free amount a last time
dbg_used = _fff_used(dbg_fifo);
dbg_free = _fff_free(dbg_fifo);
while(1);
}
while(1)
looping? \$\endgroup\$ – pacmaninbw Oct 28 '17 at 15:39dbg3 = _fff_read_safe(dbg_fifo);
) it returns the same value asdbg2
, as the fifo is empty then (each "read" remove one element). For_fff_write_safe()
the FIFO must be full to show visible effect (the element will simply be not written).while(1);
is ony there for the simulation, in a real application there would obviously go some sort ofsleep()
function in there. \$\endgroup\$ – nqtronix Oct 28 '17 at 15:44