fifofast

A fast, generic fifo for MCUs.

Getting Started • Documentation • Under the Hood • Need Help? • Contribute • About • Credits

Introduction

First-In-First-Out (FIFO) buffers are one of the most used data structures, especially on micro controllers (MCUs) to handle data input/output in real time. Although there are countless of implementations, there wasn't a single one that is well optimized for entry level MCUs.

fifofast was specifically designed to consume as little CPU time and SRAM as possible, while providing more versatility and features than typical implementations. It is ideally suited to buffer serial data, ADC measurement results or arbitrary data shared between differnt time critical functions.

Key Features

• generic data: fifofast supports any data type, even custom typedef'd ones
• static memory: no additional overhead through dynamic memory management
• inline support: speeds up execution, especially from ISRs (Interrupt Service Routines)
• minimal RAM: a typical fifo has only 3 byte management overhead
• easy to use: all typical fifo functions are implemented (and they work like you expect)
• supports debugging: with the build-in debugger of Atmel Studio 7
• well documented: extensive use of comments within the source code

Limititations

• Fifo size:
  The fifo size is limited to 2ⁿ elements to make use of the fast wrapping functionality. Other sizes will be automatically rounded up.

• Element size:
  Normal fifos can store elements of any size. An exception are point-able fifos, which have a maximum element size of 255 bytes.

• Programm memory usage:
  Each function-like macro or inline function pastes new code at its location. Compared to a regular function-based fifo the program memory usage (flash) is higher.

Minimal Code Example

The declaration of a fifo is slightly different to support generic types, but they are accessed just like you'd expect. This is the minimum code example that can be compiled:

#include "fifofast.h"

// declare a fifo with 16 elements of type 'int_8' with the name 'fifo_int8';
// for access in other .c files, move the declaration into a .h file and include it in each .c file
_fff_declare(int8_t, fifo_int8, 16);

// initialize the fifo; use this macro only in one .c file (even if accessed from different files)
_fff_init(fifo_int8);

int main(void)
{
    // volatile prevents the compiler from optimizing the variable away
    volatile int8_t tmp;
    
    // write a value to the fifo
    _fff_write(fifo_int8, -42);

    // read back the value from the fifo
    tmp = _fff_read(fifo_int8);

    // 'tmp' contains now the value '-42'
    while(1);
}

You find this a variation of this snippet and much more in fifofast_test.c.

Getting Started

This section is written especially for everyone who is not familiar with the used tools. If you run into problems, please ask for clarification.

Step 1: Software and Tools

• Atmel Studio 7.0 (Build 1931) [free]
  The installer contains all tools you need to open, edit, compile, simulate and flash this code. If you favor another development tool, feel free to use it instead. (But please understand that I can not provide any support).
• An AVR8 ISP/JTAG programmer [optional]
  To program AVR8 MCUs I use the AVR Dragon. It can be also used as a debugger and is available within Atmel Studio by default.

Step 2: Download fifofast

• Clone this repository or hit Download and extract the .zip file.

Step 3: Browse the project

• Open the project in Atmel Studio:
  Either double click fifofast.atsln or open Atmel Studio and select "File -> Open -> Project/Solution..."

• Open any file of your interest:
  Select the file in the top right window "Solution Explorer". If the window is not visible, open it by pressing CTRL + ALT + L or selecting "View -> Solution Explorer" from the menu.

Step 4: Run the demo

• Compile the demo code:
  Press F7 or select "Build -> Build Solution" from the menu

• Run the demo code in the simulator:
  Press CTRL + F5 or select "Debug -> Start Debugging and Break" from the menu

• Place breakpoints:
  Left-Click on the lightgrey area left of the code to place or remove a breakpoint. Select lines with the comment "easy breakpoint".

• View variable values:
  When the code is paused, hover over any variable to display its value. Alternately you can "Right-Click -> Watch" to display the value in the "watch window".

• Run Code:
  Press F5 to run to the next breakpoint or F10 to execute one step.

