FIFO(circular) Buffer and LIFO, UART Atmega328

Go To Last Post
18 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hi Folks,

 

I am trying to combine the code that I found, I need to do buffer that will send like LIFO, and no success. Anyone can help me with that?

 


#include <avr/io.h>
#include <avr/interrupt.h>
#include <util/delay.h>

#define USART_BAUDRATE 19200
#define UBRR_VALUE (((F_CPU / (USART_BAUDRATE * 16UL))) - 1)
//define max buffer size
#define BUF_SIZE 200
//type definition of buffer structure
typedef struct{
    //Array of chars
    uint8_t buffer[BUF_SIZE];
    //array element index
    uint8_t index;
}u8buf;
//declare buffer
u8buf buf;
//initialize buffer
void BufferInit(u8buf *buf)
{
    //set index to start of buffer
    buf->index=0;
}
//check buffer
void BufferIsFull(u8buf *buf)
{
    if ((buf->index)==(buf->index<sizeof(buf)))
    {
        return 0;
    }
    else return 1;
}
//write to buffer routine
uint8_t BufferWrite(u8buf *buf, uint8_t u8data)
{
    if (buf->index<BUF_SIZE)
    {
        buf->buffer[buf->index] = u8data;
        //increment buffer index
        buf->index++;
        return 0;
    }
        else return 1;
}
uint8_t BufferReadLIFO(u8buf *buf, volatile uint8_t *u8data)
{
    if(buf->index>0)
    {
        buf->index--;
        //dicrement buffer index
        *u8data=buf->buffer[buf->index];

        return 0;
    }
    else return 1;
}
uint8_t BufferReadFIFO(u8buf *buf, volatile uint8_t *u8data)
{
//soon
}
void USART0Init(void)
{
    // Set baud rate
    UBRR0H = (uint8_t)(UBRR_VALUE>>8);
    UBRR0L = (uint8_t)UBRR_VALUE;
    // Set frame format to 8 data bits, no parity, 1 stop bit
    UCSR0C |= (1<<UCSZ01)|(1<<UCSZ00);
    //enable reception and RC complete interrupt
    UCSR0B |= (1<<RXEN0)|(1<<RXCIE0);
}
//RX Complete interrupt service routine
ISR(USART_RX_vect)
{
    uint8_t u8temp;
    u8temp=UDR0;
    //check if period char or end of buffer
    if ((BufferWrite(&buf, u8temp)==1)||(u8temp==0x0D))
    {
        //disable reception and RX Complete interrupt
        UCSR0B &= ~((1<<RXEN0)|(1<<RXCIE0));
        //enable transmission and UDR0 empty interrupt
        UCSR0B |= (1<<TXEN0)|(1<<UDRIE0);
    }
}
//UDR0 Empty interrupt service routine
ISR(USART_UDRE_vect)
{
    //if index is not at start of buffer
    if (BufferReadLIFO(&buf, &UDR0)==1)
    {
        //start over
        //reset buffer
        BufferInit(&buf);

        //disable transmission and UDR0 empty interrupt
        UCSR0B &= ~((1<<TXEN0)|(1<<UDRIE0));
        //enable reception and RC complete interrupt
        UCSR0B |= (1<<RXEN0)|(1<<RXCIE0);
    }
}
int main (void)
{
    //Initialize USART0
    USART0Init();
    //Init buffer
    BufferInit(&buf);

    //enable global interrupts
    sei();
    while(1)
        {
               _delay_ms(100);
        }
}

 

Last Edited: Tue. Nov 26, 2019 - 02:18 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Figure out the problem on paper first!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

While a LIFO can be operated with one index to the data buffer (it's just like a stack with a stack pointer in fact!) you cannot do that with a FIFO. In that case you need to maintain separate read and write pointers. As things are added to the buffer the write index is incremented (with wrap around which is why it's called a "ring" or "circular" buffer). There is a second pointer/index which holds the point the next read will occur from. Both start at the beginning of the buffer but if you write 3 characters into the buffer the write index moves ahead by 3 bytes. The read index remains at the start. If you now read two bytes from the buffer the read index increments by 2 so is still "just behind" the write index. When the read index catches up with the right index the buffer is either completely full or completely empty. To determine which it's often helpful to keep a separate "number of characters in buffer" that increments as characters are added and decrements as they are read from it. The check for buffer_empty() is then if the count is 0 and for buffer_full() is when count=length_of_buffer. When the buffer is full you need to make a choice about how to handle an attempt to add another byte - one would be to simply reject the attempt to add, the other would be (in circular fashion) to replace the oldest character in the buffer so one is lost (one will be lost either way - either the newest being added, or the oldest that has not been consumed. If you ever hit "buffer is full" it probably means your data processing is not fast enough or your buffer is not defined big enough.

 

