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.