crypto/openssl/crypto/bn/asm/x86_64-mont.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 # October 2005.
  11 #
  12 # Montgomery multiplication routine for x86_64. While it gives modest
  13 # 9% improvement of rsa4096 sign on Opteron, rsa512 sign runs more
  14 # than twice, >2x, as fast. Most common rsa1024 sign is improved by
  15 # respectful 50%. It remains to be seen if loop unrolling and
  16 # dedicated squaring routine can provide further improvement...
  17
  18 # July 2011.
  19 #
  20 # Add dedicated squaring procedure. Performance improvement varies
  21 # from platform to platform, but in average it's ~5%/15%/25%/33%
  22 # for 512-/1024-/2048-/4096-bit RSA *sign* benchmarks respectively.
  23
  24 # August 2011.
  25 #
  26 # Unroll and modulo-schedule inner loops in such manner that they
  27 # are "fallen through" for input lengths of 8, which is critical for
  28 # 1024-bit RSA *sign*. Average performance improvement in comparison
  29 # to *initial* version of this module from 2005 is ~0%/30%/40%/45%
  30 # for 512-/1024-/2048-/4096-bit RSA *sign* benchmarks respectively.
  31
  32 # June 2013.
  33 #
  34 # Optimize reduction in squaring procedure and improve 1024+-bit RSA
  35 # sign performance by 10-16% on Intel Sandy Bridge and later
  36 # (virtually same on non-Intel processors).
  37
  38 # August 2013.
  39 #
  40 # Add MULX/ADOX/ADCX code path.
  41
  42 $flavour = shift;
  43 $output  = shift;
  44 if ($flavour =~ /\./) { $output = $flavour; undef $flavour; }
  45
  46 $win64=0; $win64=1 if ($flavour =~ /[nm]asm|mingw64/ || $output =~ /\.asm$/);
  47
  48 $0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
  49 ( $xlate="${dir}x86_64-xlate.pl" and -f $xlate ) or
  50 ( $xlate="${dir}../../perlasm/x86_64-xlate.pl" and -f $xlate) or
  51 die "can't locate x86_64-xlate.pl";
  52
  53 open OUT,"| \"$^X\" $xlate $flavour $output";
  54 *STDOUT=*OUT;
  55
  56 if (`$ENV{CC} -Wa,-v -c -o /dev/null -x assembler /dev/null 2>&1`
  57                 =~ /GNU assembler version ([2-9]\.[0-9]+)/) {
  58         $addx = ($1>=2.23);
  59 }
  60
  61 if (!$addx && $win64 && ($flavour =~ /nasm/ || $ENV{ASM} =~ /nasm/) &&
  62             `nasm -v 2>&1` =~ /NASM version ([2-9]\.[0-9]+)/) {
  63         $addx = ($1>=2.10);
  64 }
  65
  66 if (!$addx && $win64 && ($flavour =~ /masm/ || $ENV{ASM} =~ /ml64/) &&
  67             `ml64 2>&1` =~ /Version ([0-9]+)\./) {
  68         $addx = ($1>=12);
  69 }
  70
  71 if (!$addx && `$ENV{CC} -v 2>&1` =~ /((?:^clang|LLVM) version|.*based on LLVM) ([3-9])\.([0-9]+)/) {
  72         my $ver = $2 + $3/100.0;        # 3.1->3.01, 3.10->3.10
  73         $addx = ($ver>=3.03);
  74 }
  75
  76 # int bn_mul_mont(
  77 $rp="%rdi";     # BN_ULONG *rp,
  78 $ap="%rsi";     # const BN_ULONG *ap,
  79 $bp="%rdx";     # const BN_ULONG *bp,
  80 $np="%rcx";     # const BN_ULONG *np,
  81 $n0="%r8";      # const BN_ULONG *n0,
  82 $num="%r9";     # int num);
  83 $lo0="%r10";
  84 $hi0="%r11";
  85 $hi1="%r13";
  86 $i="%r14";
  87 $j="%r15";
  88 $m0="%rbx";
  89 $m1="%rbp";
  90
  91 $code=<<___;
  92 .text
  93
  94 .extern OPENSSL_ia32cap_P
  95
  96 .globl  bn_mul_mont
  97 .type   bn_mul_mont,\@function,6
  98 .align  16
  99 bn_mul_mont:
 100         test    \$3,${num}d
 101         jnz     .Lmul_enter
 102         cmp     \$8,${num}d
 103         jb      .Lmul_enter
 104 ___
 105 $code.=<<___ if ($addx);
 106         mov     OPENSSL_ia32cap_P+8(%rip),%r11d
 107 ___
 108 $code.=<<___;
 109         cmp     $ap,$bp
 110         jne     .Lmul4x_enter
 111         test    \$7,${num}d
 112         jz      .Lsqr8x_enter
 113         jmp     .Lmul4x_enter
 114
 115 .align  16
 116 .Lmul_enter:
 117         push    %rbx
 118         push    %rbp
 119         push    %r12
 120         push    %r13
 121         push    %r14
 122         push    %r15
 123
 124         mov     ${num}d,${num}d
 125         lea     2($num),%r10
 126         mov     %rsp,%r11
 127         neg     %r10
 128         lea     (%rsp,%r10,8),%rsp      # tp=alloca(8*(num+2))
 129         and     \$-1024,%rsp            # minimize TLB usage
 130
 131         mov     %r11,8(%rsp,$num,8)     # tp[num+1]=%rsp
 132 .Lmul_body:
 133         # Some OSes, *cough*-dows, insist on stack being "wired" to
 134         # physical memory in strictly sequential manner, i.e. if stack
 135         # allocation spans two pages, then reference to farmost one can
 136         # be punishable by SEGV. But page walking can do good even on
 137         # other OSes, because it guarantees that villain thread hits
 138         # the guard page before it can make damage to innocent one...
 139         sub     %rsp,%r11
 140         and     \$-4096,%r11
 141 .Lmul_page_walk:
 142         mov     (%rsp,%r11),%r10
 143         sub     \$4096,%r11
 144         .byte   0x66,0x2e               # predict non-taken
 145         jnc     .Lmul_page_walk
 146
 147         mov     $bp,%r12                # reassign $bp
 148 ___
 149                 $bp="%r12";
 150 $code.=<<___;
 151         mov     ($n0),$n0               # pull n0[0] value
 152         mov     ($bp),$m0               # m0=bp[0]
 153         mov     ($ap),%rax
 154
 155         xor     $i,$i                   # i=0
 156         xor     $j,$j                   # j=0
 157
 158         mov     $n0,$m1
 159         mulq    $m0                     # ap[0]*bp[0]
 160         mov     %rax,$lo0
 161         mov     ($np),%rax
 162
 163         imulq   $lo0,$m1                # "tp[0]"*n0
 164         mov     %rdx,$hi0
 165
 166         mulq    $m1                     # np[0]*m1
 167         add     %rax,$lo0               # discarded
 168         mov     8($ap),%rax
 169         adc     \$0,%rdx
 170         mov     %rdx,$hi1
 171
 172         lea     1($j),$j                # j++
 173         jmp     .L1st_enter
 174
 175 .align  16
 176 .L1st:
 177         add     %rax,$hi1
 178         mov     ($ap,$j,8),%rax
 179         adc     \$0,%rdx
 180         add     $hi0,$hi1               # np[j]*m1+ap[j]*bp[0]
 181         mov     $lo0,$hi0
 182         adc     \$0,%rdx
 183         mov     $hi1,-16(%rsp,$j,8)     # tp[j-1]
 184         mov     %rdx,$hi1
 185
 186 .L1st_enter:
 187         mulq    $m0                     # ap[j]*bp[0]
 188         add     %rax,$hi0
 189         mov     ($np,$j,8),%rax
 190         adc     \$0,%rdx
 191         lea     1($j),$j                # j++
 192         mov     %rdx,$lo0
 193
 194         mulq    $m1                     # np[j]*m1
 195         cmp     $num,$j
 196         jne     .L1st
 197
 198         add     %rax,$hi1
 199         mov     ($ap),%rax              # ap[0]
 200         adc     \$0,%rdx
 201         add     $hi0,$hi1               # np[j]*m1+ap[j]*bp[0]
 202         adc     \$0,%rdx
 203         mov     $hi1,-16(%rsp,$j,8)     # tp[j-1]
 204         mov     %rdx,$hi1
 205         mov     $lo0,$hi0
 206
 207         xor     %rdx,%rdx
 208         add     $hi0,$hi1
 209         adc     \$0,%rdx
 210         mov     $hi1,-8(%rsp,$num,8)
 211         mov     %rdx,(%rsp,$num,8)      # store upmost overflow bit
 212
 213         lea     1($i),$i                # i++
 214         jmp     .Louter
 215 .align  16
 216 .Louter:
 217         mov     ($bp,$i,8),$m0          # m0=bp[i]
 218         xor     $j,$j                   # j=0
 219         mov     $n0,$m1
 220         mov     (%rsp),$lo0
 221         mulq    $m0                     # ap[0]*bp[i]
 222         add     %rax,$lo0               # ap[0]*bp[i]+tp[0]
 223         mov     ($np),%rax
 224         adc     \$0,%rdx
 225
 226         imulq   $lo0,$m1                # tp[0]*n0
 227         mov     %rdx,$hi0
 228
 229         mulq    $m1                     # np[0]*m1
 230         add     %rax,$lo0               # discarded
 231         mov     8($ap),%rax
 232         adc     \$0,%rdx
 233         mov     8(%rsp),$lo0            # tp[1]
 234         mov     %rdx,$hi1
 235
 236         lea     1($j),$j                # j++
 237         jmp     .Linner_enter
 238
 239 .align  16
 240 .Linner:
 241         add     %rax,$hi1
 242         mov     ($ap,$j,8),%rax
 243         adc     \$0,%rdx
 244         add     $lo0,$hi1               # np[j]*m1+ap[j]*bp[i]+tp[j]
 245         mov     (%rsp,$j,8),$lo0
 246         adc     \$0,%rdx
 247         mov     $hi1,-16(%rsp,$j,8)     # tp[j-1]
 248         mov     %rdx,$hi1
 249
 250 .Linner_enter:
 251         mulq    $m0                     # ap[j]*bp[i]
 252         add     %rax,$hi0
 253         mov     ($np,$j,8),%rax
 254         adc     \$0,%rdx
 255         add     $hi0,$lo0               # ap[j]*bp[i]+tp[j]
 256         mov     %rdx,$hi0
 257         adc     \$0,$hi0
 258         lea     1($j),$j                # j++
 259
 260         mulq    $m1                     # np[j]*m1
 261         cmp     $num,$j
 262         jne     .Linner
 263
 264         add     %rax,$hi1
 265         mov     ($ap),%rax              # ap[0]
 266         adc     \$0,%rdx
 267         add     $lo0,$hi1               # np[j]*m1+ap[j]*bp[i]+tp[j]
 268         mov     (%rsp,$j,8),$lo0
 269         adc     \$0,%rdx
 270         mov     $hi1,-16(%rsp,$j,8)     # tp[j-1]
 271         mov     %rdx,$hi1
 272
 273         xor     %rdx,%rdx
 274         add     $hi0,$hi1
 275         adc     \$0,%rdx
 276         add     $lo0,$hi1               # pull upmost overflow bit
 277         adc     \$0,%rdx
 278         mov     $hi1,-8(%rsp,$num,8)
 279         mov     %rdx,(%rsp,$num,8)      # store upmost overflow bit
 280
 281         lea     1($i),$i                # i++
 282         cmp     $num,$i
 283         jb      .Louter
 284
 285         xor     $i,$i                   # i=0 and clear CF!
 286         mov     (%rsp),%rax             # tp[0]
 287         lea     (%rsp),$ap              # borrow ap for tp
 288         mov     $num,$j                 # j=num
 289         jmp     .Lsub
 290 .align  16
 291 .Lsub:  sbb     ($np,$i,8),%rax
 292         mov     %rax,($rp,$i,8)         # rp[i]=tp[i]-np[i]
 293         mov     8($ap,$i,8),%rax        # tp[i+1]
 294         lea     1($i),$i                # i++
 295         dec     $j                      # doesnn't affect CF!
 296         jnz     .Lsub
 297
 298         sbb     \$0,%rax                # handle upmost overflow bit
 299         xor     $i,$i
 300         and     %rax,$ap
 301         not     %rax
 302         mov     $rp,$np
 303         and     %rax,$np
 304         mov     $num,$j                 # j=num
 305         or      $np,$ap                 # ap=borrow?tp:rp
 306 .align  16
 307 .Lcopy:                                 # copy or in-place refresh
 308         mov     ($ap,$i,8),%rax
 309         mov     $i,(%rsp,$i,8)          # zap temporary vector
 310         mov     %rax,($rp,$i,8)         # rp[i]=tp[i]
 311         lea     1($i),$i
 312         sub     \$1,$j
 313         jnz     .Lcopy
 314
 315         mov     8(%rsp,$num,8),%rsi     # restore %rsp
 316         mov     \$1,%rax
 317         mov     (%rsi),%r15
 318         mov     8(%rsi),%r14
 319         mov     16(%rsi),%r13
 320         mov     24(%rsi),%r12
 321         mov     32(%rsi),%rbp
 322         mov     40(%rsi),%rbx
 323         lea     48(%rsi),%rsp
 324 .Lmul_epilogue:
 325         ret
 326 .size   bn_mul_mont,.-bn_mul_mont
 327 ___
 328 {{{
 329 my @A=("%r10","%r11");
 330 my @N=("%r13","%rdi");
 331 $code.=<<___;
 332 .type   bn_mul4x_mont,\@function,6
 333 .align  16
 334 bn_mul4x_mont:
 335 .Lmul4x_enter:
 336 ___
 337 $code.=<<___ if ($addx);
 338         and     \$0x80100,%r11d
 339         cmp     \$0x80100,%r11d
 340         je      .Lmulx4x_enter
 341 ___
 342 $code.=<<___;
 343         push    %rbx
 344         push    %rbp
 345         push    %r12
 346         push    %r13
 347         push    %r14
 348         push    %r15
 349
 350         mov     ${num}d,${num}d
 351         lea     4($num),%r10
 352         mov     %rsp,%r11
 353         neg     %r10
 354         lea     (%rsp,%r10,8),%rsp      # tp=alloca(8*(num+4))
 355         and     \$-1024,%rsp            # minimize TLB usage
 356
 357         mov     %r11,8(%rsp,$num,8)     # tp[num+1]=%rsp
 358 .Lmul4x_body:
 359         sub     %rsp,%r11
 360         and     \$-4096,%r11
 361 .Lmul4x_page_walk:
 362         mov     (%rsp,%r11),%r10
 363         sub     \$4096,%r11
 364         .byte   0x2e                    # predict non-taken
 365         jnc     .Lmul4x_page_walk
 366
 367         mov     $rp,16(%rsp,$num,8)     # tp[num+2]=$rp
 368         mov     %rdx,%r12               # reassign $bp
 369 ___
 370                 $bp="%r12";
 371 $code.=<<___;
 372         mov     ($n0),$n0               # pull n0[0] value
 373         mov     ($bp),$m0               # m0=bp[0]
 374         mov     ($ap),%rax
 375
 376         xor     $i,$i                   # i=0
 377         xor     $j,$j                   # j=0
 378
 379         mov     $n0,$m1
 380         mulq    $m0                     # ap[0]*bp[0]
 381         mov     %rax,$A[0]
 382         mov     ($np),%rax
 383
 384         imulq   $A[0],$m1               # "tp[0]"*n0
 385         mov     %rdx,$A[1]
 386
 387         mulq    $m1                     # np[0]*m1
 388         add     %rax,$A[0]              # discarded
 389         mov     8($ap),%rax
 390         adc     \$0,%rdx
 391         mov     %rdx,$N[1]
 392
 393         mulq    $m0
 394         add     %rax,$A[1]
 395         mov     8($np),%rax
 396         adc     \$0,%rdx
 397         mov     %rdx,$A[0]
 398
 399         mulq    $m1
 400         add     %rax,$N[1]
 401         mov     16($ap),%rax
 402         adc     \$0,%rdx
 403         add     $A[1],$N[1]
 404         lea     4($j),$j                # j++
 405         adc     \$0,%rdx
 406         mov     $N[1],(%rsp)
 407         mov     %rdx,$N[0]
 408         jmp     .L1st4x
 409 .align  16
 410 .L1st4x:
 411         mulq    $m0                     # ap[j]*bp[0]
 412         add     %rax,$A[0]
 413         mov     -16($np,$j,8),%rax
 414         adc     \$0,%rdx
 415         mov     %rdx,$A[1]
 416
 417         mulq    $m1                     # np[j]*m1
 418         add     %rax,$N[0]
 419         mov     -8($ap,$j,8),%rax
 420         adc     \$0,%rdx
 421         add     $A[0],$N[0]             # np[j]*m1+ap[j]*bp[0]
 422         adc     \$0,%rdx
 423         mov     $N[0],-24(%rsp,$j,8)    # tp[j-1]
 424         mov     %rdx,$N[1]
 425
 426         mulq    $m0                     # ap[j]*bp[0]
 427         add     %rax,$A[1]
 428         mov     -8($np,$j,8),%rax
 429         adc     \$0,%rdx
 430         mov     %rdx,$A[0]
 431
 432         mulq    $m1                     # np[j]*m1
 433         add     %rax,$N[1]
 434         mov     ($ap,$j,8),%rax
 435         adc     \$0,%rdx
 436         add     $A[1],$N[1]             # np[j]*m1+ap[j]*bp[0]
 437         adc     \$0,%rdx
 438         mov     $N[1],-16(%rsp,$j,8)    # tp[j-1]
 439         mov     %rdx,$N[0]
 440
 441         mulq    $m0                     # ap[j]*bp[0]
 442         add     %rax,$A[0]
 443         mov     ($np,$j,8),%rax
 444         adc     \$0,%rdx
 445         mov     %rdx,$A[1]
 446
 447         mulq    $m1                     # np[j]*m1
 448         add     %rax,$N[0]
 449         mov     8($ap,$j,8),%rax
 450         adc     \$0,%rdx
 451         add     $A[0],$N[0]             # np[j]*m1+ap[j]*bp[0]
 452         adc     \$0,%rdx
 453         mov     $N[0],-8(%rsp,$j,8)     # tp[j-1]
 454         mov     %rdx,$N[1]
 455
 456         mulq    $m0                     # ap[j]*bp[0]
 457         add     %rax,$A[1]
 458         mov     8($np,$j,8),%rax
 459         adc     \$0,%rdx
 460         lea     4($j),$j                # j++
 461         mov     %rdx,$A[0]
 462
 463         mulq    $m1                     # np[j]*m1
 464         add     %rax,$N[1]
 465         mov     -16($ap,$j,8),%rax
 466         adc     \$0,%rdx
 467         add     $A[1],$N[1]             # np[j]*m1+ap[j]*bp[0]
 468         adc     \$0,%rdx
 469         mov     $N[1],-32(%rsp,$j,8)    # tp[j-1]
 470         mov     %rdx,$N[0]
 471         cmp     $num,$j
 472         jb      .L1st4x
 473
 474         mulq    $m0                     # ap[j]*bp[0]
 475         add     %rax,$A[0]
 476         mov     -16($np,$j,8),%rax
 477         adc     \$0,%rdx
 478         mov     %rdx,$A[1]
 479
 480         mulq    $m1                     # np[j]*m1
 481         add     %rax,$N[0]
 482         mov     -8($ap,$j,8),%rax
 483         adc     \$0,%rdx
 484         add     $A[0],$N[0]             # np[j]*m1+ap[j]*bp[0]
 485         adc     \$0,%rdx
 486         mov     $N[0],-24(%rsp,$j,8)    # tp[j-1]
 487         mov     %rdx,$N[1]
 488
 489         mulq    $m0                     # ap[j]*bp[0]
 490         add     %rax,$A[1]
 491         mov     -8($np,$j,8),%rax
 492         adc     \$0,%rdx
 493         mov     %rdx,$A[0]
 494
 495         mulq    $m1                     # np[j]*m1
 496         add     %rax,$N[1]
 497         mov     ($ap),%rax              # ap[0]
 498         adc     \$0,%rdx
 499         add     $A[1],$N[1]             # np[j]*m1+ap[j]*bp[0]
 500         adc     \$0,%rdx
 501         mov     $N[1],-16(%rsp,$j,8)    # tp[j-1]
 502         mov     %rdx,$N[0]
 503
 504         xor     $N[1],$N[1]
 505         add     $A[0],$N[0]
 506         adc     \$0,$N[1]
 507         mov     $N[0],-8(%rsp,$j,8)
 508         mov     $N[1],(%rsp,$j,8)       # store upmost overflow bit
 509
 510         lea     1($i),$i                # i++
 511 .align  4
 512 .Louter4x:
 513         mov     ($bp,$i,8),$m0          # m0=bp[i]
 514         xor     $j,$j                   # j=0
 515         mov     (%rsp),$A[0]
 516         mov     $n0,$m1
 517         mulq    $m0                     # ap[0]*bp[i]
 518         add     %rax,$A[0]              # ap[0]*bp[i]+tp[0]
 519         mov     ($np),%rax
 520         adc     \$0,%rdx
 521
 522         imulq   $A[0],$m1               # tp[0]*n0
 523         mov     %rdx,$A[1]
 524
 525         mulq    $m1                     # np[0]*m1
 526         add     %rax,$A[0]              # "$N[0]", discarded
 527         mov     8($ap),%rax
 528         adc     \$0,%rdx
 529         mov     %rdx,$N[1]
 530
 531         mulq    $m0                     # ap[j]*bp[i]
 532         add     %rax,$A[1]
 533         mov     8($np),%rax
 534         adc     \$0,%rdx
 535         add     8(%rsp),$A[1]           # +tp[1]
 536         adc     \$0,%rdx
 537         mov     %rdx,$A[0]
 538
 539         mulq    $m1                     # np[j]*m1
 540         add     %rax,$N[1]
 541         mov     16($ap),%rax
 542         adc     \$0,%rdx
 543         add     $A[1],$N[1]             # np[j]*m1+ap[j]*bp[i]+tp[j]
 544         lea     4($j),$j                # j+=2
 545         adc     \$0,%rdx
 546         mov     $N[1],(%rsp)            # tp[j-1]
 547         mov     %rdx,$N[0]
 548         jmp     .Linner4x
 549 .align  16
 550 .Linner4x:
 551         mulq    $m0                     # ap[j]*bp[i]
 552         add     %rax,$A[0]
 553         mov     -16($np,$j,8),%rax
 554         adc     \$0,%rdx
 555         add     -16(%rsp,$j,8),$A[0]    # ap[j]*bp[i]+tp[j]
 556         adc     \$0,%rdx
 557         mov     %rdx,$A[1]
 558
 559         mulq    $m1                     # np[j]*m1
 560         add     %rax,$N[0]
 561         mov     -8($ap,$j,8),%rax
 562         adc     \$0,%rdx
 563         add     $A[0],$N[0]
 564         adc     \$0,%rdx
 565         mov     $N[0],-24(%rsp,$j,8)    # tp[j-1]
 566         mov     %rdx,$N[1]
 567
 568         mulq    $m0                     # ap[j]*bp[i]
 569         add     %rax,$A[1]
 570         mov     -8($np,$j,8),%rax
 571         adc     \$0,%rdx
 572         add     -8(%rsp,$j,8),$A[1]
 573         adc     \$0,%rdx
 574         mov     %rdx,$A[0]
 575
 576         mulq    $m1                     # np[j]*m1
 577         add     %rax,$N[1]
 578         mov     ($ap,$j,8),%rax
 579         adc     \$0,%rdx
 580         add     $A[1],$N[1]
 581         adc     \$0,%rdx
 582         mov     $N[1],-16(%rsp,$j,8)    # tp[j-1]
 583         mov     %rdx,$N[0]
 584
 585         mulq    $m0                     # ap[j]*bp[i]
 586         add     %rax,$A[0]
 587         mov     ($np,$j,8),%rax
 588         adc     \$0,%rdx
 589         add     (%rsp,$j,8),$A[0]       # ap[j]*bp[i]+tp[j]
 590         adc     \$0,%rdx
 591         mov     %rdx,$A[1]
 592
 593         mulq    $m1                     # np[j]*m1
 594         add     %rax,$N[0]
 595         mov     8($ap,$j,8),%rax
 596         adc     \$0,%rdx
 597         add     $A[0],$N[0]
 598         adc     \$0,%rdx
 599         mov     $N[0],-8(%rsp,$j,8)     # tp[j-1]
 600         mov     %rdx,$N[1]
 601
 602         mulq    $m0                     # ap[j]*bp[i]
 603         add     %rax,$A[1]
 604         mov     8($np,$j,8),%rax
 605         adc     \$0,%rdx
 606         add     8(%rsp,$j,8),$A[1]
 607         adc     \$0,%rdx
 608         lea     4($j),$j                # j++
 609         mov     %rdx,$A[0]
 610
 611         mulq    $m1                     # np[j]*m1
 612         add     %rax,$N[1]
 613         mov     -16($ap,$j,8),%rax
 614         adc     \$0,%rdx
 615         add     $A[1],$N[1]
 616         adc     \$0,%rdx
 617         mov     $N[1],-32(%rsp,$j,8)    # tp[j-1]
 618         mov     %rdx,$N[0]
 619         cmp     $num,$j
 620         jb      .Linner4x
 621
 622         mulq    $m0                     # ap[j]*bp[i]
 623         add     %rax,$A[0]
 624         mov     -16($np,$j,8),%rax
 625         adc     \$0,%rdx
 626         add     -16(%rsp,$j,8),$A[0]    # ap[j]*bp[i]+tp[j]
 627         adc     \$0,%rdx
 628         mov     %rdx,$A[1]
 629
 630         mulq    $m1                     # np[j]*m1
 631         add     %rax,$N[0]
 632         mov     -8($ap,$j,8),%rax
 633         adc     \$0,%rdx
 634         add     $A[0],$N[0]
 635         adc     \$0,%rdx
 636         mov     $N[0],-24(%rsp,$j,8)    # tp[j-1]
 637         mov     %rdx,$N[1]
 638
 639         mulq    $m0                     # ap[j]*bp[i]
 640         add     %rax,$A[1]
 641         mov     -8($np,$j,8),%rax
 642         adc     \$0,%rdx
 643         add     -8(%rsp,$j,8),$A[1]
 644         adc     \$0,%rdx
 645         lea     1($i),$i                # i++
 646         mov     %rdx,$A[0]
 647
 648         mulq    $m1                     # np[j]*m1
 649         add     %rax,$N[1]
 650         mov     ($ap),%rax              # ap[0]
 651         adc     \$0,%rdx
 652         add     $A[1],$N[1]
 653         adc     \$0,%rdx
 654         mov     $N[1],-16(%rsp,$j,8)    # tp[j-1]
 655         mov     %rdx,$N[0]
 656
 657         xor     $N[1],$N[1]
 658         add     $A[0],$N[0]
 659         adc     \$0,$N[1]
 660         add     (%rsp,$num,8),$N[0]     # pull upmost overflow bit
 661         adc     \$0,$N[1]
 662         mov     $N[0],-8(%rsp,$j,8)
 663         mov     $N[1],(%rsp,$j,8)       # store upmost overflow bit
 664
 665         cmp     $num,$i
 666         jb      .Louter4x
 667 ___
 668 {
 669 my @ri=("%rax","%rdx",$m0,$m1);
 670 $code.=<<___;
 671         mov     16(%rsp,$num,8),$rp     # restore $rp
 672         mov     0(%rsp),@ri[0]          # tp[0]
 673         pxor    %xmm0,%xmm0
 674         mov     8(%rsp),@ri[1]          # tp[1]
 675         shr     \$2,$num                # num/=4
 676         lea     (%rsp),$ap              # borrow ap for tp
 677         xor     $i,$i                   # i=0 and clear CF!
 678
 679         sub     0($np),@ri[0]
 680         mov     16($ap),@ri[2]          # tp[2]
 681         mov     24($ap),@ri[3]          # tp[3]
 682         sbb     8($np),@ri[1]
 683         lea     -1($num),$j             # j=num/4-1
 684         jmp     .Lsub4x
 685 .align  16
 686 .Lsub4x:
 687         mov     @ri[0],0($rp,$i,8)      # rp[i]=tp[i]-np[i]
 688         mov     @ri[1],8($rp,$i,8)      # rp[i]=tp[i]-np[i]
 689         sbb     16($np,$i,8),@ri[2]
 690         mov     32($ap,$i,8),@ri[0]     # tp[i+1]
 691         mov     40($ap,$i,8),@ri[1]
 692         sbb     24($np,$i,8),@ri[3]
 693         mov     @ri[2],16($rp,$i,8)     # rp[i]=tp[i]-np[i]
 694         mov     @ri[3],24($rp,$i,8)     # rp[i]=tp[i]-np[i]
 695         sbb     32($np,$i,8),@ri[0]
 696         mov     48($ap,$i,8),@ri[2]
 697         mov     56($ap,$i,8),@ri[3]
 698         sbb     40($np,$i,8),@ri[1]
 699         lea     4($i),$i                # i++
 700         dec     $j                      # doesnn't affect CF!
 701         jnz     .Lsub4x
 702
 703         mov     @ri[0],0($rp,$i,8)      # rp[i]=tp[i]-np[i]
 704         mov     32($ap,$i,8),@ri[0]     # load overflow bit
 705         sbb     16($np,$i,8),@ri[2]
 706         mov     @ri[1],8($rp,$i,8)      # rp[i]=tp[i]-np[i]
 707         sbb     24($np,$i,8),@ri[3]
 708         mov     @ri[2],16($rp,$i,8)     # rp[i]=tp[i]-np[i]
 709
 710         sbb     \$0,@ri[0]              # handle upmost overflow bit
 711         mov     @ri[3],24($rp,$i,8)     # rp[i]=tp[i]-np[i]
 712         xor     $i,$i                   # i=0
 713         and     @ri[0],$ap
 714         not     @ri[0]
 715         mov     $rp,$np
 716         and     @ri[0],$np
 717         lea     -1($num),$j
 718         or      $np,$ap                 # ap=borrow?tp:rp
 719
 720         movdqu  ($ap),%xmm1
 721         movdqa  %xmm0,(%rsp)
 722         movdqu  %xmm1,($rp)
 723         jmp     .Lcopy4x
 724 .align  16
 725 .Lcopy4x:                                       # copy or in-place refresh
 726         movdqu  16($ap,$i),%xmm2
 727         movdqu  32($ap,$i),%xmm1
 728         movdqa  %xmm0,16(%rsp,$i)
 729         movdqu  %xmm2,16($rp,$i)
 730         movdqa  %xmm0,32(%rsp,$i)
 731         movdqu  %xmm1,32($rp,$i)
 732         lea     32($i),$i
 733         dec     $j
 734         jnz     .Lcopy4x
 735
 736         shl     \$2,$num
 737         movdqu  16($ap,$i),%xmm2
 738         movdqa  %xmm0,16(%rsp,$i)
 739         movdqu  %xmm2,16($rp,$i)
 740 ___
 741 }
 742 $code.=<<___;
 743         mov     8(%rsp,$num,8),%rsi     # restore %rsp
 744         mov     \$1,%rax
 745         mov     (%rsi),%r15
 746         mov     8(%rsi),%r14
 747         mov     16(%rsi),%r13
 748         mov     24(%rsi),%r12
 749         mov     32(%rsi),%rbp
 750         mov     40(%rsi),%rbx
 751         lea     48(%rsi),%rsp
 752 .Lmul4x_epilogue:
 753         ret
 754 .size   bn_mul4x_mont,.-bn_mul4x_mont
 755 ___
 756 }}}
 757 \f{{{
 758 ######################################################################
 759 # void bn_sqr8x_mont(
 760 my $rptr="%rdi";        # const BN_ULONG *rptr,
 761 my $aptr="%rsi";        # const BN_ULONG *aptr,
 762 my $bptr="%rdx";        # not used
 763 my $nptr="%rcx";        # const BN_ULONG *nptr,
 764 my $n0  ="%r8";         # const BN_ULONG *n0);
 765 my $num ="%r9";         # int num, has to be divisible by 8
 766
 767 my ($i,$j,$tptr)=("%rbp","%rcx",$rptr);
 768 my @A0=("%r10","%r11");
 769 my @A1=("%r12","%r13");
 770 my ($a0,$a1,$ai)=("%r14","%r15","%rbx");
 771
 772 $code.=<<___    if ($addx);
 773 .extern bn_sqrx8x_internal              # see x86_64-mont5 module
 774 ___
 775 $code.=<<___;
 776 .extern bn_sqr8x_internal               # see x86_64-mont5 module
 777
 778 .type   bn_sqr8x_mont,\@function,6
 779 .align  32
 780 bn_sqr8x_mont:
 781 .Lsqr8x_enter:
 782         mov     %rsp,%rax
 783         push    %rbx
 784         push    %rbp
 785         push    %r12
 786         push    %r13
 787         push    %r14
 788         push    %r15
 789
 790         mov     ${num}d,%r10d
 791         shl     \$3,${num}d             # convert $num to bytes
 792         shl     \$3+2,%r10              # 4*$num
 793         neg     $num
 794
 795         ##############################################################
 796         # ensure that stack frame doesn't alias with $aptr modulo
 797         # 4096. this is done to allow memory disambiguation logic
 798         # do its job.
 799         #
 800         lea     -64(%rsp,$num,2),%r11
 801         mov     ($n0),$n0               # *n0
 802         sub     $aptr,%r11
 803         and     \$4095,%r11
 804         cmp     %r11,%r10
 805         jb      .Lsqr8x_sp_alt
 806         sub     %r11,%rsp               # align with $aptr
 807         lea     -64(%rsp,$num,2),%rsp   # alloca(frame+2*$num)
 808         jmp     .Lsqr8x_sp_done
 809
 810 .align  32
 811 .Lsqr8x_sp_alt:
 812         lea     4096-64(,$num,2),%r10   # 4096-frame-2*$num
 813         lea     -64(%rsp,$num,2),%rsp   # alloca(frame+2*$num)
 814         sub     %r10,%r11
 815         mov     \$0,%r10
 816         cmovc   %r10,%r11
 817         sub     %r11,%rsp
 818 .Lsqr8x_sp_done:
 819         and     \$-64,%rsp
 820         mov     %rax,%r11
 821         sub     %rsp,%r11
 822         and     \$-4096,%r11
 823 .Lsqr8x_page_walk:
 824         mov     (%rsp,%r11),%r10
 825         sub     \$4096,%r11
 826         .byte   0x2e                    # predict non-taken
 827         jnc     .Lsqr8x_page_walk
 828
 829         mov     $num,%r10
 830         neg     $num
 831
 832         mov     $n0,  32(%rsp)
 833         mov     %rax, 40(%rsp)          # save original %rsp
 834 .Lsqr8x_body:
 835
 836         movq    $nptr, %xmm2            # save pointer to modulus
 837         pxor    %xmm0,%xmm0
 838         movq    $rptr,%xmm1             # save $rptr
 839         movq    %r10, %xmm3             # -$num
 840 ___
 841 $code.=<<___ if ($addx);
 842         mov     OPENSSL_ia32cap_P+8(%rip),%eax
 843         and     \$0x80100,%eax
 844         cmp     \$0x80100,%eax
 845         jne     .Lsqr8x_nox
 846
 847         call    bn_sqrx8x_internal      # see x86_64-mont5 module
 848                                         # %rax  top-most carry
 849                                         # %rbp  nptr
 850                                         # %rcx  -8*num
 851                                         # %r8   end of tp[2*num]
 852         lea     (%r8,%rcx),%rbx
 853         mov     %rcx,$num
 854         mov     %rcx,%rdx
 855         movq    %xmm1,$rptr
 856         sar     \$3+2,%rcx              # %cf=0
 857         jmp     .Lsqr8x_sub
 858
 859 .align  32
 860 .Lsqr8x_nox:
 861 ___
 862 $code.=<<___;
 863         call    bn_sqr8x_internal       # see x86_64-mont5 module
 864                                         # %rax  top-most carry
 865                                         # %rbp  nptr
 866                                         # %r8   -8*num
 867                                         # %rdi  end of tp[2*num]
 868         lea     (%rdi,$num),%rbx
 869         mov     $num,%rcx
 870         mov     $num,%rdx
 871         movq    %xmm1,$rptr
 872         sar     \$3+2,%rcx              # %cf=0
 873         jmp     .Lsqr8x_sub
 874
 875 .align  32
 876 .Lsqr8x_sub:
 877         mov     8*0(%rbx),%r12
 878         mov     8*1(%rbx),%r13
 879         mov     8*2(%rbx),%r14
 880         mov     8*3(%rbx),%r15
 881         lea     8*4(%rbx),%rbx
 882         sbb     8*0(%rbp),%r12
 883         sbb     8*1(%rbp),%r13
 884         sbb     8*2(%rbp),%r14
 885         sbb     8*3(%rbp),%r15
 886         lea     8*4(%rbp),%rbp
 887         mov     %r12,8*0($rptr)
 888         mov     %r13,8*1($rptr)
 889         mov     %r14,8*2($rptr)
 890         mov     %r15,8*3($rptr)
 891         lea     8*4($rptr),$rptr
 892         inc     %rcx                    # preserves %cf
 893         jnz     .Lsqr8x_sub
 894
 895         sbb     \$0,%rax                # top-most carry
 896         lea     (%rbx,$num),%rbx        # rewind
 897         lea     ($rptr,$num),$rptr      # rewind
 898
 899         movq    %rax,%xmm1
 900         pxor    %xmm0,%xmm0
 901         pshufd  \$0,%xmm1,%xmm1
 902         mov     40(%rsp),%rsi           # restore %rsp
 903         jmp     .Lsqr8x_cond_copy
 904
 905 .align  32
 906 .Lsqr8x_cond_copy:
 907         movdqa  16*0(%rbx),%xmm2
 908         movdqa  16*1(%rbx),%xmm3
 909         lea     16*2(%rbx),%rbx
 910         movdqu  16*0($rptr),%xmm4
 911         movdqu  16*1($rptr),%xmm5
 912         lea     16*2($rptr),$rptr
 913         movdqa  %xmm0,-16*2(%rbx)       # zero tp
 914         movdqa  %xmm0,-16*1(%rbx)
 915         movdqa  %xmm0,-16*2(%rbx,%rdx)
 916         movdqa  %xmm0,-16*1(%rbx,%rdx)
 917         pcmpeqd %xmm1,%xmm0
 918         pand    %xmm1,%xmm2
 919         pand    %xmm1,%xmm3
 920         pand    %xmm0,%xmm4
 921         pand    %xmm0,%xmm5
 922         pxor    %xmm0,%xmm0
 923         por     %xmm2,%xmm4
 924         por     %xmm3,%xmm5
 925         movdqu  %xmm4,-16*2($rptr)
 926         movdqu  %xmm5,-16*1($rptr)
 927         add     \$32,$num
 928         jnz     .Lsqr8x_cond_copy
 929
 930         mov     \$1,%rax
 931         mov     -48(%rsi),%r15
 932         mov     -40(%rsi),%r14
 933         mov     -32(%rsi),%r13
 934         mov     -24(%rsi),%r12
 935         mov     -16(%rsi),%rbp
 936         mov     -8(%rsi),%rbx
 937         lea     (%rsi),%rsp
 938 .Lsqr8x_epilogue:
 939         ret
 940 .size   bn_sqr8x_mont,.-bn_sqr8x_mont
 941 ___
 942 }}}
 943 \f
 944 if ($addx) {{{
 945 my $bp="%rdx";  # original value
 946
 947 $code.=<<___;
 948 .type   bn_mulx4x_mont,\@function,6
 949 .align  32
 950 bn_mulx4x_mont:
 951 .Lmulx4x_enter:
 952         mov     %rsp,%rax
 953         push    %rbx
 954         push    %rbp
 955         push    %r12
 956         push    %r13
 957         push    %r14
 958         push    %r15
 959
 960         shl     \$3,${num}d             # convert $num to bytes
 961         .byte   0x67
 962         xor     %r10,%r10
 963         sub     $num,%r10               # -$num
 964         mov     ($n0),$n0               # *n0
 965         lea     -72(%rsp,%r10),%rsp     # alloca(frame+$num+8)
 966         and     \$-128,%rsp
 967         mov     %rax,%r11
 968         sub     %rsp,%r11
 969         and     \$-4096,%r11
 970 .Lmulx4x_page_walk:
 971         mov     (%rsp,%r11),%r10
 972         sub     \$4096,%r11
 973         .byte   0x66,0x2e               # predict non-taken
 974         jnc     .Lmulx4x_page_walk
 975
 976         lea     ($bp,$num),%r10
 977         ##############################################################
 978         # Stack layout
 979         # +0    num
 980         # +8    off-loaded &b[i]
 981         # +16   end of b[num]
 982         # +24   saved n0
 983         # +32   saved rp
 984         # +40   saved %rsp
 985         # +48   inner counter
 986         # +56
 987         # +64   tmp[num+1]
 988         #
 989         mov     $num,0(%rsp)            # save $num
 990         shr     \$5,$num
 991         mov     %r10,16(%rsp)           # end of b[num]
 992         sub     \$1,$num
 993         mov     $n0, 24(%rsp)           # save *n0
 994         mov     $rp, 32(%rsp)           # save $rp
 995         mov     %rax,40(%rsp)           # save original %rsp
 996         mov     $num,48(%rsp)           # inner counter
 997         jmp     .Lmulx4x_body
 998
 999 .align  32
1000 .Lmulx4x_body:
1001 ___
1002 my ($aptr, $bptr, $nptr, $tptr, $mi,  $bi,  $zero, $num)=
1003    ("%rsi","%rdi","%rcx","%rbx","%r8","%r9","%rbp","%rax");
1004 my $rptr=$bptr;
1005 $code.=<<___;
1006         lea     8($bp),$bptr
1007         mov     ($bp),%rdx              # b[0], $bp==%rdx actually
1008         lea     64+32(%rsp),$tptr
1009         mov     %rdx,$bi
1010
1011         mulx    0*8($aptr),$mi,%rax     # a[0]*b[0]
1012         mulx    1*8($aptr),%r11,%r14    # a[1]*b[0]
1013         add     %rax,%r11
1014         mov     $bptr,8(%rsp)           # off-load &b[i]
1015         mulx    2*8($aptr),%r12,%r13    # ...
1016         adc     %r14,%r12
1017         adc     \$0,%r13
1018
1019         mov     $mi,$bptr               # borrow $bptr
1020         imulq   24(%rsp),$mi            # "t[0]"*n0
1021         xor     $zero,$zero             # cf=0, of=0
1022
1023         mulx    3*8($aptr),%rax,%r14
1024          mov    $mi,%rdx
1025         lea     4*8($aptr),$aptr
1026         adcx    %rax,%r13
1027         adcx    $zero,%r14              # cf=0
1028
1029         mulx    0*8($nptr),%rax,%r10
1030         adcx    %rax,$bptr              # discarded
1031         adox    %r11,%r10
1032         mulx    1*8($nptr),%rax,%r11
1033         adcx    %rax,%r10
1034         adox    %r12,%r11
1035         .byte   0xc4,0x62,0xfb,0xf6,0xa1,0x10,0x00,0x00,0x00    # mulx  2*8($nptr),%rax,%r12
1036         mov     48(%rsp),$bptr          # counter value
1037         mov     %r10,-4*8($tptr)
1038         adcx    %rax,%r11
1039         adox    %r13,%r12
1040         mulx    3*8($nptr),%rax,%r15
1041          mov    $bi,%rdx
1042         mov     %r11,-3*8($tptr)
1043         adcx    %rax,%r12
1044         adox    $zero,%r15              # of=0
1045         lea     4*8($nptr),$nptr
1046         mov     %r12,-2*8($tptr)
1047
1048         jmp     .Lmulx4x_1st
1049
1050 .align  32
1051 .Lmulx4x_1st:
1052         adcx    $zero,%r15              # cf=0, modulo-scheduled
1053         mulx    0*8($aptr),%r10,%rax    # a[4]*b[0]
1054         adcx    %r14,%r10
1055         mulx    1*8($aptr),%r11,%r14    # a[5]*b[0]
1056         adcx    %rax,%r11
1057         mulx    2*8($aptr),%r12,%rax    # ...
1058         adcx    %r14,%r12
1059         mulx    3*8($aptr),%r13,%r14
1060          .byte  0x67,0x67
1061          mov    $mi,%rdx
1062         adcx    %rax,%r13
1063         adcx    $zero,%r14              # cf=0
1064         lea     4*8($aptr),$aptr
1065         lea     4*8($tptr),$tptr
1066
1067         adox    %r15,%r10
1068         mulx    0*8($nptr),%rax,%r15
1069         adcx    %rax,%r10
1070         adox    %r15,%r11
1071         mulx    1*8($nptr),%rax,%r15
1072         adcx    %rax,%r11
1073         adox    %r15,%r12
1074         mulx    2*8($nptr),%rax,%r15
1075         mov     %r10,-5*8($tptr)
1076         adcx    %rax,%r12
1077         mov     %r11,-4*8($tptr)
1078         adox    %r15,%r13
1079         mulx    3*8($nptr),%rax,%r15
1080          mov    $bi,%rdx
1081         mov     %r12,-3*8($tptr)
1082         adcx    %rax,%r13
1083         adox    $zero,%r15
1084         lea     4*8($nptr),$nptr
1085         mov     %r13,-2*8($tptr)
1086
1087         dec     $bptr                   # of=0, pass cf
1088         jnz     .Lmulx4x_1st
1089
1090         mov     0(%rsp),$num            # load num
1091         mov     8(%rsp),$bptr           # re-load &b[i]
1092         adc     $zero,%r15              # modulo-scheduled
1093         add     %r15,%r14
1094         sbb     %r15,%r15               # top-most carry
1095         mov     %r14,-1*8($tptr)
1096         jmp     .Lmulx4x_outer
1097
1098 .align  32
1099 .Lmulx4x_outer:
1100         mov     ($bptr),%rdx            # b[i]
1101         lea     8($bptr),$bptr          # b++
1102         sub     $num,$aptr              # rewind $aptr
1103         mov     %r15,($tptr)            # save top-most carry
1104         lea     64+4*8(%rsp),$tptr
1105         sub     $num,$nptr              # rewind $nptr
1106
1107         mulx    0*8($aptr),$mi,%r11     # a[0]*b[i]
1108         xor     %ebp,%ebp               # xor   $zero,$zero     # cf=0, of=0
1109         mov     %rdx,$bi
1110         mulx    1*8($aptr),%r14,%r12    # a[1]*b[i]
1111         adox    -4*8($tptr),$mi
1112         adcx    %r14,%r11
1113         mulx    2*8($aptr),%r15,%r13    # ...
1114         adox    -3*8($tptr),%r11
1115         adcx    %r15,%r12
1116         adox    $zero,%r12
1117         adcx    $zero,%r13
1118
1119         mov     $bptr,8(%rsp)           # off-load &b[i]
1120         .byte   0x67
1121         mov     $mi,%r15
1122         imulq   24(%rsp),$mi            # "t[0]"*n0
1123         xor     %ebp,%ebp               # xor   $zero,$zero     # cf=0, of=0
1124
1125         mulx    3*8($aptr),%rax,%r14
1126          mov    $mi,%rdx
1127         adox    -2*8($tptr),%r12
1128         adcx    %rax,%r13
1129         adox    -1*8($tptr),%r13
1130         adcx    $zero,%r14
1131         lea     4*8($aptr),$aptr
1132         adox    $zero,%r14
1133
1134         mulx    0*8($nptr),%rax,%r10
1135         adcx    %rax,%r15               # discarded
1136         adox    %r11,%r10
1137         mulx    1*8($nptr),%rax,%r11
1138         adcx    %rax,%r10
1139         adox    %r12,%r11
1140         mulx    2*8($nptr),%rax,%r12
1141         mov     %r10,-4*8($tptr)
1142         adcx    %rax,%r11
1143         adox    %r13,%r12
1144         mulx    3*8($nptr),%rax,%r15
1145          mov    $bi,%rdx
1146         mov     %r11,-3*8($tptr)
1147         lea     4*8($nptr),$nptr
1148         adcx    %rax,%r12
1149         adox    $zero,%r15              # of=0
1150         mov     48(%rsp),$bptr          # counter value
1151         mov     %r12,-2*8($tptr)
1152
1153         jmp     .Lmulx4x_inner
1154
1155 .align  32
1156 .Lmulx4x_inner:
1157         mulx    0*8($aptr),%r10,%rax    # a[4]*b[i]
1158         adcx    $zero,%r15              # cf=0, modulo-scheduled
1159         adox    %r14,%r10
1160         mulx    1*8($aptr),%r11,%r14    # a[5]*b[i]
1161         adcx    0*8($tptr),%r10
1162         adox    %rax,%r11
1163         mulx    2*8($aptr),%r12,%rax    # ...
1164         adcx    1*8($tptr),%r11
1165         adox    %r14,%r12
1166         mulx    3*8($aptr),%r13,%r14
1167          mov    $mi,%rdx
1168         adcx    2*8($tptr),%r12
1169         adox    %rax,%r13
1170         adcx    3*8($tptr),%r13
1171         adox    $zero,%r14              # of=0
1172         lea     4*8($aptr),$aptr
1173         lea     4*8($tptr),$tptr
1174         adcx    $zero,%r14              # cf=0
1175
1176         adox    %r15,%r10
1177         mulx    0*8($nptr),%rax,%r15
1178         adcx    %rax,%r10
1179         adox    %r15,%r11
1180         mulx    1*8($nptr),%rax,%r15
1181         adcx    %rax,%r11
1182         adox    %r15,%r12
1183         mulx    2*8($nptr),%rax,%r15
1184         mov     %r10,-5*8($tptr)
1185         adcx    %rax,%r12
1186         adox    %r15,%r13
1187         mulx    3*8($nptr),%rax,%r15
1188          mov    $bi,%rdx
1189         mov     %r11,-4*8($tptr)
1190         mov     %r12,-3*8($tptr)
1191         adcx    %rax,%r13
1192         adox    $zero,%r15
1193         lea     4*8($nptr),$nptr
1194         mov     %r13,-2*8($tptr)
1195
1196         dec     $bptr                   # of=0, pass cf
1197         jnz     .Lmulx4x_inner
1198
1199         mov     0(%rsp),$num            # load num
1200         mov     8(%rsp),$bptr           # re-load &b[i]
1201         adc     $zero,%r15              # modulo-scheduled
1202         sub     0*8($tptr),$zero        # pull top-most carry
1203         adc     %r15,%r14
1204         sbb     %r15,%r15               # top-most carry
1205         mov     %r14,-1*8($tptr)
1206
1207         cmp     16(%rsp),$bptr
1208         jne     .Lmulx4x_outer
1209
1210         lea     64(%rsp),$tptr
1211         sub     $num,$nptr              # rewind $nptr
1212         neg     %r15
1213         mov     $num,%rdx
1214         shr     \$3+2,$num              # %cf=0
1215         mov     32(%rsp),$rptr          # restore rp
1216         jmp     .Lmulx4x_sub
1217
1218 .align  32
1219 .Lmulx4x_sub:
1220         mov     8*0($tptr),%r11
1221         mov     8*1($tptr),%r12
1222         mov     8*2($tptr),%r13
1223         mov     8*3($tptr),%r14
1224         lea     8*4($tptr),$tptr
1225         sbb     8*0($nptr),%r11
1226         sbb     8*1($nptr),%r12
1227         sbb     8*2($nptr),%r13
1228         sbb     8*3($nptr),%r14
1229         lea     8*4($nptr),$nptr
1230         mov     %r11,8*0($rptr)
1231         mov     %r12,8*1($rptr)
1232         mov     %r13,8*2($rptr)
1233         mov     %r14,8*3($rptr)
1234         lea     8*4($rptr),$rptr
1235         dec     $num                    # preserves %cf
1236         jnz     .Lmulx4x_sub
1237
1238         sbb     \$0,%r15                # top-most carry
1239         lea     64(%rsp),$tptr
1240         sub     %rdx,$rptr              # rewind
1241
1242         movq    %r15,%xmm1
1243         pxor    %xmm0,%xmm0
1244         pshufd  \$0,%xmm1,%xmm1
1245         mov     40(%rsp),%rsi           # restore %rsp
1246         jmp     .Lmulx4x_cond_copy
1247
1248 .align  32
1249 .Lmulx4x_cond_copy:
1250         movdqa  16*0($tptr),%xmm2
1251         movdqa  16*1($tptr),%xmm3
1252         lea     16*2($tptr),$tptr
1253         movdqu  16*0($rptr),%xmm4
1254         movdqu  16*1($rptr),%xmm5
1255         lea     16*2($rptr),$rptr
1256         movdqa  %xmm0,-16*2($tptr)      # zero tp
1257         movdqa  %xmm0,-16*1($tptr)
1258         pcmpeqd %xmm1,%xmm0
1259         pand    %xmm1,%xmm2
1260         pand    %xmm1,%xmm3
1261         pand    %xmm0,%xmm4
1262         pand    %xmm0,%xmm5
1263         pxor    %xmm0,%xmm0
1264         por     %xmm2,%xmm4
1265         por     %xmm3,%xmm5
1266         movdqu  %xmm4,-16*2($rptr)
1267         movdqu  %xmm5,-16*1($rptr)
1268         sub     \$32,%rdx
1269         jnz     .Lmulx4x_cond_copy
1270
1271         mov     %rdx,($tptr)
1272
1273         mov     \$1,%rax
1274         mov     -48(%rsi),%r15
1275         mov     -40(%rsi),%r14
1276         mov     -32(%rsi),%r13
1277         mov     -24(%rsi),%r12
1278         mov     -16(%rsi),%rbp
1279         mov     -8(%rsi),%rbx
1280         lea     (%rsi),%rsp
1281 .Lmulx4x_epilogue:
1282         ret
1283 .size   bn_mulx4x_mont,.-bn_mulx4x_mont
1284 ___
1285 }}}
1286 $code.=<<___;
1287 .asciz  "Montgomery Multiplication for x86_64, CRYPTOGAMS by <appro\@openssl.org>"
1288 .align  16
1289 ___
1290
1291 # EXCEPTION_DISPOSITION handler (EXCEPTION_RECORD *rec,ULONG64 frame,
1292 #               CONTEXT *context,DISPATCHER_CONTEXT *disp)
1293 if ($win64) {
1294 $rec="%rcx";
1295 $frame="%rdx";
1296 $context="%r8";
1297 $disp="%r9";
1298
1299 $code.=<<___;
1300 .extern __imp_RtlVirtualUnwind
1301 .type   mul_handler,\@abi-omnipotent
1302 .align  16
1303 mul_handler:
1304         push    %rsi
1305         push    %rdi
1306         push    %rbx
1307         push    %rbp
1308         push    %r12
1309         push    %r13
1310         push    %r14
1311         push    %r15
1312         pushfq
1313         sub     \$64,%rsp
1314
1315         mov     120($context),%rax      # pull context->Rax
1316         mov     248($context),%rbx      # pull context->Rip
1317
1318         mov     8($disp),%rsi           # disp->ImageBase
1319         mov     56($disp),%r11          # disp->HandlerData
1320
1321         mov     0(%r11),%r10d           # HandlerData[0]
1322         lea     (%rsi,%r10),%r10        # end of prologue label
1323         cmp     %r10,%rbx               # context->Rip<end of prologue label
1324         jb      .Lcommon_seh_tail
1325
1326         mov     152($context),%rax      # pull context->Rsp
1327
1328         mov     4(%r11),%r10d           # HandlerData[1]
1329         lea     (%rsi,%r10),%r10        # epilogue label
1330         cmp     %r10,%rbx               # context->Rip>=epilogue label
1331         jae     .Lcommon_seh_tail
1332
1333         mov     192($context),%r10      # pull $num
1334         mov     8(%rax,%r10,8),%rax     # pull saved stack pointer
1335         lea     48(%rax),%rax
1336
1337         mov     -8(%rax),%rbx
1338         mov     -16(%rax),%rbp
1339         mov     -24(%rax),%r12
1340         mov     -32(%rax),%r13
1341         mov     -40(%rax),%r14
1342         mov     -48(%rax),%r15
1343         mov     %rbx,144($context)      # restore context->Rbx
1344         mov     %rbp,160($context)      # restore context->Rbp
1345         mov     %r12,216($context)      # restore context->R12
1346         mov     %r13,224($context)      # restore context->R13
1347         mov     %r14,232($context)      # restore context->R14
1348         mov     %r15,240($context)      # restore context->R15
1349
1350         jmp     .Lcommon_seh_tail
1351 .size   mul_handler,.-mul_handler
1352
1353 .type   sqr_handler,\@abi-omnipotent
1354 .align  16
1355 sqr_handler:
1356         push    %rsi
1357         push    %rdi
1358         push    %rbx
1359         push    %rbp
1360         push    %r12
1361         push    %r13
1362         push    %r14
1363         push    %r15
1364         pushfq
1365         sub     \$64,%rsp
1366
1367         mov     120($context),%rax      # pull context->Rax
1368         mov     248($context),%rbx      # pull context->Rip
1369
1370         mov     8($disp),%rsi           # disp->ImageBase
1371         mov     56($disp),%r11          # disp->HandlerData
1372
1373         mov     0(%r11),%r10d           # HandlerData[0]
1374         lea     (%rsi,%r10),%r10        # end of prologue label
1375         cmp     %r10,%rbx               # context->Rip<.Lsqr_body
1376         jb      .Lcommon_seh_tail
1377
1378         mov     152($context),%rax      # pull context->Rsp
1379
1380         mov     4(%r11),%r10d           # HandlerData[1]
1381         lea     (%rsi,%r10),%r10        # epilogue label
1382         cmp     %r10,%rbx               # context->Rip>=.Lsqr_epilogue
1383         jae     .Lcommon_seh_tail
1384
1385         mov     40(%rax),%rax           # pull saved stack pointer
1386
1387         mov     -8(%rax),%rbx
1388         mov     -16(%rax),%rbp
1389         mov     -24(%rax),%r12
1390         mov     -32(%rax),%r13
1391         mov     -40(%rax),%r14
1392         mov     -48(%rax),%r15
1393         mov     %rbx,144($context)      # restore context->Rbx
1394         mov     %rbp,160($context)      # restore context->Rbp
1395         mov     %r12,216($context)      # restore context->R12
1396         mov     %r13,224($context)      # restore context->R13
1397         mov     %r14,232($context)      # restore context->R14
1398         mov     %r15,240($context)      # restore context->R15
1399
1400 .Lcommon_seh_tail:
1401         mov     8(%rax),%rdi
1402         mov     16(%rax),%rsi
1403         mov     %rax,152($context)      # restore context->Rsp
1404         mov     %rsi,168($context)      # restore context->Rsi
1405         mov     %rdi,176($context)      # restore context->Rdi
1406
1407         mov     40($disp),%rdi          # disp->ContextRecord
1408         mov     $context,%rsi           # context
1409         mov     \$154,%ecx              # sizeof(CONTEXT)
1410         .long   0xa548f3fc              # cld; rep movsq
1411
1412         mov     $disp,%rsi
1413         xor     %rcx,%rcx               # arg1, UNW_FLAG_NHANDLER
1414         mov     8(%rsi),%rdx            # arg2, disp->ImageBase
1415         mov     0(%rsi),%r8             # arg3, disp->ControlPc
1416         mov     16(%rsi),%r9            # arg4, disp->FunctionEntry
1417         mov     40(%rsi),%r10           # disp->ContextRecord
1418         lea     56(%rsi),%r11           # &disp->HandlerData
1419         lea     24(%rsi),%r12           # &disp->EstablisherFrame
1420         mov     %r10,32(%rsp)           # arg5
1421         mov     %r11,40(%rsp)           # arg6
1422         mov     %r12,48(%rsp)           # arg7
1423         mov     %rcx,56(%rsp)           # arg8, (NULL)
1424         call    *__imp_RtlVirtualUnwind(%rip)
1425
1426         mov     \$1,%eax                # ExceptionContinueSearch
1427         add     \$64,%rsp
1428         popfq
1429         pop     %r15
1430         pop     %r14
1431         pop     %r13
1432         pop     %r12
1433         pop     %rbp
1434         pop     %rbx
1435         pop     %rdi
1436         pop     %rsi
1437         ret
1438 .size   sqr_handler,.-sqr_handler
1439
1440 .section        .pdata
1441 .align  4
1442         .rva    .LSEH_begin_bn_mul_mont
1443         .rva    .LSEH_end_bn_mul_mont
1444         .rva    .LSEH_info_bn_mul_mont
1445
1446         .rva    .LSEH_begin_bn_mul4x_mont
1447         .rva    .LSEH_end_bn_mul4x_mont
1448         .rva    .LSEH_info_bn_mul4x_mont
1449
1450         .rva    .LSEH_begin_bn_sqr8x_mont
1451         .rva    .LSEH_end_bn_sqr8x_mont
1452         .rva    .LSEH_info_bn_sqr8x_mont
1453 ___
1454 $code.=<<___ if ($addx);
1455         .rva    .LSEH_begin_bn_mulx4x_mont
1456         .rva    .LSEH_end_bn_mulx4x_mont
1457         .rva    .LSEH_info_bn_mulx4x_mont
1458 ___
1459 $code.=<<___;
1460 .section        .xdata
1461 .align  8
1462 .LSEH_info_bn_mul_mont:
1463         .byte   9,0,0,0
1464         .rva    mul_handler
1465         .rva    .Lmul_body,.Lmul_epilogue       # HandlerData[]
1466 .LSEH_info_bn_mul4x_mont:
1467         .byte   9,0,0,0
1468         .rva    mul_handler
1469         .rva    .Lmul4x_body,.Lmul4x_epilogue   # HandlerData[]
1470 .LSEH_info_bn_sqr8x_mont:
1471         .byte   9,0,0,0
1472         .rva    sqr_handler
1473         .rva    .Lsqr8x_body,.Lsqr8x_epilogue   # HandlerData[]
1474 ___
1475 $code.=<<___ if ($addx);
1476 .LSEH_info_bn_mulx4x_mont:
1477         .byte   9,0,0,0
1478         .rva    sqr_handler
1479         .rva    .Lmulx4x_body,.Lmulx4x_epilogue # HandlerData[]
1480 ___
1481 }
1482
1483 print $code;
1484 close STDOUT;