Eine FIFO (von engl. first in, first out) ist eine Warteschlange. Sie funktioniert nach dem Prinzip "wer zuerst kommt, mahlt zuerst" und unterscheidet sich dadurch von einem Stapel (Stack, Kellerspeicher).
Inhaltsverzeichnis
Verwendung
FIFOs finden dort Verwendung, wo Daten zwischengespeichert werden müssen. Typischerweise werden die Daten von einem Teilnehmer/Programmteil produziert und von einem anderen Teil konsumiert bzw. Verbraucht – man hat also ein Producer-Consumer-Paradigma.
Häufiges Beispiel ist eine Kommunikation, bei der Daten schneller gesendet werden, als der Empfänger sie verarbeiten kann. Damit keine Daten verloren gehen, werden sie beim Empfang in eine FIFO gespeichert und warten dort auf ihre Verarbeitung.
Auch in Ausgaberichtung werden die Daten oft nur in einen Puffer (FIFO) geschrieben. Während die Ausgaberoutine, Hardware bzw Task/Prozess die Daten verschickt, läuft das eigentliche Programm schon weiter und muss nicht warten, bis die Ausgabe fertig ist.
C-Code
Die Implementierung geht davon aus, daß es mehrere Producer und Consumer gibt. Producer bzw. Consumer mussen sich jeweils auf der gleichen Interrupt-Ebene befinden, aber die Producer können natürlich auf einer anderen Ebene arbeiten als die Consumer.
Sind die Producer (gleiches gilt für die Consumer) auf mehrere Interrupt-Ebenen verteil, müssen die entsprechenden Funktionen atomar gemacht werden! (Und nicht nur der Zugriff auf die Komponente count.)
Interface
- void fifo_init (fifo_t *b, uint8_t *buffer, const uint8_t size)
- Initialisiert die FIFO, setzt Lese- und Schreibzeiger, etc.
- uint8_t fifo_put (fifo_t *b, const uint8_t data)
- Schreibt ein Byte in die FIFO. Liefert 1 bei Erfolg und 0, falls die FIFO voll ist.
- uint8_t fifo_get_wait (fifo_t *b)
- Liefert das nächste Byte aus der FIFO, bei leerer FIFO wird gewartet, bis das nächste Zeichen eintrifft.
- int fifo_get_nowait (fifo_t *b)
- Liefert das nächste Byte aus der FIFO als int bzw. -1, falls die FIFO leer ist.
Die eigentliche Implementierung der FIFO-Funktionalitäten put und get erfolgen als Inline-Funktionen, um bei zeitkritischen Teilen schneller zu sein.
- static inline uint8_t _inline_fifo_put (fifo_t *b, const uint8_t data)
- Wie fifo_put
- static inline uint8_t _inline_fifo_get (fifo_t *b)
- Liefert das nächste Zeichen aus der FIFO. Ob überhaupt ein Zeichen in der FIFO ist, muss vorher extra abgeprüft werden.
Header
- fifo.h
- Hier wird die FIFO-Typ fifo_t definiert, die Basis-Funktionalitäten put und get werden als Inline-Funktionen implementiert.
#ifndef _FIFO_H_
#define _FIFO_H_
#include <avr/io.h>
#include <avr/interrupt.h>
extern void fifo_init (fifo_t*, uint8_t* buf, const uint8_t size);
extern uint8_t fifo_put (fifo_t*, const uint8_t data);
extern uint8_t fifo_get_wait (fifo_t*);
extern int fifo_get_nowait (fifo_t*);
typedef struct
{
uint8_t volatile count; // # Zeichen im Puffer
uint8_t size; // Puffer-Größe
uint8_t *pread; // Lesezeiger
uint8_t *pwrite; // Schreibzeiger
uint8_t read2end, write2end; // # Zeichen bis zum Überlauf Lese-/Schreibzeiger
} fifo_t;
static inline uint8_t
_inline_fifo_put (fifo_t *b, const uint8_t data)
{
if (b->count >= b->size)
return;
uint8_t * pwrite = b->pwrite;
*(pwrite++) = data;
uint8_t write2end = b->write2end;
if (--write2end == 0)
{
write2end = b->size;
pwrite -= write2end;
}
b->write2end = write2end;
b->pwrite = pwrite;
uint8_t sreg = SREG;
cli();
b->count++;
SREG = sreg;
return 1;
}
static inline uint8_t
_inline_fifo_get (fifo_t *b)
{
uint8_t *pread = b->pread;
uint8_t data = *(pread++);
uint8_t read2end = b->read2end;
if (--read2end == 0)
{
read2end = b->size;
pread -= read2end;
}
b->pread = pread;
b->read2end = read2end;
uint8_t sreg = SREG;
cli();
b->count--;
SREG = sreg;
return data;
}
#endif /* _FIFO_H_ */
Quellcode
- fifo.c
- Hier findet sich die Implementierung von fifo_init. fifo_put, fifo_get_wait und fifo_get_wait sind lediglich Wrapper der Inline-Funktionen aus dem Header. Dadurch kann in weniger zeitkritischen Fällen der Codeverbrauch vermindert werden.
#include "fifo.h"
void fifo_init (fifo_t *f, uint8_t *buffer, const uint8_t size)
{
f->count = 0;
f->pread = f->pwrite = buffer;
f->read2end = f->write2end = f->size = size;
}
uint8_t fifo_put (fifo_t *f, const uint8_t data)
{
return _inline_fifo_put (f, data);
}
uint8_t fifo_get_wait (fifo_t *f)
{
while (!f->count);
return _inline_fifo_get (f);
}
int fifo_get_nowait (fifo_t *f)
{
if (!f->count) return -1;
return (int) _inline_fifo_get (f);
}
Anwendung
Initialisierung
Bevor eine FIFO benutzt werden kann, muss sie initialisiert werden. Dazu definiert man sich einen Puffer und übergibt diesen samt Größe an fifo_init:
#include "fifo.h"
#define BUF_SIZE 10
uint8_t buffer[BUF_SIZE];
fifo_t fifo;
...
fifo_init (&fifo, buffer, BUF_SIZE);
...
Lesen/Schreiben
Ein Byte lesen (mit warten) bzw. schreiben:
uint8_t zeichen = ...;
fifo_put (&fifo, zeichen);
zeichen = fifo_get_wait (&fifo);
Siehe auch
