Catching Integer Overflows in C | Hacker News Reader

Catching Integer Overflows in C

fefe.de

81 pointsapgwoz22 comments

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.

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.

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.

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

  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;

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.

? 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."

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.

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.

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

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.

That's an interesting perspective, and one that probably works out in practice most of the time. Integration with other libs is the place I'm thinking where it doesn't, but it seems simple, and rather trivial in many cases to do the conversion to signed integers before making the library call. Of course, if you're taking advantage of the extra positive values and need a signed int, I think you're shit out of luck.

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

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.

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.

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.

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

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

x86 only has SIMD instructions for it, IIRC.

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.

And IIRC it's int16_t/uint16_t max.

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

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

Reply on news.ycombinator.com