Forums

Interrupt driven UART

Started by gois...@gmail.com October 12, 2006
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