crypto/openssl/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 &asm_init($ARGV[0],$0,$x86only = $ARGV[$#ARGV] eq "386");
  40
  41 $sse2=0;
  42 for (@ARGV) { $sse2=1 if (/-DOPENSSL_IA32_SSE2/); }
  43
  44 &external_label("OPENSSL_ia32cap_P") if ($sse2);
  45
  46 $a="eax";
  47 $b="ebx";
  48 ($a1,$a2,$a4)=("ecx","edx","ebp");
  49
  50 $R="mm0";
  51 @T=("mm1","mm2");
  52 ($A,$B,$B30,$B31)=("mm2","mm3","mm4","mm5");
  53 @i=("esi","edi");
  54
  55                                         if (!$x86only) {
  56 &function_begin_B("_mul_1x1_mmx");
  57         &sub    ("esp",32+4);
  58          &mov   ($a1,$a);
  59          &lea   ($a2,&DWP(0,$a,$a));
  60          &and   ($a1,0x3fffffff);
  61          &lea   ($a4,&DWP(0,$a2,$a2));
  62          &mov   (&DWP(0*4,"esp"),0);
  63          &and   ($a2,0x7fffffff);
  64         &movd   ($A,$a);
  65         &movd   ($B,$b);
  66          &mov   (&DWP(1*4,"esp"),$a1);  # a1
  67          &xor   ($a1,$a2);              # a1^a2
  68         &pxor   ($B31,$B31);
  69         &pxor   ($B30,$B30);
  70          &mov   (&DWP(2*4,"esp"),$a2);  # a2
  71          &xor   ($a2,$a4);              # a2^a4
  72          &mov   (&DWP(3*4,"esp"),$a1);  # a1^a2
  73         &pcmpgtd($B31,$A);              # broadcast 31st bit
  74         &paddd  ($A,$A);                # $A<<=1
  75          &xor   ($a1,$a2);              # a1^a4=a1^a2^a2^a4
  76          &mov   (&DWP(4*4,"esp"),$a4);  # a4
  77          &xor   ($a4,$a2);              # a2=a4^a2^a4
  78         &pand   ($B31,$B);
  79         &pcmpgtd($B30,$A);              # broadcast 30th bit
  80          &mov   (&DWP(5*4,"esp"),$a1);  # a1^a4
  81          &xor   ($a4,$a1);              # a1^a2^a4
  82         &psllq  ($B31,31);
  83         &pand   ($B30,$B);
  84          &mov   (&DWP(6*4,"esp"),$a2);  # a2^a4
  85         &mov    (@i[0],0x7);
  86          &mov   (&DWP(7*4,"esp"),$a4);  # a1^a2^a4
  87          &mov   ($a4,@i[0]);
  88         &and    (@i[0],$b);
  89         &shr    ($b,3);
  90         &mov    (@i[1],$a4);
  91         &psllq  ($B30,30);
  92         &and    (@i[1],$b);
  93         &shr    ($b,3);
  94         &movd   ($R,&DWP(0,"esp",@i[0],4));
  95         &mov    (@i[0],$a4);
  96         &and    (@i[0],$b);
  97         &shr    ($b,3);
  98         for($n=1;$n<9;$n++) {
  99                 &movd   (@T[1],&DWP(0,"esp",@i[1],4));
 100                 &mov    (@i[1],$a4);
 101                 &psllq  (@T[1],3*$n);
 102                 &and    (@i[1],$b);
 103                 &shr    ($b,3);
 104                 &pxor   ($R,@T[1]);
 105
 106                 push(@i,shift(@i)); push(@T,shift(@T));
 107         }
 108         &movd   (@T[1],&DWP(0,"esp",@i[1],4));
 109         &pxor   ($R,$B30);
 110         &psllq  (@T[1],3*$n++);
 111         &pxor   ($R,@T[1]);
 112
 113         &movd   (@T[0],&DWP(0,"esp",@i[0],4));
 114         &pxor   ($R,$B31);
 115         &psllq  (@T[0],3*$n);
 116         &add    ("esp",32+4);
 117         &pxor   ($R,@T[0]);
 118         &ret    ();
 119 &function_end_B("_mul_1x1_mmx");
 120                                         }
 121
 122 ($lo,$hi)=("eax","edx");
 123 @T=("ecx","ebp");
 124
 125 &function_begin_B("_mul_1x1_ialu");
 126         &sub    ("esp",32+4);
 127          &mov   ($a1,$a);
 128          &lea   ($a2,&DWP(0,$a,$a));
 129          &lea   ($a4,&DWP(0,"",$a,4));
 130          &and   ($a1,0x3fffffff);
 131         &lea    (@i[1],&DWP(0,$lo,$lo));
 132         &sar    ($lo,31);               # broadcast 31st bit
 133          &mov   (&DWP(0*4,"esp"),0);
 134          &and   ($a2,0x7fffffff);
 135          &mov   (&DWP(1*4,"esp"),$a1);  # a1
 136          &xor   ($a1,$a2);              # a1^a2
 137          &mov   (&DWP(2*4,"esp"),$a2);  # a2
 138          &xor   ($a2,$a4);              # a2^a4
 139          &mov   (&DWP(3*4,"esp"),$a1);  # a1^a2
 140          &xor   ($a1,$a2);              # a1^a4=a1^a2^a2^a4
 141          &mov   (&DWP(4*4,"esp"),$a4);  # a4
 142          &xor   ($a4,$a2);              # a2=a4^a2^a4
 143          &mov   (&DWP(5*4,"esp"),$a1);  # a1^a4
 144          &xor   ($a4,$a1);              # a1^a2^a4
 145         &sar    (@i[1],31);             # broardcast 30th bit
 146         &and    ($lo,$b);
 147          &mov   (&DWP(6*4,"esp"),$a2);  # a2^a4
 148         &and    (@i[1],$b);
 149          &mov   (&DWP(7*4,"esp"),$a4);  # a1^a2^a4
 150         &mov    ($hi,$lo);
 151         &shl    ($lo,31);
 152         &mov    (@T[0],@i[1]);
 153         &shr    ($hi,1);
 154
 155          &mov   (@i[0],0x7);
 156         &shl    (@i[1],30);
 157          &and   (@i[0],$b);
 158         &shr    (@T[0],2);
 159         &xor    ($lo,@i[1]);
 160
 161         &shr    ($b,3);
 162         &mov    (@i[1],0x7);            # 5-byte instruction!?
 163         &and    (@i[1],$b);
 164         &shr    ($b,3);
 165          &xor   ($hi,@T[0]);
 166         &xor    ($lo,&DWP(0,"esp",@i[0],4));
 167         &mov    (@i[0],0x7);
 168         &and    (@i[0],$b);
 169         &shr    ($b,3);
 170         for($n=1;$n<9;$n++) {
 171                 &mov    (@T[1],&DWP(0,"esp",@i[1],4));
 172                 &mov    (@i[1],0x7);
 173                 &mov    (@T[0],@T[1]);
 174                 &shl    (@T[1],3*$n);
 175                 &and    (@i[1],$b);
 176                 &shr    (@T[0],32-3*$n);
 177                 &xor    ($lo,@T[1]);
 178                 &shr    ($b,3);
 179                 &xor    ($hi,@T[0]);
 180
 181                 push(@i,shift(@i)); push(@T,shift(@T));
 182         }
 183         &mov    (@T[1],&DWP(0,"esp",@i[1],4));
 184         &mov    (@T[0],@T[1]);
 185         &shl    (@T[1],3*$n);
 186         &mov    (@i[1],&DWP(0,"esp",@i[0],4));
 187         &shr    (@T[0],32-3*$n);        $n++;
 188         &mov    (@i[0],@i[1]);
 189         &xor    ($lo,@T[1]);
 190         &shl    (@i[1],3*$n);
 191         &xor    ($hi,@T[0]);
 192         &shr    (@i[0],32-3*$n);
 193         &xor    ($lo,@i[1]);
 194         &xor    ($hi,@i[0]);
 195
 196         &add    ("esp",32+4);
 197         &ret    ();
 198 &function_end_B("_mul_1x1_ialu");
 199
 200 # void bn_GF2m_mul_2x2(BN_ULONG *r, BN_ULONG a1, BN_ULONG a0, BN_ULONG b1, BN_ULONG b0);
 201 &function_begin_B("bn_GF2m_mul_2x2");
 202 if (!$x86only) {
 203         &picmeup("edx","OPENSSL_ia32cap_P");
 204         &mov    ("eax",&DWP(0,"edx"));
 205         &mov    ("edx",&DWP(4,"edx"));
 206         &test   ("eax",1<<23);          # check MMX bit
 207         &jz     (&label("ialu"));
 208 if ($sse2) {
 209         &test   ("eax",1<<24);          # check FXSR bit
 210         &jz     (&label("mmx"));
 211         &test   ("edx",1<<1);           # check PCLMULQDQ bit
 212         &jz     (&label("mmx"));
 213
 214         &movups         ("xmm0",&QWP(8,"esp"));
 215         &shufps         ("xmm0","xmm0",0b10110001);
 216         &pclmulqdq      ("xmm0","xmm0",1);
 217         &mov            ("eax",&DWP(4,"esp"));
 218         &movups         (&QWP(0,"eax"),"xmm0");
 219         &ret    ();
 220
 221 &set_label("mmx",16);
 222 }
 223         &push   ("ebp");
 224         &push   ("ebx");
 225         &push   ("esi");
 226         &push   ("edi");
 227         &mov    ($a,&wparam(1));
 228         &mov    ($b,&wparam(3));
 229         &call   ("_mul_1x1_mmx");       # a1·b1
 230         &movq   ("mm7",$R);
 231
 232         &mov    ($a,&wparam(2));
 233         &mov    ($b,&wparam(4));
 234         &call   ("_mul_1x1_mmx");       # a0·b0
 235         &movq   ("mm6",$R);
 236
 237         &mov    ($a,&wparam(1));
 238         &mov    ($b,&wparam(3));
 239         &xor    ($a,&wparam(2));
 240         &xor    ($b,&wparam(4));
 241         &call   ("_mul_1x1_mmx");       # (a0+a1)·(b0+b1)
 242         &pxor   ($R,"mm7");
 243         &mov    ($a,&wparam(0));
 244         &pxor   ($R,"mm6");             # (a0+a1)·(b0+b1)-a1·b1-a0·b0
 245
 246         &movq   ($A,$R);
 247         &psllq  ($R,32);
 248         &pop    ("edi");
 249         &psrlq  ($A,32);
 250         &pop    ("esi");
 251         &pxor   ($R,"mm6");
 252         &pop    ("ebx");
 253         &pxor   ($A,"mm7");
 254         &movq   (&QWP(0,$a),$R);
 255         &pop    ("ebp");
 256         &movq   (&QWP(8,$a),$A);
 257         &emms   ();
 258         &ret    ();
 259 &set_label("ialu",16);
 260 }
 261         &push   ("ebp");
 262         &push   ("ebx");
 263         &push   ("esi");
 264         &push   ("edi");
 265         &stack_push(4+1);
 266
 267         &mov    ($a,&wparam(1));
 268         &mov    ($b,&wparam(3));
 269         &call   ("_mul_1x1_ialu");      # a1·b1
 270         &mov    (&DWP(8,"esp"),$lo);
 271         &mov    (&DWP(12,"esp"),$hi);
 272
 273         &mov    ($a,&wparam(2));
 274         &mov    ($b,&wparam(4));
 275         &call   ("_mul_1x1_ialu");      # a0·b0
 276         &mov    (&DWP(0,"esp"),$lo);
 277         &mov    (&DWP(4,"esp"),$hi);
 278
 279         &mov    ($a,&wparam(1));
 280         &mov    ($b,&wparam(3));
 281         &xor    ($a,&wparam(2));
 282         &xor    ($b,&wparam(4));
 283         &call   ("_mul_1x1_ialu");      # (a0+a1)·(b0+b1)
 284
 285         &mov    ("ebp",&wparam(0));
 286                  @r=("ebx","ecx","edi","esi");
 287         &mov    (@r[0],&DWP(0,"esp"));
 288         &mov    (@r[1],&DWP(4,"esp"));
 289         &mov    (@r[2],&DWP(8,"esp"));
 290         &mov    (@r[3],&DWP(12,"esp"));
 291
 292         &xor    ($lo,$hi);
 293         &xor    ($hi,@r[1]);
 294         &xor    ($lo,@r[0]);
 295         &mov    (&DWP(0,"ebp"),@r[0]);
 296         &xor    ($hi,@r[2]);
 297         &mov    (&DWP(12,"ebp"),@r[3]);
 298         &xor    ($lo,@r[3]);
 299         &stack_pop(4+1);
 300         &xor    ($hi,@r[3]);
 301         &pop    ("edi");
 302         &xor    ($lo,$hi);
 303         &pop    ("esi");
 304         &mov    (&DWP(8,"ebp"),$hi);
 305         &pop    ("ebx");
 306         &mov    (&DWP(4,"ebp"),$lo);
 307         &pop    ("ebp");
 308         &ret    ();
 309 &function_end_B("bn_GF2m_mul_2x2");
 310
 311 &asciz  ("GF(2^m) Multiplication for x86, CRYPTOGAMS by <appro\@openssl.org>");
 312
 313 &asm_finish();