AVR Freaks

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

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

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.

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.

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]

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.