A circular / ring buffer for embedded

[d.ioannidis]

Hi,

Just let it overflow with {$R-}. Need power of two, of course and the correct bit size.

Code: Pascal  [Select][+][-]

1. program ringbuffer;
2. {$R-}
3. var
4.     b:byte = 0;
5. begin
6.   repeat
7.     writeln(b);
8.     inc(b);
9.   until 0=1;// silly, replace with signal hi/lo....
10. end.

Audio buffers trick.... That's how I used it in the past... And it is a 256 ringbuffer which is perfect for embedded.

 I use the same technique for the ring buffer read/write indices ( i.e. see here for read ) but how the above can be a ring buffer with 256 slots ? Where the values are stored ? What am I missing ?

 Could you please elaborate ?

regards,

[alpine]

Hi,

Just let it overflow with {$R-}. Need power of two, of course and the correct bit size.

Code: Pascal  [Select][+][-]

1. program ringbuffer;
2. {$R-}
3. var
4.     b:byte = 0;
5. begin
6.   repeat
7.     writeln(b);
8.     inc(b);
9.   until 0=1;// silly, replace with signal hi/lo....
10. end.

Audio buffers trick.... That's how I used it in the past... And it is a 256 ringbuffer which is perfect for embedded.

 I use the same technique for the ring buffer read/write indices ( i.e. see here for read ) but how the above can be a ring buffer with 256 slots ? Where the values are stored ? What am I missing ?

 Could you please elaborate ?

regards,

IMO this is just an example how the buffer pointer can be incremented and modulo 256 taken, without actually writing it ( b := (b + 1) % 256 ) by using the byte boundaries.

[Thaddy]

No, modulo is on most CPU's an expensive operation. Using overflow is NOT an expensive operation.
I will add a simple sine wave later  to demonstrate its use. But it is very easy anyway.

[marcov]

No, modulo is on most CPU's an expensive operation. Using overflow is NOT an expensive operation.
I will add a simple sine wave later  to demonstrate its use. But it is very easy anyway.

Well, assuming of course that this won't fail horribly because the compiler chooses a larger register size for the variable.

[Thaddy]

which is not the case.

[marcov]

which is not the case.

Coincidence or by design?

[alpine]

No, modulo is on most CPU's an expensive operation. Using overflow is NOT an expensive operation.
I will add a simple sine wave later  to demonstrate its use. But it is very easy anyway.

No?
FYI modulo of 2^n is quite a light operation and is actually bit-wise and with 2^n-1. In your example, that you called an overflow, even the bit-wise and isn't needed because it is achieved naturally by the limited length of the register - the carry just drops into the status flags and gets ignored. Regardless of the size of the type/register, unsigned and two's complement integers always naturally form a commutative ring. See also modular arithmetics.

[d.ioannidis]

Hi,

No, modulo is on most CPU's an expensive operation. Using overflow is NOT an expensive operation.
I will add a simple sine wave later  to demonstrate its use. But it is very easy anyway.

No?
FYI modulo of 2^n is quite a light operation and is actually bit-wise and with 2^n-1. In your example, that you called an overflow, even the bit-wise and isn't needed because it is achieved naturally by the limited length of the register - the carry just drops into the status flags and gets ignored. Regardless of the size of the type/register, unsigned and two's complement integers always naturally form a commutative ring. See also modular arithmetics.

the spsc_ringbuffer code is exactly what you describe .

Stripped down is effectively :

Code: Pascal  [Select][+][-]

