Developing Software in Assembly Language
First In First Out Queue
By Jonathan W. Valvano

     This article, which discusses assembly language programming, accompanies the book Embedded Microcomputer Systems: Real Time Interfacing published by Brooks-Cole 1999. This document has four overall parts
     Syntax (fields, pseudo ops)
     Local variables

Other Examples
      Arithmetic Examples on the 6812
      Shift Examples on the 6812
      Stack Usage and Interrupts on the 6812
      Interpreters on the 6812
      Control Structure Examples on the 6812 

    The first in first out circular queue (FIFO) is also useful for data flow problems. It is a very common data structure used for I/O interfacing. The order preserving data structure temporarily saves data created by the source (producer) before it is processed by the sink (consumer). The class of FIFO's studied in this article will be statically allocated global structures. Because they are global variables, it means they will exist permanently and can be shared by more than one program. The advantage of using a FIFO structure for a data flow problem is that we can decouple the source and sink processes. Without the FIFO we would have to produce 1 piece of data, then process it, produce another piece of data, then process it. With the FIFO, the source process can continue to produce data without having to wait for the sink to finish processing the previous data. This decoupling can significantly improve system performance.

      You have probably already experienced the convenience of FIFO's. For example, you can continue to type another commands into the DOS command interpreter while it is still processing a previous command. The ASCII codes are PUT in a FIFO whenever you hit the key. When the DOS command interpreter is free it calls GET for more keyboard data to process. A FIFO is also used when you ask the computer to print a file. Rather than waiting for the actual printing to occur character by character, the print command will PUT the data in a FIFO. Whenever the printer is free, it will GET data from the FIFO. The advantage of the FIFO is it allows you to continue to use your computer while the printing occurs in the background. To implement this magic of background printing we will need interrupts, which will be covered later in the book.
      There are many producer/consumer applications. In the following table the processes on the left are producers which create or input data, while the processes on the right are consumers which process or output data.

Source/Producer   Sink/Consumer
keyboard input -> program which interprets
program with data -> printer output
program sends message -> program receives message
microphone and A/D -> program which saves sound data
program which has sound data -> D/A and speaker


      The source process puts data into the FIFO. The PutFifo operation does not discard information like the MACQ. If the FIFO is full and the user tries to call PutFifo, the PutFifo routine will return a full error signifying the last (newest) data was not properly saved. The sink process removes data from the FIFO. GetFifo will modify the FIFO. After a call to GetFifo, the particular information returned from the GetFifo routine is no longer saved on the FIFO. If the FIFO is empty and the user tries to call GetFifo, the GetFifo routine will return an empty error signifying no data could be retrieved. The FIFO is order preserving, such that the information is returned by repeated calls of GetFifo in the same order as the data was saved by repeated calls of PutFifo.

      There are many ways to implement a statically allocated FIFO. We can use either a pointer or and index to access the data in the FIFO. We can use either two pointers (or two indices) or two pointers (or two indices) and a counter. The counter specifies how many entries are currently stored in the FIFO.  We will show the implementation using two pointer implementation. If the FIFO is full when PutFifo is called then the subroutine should return a full error (e.g., V=1.) Similarly, if the FIFO is empty when GetFifo is called, then the subroutine should return an empty error (e.g., V=1.) The PutPt and GetPt must be wrapped back up to the top when they reach the bottom.

There are many mechanisms to determine whether the FIFO is empty or full. A simple method is to implement a counter containing the number of bytes currently stored in the FIFO. GetFifo would decrement the counter and PutFifo would increment the counter. The second method is to prevent the FIFO from being completely full. For example, if the FIFO had 100 bytes allocated, then the PutFifo subroutine would allow a maximum of 99 bytes to be stored. If there were already 99 bytes in the FIFO and another PutFifo were called, then the FIFO would not be modified and a full error would be returned. In this way if PutPt equals GetPt at the beginning of GetFifo, then the FIFO is empty. Similarly, if PutPt+1 equals GetPt at the beginning of PutFifo, then the FIFO is full. Be careful to wrap the PutPt+1 before comparing it to GetPt. This second method does not require the length to be stored or calculated.
;Pointer implementation of the FIFO
FifoSize  equ   10  ;Number of 8-bit data in the Fifo
PutPt     rmb   2   ;Pointer of where to put next */
GetPt     rmb   2   ;Pointer of where to get next
; FIFO is empty if PutPt=GetPt
; FIFO is full if PutPt+1=GetPt
Fifo      rmb   FifoSize   ;The statically allocated fifo data
;**********Initialize FIFO******************
; No parameters
InitFifo  ldx  #Fifo
          stx  PutPt
          stx  GetPt      ;Empty when PutPt=GetPt
;**********Put a byte into the FIFO******************
; Input RegA contains 8-bit data to put
; Output RegA is -1 if successful, 0 if data not stored
PutFifo   ldx  PutPt      ;RegX is Temporary put pointer
          staa 0,x        ;Try to put data into fifo
          cpx  #Fifo+FifoSize
          bne  PutNoWrap  ;skip if no wrapping needed
          ldx  #Fifo      ;Wrap
PutNoWrap clra            ;assume it will fail
          cpx  GetPt      ;Full if now the same
          beq  PutDone
          coma            ;RegA=-1 means OK
          stx  PutPt
PutDone   rts
;**********Get a byte from the FIFO******************
; Input RegX points to place for 8-bit data from Get
; Output RegA is -1 if successful, 0 if Fifo was empty when called
GetFifo   clra             ;assume it will fail
          ldy   GetPt
          cpx   PutPt      ;Empty if initially the same
          beq   GetDone
          coma             ;RegA=-1 means OK
          ldab   0,y      ;Data from FIFO
          stab   0,x      ;Return by reference
          cpy   #Fifo+FifoSize
          bne   GetNoWrap  ;skip if no wrapping needed
          ldy   #Fifo      ;Wrap
GetNoWrap sty   GetPt
GetDone   rts
These routines are not reentrant. For a discussion of reentrancy and how to make these routines operate in a multithreaded environment, see Chapter 4 in the book,
Embedded Microcomputer Systems: Real Time Interfacing by Jonathan W. Valvano, Brooks/Cole Publishing Co., December 1999.


This document has four overall parts
     Syntax (fields, pseudo ops)
     Local variables