Interrupt driven UART

On 17/10/2006 the venerable goister@gmail.com etched in runes:

.
.
.
> So how about this pseudocode in my ISR then
> 
> if (tail+1 == head) {  // fifo overflow!
>   overflow_flag = 1;
>   // disable UART RX here and handle retransmission
>   junk = (unsigned char) buffer2; // clears buffer2
>   // enable RX here
> } else { // no fifo overflow!
>   // check parity error from status reg here
>   if (parity_error) {
>     // disable RX here and handle retransmission
>     junk = (unsigned char) buffer2; // clears buffer2
>     // enable RX here
>   } else {
>     fifo[Tail++] = (unsigned char) buffer2;
>     Tail &= BUFFLEN - 1; // handles wraparound
>   }
> }

Be careful as this code may fail in two places:

if(tail+1 == head)

will not work when 'head' is less than 'tail'. That situation will
arise as soon as the buffer wraps around.

tail &= BUFFLEN - 1;

will only work if BUFFLEN is a power of 2. For example it will fail if
BUFFLEN is 10.

-- 
John B

John B wrote:
> On 17/10/2006 the venerable goister@gmail.com etched in runes:
>
> .
> .
> .
> > So how about this pseudocode in my ISR then
> >
> > if (tail+1 == head) {  // fifo overflow!
> >   overflow_flag = 1;
> >   // disable UART RX here and handle retransmission
> >   junk = (unsigned char) buffer2; // clears buffer2
> >   // enable RX here
> > } else { // no fifo overflow!
> >   // check parity error from status reg here
> >   if (parity_error) {
> >     // disable RX here and handle retransmission
> >     junk = (unsigned char) buffer2; // clears buffer2
> >     // enable RX here
> >   } else {
> >     fifo[Tail++] = (unsigned char) buffer2;
> >     Tail &= BUFFLEN - 1; // handles wraparound
> >   }
> > }
>
> Be careful as this code may fail in two places:
>
> if(tail+1 == head)
>
> will not work when 'head' is less than 'tail'. That situation will
> arise as soon as the buffer wraps around.
>
> tail &= BUFFLEN - 1;
>
> will only work if BUFFLEN is a power of 2. For example it will fail if
> BUFFLEN is 10.
>
> --
> John B

Hi John,

I don't really get you on your first point. fyi I'm adding to the tail
of the fifo and removing from the head of the fifo. The tail naturally
has to wrap around for an overflow to occur. For example, if head is
say 5 and the tail wraps around back to 0 and then to 4, then this
would indicated a fifo overflow since there are no more available
spaces in the fifo to add to. You do bring up a good point about
overflow though, and my tail+1 doesn't take into account of that, since
if my tail is the sizeof of the fifo then tail+1 wouldn't wrap back to
0. I'll have to take care of that.

Anyway, I do realize that BUFFLEN has to be a power of 2. The idea was
suggested by another member in an earlier post, but thanks for
reminding me of the wonders of powers of 2 arithmetic :)

In article <1161187682.551456.158040@e3g2000cwe.googlegroups.com>, 
goister@gmail.com says...
> Hi John,
> 
> I don't really get you on your first point. fyi I'm adding to the tail
> of the fifo and removing from the head of the fifo. The tail naturally
> has to wrap around for an overflow to occur. For example, if head is
> say 5 and the tail wraps around back to 0 and then to 4, then this
> would indicated a fifo overflow since there are no more available
> spaces in the fifo to add to. You do bring up a good point about
> overflow though, and my tail+1 doesn't take into account of that, since
> if my tail is the sizeof of the fifo then tail+1 wouldn't wrap back to
> 0. I'll have to take care of that.
> 
> 
> 
Don't confuse a FIFO with a circular queue.
Most UART drivers/ISR use a circular queue and just move pointers around 
the like a loop.  There will be times when the tail may point to a lower 
memory location and also the other way around.

                       Jim

