Fastest FIFO with macros for use embedded devices

Question

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 select uint8_t or uint16_t automatically, depending on _depth. The GCC extention typeof would be great for this, but only returns int or long
• 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);
}

Answer 1

• Since you've mentioned that this code is meant to be used in ISRs, I have to notice an absence of synchronization.

• _fff_write_safe should inform the caller on whether write was successful.

• To enforce the power-of-two depth, pass a power instead of depth, e.g.:

  #define _fff_create(_type, _depth, _id)                 \
      struct {uint8_t read; uint8_t write; _type data[1 << _depth];} _id = {0,0,{}}
  

Answer 2

To answer one of your specific questions:

What is the best way to limit the _depth parameter to 2^n values?

The conventional test is that these are the only values where x & (x-1) is zero (and x itself is non-zero). You can combine that with _Static_assert in C11, or with one of the ways to ASSERT expressions at build time in C (Stack Overflow).

Answer 3

Generally macros are ALL CAPS to identify that they are macros.

Underscore at the beginning of a variable or function name is generally reserved and should be avoided.

Optimization is a good thing when working with hardware, one needs to make the code as small and as fast as possible. There are other ways to optimize C besides using macros. The use of inline functions should be preferred over the use of macros. Macros are extremely difficult to debug, and make extending the code or maintenance a fairly large problem. Using macros forces the use of logic flow for compound statements

    do{_id.read=0; _id.write=0;} while (0)

I've also seen

    if (1) { statementA; StatementB; }

While the compiler will correctly optimize the previous statement, someone reading or modifying the code may wonder why the code was written this way, especially someone unfamiliar with C macros.

When optimizing C use registers as much as possible rather than normal variables, this makes the code smaller, and registers are faster than normal variables.

To make the code more portable perhaps the use of typeof can be changed to __typeof. You are probably aware that typeof is a compiler extension and not defined by all C compilers.