Ring buffer with Array + two indices mod 2N

ring_buffer.c

// 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;
}

I think size() should be { return mask(write - read); }

I think size() should be { return mask(write - read); }

@HiFiPhile nope, that's why you do mod 2N in the first place, this way you could never arrive to size() == capacity()

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

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!