1. unit spsc_ringbuffer;
2.  
3. {$mode objfpc}
4. {$macro on}
5. {$inline on}
6.  
7. interface
8.  
9. {$define SPSC_PTRUINT := Byte}
10.  
11. type
12.  
13.   TSPSCRingBuffer = packed record
14.     FBuffer: pbyte;
15.     FBufferSize, FReadIndex, FWriteIndex: SPSC_PTRUINT;
16.   end;
17.  
18. function SPSC_IsEmpty(constref ARingBuffer: TSPSCRingBuffer): boolean;
19. function SPSC_IsFull(constref ARingBuffer: TSPSCRingBuffer): boolean;
20. function SPSC_Size(constref ARingBuffer: TSPSCRingBuffer): SPSC_PTRUINT;
21.  
22. function SPSC_ReadByte(out ARingBuffer: TSPSCRingBuffer): byte;
23. procedure SPSC_WriteByte(out ARingBuffer: TSPSCRingBuffer; const AValue: byte);
24.  
25. implementation
26.  
27. function SPSC_MaskIndex(constref ARingBuffer: TSPSCRingBuffer; const AValue: SPSC_PTRUINT): SPSC_PTRUINT; inline;
28. begin
29.   Result := AValue and (ARingBuffer.FBufferSize - 1);
30. end;
31.  
32. function SPSC_IsEmpty(constref ARingBuffer: TSPSCRingBuffer): boolean;
33. begin
34.   Result := ARingBuffer.FReadIndex = ARingBuffer.FWriteIndex;
35. end;
36.  
37. function SPSC_IsFull(constref ARingBuffer: TSPSCRingBuffer): boolean;
38. begin
39.   Result := SPSC_Size(ARingBuffer) = ARingBuffer.FBufferSize - 1;
40. end;
41.  
42. function SPSC_Size(constref ARingBuffer: TSPSCRingBuffer): SPSC_PTRUINT;
43. begin
44. {$PUSH}
45. {$Q-}
46. {$R-}
47.   Result := SPSC_MaskIndex(ARingBuffer, ARingBuffer.FWriteIndex -  ARingBuffer.FReadIndex);
48. {$POP}
49. end;
50.  
51. function SPSC_ReadByte(out ARingBuffer: TSPSCRingBuffer): byte;
52. begin
53.   Result := ARingBuffer.FBuffer[SPSC_MaskIndex(ARingBuffer,  ARingBuffer.FReadIndex)];
54. {$PUSH}
55. {$Q-}
56.   Inc(ARingBuffer.FReadIndex);
57. {$POP}
58. end;
59.  
60. procedure SPSC_WriteByte(out ARingBuffer: TSPSCRingBuffer; const AValue: byte);
61. begin
62.   ARingBuffer.FBuffer[SPSC_MaskIndex(ARingBuffer, ARingBuffer.FWriteIndex)] := AValue;
63. {$PUSH}
64. {$Q-}
65.   Inc(ARingBuffer.FWriteIndex);
66. {$POP}
67. end;
68.  
69. end.
70.  

EDIT: wrong quote ....

regards,

[d.ioannidis]

Hi,

... even the bit-wise and isn't needed because it is achieved naturally by the limited length of the register ...

 the bit-wise AND is needed in the case the buffer size is smaller of the index type max value. 

 i.e. If the index are type of byte and the buffer size is 64 instead of 128 the "index AND (size - 1)" clamps the value into the buffer size range .

 At least this is how I understand it.

regards,

[alpine]

Hi,

... even the bit-wise and isn't needed because it is achieved naturally by the limited length of the register ...

 the bit-wise AND is needed in the case the buffer size is smaller of the index type max value. 

 i.e. If the index are type of byte and the buffer size is 64 instead of 128 the "index AND (size - 1)" clamps the value into the buffer size range .

 At least this is how I understand it.

regards,

Right, (x mod 2^n) is same as (x and (2^n-1)). In the case when we're incrementing a BYTE with a value of $FF, the carry from the seventh bit to the eight (which is not present) just vanishes, it is same as to make ($10000 and $FFFF) - the result is zero.

[hakelm]

Happened to see this.
Here is a little ringbuffer if someone is interested:

Code: Pascal  [Select][+][-]

