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.

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.

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.

For this project, two FIFO objects have been implemented:

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

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();

Details for each of these functions including expected outputs may be found in the header files in the GitHub repository.

Development Environment

To run the Program (IDE) :

1. Add all files to the source and header (*.c and *.h files respectively) sections of the project.

2. Check the build conditions and be sure to include -Wall and -Werror flags for your object file outputs.

3. Either CLI or GUI can be used with the respective IDEs to run the program.

Please refer Github repository for more information.