1

I was reading about this function: 

int tadd_ok ( int x, int y ) {  
    int sum = x + y;  
    int negative_overflow = x < 0 && y < 0 && sum >= 0;   
    int positive_overflow = x >=0 && y >= 0 && sum < 0;  
    return !negative_overflow && !positive_overflow;
}

This function has a problem when we pass as argument for y the TMin (i.e. the smallest 2's complement).
In this case -y will be -y when passed in i.e. still will be TMin the first condition will show we have negative overflow for values of x that are negative.
Then I read that in fact "x - y does not overflow" in these cases.

My understanding is that the problem of this function is that it does not take into account the corner case of passing the minimum negative number. I can see that it will return a negative_overflow I can not see/understand why that is wrong.
Can anyone help me understand this?

Cratylus
  • 52,998
  • 69
  • 209
  • 339
  • The problem with this function is it tries to detect the overflow *after* it may have occurred. This is wrong as in case of overflow nasal daemons already would have occurred. – ouah Sep 21 '14 at 21:38
  • @ouah:I guess the correct function try to detect before it happens?I don't know what is the difference of these approaches.Besides this erroneous approach, why is the TMin considered not to overflow? – Cratylus Sep 21 '14 at 21:41
  • 1
    The problem is that, as ouah said, the C compiler is trying to screw you over instead of helping. Instead of having signed integers overflow using 2s complement arithmetic and then letting you inspect the resulting sum, many C compilers will assume that an oevrflow can never help and optimize away your overflow check. For more info, see [this question](http://stackoverflow.com/questions/3944505/detecting-signed-overflow-in-c-c) – hugomg Sep 21 '14 at 21:48
  • Yes, the detection has to be done before. Regarding `INT_MIN` I don't really get your point in your question as you are never computing `-y` in `tadd_ok`. – ouah Sep 21 '14 at 21:48
  • @ouah:The problem stems from the fact that the function can be called as: `tadd_ok(x, -y);` to check if `x - y` will overflow. It is the argument passed in that is the problem, i.e. the way it is called – Cratylus Sep 21 '14 at 21:50
  • @Cratylus but it has nothing to do with `tadd_ok` function, if you do something like `-INT_MIN` (note the `-`) you already invoke undefined behavior and there is not much you can do inside the `tadd_ok` function. – ouah Sep 21 '14 at 21:53
  • @ouah:But `-INT_MIN` is `-INT_MIN`.It wraps arround due to asymetry.For some reason I think the point of this example code is to show that `INT_MIN` can not really cause overflow. But I don't understand why – Cratylus Sep 21 '14 at 21:54
  • 1
    @Cratylus `-INT_MIN` does not wrap, it invokes undefined behavior. Signed integer overflow invoke undefined behavior. – ouah Sep 21 '14 at 21:57
  • @ouah:Is this C specific?I mean in CS theory it wraps arround right? Because the range is [-2^31, 2^31-1] so there is no equivalent of -2^31 in the positive numbers so it wraps to one more i.e. to -2^31 – Cratylus Sep 21 '14 at 22:00
  • 1
    Yes, this is C specific and its a pain in the ass. The C standard comes from a time when not every single computer used 2s complement arithmetic so signed overflow is considered undefined behaviour. Unfortunately, this does not mean "unspecified behaviour". Many compiler will do nonsense things when signed overflow happens instead of always overflowing in the same manner. – hugomg Sep 21 '14 at 22:03
  • Yes, C specific. No such behavior in Java for example. In C unsigned integer wraps around but signed integer invokes undefined behavior. It may wrap around, but not always :) Never let signed integer arithmetic overflows in C. – ouah Sep 21 '14 at 22:08
  • To emphasis what @hugomg said you can check out how `gcc` turned a finite loop into an infinite loop due to signed overflow in the question [Why does this loop produce “warning: iteration 3u invokes undefined behavior” and output more than 4 lines?](http://stackoverflow.com/q/24296571/1708801) – Shafik Yaghmour Sep 22 '14 at 12:36
  • @ouah:So in C it does not work like, I see your point.But this example's core point I think is about what should happen if we stick to the core CS theory.The author (I think after your clarifications) erroneously used C to show his example – Cratylus Sep 22 '14 at 16:44

1 Answers1

3

You can not check for signed integer overflow after the fact, you must check before the operation is performed. This is because signed integer overflow in an arithmetic operation is undefined behavior in C and also in C++. Once you have invoked undefined behavior the result of your program becomes unpredictable(see my comment above for one of the most unexpected results I have seen). For C we can see this by going to the draft C99 standard section 6.5 Expressions which says:

If an exceptional condition occurs during the evaluation of an expression (that is, if the result is not mathematically defined or not in the range of representable values for its type), the behavior is undefined.

Cert provides a solid guide on how to prevent signed overflow: INT32-C. Ensure that operations on signed integers do not result in overflow and for additions the document recommends the following method:

#include <limits.h>

void f(signed int si_a, signed int si_b) {
  signed int sum;
  if (((si_b > 0) && (si_a > (INT_MAX - si_b))) ||
      ((si_b < 0) && (si_a < (INT_MIN - si_b)))) {
    /* Handle error */
  } else {
    sum = si_a + si_b;
  }
  /* ... */
}

the document covers all the possible overflow operations and provides a recommendation for each case.

Community
  • 1
  • 1
Shafik Yaghmour
  • 154,301
  • 39
  • 440
  • 740