James Beck wrote:
> In article <1161187682.551456.158040@e3g2000cwe.googlegroups.com>,
> goister@gmail.com says...
> > Hi John,
> >
> > I don't really get you on your first point. fyi I'm adding to the tail
> > of the fifo and removing from the head of the fifo. The tail naturally
> > has to wrap around for an overflow to occur. For example, if head is
> > say 5 and the tail wraps around back to 0 and then to 4, then this
> > would indicated a fifo overflow since there are no more available
> > spaces in the fifo to add to. You do bring up a good point about
> > overflow though, and my tail+1 doesn't take into account of that, since
> > if my tail is the sizeof of the fifo then tail+1 wouldn't wrap back to
> > 0. I'll have to take care of that.
> >
> >
> >
> Don't confuse a FIFO with a circular queue.
> Most UART drivers/ISR use a circular queue and just move pointers around
> the like a loop.  There will be times when the tail may point to a lower
> memory location and also the other way around.
>
>                        Jim

Yes I do realize it's a circular queue,  I named the array fifo because
circular_queue was too long, but I've implemented it as a circular
queue in the code as you can see, by handling the wraparounds.

"galapogos" <goister@gmail.com> wrote in message
news:1161222525.036456.8350@m7g2000cwm.googlegroups.com...
>
> James Beck wrote:
> > Don't confuse a FIFO with a circular queue.
> > Most UART drivers/ISR use a circular queue and just move pointers around
> > the like a loop.  There will be times when the tail may point to a lower
> > memory location and also the other way around.
> >
> >                        Jim
>
> Yes I do realize it's a circular queue,  I named the array fifo because
> circular_queue was too long, but I've implemented it as a circular
> queue in the code as you can see, by handling the wraparounds.

I maybe have missed something, but what exactly is the difference between a
FIFO and a circular queue?

Meindert

Meindert Sprang wrote:
> "galapogos" <goister@gmail.com> wrote in message
>> James Beck wrote:
>>
>>> Don't confuse a FIFO with a circular queue.
>>> Most UART drivers/ISR use a circular queue and just move pointers
>>> around the like a loop.  There will be times when the tail may
>>> point to a lower memory location and also the other way around.
>>
>> Yes I do realize it's a circular queue,  I named the array fifo
>> because circular_queue was too long, but I've implemented it as a
>> circular queue in the code as you can see, by handling the
>> wraparounds.
> 
> I maybe have missed something, but what exactly is the difference
> between a FIFO and a circular queue?

A FIFO and a queue are the same thing.  You can implement them
without size limits by mallocing on insert, and freeing on removal,
with a linked list, for example.  A circular queue has limits on
the total length, set by the size of the buffer.

-- 
Chuck F (cbfalconer at maineline dot net)
   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net>

In article <45377D11.A92CB3C@yahoo.com>, cbfalconer@yahoo.com says...
> Meindert Sprang wrote:
> > "galapogos" <goister@gmail.com> wrote in message
> >> James Beck wrote:
> >>
> >>> Don't confuse a FIFO with a circular queue.
> >>> Most UART drivers/ISR use a circular queue and just move pointers
> >>> around the like a loop.  There will be times when the tail may
> >>> point to a lower memory location and also the other way around.
> >>
> >> Yes I do realize it's a circular queue,  I named the array fifo
> >> because circular_queue was too long, but I've implemented it as a
> >> circular queue in the code as you can see, by handling the
> >> wraparounds.
> > 
> > I maybe have missed something, but what exactly is the difference
> > between a FIFO and a circular queue?
> 
> A FIFO and a queue are the same thing.  You can implement them
> without size limits by mallocing on insert, and freeing on removal,
> with a linked list, for example.  A circular queue has limits on
> the total length, set by the size of the buffer.
> 
> 
Aaargh!   The thought of a malloc() for every character in and a free()
for every removal in an embedded systems makes me shiver!  Suddenly,
for each character, you need a pointer (4 bytes),   a list element 
(at least another 4 bytes) and,  probably 4 bytes of memory for
character itself (some heap managers may allocate a 4-byte minimum
to maintain alignment).  Your first 200 characters of input would
then require about 2400bytes of RAM!   Scary Stuff!


Mark Borgerson

