On Sat, 1 Aug 2009, sergio masci wrote:

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

Ok, further to Dave's asertion that we could use a flag to allow us to 
completely fill the FIFO. I have revised the FIFO code I posted and come 
up with the following (appended to the end of this post). It uses two 
extra counts instead of the one flag proposed by Dave.

All comments welcome.


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_cnt_in  = 3
const	fifo_cnt_out = 4
const	fifo_buff    = 5

const	fifo_error = 0xffffffff
const	fifo_ok    = 0


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

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


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

	byte	indx
	char	ch


	if fifo[fifo_cnt_in] - fifo[fifo_cnt_out] == 0 then
		return fifo_error
	endif

	indx = fifo[fifo_tail]

	ch = fifo[fifo_buff + indx]

	indx = indx + 1

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

	fifo[fifo_tail] = indx

	fifo[fifo_cnt_out] += 1

	return ch
endproc


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

	byte	indx
	byte	cnt


	cnt = fifo[fifo_cnt_in] - fifo[fifo_cnt_out]

	if cnt < 0 then
		cnt = -cnt
	endif

	if cnt == fifo[fifo_len] then
		return fifo_error
	endif

	indx = fifo[fifo_head] + 1

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

	fifo[fifo_buff + fifo[fifo_head]] = ch

	fifo[fifo_head] = indx

	fifo[fifo_cnt_in] += 1

	return fifo_ok
endproc


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

	if fifo[fifo_cnt_in] - fifo[fifo_cnt_out] == 0 then
		return true
	endif

	return false
endproc


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

	byte	cnt


	cnt = fifo[fifo_cnt_in] - fifo[fifo_cnt_out]

	if cnt < 0 then
		cnt = -cnt
	endif

	if cnt == fifo[fifo_len] 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