www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Not just for cryptography

reply bearophile <bearophileHUGS lycos.com> writes:
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=

Bye,
bearophile
Jul 27 2008
next sibling parent Sean Kelly <sean invisibleduck.org> writes:
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 :) Sean
Jul 28 2008
prev sibling next sibling parent reply Era Scarecrow <rtcvb32 yahoo.com> writes:
 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
Jul 30 2008
next sibling parent BCS <ao pathlink.com> writes:
Reply to Era,


 Perhaps a new type of int for non-overflowable?
 
uint.max * uint.max * uint.max
Jul 30 2008
prev sibling parent Don <nospam nospam.com.au> writes:
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.
Aug 01 2008
prev sibling next sibling parent reply Era Scarecrow <rtcvb32 yahoo.com> writes:
 From: Don <nospam nospam.com.au>
 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
:)
<Snip>
 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.
Sounds promising. From what i know in C, that is never brought up, so if i wanted to handle a overflow or a carry flag i'd have to use a long long. (For a unsigned unlimited Integer math library i made, but has problems) Would it be possible, to have a couple operators or a special inline functions we can use to be able to use those possible overflows? I'd rather not ASM in lines where it won't be portable :( int carry, a = int.umax; b = a + a; if (Register.Overflow || Register.Carry){...} //possible? math_overflow{...} //or math_carryOn{...} //or?? ASM(Intel) { jno notOverFlow ... } notOverFlow: //or?? long long carry, a = int.umax; b = a + a; if (b>int.umax) {...} Era
Aug 04 2008
parent bearophile <bearophileHUGS lycos.com> writes:
Era Scarecrow Wrote:
...

An idea is for DMD to:
- when in release mode perform as now
- When not in release mode use 4 byte numbers (or 8 byte on 64 bit CPUs) to
compute operations among integral values represented in 1 or 2 bytes, use 8
bytes to perform operations among integral values represented in 4 bytes, and
use 16 bytes to perform operations performed among 8 byte integral values. And
control if the result can fit in the right range. I think Delphi works almost
this way. In Delphi you also can define types of integer intervals:
Smally = 1 .. 25;
so the compiler (if not in release mode) controls if values are in those bounds
too.
(In D you can perform something similar adding pre/post that test if that value
is in the interval, but such control is done less often and you have to do it
yourself manually in many parts of the code, so you don't spot the bug as soon
you go out of the bounds).
In some points the compiler doesn't need to control the bounds because it can
infer the value will not go out of bounds.

Bye,
bearophile
Aug 04 2008
prev sibling parent Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
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=
 
 Bye,
 bearophile
That's what happens when people use "undefined" behavior as an ambiguous expression that can mean both "illegal" behavior, and "unspecified in some aspects but valid" behavior. Illegal behavior should be called illegal behavior, period. (http://lists.puremagic.com/pipermail/digitalmars-d/2008-April/036814.html) -- Bruno Medeiros - Software Developer, MSc. in CS/E graduate http://www.prowiki.org/wiki4d/wiki.cgi?BrunoMedeiros#D
Aug 11 2008