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

(date of last change: March 3, 2008 16:52 )