1

How can I rewrite this test so that the test itself won't overflow? Can I use the fact that (size_t) -1 is odd (power of 2 minus 1)?

size_t size;
...
if ((size * 3U + 1U) / 2U > (size_t) -1) {
    /* out of address space */
}

EDIT: Sorry, my question title was wrong. I don't want to check if (n * 3 + 1) / 2 will overflow, but if n / 2 * 3 + n % 2 * 2 will. I changed the title. Thanks for your correct replies to a bad question.

potrzebie
  • 1,768
  • 1
  • 12
  • 25

1 Answers1

2

Here is a solution for this precise formula, the reasoning behind it won't work for the general case, but for the given one, and many others, it does.

Overflow happens precisely when size*3 + 1 is not representable, unsigned integer divisions can never overflow. So, your condition should be size*3 + 1 > max_value. Here, max_value is the unsigned value with all bits set, which you generated with (size_t)-1.

The +1 can simply moved to the right side without invoking overflow since max_value is definitely greater than 1, so we arrive at size*3 > max_value - 1. Likewise, *3 can be moved without invoking overflow. So what you need to check is size > (max_value - 1)/3.

Please note that, contrary to what I said originally (mea culpa), size > max_value/3 does not work because max_value is a multiple of 3 when the integer type is unsigned (the condition is that there is an even number of bits available for positive numbers). So, the when size is 0x5555, we get 3*size = 0xffff and 3*size + 1 = 0x0000. Sorry for mixing that up.

cmaster - reinstate monica
  • 38,891
  • 9
  • 62
  • 106
  • _Signed_ integer division _can_ overflow (e.g. `INT_MIN / -1`), but that's obviously irrelevant here. – Joshua Green Oct 27 '13 at 01:24
  • Also, why can't `max_value` be a multiple of 3? In fact, since `size_t` must contain an even number of bits, `max_value` _must_ be a multiple of 3. – Joshua Green Oct 27 '13 at 01:27
  • @JoshuaGreen Nitpick: `size_t` need not have an even number of bits, but otherwise I agree with you. – pburka Oct 27 '13 at 03:05
  • @JoshuaGreen I'm very sorry, I mixed `2^n` up with `2^n-1`, so my reasoning about indivisibility with 3 was plain wrong. Since I could not delete the answer anymore, I have completely reworked the second part. Hope it's correct now. Thanks also for pointing out that `INT_MIN/-1` does overflow; even though it's not relevant here, and the only case in which overflow can occur, it's worth being precise, so I changed my assertion about integer division to _unsigned_ integer division. – cmaster - reinstate monica Oct 27 '13 at 08:10