As I say LIFO is much easier as you just increment on adds and decrement on reads - you probably do want some protection against "buffer is full" there too though (index = last byte of buffer).

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I verified:

BufferWrite

It works well by printing &buf on 16x2 LCD, which means the string is ok. Let say it has in terminal: 1234QWER or (1[0]2[1]3[2]4[3]Q[4]W[5]E[6]R[7])

when it comes to send it out through echo way to terminal, I receive REWQ4321. So then, "one step back" and let me to understand it, such buffer will be LIFO or FIFO? For me it looks FIFO, 1 came firs, and 1 left first

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

S_Li wrote:
let me to understand it, such buffer will be LIFO or FIFO? For me it looks FIFO, 1 came firs, and 1 left first
What you just described is LIFO. Last in First out. Sou put 1234QWER into it then the first thing out when you start to read it is the last thing in - that is 'R' then 'E' and so on.

 

if it had been a FIFO (First in, First Out) then things come back out in the order you put them in (the first thing put in is the first thing that comes out) so in this case you would push 1234QWER into the buffer then you would read 1234QWER back out (in that order). But, like I say, to do that requires two different indices/pointers - one to keep track of where you are writing and one to keep track of where you are reading.

 

FIFO is much more complex to implement than LIFO but it's the kind of buffer you would want to use (for example) when a UART interrupt is receiving data into the micro faster than you can use it. So you put the characters as they arrive into the FIFO but when you come to process them you want to take them out in the same order as they arrived (so someone sends "Hello" and you later read it out as "Hello" and not "olleH" which is what you would get from a LIFO).

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

ok, then my world became upsidedown now.

thanks for now. 

I will try to focus my attention on other function.

till then I change the name in code in correct order.

here you are my data in sigrok:

Attachment(s): 

Last Edited: Tue. Nov 26, 2019 - 10:54 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I changed little bit BufferIsFull

 

void BufferIsFull(u8buf *buf)
{
    if ((buf->index<sizeof(buf))==(buf->index<BUF_SIZE))
    {
        return 1;
    }
    else return 0;
}

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

That won't work.

