Forum > Embedded
A circular / ring buffer for embedded
marcov:
--- Quote from: Thaddy on October 12, 2022, 06:16:23 pm ---which is not the case.
--- End quote ---
Coincidence or by design?
alpine:
--- Quote from: Thaddy 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.
--- End quote ---
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,
--- Quote from: y.ivanov on October 12, 2022, 07:32:35 pm ---
--- Quote from: Thaddy 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.
--- End quote ---
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.
--- End quote ---
the spsc_ringbuffer code is exactly what you describe .
Stripped down is effectively :
--- Code: Pascal [+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i < x.length; i++) { x[i].style.maxHeight='none'; x[i].style.height = Math.min(x[i].clientHeight+15,306)+'px'; x[i].style.resize = "vertical";}};} ---unit spsc_ringbuffer; {$mode objfpc}{$macro on}{$inline on} interface {$define SPSC_PTRUINT := Byte} type TSPSCRingBuffer = packed record FBuffer: pbyte; FBufferSize, FReadIndex, FWriteIndex: SPSC_PTRUINT; end; function SPSC_IsEmpty(constref ARingBuffer: TSPSCRingBuffer): boolean;function SPSC_IsFull(constref ARingBuffer: TSPSCRingBuffer): boolean;function SPSC_Size(constref ARingBuffer: TSPSCRingBuffer): SPSC_PTRUINT; function SPSC_ReadByte(out ARingBuffer: TSPSCRingBuffer): byte;procedure SPSC_WriteByte(out ARingBuffer: TSPSCRingBuffer; const AValue: byte); implementation function SPSC_MaskIndex(constref ARingBuffer: TSPSCRingBuffer; const AValue: SPSC_PTRUINT): SPSC_PTRUINT; inline;begin Result := AValue and (ARingBuffer.FBufferSize - 1);end; function SPSC_IsEmpty(constref ARingBuffer: TSPSCRingBuffer): boolean;begin Result := ARingBuffer.FReadIndex = ARingBuffer.FWriteIndex;end; function SPSC_IsFull(constref ARingBuffer: TSPSCRingBuffer): boolean;begin Result := SPSC_Size(ARingBuffer) = ARingBuffer.FBufferSize - 1;end; function SPSC_Size(constref ARingBuffer: TSPSCRingBuffer): SPSC_PTRUINT;begin{$PUSH}{$Q-}{$R-} Result := SPSC_MaskIndex(ARingBuffer, ARingBuffer.FWriteIndex - ARingBuffer.FReadIndex);{$POP}end; function SPSC_ReadByte(out ARingBuffer: TSPSCRingBuffer): byte;begin Result := ARingBuffer.FBuffer[SPSC_MaskIndex(ARingBuffer, ARingBuffer.FReadIndex)];{$PUSH}{$Q-} Inc(ARingBuffer.FReadIndex);{$POP}end; procedure SPSC_WriteByte(out ARingBuffer: TSPSCRingBuffer; const AValue: byte);begin ARingBuffer.FBuffer[SPSC_MaskIndex(ARingBuffer, ARingBuffer.FWriteIndex)] := AValue;{$PUSH}{$Q-} Inc(ARingBuffer.FWriteIndex);{$POP}end; end.
EDIT: wrong quote ....
regards,
d.ioannidis:
Hi,
--- Quote from: y.ivanov on October 12, 2022, 07:32:35 pm ---... even the bit-wise and isn't needed because it is achieved naturally by the limited length of the register ...
--- End quote ---
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:
--- Quote from: d.ioannidis on October 12, 2022, 08:03:08 pm ---Hi,
--- Quote from: y.ivanov on October 12, 2022, 07:32:35 pm ---... even the bit-wise and isn't needed because it is achieved naturally by the limited length of the register ...
--- End quote ---
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,
--- End quote ---
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.
Navigation
[0] Message Index
[*] Previous page