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
Overview
Syntax (fields, pseudo ops)
Local variables
Examples
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
rts
;**********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
inx
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
iny
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
Overview
Syntax (fields, pseudo ops)
Local variables
Examples