Step 5: Going further

• Changing the target device:
  Press ALT + F7 and select "Device -> Change device..." to select your desired MCU.

• Program a real device:
  Connect your programmer, press ALT + F7 and select "Tool". Choose your tool, your programming interface and wire up your MCU. Press CTRL + ALT + F7 to flash the code to the MCU. Non-official programmers are not supported by Atmel Studio.

Documentation

API

To keep the documentation up-to-date with the least hassle, all configuration options, functions and their arguments are explained in a comment right in front of the declaration. See fifofast.h for more information. This section will be updated as soon as this project hits version 1.0.0.

Below you find information about the unusual functions/ macros in this implementation.

_fff_peek()

The macro _fff_peek() allows the user to access any element of the fifo as if it was an array. The first element of the fifo can be accessed with _fff_peek(fifo, 0), the following elements with an incremented index. See the illustration below:

array within fifo:
first element       v
      ┌───┬───┬───┬───┬───┬───┬───┬───┐
      │   │   │   │ d │ a │ t │ a │   │
      └───┴───┴───┴───┴───┴───┴───┴───┘
_fff_peek(fifo, 0)  ^   ^   ^   ^
_fff_peek(fifo, 1) ─────┘   │   │
_fff_peek(fifo, 2) ─────────┘   │
_fff_peek(fifo, 3) ─────────────┘

_fff_peek() is different from the typical _fff_read() and _fff_write() in multiple ways:

1. The macro can be used as a right side or left side argument to read from/ write to a specific location.
2. The data pointers are not changed. Reading or writing data will not remove/ add elements to/ from the fifo.
3. The current fifo level is not checked, allowing the user to access "empty space", too.

Thus _fff_peek() is especially useful for any algorithm that needs to modify present data with minimum overhead. This macro is only marginally slower than a regular array access and significantly faster than copying data to a temporary buffer

_fff_rebase()

If you receive strings through a serial interface you may want to use a fifo to store them temporally. Once completely received, you may want to use any of the build-in string functions on the stored data. This is not always directly possible. Consider the following case:

A fifo has received multiple chars, which might be stored in the internal array as shown below:

array within fifo:
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ n │ g │   │   │ s │ t │ r │ i │
└───┴───┴───┴───┴───┴───┴───┴───┘

However, the string functions expect a continuous data array without the "wrap" in the middle. To solve this, 0.8.0 adds the macro _fff_rebase(). It re-arranges the array, so that the first element is stored in the first position of the array.

array within fifo, after _fff_rebase():
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ s │ t │ r │ i │ n │ g │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘

To get a pointer to the first character, you can use _fff_peek():

char* first_char = &_fff_peek(fifo, 0);

Note: _fff_rebase() iterates across all elements in the array and the execution time increases linearly with depth and element size of the fifo. Use only when necessary.

Configuration

fifofast is designed to work out-of-the-box the majority of all use cases. To increase flexibility, but retain the performance for simple applications, you can set configuration options* in fifofast.h in the section User Config.

_{*As of 0.7.0 there is only one configuration option, but this is the place where other options would go.}

Pointable Fifos

Since release 0.6.0 you can create special fifos which can be referenced by a pointer. They are created very similar to normal fifos, but they have a _p as a suffix:

// declare pointable fifo
_fff_declare_p(uint8_t, fifo_uint8p, 4);

//init pointable fifo
_fff_init_p(fifo_uint8p);

To access such a fifo you have two options:

1. Pass its pointer to one of the implemented functions OR
2. Use its identifier in a macro

Generic data in C can only be archived with pointers and type casts. This can be very confusing, so let me demonstrate it with examples:

// 'fifo_uint8_p' has its own type depending on data type and depth, but its header looks like fff_proto_t,
// which is the only type excepted by the functions. Therefore you need to convert the pointer first:
uint8_t tmp_is_empty = fff_is_empty((fff_proto_t*)&fifo_uint8_p);

