nRF51 SDK: FIFO library

| nRF51 SDK

- Home
- Related Pages
- API Reference
- Data Structures

All Data Structures Functions Variables Typedefs Enumerations Enumerator Groups Pages
FIFO library

The FIFO library provides a simple circular buffer implementation for storing bytes. The FIFO uses the size and buffer memory provided by the application on initialization.

# Initializing FIFO

// Create a FIFO structure
app_fifo_t my_fifo;
// Create a buffer for the FIFO
uint16_t buffer_size = 8;
uint8_t buffer[buffer_size];
// Initialize FIFO structure
uint32_t err_code = app_fifo_init(&test_fifo, buffer, (uint16_t)sizeof(buffer));

The application must provide a FIFO structure and memory buffer to the initialization function.
The FIFO structured is passed by reference and will be initialized by the FIFO module.
As seen in the above code the application needs to ensure the buffer has reserved memory space for the lifetime of the FIFO.

The FIFO app_fifo_t instance will ensure correct indexing when reading and writing data to the FIFO.

The size of the buffer has to be a power of two.

The library module itself will not store state information thus the application must ensure that the memory used by app_fifo_t is not reclaimed as long as the FIFO is in use.

# FIFO instance

typedef struct
{
uint8_t * p_buf; /**< Pointer to FIFO buffer memory. */
uint16_t buf_size_mask; /**< Read/write index mask. Also used for size checking. */
volatile uint32_t read_pos; /**< Next read position in the FIFO buffer. */
volatile uint32_t write_pos; /**< Next write position in the FIFO buffer. */
} app_fifo_t;

The structure used to make a FIFO instance contains 4 members:

- p_buf - which is the copy of the address to the provided buffer.
- read_pos - counter to the next byte to be read in the provided buffer.
- write_pos - counter to the next byte to be written in provided buffer.
- buf_size_mask - this is field which is calculated based on the buffer size. As the size of the buffer is always a power of two, it is possible to get a filter mask by subtracting 1.

The FIFO is implemented as a circular buffer of size `<n>`. Whenever the `<n>-th` element is added to the buffer, the index wraps over and counts from index zero.

This can be summarized to:

- Buffer size, n .
- Calculated read / write index, i .
- Read / write counter, count.

Thus we have: `i = count mod n`.

To simplify the index handling, the FIFO is restricted to require the buffer size `<n>`, to be a power of two, as this reduces the modulus operation to become a simple AND operation with ``<n>` - 1`.

Example, buffer size `n = 8` :

    n     = 8 = 0b00001000
    n - 1 = 7 = 0b00000111

    ANDing any number with <n>-1 , is identical to the modulus operation of <n>, when <n> is a power of two, see below:

    3 = 11 mod 8 = 11 AND 7 = 0b00001011 & 0b00000111 = 0b00000011 = 3 .

A check is performed during initialization of the FIFO to ensure the size `<n>` is a power of two.

In the image below we can see a graphical representation of how the FIFO instance looks like when it is initialized. The two arrows on the top illustrates the read and write index to their next elements in the buffer. They both start at index 0 and all the bytes in the buffer is free to be used.

Figure 1: FIFO instance read and write indices after initialization.

Warning
  The FIFO implementation is not re-entrant safe. Thus data must be added or fetched from the FIFO from the same context level. However, adding in one context level and fetching from another context is supported.

# Adding an element

To add an element to the FIFO the application has to use the app_fifo_put function. This is done by passing the `FIFO` `structure` and the `data` to app_fifo_put.

Example of adding an element to the FIFO:

uint8_t data = 88;
// Add an element to the FIFO
err_code = app_fifo_put(&my_fifo, data);

When the new element is added to the buffer the value supplied as parameter to the put function will be copied over to the current index of the write_pos member of the FIFO instance. When an element has been added to the FIFO, the write_pos member of the instance will be incremented by 1 to point to the next free byte. This is illustrated in Figure 2. For each element added the write_pos counter increments. An illustration of this can be seen in Figure 3.

Figure 2: FIFO instance with 1 element added.
Figure 3: FIFO instance with 4 elements added.

If the FIFO is full then NRF_ERROR_NO_MEM will be returned.

# Fetching an element

To get an element from the FIFO, the application has to use the app_fifo_get function.
This is done by passing the `FIFO` `structure` and a reference, `return_val` , for returning the data from app_fifo_get.

Example of fetching an element from the FIFO:

// Consume one element from FIFO
uint8_t return_val;
err_code = app_fifo_get(&my_fifo, &return_val);

When app_fifo_get is called the memory of the supplied by-reference parameter is filled with the value stored in the memory buffer. Then, the read_pos member of the FIFO instance is incremented to free the byte read. An example of a FIFO where two elements has been consumed is shown below in Figure 4. For each element fetched from the FIFO the read_pos counter is increment therefore each byte can only be fetched once. This is shown in Figure 4.

Figure 4: FIFO instance with 2 elements consumed.

# Empty Buffer

The read_pos and write_pos has the same value when the FIFO is empty. This is the case when the FIFO is initialized as read_pos and write_pos are both initialized to 0.
Or when all elements in the FIFO has been fetched, in which case read_pos == write_pos. An illustration of this is given in Figure 5.

The FIFO can also be emptied by executing app_fifo_flush.

When the FIFO is empty then any calls to app_fifo_get function will return NRF_ERROR_NOT_FOUND.

Figure 5: FIFO instance with no elements.

# Full Buffer

When `write_pos == read_pos + <n>` then the buffer is full and any subsequent calls to app_fifo_put function will return NRF_ERROR_NO_MEM.

Figure 6: FIFO instance with all available elements used.