FIFO

Der FIFO-Puffer oder Ringpuffer ist die zweite wichtige Pufferstruktur. Die Abkürzung FIFO steht für die Bezeichnung 'First In, First Out'. Wie der Name des FIFOs sagt, wird der zuerst abgespeicherte Wert auch wieder zuerst ausgegeben. Man kann sich ein FIFO auch als 'Durchlaufspeicher' vorstellen, in dem die abgespeicherten Werte eine gewisse Zeit verweilen und dann in derselben Reihenfolge wieder ausgelesen werden.

Die Abbildung zeigt die Funktion eines FIFO. Das FIFO wird ebenso wie der Stack in einem reservierten Speicherbereich angelegt, ist aber im Gegensatz zum Stack zyklisch organisiert. Zur Funktion des FIFOs werden zwei Pointer benötigt, ein Input-Pointer und ein Output-Pointer. Beide zeigen nach der Initialisierung auf dieselbe Stelle des Puffers. Sollen Daten geschrieben werden, so wird das jeweilige Datum in die Speicherzelle geschrieben, auf die der Input-Pointer zeigt, und dann der Input-Pointer auf die nächste Adresse gesetzt. Beim Lesen eines Datums wird der Wert aus der Speicherzelle geholt, auf die der Output-Pointer zeigt, und dann der Output-Pointer auf die nächste Speicheradresse gesetzt.

Beim Erhöhen der Pointer ist darauf zu achten, dass die Pointer in zyklischer Weise erhöht werden. Das heißt, dass der Pointer auf den Anfang des Speicher bereichs gesetzt wird, wenn er das Ende des Bereichs überschreitet. Sind Input- und Output-Pointer gleich, so ist das FIFO leer.

FIFOs werden überall dort eingesetzt, wo es notwendig ist, in einen Datenstrom eine Verzögerung einzubauen. So kommen zum Beispiel die Zeichen auf einer seriellen Schnittstelle zu beliebigen Zeiten im Computer an, können aber nur zu bestimmten Zeiten weiterverarbeitet werden. In diesem Fall leitet man den Strom der Daten in ein FIFO, aus dem dann die eingelangten Zeichen asynchron ausgelesen werden können.

Der folgende kleine Programmausschnitt zeigt die Implementation eines FIFOs in Z80-Assembler. Es sind vier Funktionen als Unterprogramme implementiert: FIFO lesen, FIFO beschreiben, FIFO-Zustand überprüfen und FIFO löschen. Das hier gezeigte FIFO ist 256 Byte lang, die Input- und Outputpointer stehen als Bytevariable zu Beginn des Datenpuffers. Das FIFO benötigt also insgesamt 258 Bytes.

;===================================================
;----- 8-Bit-Zeichen in FIFO schreiben -------------
;===================================================
;
;ENTRY:     HL zeigt auf Beginn des FIFOs,
;           AKKU enthält Zeichen
;EXIT:      CF=0 --> Zeichen in FIFO eingetragen
;           CF=1 --> FIFO ist voll, Zeichen nicht
;           eingetragen
;
;Struktur des FIFOs:
;  1. Byte: FIFO input pointer (0..255)
;  2. Byte: FIFO output pointer (0..255)
;  3.-258.Byte:         FIFO Datenfeld
;  ---> Gesamtlänge: 258 Byte
;
            .GLOBAL WRFIFO
WRFIFO:     PUSH    HL
            PUSH    BC
            PUSH    AF
            LD      C,(HL)      ;Eingangspointer
            INC     HL
            LD      A,(HL)      ;Ausgangspointer
            DEC     A           ;FIFO voll ?
            CP      C
            JR      Z,FIFFUL    ;ja
            POP     AF
            DEC     HL
            INC     (HL)        ;neuer Pointer
            INC     HL
            INC     HL          ;Datenadresse
            LD      B,0         ;  berechnen
            ADD     HL,BC
            LD      (HL),A
            POP     BC
            POP     HL
            OR      A           ;Carry Flag rücksetzen
            RET
;
FIFFUL:     POP     AF          ;FIFO voll
            POP     BC
            POP     HL
            SCF                 ;Carry Flag setzen
            RET
;
;===================================================
;------ 8-Bit-Zeichen von FIFO lesen ---------------
;===================================================
;
;ENTRY:     HL zeigt auf Beginn des FIFOs
;EXIT:      CF=0, Daten in AKKU sind gültig
;           CF=1, FIFO ist leer
;
            .GLOBAL RDFIFO
RDFIFO:     PUSH    HL
            PUSH    BC
            LD      A,(HL)      ;FIFO Eingangspointer
            INC     HL
            LD      C,(HL)      ;FIFO Ausgangspointer
            CP      C           ;FIFO leer ?
            JR      Z,FIFMPT
            INC     (HL)
            INC     HL          ;Datenadresse
            LD      B,0         ;  berechnen
            ADD     HL,BC
            LD      A,(HL)
            POP     BC
            POP     HL
            OR      A           ;CF=0 ---> Daten OK
            RET
;
FIFMPT:     POP     BC
            POP     HL
            SCF                 ;CF=1 ---> Daten
            RET                 ;  ungültig
;
;===================================================
;----- FIFO löschen --------------------------------
;===================================================
;
;ENTRY:     HL zeigt auf Beginn des FIFOs
;EXIT:      FIFO ist gelöscht und leer
;
            .GLOBAL CLRFIF
CLRFIF:     PUSH    AF
            XOR     A
            LD      (HL),A
            INC     HL
            LD      (HL),A
            DEC     HL
            POP     AF
            RET
;
;===================================================
;----- FIFO Status testen --------------------------
;===================================================
;
;ENTRY:     HL zeigt auf Beginn des FIFOs
;EXIT:      CF=1 ---> FIFO voll
;           ZF=1 ---> FIFO leer
;           AKKU enthält Zahl der Zeichen in FIFO
;
            .GLOBAL TSTFIF
TSTFIF:     LD      A,(HL)
            INC     HL
            SUB     (HL)
            JR      Z,TFE       ;FIFO leer
            CP      0FFH
            JR      Z,TFF       ;FIFO voll
            SCF                 ;FIFO weder voll noch
            CCF                 ;  leer
            DEC     HL
            RET
;
TFE:        SCF
            CCF
            DEC     HL          ;CF=0, ZF=1
            RET
;
TFF:        XOR     A
            LD      A,0FFH
            SCF                 ;CF=1, ZF=0
            DEC     HL
            RET

Da FIFOs sehr vielfältig eingesetzt werden können, werden von manchen Herstellern auch integrierte Schaltungen angeboten.