// alternatively you can create a new temporal pointer like this:
fff_proto_t* fifo_pointer = (fff_proto_t*)&fifo_uint8_p;

// to write you need to pass a pointer to the data location. NO type check can be performed!
uint8_t tmp_value = 42;
fff_write(fifo_pointer, &tmp_value);

// if you read data, you will only receive a void pointer. This needs to be cast into a pointer of the right
// type and then de-referenced:
uint8_t tmp_read = *(uint8_t*)fff_peek_read(fifo_pointer, 0);   // returns '42'

Type conversions are often considered to be an evil feature of C, as it hides all type mismatches. To reduce the chance of bug, only use these inline functions where absolutly required!

FIFO Arrays

For some applications you may need multiple identical fifos which can be selected with an index.

To create a fifo array, declare its structure first:

// declare an array (suffix _a) of fifos with 16 elements each.
_fff_declare_a(uint8_t, fifo_array, 16, 5);

Next initialize it and specify the amount of fifos you need:

// initialize an array (suffix _a) of 5 fifos.
_fff_init_a(fifo_array, 5);

Now you can access each fifo like this:

// write to the fifo at index 'fifo_nr' the value 'data'
_fff_write(fifo_array[fifo_nr], data);

Aligned Data

Because fifofast supports any data type, it may also be used to store frames for a serial data transmission. It is often useful to access the data not only in binary (raw) format, but also as a struct (header):

typedef struct  
{
    uint16_t control;
    uint8_t length;
    uint8_t id;
    uint8_t data[];
} header_t;

typedef union __attribute__((aligned(2), packed))
{
    uint8_t raw[32];
    header_t header;
} frame_u;

In this case the header variable control is 2 bytes large and must be stored aligned on most architectures. The union however is treated by default as a uint8_t array, so no alignment is enforced. To do this manually, GCC supports the __attribute__((aligned(n))). If a struct or union is declared like this, it will be correctly stored in the fifo.

To align any non-typedef'd data, you can declare a fifo like this:

_fff_declare(uint8_t __attribute__((aligned(4))), fifo_uint8, 4);

Under the Hood

To use fifofast you don't need to know its inner workings. This chapter is for those who seek to understand and learn.

The Typical Implementation

To get the best performance most fifos are based on an array for data storage. New elements are always placed at the next free index. When the fifo is read, the element of the earliest written index is returned. Example:

empty array:
┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │   │   │   │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘

write 4 elements:
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ a │ b │ c │ d │   │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘

read 2 elements:
┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │ c │ d │   │   │   │   │
└───┴───┴───┴───┴───┴───┴───┴───┘

After the array was filled at least once, new data must be added to the very first location. This is called a circular buffer (wiki)

after some time (example):
┌───┬───┬───┬───┬───┬───┬───┬───┐
│   │   │   │   │   │ e │ f │ g │
└───┴───┴───┴───┴───┴───┴───┴───┘

write 1 element:
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ h │   │   │   │   │ e │ f │ g │
└───┴───┴───┴───┴───┴───┴───┴───┘

To detect this overflow the straight forward approach is to use if(index > array_size){index = 0;}. This comparison has to be done for every fifo access. Branches take typically more cycles than arithmetic instruction, especially if a instruction pipeline (wiki) is used within the MCU.

2ⁿ Ring Buffer

If the array has a length of 2ⁿ elements, this if can be replaced with a faster logic instruction.

// increment the write index by 1
index = ((index+1) & (array_size-1));

Let's take the example above and observe the bahavior:

// start values
uint8_t array_size  = 8;
uint8_t index       = 5;

// first increment                v equivilant binary          v decimal result
index = ((5+1) & (8-1));   // == (0b0110 & 0b0111) == 0b110 == 6
index = ((6+1) & (8-1));   // == (0b0111 & 0b0111) == 0b111 == 7
index = ((7+1) & (8-1));   // == (0b1000 & 0b0111) == 0b000 == 0
index = ((0+1) & (8-1));   // == (0b0001 & 0b0111) == 0b001 == 1

