crypto/bn/asm/x86_64-mont.pl

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