Difference (last change)
(
Author,
normal page display)
Changed: 29c29
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 compare a function.
|
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.
|
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.