As you can see, the logic operation works exactly as we want! Of course you don't have to deal with this detail, fifofast takes care of that for you. For more info look in the resource section.

Generic Data

Support for generic data types is not a part of C so fifofast has to use a creative work-around with macros. The key are the _fff_declare(...) macros:

#define _fff_declare(_type, _id, _depth)            \
struct _FFF_NAME_STRUCT(_id)                        \
{                                                   \
    _FFF_GET_TYPE(_depth) read;                     \
    _FFF_GET_TYPE(_depth) write;                    \
    _FFF_GET_TYPE(_depth) level;                    \
    _type data[_FFF_GET_ARRAYDEPTH16(_depth)];      \
} _id

Each macro "call" declares a new struct with an individual type and identifier. Therefore each of these struct can have members of a different size. However all structs have identical member identifiers, so if the _id known, a member can be accessed with _id.member like a normal struct. The compiler keeps track of all datatypes used within the structure and generates appropriate code.

Support

Get Help

Something doesn't work as expected? No worries! Just open up a new issue in the GitHub issue tracker. Please provide all information to reproduce your problem. If you don't have a GitHub account (and can't be bothered to create one,) you can contact me directly.

Contribute

Spotted an error? Open an issue or submit a pull request.

There is no CONTRIBUTING.md yet, sorry. Contributions will inherit the license of this project. If you have any questions, just ask.

About

Status

This project is currently classified as :
The developers are working on new features, optimisations, documentation or another part of the project. The code will be kept in working condition by updating dependencies, fixing bugs and solving issues with a high priority.

The first version of this fifo was created about a year ago. Since then I've used the macros successfully for multiple projects and different MCU architectures (AVR8, SAMG and SAML). fifofast is activly used for upcoming projects and will receive additional features whenever I need them.

Known Issues

• Non-Atomic Glitches:
  Accessing the same fifo from normal and ISR code can cause glitches with some function combinations. To prevent this, put the normal code in an atomic block if the fifo is also accessed in an ISR.

Planned Features

• none (for now)

Changelog

This project uses Semantic Versioning 2.0.0. During initial development (0.x.x versions) any major increase is substituted with a minor increase (0.1.0->0.2.0 instead of 0.1.0->1.0.0).

The message of each commit contains detailed information about the changes made. The list below is a summary about all significant improvements.

• 0.8.0 (latest)
  • implemented _fff_rebase() to handle strings better
• 0.7.0
  • improved usage of struct member 'level'
    • 'level' contains now real value, even if fifo is full
    • demo-code compiles with 25% less flash usage
    • less if-statements required, performance therefore increased
• 0.6.0
  • implemented pointable fifos, including tests
• 0.5.0
  • testing now automated with the brand new unittrace.
  • finally polished up this readme 🎉
• 0.4.0
  • array with several fifos now possible
  • aligned data example provided
• 0.3.0
  • complete and successful test of all macros (this time for real)
• 0.2.0
  • complete test of all macros
  • changed fifo struct to improve readability
  • MIT License added to git
• 0.1.0
  • initial commit

Contact

If you haven't done so already, please check out Get Help for the fastest possible help on your issue. Alternatively you can find my public email address on my profile.

Credits

Projects Used

• git-template - A simple and clean git repository template.
  

• unittrace - A simple testing and debugging tool for MCUs inspired by MinUnit
  Specifically written for this project, because testing became to annoying.

Related Projects

• none (yet)

Want yours to be listed here, too? Create a merge request or get in touch.

Additional Resources

• 2ⁿ circular buffer explanation (German) or English (with google translate)

• GCC: Atomically and Non-Atomically Executed Code Blocks

• GCC: Specifying Attributes of Variables

License

This project is proudly licensed under the MIT license.

The MIT license was chosen to give you the freedom to use this project in any way you want, while protecting all contributors from legal claims. Good code works, great code works for everyone. If this code has become a part of one of your projects, a link back to us would be highly appreciated. Thanks!