Last update March 3, 2008

Cmp Integer Overflow Problem

opCmp and Integer overflow

Where is the problem

struct Pair {
    int a;
    int opCmp(Pair rhs) {
        return a-rhs.a;
    }
}
// or simply
int cmp(int a,int b) {
    return a-b;
}

Why this code must not be used? Because of compare function has 3 basic rules it must satisfy:

cmp(a,a)=0
cmp(a,b)=-cmp(b,a)
if cmp(a,b)<0 and cmp(b,c)<0 then cmp(a,c)<0

The third rule is not satisfied with such definition of cmp:

  int a=int.min, b=0, c=1;
  cmp(a,b)=int.min   => a<b
  cmp(b,c)=-1        => b<c
  cmp(a,c)=int.max   => a>c !!!

a<b<c using 3rd rule it must be a<c but we have a>c. So this cmp function can be never used as a compare function.

Why this problem still exist

Because on data used no one found this problem or did not belive his eyes and try to find error elsewhere. It returns valid results for 3/4 of possible input data. If we try check it with usual number 1,2,3,-5,100, and so on. But if we check all possible values we'll find where 1/4 of possible values return wrong result

int.min
+--------0--------+--> a
|0    B  : \    A |
|  0     :   \    |
|    0   :   B \  |
| B    0 :       \|
0........0........0 zero
|\       : 0    B |
|  \ B   :   0    |
|    \   :     0  |
| A    \ :  B    0|
+--------0--------+ int.max
|              
v b

The possible origin

The possible origin of this problem is from assembler language where this operation was succesifully used. Single substraction and we have all information required.

  mov EAX,a
  sub EAX,b
  jz  @equal
  jl  @int_less
  jle @int_less_or_equal
  jg  @int_great
  jge @int_great_or_equal
  jc  @uint_less
  jnc @uint_great_or_equal
  ...

It works because there are more than 32bit of result. Substract operations also change Zero,Carry and Overflow and some other flags in FLAGS register. So we can clearly understand what result we have. Loking on this simplisity anyone want to use it in high level language. But there is no FLAGS register in high level languages, so this scheeme can not be implemented.

What to do

The solution only one. Review and fixup all existing code and documentation.