delphi2007 教程

delphi2007 教程

首页 新随笔 联系 聚合 管理
  1013 Posts :: 0 Stories :: 28 Comments :: 0 Trackbacks
大整数加法优化 Delphi / Windows SDK/API
http://www.delphi2007.net/DelphiBase/html/delphi_20061217100254136.html
改自FGInt单元,将原来的  
   
  TGInt   =   Record  
              Sign   :   TSign;  
              Number   :   Array   Of   Int64;  
  定义做了修改.又用汇编做了部分优化,效率提升应该在40%左右.  
  还有没有更大的优化空间  
   
  Unit   FBigInt;  
   
  Interface  
   
  Uses   Windows,   SysUtils,   Controls,   Math;  
   
  Type  
        TCompare   =   (Lt,   St,   Eq,   Er);  
        TSign   =   (negative,   positive);  
        TBInt   =   Record  
              Sign   :   TSign;  
              Number   :   Array   Of   Longword;  
        End;  
   
        Function   FBIntNew(Size:int64):TBInt;  
        Procedure   FBIntDestroy(Var   FBInt   :   TBInt);  
        Function   FBIntAdd(Const   FBInt1,   FBInt2   :   TBInt):TBInt;  
        Function   FBIntCompareAbs(Const   FBInt1,   FBInt2   :   TBInt)   :   TCompare;  
  Implementation  
   
  {$H+}  
  Function   FBIntNew(Size:int64):TBInt;  
  begin  
      SetLength(Result.Number,Size);  
      ZeroMemory(Result.Number,Size*8);  
      Result.Number[0]:=Size-1;  
      Result.Sign:=positive;  
  end;  
   
  Procedure   FBIntDestroy(Var   FBInt   :   TBInt);  
  Begin  
        FBInt.Number   :=   Nil;  
  End;  
   
  Function   FBIntAdd(Const   FBInt1,   FBInt2   :   TBInt):TBInt;  
  Var  
        i,   size1,   size2,   size   :   longint;  
        rest   :   integer;  
        Trest   :   int64;  
  Begin  
      If   FBInt1.Number[0]   <   FBInt2.Number[0]   Then   Result:=FBIntAdd(FBInt2,   FBInt1)   Else  
      Begin  
          If   FBInt1.Sign   =   FBInt2.Sign   Then  
          Begin  
              SetLength(Result.Number,   FBInt1.Number[0]   +   2);  
              //rest   :=   0;  
              asm  
                  clc  
                  mov   eax,[esi+$04]  
                  mov   ebp,[eax]  
                  test   ebp,ebp  
                  jle   @LoopOneEnd  
                  mov   ecx,$00000001  
                  @LoopOne:  
                  mov   eax,[ebx+$04]  
                  mov   eax,[eax+ecx*4]  
                  mov   edx,[esi+$04]  
                  adc   eax,[edx+ecx*4]  
                  mov   edx,[edi+$04]  
                  mov   [edx+ecx*4],eax  
                  inc   ecx  
                  dec   ebp  
                  jnz   @LoopOne  
                  @LoopOneEnd:  
                  pushf  
                  mov   eax,[esi+$04]  
                  mov   ebp,[eax]  
                  mov   eax,[ebx+$04]  
                  sub   ebp,[eax]  
                  popf  
                  test   ebp,ebp  
                  jle   @LoopOneEnd  
                  jnc   @looptwoend  
                  mov   eax,[ebx+$04]  
                  mov   eax,[eax+ecx*4]  
                  adc   eax,$0  
                  dec   ebp  
                  jnz   @LoopOneEnd  
                  @looptwoend:  
              end;  
              size   :=   FBInt1.Number[0]+1;  
  //             For   i   :=   1   To   FBInt2.Number[0]   Do  
  //             Begin  
  //                 Trest   :=   FBInt1.Number[i]   +   FBInt2.Number[i]   +   rest;  
  //                 Result.Number[i]   :=   Trest   And   4294967295;  
  //                 rest   :=   Trest   Shr   32;  
  //             End;  
  //             For   i   :=   (FBInt2.Number[0]   +   1)   To   FBInt1.Number[0]   Do  
  //             Begin  
  //                 Trest   :=   FBInt1.Number[i]   +   rest;  
  //                 Result.Number[i]   :=   Trest   And   4294967295;  
  //                 rest   :=   Trest   Shr   32;  
  //             End;  
  //             size   :=   FBInt1.Number[0]+1;  
  //             Result.Number[size]   :=   rest;  
              While   (Result.Number[size]   =   0)   And   (size   >   1)   Do   size   :=   size   -   1;  
              If   size   <=   FBInt1.Number[0]   Then   SetLength(Result.Number   ,   size   +   1);  
              Result.Number[0]   :=   size   ;  
              Result.Sign   :=   FBInt1.Sign;  
          End  
          Else  
          Begin  
              If   FBIntCompareAbs(FBInt2,   FBInt1)   =   Lt   Then   Result:=FBIntAdd(FBInt2,   FBInt1)  
              Else  
              Begin  
                  SetLength(Result.Number,   FBInt1.Number[0]   +   1);  
                  rest   :=   0;  
                  asm  
                      clc  
                      mov   eax,[esi+$04]  
                      mov   ebp,[eax]  
                      test   ebp,ebp  
                      jle   @LoopOneEnd  
                      mov   ecx,$00000001  
                      @LoopOne:  
                      mov   eax,[ebx+$04]  
                      mov   eax,[eax+ecx*4]  
                      mov   edx,[esi+$04]  
                      SBB   eax,[edx+ecx*4]  
                      mov   edx,[edi+$04]  
                      mov   [edx+ecx*4],eax  
                      inc   ecx  
                      dec   ebp  
                      jnz   @LoopOne  
                      @LoopOneEnd:  
                      pushf  
                      mov   eax,[esi+$04]  
                      mov   ebp,[eax]  
                      mov   eax,[ebx+$04]  
                      sub   ebp,[eax]  
                      popf  
                      test   ebp,ebp  
                      jle   @LoopOneEnd  
                      jnc   @looptwoend  
                      mov   eax,[ebx+$04]  
                      mov   eax,[eax+ecx*4]  
                      SBB   eax,$0  
                      dec   ebp  
                      jnz   @LoopOneEnd  
                      @looptwoend:  
                  end;  
  //                 For   i   :=   1   To   FBInt2.Number[0]   Do  
  //                 Begin  
  //                     Trest   :=   FBInt1.Number[i]   -   FBInt2.Number[i]   +   rest;  
  //                     Result.Number[i]   :=   Trest   And   4294967295;  
  //                     If   (FBInt1.Number[i]   >   FBInt2.Number[i])   Then   rest   :=   0   Else   rest   :=   -1;  
  //                 End;  
  //                 For   i   :=   (FBInt2.Number[0]   +   1)   To   FBInt1.Number[0]   Do  
  //                 Begin  
  //                     Trest   :=   FBInt1.Number[i]   +   rest;  
  //                     Result.Number[i]   :=   Trest   And   4294967295;  
  //                     If   (FBInt1.Number[i]   >   FBInt2.Number[i])   Then   rest   :=   0   Else   rest   :=   -1;  
  //                 End;  
                  size   :=   FBInt1.Number[0];  
                  While   (Result.Number[size]   =   0)   And   (size   >   1)   Do   size   :=   size   -   1;  
                  If   size   <=   FBInt1.Number[0]   Then   SetLength(Result.Number   ,   size   +   1);  
                  Result.Number[0]   :=   size   ;  
                  Result.Sign   :=   FBInt1.Sign;  
              End;  
          End;  
      End;  
  end;  
   
  //   Compare   2   FBInts   in   absolute   value,   returns  
  //   Lt   if   FBInt1   >   FBInt2,   St   if   FBInt1   <   FBInt2,   Eq   if   FBInt1   =   FBInt2,  
  //   Er   otherwise  
   
  Function   FBIntCompareAbs(Const   FBInt1,   FBInt2   :   TBInt)   :   TCompare;  
  Var  
        size1,   size2,   i   :   longint;  
  Begin  
        FBIntCompareAbs   :=   Er;  
        size1   :=   FBInt1.Number[0];  
        size2   :=   FBInt2.Number[0];  
        If   size1   >   size2   Then   FBIntCompareAbs   :=   Lt   Else  
              If   size1   <   size2   Then   FBIntCompareAbs   :=   St   Else  
              Begin  
                    i   :=   size2;  
                    While   (FBInt1.Number[i]   =   FBInt2.Number[i])   And   (i   >   1)   Do   i   :=   i   -   1;  
                    If   FBInt1.Number[i]   =   FBInt2.Number[i]   Then   FBIntCompareAbs   :=   Eq   Else  
                          If   FBInt1.Number[i]   <   FBInt2.Number[i]   Then   FBIntCompareAbs   :=   St   Else  
                                If   FBInt1.Number[i]   >   FBInt2.Number[i]   Then   FBIntCompareAbs   :=   Lt;  
              End;  
  End;  
  End  
 

注释掉的部分是被ASM替代掉的原代码

自己顶下  
 

支持  
  虽然用处好像不大。^_^

呵呵,主要是因为最近在研究RSA加密,可是里面使用FGInt大整数运算单元效率太低,所以打算重写一下,看能不能提高效率

posted on 2008-10-14 16:34 delphi2007 阅读(123) 评论(0)  编辑 收藏 引用
只有注册用户登录后才能发表评论。