Detecting signed overflow in C/C++

user_469408 0
Viewed 37321

At first glance, this question may seem like a duplicate of How to detect integer overflow?, however it is actually significantly different.

I've found that while detecting an unsigned integer overflow is pretty trivial, detecting a signed overflow in C/C++ is actually more difficult than most people think.

The most obvious, yet naive, way to do it would be something like:

int add(int lhs, int rhs)
{
 int sum = lhs + rhs;
 if ((lhs >= 0 && sum < rhs) || (lhs < 0 && sum > rhs)) {
  /* an overflow has occurred */
  abort();
 }
 return sum; 
}

The problem with this is that according to the C standard, signed integer overflow is undefined behavior. In other words, according to the standard, as soon as you even cause a signed overflow, your program is just as invalid as if you dereferenced a null pointer. So you can't cause undefined behavior, and then try to detect the overflow after the fact, as in the above post-condition check example.

Even though the above check is likely to work on many compilers, you can't count on it. In fact, because the C standard says signed integer overflow is undefined, some compilers (like GCC) will optimize away the above check when optimization flags are set, because the compiler assumes a signed overflow is impossible. This totally breaks the attempt to check for overflow.

So, another possible way to check for overflow would be:

int add(int lhs, int rhs)
{
 if (lhs >= 0 && rhs >= 0) {
  if (INT_MAX - lhs <= rhs) {
   /* overflow has occurred */
   abort();
  }
 }
 else if (lhs < 0 && rhs < 0) {
  if (lhs <= INT_MIN - rhs) {
   /* overflow has occurred */
   abort();
  }
 }

 return lhs + rhs;
}

This seems more promising, since we don't actually add the two integers together until we make sure in advance that performing such an add will not result in overflow. Thus, we don't cause any undefined behavior.

However, this solution is unfortunately a lot less efficient than the initial solution, since you have to perform a subtract operation just to test if your addition operation will work. And even if you don't care about this (small) performance hit, I'm still not entirely convinced this solution is adequate. The expression lhs <= INT_MIN - rhs seems exactly like the sort of expression the compiler might optimize away, thinking that signed overflow is impossible.

So is there a better solution here? Something that is guaranteed to 1) not cause undefined behavior, and 2) not provide the compiler with an opportunity to optimize away overflow checks? I was thinking there might be some way to do it by casting both operands to unsigned, and performing checks by rolling your own two's-complement arithmetic, but I'm not really sure how to do that.

undefined-behavior integer-overflow signed c c++
13 Answers

Your fundamental problem is that lhs + rhs doesn't do the right thing. But if you're willing to assume a two's complement machine, we can fix that. Suppose you have a function to_int_modular that converts unsigned to int in a way that is guaranteed to be the inverse of conversion from int to unsigned, and it optimizes away to nothing at run time. (See below for how to implement it.)

If you use it to fix the undefined behavior in your original attempt, and also rewrite the conditional to avoid the redundant test of lhs >= 0 and lhs < 0, then you get

int add(int lhs, int rhs)
{
 int sum = to_int_modular((unsigned)lhs + rhs);
 if (lhs >= 0) {
  if (sum < rhs)
    abort();
 } else {
  if (sum > rhs)
   abort();
 }
 return sum; 
}

which should outperform the current top-voted answer, since it has a similar structure but requires fewer arithmetic operations.

(Reorganizing the if shouldn't be necessary, but in tests on godbolt, ICC and MSVC do eliminate the redundant test on their own, but GCC and Clang surprisingly don't.)

If you prefer to compute the result in a wider size and then bounds check, one way to do the bounds check is

 long long sum = (long long)lhs + rhs;
 if ((int)sum != sum)
  abort();

... except that the behavior is undefined on overflow. But you can fix that with the same helper function:

 if (to_int_modular(sum) != sum)

This will probably outperform the current accepted answer on compilers that aren't smart enough to optimize it to a test of the overflow flag.

Unfortunately, testing (visual inspection on godbolt) suggests that GCC, ICC and MSVC do better with the code above than with the code in the accepted answer, but Clang does better with the code in the accepted answer. As usual, nothing is easy.

This approach can only work on architectures where the ranges of int and unsigned are equally large, and the specific implementations below also depend on its being two's complement. Machines not meeting those specs are vanishingly rare, but I'll check for them anyway:

static_assert(INT_MIN + INT_MAX == -1 && UINT_MAX + INT_MIN == INT_MAX);

One way to implement to_int_modular is

inline int to_int_modular(unsigned u) {
    int i;
    memcpy(&i, &u, sizeof(i));
    return i;
}

All major x64 compilers have no trouble optimizing that to nothing, but when optimizations are disabled, MSVC and ICC generate a call to memcpy, which may be a bit slow if you use this function a lot. This implementation also depends on details of the representation of unsigned and int that probably aren't guaranteed by the standard.

Another way is this:

inline int to_int_modular(unsigned u) {
    return u <= INT_MAX ? (int)u : (int)(u - INT_MIN) + INT_MIN;
}

All major x64 compilers optimize that to nothing except ICC, which makes an utter mess of it and every variation that I could think of. ICX does fine, and it appears that Intel is abandoning ICC and moving to ICX, so maybe this problem will fix itself.

user_56707730
Related