Implementation of different types of FIFO
Implementation of different types of FIFO
This project was a part of Principles of Embedded Software Course, that I took at University of Colorado Boulder. The focus of the project is based on different ways to implement FIFOs.
This project was a part of Principles of Embedded Software Course, that I took at University of Colorado Boulder. The focus of the project is based on different ways to implement FIFOs.
What is a FIFO and what functionality it offers?
What is a FIFO and what functionality it offers?
A FIFO object—often called a queue instead—is intended to connect some code which produces data with some code which consumes data. This design pattern is relatively widespread; it is commonly used when producer and consumer threads run asynchronously with respect to each other.
A FIFO object—often called a queue instead—is intended to connect some code which produces data with some code which consumes data. This design pattern is relatively widespread; it is commonly used when producer and consumer threads run asynchronously with respect to each other.
One common use of a FIFO might be some video capture hardware. In this example, there is a producer thread that captures a frame of uncompressed video from a hardware buffer in response to either a timer or an interrupt. The producer thread enqueues a pointer to the memory containing the video frame onto the FIFO. Asynchronously, meanwhile, a consumer thread is dequeuing video frames from the FIFO in order to encode those frames using h.264 (and eventually transmit them across a network). Because uncompressed video is a firehose of data , we want to minimize copying it, so our two threads will pass pointers to the video across the FIFO. Presumably the two threads will manage this memory—malloc’ing and freeing it, perhaps—outside the context of the FIFO.
One common use of a FIFO might be some video capture hardware. In this example, there is a producer thread that captures a frame of uncompressed video from a hardware buffer in response to either a timer or an interrupt. The producer thread enqueues a pointer to the memory containing the video frame onto the FIFO. Asynchronously, meanwhile, a consumer thread is dequeuing video frames from the FIFO in order to encode those frames using h.264 (and eventually transmit them across a network). Because uncompressed video is a firehose of data , we want to minimize copying it, so our two threads will pass pointers to the video across the FIFO. Presumably the two threads will manage this memory—malloc’ing and freeing it, perhaps—outside the context of the FIFO.
A different possible use of a FIFO might be for bytes being read from a UART. In this example, the producer is likely to be the interrupt service routine (ISR) for the UART hardware. When a byte arrives at the UART and the interrupt is triggered, the ISR will enqueue the byte onto a FIFO. Meanwhile, a consumer thread will periodically wake up and dequeue bytes that have arrived. Most likely, the consumer thread will run far less frequently than the producer thread, but it will process more bytes of data at a time.
A different possible use of a FIFO might be for bytes being read from a UART. In this example, the producer is likely to be the interrupt service routine (ISR) for the UART hardware. When a byte arrives at the UART and the interrupt is triggered, the ISR will enqueue the byte onto a FIFO. Meanwhile, a consumer thread will periodically wake up and dequeue bytes that have arrived. Most likely, the consumer thread will run far less frequently than the producer thread, but it will process more bytes of data at a time.
For this project, two FIFO objects have been implemented:
For this project, two FIFO objects have been implemented:
a) llfifo: A linked-list implementation of a FIFO
a) llfifo: A linked-list implementation of a FIFO
The Linked List based FIFO implements the following API:
llfifo_t *llfifo_create(int capacity);
int llfifo_enqueue(llfifo_t *fifo, void *element);
void *llfifo_dequeue(llfifo_t *fifo);
int llfifo_length(llfifo_t *fifo);
int llfifo_capacity(llfifo_t *fifo);
void llfifo_destroy(llfifo_t *fifo);
b) cbfifo: A circular-buffer implementation of a FIFO
b) cbfifo: A circular-buffer implementation of a FIFO
The Circular Buffer based FIFO implements the following API:
size_t cbfifo_enqueue(void *buf, size_t nbyte);
size_t cbfifo_dequeue(void *buf, size_t nbyte);
size_t cbfifo_length();
size_t cbfifo_capacity();
Development Environment
Development Environment
To run the Program (IDE) :
To run the Program (IDE) :
- Add all files to the source and header (*.c and *.h files respectively) sections of the project.
- Check the build conditions and be sure to include -Wall and -Werror flags for your object file outputs.
- Either CLI or GUI can be used with the respective IDEs to run the program.