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.

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