crypto/bn/asm/x86-mont.pl

   1 #!/usr/bin/env perl
   2
   3 # ====================================================================
   4 # Written by Andy Polyakov <appro@fy.chalmers.se> for the OpenSSL
   5 # project. Rights for redistribution and usage in source and binary
   6 # forms are granted according to the OpenSSL license.
   7 # ====================================================================
   8
   9 # October 2005
  10 #
  11 # This is a "teaser" code, as it can be improved in several ways...
  12 # First of all non-SSE2 path should be implemented (yes, for now it
  13 # performs Montgomery multiplication/convolution only on SSE2-capable
  14 # CPUs such as P4, others fall down to original code). Then inner loop
  15 # can be unrolled and modulo-scheduled to improve ILP and possibly
  16 # moved to 128-bit XMM register bank (though it would require input
  17 # rearrangement and/or increase bus bandwidth utilization). Dedicated
  18 # squaring procedure should give further performance improvement...
  19 # Yet, for being draft, the code improves rsa512 *sign* benchmark by
  20 # 110%(!), rsa1024 one - by 70% and rsa4096 - by 20%:-)
  21
  22 push(@INC,"perlasm","../../perlasm");
  23 require "x86asm.pl";
  24
  25 &asm_init($ARGV[0],$0);
  26
  27 $sse2=0;
  28 for (@ARGV) { $sse2=1 if (/-DOPENSSL_IA32_SSE2/); }
  29
  30 &external_label("OPENSSL_ia32cap_P") if ($sse2);
  31
  32 &function_begin("bn_mul_mont",$sse2?"EXTRN\t_OPENSSL_ia32cap_P:DWORD":"");
  33
  34 $i="ebx";
  35 $j="ecx";
  36 $ap="esi";
  37 $rp="edi";      $bp="edi";              # overlapping variables!!!
  38 $np="edx";
  39 $num="ebp";
  40
  41 $_rp=&DWP(4*0,"esp");                   # stack top layout
  42 $_ap=&DWP(4*1,"esp");
  43 $_bp=&DWP(4*2,"esp");
  44 $_np=&DWP(4*3,"esp");
  45 $_n0=&DWP(4*4,"esp");
  46 $_num=&DWP(4*5,"esp");
  47 $_sp=&DWP(4*6,"esp");
  48 $frame=32;                              # size of above frame rounded up to 16n
  49
  50 $acc0="mm0";                            # mmx register bank layout
  51 $acc1="mm1";
  52 $car0="mm2";
  53 $car1="mm3";
  54 $mul0="mm4";
  55 $mul1="mm5";
  56 $temp="mm6";
  57 $mask="mm7";
  58
  59 if($sse2) {
  60         &picmeup("eax","OPENSSL_ia32cap_P");
  61         &bt     (&DWP(0,"eax"),26);
  62         &jnc    (&label("non_sse2"));
  63
  64         ################################# load argument block...
  65         &mov    ("eax",&wparam(0));     # BN_ULONG *rp
  66         &mov    ("ebx",&wparam(1));     # const BN_ULONG *ap
  67         &mov    ("ecx",&wparam(2));     # const BN_ULONG *bp
  68         &mov    ("edx",&wparam(3));     # const BN_ULONG *np
  69         &mov    ("esi",&wparam(4));     # BN_ULONG n0
  70         &mov    ($num,&wparam(5));      # int num
  71
  72         &mov    ("edi","esp");          # saved stack pointer!
  73         &add    ($num,1);               # extra word on top of tp
  74         &neg    ($num);
  75         &lea    ("esp",&DWP(-$frame,"esp",$num,4));     # alloca($frame+8*($num+1))
  76         &neg    ($num);
  77         &and    ("esp",-1024);          # minimize TLB utilization
  78         &sub    ($num,1);               # num is restored to its original value
  79                                         # and will remain constant from now...
  80
  81         &mov    ($_rp,"eax");           # ... save a copy of argument block
  82         &mov    ($_ap,"ebx");
  83         &mov    ($_bp,"ecx");
  84         &mov    ($_np,"edx");
  85         &mov    ($_n0,"esi");
  86         #&mov   ($_num,$num);           # redundant in sse2 context
  87         &mov    ($_sp,"edi");           # saved stack pointer!
  88
  89         &mov    ("eax",-1);
  90         &movd   ($mask,"eax");          # mask 32 lower bits
  91
  92         &mov    ($ap,$_ap);             # load input pointers
  93         &mov    ($bp,$_bp);
  94         &mov    ($np,$_np);
  95
  96         &xor    ($i,$i);                # i=0
  97         &xor    ($j,$j);                # j=0
  98
  99         &movd   ($mul0,&DWP(0,$bp));            # bp[0]
 100         &movd   ($mul1,&DWP(0,$ap));            # ap[0]
 101         &movd   ($car1,&DWP(0,$np));            # np[0]
 102
 103         &pmuludq($mul1,$mul0);                  # ap[0]*bp[0]
 104         &movq   ($car0,$mul1);
 105         &movq   ($acc0,$mul1);                  # I wish movd worked for
 106         &pand   ($acc0,$mask);                  # inter-register transfers
 107
 108         &pmuludq($mul1,$_n0);                   # *=n0
 109
 110         &pmuludq($car1,$mul1);                  # "t[0]"*np[0]*n0
 111         &paddq  ($car1,$acc0);
 112
 113         &psrlq  ($car0,32);
 114         &psrlq  ($car1,32);
 115
 116         &inc    ($j);                           # j++
 117 &set_label("1st");
 118         &movd   ($acc0,&DWP(0,$ap,$j,4));       # ap[j]
 119         &movd   ($acc1,&DWP(0,$np,$j,4));       # np[j]
 120         &pmuludq($acc0,$mul0);                  # ap[j]*bp[0]
 121         &pmuludq($acc1,$mul1);                  # np[j]*m1
 122
 123         &paddq  ($car0,$acc0);                  # +=c0
 124         &movq   ($acc0,$car0);
 125         &pand   ($acc0,$mask);
 126
 127         &paddq  ($car1,$acc1);                  # +=c1
 128         &paddq  ($car1,$acc0);                  # +=ap[j]*bp[0];
 129         &movd   (&DWP($frame-4,"esp",$j,4),$car1);      # tp[j-1]=
 130
 131         &psrlq  ($car0,32);
 132         &psrlq  ($car1,32);
 133
 134         &lea    ($j,&DWP(1,$j));
 135         &cmp    ($j,$num);
 136         &jl     (&label("1st"));
 137
 138         &paddq  ($car1,$car0);
 139         &movq   (&DWP($frame-4,"esp",$num,4),$car1);
 140
 141         &inc    ($i);                           # i++
 142 &set_label("outer");
 143         &xor    ($j,$j);                        # j=0
 144
 145         &movd   ($mul0,&DWP(0,$bp,$i,4));       # bp[i]
 146         &movd   ($mul1,&DWP(0,$ap));            # ap[0]
 147         &movd   ($temp,&DWP($frame,"esp"));     # tp[0]
 148         &movd   ($car1,&DWP(0,$np));            # np[0]
 149         &pmuludq($mul1,$mul0);                  # ap[0]*bp[i]
 150
 151         &paddq  ($mul1,$temp);                  # +=tp[0]
 152         &movq   ($acc0,$mul1);
 153         &movq   ($car0,$mul1);
 154         &pand   ($acc0,$mask);
 155
 156         &pmuludq($mul1,$_n0);                   # *=n0
 157
 158         &pmuludq($car1,$mul1);
 159         &paddq  ($car1,$acc0);
 160
 161         &psrlq  ($car0,32);
 162         &psrlq  ($car1,32);
 163
 164         &inc    ($j);                           # j++
 165 &set_label("inner");
 166         &movd   ($acc0,&DWP(0,$ap,$j,4));       # ap[j]
 167         &movd   ($acc1,&DWP(0,$np,$j,4));       # np[j]
 168         &movd   ($temp,&DWP($frame,"esp",$j,4));# tp[j]
 169         &pmuludq($acc0,$mul0);                  # ap[j]*bp[i]
 170         &pmuludq($acc1,$mul1);                  # np[j]*m1
 171         &paddq  ($car0,$temp);                  # +=tp[j]
 172         &paddq  ($car0,$acc0);                  # +=c0
 173         &movq   ($acc0,$car0);
 174         &pand   ($acc0,$mask);
 175
 176         &paddq  ($car1,$acc1);                  # +=c1
 177         &paddq  ($car1,$acc0);                  # +=ap[j]*bp[i]+tp[j]
 178         &movd   (&DWP($frame-4,"esp",$j,4),$car1);      # tp[j-1]=
 179
 180         &psrlq  ($car0,32);
 181         &psrlq  ($car1,32);
 182
 183         &lea    ($j,&DWP(1,$j));                # j++
 184         &cmp    ($j,$num);
 185         &jl     (&label("inner"));
 186
 187         &movd   ($temp,&DWP($frame,"esp",$num,4));
 188         &paddq  ($car1,$car0);
 189         &paddq  ($car1,$temp);
 190         &movq   (&DWP($frame-4,"esp",$num,4),$car1);
 191
 192         &lea    ($i,&DWP(1,$i));                # i++
 193         &cmp    ($i,$num);
 194         &jl     (&label("outer"));
 195
 196         &emms   ();                             # done with mmx bank
 197
 198         &mov    ("esi",&DWP($frame,"esp",$num,4));# load upmost overflow bit
 199         &mov    ($rp,$_rp);                     # load result pointer
 200                                                 # [$ap and $bp are zapped]
 201         &xor    ($i,$i);                        # i=0
 202         &lea    ($j,&DWP(-1,$num));             # j=num-1
 203         &cmp    ("esi",0);                      # clears CF unconditionally
 204         &jnz    (&label("sub"));
 205         &mov    ("eax",&DWP($frame,"esp",$j,4));
 206         &cmp    ("eax",&DWP(0,$np,$j,4));       # tp[num-1]-np[num-1]?
 207         &jae    (&label("sub"));                # if taken CF is cleared
 208 &set_label("copy");
 209         &mov    ("eax",&DWP($frame,"esp",$j,4));
 210         &mov    (&DWP(0,$rp,$j,4),"eax");       # rp[i]=tp[i]
 211         &mov    (&DWP($frame,"esp",$j,4),$j);   # zap temporary vector
 212         &dec    ($j);
 213         &jge    (&label("copy"));
 214         &jmp    (&label("exit_sse2"));
 215
 216 &set_label("sub",4);
 217         &mov    ("eax",&DWP($frame,"esp",$i,4));
 218         &sbb    ("eax",&DWP(0,$np,$i,4));
 219         &mov    (&DWP(0,$rp,$i,4),"eax");       # rp[i]=tp[i]-np[i]
 220         &lea    ($i,&DWP(1,$i));                # i++
 221         &dec    ($j);                           # doesn't affect CF!
 222         &jge    (&label("sub"));
 223         &lea    ($j,&DWP(-1,$num));             # j=num-1
 224         &sbb    ("esi",0);                      # esi holds upmost overflow bit
 225         &jc     (&label("copy"));
 226 &set_label("zap");
 227         &mov    (&DWP($frame,"esp",$j,4),$i);   # zap temporary vector
 228         &dec    ($j);
 229         &jge    (&label("zap"));
 230
 231 &set_label("exit_sse2");
 232         &mov    ("esp",$_sp);           # pull saved stack pointer
 233         &mov    ("eax",1);
 234         &jmp    (&label("leave"));
 235 &set_label("non_sse2");
 236 }
 237
 238         &xor    ("eax","eax");  # zero signals "not implemented [yet]"
 239
 240 &set_label("leave");
 241 &function_end("bn_mul_mont");
 242
 243 &asm_finish();