Recent

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

d.ioannidis

  • Full Member
  • ***
  • Posts: 221
    • Nephelae
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 ?

 Could you please elaborate ?

regards,

alpine

  • Hero Member
  • *****
  • Posts: 1038
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 ?

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

Thaddy

  • Hero Member
  • *****
  • Posts: 14205
  • Probably until I exterminate Putin.
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.
Specialize a type, not a var.

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11383
  • 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.

Thaddy

  • Hero Member
  • *****
  • Posts: 14205
  • Probably until I exterminate Putin.
Re: A circular / ring buffer for embedded
« Reply #19 on: October 12, 2022, 06:16:23 pm »
which is not the case.
Specialize a type, not a var.

marcov

  • Administrator
  • Hero Member
  • *
  • Posts: 11383
  • 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: 1038
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
    • Nephelae
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;
  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,


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

d.ioannidis

  • Full Member
  • ***
  • Posts: 221
    • Nephelae
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: 1038
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

 

TinyPortal © 2005-2018