Software FIFO
The base of any embedded system is the drivers that interact with the hardware. 99% of the time, these drivers use interrupts to handle the asynchronous behavior of hardware. A crucial component in driver development is often a first-in-first-out (FIFO) buffer that allows the hardware interrupt handler to act independently of the regular system code. FIFOs allow a system to have a ‘producer’ and ‘consumer’ of data. The rate at which the FIFO is filled and emptied does not have to be the same on both sides. This asynchronous behavior allows for bursty data flows. A basic FIFO has two interfaces: a write interface that allows some code to write data to it; and a read interface that allows other code to pull data from it.
Header File
Developing a precise interface specification before implementation will make the design process faster and less buggy. Here is the specification to my FIFO:
/************************************************************************
Copyright (c) 2011, Nic McDonald
All rights reserved.
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:
1. Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above
copyright notice, this list of conditions and the following
disclaimer in the documentation and/or other materials provided
with the distribution.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*************************************************************************
Information:
File Name : fifo.h
Author(s) : Nic McDonald
Hardware : Any
Purpose : First In First Out Buffer
*************************************************************************
Modification History:
Revision Date Author Description of Revision
1.00 05/30/2011 NGM initial
************************************************************************/
#ifndef _FIFO_H_
#define _FIFO_H_
/* includes */
#include <stdint.h>
/* defines */
#define FIFO_GOOD 0x00
#define FIFO_OVERFLOW 0x01
#define FIFO_UNDERFLOW 0x02
/* typedefs */
typedef struct {
volatile uint32_t size;
volatile uint8_t* data;
volatile uint8_t status;
volatile uint32_t putIndex;
volatile uint32_t getIndex;
volatile uint32_t used;
} FIFO;
/* functions */
void fifo_init(FIFO* f, uint32_t size, uint8_t* data);
uint32_t fifo_isFull(FIFO* f);
uint32_t fifo_isEmpty(FIFO* f);
uint8_t fifo_get(FIFO* f);
void fifo_put(FIFO* f, uint8_t c);
uint8_t fifo_peek(FIFO* f);
uint32_t fifo_available(FIFO* f);
void fifo_clear(FIFO* f);
uint8_t fifo_status(FIFO* f);
#endif // _FIFO_H_
Source File
It is important to design a FIFO to be robust even when the user abuses the interface specification. For instance, you don’t want the memory to become corrupted when the user reads from the FIFO when it is empty or when the user writes to the FIFO when it is full. The memory allocated to the FIFO may become corrupt, but the memory surrounding it should not. Here is the implementation behind the header file’s specification:
/************************************************************************
Copyright (c) 2011, Nic McDonald
All rights reserved.
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:
1. Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above
copyright notice, this list of conditions and the following
disclaimer in the documentation and/or other materials provided
with the distribution.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR
TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*************************************************************************
Information:
File Name : fifo.c
Author(s) : Nic McDonald
Hardware : Any
Purpose : First In First Out Buffer
*************************************************************************
Modification History:
Revision Date Author Description of Revision
1.00 05/30/2011 NGM initial
*************************************************************************
Theory of Operation:
This FIFO implementation provides a memory safe 'First In First Out'
circular buffer. If the operating conditions of a FIFO causes it
to 'underflow' or 'overflow' the FIFO will not corrupt memory other
than its own data buffer. However, memory accesses into the buffer
will be invalid. If a FIFO 'underflows' or 'overflows', it should
be re-initialized or cleared.
Example Usage:
volatile uint8_t fifo_buf[128];
FIFO fifo;
fifo_init(&fifo, 128, fifo_buf);
************************************************************************/
#include "fifo.h"
void fifo_init(FIFO* f, uint32_t size, uint8_t* data) {
f->size = size;
f->data = data;
f->status = FIFO_GOOD;
f->putIndex = 0;
f->getIndex = 0;
f->used = 0;
}
uint32_t fifo_isFull(FIFO* f) {
return (f->used >= f->size);
}
uint32_t fifo_isEmpty(FIFO* f) {
return (f->used == 0);
}
uint8_t fifo_get(FIFO* f) {
uint8_t c;
if (f->used > 0) {
c = f->data[f->getIndex];
f->getIndex = (f->getIndex+1) % f->size;
f->used--;
return c;
}
else {
f->status = FIFO_UNDERFLOW;
return 0;
}
}
void fifo_put(FIFO* f, uint8_t c) {
if (f->used >= f->size)
f->status = FIFO_OVERFLOW;
else {
f->data[f->putIndex] = c;
f->putIndex = (f->putIndex+1) % f->size;
f->used++;
}
}
uint8_t fifo_peek(FIFO* f) {
return f->data[f->getIndex];
}
uint32_t fifo_available(FIFO* f) {
return f->used;
}
void fifo_clear(FIFO* f) {
f->status = FIFO_GOOD;
f->putIndex = 0;
f->getIndex = 0;
f->used = 0;
}
uint8_t fifo_status(FIFO* f) {
return f->status;
}
How to use a FIFO
Previously I mentioned that a FIFO is a method for synchronizing two asynchronous data flows. If these two data flows are on different threads (including interrupts), extreme care must be taken when accessing the FIFO. FIFOs are often used in UART drivers.
Let’s consider a case where a FIFO is used to bridge the gap between a UART receiver and some user code. A FIFO works great in this situation because UART data comes in very bursty and the user code may not be able to immediately handle the data. The FIFO allows the user to pull the data at its own speed, as long as the FIFO doesn’t overflow.
In this case there are two threads accessing the FIFO. The UART receive interrupt can come at any time and will interrupt the user’s code. The FIFOs functionality is heavily based on a variable that represents how many bytes are currently in the FIFO (in my code it is ‘used’). The interrupt code will be using the ‘fifo_put()’ function and the user code will be using the ‘fifo_get()’ function. Both functions modify the ‘used’ variable. If proper synchronization techniques are not taken, the interrupt code might call ‘fifo_put()’ right in the middle of the user calling ‘fifo_get()’. This could cause the ‘used’ variable to become corrupted and the FIFO would then be unusable. Fortunately in the interrupt case, the user code just needs to temporarily turn off the UART receive interrupt while calling ‘fifo_get()’. For a multi-threaded design, semaphores should be used to properly access the FIFO functions without corrupting the variables.
Mr. Digital 