Best way to detect integer overflow in C/C++

Question

I was writing a program in C++ to find all solutions of a^b = c (a to the power of b), where a, b and c together use all the digits 0-9 exactly once. The program looped over values of a and b, and ran a digit-counting routine each time on a, b and a^b to check if the digits condition was satisfied.

However, spurious solutions can be generated when a^b overflows the integer limit. I ended up checking for this using code like:

unsigned long b, c, c_test;
...
c_test=c*b;         // Possible overflow
if (c_test/b != c) {/* There has been an overflow*/}
else c=c_test;      // No overflow

Is there a better way of testing for overflow? I know that some chips have an internal flag that is set when overflow occurs, but I've never seen it accessed through C or C++.

Answer 1

Inline assembly lets you check the overflow bit directly. If you are going to be using C++, you really should learn assembly.

Answer 2

The simplest way is to convert your unsigned longs into unsigned long longs, do your multiplication, and compare the result to 0x100000000LL.

You'll probably find that this is more efficient than doing the division as you've done in your example.

Oh, and it'll work in both C and C++ (as you've tagged the question with both).

---

Just been taking a look at the glibc manual. There's a mention of an integer overflow trap (FPE_INTOVF_TRAP) as part of SIGFPE. That would be ideal, apart from the nasty bits in the manual:

FPE_INTOVF_TRAP Integer overflow (impossible in a C program unless you enable overflow trapping in a hardware-specific fashion).

A bit of a shame really.

Answer 3

You can't access the overflow flag from C/C++.

Some compilers allow you to insert trap instructions into the code. On GCC the option is -ftrapv (but I have to admit that I've never used it. Will check it after posting).

The only portable and compiler independent thing you can do is to check for overflows on your own. Just like you did in your example.

Edit:

Just checked: -ftrapv seems to do nothing on x86 using the lastest GCC. Guess it's a left over from an old version or specific to some other architecture. I had expected the compiler to insert an INTO opcode after each addition. Unfortunately it does not do this.

Answer 4

Some compilers provide access to the integer overflow flag in the CPU which you could then test but this isn't standard.

You could also test for the possibility of overflow before you perform the multiplication:

if ( b > ULONG_MAX / a ) // a * b would overflow

Answer 5

A clean way to do it would be to override all operators (+ and * in particular) and check for an overflow before perorming the operations.

Answer 6

You can't access the overflow flag from C/C++.

I don't agree with this. You could write some inline asm and use a jo (jump overflow) instruction assuming you are on x86 to trap the overflow. Of course you code would no longer be portable to other architectures.

look at info as and info gcc.

Answer 7

Information which may be useful on this subject:

Chapter 5 of "Secure Coding in C and C++" by Seacord

• http://www.informit.com/content/images/0321335724/samplechapter/seacord_ch05.pdf

SafeInt classes for C++

• http://blogs.msdn.com/david_leblanc/archive/2008/09/30/safeint-3-on-codeplex.aspx
• http://www.codeplex.com/SafeInt

IntSafe library for C:

• http://blogs.msdn.com/michael_howard/archive/2006/02/02/523392.aspx

Answer 8

Am I on the wrong track here or does XOR not generate overflows as it is a logical operation?

Therefore if you are getting overflows, the problem must lie with your values of a and b?

Answer 9

There is a way to determine whether an operation is likely to overflow, using the positions of the most-significant one-bits in the operands and a little basic binary-math knowledge.

For addition, any two operands will result in (at most) one bit more than the largest operand's highest one-bit. For example:

bool addition_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
    return (a_bits<32 && b_bits<32);
}

For multiplication, any two operands will result in (at most) the sum of the bits of the operands. For example:

bool multiplication_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
    return (a_bits+b_bits<=32);
}

Similarly, you can estimate the maximum size of the result of a to the power of b like this:

bool exponentiation_is_safe(uint32_t a, uint32_t b) {
    size_t a_bits=highestOneBitPosition(a);
    return (a_bits*b<=32);
}

(Substitute the number of bits for your target integer, of course.)

I'm not sure of the fastest way to determine the position of the highest one-bit in a number, here's a brute-force method:

size_t highestOneBitPosition(uint32_t a) {
    size_t bits=0;
    while (a!=0) {
        ++bits;
        a>>=1;
    };
    return bits;
}

It's not perfect, but that'll give you a good idea whether any two numbers could overflow before you do the operation. I don't know whether it would be faster than simply checking the result the way you suggested, because of the loop in the highestOneBitPosition function, but it might (especially if you knew how many bits were in the operands beforehand).