In article <12je2k41hk5or80@corp.supernews.com>, 
ms@NOJUNKcustomORSPAMware.nl says...
> "galapogos" <goister@gmail.com> wrote in message
> news:1161222525.036456.8350@m7g2000cwm.googlegroups.com...
> >
> > James Beck wrote:
> > > Don't confuse a FIFO with a circular queue.
> > > Most UART drivers/ISR use a circular queue and just move pointers around
> > > the like a loop.  There will be times when the tail may point to a lower
> > > memory location and also the other way around.
> > >
> > >                        Jim
> >
> > Yes I do realize it's a circular queue,  I named the array fifo because
> > circular_queue was too long, but I've implemented it as a circular
> > queue in the code as you can see, by handling the wraparounds.
> 
> I maybe have missed something, but what exactly is the difference between a
> FIFO and a circular queue?
> 
> Meindert
> 

When I think of FIFO I think of a linear system, possibly hardware 
based, that may or may not have "wrap around" in the memory pointer 
sense.  Like a stack that pushes on one end and pops at the other that 
you may not be able manipulate the data pointer directly.  I know I'm 
splitting hairs and may not even be exactly correct in my thinking, but 
when I mean a circular queue I say it.  
In the end I was really just trying to point out that there will be 
times when the pointers into the queue can wrap around at different 
times and make doing simple math like 
num_in_queue = queue_head - queue_tail 
might not work right unless you take into account that when the head 
pointer rolls back around before the tail pointer the answer is going to 
wrap also.  Not that it is a show stopper it just needs to be accounted 
for.

                       Jim

Mark Borgerson wrote:
> cbfalconer@yahoo.com says...
>> Meindert Sprang wrote:
>>> "galapogos" <goister@gmail.com> wrote in message
>>>> James Beck wrote:
>>>>
>>>>> Don't confuse a FIFO with a circular queue.
>>>>> Most UART drivers/ISR use a circular queue and just move pointers
>>>>> around the like a loop.  There will be times when the tail may
>>>>> point to a lower memory location and also the other way around.
>>>>
>>>> Yes I do realize it's a circular queue,  I named the array fifo
>>>> because circular_queue was too long, but I've implemented it as a
>>>> circular queue in the code as you can see, by handling the
>>>> wraparounds.
>>>
>>> I maybe have missed something, but what exactly is the difference
>>> between a FIFO and a circular queue?
>>
>> A FIFO and a queue are the same thing.  You can implement them
>> without size limits by mallocing on insert, and freeing on removal,
>> with a linked list, for example.  A circular queue has limits on
>> the total length, set by the size of the buffer.
>>
> Aaargh!   The thought of a malloc() for every character in and a free()
> for every removal in an embedded systems makes me shiver!  Suddenly,
> for each character, you need a pointer (4 bytes),   a list element
> (at least another 4 bytes) and,  probably 4 bytes of memory for
> character itself (some heap managers may allocate a 4-byte minimum
> to maintain alignment).  Your first 200 characters of input would
> then require about 2400bytes of RAM!   Scary Stuff!

I wasn't thinking of a queue of chars, but rather of records or
lines.  The lines variant is likely to have a two level allocation,
for the header and for the variable length line itself.  The point
was that a queue need not be length limited, but a circular buffer
must be.

-- 
Chuck F (cbfalconer at maineline dot net)
   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net>

"CBFalconer" <cbfalconer@yahoo.com> wrote in message
news:45377D11.A92CB3C@yahoo.com...
> Meindert Sprang wrote:
> > I maybe have missed something, but what exactly is the difference
> > between a FIFO and a circular queue?
>
> A FIFO and a queue are the same thing.  You can implement them
> without size limits by mallocing on insert, and freeing on removal,
> with a linked list, for example.  A circular queue has limits on
> the total length, set by the size of the buffer.

In my world (embedded hardware and software design) a FIFO chip has a limit
on total length and they have circular address registers. In software, my
circular buffers/queues/fifos also have a size limit and pointers/indices
that wrap around. So there's no difference. Also, considered as a black box,
they operate the same: whatever you put in first, comes out first. So it's a
FIFO. Both.

Meindert