| View previous topic :: View next topic |
| Author |
Message |
BM92
Joined: 04 Oct 2013
Posts: 18
|
| FIFO queue |
 Posted: Mon Nov 04, 2013 6:58 am |
 |
|
I am attempting to create an array which will take data in and once full remove the oldest piece of data and enter a new piece of data.
I was thinking along the lines of using
| Code: | int Q[100], f=0, r=-1;
int Qfull()
{
if (r==size) return 1;
return 0;
}
int Qinsert()
{
if(Qfull())
{
elem=Q[f];
f=f+1;
return elem;
r++;
Q[r]=SPI1BUF;
}
else
{
r++;
Q[r]=SPI1BUF;
}
} |
However this will eventually fail once the array is full due to r increasing beyond 100 and the front term will also reach 100 eventually too. Is there anyway to shift the array values |
|
 |
Ttelmah
Joined: 11 Mar 2010
Posts: 19538
|
|
| Posted: Mon Nov 04, 2013 8:38 am |
|
|
Look at a circular buffer...
EX_SISR.C, shows one being used for serial data. You have two addresses stored, 'where the next character is to go', and 'where data should come from'. These 'chase' one another round the buffer.
So adding a character, means writing it 'where the next character is to go', then incrementing this address. If the address gets to the end of the buffer it goes back to zero. When the address if incremented, if it matches 'where data should come from', then the buffer is full, so you increment 'where data should come from' to lose the oldest character.
Reading a character is just a matter of reading from 'where data is to come from', and incrementing this.
If the addresses 'match' after reading, then the buffer is empty.
As a comment, 'int' in CCS, is _unsigned_, so can't hold -1.....
The advantage is that the data never has to move. Just the addresses.
| Code: |
#define SIBUFF (100) //buffer size
typedef struct {
int8 in;
int8 out;
int8 buff[SIBUFF];
} buffer;
buffer Q;
int8 btempQ;
#define incin(buff) ((buff.in==(SIBUFF-1))?0:buff.in+1)
#define incout(buff) ((buff.out==(SIBUFF-1))?0:buff.out+1)
#define isempty(buff) (buff.in==buff.out)
#define hasdata(buff) (buff.in!=buff.out)
#define isfull(buff) ((incin(buff)==buff.out)
#define tobuff(bname,c) { bname.buff[bname.in]=c;\
bname.in=incin(bname);\
if (bname.in==bname.out) bname.out=incout(bname);\
}
#define frombuff(bname) (btemp##bname=bname.buff[bname.out],\
bname.out=incout(bname), \
btemp##bname)
#define clrbuff(buff) buff.in=buff.out=0
|
Then 'clrbuff(Q)' will reset the pointers,
tobuff(Q,chr) adds 'chr' to the buffer
hasdata(Q) returns TRUE if the buffer has data available.
isempty(Q) returns TRUE if the buffer is empty
isfull(Q) returns TRUE if the buffer is full
val=frombuff(Q) reads the next character from the buffer.
Same code can be used for multiple different buffers.
Best Wishes |
|
|
BM92
Joined: 04 Oct 2013
Posts: 18
|
|
| Posted: Mon Nov 04, 2013 9:49 am |
|
|
Im not sure i entirely understand the code above. I am looking for a simple way to fill and array with data. Once full i want the oldest piece of data to be removed and a new piece of data to be added.
Is this not possible using a linear queue in the fashion i have but implementing some form of code to shift the data? |
|
|
asmboy
Joined: 20 Nov 2007
Posts: 2128
Location: albany ny
|
|
| Posted: Mon Nov 04, 2013 10:10 am |
|
|
MR. T's code is robust and superior to any linear buffer ,
in that it can be loaded by an interrupt handler safely
even if in the middle of a buffer read operation.
so long as you service it often enough, you will never lose any data.
shifting and double handling the data is slow and risky.
The code he posted uses very efficient CCS coding as bonus.
i would not hesitate to use it, as it is top quality programming. |
|
|
Ttelmah
Joined: 11 Mar 2010
Posts: 19538
|
|
| Posted: Mon Nov 04, 2013 10:41 am |
|
|
Thanks asmboy. 
I'd do a wiki search on circular buffers.
It really is vital to change the way you think....
Key is that reading a byte in an array on a PIC, is quite inefficient. Typically takes about ten instructions. Now 'moving' a 100 byte buffer by one byte, involves 99 reads, and 99 writes. So about 2000 instructions!. Ouch...
The point is though that you never actually have to move the data. Imagine you have a group of cards laid on a table. You want to add cards at one end of this, and remove them at the other. Obvious way is the way you are thinking, physically moving the cards. However the other 'way', is to have the cards just laid out 'round' the table, and have two little 'markers' showing where you want to add them, and where you want to remove them. All you have to do is move these markers, not the cards themselves. This is the circular buffer.
Best Wishes |
|
|
BM92
Joined: 04 Oct 2013
Posts: 18
|
|
| Posted: Mon Nov 04, 2013 1:52 pm |
|
|
| Ttelmah wrote: | Thanks asmboy.
I'd do a wiki search on circular buffers.
It really is vital to change the way you think....
Key is that reading a byte in an array on a PIC, is quite inefficient. Typically takes about ten instructions. Now 'moving' a 100 byte buffer by one byte, involves 99 reads, and 99 writes. So about 2000 instructions!. Ouch...
The point is though that you never actually have to move the data. Imagine you have a group of cards laid on a table. You want to add cards at one end of this, and remove them at the other. Obvious way is the way you are thinking, physically moving the cards. However the other 'way', is to have the cards just laid out 'round' the table, and have two little 'markers' showing where you want to add them, and where you want to remove them. All you have to do is move these markers, not the cards themselves. This is the circular buffer.
Best Wishes |
That makes a lot of sense. thank you. I guess i am just struggling with the way you have written it as it may be more advanced than i am used to. when looking at examples i understand more such as the following i cannot see the point at which the old data is overwritten. apologies if there is something very basic i seem to be missing
| Code: | #define BUFFER_SIZE 256
item *buffer[BUFFER_SIZE];
int start = 0;
int end = 0
int active = 0;
void PushToQueue(item *p)
{
buffer[end] = p;
end = (end + 1) % BUFFER_SIZE;
if (active < BUFFER_SIZE)
{
active++;
} else {
/* Overwriting the oldest. Move start to next-oldest */
start = (start + 1) % BUFFER_SIZE;
}
}
item *RetrieveFromQueue(void)
{
item *p;
if (!active) { return NULL; }
p = buffer[start];
start = (start + 1) % BUFFER_SIZE;
active--;
return p;
}
|
edit: after reading i believe it is to do with the Modulus operator. How does this work. For example what is the purpose of end=(end+1) % BUFFER_SIZE
Last edited by BM92 on Mon Nov 04, 2013 2:42 pm; edited 1 time in total |
|
|
gpsmikey
Joined: 16 Nov 2010
Posts: 588
Location: Kirkland, WA
|
|
| Posted: Mon Nov 04, 2013 2:27 pm |
|
|
Look at it like washing your car - you can hold the brush still and move the car back and forth (shifting the data) or you can hold the car still and move the brush back and forth (pointing to where to "wash"). changing where you point is definitely easier (and faster).
mikey
_________________
mikey
-- you can't have too many gadgets or too much disk space !
old engineering saying: 1+1 = 3 for sufficiently large values of 1 or small values of 3 |
|
|
Ttelmah
Joined: 11 Mar 2010
Posts: 19538
|
|
| Posted: Mon Nov 04, 2013 2:31 pm |
|
|
First, don't use % BUFFER_SIZE
This only works efficiently with 'binary' buffer sizes (1,2,4,8 etc.). Otherwise it has to code as a division, which is slow. This is a limitation that is not documented in the EX_SISR code....
The alternative is to test if the value is BUFFER_SIZE-1, and if so, increment it to zero. This can be coded as:
| Code: |
if (end==(BUFFER_SIZE-1))
end=0;
else
end++;
//Now, C allows this also to be coded as:
end=((end==(BUFFER_SIZE-1))?0:end+1;
|
The second is the code used in my version above.
It is rather a 'non obvious' bit of C, but what it does is evaluate the test, and then sets the result to the first or second value. 'BUFFER_SIZE-1', is a constant, so this is calculated at compile time. So no maths at all...
Now also the whole buffer is stored in one data construct - the structure. This means that you can declare multiple buffers without having to declare separate variables each time.
You seem to be passing the whole buffer around using a pointer. Why?.
You were showing the original buffer as just storing integers, as such you don't want to be doing this. Your original buffer stored 100 numbers so this is what I showed.
You were showing the value coming from the SPI1BUF. As such you would need to wait for a new value to arrive (if a slave), or clock out a new value (if a master).
Best Wishes |
|
|
BM92
Joined: 04 Oct 2013
Posts: 18
|
|
| Posted: Mon Nov 04, 2013 2:44 pm |
|
|
| Ttelmah wrote: | First, don't use % BUFFER_SIZE
This only works efficiently with 'binary' buffer sizes (1,2,4,8 etc.). Otherwise it has to code as a division, which is slow. This is a limitation that is not documented in the EX_SISR code....
The alternative is to test if the value is BUFFER_SIZE-1, and if so, increment it to zero. This can be coded as:
| Code: |
if (end==(BUFFER_SIZE-1))
end=0;
else
end++;
//Now, C allows this also to be coded as:
end=((end==(BUFFER_SIZE-1))?0:end+1;
|
The second is the code used in my version above.
It is rather a 'non obvious' bit of C, but what it does is evaluate the test, and then sets the result to the first or second value. 'BUFFER_SIZE-1', is a constant, so this is calculated at compile time. So no maths at all...
Now also the whole buffer is stored in one data construct - the structure. This means that you can declare multiple buffers without having to declare separate variables each time.
You seem to be passing the whole buffer around using a pointer. Why?.
You were showing the original buffer as just storing integers, as such you don't want to be doing this. Your original buffer stored 100 numbers so this is what I showed.
You were showing the value coming from the SPI1BUF. As such you would need to wait for a new value to arrive (if a slave), or clock out a new value (if a master).
Best Wishes |
Great thank you. Yes i am simply storing integer numbers in the buffer. I will take a look at your method and try to understand it some more. Guess its just a case of reading it and trying to get my head around a different way of writing things. Thank you for all your help |
|
|
BM92
Joined: 04 Oct 2013
Posts: 18
|
|
| Posted: Mon Nov 04, 2013 3:17 pm |
|
|
After looking at the usage i need for my code i have realised that i do not need to take any data out as i am simply keeping this array to take an average of values that are stored. Therefore i can just overwrite the oldest piece of data and not do anything else.
Does the following code seem ok?
| Code: | int end=0;
int active=0;
int BUF_SIZE=10;
int buff[BUF_SIZE];
int in;
#define incout(buff) ((buff.end==(SIBUFF-1))?0:buff.end+1)
cirBuff()
{
if(active<(BUF_SIZE-1))
{
buff[end]=in;
end++;
active++;
}
else
{
incout(buff);
buff[end]=in;
}
} |
|
|
|
Ttelmah
Joined: 11 Mar 2010
Posts: 19538
|
|
| Posted: Mon Nov 04, 2013 4:01 pm |
|
|
Look how I use incout. The result has to go somewhere.
If you just want to average, why store the data at all?. Just store the sum.
Add the values as you go, and when you have received what you want, divide the sum by the number of values, store this, and clear the sum. Much less memory....
Best Wishes |
|
|
BM92
Joined: 04 Oct 2013
Posts: 18
|
|
| Posted: Mon Nov 04, 2013 4:09 pm |
|
|
The reason for this method is because the specific application i am using my code for is not a standard one and must be done in this way. I will not go into details but there are more than one process which i need to carry out on this array.
Why does the data need to go somewhere. Can it not simply be overwritten by placing another piece of data in that cell? |
|
|
Ttelmah
Joined: 11 Mar 2010
Posts: 19538
|
|
| Posted: Tue Nov 05, 2013 2:03 am |
|
|
The output address, is not the data.
incout, and incin, increment the addresses where the data is to be stored/read. The calculated value has to go back into these addresses.
Best Wishes |
|
|
Mike Walne
Joined: 19 Feb 2004
Posts: 1785
Location: Boston Spa UK
|
|
| Posted: Tue Nov 05, 2013 3:39 am |
|
|
This does not help | Quote: | | The reason for this method is because the specific application i am using my code for is not a standard one and must be done in this way. |
Tell us everything to be done on the array, we may be able to offer a better solution.
I frequently calculate mean and RMS values.
Text books often show this as two passes through all the data.
It is not necessary to use arrays at all, simply sums.
Mike |
|
|
BM92
Joined: 04 Oct 2013
Posts: 18
|
|
| Posted: Wed Nov 06, 2013 5:35 pm |
|
|
I can confirm that after testing my code works as is needed. After a few minor tweeks to it. This mean it will replace the oldest piece of data with a new piece of data.
The array is used for a PID type function except it will be taking averages of multiple values instead of a single value.
eg. (sum of (setpoint-data))/size
and the same type of thing for differential and integral |
|
|
|
FAQ 
Search
Register
Profile 
Log in to check your private messages 
Log in