1. unit ringbuffer;
2.  
3. {$mode ObjFPC}{$H+}
4.  
5. interface
6.  
7. uses
8.   Classes, SysUtils;
9. type
10.   tdata=integer;
11.   tdataarr=array of tdata;
12.   { tringbuffer }
13.  
14.   tringbuffer=class
15.   private
16.     fdata:tdataarr;
17.     mask:integer;
18.     indexofzero:integer;
19.     function getdata(age: integer): tdata;
20.     procedure setdata(age: integer; AValue: tdata);
21.   public
22.     constructor create(asize:integer);
23.     property data[age:integer]:tdata read getdata write setdata; //use only to alter data w:o adding new items
24.     procedure put(avalue:tdata);  //inserts a new item updates indexofzero
25.   end;
26.  
27. implementation
28.  
29. { tringbuffer }
30.  
31. function tringbuffer.getdata(age: integer): tdata;
32. begin
33.   age:=(age+indexofzero) and mask;
34.   result:=fdata[age];
35. end;
36.  
37. procedure tringbuffer.setdata(age: integer; AValue: tdata);
38. begin
39.   age:=(age+indexofzero) and mask;
40.   fdata[age]:=avalue;
41. end;
42.  
43. constructor tringbuffer.create(asize: integer);
44. begin
45.   mask:=1;
46.   while mask<asize do
47.     mask:=(mask shl 1)+1;
48.   setlength(fdata,mask);
49. end;
50.  
51. procedure tringbuffer.put(avalue: tdata);
52. begin
53.   indexofzero:=(indexofzero-1) and mask;
54.   fdata[indexofzero]:=avalue;
55. end;
56.  
57. end.
58.  

[Thaddy]

On embedded, my ringbuffer approach is really the way to go and it is also the most used in other programming languages, because it is the least computationally expensive as long as you know what you are doing.
There is a lot of cow dung in this thread. Mine isn't. It is pretty much standard.
Most people have ears, in the case of programmers they are merely rudimentary, just as our vestigal organ: the tail bone, which seems appropiate in this context.

[Thaddy]

OK, the loooong promised code. I had some time.

Code: Pascal  [Select][+][-]

1. program sinewaveringbuffer;
2. {$mode objfpc}{$R-}{$Q-}
3. uses
4.   SysUtils, Math;
5.  
6. const
7.   BufferSize = 256; // Size of the ring buffer
8.   TwoPi = 2 * Pi;   // Precompute 2 * Pi for sine wave calculation
9.  
10. var
11.   RingBuffer: array[0..BufferSize-1] of Single; // Ring buffer to store sine wave samples
12.   Index: Cardinal = 0; // Index for the ring buffer (will overflow naturally)
13.  
14. // Initialize the ring buffer with a sine wave
15. procedure InitializeRingBuffer;
16. var
17.   i: Integer;
18. begin
19.   for i := 0 to BufferSize - 1 do
20.     RingBuffer[i] := Sin(TwoPi * i / BufferSize); // Generate sine wave samples
21. end;
22.  
23. // Get the next sample from the ring buffer
24. function GetNextSample: Single;inline;
25. begin
26.   Result := RingBuffer[Index];
27.   Index := (Index + 1) and (BufferSize - 1); // Increment index with overflow (power-of-two buffer size required)
28. end;
29.  
30. // Main program
31. var
32.   i: Integer;
33.   Sample: Single;
34. begin
35.   // Initialize the ring buffer with a sine wave
36.   InitializeRingBuffer;
37.  
38.   // Generate and print some samples
39.   for i := 1 to 1000 do
40.   begin
41.     Sample := GetNextSample;
42.     WriteLn('Sample ', i, ': ', Sample:0:4);
43.   end;
44. end.

Can run forever otherwise.
This is simply how it works. I use this for audio for 25+ odd years.
This is really the fastest approach to a ring buffer and works for real time tested up to 192000 sample rate.
It is lifted from a 22 year old back-up. Added fresh comments.

[robert rozee]

an interesting thread - largely because i always understood that the concept of a ringbuffer was that it had a head and a tail. the structure i use is:

Code: Pascal  [Select][+][-]

1. const RxBuffer:record                                    // serial input (ring) buffer
2.                  data:array [0..$3FFFF] of char;         // 256k
3.                  head:integer;
4.                  tail:integer;
5.                  skip:boolean
6.                end=(data:''; head:0; tail:0; skip:false);

two processes then have access to the ring buffer. in the above case this is a thread dedicated to reading data from a serial port:

Code: Pascal  [Select][+][-]

