8

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.

Kaiting Chen
  • 1,076
  • 1
  • 7
  • 12
  • @meaning-matters: Let's assume I want to stick to integer operations only. – Kaiting Chen Jun 26 '15 at 16:02
  • You are correct. Thanks for commenting, I removed my answer. (Very good question) – ryyker Jun 26 '15 at 16:42
  • going through a lot of operations like that may be slower than letting the compiler optimize out the original expression. Did you measure the performance? – phuclv Jun 26 '15 at 16:54
  • @LưuVĩnhPhúc: The problem is that the original expression doesn't work. `volume * 8` might overflow `size_t` before the division by 5 takes place. The compiler can't deal with this directly. – Kaiting Chen Jun 26 '15 at 16:55
  • oops I didn't notice about overflow. But there are also many ways to detect overflow in C – phuclv Jun 26 '15 at 16:58

1 Answers1

6

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.

Kaiting Chen
  • 1,076
  • 1
  • 7
  • 12
gnasher729
  • 51,477
  • 5
  • 75
  • 98
  • size_t is unsigned, so returning -1 is undefined behaviour. I think 0 is better. – Wouter Verhelst Jun 26 '15 at 16:02
  • 4
    @WouterVerhelst: Do you have a citation for that (hint: you don't, it's perfectly defined)? – EOF Jun 26 '15 at 16:03
  • As far as I can tell, `vol2` is unneeded: `volume/5` is already truncated to an integer value. – EOF Jun 26 '15 at 16:06
  • @FredLarson: That question is for C++. For C: http://stackoverflow.com/questions/2760502/question-about-c-behaviour-for-unsigned-integer-underflow (to clarify here, returning `-1` is exactly the same as returning `SIZE_MAX`). – Stephen Canon Jun 26 '15 at 16:11
  • @StephenCanon: You're right. I neglected to check the tag. – Fred Larson Jun 26 '15 at 16:22