FIFO mit avr-gcc: Unterschied zwischen den Versionen

Aktuelle Version vom 4. November 2012, 21:13 Uhr

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).

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.

Beispiel

Hier das Beispiel für eine FIFO, deren Puffer 10 Zeichen lang ist. In der FIFO warten 4 Zeichen an den Positionen 7, 8, 9 und 0. Das nächste gelesene Zeichen kommt aus Position 7, das nächste Zeichen, das geschrieben wird, wird an Position 1 landen. Bei leerer FIFO fallen Lese- und Schreibzeiger zusammen. Lese- und Schreibzeiger wandern von links nach rechts. Kommt ein Zeiger rechts an, springt er wieder zur linken Zelle, dem Anfang des Puffers.

C-Code

Die Implementierung geht davon aus, daß es mehrere Producer und Consumer gibt. Producer bzw. Consumer müssen 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 *f, uint8_t *buffer, const uint8_t size)

Initialisiert die FIFO, setzt Lese- und Schreibzeiger, etc. Die FIFO verwendet den Puffer buffer, der size Bytes sein muss.

uint8_t fifo_put (fifo_t *f, const uint8_t data)

Schreibt das Byte data in die FIFO. Liefert 1 bei Erfolg und 0, falls die FIFO voll ist.

uint8_t fifo_get_wait (fifo_t *f)

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 *f)

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 *f, const uint8_t data)

Wie fifo_put

static inline uint8_t _inline_fifo_get (fifo_t *f)

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 der FIFO-Typ fifo_t definiert, die Basis-Funktionalitäten put und get werden als Inline-Funktionen implementiert. Der Quellcode sieht etwas umständlich aus, resultiert aber im besten Code.

#ifndef FIFO_H
#define FIFO_H

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

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;

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

static inline uint8_t
_inline_fifo_put (fifo_t *f, const uint8_t data)
{
	if (f->count >= f->size)
		return 0;
		
	uint8_t * pwrite = f->pwrite;
	
	*(pwrite++) = data;
	
	uint8_t write2end = f->write2end;
	
	if (--write2end == 0)
	{
		write2end = f->size;
		pwrite -= write2end;
	}
	
	f->write2end = write2end;
	f->pwrite = pwrite;

	uint8_t sreg = SREG;
	cli();
	f->count++;
	SREG = sreg;
	
	return 1;
}

static inline uint8_t 
_inline_fifo_get (fifo_t *f)
{
	uint8_t *pread = f->pread;
	uint8_t data = *(pread++);
	uint8_t read2end = f->read2end;
	
	if (--read2end == 0)
	{
		read2end = f->size;
		pread -= read2end;
	}
	
	f->pread = pread;
	f->read2end = read2end;
	
	uint8_t sreg = SREG;
	cli();
	f->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_nowait 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);       
...

Alternativ lässt man den Startup-Code die Initialisierung übernehmen und schreibt sie explizit in einem Initialtzer hin. In diesem Falle müssen die Werte aber zur Compile-Zeit bekannt sein.

#include "fifo.h"

#define BUF_SIZE 10

uint8_t buffer[BUF_SIZE];

// Dedicated initializers are available in GNU-C only
fifo_t fifo = 
{
	.size = BUF_SIZE,
	.pread   = buffer,
	.pwrite  = buffer,
	.buf     = buffer,
	.buf_end = buffer + BUF_SIZE,
    	.count = 0
};

Lesen/Schreiben

Ein Byte lesen (mit warten) bzw. schreiben:

    uint8_t zeichen = ...;

    fifo_put (&fifo, zeichen);

    zeichen = fifo_get_wait (&fifo);

Siehe auch

• avr-gcc
• UART mit avr-gcc
• Software-UART mit avr-gcc