Answer 10

If you have a datatype which is bigger than the one you want to test (say a you do a 32-bit add and you have a 64-bit type). Then this will detect if an overflow occured. My example is for an 8-bit add. But can be scaled up.

uint8_t x, y;   /* give these values */
const uint16_t data16   = x + y;
const bool carry     = (data16 > 0xff);
const bool overflow     = ((~(x ^ y)) & (x ^ data16) & 0x80);

It is based on the concepts explained on this page: http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Comb/overflow.html

For a 32-bit example, 0xff becomes 0xffffffff and 0x80 becomes 0x80000000 and finally uint16_t becomes a uint64_t.

NOTE: this catches integer addition/subtraction overflows, and I realized that your question involves powers. In which case, division is likely the best approach. This is commonly a way that calloc implementations make sure that the params don't overflow as they are multiplied to get the final size.

Answer 11

Calculate the results with doubles. They have 15 significant digits. Your rquirement has a hard upperbound on c of 10^8 - it can have at most 8 digits. Hence, the result will be precise if it's in range, and it will not overflow otherwise.

Answer 12

@MSalters: Good idea.

If the integer calculation is required (for precision), but floating point is available, you could do something like:

uint64_t foo( uint64_t a, uint64_t b ) {
    double   dc;

    dc = pow( a, b );

    if ( dc < UINT_MAX ) {
       return ( powu64( a, b ) );
    }
    else {
      // overflow
    }
}

Answer 13

I just noticed that there are a lot of referrals from this page to www.CodePlex.com/SafeInt, and given that much of this code seems to be cross-platform, I thought it might be of interest that SafeInt has now been ported to compile nicely on gcc 4.3.2 - see the planned release 3.0.12p for more details. Not 100% baked, but stay tuned.

Answer 14

Here's a great book chapter on the issue: CERT C Secure Coding - 'Ensure the operations on signed integers do not result in overflow.

It gives a two's complement version that is architecture dependent version and an architecture independent version.

Answer 15

CERT has developed a new approach to detecting and reporting signed integer overflow, unsigned integer wrapping, and integer truncation using the "as-if" infinitely ranged (AIR) integer model. CERT has published a technical report describing the model and produced a working prototype based on GCC 4.4.0 and GCC 4.5.0.

The AIR integer model either produces a value equivalent to one that would have been obtained using infinitely ranged integers or results in a runtime constraint violation. Unlike previous integer models, AIR integers do not require precise traps, and consequently do not break or inhibit most existing optimizations.

Answer 16

I see you're using unsigned integers. By definition, in C (don't know about C++), unsigned arithmetic does not overflow ... so, at least for C, your point is moot :)

With signed integers, once there has been overflow, Undefined Behaviour has occurred and your program can do anything (for example: render tests inconclusive).

#include <limits.h>
int a = <something>;
int x = <something>;
a += x;              /* UB */
if (a < 0) {         /* unreliable test */
  /* ... */
}

To create a conforming program you need to test for overflow before generating said overflow. The method can be used with unsigned integers too

#include <limits.h>
int a = <soething>;
int x = <something>;
if ((x >= 0) && (a > INT_MAX - x)) /* `a + x` would overflow */;
if ((x < 0) && (a < INT_MIN - x)) /* `a + x` would underflow */;
/* ... same thing for subtraction, multiplication, and division */

Answer 17

This link points out a solution more general than the one discussed by CERT (it is more general in term of handled types), even if it requires some GCC extensions (I don't know how widely supported they are).

Answer 18

The simple way to test for overflow is to do validation by checking whether the current value is less than the previous value. For example, suppose you had a loop to print the powers of 2:

long lng; int n; for (n = 0; n < 34; ++n) { lng = pow (2, n); printf ("%li\n", lng); }

Adding overflow checking the way that I described results in this:

long signed lng, lng_prev = 0;
int n;
for (n = 0; n < 34; ++n)
  {
    lng = pow (2, n);
    if (lng <= lng_prev)
      {
        printf ("Overflow: %i\n", n);
        /* Do whatever you do in the event of overflow.  */
      }
    printf ("%li\n", lng);
    lng_prev = lng;
  }

It works for unsigned values as well as both positive and negative signed values.

Of course, if you wanted to do something similar for decreasing values instead of increasing values, you would flip the <= sign to make it >=, assuming the behaviour of underflow is the same as the behaviour of overflow. In all honesty, that's about as portable as you'll get without access to a CPU's overflow flag (and that would require inline assembly code, making your code non-portable across implementations anyway).