### Bookstore

 Computer Math and Games in Pascal (preview) Lazarus Handbook

### Author Topic: A circular / ring buffer for embedded  (Read 5770 times)

#### d.ioannidis

• Full Member
• Posts: 221
##### Re: A circular / ring buffer for embedded
« Reply #15 on: October 12, 2022, 11:07:31 am »
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 ?

regards,

#### alpine

• Hero Member
• Posts: 1141
##### Re: A circular / ring buffer for embedded
« Reply #16 on: October 12, 2022, 11:35:47 am »
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 ?

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.
"I'm sorry Dave, I'm afraid I can't do that."
—HAL 9000

• Hero Member
• Posts: 14850
• Censorship about opinions does not belong here.
##### Re: A circular / ring buffer for embedded
« Reply #17 on: October 12, 2022, 06:11:38 pm »
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.
Remember the Medway disaster..

#### marcov

• Hero Member
• Posts: 11606
• FPC developer.
##### Re: A circular / ring buffer for embedded
« Reply #18 on: October 12, 2022, 06:14:46 pm »
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.

• Hero Member
• Posts: 14850
• Censorship about opinions does not belong here.
##### Re: A circular / ring buffer for embedded
« Reply #19 on: October 12, 2022, 06:16:23 pm »
which is not the case.
Remember the Medway disaster..

#### marcov

• Hero Member
• Posts: 11606
• FPC developer.
##### Re: A circular / ring buffer for embedded
« Reply #20 on: October 12, 2022, 06:23:03 pm »
which is not the case.

Coincidence or by design?

#### alpine

• Hero Member
• Posts: 1141
##### Re: A circular / ring buffer for embedded
« Reply #21 on: October 12, 2022, 07:32:35 pm »
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.
"I'm sorry Dave, I'm afraid I can't do that."
—HAL 9000

#### d.ioannidis

• Full Member
• Posts: 221
##### Re: A circular / ring buffer for embedded
« Reply #22 on: October 12, 2022, 07:34:32 pm »
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;
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-}
48. {\$POP}
49. end;
50.
51. function SPSC_ReadByte(out ARingBuffer: TSPSCRingBuffer): byte;
52. begin
54. {\$PUSH}
55. {\$Q-}
57. {\$POP}
58. end;
59.
60. procedure SPSC_WriteByte(out ARingBuffer: TSPSCRingBuffer; const AValue: byte);
61. begin
63. {\$PUSH}
64. {\$Q-}
65.   Inc(ARingBuffer.FWriteIndex);
66. {\$POP}
67. end;
68.
69. end.
70.

EDIT: wrong quote ....

regards,

« Last Edit: October 12, 2022, 07:36:04 pm by d.ioannidis »

#### d.ioannidis

• Full Member
• Posts: 221
##### Re: A circular / ring buffer for embedded
« Reply #23 on: October 12, 2022, 08:03:08 pm »
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

• Hero Member
• Posts: 1141
##### Re: A circular / ring buffer for embedded
« Reply #24 on: October 12, 2022, 08:17:00 pm »
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.
"I'm sorry Dave, I'm afraid I can't do that."
—HAL 9000