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