-
-
Save mcejp/719d3485b04cfcf82e8a8734957da06a to your computer and use it in GitHub Desktop.
// Background: https://www.snellman.net/blog/archive/2016-12-13-ring-buffers/ | |
// Variant with indices modulo 2*capacity as suggested by dizzy57 and Aristotle Pagaltzis | |
size_t read; | |
size_t write; | |
mask(val) { return val % array.capacity; } | |
inc(index) { return wrap(index + 1); } | |
push(val) { assert(!full()); array[mask(write)] = val; write = inc(write); } | |
shift() { assert(!empty()); ret = array[mask(read)]; read = inc(read); return ret; } | |
empty() { return read == write; } | |
full() { return size() == array.capacity; } | |
size() { return wrap(write - read); } | |
free() { return array.capacity - size(); } | |
// If you can assure power-of-2 capacity | |
wrap(val) { return val % (array.capacity * 2); } | |
// If you can NOT assure power-of-2 capacity | |
size_t wrap(intptr_t val) { | |
val = val % (intptr_t)(capacity * 2); | |
if (val < 0) { | |
val += capacity * 2; | |
} | |
return val; | |
} | |
// Additional operations | |
read(data_out, count) { | |
count = min(count, size()); | |
run = min(count, array.capacity - mask(read)); | |
rem = count - run; | |
memcpy(data_out, array + mask(read), run); | |
memcpy(data_out + run, array, rem); | |
read = wrap(read + count); | |
return count; | |
} | |
write(data, count) { | |
count = min(count, array.capacity - size()); | |
run = min(count, array.capacity - mask(write)); | |
rem = count - run; | |
memcpy(array + mask(write), data, run); | |
memcpy(array, data + run, rem); | |
write = wrap(write + count); | |
return count; | |
} |
Assume capacity is 3 and the size_t is something small and workable for our example, say uint8. So we work with integer mod 256 and we wrap() at 2x3 = 6.
Now if the head is at 1 and the tail at 5, our size() should be 1. But 0 - 5 is congruent to 252 mod 256 and Wrap(252) is 0.
I thus fear size() is buggy.
@etiennemlb You are making the tacit assumption that wrap
takes a size_t
argument. Which is not unreasonable, but it will indeed break if the buffer size is not 2**N. Ideally wrap
would just take a signed argument, and this indeed gives the correct result in Python, where the %
operator always returns a number with the same sign as the denominator, so (-4) % 6 == 2
In C/C++/Java, they made the unfortunate choice of having %
return a value with the sign of the numerator. Therefore, (-4) % 6
will still be -4, which is not helpful here. I might not have been aware of this at the time of writing.
Thanks for pointing this out. I'll be back with a fix. Let's have the most robust implementation of a Ring buffer with Array + two indices mod 2N on the internet :)
I think this is the endless debate of modulo over remainder, with knuth advocating for the definition you gave and the C guys (and thus by transitivity, a whole bunch of language) choosing the over zealous (?) solution.
The modulo operator on signed ints is what we would like for the purpose above. Instead C gives us the remainder.
To be fair, the C % operator (remainder) is what the hardware gives us on x86. I'm not aware of a modulo operator (as in not the remainder operator for signed integers) that is available in the x86 ISA.
@etiennemlb I updated the code a few days ago and forgot to ping you. I would be grateful for your feedback!
Sorry I worked on an overwritable FIFO when the situation is more complicated, I must have mingled things....
https://github.com/hathach/tinyusb/blob/master/src/common/tusb_fifo.h