Warteschlange (FIFO)

Bei vielen Anwendungen fallen Daten schneller an, als diese verarbeitet werden können. Damit keine Daten verloren gehen werden die Daten in einer FIFO zwischengespeichert. Die FIFO erhält im Gegensatz zu einem Stapelspeicher die Reihenfolge der Daten. Angebracht ist die FIFO, wenn die Daten stoßweise eintreffen und die Verarbeitungsgeschwindigkeit im Mitter hoch genug ist, damit keine Daten verloren gehen.

Typisches Anwendungsbeispiel ist eine Datenübertragung über einen langsamen Kanal: Das Hauptprogramm gibt seine Daten in die FIFO und braucht sich danach nicht mehr um die Daten zu kümmern. Die Ausgaberoutine entnimmt die Daten der FIFO und kümmert sich um deren Übertragung.

Der Zugriff auf die FIFOs erfolgt über FIFO-Objekte, von denen man die Adresse an die Funktionen übergibt. Die Struktur heisst fifo_t und wird im Header definiert.

Die einzige Komponente dieser Struktur, die für eine Anwendung interessant sein könnte, ist .count, welche die Anzahl der in der FIFO gespeicherten Werte merkt. Dieser Wert darf nicht von aussen verändert werden, kann aber abgefragt werden um zB zu überprüfen, ob die FIFO leer ist oder nicht.

Folgende Funktionen zum Bedienen einer FIFO gibt es:

void fifo_init (fifo_t * pf, uint8_t * buf, uint8_t size): Initialisiert die FIFO beim Programmstart. pf ist Pointer auf die zu initialisierende FIFO. buf ist die Anfangsadresse des FIFO-Puffers, der size Bytes lange ist.
void fifo_put (fifo_t * pf, uint8_t val): Schreibt den Wert val in die FIFO, deren Adresse wieder in pf übergeben wird.
int fifo_get (fifo_t * pf): Liest einen Wert aus der FIFO. Ist der Rückgabewert gleich -1, dann ist die FIFO momentan leer. Ansonsten wird der nächste Wert aus der FIFO zurückgeliefert, der zwischen 0 und 255 (0xff) liegt.

Ausserdem gibt es für Sonderfälle noch Inline-Funktionen, welche die gleichen Aufgaben wie die korrespondierenden nicht-inline Funktionen erfüllen. Diese Implementierungen vermeiden den Overhead eines Funktionsaufrufs, was besonders dann wichtig ist, wenn eine FIFO aus einer Interrupt-Routine heraus bedient werden soll. Der Aufruf erfolgt analog zu den oben beschriebenen Funktionen.

inline void _inline_fifo_put_nocli (fifo_t * pf, uint8_t val): Put als Inline-Funktion. Diese Funktion muss in einem Umfeld aufgerufen werden, das keine Interrupts zulässt, wie zB innerhalb einer SIGNAL bzw. ISR Interrupt-Service-Routine.
inline int _inline_fifo_get_nocli (fifo_t * pf): Dito, für die get-Funktion.

fifo.h

Hier wird die Struktur fifo_t definiert, und die Inline-FUnktionen werden implementiert.

#ifndef _FIFO_H_
#define _FIFO_H_

#include <avr/io.h>
#include <avr/interrupt.h>

typedef struct
{
    uint8_t volatile count;
    uint8_t size;
    uint8_t *pread;
    uint8_t *pwrite;
    uint8_t read2end, write2end;
} fifo_t;

extern void fifo_init (fifo_t * const pf, uint8_t * buf, const uint8_t size);
extern void fifo_put (fifo_t * const pf, const uint8_t);
extern int fifo_get (fifo_t * const pf);

static inline void
_inline_fifo_put_nocli (fifo_t * const 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;

    b->count++;
}

static inline int
_inline_fifo_get (fifo_t * const b)
{
    if (!b->count)
        return -1;

    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;
}

static inline int
_inline_fifo_get_nocli (fifo_t * const b)
{
    if (!b->count)
        return -1;

    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;

    b->count--;

    return data;
}

#endif /* _FIFO_H_ */

fifo.c

Hier findet die Implementierung der "normalen" FUnktionen – also der nicht-inline-Funktionen – statt.

#include <avr/interrupt.h>

#include "fifo.h"

void fifo_init (fifo_t * const f, uint8_t * const buf, const uint8_t size)
{
    f->pread = f->pwrite = buf;
    f->count = 0;
    f->read2end = f->write2end = f->size = size;
}

void fifo_put (fifo_t * const 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;
}

int fifo_get (fifo_t * const b)
{
    return _inline_fifo_get (b);
}

main.c

Ein ganz einfaches Beispiel, um die Verwendung zu zeigen. .

#include "fifo.h"

// FIFO #1 kann 20 Bytes halten
#define FIFO1_BUF_SIZE 20

// Die FIFO...
fifo_t fifo1;

// ...und ihr Puffer
uint8_t fifo1_buf[FIFO1_BUF_SIZE];

int main ()
{
    fifo_init (& fifo1, fifo1_buf, sizeof (fifo1_fuf));

    while (1)
    {
        uint8_t wert;

        // Was in die FIFO rein tun...
        fifo_put (& fifo1, 42);

        // ...und wieder lesen
        wert = fifo_get (& fifo1);
    }
}

FIFO: first in, first out

fifo.h

fifo.c

main.c