1. procedure TSerialThread.Execute;
2. var I, J, K:integer;
3.      Buffer:string[255];
4.          ch:char;
5. begin
6.   while not ExitThreads do
7.   begin
8.  
9. // ******** read data from serial port and place into RxBuffer *****************
10.  
11.     if not RxBuffer.skip and CONNECTED then                            // RxBuffer.skip -> application is in the middle of accessing the RxBuffer
12.     repeat
13.  
14.       try I:=fpRead(SerialHandle, @Buffer[1], 250) except I:=-1 end;   // adding @ suppresses a compiler note, seems to still work ok
15.  
16.  
17.       if I>0 then begin                                                // data has been read in from serial port
18.                     SetLength(Buffer, I);
19.  
20.                     for J:=1 to length(Buffer) do
21.                     begin
22.                       ch:=Buffer[J];
23.                       K:=(RxBuffer.head+1) mod sizeof(RxBuffer.data);
24.  
25.                       if K<>RxBuffer.tail then
26.                       begin
27.                         RxBuffer.data[RxBuffer.head]:=ch;              // insert character into ring buffer
28.                         RxBuffer.head:=K                               // increment head index
29.                       end
30.                     end
31.                   end else
32.       if I<0 then begin                                                // ERROR - disconnect and advise main program
33.                     CONNECTED:=false;
34.                     try fpClose(SerialHandle) except end
35.                   end
36.  
37.     until not CONNECTED or (I<=0)                                      // keep reading until disconnected or nothing to read
38.   end
39. end;

(SerialHandle, CONNECTED, and ExitThreads defined elsewhere)

... and a regular timer event that processes data from the ring buffer with the aid of a few 'helper' functions:

Code: Pascal  [Select][+][-]

1. // returns how much time has elapsed since GetTickCount64 was assigned to a counter
2. // (placed up here as is used within serial.inc)
3. function timesince(counter:int64):int64;
4. begin
5.   result:=GetTickCount64-counter
6. end;
7.  
8.  
9. function ReadSerialQueue(var ch:char; timeout:int64):boolean;          // read (any) single character , with timeout
10. var TimeFlag:boolean;
11.         mark:int64;
12.            I:integer;
13.            B:boolean;
14. begin
15.   ch:=#00;                                                             // returns character set to #00 if nothing to read
16.   mark:=GetTickCount64;
17.  
18.   RxBuffer.skip:=true;         { lock access }
19.   B:=(RxBuffer.head=RxBuffer.tail);
20.   RxBuffer.skip:=false;        { free access }
21.  
22.   if (timeout<>0) and B then
23.   repeat                                                               // may NOT pass through -> TimeFlag MAY be undefined
24.     Application.ProcessMessages;
25.     TimeFlag:=(timesince(mark)>timeout);
26.  
27.     RxBuffer.skip:=true;       { lock access }
28.     B:=(RxBuffer.head<>RxBuffer.tail);
29.     RxBuffer.skip:=false       { free access }
30.   until B or TimeFlag;
31.  
32.   RxBuffer.skip:=true;         { lock access }
33.   B:=(RxBuffer.head=RxBuffer.tail);
34.   RxBuffer.skip:=false;        { free access }
35.  
36.   if B then result:=false else
37.   begin
38.     RxBuffer.skip:=true;       { lock access }
39.     I:=RxBuffer.tail;
40.     RxBuffer.skip:=false;      { free access }
41.  
42.     ch:=RxBuffer.data[I];
43.     I:=(I+1) mod sizeof(RxBuffer.data);
44.  
45.     RxBuffer.skip:=true;       { lock access }
46.     RxBuffer.tail:=I;
47.     RxBuffer.skip:=false;      { free access }
48.     result:=true
49.   end
50. end;

Code: Pascal  [Select][+][-]

1. procedure TForm1.Timer1Timer(Sender: TObject);
2. begin
3.   if ReadSerialQueue(ch, 0) then then write(ch)
4. end;

the above is all code i just clipped out of a much larger project and purged of superfluous stuff that wasn't relevant here (like a 2nd ring buffer for TxData and handled by the same serial thread). so i might have broken something in the process!


cheers,
rob   :-)

[Thaddy]

Robert,

You confuse the theory of a ringbuffer with its possible implementation as a linked list with a fixed size, which can be a ringbuffer, but is implementation detail.
A ringbuffer is theoretically any implementation of fixed length that resets itself to its start after a given linear number of probes, a.k.a. a ladder run.

But a ringbuffer need not be a linked list. A linked list is certainly not the most efficient implementation of a ringbuffer. That is the way I demonstrated: no need to maintain any pointers, hence it is so popular for real-time applications like video and audio: It is demonstrably the fastest way.