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