Catching Integer Overflows in C

http://www.fefe.de/intof.html

by apgwoz • 15 years ago

81 22 15 years ago

I'm not a fan of this approach - did you notice that addition, for instance, just returns 1(!) instead of overflowing?

The proper way to do this is still

    if (a > UINT_MAX - b)
        errx(1, "Too large.");
    a += b;

and variants.

apgwoz2• 15 years ago

And for INT_MIN? The c-faq (http://c-faq.com/misc/sd26.html) says that this approach fails in that case. Is your suggestion to just avoid INT_MIN? If so, that works. :)

JoachimSchipper2• 15 years ago

To be honest, my suggestion is to avoid signed integers, or at least negative signed integers (beyond perhaps -1 for signalling errors). I find that I almost never need them, and unsigned integers are much nicer to work with.

rplnt• 15 years ago

I've used this approach in one of my school assignments. The result (macros) weren't so nice but I think they've worked. It was few years back so I'm not so sure now.

https://github.com/rplnt/personal/blob/master/C/fractions/zl...

Estragon• 15 years ago

The return value of 1 is strange, but superficial. It's easy enough to replace that with arbitrary behavior. The advantage of the approach in the OP is that it is more agnostic about the types involved, leading to more flexible code.

jensnockert• 15 years ago

Or use saturating arithmetic, loads of common processors have instructions for that.

carbonica• 15 years ago

x86 only has SIMD instructions for it, IIRC.

onan_barbarian• 15 years ago

You do recall correctly.

Further, x86 only provides these SIMD operations on 8-bit and 16-bit quantities, not on 32-bit or 64-bit quantities (although all these types can be packed into a SIMD register and operated on with at least some operations; for example regular, non-saturating add).

SSE has a menagerie of non-orthogonal oddities, unfortunately; this is only one of them.

adobriyan• 15 years ago

And IIRC it's int16_t/uint16_t max.

tedunangst2• 15 years ago

Yes, "don't use C" can solve lots of problems, but it doesn't solve them when using C.

praptak2• 15 years ago

This (I mean lack of overflow checking in arithmetic) is one of the areas where C shows its weakness as a sort of a lowest common denominator assembly. If at all possible (portability be damned) I'd prefer to crank out the inline __asm__ and get the access to the overflow flags of the underlying CPU.

tptacek• 15 years ago

How much does that _really_ help you? The C code to detect an overflow given the context (adding, multiplying, subtracting, &c) isn't difficult. The reason integer overflows are pernicious is that they're easy to miss.

praptak2• 15 years ago

Valid point. But it's not about the difficulty - the macros are probably easier. I just simply don't like the pattern of the compiler discarding the information and the macros (indirectly) reconstructing it.

If you need the information then the straightforward thing to do is not to discard it in the first place.

1amzave• 15 years ago

I'm kind of surprised GCC doesn't have a __builtin_* extension for overflow detection. It seems like a pretty natural fit among a lot of the other ones.

...and after a quick bit of googling, it appears this has been discussed by the GCC devs semi-recently: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48580

jerf• 15 years ago

How is an abs function that can return a negative value not a flat-out bug‽ Seriously? It may still not be cool to end up with true_abs(MIN_INT) - 1 rather than the "real" value, but at least it won't be negative. That's really bad.

rcfox• 15 years ago

Either way, you're going to have the incorrect number. When debugging, I'd rather have something that is very incorrect rather than having a mysterious off-by-one error.

Edit: The C99 standard acknowledges that abs(INT_MIN) isn't representable, so using abs(INT_MIN) is undefined.

ahmetalpbalkan• 15 years ago

Microsoft has a c++ SafeInt library that does this.

http://msdn.microsoft.com/en-us/library/dd570023.aspx http://safeint.codeplex.com/

haberman2• 15 years ago

The basis of this article is incorrect if you care about standards compliance. Signed integer overflow is undefined in C, so checking "a+b<a" is not a correct way to test for overflow of signed integers. And this statement, while it may be true in some implementations, cannot be assumed in general:

> Since the addition operation in the CPU is agnostic to whether the integer is signed or unsigned, the same goes for signed integers.

tedunangst2• 15 years ago

? Unless the article was changed, it says "solution 2 does not work, because in the C language, when adding a number to a pointer or to a signed integer, overflow is undefined."

haberman2• 15 years ago

I'm glad that this is corrected later on, but that contradicts the statements made at the beginning of the article:

> So, if you want to add two integers a and b (b >= 0), the easiest way to find out if that overflows is to check whether a+b<a (or b; some people think you have to check against min(a,b), but that is unnecessary).

This statement is untrue, as is the other statement I quoted.

iam• 15 years ago

  volatile int b = 23;
  if (a + b < b) overflow;

Tada. That's how you get around the GCC optimization issue in practice. I suppose though this doesn't suite as a proper answer since overflowing as a result of adding two signed integers results in undefined behavior..

The solution is to cast the integers to unsigned and then do the overflow check. The following two standard sections should demonstrate the standards-compliance of the code below.

> ANSI C99 6.2.5 Types #9

> A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type.

> ANSI C99 6.3.1.3 Signed and unsigned integers #2

> Otherwise, if the new type is unsigned, the value is converted by repeatedly adding or subtracting one more than the maximum value that can be represented in the new type until the value is in the range of the new type.

---------

  // shift the MSB to the LSB
  #define signof(x) (!!((x) & INT_MIN))

  int x, y;

  // bits stay the same thanks to 6.3.1.3
  unsigned int a = (unsigned int) x;
  unsigned int b = (unsigned int) y;

  unsigned int sign_a = signof(a);
  unsigned int sign_b = signof(b);

  // a+b should have the same sign as a and b, otherwise an overflow/underflow has occurred
  // note that a+b is well defined for unsigned ints according to 6.2.5 #9
  if (sign_a == sign_b && signof(a+b) != sign_a) overflow;

The code for checking overflow on unsigned ints is trivial:

  unsigned int a, b;
  if (a + b < a) overflow;

Catching Integer Overflows in C

Related Stories