crypto/bn/asm/x86-gf2m.pl

   1 #!/usr/bin/env perl
   2 #
   3 # ====================================================================
   4 # Written by Andy Polyakov <appro@openssl.org> for the OpenSSL
   5 # project. The module is, however, dual licensed under OpenSSL and
   6 # CRYPTOGAMS licenses depending on where you obtain it. For further
   7 # details see http://www.openssl.org/~appro/cryptogams/.
   8 # ====================================================================
   9 #
  10 # May 2011
  11 #
  12 # The module implements bn_GF2m_mul_2x2 polynomial multiplication used
  13 # in bn_gf2m.c. It's kind of low-hanging mechanical port from C for
  14 # the time being... Except that it has three code paths: pure integer
  15 # code suitable for any x86 CPU, MMX code suitable for PIII and later
  16 # and PCLMULQDQ suitable for Westmere and later. Improvement varies
  17 # from one benchmark and µ-arch to another. Below are interval values
  18 # for 163- and 571-bit ECDH benchmarks relative to compiler-generated
  19 # code:
  20 #
  21 # PIII          16%-30%
  22 # P4            12%-12%
  23 # Opteron       18%-40%
  24 # Core2         19%-44%
  25 # Atom          38%-64%
  26 # Westmere      53%-121%(PCLMULQDQ)/20%-32%(MMX)
  27 # Sandy Bridge  72%-127%(PCLMULQDQ)/27%-23%(MMX)
  28 #
  29 # Note that above improvement coefficients are not coefficients for
  30 # bn_GF2m_mul_2x2 itself. For example 120% ECDH improvement is result
  31 # of bn_GF2m_mul_2x2 being >4x faster. As it gets faster, benchmark
  32 # is more and more dominated by other subroutines, most notably by
  33 # BN_GF2m_mod[_mul]_arr...
  34
  35 $0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
  36 push(@INC,"${dir}","${dir}../../perlasm");
  37 require "x86asm.pl";
  38
  39 $output = pop;
  40 open STDOUT,">$output";
  41
  42 &asm_init($ARGV[0],$0,$x86only = $ARGV[$#ARGV] eq "386");
  43
  44 $sse2=0;
  45 for (@ARGV) { $sse2=1 if (/-DOPENSSL_IA32_SSE2/); }
  46
  47 &external_label("OPENSSL_ia32cap_P") if ($sse2);
  48
  49 $a="eax";
  50 $b="ebx";
  51 ($a1,$a2,$a4)=("ecx","edx","ebp");
  52
  53 $R="mm0";
  54 @T=("mm1","mm2");
  55 ($A,$B,$B30,$B31)=("mm2","mm3","mm4","mm5");
  56 @i=("esi","edi");
  57
  58                                         if (!$x86only) {
  59 &function_begin_B("_mul_1x1_mmx");
  60         &sub    ("esp",32+4);
  61          &mov   ($a1,$a);
  62          &lea   ($a2,&DWP(0,$a,$a));
  63          &and   ($a1,0x3fffffff);
  64          &lea   ($a4,&DWP(0,$a2,$a2));
  65          &mov   (&DWP(0*4,"esp"),0);
  66          &and   ($a2,0x7fffffff);
  67         &movd   ($A,$a);
  68         &movd   ($B,$b);
  69          &mov   (&DWP(1*4,"esp"),$a1);  # a1
  70          &xor   ($a1,$a2);              # a1^a2
  71         &pxor   ($B31,$B31);
  72         &pxor   ($B30,$B30);
  73          &mov   (&DWP(2*4,"esp"),$a2);  # a2
  74          &xor   ($a2,$a4);              # a2^a4
  75          &mov   (&DWP(3*4,"esp"),$a1);  # a1^a2
  76         &pcmpgtd($B31,$A);              # broadcast 31st bit
  77         &paddd  ($A,$A);                # $A<<=1
  78          &xor   ($a1,$a2);              # a1^a4=a1^a2^a2^a4
  79          &mov   (&DWP(4*4,"esp"),$a4);  # a4
  80          &xor   ($a4,$a2);              # a2=a4^a2^a4
  81         &pand   ($B31,$B);
  82         &pcmpgtd($B30,$A);              # broadcast 30th bit
  83          &mov   (&DWP(5*4,"esp"),$a1);  # a1^a4
  84          &xor   ($a4,$a1);              # a1^a2^a4
  85         &psllq  ($B31,31);
  86         &pand   ($B30,$B);
  87          &mov   (&DWP(6*4,"esp"),$a2);  # a2^a4
  88         &mov    (@i[0],0x7);
  89          &mov   (&DWP(7*4,"esp"),$a4);  # a1^a2^a4
  90          &mov   ($a4,@i[0]);
  91         &and    (@i[0],$b);
  92         &shr    ($b,3);
  93         &mov    (@i[1],$a4);
  94         &psllq  ($B30,30);
  95         &and    (@i[1],$b);
  96         &shr    ($b,3);
  97         &movd   ($R,&DWP(0,"esp",@i[0],4));
  98         &mov    (@i[0],$a4);
  99         &and    (@i[0],$b);
 100         &shr    ($b,3);
 101         for($n=1;$n<9;$n++) {
 102                 &movd   (@T[1],&DWP(0,"esp",@i[1],4));
 103                 &mov    (@i[1],$a4);
 104                 &psllq  (@T[1],3*$n);
 105                 &and    (@i[1],$b);
 106                 &shr    ($b,3);
 107                 &pxor   ($R,@T[1]);
 108
 109                 push(@i,shift(@i)); push(@T,shift(@T));
 110         }
 111         &movd   (@T[1],&DWP(0,"esp",@i[1],4));
 112         &pxor   ($R,$B30);
 113         &psllq  (@T[1],3*$n++);
 114         &pxor   ($R,@T[1]);
 115
 116         &movd   (@T[0],&DWP(0,"esp",@i[0],4));
 117         &pxor   ($R,$B31);
 118         &psllq  (@T[0],3*$n);
 119         &add    ("esp",32+4);
 120         &pxor   ($R,@T[0]);
 121         &ret    ();
 122 &function_end_B("_mul_1x1_mmx");
 123                                         }
 124
 125 ($lo,$hi)=("eax","edx");
 126 @T=("ecx","ebp");
 127
 128 &function_begin_B("_mul_1x1_ialu");
 129         &sub    ("esp",32+4);
 130          &mov   ($a1,$a);
 131          &lea   ($a2,&DWP(0,$a,$a));
 132          &lea   ($a4,&DWP(0,"",$a,4));
 133          &and   ($a1,0x3fffffff);
 134         &lea    (@i[1],&DWP(0,$lo,$lo));
 135         &sar    ($lo,31);               # broadcast 31st bit
 136          &mov   (&DWP(0*4,"esp"),0);
 137          &and   ($a2,0x7fffffff);
 138          &mov   (&DWP(1*4,"esp"),$a1);  # a1
 139          &xor   ($a1,$a2);              # a1^a2
 140          &mov   (&DWP(2*4,"esp"),$a2);  # a2
 141          &xor   ($a2,$a4);              # a2^a4
 142          &mov   (&DWP(3*4,"esp"),$a1);  # a1^a2
 143          &xor   ($a1,$a2);              # a1^a4=a1^a2^a2^a4
 144          &mov   (&DWP(4*4,"esp"),$a4);  # a4
 145          &xor   ($a4,$a2);              # a2=a4^a2^a4
 146          &mov   (&DWP(5*4,"esp"),$a1);  # a1^a4
 147          &xor   ($a4,$a1);              # a1^a2^a4
 148         &sar    (@i[1],31);             # broardcast 30th bit
 149         &and    ($lo,$b);
 150          &mov   (&DWP(6*4,"esp"),$a2);  # a2^a4
 151         &and    (@i[1],$b);
 152          &mov   (&DWP(7*4,"esp"),$a4);  # a1^a2^a4
 153         &mov    ($hi,$lo);
 154         &shl    ($lo,31);
 155         &mov    (@T[0],@i[1]);
 156         &shr    ($hi,1);
 157
 158          &mov   (@i[0],0x7);
 159         &shl    (@i[1],30);
 160          &and   (@i[0],$b);
 161         &shr    (@T[0],2);
 162         &xor    ($lo,@i[1]);
 163
 164         &shr    ($b,3);
 165         &mov    (@i[1],0x7);            # 5-byte instruction!?
 166         &and    (@i[1],$b);
 167         &shr    ($b,3);
 168          &xor   ($hi,@T[0]);
 169         &xor    ($lo,&DWP(0,"esp",@i[0],4));
 170         &mov    (@i[0],0x7);
 171         &and    (@i[0],$b);
 172         &shr    ($b,3);
 173         for($n=1;$n<9;$n++) {
 174                 &mov    (@T[1],&DWP(0,"esp",@i[1],4));
 175                 &mov    (@i[1],0x7);
 176                 &mov    (@T[0],@T[1]);
 177                 &shl    (@T[1],3*$n);
 178                 &and    (@i[1],$b);
 179                 &shr    (@T[0],32-3*$n);
 180                 &xor    ($lo,@T[1]);
 181                 &shr    ($b,3);
 182                 &xor    ($hi,@T[0]);
 183
 184                 push(@i,shift(@i)); push(@T,shift(@T));
 185         }
 186         &mov    (@T[1],&DWP(0,"esp",@i[1],4));
 187         &mov    (@T[0],@T[1]);
 188         &shl    (@T[1],3*$n);
 189         &mov    (@i[1],&DWP(0,"esp",@i[0],4));
 190         &shr    (@T[0],32-3*$n);        $n++;
 191         &mov    (@i[0],@i[1]);
 192         &xor    ($lo,@T[1]);
 193         &shl    (@i[1],3*$n);
 194         &xor    ($hi,@T[0]);
 195         &shr    (@i[0],32-3*$n);
 196         &xor    ($lo,@i[1]);
 197         &xor    ($hi,@i[0]);
 198
 199         &add    ("esp",32+4);
 200         &ret    ();
 201 &function_end_B("_mul_1x1_ialu");
 202
 203 # void bn_GF2m_mul_2x2(BN_ULONG *r, BN_ULONG a1, BN_ULONG a0, BN_ULONG b1, BN_ULONG b0);
 204 &function_begin_B("bn_GF2m_mul_2x2");
 205 if (!$x86only) {
 206         &picmeup("edx","OPENSSL_ia32cap_P");
 207         &mov    ("eax",&DWP(0,"edx"));
 208         &mov    ("edx",&DWP(4,"edx"));
 209         &test   ("eax",1<<23);          # check MMX bit
 210         &jz     (&label("ialu"));
 211 if ($sse2) {
 212         &test   ("eax",1<<24);          # check FXSR bit
 213         &jz     (&label("mmx"));
 214         &test   ("edx",1<<1);           # check PCLMULQDQ bit
 215         &jz     (&label("mmx"));
 216
 217         &movups         ("xmm0",&QWP(8,"esp"));
 218         &shufps         ("xmm0","xmm0",0b10110001);
 219         &pclmulqdq      ("xmm0","xmm0",1);
 220         &mov            ("eax",&DWP(4,"esp"));
 221         &movups         (&QWP(0,"eax"),"xmm0");
 222         &ret    ();
 223
 224 &set_label("mmx",16);
 225 }
 226         &push   ("ebp");
 227         &push   ("ebx");
 228         &push   ("esi");
 229         &push   ("edi");
 230         &mov    ($a,&wparam(1));
 231         &mov    ($b,&wparam(3));
 232         &call   ("_mul_1x1_mmx");       # a1·b1
 233         &movq   ("mm7",$R);
 234
 235         &mov    ($a,&wparam(2));
 236         &mov    ($b,&wparam(4));
 237         &call   ("_mul_1x1_mmx");       # a0·b0
 238         &movq   ("mm6",$R);
 239
 240         &mov    ($a,&wparam(1));
 241         &mov    ($b,&wparam(3));
 242         &xor    ($a,&wparam(2));
 243         &xor    ($b,&wparam(4));
 244         &call   ("_mul_1x1_mmx");       # (a0+a1)·(b0+b1)
 245         &pxor   ($R,"mm7");
 246         &mov    ($a,&wparam(0));
 247         &pxor   ($R,"mm6");             # (a0+a1)·(b0+b1)-a1·b1-a0·b0
 248
 249         &movq   ($A,$R);
 250         &psllq  ($R,32);
 251         &pop    ("edi");
 252         &psrlq  ($A,32);
 253         &pop    ("esi");
 254         &pxor   ($R,"mm6");
 255         &pop    ("ebx");
 256         &pxor   ($A,"mm7");
 257         &movq   (&QWP(0,$a),$R);
 258         &pop    ("ebp");
 259         &movq   (&QWP(8,$a),$A);
 260         &emms   ();
 261         &ret    ();
 262 &set_label("ialu",16);
 263 }
 264         &push   ("ebp");
 265         &push   ("ebx");
 266         &push   ("esi");
 267         &push   ("edi");
 268         &stack_push(4+1);
 269
 270         &mov    ($a,&wparam(1));
 271         &mov    ($b,&wparam(3));
 272         &call   ("_mul_1x1_ialu");      # a1·b1
 273         &mov    (&DWP(8,"esp"),$lo);
 274         &mov    (&DWP(12,"esp"),$hi);
 275
 276         &mov    ($a,&wparam(2));
 277         &mov    ($b,&wparam(4));
 278         &call   ("_mul_1x1_ialu");      # a0·b0
 279         &mov    (&DWP(0,"esp"),$lo);
 280         &mov    (&DWP(4,"esp"),$hi);
 281
 282         &mov    ($a,&wparam(1));
 283         &mov    ($b,&wparam(3));
 284         &xor    ($a,&wparam(2));
 285         &xor    ($b,&wparam(4));
 286         &call   ("_mul_1x1_ialu");      # (a0+a1)·(b0+b1)
 287
 288         &mov    ("ebp",&wparam(0));
 289                  @r=("ebx","ecx","edi","esi");
 290         &mov    (@r[0],&DWP(0,"esp"));
 291         &mov    (@r[1],&DWP(4,"esp"));
 292         &mov    (@r[2],&DWP(8,"esp"));
 293         &mov    (@r[3],&DWP(12,"esp"));
 294
 295         &xor    ($lo,$hi);
 296         &xor    ($hi,@r[1]);
 297         &xor    ($lo,@r[0]);
 298         &mov    (&DWP(0,"ebp"),@r[0]);
 299         &xor    ($hi,@r[2]);
 300         &mov    (&DWP(12,"ebp"),@r[3]);
 301         &xor    ($lo,@r[3]);
 302         &stack_pop(4+1);
 303         &xor    ($hi,@r[3]);
 304         &pop    ("edi");
 305         &xor    ($lo,$hi);
 306         &pop    ("esi");
 307         &mov    (&DWP(8,"ebp"),$hi);
 308         &pop    ("ebx");
 309         &mov    (&DWP(4,"ebp"),$lo);
 310         &pop    ("ebp");
 311         &ret    ();
 312 &function_end_B("bn_GF2m_mul_2x2");
 313
 314 &asciz  ("GF(2^m) Multiplication for x86, CRYPTOGAMS by <appro\@openssl.org>");
 315
 316 &asm_finish();
 317
 318 close STDOUT;