void BufferIsFull(u8buf *buf)
{
    if ((buf->index < sizeof(buf))...

"buf" in this is "pointer to u8buf data". I can tell you now that sizeof(any_pointer_type) in avr-gcc is always 2 because all pointers are 16 bit. So you can't use sizeof() here. I guess you really just want to check if the index is less than BUF_SIZE.

 

But I see that the right side of that == is the "right" test. In fact I don't actually know what you intend by the test for equality or why you have two conditional clauses at all?

 

Also, if you are going to implement a BufferIsFull() test then why in:

uint8_t BufferWrite(u8buf *buf, uint8_t u8data)
{
    if (buf->index<BUF_SIZE)
    {

do you not actually use it? Presumably this really means:

uint8_t BufferWrite(u8buf *buf, uint8_t u8data)
{
    if (!BufferIsFull())
    {

Oh and how can BufferIsFull() return 0/1 when the function interface says the function return is "void" ?

 

The whole software looks like you have rushed to implementation before doing design? You shouldn't design software as you are writing C. You should design your solution first THEN write the C to implement the design you have come up with.

Last Edited: Wed. Nov 27, 2019 - 02:22 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

you are right, I do not understand much, however I decided to go in this "sport" to have FIFO solution, trial and fails. Well in the end, I use examples, I do not hide that ))

 

I had check the inspiration here:

https://stackoverflow.com/questions/37538/how-do-i-determine-the-size-of-my-array-in-c

then, in such case, it looks an appropriate solution for avr-gcc to use: 

int a[17];
size_t n = sizeof(a) / sizeof(int);

I guess, by using define, it may have the following form:

 

#define elements (sizeof(buf)/sizeof(*(buf)))

 

 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Here is a buffer example in C (untested)-

https://godbolt.org/z/auQSsk

 

It may be a good start, or just look it over for ideas.

 

I put that together translating my c++ buffer (which works)-

https://github.com/cv007/Avr0PlusPlus/blob/master/Buffer.hpp

 

 

Last Edited: Mon. Dec 2, 2019 - 03:59 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0
int a[17];
size_t n = sizeof(a) / sizeof(int);

Yes but of course that works. What exactly is "a" in this? It is an array of 17 elements that are each of size "int". In AVR sizeof(int) is 2 so sizeof(a) is 34. Then sizeof(int) is 2 so 34 / 2 is 17.

 

But consider this:

void find_size(int * ptrA) {
    printf("size = %d", sizeof(ptrA));
}

int main(void) {
    int a[17];
    size_t num_elements = sizeof(a) / sizeof(int);
    find_size(a);
}

In this code then sure "a" is passed to the find_size() function but the thing being passed here is not "a" itself but just a "pointer to a", that is "the address of a". So when this code gets into find_size() what will it discover? Let's say that the 34 bytes of array a[] have been placed in memory at location 0x1234. So all that is actually passed to the find_size() function is not all 34 bytes (17 elements) but simply the address of where those 34 bytes start (i.e. 0x1234). It is passed as an "int *". Like I said above in AVR "int *" and in fact "anything *" are pointers and they are all 16 bits, 2 bytes. So the printf() in find_size will always print "size = 2". It does not matter whether a[] has 3 elements or 17 elements of 2,429 elements the result is always the same the value (pointer) 0x1234 is held in 2 bytes and that's what the sizeof() prints.

 

With a function like this there are two potential solutions to know how many bytes/elements are in the array. Either you have to pass that separately like:

void find_size(int * ptrA, int len) {
    ...
}

then you call this with:

find_size(a, 17); // passing number of elements
or
find_size(a, 34); // passing number of bytes

or you need to set aside some special value that can be placed in in the data to say where it ends. So you might do:

a[8] = 4545;
find_size(a);

where 4545 is a "special marker value" that would not otherwise appear in the data and this is used to mark the end (and hence signal to stop counting the length) in the receiving code. C already has a very special, heavily used version of this. If I say:

char msg[] = "Hello world";
int n;

n = strlen(msg);

Then when msg[] is created not only are the characters 'H', 'e', 'l' and so on placed into adjacent memory locations but right after the 'd' at the end a very special extra byte (that cannot normally appear in a string) is added on the end. C puts 0x00 in the next byte to say "the string ends here". Then the strlen() function works by counting up the occupied bytes until it comes to one that holds the special 0x00 "end of string" marker.

 

So you either mark the data end somehow then you can just pass the address of the array and let the receiver look for the end marker. Or you pass the address of the array and a separate length so the receiver knows where the data ends.

 

This use of sizeof(pointer_to_data) is one of the most common mistakes in the whole of C - too often people forget that you can't get the size of some data simply because you are given a pointer to (the address of) the data.

Last Edited: Wed. Nov 27, 2019 - 03:44 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

BufferReadFIFO pass well only first time, something still is not working yet.

 

//define max buffer size
#define MAX_BUF_SIZE 200
//type definition of buffer structure
typedef struct{
    //Array of chars
    uint8_t buffer[MAX_BUF_SIZE];
    uint8_t actual_buffer_size;
    uint8_t index_write;
    uint8_t index_read;
}u8buf;
//declare buffer
u8buf buf;
//initialize buffer
void BufferInit(u8buf *buf)
{
    //set index to start of buffer
    buf->index_write=0;
}
//Buffer lenght
uint8_t DataLength(u8buf *buf)
{
   // return length of valid data in buf
   return (buf->index_write - buf->index_read) & (buf->actual_buffer_size - 1);
}
//write to buffer routine
uint8_t BufferWrite(u8buf *buf, uint8_t u8data)
{
    if (buf->index_write<MAX_BUF_SIZE)
    {
        buf->buffer[buf->index_write] = u8data;
        //increment buffer index
        buf->index_write++;
        return 0;
    }
        else return 1;
}
uint8_t BufferReadLIFO(u8buf *buf, volatile uint8_t *u8data)
{
    if(buf->index_write>0)
    {
        buf->index_write--;
        *u8data=buf->buffer[buf->index_write];
        return 0;
    }
    else return 1;
}
uint8_t BufferReadFIFO(u8buf *buf, volatile uint8_t *u8data)
{
    if (DataLength(buf) == 0)
    {
        return 1;
    }
    // read data & increment read pointer
    *u8data = buf->buffer[buf->index_read];
    buf->index_read = (buf->index_read + 1) & (buf->actual_buffer_size - 1);
    return 0;
}

 

Last Edited: Mon. Dec 2, 2019 - 02:53 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

That code uses a member called "actual_buffer_size" without, apparently, ever initialising it ?!? Perhaps you intended:

void BufferInit(u8buf *buf)
{
    //set index to start of buffer
    buf->index_write=0;
    buf->acutal_buffer_size = MAX_BUF_SIZE;
}

but forget it as that's still not going to work. You do your buffer wrapping with:

buf->index_read = (buf->index_read + 1) & (buf->actual_buffer_size - 1);

but & (AND) with size-1 will ONLY work when the buffer size is some binary multiple so if it were 64 then & (size-1) would be & 0x3F or if it were 512 then it would be & 0x1FF etc.

 

But your size is 200. 200 - 1 is 199 so your & would be with 0xC7 which is 0b110111. That does not constrain the index correctly?!?

 

Also you do:

uint8_t BufferWrite(u8buf *buf, uint8_t u8data)
{
    if (buf->index_write<MAX_BUF_SIZE)
    {
        buf->buffer[buf->index_write] = u8data;
        //increment buffer index
        buf->index_write++;
        return 0;

That increments the write index without making any attempt to wrap it. So when that reaches the end of the buffer it drops off the end.

 

If you want to see a really good implementation of FIFO then look at:

 

http://www.fourwalledcubicle.com/files/LightweightRingBuff.h

 

That uses buffer pointers not buffer indices and just does the simple test of "has the pointer reached the address of the last byte in the buffer? if so set it back to the start". No fancy messing about.

Last Edited: Mon. Dec 2, 2019 - 01:23 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

clawson wrote:
buf->acutal_buffer_size = MAX_BUF_SIZE;

I tried, and many other thing. that why I left if in the way that it is.

About buffer size, it makes no sense if it will not accept any length.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 1

S_Li wrote:
About buffer size, it makes no sense if it will not accept any length.

Let me know when you find the model of microcontroller with infinite storage space.  [hint:  there is none and thus your assertion isn't correct]

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

theusch wrote:

S_Li wrote:

About buffer size, it makes no sense if it will not accept any length.

 

Let me know when you find the model of microcontroller with infinite storage space.  [hint:  there is none and thus your assertion isn't correct]

your sarcasm is not accepted. i am speaking in reasonable limits

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

S_Li wrote:
About buffer size, it makes no sense if it will not accept any length.
It's your choice. There is a "trick" you can use if you are willing to stick to binary sized buffers (8, 16, 32, 64, 128... bytes). In this case you can make your index increment:

index = (index + 1) & (buff_size - 1);

so for 8, 16, 32, 64, 128 etc sized buffers this will & with 7, 15, 31, 63, 127 etc so that is 0b111, 0b1111, 0b11111, 0b111111, 0b1111111 etc - clearly these are "special values" that mask out just the lower bits of the incremented value. So say the buffer size is 32 bytes and index is currently 31 then 31+1 becomes 32 or 0b100000 but this is &'d with 0b11111 so the leading 0 is dropped and it's reset back to 0 without special code. If you want to support ANY size of buffer then the other choice is:

index++;
if (index >= buff_size) {
    index = 0;
}

so this requires a test for the special case when the index has reached the end of the buffer.

 

The & solution is "quick and neat" and can save a few cycles if time is really critical. But if you want the flexibility of 20, 37, 59 byte buffers then use the latter.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

S_Li wrote:
your sarcasm is not accepted. i am speaking in reasonable limits

How am I to know that "any size" includes "reasonable limits"?

 

I thought about, in general terms, how I might approach coding a LIFO with unknown "size".  The first question seems to be whether to stop adding, "truncate", when full.  But then the contents of the buffer becomes stale, and the latest in are lost.

 

Or, you can do a wrap mechanism where the oldest is lost.  But then the mechanism becomes more complicated, akin to the FIFO case.  I discarded the notion of moving all elements "down" as being too slow and costly.

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.