On Thu, 30 Jul 2009, Dave Tweed wrote:

> Harold Hallikainen wrote:
> > Here's my current FIFO code. Many FIFO implementations try to calculate
> > how much is in a FIFO or how much space is left by comparing the input
> > and output pointers. This is complicated with wrap-around.
> 
> No, it isn't at all, as long as you're correctly using unsigned arithmetic,
> modulo the FIFO size.
> 
> The big advantage to having only head and tail indices is that there is
> only one variable that needs to be modified by the process writing to the
> FIFO, and only one variable that needs to be modified by the process reading
> from the FIFO, and there are no concurrency issues, even in a multi-threaded
> application. Either process can do a simple modular subtraction on the two
> indices in order to find out how full the FIFO is.
> 
> There is one ambiguity -- when the indices are equal, is the FIFO completely
> full or completely empty? This means that you can't actually completely fill
> the FIFO in a simple implementation. However, there's a workaround: Add an
> empty/full flag to the FIFO structure. The writing process sets this flag
> if it completely fills the FIFO, and then it doesn't try to write to the
> FIFO again until the flag is cleared. The reading process unconditionally
> clears the flag. This still does not introduce any concurrency issues in a
> multithreaded environment.
> 
> When you have "bytes used" and/or "bytes free" variables in the FIFO
> structure, both processes must update them, and you have to make sure
> that they always get updated atomically (and consistently) with the
> index variables, which adds complexity, takes longer, uses extra space,
> and is prone to error.

There is no ambiguity when the indices are equal (and no need for a 
special 'full' flag) if you observe two simple rules:
(1)... (tail == head) means empty
(2)... head cannot be incremented to be equal to tail

This means that the fifo buffer can only ever store a max of 
('buffer_length' - 1) items (in other words one item becomes a guard 
item). So if the buffer is 10 bytes longs you can only store 9 bytes in it 
before it gets full. This is no big deal since this eliminates the use of 
a special 'full' flag. In other words it takes the same amount of space 
but you get the 'full' flag equivalent updated for free.

Here is the code I've been using for *** MANY *** years.

NOTE: the way a temporary index is used to protect the location of fifo 
item while it is being manipulated and consequently these routines are
*** INTERRUPT SAFE ***

Friendly Regards
Sergio Masci


//----------------------------------------------------------------------
//----------------------------------------------------------------------

FIFO is just an array of bytes of size N + 3 where N is the size of the 
buffer and the maximum number of bytes that can be stored in the buffer is 
N - 1


const	fifo_len  = 0
const	fifo_head = 1
const	fifo_tail = 2
const	fifo_buff = 3

const	fifo_error = 0xffffffff
const	fifo_ok    = 0


//----------------------------------------------------------------------
//----------------------------------------------------------------------
proc inline fifo_init(FIFO *fifo, byte len)

	fifo[fifo_len]  = len
	fifo[fifo_head] = 0
	fifo[fifo_tail] = 0
endproc


//----------------------------------------------------------------------
//----------------------------------------------------------------------
proc int fifo_read(FIFO *fifo)

	char	indx
	char	ch

	indx = fifo[fifo_tail]

	if indx == fifo[fifo_head] then
		return fifo_error
	endif

	ch = fifo[fifo_buff + indx]

	indx = indx + 1

	if indx >= fifo[fifo_len] then
		indx = 0
	endif

	fifo[fifo_tail] = indx

	return ch
endproc


//----------------------------------------------------------------------
//----------------------------------------------------------------------
proc byte fifo_write(FIFO *fifo, char ch)

	char	indx

	indx = fifo[fifo_head] + 1

	if indx >= fifo[fifo_len] then
		indx = 0
	endif

	if indx == fifo[fifo_tail] then
		return fifo_error
	endif

	fifo[fifo_buff + fifo[fifo_head]] = ch

	fifo[fifo_head] = indx

	return fifo_ok
endproc


//----------------------------------------------------------------------
//----------------------------------------------------------------------
proc byte fifo_empty(FIFO *fifo)

	if fifo[fifo_tail] == fifo[fifo_head] then
		return true
	endif

	return false
endproc


//----------------------------------------------------------------------
//----------------------------------------------------------------------
proc byte fifo_full(FIFO *fifo, char ch)

	char	indx

	indx = fifo[fifo_head] + 1

	if indx >= fifo[fifo_len] then
		indx = 0
	endif

	if indx == fifo[fifo_tail] then
		return true
	endif

	return false
endproc
-- 
http://www.piclist.com PIC/SX FAQ & list archive
View/change your membership options at
http://mailman.mit.edu/mailman/listinfo/piclist