> From: Sean Kelly <sean@invisibleduck.org>
> 
> bearophile wrote:
> > Another little story for people that think the
> multi-precision integers are mostly good for cryptography:
> >
> http://dobbscodetalk.com/index.php?option=com_content&task=view&id=614&Itemid=
> 
> Avoiding computation overflow is never a bad thing :)

 There's an idea...

 I have a feature request. Please give me heads or tails on what you think. implementing it hopefully won't break any code, and i don't know of a single compiler/language the is protected against this.

 When using math operations hopefully the compiler can take the types and increase them by 1 (32 to 64bit), and then when you do comparisons immediately following those you can compare against the larger non-overflow version vs the one that can overflow. (but if you don't do a compare, it would probably only keep the 32bit version anyways).

 Perhaps a new type of int for non-overflowable?

 Internally (Assembly) it would look something like this. (Intel Syntax, forgive me if my code is off, it's been about 8 years)

 if (a+b > 0){
...
}
--becomes
 xor edx,edx        ;clear upper 32bits
 mov eax, [esp-12]  ;int a
 add eax, [esp-8]   ;int b
 adc edx, 0         ;add with carry

--then following the compare

 cmp edx,0
 jg inside_if  ;jump if greater than 0. More likely?
 jb outside_if ;below 0, so it's false
 cmp eax,0
 jbe outside_if
inside_if:
;{...}
outside_if:


--
 Following that note, if you multiply the largest size against itself, the number of bits consumed only doubles. (32bits becomes no more than 64bits) and immediately following with compares and such, this can keep the overflow from happening.

 Any thoughts?

 Era

Reply to Era,


> Perhaps a new type of int for non-overflowable?
> 

uint.max * uint.max * uint.max

Era Scarecrow wrote:
>> From: Sean Kelly <sean@invisibleduck.org>
>>
>> bearophile wrote:
>>> Another little story for people that think the
>> multi-precision integers are mostly good for cryptography:
>> http://dobbscodetalk.com/index.php?option=com_content&task=view&id=614&Itemid=
>>
>> Avoiding computation overflow is never a bad thing :)
> 
>  There's an idea...
> 
>  I have a feature request. Please give me heads or tails on what you think. implementing it hopefully won't break any code, and i don't know of a single compiler/language the is protected against this.
> 
>  When using math operations hopefully the compiler can take the types and increase them by 1 (32 to 64bit), and then when you do comparisons immediately following those you can compare against the larger non-overflow version vs the one that can overflow. (but if you don't do a compare, it would probably only keep the 32bit version anyways).

Actually that's (sort of) implemented in most hardware (X86, for instance). The overflow flag is set if you get an int overflow (signed ints). The carry flag is set if you get a uint overflow.

There are several branch instructions which make use of it.

>  Internally (Assembly) it would look something like this.
>  if (a+b > 0){
> ...
> }
> --becomes
>  xor edx,edx        ;clear upper 32bits
>  mov eax, [esp-12]  ;int a
>  add eax, [esp-8]   ;int b
>  adc edx, 0         ;add with carry

> 
> --then following the compare 
> 
>  cmp edx,0
>  jg inside_if  ;jump if greater than 0. More likely?
>  jb outside_if ;below 0, so it's false
>  cmp eax,0
>  jbe outside_if
> inside_if:
> ;{...}
> outside_if:

mov eax, [esp-12];
add eax, [esp-8];
jo error;
jbe outside_if;

error: throw IntegerOverflowException.

Could be added in debug builds, at least.