I need to take a size_t volume and calculate this result in a size_t:
size_t next = (volume * 8 + 3) / 5
If this result would overflow a size_t then next should be zero. The problem is of course that volume * 8 + 3 can overflow while the entire result fits in a size_t.
At the moment I am splitting out the last 4 bits of volume and performing the multiplication, addition, and division separately. My question is: Can I do better than what I have so far if there is no type larger than size_t?
size_t next_volume(size_t volume) {
// check if the numerator will overflow size_t
if (volume > (SIZE_MAX - 3) / 8) {
size_t lower, upper;
// multiply lower 4 bits by 8 and add 3
lower = ((volume & 0xF) * 8) + 3;
// downshift the rest and multiply by 8
upper = (volume >> 4) * 8;
// divide upper remainder and lower by 5
lower = ((upper % 5 << 4) + lower) / 5;
// divide upper by 5
upper = upper / 5;
// ensure the sum will not overflow size_t
if (upper + (lower >> 4) > SIZE_MAX >> 4)
return 0;
return (upper << 4) + lower;
} else return (volume * 8 + 3) / 5;
}
There might be some errors in that code. I haven't put it through extensive testing yet but I believe all the main ideas are there.
Let vol1 = volume % 5, vol2 = volume - vol1. vol2 is divisible by 5, therefore mathematically (vol2 * 8) / 5 = (vol2 / 5) * 8, so you get the correct result as
size_t vol1 = volume % 5;
size_t vol2 = volume - vol1;
size_t result = (vol2 / 5) * 8 + (vol1 * 8 + 3) / 5
Obviously you will get an overflow if the result doesn't fit into size_t, but not if there is an overflow anywhere in the calculation. Since you multiply by 8/5, in case of an overflow the result will be about 0.6 * volume < volume, so you can return
return result < volume ? (size_t) -1 : result;
which is surely better than returning 0.