Fifofast
A fast, generic fifo for MCUs.
Install / Use
/learn @nqtronix/FifofastREADME
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.
<br>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:<br> 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:<br> 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:<br> 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.<br>
Step 1: Software and Tools
- [Atmel Studio 7.0][tool-atmel-studio-7-0] (Build 1931) [free]<br> 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]<br> To program AVR8 MCUs I use the [AVR Dragon][tool-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][git-download] and extract the .zip file.
Step 3: Browse the project
-
Open the project in Atmel Studio:<br> Either double click
fifofast.atslnor open Atmel Studio and select "File -> Open -> Project/Solution..." -
Open any file of your interest:<br> Select the file in the top right window "Solution Explorer". If the window is not visible, open it by pressing
CTRL + ALT + Lor selecting "View -> Solution Explorer" from the menu.
Step 4: Run the demo
-
Compile the demo code:<br> Press
F7or select "Build -> Build Solution" from the menu -
Run the demo code in the simulator:<br> Press
CTRL + F5or select "Debug -> Start Debugging and Break" from the menu -
Place breakpoints:<br> 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:<br> 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:<br> Press
F5to run to the next breakpoint orF10to execute one step.
Step 5: Going further
-
Changing the target device:<br> Press
ALT + F7and select "Device -> Change device..." to select your desired MCU. -
Program a real device:<br> Connect your programmer, press
ALT + F7and select "Tool". Choose your tool, your programming interface and wire up your MCU. PressCTRL + ALT + F7to 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:
- The macro can be used as a right side or left side argument to read from/ write to a specific location.
- The data pointers are not changed. Reading or writing data will not remove/ add elements to/ from the fifo.
- 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.
<sub>*As of 0.7.0 there is only one configuration option, but this is the place where other options would go.</sub>
<br>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);
