Best way to detect integer overflow in C/C?

Information which may be useful on this subject: Chapter 5 of "Secure Coding in C and C++" by Seacord informit.com/content/images/0321335724/s... SafeInt classes for C blogs.msdn.com/david_leblanc/archive/200... codeplex.com/SafeInt IntSafe library for C: blogs.msdn.com/michael_howard/archive/20....

Information which may be useful on this subject: Chapter 5 of "Secure Coding in C and C++" by Seacord informit.com/content/images/0321335724/s... SafeInt classes for C++ blogs.msdn.com/david_leblanc/archive/200... codeplex.com/SafeInt IntSafe library for C: blogs.msdn.com/michael_howard/archive/20....

Seacord's Secure Coding is a great resource, but don't use IntegerLib. See blog.regehr. Org/archives/593.

– noloader Sep 26 at 0:53.

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>=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).

7 and of course you could rename highestOneBitPosition to log :) – Oliver Hallam Jan 25 '10 at 18:14 4 Yes, it's the same operation as log2, but that wouldn't necessarily be as obvious to someone who didn't have a mathematical background. – Head Geek Feb 4 '10 at 20:19 1 Doesn't this algorithm underestimate the safe answers? 2^31 + 0 would detect as unsafe since highestOneBitPosition(2^31) = 32.(2^32 - 1) * 1 would detect as unsafe since 32 + 1 > 32.1 ^ 100 would detect as unsafe since 1 * 100 > 32.

– clahey Apr 15 '10 at 17:51 Not quite sure where you're coming from. Those functions are meant to determine whether a mathematical operation is safe from overflowing. Unless the code explicitly checks for a zero or one multiplicand, (2^32 - 1) * 1 can't be determined as safe without doing the entire operation.

– Head Geek Apr 16 '10 at 2:30 "highestOneBitPosition" - count leading zeros?Publib.boulder.ibm. Com/infocenter/aix/v6r1/index. Jsp?

Topic=/… – noloader Jun 19 at 5:54.

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 ( be > ULONG_MAX / a ) // a * be would overflow.

4 ...or use numeric_limits::max() – Jonas Gulle Oct 13 '08 at 23:15 2 Don't forget to handle a=0 -- division breaks then. – Thelema Jul 3 '09 at 14:24 @Thelema: "Don't forget to handle a=0" - and INT_MIN / -1. – noloader Jun 19 at 5:56.

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.

1 Heh... what I didn't say was that I'm asking this question in preparation for writing a program to solve a problem with larger numbers, in which I'm already using long long int. Since long long int is not (allegedly) in the C++ standard, I stuck with the 32-bit version to avoid confusion. – Chris Johnson Oct 13 '08 at 23:59 Ah - that would be a subtly different question then.

;-) – Andrew Edgecombe Oct 14 '08 at 0:30.

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 int a = ; int x = ; a += x; /* UB */ if (a = 0) && (a > INT_MAX - x)) /* `a + x` would overflow */; if ((x.

4 Unsigned integers don't strictly overflow in C++ either (ISO/IEC 14882:2003 3.9.1.4). My use of 'overflow' in the question was the more colloquial meaning, intended to include the well-defined wrapping of unsigned types, since I was interested in unsigned ints representing mathematical positive integers, not positive integers mod 2^32 (or 2^64). The distinction between overflow as a deviation from mathematical infinite-sized integer behaviour, and overflow as an undefined behaviour in the language seems rarely to be made explicit.

– Chris Johnson Oct 3 '09 at 18:47 That test doesn't need to be x >= 0 - x > 0 will suffice (if x == 0, then x + a can't overflow for obvious reasons). – caf Apr 26 '10 at 0:20.

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: cs.umd.edu/class/spring2003/cmsc311/Note... 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.

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.

Maybe it varies: -ftrapv seems to work fine using GCC 4.3.4 on a Cygwin box. There's an example at stackoverflow. Com/questions/5005379/… – Nate Kohl Feb 15 at 15:45.

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.

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.

For unsigned integers, just check that the result is bigger than one of the arguments : unsigned int r, a, b; r = a+b; if (r =0; if (s == (b>=0) && s! = (r>=0)) { // overflow }.

Warning: gcc can optimize away an overflow check when compiling with -O2 The option -Wall will give you a warning in some cases like if (a + be I think the compiler should issue a warning by default when making an optimization that relies on overflow not occurring. The present situation allows the compiler to optimize away an overflow check, which is unacceptable in my opinion.

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.

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

Inline assembly ties you to one architecture and causes the compiler to shutdown many optimizations. It should be generally avoided. – James Curran Oct 13 '08 at 23:15.

I just noticed that there are a lot of referrals from this page to 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.

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).

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

Except that you can't override operators for builtin types. You'd need to write a class for that and rewrite client code to use it. – Blaisorblade May 1 '10 at 17:02.

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.

2 inline assembler is no C/C++ feature and platform independent. On x86 you can use the into instruction istead of branches btw. – Nils Pipenbrinck Oct 13 '08 at 23:32.

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 be ) { double dc; dc = pow( a, be ); if ( dc.

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 =, 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).

Although it has been two years, I felt I might as well add my penithworth for a really fast way to detect overflow for at least additions, which might give a lead for multiplication, division and power-of The idea is that exactly because the processor will just let the value wrap back to zero and that C/C++ is to abstracted from any specific processor, you can: uint32_t x, y; uint32_t value = x + y; bool overflow = value.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.