crypto/bn/asm/x86_64-mont5.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 # August 2011.
  11 #
  12 # Companion to x86_64-mont.pl that optimizes cache-timing attack
  13 # countermeasures. The subroutines are produced by replacing bp[i]
  14 # references in their x86_64-mont.pl counterparts with cache-neutral
  15 # references to powers table computed in BN_mod_exp_mont_consttime.
  16 # In addition subroutine that scatters elements of the powers table
  17 # is implemented, so that scatter-/gathering can be tuned without
  18 # bn_exp.c modifications.
  19
  20 # August 2013.
  21 #
  22 # Add MULX/AD*X code paths and additional interfaces to optimize for
  23 # branch prediction unit. For input lengths that are multiples of 8
  24 # the np argument is not just modulus value, but one interleaved
  25 # with 0. This is to optimize post-condition...
  26
  27 $flavour = shift;
  28 $output  = shift;
  29 if ($flavour =~ /\./) { $output = $flavour; undef $flavour; }
  30
  31 $win64=0; $win64=1 if ($flavour =~ /[nm]asm|mingw64/ || $output =~ /\.asm$/);
  32
  33 $0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
  34 ( $xlate="${dir}x86_64-xlate.pl" and -f $xlate ) or
  35 ( $xlate="${dir}../../perlasm/x86_64-xlate.pl" and -f $xlate) or
  36 die "can't locate x86_64-xlate.pl";
  37
  38 open OUT,"| \"$^X\" $xlate $flavour $output";
  39 *STDOUT=*OUT;
  40
  41 if (`$ENV{CC} -Wa,-v -c -o /dev/null -x assembler /dev/null 2>&1`
  42                 =~ /GNU assembler version ([2-9]\.[0-9]+)/) {
  43         $addx = ($1>=2.23);
  44 }
  45
  46 if (!$addx && $win64 && ($flavour =~ /nasm/ || $ENV{ASM} =~ /nasm/) &&
  47             `nasm -v 2>&1` =~ /NASM version ([2-9]\.[0-9]+)/) {
  48         $addx = ($1>=2.10);
  49 }
  50
  51 if (!$addx && $win64 && ($flavour =~ /masm/ || $ENV{ASM} =~ /ml64/) &&
  52             `ml64 2>&1` =~ /Version ([0-9]+)\./) {
  53         $addx = ($1>=12);
  54 }
  55
  56 if (!$addx && `$ENV{CC} -v 2>&1` =~ /((?:^clang|LLVM) version|based on LLVM) ([3-9])\.([0-9]+)/) {
  57         my $ver = $2 + $3/100.0;        # 3.1->3.01, 3.10->3.10
  58         $addx = ($ver>=3.03);
  59 }
  60
  61 # int bn_mul_mont_gather5(
  62 $rp="%rdi";     # BN_ULONG *rp,
  63 $ap="%rsi";     # const BN_ULONG *ap,
  64 $bp="%rdx";     # const BN_ULONG *bp,
  65 $np="%rcx";     # const BN_ULONG *np,
  66 $n0="%r8";      # const BN_ULONG *n0,
  67 $num="%r9";     # int num,
  68                 # int idx);     # 0 to 2^5-1, "index" in $bp holding
  69                                 # pre-computed powers of a', interlaced
  70                                 # in such manner that b[0] is $bp[idx],
  71                                 # b[1] is [2^5+idx], etc.
  72 $lo0="%r10";
  73 $hi0="%r11";
  74 $hi1="%r13";
  75 $i="%r14";
  76 $j="%r15";
  77 $m0="%rbx";
  78 $m1="%rbp";
  79
  80 $code=<<___;
  81 .text
  82
  83 .extern OPENSSL_ia32cap_P
  84
  85 .globl  bn_mul_mont_gather5
  86 .type   bn_mul_mont_gather5,\@function,6
  87 .align  64
  88 bn_mul_mont_gather5:
  89         test    \$7,${num}d
  90         jnz     .Lmul_enter
  91 ___
  92 $code.=<<___ if ($addx);
  93         mov     OPENSSL_ia32cap_P+8(%rip),%r11d
  94 ___
  95 $code.=<<___;
  96         jmp     .Lmul4x_enter
  97
  98 .align  16
  99 .Lmul_enter:
 100         mov     ${num}d,${num}d
 101         mov     %rsp,%rax
 102         mov     `($win64?56:8)`(%rsp),%r10d     # load 7th argument
 103         push    %rbx
 104         push    %rbp
 105         push    %r12
 106         push    %r13
 107         push    %r14
 108         push    %r15
 109 ___
 110 $code.=<<___ if ($win64);
 111         lea     -0x28(%rsp),%rsp
 112         movaps  %xmm6,(%rsp)
 113         movaps  %xmm7,0x10(%rsp)
 114 ___
 115 $code.=<<___;
 116         lea     2($num),%r11
 117         neg     %r11
 118         lea     (%rsp,%r11,8),%rsp      # tp=alloca(8*(num+2))
 119         and     \$-1024,%rsp            # minimize TLB usage
 120
 121         mov     %rax,8(%rsp,$num,8)     # tp[num+1]=%rsp
 122 .Lmul_body:
 123         mov     $bp,%r12                # reassign $bp
 124 ___
 125                 $bp="%r12";
 126                 $STRIDE=2**5*8;         # 5 is "window size"
 127                 $N=$STRIDE/4;           # should match cache line size
 128 $code.=<<___;
 129         mov     %r10,%r11
 130         shr     \$`log($N/8)/log(2)`,%r10
 131         and     \$`$N/8-1`,%r11
 132         not     %r10
 133         lea     .Lmagic_masks(%rip),%rax
 134         and     \$`2**5/($N/8)-1`,%r10  # 5 is "window size"
 135         lea     96($bp,%r11,8),$bp      # pointer within 1st cache line
 136         movq    0(%rax,%r10,8),%xmm4    # set of masks denoting which
 137         movq    8(%rax,%r10,8),%xmm5    # cache line contains element
 138         movq    16(%rax,%r10,8),%xmm6   # denoted by 7th argument
 139         movq    24(%rax,%r10,8),%xmm7
 140
 141         movq    `0*$STRIDE/4-96`($bp),%xmm0
 142         movq    `1*$STRIDE/4-96`($bp),%xmm1
 143         pand    %xmm4,%xmm0
 144         movq    `2*$STRIDE/4-96`($bp),%xmm2
 145         pand    %xmm5,%xmm1
 146         movq    `3*$STRIDE/4-96`($bp),%xmm3
 147         pand    %xmm6,%xmm2
 148         por     %xmm1,%xmm0
 149         pand    %xmm7,%xmm3
 150         por     %xmm2,%xmm0
 151         lea     $STRIDE($bp),$bp
 152         por     %xmm3,%xmm0
 153
 154         movq    %xmm0,$m0               # m0=bp[0]
 155
 156         mov     ($n0),$n0               # pull n0[0] value
 157         mov     ($ap),%rax
 158
 159         xor     $i,$i                   # i=0
 160         xor     $j,$j                   # j=0
 161
 162         movq    `0*$STRIDE/4-96`($bp),%xmm0
 163         movq    `1*$STRIDE/4-96`($bp),%xmm1
 164         pand    %xmm4,%xmm0
 165         movq    `2*$STRIDE/4-96`($bp),%xmm2
 166         pand    %xmm5,%xmm1
 167
 168         mov     $n0,$m1
 169         mulq    $m0                     # ap[0]*bp[0]
 170         mov     %rax,$lo0
 171         mov     ($np),%rax
 172
 173         movq    `3*$STRIDE/4-96`($bp),%xmm3
 174         pand    %xmm6,%xmm2
 175         por     %xmm1,%xmm0
 176         pand    %xmm7,%xmm3
 177
 178         imulq   $lo0,$m1                # "tp[0]"*n0
 179         mov     %rdx,$hi0
 180
 181         por     %xmm2,%xmm0
 182         lea     $STRIDE($bp),$bp
 183         por     %xmm3,%xmm0
 184
 185         mulq    $m1                     # np[0]*m1
 186         add     %rax,$lo0               # discarded
 187         mov     8($ap),%rax
 188         adc     \$0,%rdx
 189         mov     %rdx,$hi1
 190
 191         lea     1($j),$j                # j++
 192         jmp     .L1st_enter
 193
 194 .align  16
 195 .L1st:
 196         add     %rax,$hi1
 197         mov     ($ap,$j,8),%rax
 198         adc     \$0,%rdx
 199         add     $hi0,$hi1               # np[j]*m1+ap[j]*bp[0]
 200         mov     $lo0,$hi0
 201         adc     \$0,%rdx
 202         mov     $hi1,-16(%rsp,$j,8)     # tp[j-1]
 203         mov     %rdx,$hi1
 204
 205 .L1st_enter:
 206         mulq    $m0                     # ap[j]*bp[0]
 207         add     %rax,$hi0
 208         mov     ($np,$j,8),%rax
 209         adc     \$0,%rdx
 210         lea     1($j),$j                # j++
 211         mov     %rdx,$lo0
 212
 213         mulq    $m1                     # np[j]*m1
 214         cmp     $num,$j
 215         jne     .L1st
 216
 217         movq    %xmm0,$m0               # bp[1]
 218
 219         add     %rax,$hi1
 220         mov     ($ap),%rax              # ap[0]
 221         adc     \$0,%rdx
 222         add     $hi0,$hi1               # np[j]*m1+ap[j]*bp[0]
 223         adc     \$0,%rdx
 224         mov     $hi1,-16(%rsp,$j,8)     # tp[j-1]
 225         mov     %rdx,$hi1
 226         mov     $lo0,$hi0
 227
 228         xor     %rdx,%rdx
 229         add     $hi0,$hi1
 230         adc     \$0,%rdx
 231         mov     $hi1,-8(%rsp,$num,8)
 232         mov     %rdx,(%rsp,$num,8)      # store upmost overflow bit
 233
 234         lea     1($i),$i                # i++
 235         jmp     .Louter
 236 .align  16
 237 .Louter:
 238         xor     $j,$j                   # j=0
 239         mov     $n0,$m1
 240         mov     (%rsp),$lo0
 241
 242         movq    `0*$STRIDE/4-96`($bp),%xmm0
 243         movq    `1*$STRIDE/4-96`($bp),%xmm1
 244         pand    %xmm4,%xmm0
 245         movq    `2*$STRIDE/4-96`($bp),%xmm2
 246         pand    %xmm5,%xmm1
 247
 248         mulq    $m0                     # ap[0]*bp[i]
 249         add     %rax,$lo0               # ap[0]*bp[i]+tp[0]
 250         mov     ($np),%rax
 251         adc     \$0,%rdx
 252
 253         movq    `3*$STRIDE/4-96`($bp),%xmm3
 254         pand    %xmm6,%xmm2
 255         por     %xmm1,%xmm0
 256         pand    %xmm7,%xmm3
 257
 258         imulq   $lo0,$m1                # tp[0]*n0
 259         mov     %rdx,$hi0
 260
 261         por     %xmm2,%xmm0
 262         lea     $STRIDE($bp),$bp
 263         por     %xmm3,%xmm0
 264
 265         mulq    $m1                     # np[0]*m1
 266         add     %rax,$lo0               # discarded
 267         mov     8($ap),%rax
 268         adc     \$0,%rdx
 269         mov     8(%rsp),$lo0            # tp[1]
 270         mov     %rdx,$hi1
 271
 272         lea     1($j),$j                # j++
 273         jmp     .Linner_enter
 274
 275 .align  16
 276 .Linner:
 277         add     %rax,$hi1
 278         mov     ($ap,$j,8),%rax
 279         adc     \$0,%rdx
 280         add     $lo0,$hi1               # np[j]*m1+ap[j]*bp[i]+tp[j]
 281         mov     (%rsp,$j,8),$lo0
 282         adc     \$0,%rdx
 283         mov     $hi1,-16(%rsp,$j,8)     # tp[j-1]
 284         mov     %rdx,$hi1
 285
 286 .Linner_enter:
 287         mulq    $m0                     # ap[j]*bp[i]
 288         add     %rax,$hi0
 289         mov     ($np,$j,8),%rax
 290         adc     \$0,%rdx
 291         add     $hi0,$lo0               # ap[j]*bp[i]+tp[j]
 292         mov     %rdx,$hi0
 293         adc     \$0,$hi0
 294         lea     1($j),$j                # j++
 295
 296         mulq    $m1                     # np[j]*m1
 297         cmp     $num,$j
 298         jne     .Linner
 299
 300         movq    %xmm0,$m0               # bp[i+1]
 301
 302         add     %rax,$hi1
 303         mov     ($ap),%rax              # ap[0]
 304         adc     \$0,%rdx
 305         add     $lo0,$hi1               # np[j]*m1+ap[j]*bp[i]+tp[j]
 306         mov     (%rsp,$j,8),$lo0
 307         adc     \$0,%rdx
 308         mov     $hi1,-16(%rsp,$j,8)     # tp[j-1]
 309         mov     %rdx,$hi1
 310
 311         xor     %rdx,%rdx
 312         add     $hi0,$hi1
 313         adc     \$0,%rdx
 314         add     $lo0,$hi1               # pull upmost overflow bit
 315         adc     \$0,%rdx
 316         mov     $hi1,-8(%rsp,$num,8)
 317         mov     %rdx,(%rsp,$num,8)      # store upmost overflow bit
 318
 319         lea     1($i),$i                # i++
 320         cmp     $num,$i
 321         jb      .Louter
 322
 323         xor     $i,$i                   # i=0 and clear CF!
 324         mov     (%rsp),%rax             # tp[0]
 325         lea     (%rsp),$ap              # borrow ap for tp
 326         mov     $num,$j                 # j=num
 327         jmp     .Lsub
 328 .align  16
 329 .Lsub:  sbb     ($np,$i,8),%rax
 330         mov     %rax,($rp,$i,8)         # rp[i]=tp[i]-np[i]
 331         mov     8($ap,$i,8),%rax        # tp[i+1]
 332         lea     1($i),$i                # i++
 333         dec     $j                      # doesnn't affect CF!
 334         jnz     .Lsub
 335
 336         sbb     \$0,%rax                # handle upmost overflow bit
 337         xor     $i,$i
 338         and     %rax,$ap
 339         not     %rax
 340         mov     $rp,$np
 341         and     %rax,$np
 342         mov     $num,$j                 # j=num
 343         or      $np,$ap                 # ap=borrow?tp:rp
 344 .align  16
 345 .Lcopy:                                 # copy or in-place refresh
 346         mov     ($ap,$i,8),%rax
 347         mov     $i,(%rsp,$i,8)          # zap temporary vector
 348         mov     %rax,($rp,$i,8)         # rp[i]=tp[i]
 349         lea     1($i),$i
 350         sub     \$1,$j
 351         jnz     .Lcopy
 352
 353         mov     8(%rsp,$num,8),%rsi     # restore %rsp
 354         mov     \$1,%rax
 355 ___
 356 $code.=<<___ if ($win64);
 357         movaps  -88(%rsi),%xmm6
 358         movaps  -72(%rsi),%xmm7
 359 ___
 360 $code.=<<___;
 361         mov     -48(%rsi),%r15
 362         mov     -40(%rsi),%r14
 363         mov     -32(%rsi),%r13
 364         mov     -24(%rsi),%r12
 365         mov     -16(%rsi),%rbp
 366         mov     -8(%rsi),%rbx
 367         lea     (%rsi),%rsp
 368 .Lmul_epilogue:
 369         ret
 370 .size   bn_mul_mont_gather5,.-bn_mul_mont_gather5
 371 ___
 372 {{{
 373 my @A=("%r10","%r11");
 374 my @N=("%r13","%rdi");
 375 $code.=<<___;
 376 .type   bn_mul4x_mont_gather5,\@function,6
 377 .align  32
 378 bn_mul4x_mont_gather5:
 379 .Lmul4x_enter:
 380 ___
 381 $code.=<<___ if ($addx);
 382         and     \$0x80100,%r11d
 383         cmp     \$0x80100,%r11d
 384         je      .Lmulx4x_enter
 385 ___
 386 $code.=<<___;
 387         .byte   0x67
 388         mov     %rsp,%rax
 389         push    %rbx
 390         push    %rbp
 391         push    %r12
 392         push    %r13
 393         push    %r14
 394         push    %r15
 395 ___
 396 $code.=<<___ if ($win64);
 397         lea     -0x28(%rsp),%rsp
 398         movaps  %xmm6,(%rsp)
 399         movaps  %xmm7,0x10(%rsp)
 400 ___
 401 $code.=<<___;
 402         .byte   0x67
 403         mov     ${num}d,%r10d
 404         shl     \$3,${num}d
 405         shl     \$3+2,%r10d             # 4*$num
 406         neg     $num                    # -$num
 407
 408         ##############################################################
 409         # ensure that stack frame doesn't alias with $aptr+4*$num
 410         # modulo 4096, which covers ret[num], am[num] and n[2*num]
 411         # (see bn_exp.c). this is done to allow memory disambiguation
 412         # logic do its magic. [excessive frame is allocated in order
 413         # to allow bn_from_mont8x to clear it.]
 414         #
 415         lea     -64(%rsp,$num,2),%r11
 416         sub     $ap,%r11
 417         and     \$4095,%r11
 418         cmp     %r11,%r10
 419         jb      .Lmul4xsp_alt
 420         sub     %r11,%rsp               # align with $ap
 421         lea     -64(%rsp,$num,2),%rsp   # alloca(128+num*8)
 422         jmp     .Lmul4xsp_done
 423
 424 .align  32
 425 .Lmul4xsp_alt:
 426         lea     4096-64(,$num,2),%r10
 427         lea     -64(%rsp,$num,2),%rsp   # alloca(128+num*8)
 428         sub     %r10,%r11
 429         mov     \$0,%r10
 430         cmovc   %r10,%r11
 431         sub     %r11,%rsp
 432 .Lmul4xsp_done:
 433         and     \$-64,%rsp
 434         neg     $num
 435
 436         mov     %rax,40(%rsp)
 437 .Lmul4x_body:
 438
 439         call    mul4x_internal
 440
 441         mov     40(%rsp),%rsi           # restore %rsp
 442         mov     \$1,%rax
 443 ___
 444 $code.=<<___ if ($win64);
 445         movaps  -88(%rsi),%xmm6
 446         movaps  -72(%rsi),%xmm7
 447 ___
 448 $code.=<<___;
 449         mov     -48(%rsi),%r15
 450         mov     -40(%rsi),%r14
 451         mov     -32(%rsi),%r13
 452         mov     -24(%rsi),%r12
 453         mov     -16(%rsi),%rbp
 454         mov     -8(%rsi),%rbx
 455         lea     (%rsi),%rsp
 456 .Lmul4x_epilogue:
 457         ret
 458 .size   bn_mul4x_mont_gather5,.-bn_mul4x_mont_gather5
 459
 460 .type   mul4x_internal,\@abi-omnipotent
 461 .align  32
 462 mul4x_internal:
 463         shl     \$5,$num
 464         mov     `($win64?56:8)`(%rax),%r10d     # load 7th argument
 465         lea     256(%rdx,$num),%r13
 466         shr     \$5,$num                # restore $num
 467 ___
 468                 $bp="%r12";
 469                 $STRIDE=2**5*8;         # 5 is "window size"
 470                 $N=$STRIDE/4;           # should match cache line size
 471                 $tp=$i;
 472 $code.=<<___;
 473         mov     %r10,%r11
 474         shr     \$`log($N/8)/log(2)`,%r10
 475         and     \$`$N/8-1`,%r11
 476         not     %r10
 477         lea     .Lmagic_masks(%rip),%rax
 478         and     \$`2**5/($N/8)-1`,%r10  # 5 is "window size"
 479         lea     96(%rdx,%r11,8),$bp     # pointer within 1st cache line
 480         movq    0(%rax,%r10,8),%xmm4    # set of masks denoting which
 481         movq    8(%rax,%r10,8),%xmm5    # cache line contains element
 482         add     \$7,%r11
 483         movq    16(%rax,%r10,8),%xmm6   # denoted by 7th argument
 484         movq    24(%rax,%r10,8),%xmm7
 485         and     \$7,%r11
 486
 487         movq    `0*$STRIDE/4-96`($bp),%xmm0
 488         lea     $STRIDE($bp),$tp        # borrow $tp
 489         movq    `1*$STRIDE/4-96`($bp),%xmm1
 490         pand    %xmm4,%xmm0
 491         movq    `2*$STRIDE/4-96`($bp),%xmm2
 492         pand    %xmm5,%xmm1
 493         movq    `3*$STRIDE/4-96`($bp),%xmm3
 494         pand    %xmm6,%xmm2
 495         .byte   0x67
 496         por     %xmm1,%xmm0
 497         movq    `0*$STRIDE/4-96`($tp),%xmm1
 498         .byte   0x67
 499         pand    %xmm7,%xmm3
 500         .byte   0x67
 501         por     %xmm2,%xmm0
 502         movq    `1*$STRIDE/4-96`($tp),%xmm2
 503         .byte   0x67
 504         pand    %xmm4,%xmm1
 505         .byte   0x67
 506         por     %xmm3,%xmm0
 507         movq    `2*$STRIDE/4-96`($tp),%xmm3
 508
 509         movq    %xmm0,$m0               # m0=bp[0]
 510         movq    `3*$STRIDE/4-96`($tp),%xmm0
 511         mov     %r13,16+8(%rsp)         # save end of b[num]
 512         mov     $rp, 56+8(%rsp)         # save $rp
 513
 514         mov     ($n0),$n0               # pull n0[0] value
 515         mov     ($ap),%rax
 516         lea     ($ap,$num),$ap          # end of a[num]
 517         neg     $num
 518
 519         mov     $n0,$m1
 520         mulq    $m0                     # ap[0]*bp[0]
 521         mov     %rax,$A[0]
 522         mov     ($np),%rax
 523
 524         pand    %xmm5,%xmm2
 525         pand    %xmm6,%xmm3
 526         por     %xmm2,%xmm1
 527
 528         imulq   $A[0],$m1               # "tp[0]"*n0
 529         ##############################################################
 530         # $tp is chosen so that writing to top-most element of the
 531         # vector occurs just "above" references to powers table,
 532         # "above" modulo cache-line size, which effectively precludes
 533         # possibility of memory disambiguation logic failure when
 534         # accessing the table.
 535         #
 536         lea     64+8(%rsp,%r11,8),$tp
 537         mov     %rdx,$A[1]
 538
 539         pand    %xmm7,%xmm0
 540         por     %xmm3,%xmm1
 541         lea     2*$STRIDE($bp),$bp
 542         por     %xmm1,%xmm0
 543
 544         mulq    $m1                     # np[0]*m1
 545         add     %rax,$A[0]              # discarded
 546         mov     8($ap,$num),%rax
 547         adc     \$0,%rdx
 548         mov     %rdx,$N[1]
 549
 550         mulq    $m0
 551         add     %rax,$A[1]
 552         mov     16*1($np),%rax          # interleaved with 0, therefore 16*n
 553         adc     \$0,%rdx
 554         mov     %rdx,$A[0]
 555
 556         mulq    $m1
 557         add     %rax,$N[1]
 558         mov     16($ap,$num),%rax
 559         adc     \$0,%rdx
 560         add     $A[1],$N[1]
 561         lea     4*8($num),$j            # j=4
 562         lea     16*4($np),$np
 563         adc     \$0,%rdx
 564         mov     $N[1],($tp)
 565         mov     %rdx,$N[0]
 566         jmp     .L1st4x
 567
 568 .align  32
 569 .L1st4x:
 570         mulq    $m0                     # ap[j]*bp[0]
 571         add     %rax,$A[0]
 572         mov     -16*2($np),%rax
 573         lea     32($tp),$tp
 574         adc     \$0,%rdx
 575         mov     %rdx,$A[1]
 576
 577         mulq    $m1                     # np[j]*m1
 578         add     %rax,$N[0]
 579         mov     -8($ap,$j),%rax
 580         adc     \$0,%rdx
 581         add     $A[0],$N[0]             # np[j]*m1+ap[j]*bp[0]
 582         adc     \$0,%rdx
 583         mov     $N[0],-24($tp)          # tp[j-1]
 584         mov     %rdx,$N[1]
 585
 586         mulq    $m0                     # ap[j]*bp[0]
 587         add     %rax,$A[1]
 588         mov     -16*1($np),%rax
 589         adc     \$0,%rdx
 590         mov     %rdx,$A[0]
 591
 592         mulq    $m1                     # np[j]*m1
 593         add     %rax,$N[1]
 594         mov     ($ap,$j),%rax
 595         adc     \$0,%rdx
 596         add     $A[1],$N[1]             # np[j]*m1+ap[j]*bp[0]
 597         adc     \$0,%rdx
 598         mov     $N[1],-16($tp)          # tp[j-1]
 599         mov     %rdx,$N[0]
 600
 601         mulq    $m0                     # ap[j]*bp[0]
 602         add     %rax,$A[0]
 603         mov     16*0($np),%rax
 604         adc     \$0,%rdx
 605         mov     %rdx,$A[1]
 606
 607         mulq    $m1                     # np[j]*m1
 608         add     %rax,$N[0]
 609         mov     8($ap,$j),%rax
 610         adc     \$0,%rdx
 611         add     $A[0],$N[0]             # np[j]*m1+ap[j]*bp[0]
 612         adc     \$0,%rdx
 613         mov     $N[0],-8($tp)           # tp[j-1]
 614         mov     %rdx,$N[1]
 615
 616         mulq    $m0                     # ap[j]*bp[0]
 617         add     %rax,$A[1]
 618         mov     16*1($np),%rax
 619         adc     \$0,%rdx
 620         mov     %rdx,$A[0]
 621
 622         mulq    $m1                     # np[j]*m1
 623         add     %rax,$N[1]
 624         mov     16($ap,$j),%rax
 625         adc     \$0,%rdx
 626         add     $A[1],$N[1]             # np[j]*m1+ap[j]*bp[0]
 627         lea     16*4($np),$np
 628         adc     \$0,%rdx
 629         mov     $N[1],($tp)             # tp[j-1]
 630         mov     %rdx,$N[0]
 631
 632         add     \$32,$j                 # j+=4
 633         jnz     .L1st4x
 634
 635         mulq    $m0                     # ap[j]*bp[0]
 636         add     %rax,$A[0]
 637         mov     -16*2($np),%rax
 638         lea     32($tp),$tp
 639         adc     \$0,%rdx
 640         mov     %rdx,$A[1]
 641
 642         mulq    $m1                     # np[j]*m1
 643         add     %rax,$N[0]
 644         mov     -8($ap),%rax
 645         adc     \$0,%rdx
 646         add     $A[0],$N[0]             # np[j]*m1+ap[j]*bp[0]
 647         adc     \$0,%rdx
 648         mov     $N[0],-24($tp)          # tp[j-1]
 649         mov     %rdx,$N[1]
 650
 651         mulq    $m0                     # ap[j]*bp[0]
 652         add     %rax,$A[1]
 653         mov     -16*1($np),%rax
 654         adc     \$0,%rdx
 655         mov     %rdx,$A[0]
 656
 657         mulq    $m1                     # np[j]*m1
 658         add     %rax,$N[1]
 659         mov     ($ap,$num),%rax         # ap[0]
 660         adc     \$0,%rdx
 661         add     $A[1],$N[1]             # np[j]*m1+ap[j]*bp[0]
 662         adc     \$0,%rdx
 663         mov     $N[1],-16($tp)          # tp[j-1]
 664         mov     %rdx,$N[0]
 665
 666         movq    %xmm0,$m0               # bp[1]
 667         lea     ($np,$num,2),$np        # rewind $np
 668
 669         xor     $N[1],$N[1]
 670         add     $A[0],$N[0]
 671         adc     \$0,$N[1]
 672         mov     $N[0],-8($tp)
 673
 674         jmp     .Louter4x
 675
 676 .align  32
 677 .Louter4x:
 678         mov     ($tp,$num),$A[0]
 679         mov     $n0,$m1
 680         mulq    $m0                     # ap[0]*bp[i]
 681         add     %rax,$A[0]              # ap[0]*bp[i]+tp[0]
 682         mov     ($np),%rax
 683         adc     \$0,%rdx
 684
 685         movq    `0*$STRIDE/4-96`($bp),%xmm0
 686         movq    `1*$STRIDE/4-96`($bp),%xmm1
 687         pand    %xmm4,%xmm0
 688         movq    `2*$STRIDE/4-96`($bp),%xmm2
 689         pand    %xmm5,%xmm1
 690         movq    `3*$STRIDE/4-96`($bp),%xmm3
 691
 692         imulq   $A[0],$m1               # tp[0]*n0
 693         .byte   0x67
 694         mov     %rdx,$A[1]
 695         mov     $N[1],($tp)             # store upmost overflow bit
 696
 697         pand    %xmm6,%xmm2
 698         por     %xmm1,%xmm0
 699         pand    %xmm7,%xmm3
 700         por     %xmm2,%xmm0
 701         lea     ($tp,$num),$tp          # rewind $tp
 702         lea     $STRIDE($bp),$bp
 703         por     %xmm3,%xmm0
 704
 705         mulq    $m1                     # np[0]*m1
 706         add     %rax,$A[0]              # "$N[0]", discarded
 707         mov     8($ap,$num),%rax
 708         adc     \$0,%rdx
 709         mov     %rdx,$N[1]
 710
 711         mulq    $m0                     # ap[j]*bp[i]
 712         add     %rax,$A[1]
 713         mov     16*1($np),%rax          # interleaved with 0, therefore 16*n
 714         adc     \$0,%rdx
 715         add     8($tp),$A[1]            # +tp[1]
 716         adc     \$0,%rdx
 717         mov     %rdx,$A[0]
 718
 719         mulq    $m1                     # np[j]*m1
 720         add     %rax,$N[1]
 721         mov     16($ap,$num),%rax
 722         adc     \$0,%rdx
 723         add     $A[1],$N[1]             # np[j]*m1+ap[j]*bp[i]+tp[j]
 724         lea     4*8($num),$j            # j=4
 725         lea     16*4($np),$np
 726         adc     \$0,%rdx
 727         mov     %rdx,$N[0]
 728         jmp     .Linner4x
 729
 730 .align  32
 731 .Linner4x:
 732         mulq    $m0                     # ap[j]*bp[i]
 733         add     %rax,$A[0]
 734         mov     -16*2($np),%rax
 735         adc     \$0,%rdx
 736         add     16($tp),$A[0]           # ap[j]*bp[i]+tp[j]
 737         lea     32($tp),$tp
 738         adc     \$0,%rdx
 739         mov     %rdx,$A[1]
 740
 741         mulq    $m1                     # np[j]*m1
 742         add     %rax,$N[0]
 743         mov     -8($ap,$j),%rax
 744         adc     \$0,%rdx
 745         add     $A[0],$N[0]
 746         adc     \$0,%rdx
 747         mov     $N[1],-32($tp)          # tp[j-1]
 748         mov     %rdx,$N[1]
 749
 750         mulq    $m0                     # ap[j]*bp[i]
 751         add     %rax,$A[1]
 752         mov     -16*1($np),%rax
 753         adc     \$0,%rdx
 754         add     -8($tp),$A[1]
 755         adc     \$0,%rdx
 756         mov     %rdx,$A[0]
 757
 758         mulq    $m1                     # np[j]*m1
 759         add     %rax,$N[1]
 760         mov     ($ap,$j),%rax
 761         adc     \$0,%rdx
 762         add     $A[1],$N[1]
 763         adc     \$0,%rdx
 764         mov     $N[0],-24($tp)          # tp[j-1]
 765         mov     %rdx,$N[0]
 766
 767         mulq    $m0                     # ap[j]*bp[i]
 768         add     %rax,$A[0]
 769         mov     16*0($np),%rax
 770         adc     \$0,%rdx
 771         add     ($tp),$A[0]             # ap[j]*bp[i]+tp[j]
 772         adc     \$0,%rdx
 773         mov     %rdx,$A[1]
 774
 775         mulq    $m1                     # np[j]*m1
 776         add     %rax,$N[0]
 777         mov     8($ap,$j),%rax
 778         adc     \$0,%rdx
 779         add     $A[0],$N[0]
 780         adc     \$0,%rdx
 781         mov     $N[1],-16($tp)          # tp[j-1]
 782         mov     %rdx,$N[1]
 783
 784         mulq    $m0                     # ap[j]*bp[i]
 785         add     %rax,$A[1]
 786         mov     16*1($np),%rax
 787         adc     \$0,%rdx
 788         add     8($tp),$A[1]
 789         adc     \$0,%rdx
 790         mov     %rdx,$A[0]
 791
 792         mulq    $m1                     # np[j]*m1
 793         add     %rax,$N[1]
 794         mov     16($ap,$j),%rax
 795         adc     \$0,%rdx
 796         add     $A[1],$N[1]
 797         lea     16*4($np),$np
 798         adc     \$0,%rdx
 799         mov     $N[0],-8($tp)           # tp[j-1]
 800         mov     %rdx,$N[0]
 801
 802         add     \$32,$j                 # j+=4
 803         jnz     .Linner4x
 804
 805         mulq    $m0                     # ap[j]*bp[i]
 806         add     %rax,$A[0]
 807         mov     -16*2($np),%rax
 808         adc     \$0,%rdx
 809         add     16($tp),$A[0]           # ap[j]*bp[i]+tp[j]
 810         lea     32($tp),$tp
 811         adc     \$0,%rdx
 812         mov     %rdx,$A[1]
 813
 814         mulq    $m1                     # np[j]*m1
 815         add     %rax,$N[0]
 816         mov     -8($ap),%rax
 817         adc     \$0,%rdx
 818         add     $A[0],$N[0]
 819         adc     \$0,%rdx
 820         mov     $N[1],-32($tp)          # tp[j-1]
 821         mov     %rdx,$N[1]
 822
 823         mulq    $m0                     # ap[j]*bp[i]
 824         add     %rax,$A[1]
 825         mov     $m1,%rax
 826         mov     -16*1($np),$m1
 827         adc     \$0,%rdx
 828         add     -8($tp),$A[1]
 829         adc     \$0,%rdx
 830         mov     %rdx,$A[0]
 831
 832         mulq    $m1                     # np[j]*m1
 833         add     %rax,$N[1]
 834         mov     ($ap,$num),%rax         # ap[0]
 835         adc     \$0,%rdx
 836         add     $A[1],$N[1]
 837         adc     \$0,%rdx
 838         mov     $N[0],-24($tp)          # tp[j-1]
 839         mov     %rdx,$N[0]
 840
 841         movq    %xmm0,$m0               # bp[i+1]
 842         mov     $N[1],-16($tp)          # tp[j-1]
 843         lea     ($np,$num,2),$np        # rewind $np
 844
 845         xor     $N[1],$N[1]
 846         add     $A[0],$N[0]
 847         adc     \$0,$N[1]
 848         add     ($tp),$N[0]             # pull upmost overflow bit
 849         adc     \$0,$N[1]               # upmost overflow bit
 850         mov     $N[0],-8($tp)
 851
 852         cmp     16+8(%rsp),$bp
 853         jb      .Louter4x
 854 ___
 855 if (1) {
 856 $code.=<<___;
 857         sub     $N[0],$m1               # compare top-most words
 858         adc     $j,$j                   # $j is zero
 859         or      $j,$N[1]
 860         xor     \$1,$N[1]
 861         lea     ($tp,$num),%rbx         # tptr in .sqr4x_sub
 862         lea     ($np,$N[1],8),%rbp      # nptr in .sqr4x_sub
 863         mov     %r9,%rcx
 864         sar     \$3+2,%rcx              # cf=0
 865         mov     56+8(%rsp),%rdi         # rptr in .sqr4x_sub
 866         jmp     .Lsqr4x_sub
 867 ___
 868 } else {
 869 my @ri=("%rax",$bp,$m0,$m1);
 870 my $rp="%rdx";
 871 $code.=<<___
 872         xor     \$1,$N[1]
 873         lea     ($tp,$num),$tp          # rewind $tp
 874         sar     \$5,$num                # cf=0
 875         lea     ($np,$N[1],8),$np
 876         mov     56+8(%rsp),$rp          # restore $rp
 877         jmp     .Lsub4x
 878
 879 .align  32
 880 .Lsub4x:
 881         .byte   0x66
 882         mov     8*0($tp),@ri[0]
 883         mov     8*1($tp),@ri[1]
 884         .byte   0x66
 885         sbb     16*0($np),@ri[0]
 886         mov     8*2($tp),@ri[2]
 887         sbb     16*1($np),@ri[1]
 888         mov     3*8($tp),@ri[3]
 889         lea     4*8($tp),$tp
 890         sbb     16*2($np),@ri[2]
 891         mov     @ri[0],8*0($rp)
 892         sbb     16*3($np),@ri[3]
 893         lea     16*4($np),$np
 894         mov     @ri[1],8*1($rp)
 895         mov     @ri[2],8*2($rp)
 896         mov     @ri[3],8*3($rp)
 897         lea     8*4($rp),$rp
 898
 899         inc     $num
 900         jnz     .Lsub4x
 901
 902         ret
 903 ___
 904 }
 905 $code.=<<___;
 906 .size   mul4x_internal,.-mul4x_internal
 907 ___
 908 }}}
 909 \f{{{
 910 ######################################################################
 911 # void bn_power5(
 912 my $rptr="%rdi";        # BN_ULONG *rptr,
 913 my $aptr="%rsi";        # const BN_ULONG *aptr,
 914 my $bptr="%rdx";        # const void *table,
 915 my $nptr="%rcx";        # const BN_ULONG *nptr,
 916 my $n0  ="%r8";         # const BN_ULONG *n0);
 917 my $num ="%r9";         # int num, has to be divisible by 8
 918                         # int pwr
 919
 920 my ($i,$j,$tptr)=("%rbp","%rcx",$rptr);
 921 my @A0=("%r10","%r11");
 922 my @A1=("%r12","%r13");
 923 my ($a0,$a1,$ai)=("%r14","%r15","%rbx");
 924
 925 $code.=<<___;
 926 .globl  bn_power5
 927 .type   bn_power5,\@function,6
 928 .align  32
 929 bn_power5:
 930 ___
 931 $code.=<<___ if ($addx);
 932         mov     OPENSSL_ia32cap_P+8(%rip),%r11d
 933         and     \$0x80100,%r11d
 934         cmp     \$0x80100,%r11d
 935         je      .Lpowerx5_enter
 936 ___
 937 $code.=<<___;
 938         mov     %rsp,%rax
 939         push    %rbx
 940         push    %rbp
 941         push    %r12
 942         push    %r13
 943         push    %r14
 944         push    %r15
 945 ___
 946 $code.=<<___ if ($win64);
 947         lea     -0x28(%rsp),%rsp
 948         movaps  %xmm6,(%rsp)
 949         movaps  %xmm7,0x10(%rsp)
 950 ___
 951 $code.=<<___;
 952         mov     ${num}d,%r10d
 953         shl     \$3,${num}d             # convert $num to bytes
 954         shl     \$3+2,%r10d             # 4*$num
 955         neg     $num
 956         mov     ($n0),$n0               # *n0
 957
 958         ##############################################################
 959         # ensure that stack frame doesn't alias with $aptr+4*$num
 960         # modulo 4096, which covers ret[num], am[num] and n[2*num]
 961         # (see bn_exp.c). this is done to allow memory disambiguation
 962         # logic do its magic.
 963         #
 964         lea     -64(%rsp,$num,2),%r11
 965         sub     $aptr,%r11
 966         and     \$4095,%r11
 967         cmp     %r11,%r10
 968         jb      .Lpwr_sp_alt
 969         sub     %r11,%rsp               # align with $aptr
 970         lea     -64(%rsp,$num,2),%rsp   # alloca(frame+2*$num)
 971         jmp     .Lpwr_sp_done
 972
 973 .align  32
 974 .Lpwr_sp_alt:
 975         lea     4096-64(,$num,2),%r10   # 4096-frame-2*$num
 976         lea     -64(%rsp,$num,2),%rsp   # alloca(frame+2*$num)
 977         sub     %r10,%r11
 978         mov     \$0,%r10
 979         cmovc   %r10,%r11
 980         sub     %r11,%rsp
 981 .Lpwr_sp_done:
 982         and     \$-64,%rsp
 983         mov     $num,%r10
 984         neg     $num
 985
 986         ##############################################################
 987         # Stack layout
 988         #
 989         # +0    saved $num, used in reduction section
 990         # +8    &t[2*$num], used in reduction section
 991         # +32   saved *n0
 992         # +40   saved %rsp
 993         # +48   t[2*$num]
 994         #
 995         mov     $n0,  32(%rsp)
 996         mov     %rax, 40(%rsp)          # save original %rsp
 997 .Lpower5_body:
 998         movq    $rptr,%xmm1             # save $rptr
 999         movq    $nptr,%xmm2             # save $nptr
1000         movq    %r10, %xmm3             # -$num
1001         movq    $bptr,%xmm4
1002
1003         call    __bn_sqr8x_internal
1004         call    __bn_sqr8x_internal
1005         call    __bn_sqr8x_internal
1006         call    __bn_sqr8x_internal
1007         call    __bn_sqr8x_internal
1008
1009         movq    %xmm2,$nptr
1010         movq    %xmm4,$bptr
1011         mov     $aptr,$rptr
1012         mov     40(%rsp),%rax
1013         lea     32(%rsp),$n0
1014
1015         call    mul4x_internal
1016
1017         mov     40(%rsp),%rsi           # restore %rsp
1018         mov     \$1,%rax
1019         mov     -48(%rsi),%r15
1020         mov     -40(%rsi),%r14
1021         mov     -32(%rsi),%r13
1022         mov     -24(%rsi),%r12
1023         mov     -16(%rsi),%rbp
1024         mov     -8(%rsi),%rbx
1025         lea     (%rsi),%rsp
1026 .Lpower5_epilogue:
1027         ret
1028 .size   bn_power5,.-bn_power5
1029
1030 .globl  bn_sqr8x_internal
1031 .hidden bn_sqr8x_internal
1032 .type   bn_sqr8x_internal,\@abi-omnipotent
1033 .align  32
1034 bn_sqr8x_internal:
1035 __bn_sqr8x_internal:
1036         ##############################################################
1037         # Squaring part:
1038         #
1039         # a) multiply-n-add everything but a[i]*a[i];
1040         # b) shift result of a) by 1 to the left and accumulate
1041         #    a[i]*a[i] products;
1042         #
1043         ##############################################################
1044         #                                                     a[1]a[0]
1045         #                                                 a[2]a[0]
1046         #                                             a[3]a[0]
1047         #                                             a[2]a[1]
1048         #                                         a[4]a[0]
1049         #                                         a[3]a[1]
1050         #                                     a[5]a[0]
1051         #                                     a[4]a[1]
1052         #                                     a[3]a[2]
1053         #                                 a[6]a[0]
1054         #                                 a[5]a[1]
1055         #                                 a[4]a[2]
1056         #                             a[7]a[0]
1057         #                             a[6]a[1]
1058         #                             a[5]a[2]
1059         #                             a[4]a[3]
1060         #                         a[7]a[1]
1061         #                         a[6]a[2]
1062         #                         a[5]a[3]
1063         #                     a[7]a[2]
1064         #                     a[6]a[3]
1065         #                     a[5]a[4]
1066         #                 a[7]a[3]
1067         #                 a[6]a[4]
1068         #             a[7]a[4]
1069         #             a[6]a[5]
1070         #         a[7]a[5]
1071         #     a[7]a[6]
1072         #                                                     a[1]a[0]
1073         #                                                 a[2]a[0]
1074         #                                             a[3]a[0]
1075         #                                         a[4]a[0]
1076         #                                     a[5]a[0]
1077         #                                 a[6]a[0]
1078         #                             a[7]a[0]
1079         #                                             a[2]a[1]
1080         #                                         a[3]a[1]
1081         #                                     a[4]a[1]
1082         #                                 a[5]a[1]
1083         #                             a[6]a[1]
1084         #                         a[7]a[1]
1085         #                                     a[3]a[2]
1086         #                                 a[4]a[2]
1087         #                             a[5]a[2]
1088         #                         a[6]a[2]
1089         #                     a[7]a[2]
1090         #                             a[4]a[3]
1091         #                         a[5]a[3]
1092         #                     a[6]a[3]
1093         #                 a[7]a[3]
1094         #                     a[5]a[4]
1095         #                 a[6]a[4]
1096         #             a[7]a[4]
1097         #             a[6]a[5]
1098         #         a[7]a[5]
1099         #     a[7]a[6]
1100         #                                                         a[0]a[0]
1101         #                                                 a[1]a[1]
1102         #                                         a[2]a[2]
1103         #                                 a[3]a[3]
1104         #                         a[4]a[4]
1105         #                 a[5]a[5]
1106         #         a[6]a[6]
1107         # a[7]a[7]
1108
1109         lea     32(%r10),$i             # $i=-($num-32)
1110         lea     ($aptr,$num),$aptr      # end of a[] buffer, ($aptr,$i)=&ap[2]
1111
1112         mov     $num,$j                 # $j=$num
1113
1114                                         # comments apply to $num==8 case
1115         mov     -32($aptr,$i),$a0       # a[0]
1116         lea     48+8(%rsp,$num,2),$tptr # end of tp[] buffer, &tp[2*$num]
1117         mov     -24($aptr,$i),%rax      # a[1]
1118         lea     -32($tptr,$i),$tptr     # end of tp[] window, &tp[2*$num-"$i"]
1119         mov     -16($aptr,$i),$ai       # a[2]
1120         mov     %rax,$a1
1121
1122         mul     $a0                     # a[1]*a[0]
1123         mov     %rax,$A0[0]             # a[1]*a[0]
1124          mov    $ai,%rax                # a[2]
1125         mov     %rdx,$A0[1]
1126         mov     $A0[0],-24($tptr,$i)    # t[1]
1127
1128         mul     $a0                     # a[2]*a[0]
1129         add     %rax,$A0[1]
1130          mov    $ai,%rax
1131         adc     \$0,%rdx
1132         mov     $A0[1],-16($tptr,$i)    # t[2]
1133         mov     %rdx,$A0[0]
1134
1135
1136          mov    -8($aptr,$i),$ai        # a[3]
1137         mul     $a1                     # a[2]*a[1]
1138         mov     %rax,$A1[0]             # a[2]*a[1]+t[3]
1139          mov    $ai,%rax
1140         mov     %rdx,$A1[1]
1141
1142          lea    ($i),$j
1143         mul     $a0                     # a[3]*a[0]
1144         add     %rax,$A0[0]             # a[3]*a[0]+a[2]*a[1]+t[3]
1145          mov    $ai,%rax
1146         mov     %rdx,$A0[1]
1147         adc     \$0,$A0[1]
1148         add     $A1[0],$A0[0]
1149         adc     \$0,$A0[1]
1150         mov     $A0[0],-8($tptr,$j)     # t[3]
1151         jmp     .Lsqr4x_1st
1152
1153 .align  32
1154 .Lsqr4x_1st:
1155          mov    ($aptr,$j),$ai          # a[4]
1156         mul     $a1                     # a[3]*a[1]
1157         add     %rax,$A1[1]             # a[3]*a[1]+t[4]
1158          mov    $ai,%rax
1159         mov     %rdx,$A1[0]
1160         adc     \$0,$A1[0]
1161
1162         mul     $a0                     # a[4]*a[0]
1163         add     %rax,$A0[1]             # a[4]*a[0]+a[3]*a[1]+t[4]
1164          mov    $ai,%rax                # a[3]
1165          mov    8($aptr,$j),$ai         # a[5]
1166         mov     %rdx,$A0[0]
1167         adc     \$0,$A0[0]
1168         add     $A1[1],$A0[1]
1169         adc     \$0,$A0[0]
1170
1171
1172         mul     $a1                     # a[4]*a[3]
1173         add     %rax,$A1[0]             # a[4]*a[3]+t[5]
1174          mov    $ai,%rax
1175          mov    $A0[1],($tptr,$j)       # t[4]
1176         mov     %rdx,$A1[1]
1177         adc     \$0,$A1[1]
1178
1179         mul     $a0                     # a[5]*a[2]
1180         add     %rax,$A0[0]             # a[5]*a[2]+a[4]*a[3]+t[5]
1181          mov    $ai,%rax
1182          mov    16($aptr,$j),$ai        # a[6]
1183         mov     %rdx,$A0[1]
1184         adc     \$0,$A0[1]
1185         add     $A1[0],$A0[0]
1186         adc     \$0,$A0[1]
1187
1188         mul     $a1                     # a[5]*a[3]
1189         add     %rax,$A1[1]             # a[5]*a[3]+t[6]
1190          mov    $ai,%rax
1191          mov    $A0[0],8($tptr,$j)      # t[5]
1192         mov     %rdx,$A1[0]
1193         adc     \$0,$A1[0]
1194
1195         mul     $a0                     # a[6]*a[2]
1196         add     %rax,$A0[1]             # a[6]*a[2]+a[5]*a[3]+t[6]
1197          mov    $ai,%rax                # a[3]
1198          mov    24($aptr,$j),$ai        # a[7]
1199         mov     %rdx,$A0[0]
1200         adc     \$0,$A0[0]
1201         add     $A1[1],$A0[1]
1202         adc     \$0,$A0[0]
1203
1204
1205         mul     $a1                     # a[6]*a[5]
1206         add     %rax,$A1[0]             # a[6]*a[5]+t[7]
1207          mov    $ai,%rax
1208          mov    $A0[1],16($tptr,$j)     # t[6]
1209         mov     %rdx,$A1[1]
1210         adc     \$0,$A1[1]
1211          lea    32($j),$j
1212
1213         mul     $a0                     # a[7]*a[4]
1214         add     %rax,$A0[0]             # a[7]*a[4]+a[6]*a[5]+t[6]
1215          mov    $ai,%rax
1216         mov     %rdx,$A0[1]
1217         adc     \$0,$A0[1]
1218         add     $A1[0],$A0[0]
1219         adc     \$0,$A0[1]
1220         mov     $A0[0],-8($tptr,$j)     # t[7]
1221
1222         cmp     \$0,$j
1223         jne     .Lsqr4x_1st
1224
1225         mul     $a1                     # a[7]*a[5]
1226         add     %rax,$A1[1]
1227         lea     16($i),$i
1228         adc     \$0,%rdx
1229         add     $A0[1],$A1[1]
1230         adc     \$0,%rdx
1231
1232         mov     $A1[1],($tptr)          # t[8]
1233         mov     %rdx,$A1[0]
1234         mov     %rdx,8($tptr)           # t[9]
1235         jmp     .Lsqr4x_outer
1236
1237 .align  32
1238 .Lsqr4x_outer:                          # comments apply to $num==6 case
1239         mov     -32($aptr,$i),$a0       # a[0]
1240         lea     48+8(%rsp,$num,2),$tptr # end of tp[] buffer, &tp[2*$num]
1241         mov     -24($aptr,$i),%rax      # a[1]
1242         lea     -32($tptr,$i),$tptr     # end of tp[] window, &tp[2*$num-"$i"]
1243         mov     -16($aptr,$i),$ai       # a[2]
1244         mov     %rax,$a1
1245
1246         mul     $a0                     # a[1]*a[0]
1247         mov     -24($tptr,$i),$A0[0]    # t[1]
1248         add     %rax,$A0[0]             # a[1]*a[0]+t[1]
1249          mov    $ai,%rax                # a[2]
1250         adc     \$0,%rdx
1251         mov     $A0[0],-24($tptr,$i)    # t[1]
1252         mov     %rdx,$A0[1]
1253
1254         mul     $a0                     # a[2]*a[0]
1255         add     %rax,$A0[1]
1256          mov    $ai,%rax
1257         adc     \$0,%rdx
1258         add     -16($tptr,$i),$A0[1]    # a[2]*a[0]+t[2]
1259         mov     %rdx,$A0[0]
1260         adc     \$0,$A0[0]
1261         mov     $A0[1],-16($tptr,$i)    # t[2]
1262
1263         xor     $A1[0],$A1[0]
1264
1265          mov    -8($aptr,$i),$ai        # a[3]
1266         mul     $a1                     # a[2]*a[1]
1267         add     %rax,$A1[0]             # a[2]*a[1]+t[3]
1268          mov    $ai,%rax
1269         adc     \$0,%rdx
1270         add     -8($tptr,$i),$A1[0]
1271         mov     %rdx,$A1[1]
1272         adc     \$0,$A1[1]
1273
1274         mul     $a0                     # a[3]*a[0]
1275         add     %rax,$A0[0]             # a[3]*a[0]+a[2]*a[1]+t[3]
1276          mov    $ai,%rax
1277         adc     \$0,%rdx
1278         add     $A1[0],$A0[0]
1279         mov     %rdx,$A0[1]
1280         adc     \$0,$A0[1]
1281         mov     $A0[0],-8($tptr,$i)     # t[3]
1282
1283         lea     ($i),$j
1284         jmp     .Lsqr4x_inner
1285
1286 .align  32
1287 .Lsqr4x_inner:
1288          mov    ($aptr,$j),$ai          # a[4]
1289         mul     $a1                     # a[3]*a[1]
1290         add     %rax,$A1[1]             # a[3]*a[1]+t[4]
1291          mov    $ai,%rax
1292         mov     %rdx,$A1[0]
1293         adc     \$0,$A1[0]
1294         add     ($tptr,$j),$A1[1]
1295         adc     \$0,$A1[0]
1296
1297         .byte   0x67
1298         mul     $a0                     # a[4]*a[0]
1299         add     %rax,$A0[1]             # a[4]*a[0]+a[3]*a[1]+t[4]
1300          mov    $ai,%rax                # a[3]
1301          mov    8($aptr,$j),$ai         # a[5]
1302         mov     %rdx,$A0[0]
1303         adc     \$0,$A0[0]
1304         add     $A1[1],$A0[1]
1305         adc     \$0,$A0[0]
1306
1307         mul     $a1                     # a[4]*a[3]
1308         add     %rax,$A1[0]             # a[4]*a[3]+t[5]
1309         mov     $A0[1],($tptr,$j)       # t[4]
1310          mov    $ai,%rax
1311         mov     %rdx,$A1[1]
1312         adc     \$0,$A1[1]
1313         add     8($tptr,$j),$A1[0]
1314         lea     16($j),$j               # j++
1315         adc     \$0,$A1[1]
1316
1317         mul     $a0                     # a[5]*a[2]
1318         add     %rax,$A0[0]             # a[5]*a[2]+a[4]*a[3]+t[5]
1319          mov    $ai,%rax
1320         adc     \$0,%rdx
1321         add     $A1[0],$A0[0]
1322         mov     %rdx,$A0[1]
1323         adc     \$0,$A0[1]
1324         mov     $A0[0],-8($tptr,$j)     # t[5], "preloaded t[1]" below
1325
1326         cmp     \$0,$j
1327         jne     .Lsqr4x_inner
1328
1329         .byte   0x67
1330         mul     $a1                     # a[5]*a[3]
1331         add     %rax,$A1[1]
1332         adc     \$0,%rdx
1333         add     $A0[1],$A1[1]
1334         adc     \$0,%rdx
1335
1336         mov     $A1[1],($tptr)          # t[6], "preloaded t[2]" below
1337         mov     %rdx,$A1[0]
1338         mov     %rdx,8($tptr)           # t[7], "preloaded t[3]" below
1339
1340         add     \$16,$i
1341         jnz     .Lsqr4x_outer
1342
1343                                         # comments apply to $num==4 case
1344         mov     -32($aptr),$a0          # a[0]
1345         lea     48+8(%rsp,$num,2),$tptr # end of tp[] buffer, &tp[2*$num]
1346         mov     -24($aptr),%rax         # a[1]
1347         lea     -32($tptr,$i),$tptr     # end of tp[] window, &tp[2*$num-"$i"]
1348         mov     -16($aptr),$ai          # a[2]
1349         mov     %rax,$a1
1350
1351         mul     $a0                     # a[1]*a[0]
1352         add     %rax,$A0[0]             # a[1]*a[0]+t[1], preloaded t[1]
1353          mov    $ai,%rax                # a[2]
1354         mov     %rdx,$A0[1]
1355         adc     \$0,$A0[1]
1356
1357         mul     $a0                     # a[2]*a[0]
1358         add     %rax,$A0[1]
1359          mov    $ai,%rax
1360          mov    $A0[0],-24($tptr)       # t[1]
1361         mov     %rdx,$A0[0]
1362         adc     \$0,$A0[0]
1363         add     $A1[1],$A0[1]           # a[2]*a[0]+t[2], preloaded t[2]
1364          mov    -8($aptr),$ai           # a[3]
1365         adc     \$0,$A0[0]
1366
1367         mul     $a1                     # a[2]*a[1]
1368         add     %rax,$A1[0]             # a[2]*a[1]+t[3], preloaded t[3]
1369          mov    $ai,%rax
1370          mov    $A0[1],-16($tptr)       # t[2]
1371         mov     %rdx,$A1[1]
1372         adc     \$0,$A1[1]
1373
1374         mul     $a0                     # a[3]*a[0]
1375         add     %rax,$A0[0]             # a[3]*a[0]+a[2]*a[1]+t[3]
1376          mov    $ai,%rax
1377         mov     %rdx,$A0[1]
1378         adc     \$0,$A0[1]
1379         add     $A1[0],$A0[0]
1380         adc     \$0,$A0[1]
1381         mov     $A0[0],-8($tptr)        # t[3]
1382
1383         mul     $a1                     # a[3]*a[1]
1384         add     %rax,$A1[1]
1385          mov    -16($aptr),%rax         # a[2]
1386         adc     \$0,%rdx
1387         add     $A0[1],$A1[1]
1388         adc     \$0,%rdx
1389
1390         mov     $A1[1],($tptr)          # t[4]
1391         mov     %rdx,$A1[0]
1392         mov     %rdx,8($tptr)           # t[5]
1393
1394         mul     $ai                     # a[2]*a[3]
1395 ___
1396 {
1397 my ($shift,$carry)=($a0,$a1);
1398 my @S=(@A1,$ai,$n0);
1399 $code.=<<___;
1400          add    \$16,$i
1401          xor    $shift,$shift
1402          sub    $num,$i                 # $i=16-$num
1403          xor    $carry,$carry
1404
1405         add     $A1[0],%rax             # t[5]
1406         adc     \$0,%rdx
1407         mov     %rax,8($tptr)           # t[5]
1408         mov     %rdx,16($tptr)          # t[6]
1409         mov     $carry,24($tptr)        # t[7]
1410
1411          mov    -16($aptr,$i),%rax      # a[0]
1412         lea     48+8(%rsp),$tptr
1413          xor    $A0[0],$A0[0]           # t[0]
1414          mov    8($tptr),$A0[1]         # t[1]
1415
1416         lea     ($shift,$A0[0],2),$S[0] # t[2*i]<<1 | shift
1417         shr     \$63,$A0[0]
1418         lea     ($j,$A0[1],2),$S[1]     # t[2*i+1]<<1 |
1419         shr     \$63,$A0[1]
1420         or      $A0[0],$S[1]            # | t[2*i]>>63
1421          mov    16($tptr),$A0[0]        # t[2*i+2]      # prefetch
1422         mov     $A0[1],$shift           # shift=t[2*i+1]>>63
1423         mul     %rax                    # a[i]*a[i]
1424         neg     $carry                  # mov $carry,cf
1425          mov    24($tptr),$A0[1]        # t[2*i+2+1]    # prefetch
1426         adc     %rax,$S[0]
1427          mov    -8($aptr,$i),%rax       # a[i+1]        # prefetch
1428         mov     $S[0],($tptr)
1429         adc     %rdx,$S[1]
1430
1431         lea     ($shift,$A0[0],2),$S[2] # t[2*i]<<1 | shift
1432          mov    $S[1],8($tptr)
1433          sbb    $carry,$carry           # mov cf,$carry
1434         shr     \$63,$A0[0]
1435         lea     ($j,$A0[1],2),$S[3]     # t[2*i+1]<<1 |
1436         shr     \$63,$A0[1]
1437         or      $A0[0],$S[3]            # | t[2*i]>>63
1438          mov    32($tptr),$A0[0]        # t[2*i+2]      # prefetch
1439         mov     $A0[1],$shift           # shift=t[2*i+1]>>63
1440         mul     %rax                    # a[i]*a[i]
1441         neg     $carry                  # mov $carry,cf
1442          mov    40($tptr),$A0[1]        # t[2*i+2+1]    # prefetch
1443         adc     %rax,$S[2]
1444          mov    0($aptr,$i),%rax        # a[i+1]        # prefetch
1445         mov     $S[2],16($tptr)
1446         adc     %rdx,$S[3]
1447         lea     16($i),$i
1448         mov     $S[3],24($tptr)
1449         sbb     $carry,$carry           # mov cf,$carry
1450         lea     64($tptr),$tptr
1451         jmp     .Lsqr4x_shift_n_add
1452
1453 .align  32
1454 .Lsqr4x_shift_n_add:
1455         lea     ($shift,$A0[0],2),$S[0] # t[2*i]<<1 | shift
1456         shr     \$63,$A0[0]
1457         lea     ($j,$A0[1],2),$S[1]     # t[2*i+1]<<1 |
1458         shr     \$63,$A0[1]
1459         or      $A0[0],$S[1]            # | t[2*i]>>63
1460          mov    -16($tptr),$A0[0]       # t[2*i+2]      # prefetch
1461         mov     $A0[1],$shift           # shift=t[2*i+1]>>63
1462         mul     %rax                    # a[i]*a[i]
1463         neg     $carry                  # mov $carry,cf
1464          mov    -8($tptr),$A0[1]        # t[2*i+2+1]    # prefetch
1465         adc     %rax,$S[0]
1466          mov    -8($aptr,$i),%rax       # a[i+1]        # prefetch
1467         mov     $S[0],-32($tptr)
1468         adc     %rdx,$S[1]
1469
1470         lea     ($shift,$A0[0],2),$S[2] # t[2*i]<<1 | shift
1471          mov    $S[1],-24($tptr)
1472          sbb    $carry,$carry           # mov cf,$carry
1473         shr     \$63,$A0[0]
1474         lea     ($j,$A0[1],2),$S[3]     # t[2*i+1]<<1 |
1475         shr     \$63,$A0[1]
1476         or      $A0[0],$S[3]            # | t[2*i]>>63
1477          mov    0($tptr),$A0[0]         # t[2*i+2]      # prefetch
1478         mov     $A0[1],$shift           # shift=t[2*i+1]>>63
1479         mul     %rax                    # a[i]*a[i]
1480         neg     $carry                  # mov $carry,cf
1481          mov    8($tptr),$A0[1]         # t[2*i+2+1]    # prefetch
1482         adc     %rax,$S[2]
1483          mov    0($aptr,$i),%rax        # a[i+1]        # prefetch
1484         mov     $S[2],-16($tptr)
1485         adc     %rdx,$S[3]
1486
1487         lea     ($shift,$A0[0],2),$S[0] # t[2*i]<<1 | shift
1488          mov    $S[3],-8($tptr)
1489          sbb    $carry,$carry           # mov cf,$carry
1490         shr     \$63,$A0[0]
1491         lea     ($j,$A0[1],2),$S[1]     # t[2*i+1]<<1 |
1492         shr     \$63,$A0[1]
1493         or      $A0[0],$S[1]            # | t[2*i]>>63
1494          mov    16($tptr),$A0[0]        # t[2*i+2]      # prefetch
1495         mov     $A0[1],$shift           # shift=t[2*i+1]>>63
1496         mul     %rax                    # a[i]*a[i]
1497         neg     $carry                  # mov $carry,cf
1498          mov    24($tptr),$A0[1]        # t[2*i+2+1]    # prefetch
1499         adc     %rax,$S[0]
1500          mov    8($aptr,$i),%rax        # a[i+1]        # prefetch
1501         mov     $S[0],0($tptr)
1502         adc     %rdx,$S[1]
1503
1504         lea     ($shift,$A0[0],2),$S[2] # t[2*i]<<1 | shift
1505          mov    $S[1],8($tptr)
1506          sbb    $carry,$carry           # mov cf,$carry
1507         shr     \$63,$A0[0]
1508         lea     ($j,$A0[1],2),$S[3]     # t[2*i+1]<<1 |
1509         shr     \$63,$A0[1]
1510         or      $A0[0],$S[3]            # | t[2*i]>>63
1511          mov    32($tptr),$A0[0]        # t[2*i+2]      # prefetch
1512         mov     $A0[1],$shift           # shift=t[2*i+1]>>63
1513         mul     %rax                    # a[i]*a[i]
1514         neg     $carry                  # mov $carry,cf
1515          mov    40($tptr),$A0[1]        # t[2*i+2+1]    # prefetch
1516         adc     %rax,$S[2]
1517          mov    16($aptr,$i),%rax       # a[i+1]        # prefetch
1518         mov     $S[2],16($tptr)
1519         adc     %rdx,$S[3]
1520         mov     $S[3],24($tptr)
1521         sbb     $carry,$carry           # mov cf,$carry
1522         lea     64($tptr),$tptr
1523         add     \$32,$i
1524         jnz     .Lsqr4x_shift_n_add
1525
1526         lea     ($shift,$A0[0],2),$S[0] # t[2*i]<<1 | shift
1527         .byte   0x67
1528         shr     \$63,$A0[0]
1529         lea     ($j,$A0[1],2),$S[1]     # t[2*i+1]<<1 |
1530         shr     \$63,$A0[1]
1531         or      $A0[0],$S[1]            # | t[2*i]>>63
1532          mov    -16($tptr),$A0[0]       # t[2*i+2]      # prefetch
1533         mov     $A0[1],$shift           # shift=t[2*i+1]>>63
1534         mul     %rax                    # a[i]*a[i]
1535         neg     $carry                  # mov $carry,cf
1536          mov    -8($tptr),$A0[1]        # t[2*i+2+1]    # prefetch
1537         adc     %rax,$S[0]
1538          mov    -8($aptr),%rax          # a[i+1]        # prefetch
1539         mov     $S[0],-32($tptr)
1540         adc     %rdx,$S[1]
1541
1542         lea     ($shift,$A0[0],2),$S[2] # t[2*i]<<1|shift
1543          mov    $S[1],-24($tptr)
1544          sbb    $carry,$carry           # mov cf,$carry
1545         shr     \$63,$A0[0]
1546         lea     ($j,$A0[1],2),$S[3]     # t[2*i+1]<<1 |
1547         shr     \$63,$A0[1]
1548         or      $A0[0],$S[3]            # | t[2*i]>>63
1549         mul     %rax                    # a[i]*a[i]
1550         neg     $carry                  # mov $carry,cf
1551         adc     %rax,$S[2]
1552         adc     %rdx,$S[3]
1553         mov     $S[2],-16($tptr)
1554         mov     $S[3],-8($tptr)
1555 ___
1556 }\f
1557 ######################################################################
1558 # Montgomery reduction part, "word-by-word" algorithm.
1559 #
1560 # This new path is inspired by multiple submissions from Intel, by
1561 # Shay Gueron, Vlad Krasnov, Erdinc Ozturk, James Guilford,
1562 # Vinodh Gopal...
1563 {
1564 my ($nptr,$tptr,$carry,$m0)=("%rbp","%rdi","%rsi","%rbx");
1565
1566 $code.=<<___;
1567         movq    %xmm2,$nptr
1568 sqr8x_reduction:
1569         xor     %rax,%rax
1570         lea     ($nptr,$num,2),%rcx     # end of n[]
1571         lea     48+8(%rsp,$num,2),%rdx  # end of t[] buffer
1572         mov     %rcx,0+8(%rsp)
1573         lea     48+8(%rsp,$num),$tptr   # end of initial t[] window
1574         mov     %rdx,8+8(%rsp)
1575         neg     $num
1576         jmp     .L8x_reduction_loop
1577
1578 .align  32
1579 .L8x_reduction_loop:
1580         lea     ($tptr,$num),$tptr      # start of current t[] window
1581         .byte   0x66
1582         mov     8*0($tptr),$m0
1583         mov     8*1($tptr),%r9
1584         mov     8*2($tptr),%r10
1585         mov     8*3($tptr),%r11
1586         mov     8*4($tptr),%r12
1587         mov     8*5($tptr),%r13
1588         mov     8*6($tptr),%r14
1589         mov     8*7($tptr),%r15
1590         mov     %rax,(%rdx)             # store top-most carry bit
1591         lea     8*8($tptr),$tptr
1592
1593         .byte   0x67
1594         mov     $m0,%r8
1595         imulq   32+8(%rsp),$m0          # n0*a[0]
1596         mov     16*0($nptr),%rax        # n[0]
1597         mov     \$8,%ecx
1598         jmp     .L8x_reduce
1599
1600 .align  32
1601 .L8x_reduce:
1602         mulq    $m0
1603          mov    16*1($nptr),%rax        # n[1]
1604         neg     %r8
1605         mov     %rdx,%r8
1606         adc     \$0,%r8
1607
1608         mulq    $m0
1609         add     %rax,%r9
1610          mov    16*2($nptr),%rax
1611         adc     \$0,%rdx
1612         add     %r9,%r8
1613          mov    $m0,48-8+8(%rsp,%rcx,8) # put aside n0*a[i]
1614         mov     %rdx,%r9
1615         adc     \$0,%r9
1616
1617         mulq    $m0
1618         add     %rax,%r10
1619          mov    16*3($nptr),%rax
1620         adc     \$0,%rdx
1621         add     %r10,%r9
1622          mov    32+8(%rsp),$carry       # pull n0, borrow $carry
1623         mov     %rdx,%r10
1624         adc     \$0,%r10
1625
1626         mulq    $m0
1627         add     %rax,%r11
1628          mov    16*4($nptr),%rax
1629         adc     \$0,%rdx
1630          imulq  %r8,$carry              # modulo-scheduled
1631         add     %r11,%r10
1632         mov     %rdx,%r11
1633         adc     \$0,%r11
1634
1635         mulq    $m0
1636         add     %rax,%r12
1637          mov    16*5($nptr),%rax
1638         adc     \$0,%rdx
1639         add     %r12,%r11
1640         mov     %rdx,%r12
1641         adc     \$0,%r12
1642
1643         mulq    $m0
1644         add     %rax,%r13
1645          mov    16*6($nptr),%rax
1646         adc     \$0,%rdx
1647         add     %r13,%r12
1648         mov     %rdx,%r13
1649         adc     \$0,%r13
1650
1651         mulq    $m0
1652         add     %rax,%r14
1653          mov    16*7($nptr),%rax
1654         adc     \$0,%rdx
1655         add     %r14,%r13
1656         mov     %rdx,%r14
1657         adc     \$0,%r14
1658
1659         mulq    $m0
1660          mov    $carry,$m0              # n0*a[i]
1661         add     %rax,%r15
1662          mov    16*0($nptr),%rax        # n[0]
1663         adc     \$0,%rdx
1664         add     %r15,%r14
1665         mov     %rdx,%r15
1666         adc     \$0,%r15
1667
1668         dec     %ecx
1669         jnz     .L8x_reduce
1670
1671         lea     16*8($nptr),$nptr
1672         xor     %rax,%rax
1673         mov     8+8(%rsp),%rdx          # pull end of t[]
1674         cmp     0+8(%rsp),$nptr         # end of n[]?
1675         jae     .L8x_no_tail
1676
1677         .byte   0x66
1678         add     8*0($tptr),%r8
1679         adc     8*1($tptr),%r9
1680         adc     8*2($tptr),%r10
1681         adc     8*3($tptr),%r11
1682         adc     8*4($tptr),%r12
1683         adc     8*5($tptr),%r13
1684         adc     8*6($tptr),%r14
1685         adc     8*7($tptr),%r15
1686         sbb     $carry,$carry           # top carry
1687
1688         mov     48+56+8(%rsp),$m0       # pull n0*a[0]
1689         mov     \$8,%ecx
1690         mov     16*0($nptr),%rax
1691         jmp     .L8x_tail
1692
1693 .align  32
1694 .L8x_tail:
1695         mulq    $m0
1696         add     %rax,%r8
1697          mov    16*1($nptr),%rax
1698          mov    %r8,($tptr)             # save result
1699         mov     %rdx,%r8
1700         adc     \$0,%r8
1701
1702         mulq    $m0
1703         add     %rax,%r9
1704          mov    16*2($nptr),%rax
1705         adc     \$0,%rdx
1706         add     %r9,%r8
1707          lea    8($tptr),$tptr          # $tptr++
1708         mov     %rdx,%r9
1709         adc     \$0,%r9
1710
1711         mulq    $m0
1712         add     %rax,%r10
1713          mov    16*3($nptr),%rax
1714         adc     \$0,%rdx
1715         add     %r10,%r9
1716         mov     %rdx,%r10
1717         adc     \$0,%r10
1718
1719         mulq    $m0
1720         add     %rax,%r11
1721          mov    16*4($nptr),%rax
1722         adc     \$0,%rdx
1723         add     %r11,%r10
1724         mov     %rdx,%r11
1725         adc     \$0,%r11
1726
1727         mulq    $m0
1728         add     %rax,%r12
1729          mov    16*5($nptr),%rax
1730         adc     \$0,%rdx
1731         add     %r12,%r11
1732         mov     %rdx,%r12
1733         adc     \$0,%r12
1734
1735         mulq    $m0
1736         add     %rax,%r13
1737          mov    16*6($nptr),%rax
1738         adc     \$0,%rdx
1739         add     %r13,%r12
1740         mov     %rdx,%r13
1741         adc     \$0,%r13
1742
1743         mulq    $m0
1744         add     %rax,%r14
1745          mov    16*7($nptr),%rax
1746         adc     \$0,%rdx
1747         add     %r14,%r13
1748         mov     %rdx,%r14
1749         adc     \$0,%r14
1750
1751         mulq    $m0
1752          mov    48-16+8(%rsp,%rcx,8),$m0# pull n0*a[i]
1753         add     %rax,%r15
1754         adc     \$0,%rdx
1755         add     %r15,%r14
1756          mov    16*0($nptr),%rax        # pull n[0]
1757         mov     %rdx,%r15
1758         adc     \$0,%r15
1759
1760         dec     %ecx
1761         jnz     .L8x_tail
1762
1763         lea     16*8($nptr),$nptr
1764         mov     8+8(%rsp),%rdx          # pull end of t[]
1765         cmp     0+8(%rsp),$nptr         # end of n[]?
1766         jae     .L8x_tail_done          # break out of loop
1767
1768          mov    48+56+8(%rsp),$m0       # pull n0*a[0]
1769         neg     $carry
1770          mov    8*0($nptr),%rax         # pull n[0]
1771         adc     8*0($tptr),%r8
1772         adc     8*1($tptr),%r9
1773         adc     8*2($tptr),%r10
1774         adc     8*3($tptr),%r11
1775         adc     8*4($tptr),%r12
1776         adc     8*5($tptr),%r13
1777         adc     8*6($tptr),%r14
1778         adc     8*7($tptr),%r15
1779         sbb     $carry,$carry           # top carry
1780
1781         mov     \$8,%ecx
1782         jmp     .L8x_tail
1783
1784 .align  32
1785 .L8x_tail_done:
1786         add     (%rdx),%r8              # can this overflow?
1787         xor     %rax,%rax
1788
1789         neg     $carry
1790 .L8x_no_tail:
1791         adc     8*0($tptr),%r8
1792         adc     8*1($tptr),%r9
1793         adc     8*2($tptr),%r10
1794         adc     8*3($tptr),%r11
1795         adc     8*4($tptr),%r12
1796         adc     8*5($tptr),%r13
1797         adc     8*6($tptr),%r14
1798         adc     8*7($tptr),%r15
1799         adc     \$0,%rax                # top-most carry
1800          mov    -16($nptr),%rcx         # np[num-1]
1801          xor    $carry,$carry
1802
1803         movq    %xmm2,$nptr             # restore $nptr
1804
1805         mov     %r8,8*0($tptr)          # store top 512 bits
1806         mov     %r9,8*1($tptr)
1807          movq   %xmm3,$num              # $num is %r9, can't be moved upwards
1808         mov     %r10,8*2($tptr)
1809         mov     %r11,8*3($tptr)
1810         mov     %r12,8*4($tptr)
1811         mov     %r13,8*5($tptr)
1812         mov     %r14,8*6($tptr)
1813         mov     %r15,8*7($tptr)
1814         lea     8*8($tptr),$tptr
1815
1816         cmp     %rdx,$tptr              # end of t[]?
1817         jb      .L8x_reduction_loop
1818 ___
1819 }\f
1820 ##############################################################
1821 # Post-condition, 4x unrolled
1822 #
1823 {
1824 my ($tptr,$nptr)=("%rbx","%rbp");
1825 $code.=<<___;
1826         #xor    %rsi,%rsi               # %rsi was $carry above
1827         sub     %r15,%rcx               # compare top-most words
1828         lea     (%rdi,$num),$tptr       # %rdi was $tptr above
1829         adc     %rsi,%rsi
1830         mov     $num,%rcx
1831         or      %rsi,%rax
1832         movq    %xmm1,$rptr             # restore $rptr
1833         xor     \$1,%rax
1834         movq    %xmm1,$aptr             # prepare for back-to-back call
1835         lea     ($nptr,%rax,8),$nptr
1836         sar     \$3+2,%rcx              # cf=0
1837         jmp     .Lsqr4x_sub
1838
1839 .align  32
1840 .Lsqr4x_sub:
1841         .byte   0x66
1842         mov     8*0($tptr),%r12
1843         mov     8*1($tptr),%r13
1844         sbb     16*0($nptr),%r12
1845         mov     8*2($tptr),%r14
1846         sbb     16*1($nptr),%r13
1847         mov     8*3($tptr),%r15
1848         lea     8*4($tptr),$tptr
1849         sbb     16*2($nptr),%r14
1850         mov     %r12,8*0($rptr)
1851         sbb     16*3($nptr),%r15
1852         lea     16*4($nptr),$nptr
1853         mov     %r13,8*1($rptr)
1854         mov     %r14,8*2($rptr)
1855         mov     %r15,8*3($rptr)
1856         lea     8*4($rptr),$rptr
1857
1858         inc     %rcx                    # pass %cf
1859         jnz     .Lsqr4x_sub
1860 ___
1861 }
1862 $code.=<<___;
1863         mov     $num,%r10               # prepare for back-to-back call
1864         neg     $num                    # restore $num
1865         ret
1866 .size   bn_sqr8x_internal,.-bn_sqr8x_internal
1867 ___
1868 {
1869 $code.=<<___;
1870 .globl  bn_from_montgomery
1871 .type   bn_from_montgomery,\@abi-omnipotent
1872 .align  32
1873 bn_from_montgomery:
1874         testl   \$7,`($win64?"48(%rsp)":"%r9d")`
1875         jz      bn_from_mont8x
1876         xor     %eax,%eax
1877         ret
1878 .size   bn_from_montgomery,.-bn_from_montgomery
1879
1880 .type   bn_from_mont8x,\@function,6
1881 .align  32
1882 bn_from_mont8x:
1883         .byte   0x67
1884         mov     %rsp,%rax
1885         push    %rbx
1886         push    %rbp
1887         push    %r12
1888         push    %r13
1889         push    %r14
1890         push    %r15
1891 ___
1892 $code.=<<___ if ($win64);
1893         lea     -0x28(%rsp),%rsp
1894         movaps  %xmm6,(%rsp)
1895         movaps  %xmm7,0x10(%rsp)
1896 ___
1897 $code.=<<___;
1898         .byte   0x67
1899         mov     ${num}d,%r10d
1900         shl     \$3,${num}d             # convert $num to bytes
1901         shl     \$3+2,%r10d             # 4*$num
1902         neg     $num
1903         mov     ($n0),$n0               # *n0
1904
1905         ##############################################################
1906         # ensure that stack frame doesn't alias with $aptr+4*$num
1907         # modulo 4096, which covers ret[num], am[num] and n[2*num]
1908         # (see bn_exp.c). this is done to allow memory disambiguation
1909         # logic do its magic.
1910         #
1911         lea     -64(%rsp,$num,2),%r11
1912         sub     $aptr,%r11
1913         and     \$4095,%r11
1914         cmp     %r11,%r10
1915         jb      .Lfrom_sp_alt
1916         sub     %r11,%rsp               # align with $aptr
1917         lea     -64(%rsp,$num,2),%rsp   # alloca(frame+2*$num)
1918         jmp     .Lfrom_sp_done
1919
1920 .align  32
1921 .Lfrom_sp_alt:
1922         lea     4096-64(,$num,2),%r10   # 4096-frame-2*$num
1923         lea     -64(%rsp,$num,2),%rsp   # alloca(frame+2*$num)
1924         sub     %r10,%r11
1925         mov     \$0,%r10
1926         cmovc   %r10,%r11
1927         sub     %r11,%rsp
1928 .Lfrom_sp_done:
1929         and     \$-64,%rsp
1930         mov     $num,%r10
1931         neg     $num
1932
1933         ##############################################################
1934         # Stack layout
1935         #
1936         # +0    saved $num, used in reduction section
1937         # +8    &t[2*$num], used in reduction section
1938         # +32   saved *n0
1939         # +40   saved %rsp
1940         # +48   t[2*$num]
1941         #
1942         mov     $n0,  32(%rsp)
1943         mov     %rax, 40(%rsp)          # save original %rsp
1944 .Lfrom_body:
1945         mov     $num,%r11
1946         lea     48(%rsp),%rax
1947         pxor    %xmm0,%xmm0
1948         jmp     .Lmul_by_1
1949
1950 .align  32
1951 .Lmul_by_1:
1952         movdqu  ($aptr),%xmm1
1953         movdqu  16($aptr),%xmm2
1954         movdqu  32($aptr),%xmm3
1955         movdqa  %xmm0,(%rax,$num)
1956         movdqu  48($aptr),%xmm4
1957         movdqa  %xmm0,16(%rax,$num)
1958         .byte   0x48,0x8d,0xb6,0x40,0x00,0x00,0x00      # lea   64($aptr),$aptr
1959         movdqa  %xmm1,(%rax)
1960         movdqa  %xmm0,32(%rax,$num)
1961         movdqa  %xmm2,16(%rax)
1962         movdqa  %xmm0,48(%rax,$num)
1963         movdqa  %xmm3,32(%rax)
1964         movdqa  %xmm4,48(%rax)
1965         lea     64(%rax),%rax
1966         sub     \$64,%r11
1967         jnz     .Lmul_by_1
1968
1969         movq    $rptr,%xmm1
1970         movq    $nptr,%xmm2
1971         .byte   0x67
1972         mov     $nptr,%rbp
1973         movq    %r10, %xmm3             # -num
1974 ___
1975 $code.=<<___ if ($addx);
1976         mov     OPENSSL_ia32cap_P+8(%rip),%r11d
1977         and     \$0x80100,%r11d
1978         cmp     \$0x80100,%r11d
1979         jne     .Lfrom_mont_nox
1980
1981         lea     (%rax,$num),$rptr
1982         call    sqrx8x_reduction
1983
1984         pxor    %xmm0,%xmm0
1985         lea     48(%rsp),%rax
1986         mov     40(%rsp),%rsi           # restore %rsp
1987         jmp     .Lfrom_mont_zero
1988
1989 .align  32
1990 .Lfrom_mont_nox:
1991 ___
1992 $code.=<<___;
1993         call    sqr8x_reduction
1994
1995         pxor    %xmm0,%xmm0
1996         lea     48(%rsp),%rax
1997         mov     40(%rsp),%rsi           # restore %rsp
1998         jmp     .Lfrom_mont_zero
1999
2000 .align  32
2001 .Lfrom_mont_zero:
2002         movdqa  %xmm0,16*0(%rax)
2003         movdqa  %xmm0,16*1(%rax)
2004         movdqa  %xmm0,16*2(%rax)
2005         movdqa  %xmm0,16*3(%rax)
2006         lea     16*4(%rax),%rax
2007         sub     \$32,$num
2008         jnz     .Lfrom_mont_zero
2009
2010         mov     \$1,%rax
2011         mov     -48(%rsi),%r15
2012         mov     -40(%rsi),%r14
2013         mov     -32(%rsi),%r13
2014         mov     -24(%rsi),%r12
2015         mov     -16(%rsi),%rbp
2016         mov     -8(%rsi),%rbx
2017         lea     (%rsi),%rsp
2018 .Lfrom_epilogue:
2019         ret
2020 .size   bn_from_mont8x,.-bn_from_mont8x
2021 ___
2022 }
2023 }}}
2024 \f
2025 if ($addx) {{{
2026 my $bp="%rdx";  # restore original value
2027
2028 $code.=<<___;
2029 .type   bn_mulx4x_mont_gather5,\@function,6
2030 .align  32
2031 bn_mulx4x_mont_gather5:
2032 .Lmulx4x_enter:
2033         .byte   0x67
2034         mov     %rsp,%rax
2035         push    %rbx
2036         push    %rbp
2037         push    %r12
2038         push    %r13
2039         push    %r14
2040         push    %r15
2041 ___
2042 $code.=<<___ if ($win64);
2043         lea     -0x28(%rsp),%rsp
2044         movaps  %xmm6,(%rsp)
2045         movaps  %xmm7,0x10(%rsp)
2046 ___
2047 $code.=<<___;
2048         .byte   0x67
2049         mov     ${num}d,%r10d
2050         shl     \$3,${num}d             # convert $num to bytes
2051         shl     \$3+2,%r10d             # 4*$num
2052         neg     $num                    # -$num
2053         mov     ($n0),$n0               # *n0
2054
2055         ##############################################################
2056         # ensure that stack frame doesn't alias with $aptr+4*$num
2057         # modulo 4096, which covers a[num], ret[num] and n[2*num]
2058         # (see bn_exp.c). this is done to allow memory disambiguation
2059         # logic do its magic. [excessive frame is allocated in order
2060         # to allow bn_from_mont8x to clear it.]
2061         #
2062         lea     -64(%rsp,$num,2),%r11
2063         sub     $ap,%r11
2064         and     \$4095,%r11
2065         cmp     %r11,%r10
2066         jb      .Lmulx4xsp_alt
2067         sub     %r11,%rsp               # align with $aptr
2068         lea     -64(%rsp,$num,2),%rsp   # alloca(frame+$num)
2069         jmp     .Lmulx4xsp_done
2070
2071 .align  32
2072 .Lmulx4xsp_alt:
2073         lea     4096-64(,$num,2),%r10   # 4096-frame-$num
2074         lea     -64(%rsp,$num,2),%rsp   # alloca(frame+$num)
2075         sub     %r10,%r11
2076         mov     \$0,%r10
2077         cmovc   %r10,%r11
2078         sub     %r11,%rsp
2079 .Lmulx4xsp_done:
2080         and     \$-64,%rsp              # ensure alignment
2081         ##############################################################
2082         # Stack layout
2083         # +0    -num
2084         # +8    off-loaded &b[i]
2085         # +16   end of b[num]
2086         # +24   inner counter
2087         # +32   saved n0
2088         # +40   saved %rsp
2089         # +48
2090         # +56   saved rp
2091         # +64   tmp[num+1]
2092         #
2093         mov     $n0, 32(%rsp)           # save *n0
2094         mov     %rax,40(%rsp)           # save original %rsp
2095 .Lmulx4x_body:
2096         call    mulx4x_internal
2097
2098         mov     40(%rsp),%rsi           # restore %rsp
2099         mov     \$1,%rax
2100 ___
2101 $code.=<<___ if ($win64);
2102         movaps  -88(%rsi),%xmm6
2103         movaps  -72(%rsi),%xmm7
2104 ___
2105 $code.=<<___;
2106         mov     -48(%rsi),%r15
2107         mov     -40(%rsi),%r14
2108         mov     -32(%rsi),%r13
2109         mov     -24(%rsi),%r12
2110         mov     -16(%rsi),%rbp
2111         mov     -8(%rsi),%rbx
2112         lea     (%rsi),%rsp
2113 .Lmulx4x_epilogue:
2114         ret
2115 .size   bn_mulx4x_mont_gather5,.-bn_mulx4x_mont_gather5
2116
2117 .type   mulx4x_internal,\@abi-omnipotent
2118 .align  32
2119 mulx4x_internal:
2120         .byte   0x4c,0x89,0x8c,0x24,0x08,0x00,0x00,0x00 # mov   $num,8(%rsp)            # save -$num
2121         .byte   0x67
2122         neg     $num                    # restore $num
2123         shl     \$5,$num
2124         lea     256($bp,$num),%r13
2125         shr     \$5+5,$num
2126         mov     `($win64?56:8)`(%rax),%r10d     # load 7th argument
2127         sub     \$1,$num
2128         mov     %r13,16+8(%rsp)         # end of b[num]
2129         mov     $num,24+8(%rsp)         # inner counter
2130         mov     $rp, 56+8(%rsp)         # save $rp
2131 ___
2132 my ($aptr, $bptr, $nptr, $tptr, $mi,  $bi,  $zero, $num)=
2133    ("%rsi","%rdi","%rcx","%rbx","%r8","%r9","%rbp","%rax");
2134 my $rptr=$bptr;
2135 my $STRIDE=2**5*8;              # 5 is "window size"
2136 my $N=$STRIDE/4;                # should match cache line size
2137 $code.=<<___;
2138         mov     %r10,%r11
2139         shr     \$`log($N/8)/log(2)`,%r10
2140         and     \$`$N/8-1`,%r11
2141         not     %r10
2142         lea     .Lmagic_masks(%rip),%rax
2143         and     \$`2**5/($N/8)-1`,%r10  # 5 is "window size"
2144         lea     96($bp,%r11,8),$bptr    # pointer within 1st cache line
2145         movq    0(%rax,%r10,8),%xmm4    # set of masks denoting which
2146         movq    8(%rax,%r10,8),%xmm5    # cache line contains element
2147         add     \$7,%r11
2148         movq    16(%rax,%r10,8),%xmm6   # denoted by 7th argument
2149         movq    24(%rax,%r10,8),%xmm7
2150         and     \$7,%r11
2151
2152         movq    `0*$STRIDE/4-96`($bptr),%xmm0
2153         lea     $STRIDE($bptr),$tptr    # borrow $tptr
2154         movq    `1*$STRIDE/4-96`($bptr),%xmm1
2155         pand    %xmm4,%xmm0
2156         movq    `2*$STRIDE/4-96`($bptr),%xmm2
2157         pand    %xmm5,%xmm1
2158         movq    `3*$STRIDE/4-96`($bptr),%xmm3
2159         pand    %xmm6,%xmm2
2160         por     %xmm1,%xmm0
2161         movq    `0*$STRIDE/4-96`($tptr),%xmm1
2162         pand    %xmm7,%xmm3
2163         por     %xmm2,%xmm0
2164         movq    `1*$STRIDE/4-96`($tptr),%xmm2
2165         por     %xmm3,%xmm0
2166         .byte   0x67,0x67
2167         pand    %xmm4,%xmm1
2168         movq    `2*$STRIDE/4-96`($tptr),%xmm3
2169
2170         movq    %xmm0,%rdx              # bp[0]
2171         movq    `3*$STRIDE/4-96`($tptr),%xmm0
2172         lea     2*$STRIDE($bptr),$bptr  # next &b[i]
2173         pand    %xmm5,%xmm2
2174         .byte   0x67,0x67
2175         pand    %xmm6,%xmm3
2176         ##############################################################
2177         # $tptr is chosen so that writing to top-most element of the
2178         # vector occurs just "above" references to powers table,
2179         # "above" modulo cache-line size, which effectively precludes
2180         # possibility of memory disambiguation logic failure when
2181         # accessing the table.
2182         #
2183         lea     64+8*4+8(%rsp,%r11,8),$tptr
2184
2185         mov     %rdx,$bi
2186         mulx    0*8($aptr),$mi,%rax     # a[0]*b[0]
2187         mulx    1*8($aptr),%r11,%r12    # a[1]*b[0]
2188         add     %rax,%r11
2189         mulx    2*8($aptr),%rax,%r13    # ...
2190         adc     %rax,%r12
2191         adc     \$0,%r13
2192         mulx    3*8($aptr),%rax,%r14
2193
2194         mov     $mi,%r15
2195         imulq   32+8(%rsp),$mi          # "t[0]"*n0
2196         xor     $zero,$zero             # cf=0, of=0
2197         mov     $mi,%rdx
2198
2199         por     %xmm2,%xmm1
2200         pand    %xmm7,%xmm0
2201         por     %xmm3,%xmm1
2202         mov     $bptr,8+8(%rsp)         # off-load &b[i]
2203         por     %xmm1,%xmm0
2204
2205         .byte   0x48,0x8d,0xb6,0x20,0x00,0x00,0x00      # lea   4*8($aptr),$aptr
2206         adcx    %rax,%r13
2207         adcx    $zero,%r14              # cf=0
2208
2209         mulx    0*16($nptr),%rax,%r10
2210         adcx    %rax,%r15               # discarded
2211         adox    %r11,%r10
2212         mulx    1*16($nptr),%rax,%r11
2213         adcx    %rax,%r10
2214         adox    %r12,%r11
2215         mulx    2*16($nptr),%rax,%r12
2216         mov     24+8(%rsp),$bptr        # counter value
2217         .byte   0x66
2218         mov     %r10,-8*4($tptr)
2219         adcx    %rax,%r11
2220         adox    %r13,%r12
2221         mulx    3*16($nptr),%rax,%r15
2222          .byte  0x67,0x67
2223          mov    $bi,%rdx
2224         mov     %r11,-8*3($tptr)
2225         adcx    %rax,%r12
2226         adox    $zero,%r15              # of=0
2227         .byte   0x48,0x8d,0x89,0x40,0x00,0x00,0x00      # lea   4*16($nptr),$nptr
2228         mov     %r12,-8*2($tptr)
2229         #jmp    .Lmulx4x_1st
2230
2231 .align  32
2232 .Lmulx4x_1st:
2233         adcx    $zero,%r15              # cf=0, modulo-scheduled
2234         mulx    0*8($aptr),%r10,%rax    # a[4]*b[0]
2235         adcx    %r14,%r10
2236         mulx    1*8($aptr),%r11,%r14    # a[5]*b[0]
2237         adcx    %rax,%r11
2238         mulx    2*8($aptr),%r12,%rax    # ...
2239         adcx    %r14,%r12
2240         mulx    3*8($aptr),%r13,%r14
2241          .byte  0x67,0x67
2242          mov    $mi,%rdx
2243         adcx    %rax,%r13
2244         adcx    $zero,%r14              # cf=0
2245         lea     4*8($aptr),$aptr
2246         lea     4*8($tptr),$tptr
2247
2248         adox    %r15,%r10
2249         mulx    0*16($nptr),%rax,%r15
2250         adcx    %rax,%r10
2251         adox    %r15,%r11
2252         mulx    1*16($nptr),%rax,%r15
2253         adcx    %rax,%r11
2254         adox    %r15,%r12
2255         mulx    2*16($nptr),%rax,%r15
2256         mov     %r10,-5*8($tptr)
2257         adcx    %rax,%r12
2258         mov     %r11,-4*8($tptr)
2259         adox    %r15,%r13
2260         mulx    3*16($nptr),%rax,%r15
2261          mov    $bi,%rdx
2262         mov     %r12,-3*8($tptr)
2263         adcx    %rax,%r13
2264         adox    $zero,%r15
2265         lea     4*16($nptr),$nptr
2266         mov     %r13,-2*8($tptr)
2267
2268         dec     $bptr                   # of=0, pass cf
2269         jnz     .Lmulx4x_1st
2270
2271         mov     8(%rsp),$num            # load -num
2272         movq    %xmm0,%rdx              # bp[1]
2273         adc     $zero,%r15              # modulo-scheduled
2274         lea     ($aptr,$num),$aptr      # rewind $aptr
2275         add     %r15,%r14
2276         mov     8+8(%rsp),$bptr         # re-load &b[i]
2277         adc     $zero,$zero             # top-most carry
2278         mov     %r14,-1*8($tptr)
2279         jmp     .Lmulx4x_outer
2280
2281 .align  32
2282 .Lmulx4x_outer:
2283         mov     $zero,($tptr)           # save top-most carry
2284         lea     4*8($tptr,$num),$tptr   # rewind $tptr
2285         mulx    0*8($aptr),$mi,%r11     # a[0]*b[i]
2286         xor     $zero,$zero             # cf=0, of=0
2287         mov     %rdx,$bi
2288         mulx    1*8($aptr),%r14,%r12    # a[1]*b[i]
2289         adox    -4*8($tptr),$mi         # +t[0]
2290         adcx    %r14,%r11
2291         mulx    2*8($aptr),%r15,%r13    # ...
2292         adox    -3*8($tptr),%r11
2293         adcx    %r15,%r12
2294         mulx    3*8($aptr),%rdx,%r14
2295         adox    -2*8($tptr),%r12
2296         adcx    %rdx,%r13
2297         lea     ($nptr,$num,2),$nptr    # rewind $nptr
2298         lea     4*8($aptr),$aptr
2299         adox    -1*8($tptr),%r13
2300         adcx    $zero,%r14
2301         adox    $zero,%r14
2302
2303         .byte   0x67
2304         mov     $mi,%r15
2305         imulq   32+8(%rsp),$mi          # "t[0]"*n0
2306
2307         movq    `0*$STRIDE/4-96`($bptr),%xmm0
2308         .byte   0x67,0x67
2309         mov     $mi,%rdx
2310         movq    `1*$STRIDE/4-96`($bptr),%xmm1
2311         .byte   0x67
2312         pand    %xmm4,%xmm0
2313         movq    `2*$STRIDE/4-96`($bptr),%xmm2
2314         .byte   0x67
2315         pand    %xmm5,%xmm1
2316         movq    `3*$STRIDE/4-96`($bptr),%xmm3
2317         add     \$$STRIDE,$bptr         # next &b[i]
2318         .byte   0x67
2319         pand    %xmm6,%xmm2
2320         por     %xmm1,%xmm0
2321         pand    %xmm7,%xmm3
2322         xor     $zero,$zero             # cf=0, of=0
2323         mov     $bptr,8+8(%rsp)         # off-load &b[i]
2324
2325         mulx    0*16($nptr),%rax,%r10
2326         adcx    %rax,%r15               # discarded
2327         adox    %r11,%r10
2328         mulx    1*16($nptr),%rax,%r11
2329         adcx    %rax,%r10
2330         adox    %r12,%r11
2331         mulx    2*16($nptr),%rax,%r12
2332         adcx    %rax,%r11
2333         adox    %r13,%r12
2334         mulx    3*16($nptr),%rax,%r15
2335          mov    $bi,%rdx
2336          por    %xmm2,%xmm0
2337         mov     24+8(%rsp),$bptr        # counter value
2338         mov     %r10,-8*4($tptr)
2339          por    %xmm3,%xmm0
2340         adcx    %rax,%r12
2341         mov     %r11,-8*3($tptr)
2342         adox    $zero,%r15              # of=0
2343         mov     %r12,-8*2($tptr)
2344         lea     4*16($nptr),$nptr
2345         jmp     .Lmulx4x_inner
2346
2347 .align  32
2348 .Lmulx4x_inner:
2349         mulx    0*8($aptr),%r10,%rax    # a[4]*b[i]
2350         adcx    $zero,%r15              # cf=0, modulo-scheduled
2351         adox    %r14,%r10
2352         mulx    1*8($aptr),%r11,%r14    # a[5]*b[i]
2353         adcx    0*8($tptr),%r10
2354         adox    %rax,%r11
2355         mulx    2*8($aptr),%r12,%rax    # ...
2356         adcx    1*8($tptr),%r11
2357         adox    %r14,%r12
2358         mulx    3*8($aptr),%r13,%r14
2359          mov    $mi,%rdx
2360         adcx    2*8($tptr),%r12
2361         adox    %rax,%r13
2362         adcx    3*8($tptr),%r13
2363         adox    $zero,%r14              # of=0
2364         lea     4*8($aptr),$aptr
2365         lea     4*8($tptr),$tptr
2366         adcx    $zero,%r14              # cf=0
2367
2368         adox    %r15,%r10
2369         mulx    0*16($nptr),%rax,%r15
2370         adcx    %rax,%r10
2371         adox    %r15,%r11
2372         mulx    1*16($nptr),%rax,%r15
2373         adcx    %rax,%r11
2374         adox    %r15,%r12
2375         mulx    2*16($nptr),%rax,%r15
2376         mov     %r10,-5*8($tptr)
2377         adcx    %rax,%r12
2378         adox    %r15,%r13
2379         mov     %r11,-4*8($tptr)
2380         mulx    3*16($nptr),%rax,%r15
2381          mov    $bi,%rdx
2382         lea     4*16($nptr),$nptr
2383         mov     %r12,-3*8($tptr)
2384         adcx    %rax,%r13
2385         adox    $zero,%r15
2386         mov     %r13,-2*8($tptr)
2387
2388         dec     $bptr                   # of=0, pass cf
2389         jnz     .Lmulx4x_inner
2390
2391         mov     0+8(%rsp),$num          # load -num
2392         movq    %xmm0,%rdx              # bp[i+1]
2393         adc     $zero,%r15              # modulo-scheduled
2394         sub     0*8($tptr),$bptr        # pull top-most carry to %cf
2395         mov     8+8(%rsp),$bptr         # re-load &b[i]
2396         mov     16+8(%rsp),%r10
2397         adc     %r15,%r14
2398         lea     ($aptr,$num),$aptr      # rewind $aptr
2399         adc     $zero,$zero             # top-most carry
2400         mov     %r14,-1*8($tptr)
2401
2402         cmp     %r10,$bptr
2403         jb      .Lmulx4x_outer
2404
2405         mov     -16($nptr),%r10
2406         xor     %r15,%r15
2407         sub     %r14,%r10               # compare top-most words
2408         adc     %r15,%r15
2409         or      %r15,$zero
2410         xor     \$1,$zero
2411         lea     ($tptr,$num),%rdi       # rewind $tptr
2412         lea     ($nptr,$num,2),$nptr    # rewind $nptr
2413         .byte   0x67,0x67
2414         sar     \$3+2,$num              # cf=0
2415         lea     ($nptr,$zero,8),%rbp
2416         mov     56+8(%rsp),%rdx         # restore rp
2417         mov     $num,%rcx
2418         jmp     .Lsqrx4x_sub            # common post-condition
2419 .size   mulx4x_internal,.-mulx4x_internal
2420 ___
2421 }\f{
2422 ######################################################################
2423 # void bn_power5(
2424 my $rptr="%rdi";        # BN_ULONG *rptr,
2425 my $aptr="%rsi";        # const BN_ULONG *aptr,
2426 my $bptr="%rdx";        # const void *table,
2427 my $nptr="%rcx";        # const BN_ULONG *nptr,
2428 my $n0  ="%r8";         # const BN_ULONG *n0);
2429 my $num ="%r9";         # int num, has to be divisible by 8
2430                         # int pwr);
2431
2432 my ($i,$j,$tptr)=("%rbp","%rcx",$rptr);
2433 my @A0=("%r10","%r11");
2434 my @A1=("%r12","%r13");
2435 my ($a0,$a1,$ai)=("%r14","%r15","%rbx");
2436
2437 $code.=<<___;
2438 .type   bn_powerx5,\@function,6
2439 .align  32
2440 bn_powerx5:
2441 .Lpowerx5_enter:
2442         .byte   0x67
2443         mov     %rsp,%rax
2444         push    %rbx
2445         push    %rbp
2446         push    %r12
2447         push    %r13
2448         push    %r14
2449         push    %r15
2450 ___
2451 $code.=<<___ if ($win64);
2452         lea     -0x28(%rsp),%rsp
2453         movaps  %xmm6,(%rsp)
2454         movaps  %xmm7,0x10(%rsp)
2455 ___
2456 $code.=<<___;
2457         .byte   0x67
2458         mov     ${num}d,%r10d
2459         shl     \$3,${num}d             # convert $num to bytes
2460         shl     \$3+2,%r10d             # 4*$num
2461         neg     $num
2462         mov     ($n0),$n0               # *n0
2463
2464         ##############################################################
2465         # ensure that stack frame doesn't alias with $aptr+4*$num
2466         # modulo 4096, which covers ret[num], am[num] and n[2*num]
2467         # (see bn_exp.c). this is done to allow memory disambiguation
2468         # logic do its magic.
2469         #
2470         lea     -64(%rsp,$num,2),%r11
2471         sub     $aptr,%r11
2472         and     \$4095,%r11
2473         cmp     %r11,%r10
2474         jb      .Lpwrx_sp_alt
2475         sub     %r11,%rsp               # align with $aptr
2476         lea     -64(%rsp,$num,2),%rsp   # alloca(frame+2*$num)
2477         jmp     .Lpwrx_sp_done
2478
2479 .align  32
2480 .Lpwrx_sp_alt:
2481         lea     4096-64(,$num,2),%r10   # 4096-frame-2*$num
2482         lea     -64(%rsp,$num,2),%rsp   # alloca(frame+2*$num)
2483         sub     %r10,%r11
2484         mov     \$0,%r10
2485         cmovc   %r10,%r11
2486         sub     %r11,%rsp
2487 .Lpwrx_sp_done:
2488         and     \$-64,%rsp
2489         mov     $num,%r10
2490         neg     $num
2491
2492         ##############################################################
2493         # Stack layout
2494         #
2495         # +0    saved $num, used in reduction section
2496         # +8    &t[2*$num], used in reduction section
2497         # +16   intermediate carry bit
2498         # +24   top-most carry bit, used in reduction section
2499         # +32   saved *n0
2500         # +40   saved %rsp
2501         # +48   t[2*$num]
2502         #
2503         pxor    %xmm0,%xmm0
2504         movq    $rptr,%xmm1             # save $rptr
2505         movq    $nptr,%xmm2             # save $nptr
2506         movq    %r10, %xmm3             # -$num
2507         movq    $bptr,%xmm4
2508         mov     $n0,  32(%rsp)
2509         mov     %rax, 40(%rsp)          # save original %rsp
2510 .Lpowerx5_body:
2511
2512         call    __bn_sqrx8x_internal
2513         call    __bn_sqrx8x_internal
2514         call    __bn_sqrx8x_internal
2515         call    __bn_sqrx8x_internal
2516         call    __bn_sqrx8x_internal
2517
2518         mov     %r10,$num               # -num
2519         mov     $aptr,$rptr
2520         movq    %xmm2,$nptr
2521         movq    %xmm4,$bptr
2522         mov     40(%rsp),%rax
2523
2524         call    mulx4x_internal
2525
2526         mov     40(%rsp),%rsi           # restore %rsp
2527         mov     \$1,%rax
2528 ___
2529 $code.=<<___ if ($win64);
2530         movaps  -88(%rsi),%xmm6
2531         movaps  -72(%rsi),%xmm7
2532 ___
2533 $code.=<<___;
2534         mov     -48(%rsi),%r15
2535         mov     -40(%rsi),%r14
2536         mov     -32(%rsi),%r13
2537         mov     -24(%rsi),%r12
2538         mov     -16(%rsi),%rbp
2539         mov     -8(%rsi),%rbx
2540         lea     (%rsi),%rsp
2541 .Lpowerx5_epilogue:
2542         ret
2543 .size   bn_powerx5,.-bn_powerx5
2544
2545 .globl  bn_sqrx8x_internal
2546 .hidden bn_sqrx8x_internal
2547 .type   bn_sqrx8x_internal,\@abi-omnipotent
2548 .align  32
2549 bn_sqrx8x_internal:
2550 __bn_sqrx8x_internal:
2551         ##################################################################
2552         # Squaring part:
2553         #
2554         # a) multiply-n-add everything but a[i]*a[i];
2555         # b) shift result of a) by 1 to the left and accumulate
2556         #    a[i]*a[i] products;
2557         #
2558         ##################################################################
2559         # a[7]a[7]a[6]a[6]a[5]a[5]a[4]a[4]a[3]a[3]a[2]a[2]a[1]a[1]a[0]a[0]
2560         #                                                     a[1]a[0]
2561         #                                                 a[2]a[0]
2562         #                                             a[3]a[0]
2563         #                                             a[2]a[1]
2564         #                                         a[3]a[1]
2565         #                                     a[3]a[2]
2566         #
2567         #                                         a[4]a[0]
2568         #                                     a[5]a[0]
2569         #                                 a[6]a[0]
2570         #                             a[7]a[0]
2571         #                                     a[4]a[1]
2572         #                                 a[5]a[1]
2573         #                             a[6]a[1]
2574         #                         a[7]a[1]
2575         #                                 a[4]a[2]
2576         #                             a[5]a[2]
2577         #                         a[6]a[2]
2578         #                     a[7]a[2]
2579         #                             a[4]a[3]
2580         #                         a[5]a[3]
2581         #                     a[6]a[3]
2582         #                 a[7]a[3]
2583         #
2584         #                     a[5]a[4]
2585         #                 a[6]a[4]
2586         #             a[7]a[4]
2587         #             a[6]a[5]
2588         #         a[7]a[5]
2589         #     a[7]a[6]
2590         # a[7]a[7]a[6]a[6]a[5]a[5]a[4]a[4]a[3]a[3]a[2]a[2]a[1]a[1]a[0]a[0]
2591 ___
2592 {
2593 my ($zero,$carry)=("%rbp","%rcx");
2594 my $aaptr=$zero;
2595 $code.=<<___;
2596         lea     48+8(%rsp),$tptr
2597         lea     ($aptr,$num),$aaptr
2598         mov     $num,0+8(%rsp)                  # save $num
2599         mov     $aaptr,8+8(%rsp)                # save end of $aptr
2600         jmp     .Lsqr8x_zero_start
2601
2602 .align  32
2603 .byte   0x66,0x66,0x66,0x2e,0x0f,0x1f,0x84,0x00,0x00,0x00,0x00,0x00
2604 .Lsqrx8x_zero:
2605         .byte   0x3e
2606         movdqa  %xmm0,0*8($tptr)
2607         movdqa  %xmm0,2*8($tptr)
2608         movdqa  %xmm0,4*8($tptr)
2609         movdqa  %xmm0,6*8($tptr)
2610 .Lsqr8x_zero_start:                     # aligned at 32
2611         movdqa  %xmm0,8*8($tptr)
2612         movdqa  %xmm0,10*8($tptr)
2613         movdqa  %xmm0,12*8($tptr)
2614         movdqa  %xmm0,14*8($tptr)
2615         lea     16*8($tptr),$tptr
2616         sub     \$64,$num
2617         jnz     .Lsqrx8x_zero
2618
2619         mov     0*8($aptr),%rdx         # a[0], modulo-scheduled
2620         #xor    %r9,%r9                 # t[1], ex-$num, zero already
2621         xor     %r10,%r10
2622         xor     %r11,%r11
2623         xor     %r12,%r12
2624         xor     %r13,%r13
2625         xor     %r14,%r14
2626         xor     %r15,%r15
2627         lea     48+8(%rsp),$tptr
2628         xor     $zero,$zero             # cf=0, cf=0
2629         jmp     .Lsqrx8x_outer_loop
2630
2631 .align  32
2632 .Lsqrx8x_outer_loop:
2633         mulx    1*8($aptr),%r8,%rax     # a[1]*a[0]
2634         adcx    %r9,%r8                 # a[1]*a[0]+=t[1]
2635         adox    %rax,%r10
2636         mulx    2*8($aptr),%r9,%rax     # a[2]*a[0]
2637         adcx    %r10,%r9
2638         adox    %rax,%r11
2639         .byte   0xc4,0xe2,0xab,0xf6,0x86,0x18,0x00,0x00,0x00    # mulx  3*8($aptr),%r10,%rax    # ...
2640         adcx    %r11,%r10
2641         adox    %rax,%r12
2642         .byte   0xc4,0xe2,0xa3,0xf6,0x86,0x20,0x00,0x00,0x00    # mulx  4*8($aptr),%r11,%rax
2643         adcx    %r12,%r11
2644         adox    %rax,%r13
2645         mulx    5*8($aptr),%r12,%rax
2646         adcx    %r13,%r12
2647         adox    %rax,%r14
2648         mulx    6*8($aptr),%r13,%rax
2649         adcx    %r14,%r13
2650         adox    %r15,%rax
2651         mulx    7*8($aptr),%r14,%r15
2652          mov    1*8($aptr),%rdx         # a[1]
2653         adcx    %rax,%r14
2654         adox    $zero,%r15
2655         adc     8*8($tptr),%r15
2656         mov     %r8,1*8($tptr)          # t[1]
2657         mov     %r9,2*8($tptr)          # t[2]
2658         sbb     $carry,$carry           # mov %cf,$carry
2659         xor     $zero,$zero             # cf=0, of=0
2660
2661
2662         mulx    2*8($aptr),%r8,%rbx     # a[2]*a[1]
2663         mulx    3*8($aptr),%r9,%rax     # a[3]*a[1]
2664         adcx    %r10,%r8
2665         adox    %rbx,%r9
2666         mulx    4*8($aptr),%r10,%rbx    # ...
2667         adcx    %r11,%r9
2668         adox    %rax,%r10
2669         .byte   0xc4,0xe2,0xa3,0xf6,0x86,0x28,0x00,0x00,0x00    # mulx  5*8($aptr),%r11,%rax
2670         adcx    %r12,%r10
2671         adox    %rbx,%r11
2672         .byte   0xc4,0xe2,0x9b,0xf6,0x9e,0x30,0x00,0x00,0x00    # mulx  6*8($aptr),%r12,%rbx
2673         adcx    %r13,%r11
2674         adox    %r14,%r12
2675         .byte   0xc4,0x62,0x93,0xf6,0xb6,0x38,0x00,0x00,0x00    # mulx  7*8($aptr),%r13,%r14
2676          mov    2*8($aptr),%rdx         # a[2]
2677         adcx    %rax,%r12
2678         adox    %rbx,%r13
2679         adcx    %r15,%r13
2680         adox    $zero,%r14              # of=0
2681         adcx    $zero,%r14              # cf=0
2682
2683         mov     %r8,3*8($tptr)          # t[3]
2684         mov     %r9,4*8($tptr)          # t[4]
2685
2686         mulx    3*8($aptr),%r8,%rbx     # a[3]*a[2]
2687         mulx    4*8($aptr),%r9,%rax     # a[4]*a[2]
2688         adcx    %r10,%r8
2689         adox    %rbx,%r9
2690         mulx    5*8($aptr),%r10,%rbx    # ...
2691         adcx    %r11,%r9
2692         adox    %rax,%r10
2693         .byte   0xc4,0xe2,0xa3,0xf6,0x86,0x30,0x00,0x00,0x00    # mulx  6*8($aptr),%r11,%rax
2694         adcx    %r12,%r10
2695         adox    %r13,%r11
2696         .byte   0xc4,0x62,0x9b,0xf6,0xae,0x38,0x00,0x00,0x00    # mulx  7*8($aptr),%r12,%r13
2697         .byte   0x3e
2698          mov    3*8($aptr),%rdx         # a[3]
2699         adcx    %rbx,%r11
2700         adox    %rax,%r12
2701         adcx    %r14,%r12
2702         mov     %r8,5*8($tptr)          # t[5]
2703         mov     %r9,6*8($tptr)          # t[6]
2704          mulx   4*8($aptr),%r8,%rax     # a[4]*a[3]
2705         adox    $zero,%r13              # of=0
2706         adcx    $zero,%r13              # cf=0
2707
2708         mulx    5*8($aptr),%r9,%rbx     # a[5]*a[3]
2709         adcx    %r10,%r8
2710         adox    %rax,%r9
2711         mulx    6*8($aptr),%r10,%rax    # ...
2712         adcx    %r11,%r9
2713         adox    %r12,%r10
2714         mulx    7*8($aptr),%r11,%r12
2715          mov    4*8($aptr),%rdx         # a[4]
2716          mov    5*8($aptr),%r14         # a[5]
2717         adcx    %rbx,%r10
2718         adox    %rax,%r11
2719          mov    6*8($aptr),%r15         # a[6]
2720         adcx    %r13,%r11
2721         adox    $zero,%r12              # of=0
2722         adcx    $zero,%r12              # cf=0
2723
2724         mov     %r8,7*8($tptr)          # t[7]
2725         mov     %r9,8*8($tptr)          # t[8]
2726
2727         mulx    %r14,%r9,%rax           # a[5]*a[4]
2728          mov    7*8($aptr),%r8          # a[7]
2729         adcx    %r10,%r9
2730         mulx    %r15,%r10,%rbx          # a[6]*a[4]
2731         adox    %rax,%r10
2732         adcx    %r11,%r10
2733         mulx    %r8,%r11,%rax           # a[7]*a[4]
2734          mov    %r14,%rdx               # a[5]
2735         adox    %rbx,%r11
2736         adcx    %r12,%r11
2737         #adox   $zero,%rax              # of=0
2738         adcx    $zero,%rax              # cf=0
2739
2740         mulx    %r15,%r14,%rbx          # a[6]*a[5]
2741         mulx    %r8,%r12,%r13           # a[7]*a[5]
2742          mov    %r15,%rdx               # a[6]
2743          lea    8*8($aptr),$aptr
2744         adcx    %r14,%r11
2745         adox    %rbx,%r12
2746         adcx    %rax,%r12
2747         adox    $zero,%r13
2748
2749         .byte   0x67,0x67
2750         mulx    %r8,%r8,%r14            # a[7]*a[6]
2751         adcx    %r8,%r13
2752         adcx    $zero,%r14
2753
2754         cmp     8+8(%rsp),$aptr
2755         je      .Lsqrx8x_outer_break
2756
2757         neg     $carry                  # mov $carry,%cf
2758         mov     \$-8,%rcx
2759         mov     $zero,%r15
2760         mov     8*8($tptr),%r8
2761         adcx    9*8($tptr),%r9          # +=t[9]
2762         adcx    10*8($tptr),%r10        # ...
2763         adcx    11*8($tptr),%r11
2764         adc     12*8($tptr),%r12
2765         adc     13*8($tptr),%r13
2766         adc     14*8($tptr),%r14
2767         adc     15*8($tptr),%r15
2768         lea     ($aptr),$aaptr
2769         lea     2*64($tptr),$tptr
2770         sbb     %rax,%rax               # mov %cf,$carry
2771
2772         mov     -64($aptr),%rdx         # a[0]
2773         mov     %rax,16+8(%rsp)         # offload $carry
2774         mov     $tptr,24+8(%rsp)
2775
2776         #lea    8*8($tptr),$tptr        # see 2*8*8($tptr) above
2777         xor     %eax,%eax               # cf=0, of=0
2778         jmp     .Lsqrx8x_loop
2779
2780 .align  32
2781 .Lsqrx8x_loop:
2782         mov     %r8,%rbx
2783         mulx    0*8($aaptr),%rax,%r8    # a[8]*a[i]
2784         adcx    %rax,%rbx               # +=t[8]
2785         adox    %r9,%r8
2786
2787         mulx    1*8($aaptr),%rax,%r9    # ...
2788         adcx    %rax,%r8
2789         adox    %r10,%r9
2790
2791         mulx    2*8($aaptr),%rax,%r10
2792         adcx    %rax,%r9
2793         adox    %r11,%r10
2794
2795         mulx    3*8($aaptr),%rax,%r11
2796         adcx    %rax,%r10
2797         adox    %r12,%r11
2798
2799         .byte   0xc4,0x62,0xfb,0xf6,0xa5,0x20,0x00,0x00,0x00    # mulx  4*8($aaptr),%rax,%r12
2800         adcx    %rax,%r11
2801         adox    %r13,%r12
2802
2803         mulx    5*8($aaptr),%rax,%r13
2804         adcx    %rax,%r12
2805         adox    %r14,%r13
2806
2807         mulx    6*8($aaptr),%rax,%r14
2808          mov    %rbx,($tptr,%rcx,8)     # store t[8+i]
2809          mov    \$0,%ebx
2810         adcx    %rax,%r13
2811         adox    %r15,%r14
2812
2813         .byte   0xc4,0x62,0xfb,0xf6,0xbd,0x38,0x00,0x00,0x00    # mulx  7*8($aaptr),%rax,%r15
2814          mov    8($aptr,%rcx,8),%rdx    # a[i]
2815         adcx    %rax,%r14
2816         adox    %rbx,%r15               # %rbx is 0, of=0
2817         adcx    %rbx,%r15               # cf=0
2818
2819         .byte   0x67
2820         inc     %rcx                    # of=0
2821         jnz     .Lsqrx8x_loop
2822
2823         lea     8*8($aaptr),$aaptr
2824         mov     \$-8,%rcx
2825         cmp     8+8(%rsp),$aaptr        # done?
2826         je      .Lsqrx8x_break
2827
2828         sub     16+8(%rsp),%rbx         # mov 16(%rsp),%cf
2829         .byte   0x66
2830         mov     -64($aptr),%rdx
2831         adcx    0*8($tptr),%r8
2832         adcx    1*8($tptr),%r9
2833         adc     2*8($tptr),%r10
2834         adc     3*8($tptr),%r11
2835         adc     4*8($tptr),%r12
2836         adc     5*8($tptr),%r13
2837         adc     6*8($tptr),%r14
2838         adc     7*8($tptr),%r15
2839         lea     8*8($tptr),$tptr
2840         .byte   0x67
2841         sbb     %rax,%rax               # mov %cf,%rax
2842         xor     %ebx,%ebx               # cf=0, of=0
2843         mov     %rax,16+8(%rsp)         # offload carry
2844         jmp     .Lsqrx8x_loop
2845
2846 .align  32
2847 .Lsqrx8x_break:
2848         sub     16+8(%rsp),%r8          # consume last carry
2849         mov     24+8(%rsp),$carry       # initial $tptr, borrow $carry
2850         mov     0*8($aptr),%rdx         # a[8], modulo-scheduled
2851         xor     %ebp,%ebp               # xor   $zero,$zero
2852         mov     %r8,0*8($tptr)
2853         cmp     $carry,$tptr            # cf=0, of=0
2854         je      .Lsqrx8x_outer_loop
2855
2856         mov     %r9,1*8($tptr)
2857          mov    1*8($carry),%r9
2858         mov     %r10,2*8($tptr)
2859          mov    2*8($carry),%r10
2860         mov     %r11,3*8($tptr)
2861          mov    3*8($carry),%r11
2862         mov     %r12,4*8($tptr)
2863          mov    4*8($carry),%r12
2864         mov     %r13,5*8($tptr)
2865          mov    5*8($carry),%r13
2866         mov     %r14,6*8($tptr)
2867          mov    6*8($carry),%r14
2868         mov     %r15,7*8($tptr)
2869          mov    7*8($carry),%r15
2870         mov     $carry,$tptr
2871         jmp     .Lsqrx8x_outer_loop
2872
2873 .align  32
2874 .Lsqrx8x_outer_break:
2875         mov     %r9,9*8($tptr)          # t[9]
2876          movq   %xmm3,%rcx              # -$num
2877         mov     %r10,10*8($tptr)        # ...
2878         mov     %r11,11*8($tptr)
2879         mov     %r12,12*8($tptr)
2880         mov     %r13,13*8($tptr)
2881         mov     %r14,14*8($tptr)
2882 ___
2883 }\f{
2884 my $i="%rcx";
2885 $code.=<<___;
2886         lea     48+8(%rsp),$tptr
2887         mov     ($aptr,$i),%rdx         # a[0]
2888
2889         mov     8($tptr),$A0[1]         # t[1]
2890         xor     $A0[0],$A0[0]           # t[0], of=0, cf=0
2891         mov     0+8(%rsp),$num          # restore $num
2892         adox    $A0[1],$A0[1]
2893          mov    16($tptr),$A1[0]        # t[2]  # prefetch
2894          mov    24($tptr),$A1[1]        # t[3]  # prefetch
2895         #jmp    .Lsqrx4x_shift_n_add    # happens to be aligned
2896
2897 .align  32
2898 .Lsqrx4x_shift_n_add:
2899         mulx    %rdx,%rax,%rbx
2900          adox   $A1[0],$A1[0]
2901         adcx    $A0[0],%rax
2902          .byte  0x48,0x8b,0x94,0x0e,0x08,0x00,0x00,0x00 # mov   8($aptr,$i),%rdx        # a[i+1]        # prefetch
2903          .byte  0x4c,0x8b,0x97,0x20,0x00,0x00,0x00      # mov   32($tptr),$A0[0]        # t[2*i+4]      # prefetch
2904          adox   $A1[1],$A1[1]
2905         adcx    $A0[1],%rbx
2906          mov    40($tptr),$A0[1]                # t[2*i+4+1]    # prefetch
2907         mov     %rax,0($tptr)
2908         mov     %rbx,8($tptr)
2909
2910         mulx    %rdx,%rax,%rbx
2911          adox   $A0[0],$A0[0]
2912         adcx    $A1[0],%rax
2913          mov    16($aptr,$i),%rdx       # a[i+2]        # prefetch
2914          mov    48($tptr),$A1[0]        # t[2*i+6]      # prefetch
2915          adox   $A0[1],$A0[1]
2916         adcx    $A1[1],%rbx
2917          mov    56($tptr),$A1[1]        # t[2*i+6+1]    # prefetch
2918         mov     %rax,16($tptr)
2919         mov     %rbx,24($tptr)
2920
2921         mulx    %rdx,%rax,%rbx
2922          adox   $A1[0],$A1[0]
2923         adcx    $A0[0],%rax
2924          mov    24($aptr,$i),%rdx       # a[i+3]        # prefetch
2925          lea    32($i),$i
2926          mov    64($tptr),$A0[0]        # t[2*i+8]      # prefetch
2927          adox   $A1[1],$A1[1]
2928         adcx    $A0[1],%rbx
2929          mov    72($tptr),$A0[1]        # t[2*i+8+1]    # prefetch
2930         mov     %rax,32($tptr)
2931         mov     %rbx,40($tptr)
2932
2933         mulx    %rdx,%rax,%rbx
2934          adox   $A0[0],$A0[0]
2935         adcx    $A1[0],%rax
2936         jrcxz   .Lsqrx4x_shift_n_add_break
2937          .byte  0x48,0x8b,0x94,0x0e,0x00,0x00,0x00,0x00 # mov   0($aptr,$i),%rdx        # a[i+4]        # prefetch
2938          adox   $A0[1],$A0[1]
2939         adcx    $A1[1],%rbx
2940          mov    80($tptr),$A1[0]        # t[2*i+10]     # prefetch
2941          mov    88($tptr),$A1[1]        # t[2*i+10+1]   # prefetch
2942         mov     %rax,48($tptr)
2943         mov     %rbx,56($tptr)
2944         lea     64($tptr),$tptr
2945         nop
2946         jmp     .Lsqrx4x_shift_n_add
2947
2948 .align  32
2949 .Lsqrx4x_shift_n_add_break:
2950         adcx    $A1[1],%rbx
2951         mov     %rax,48($tptr)
2952         mov     %rbx,56($tptr)
2953         lea     64($tptr),$tptr         # end of t[] buffer
2954 ___
2955 }\f
2956 ######################################################################
2957 # Montgomery reduction part, "word-by-word" algorithm.
2958 #
2959 # This new path is inspired by multiple submissions from Intel, by
2960 # Shay Gueron, Vlad Krasnov, Erdinc Ozturk, James Guilford,
2961 # Vinodh Gopal...
2962 {
2963 my ($nptr,$carry,$m0)=("%rbp","%rsi","%rdx");
2964
2965 $code.=<<___;
2966         movq    %xmm2,$nptr
2967 sqrx8x_reduction:
2968         xor     %eax,%eax               # initial top-most carry bit
2969         mov     32+8(%rsp),%rbx         # n0
2970         mov     48+8(%rsp),%rdx         # "%r8", 8*0($tptr)
2971         lea     -128($nptr,$num,2),%rcx # end of n[]
2972         #lea    48+8(%rsp,$num,2),$tptr # end of t[] buffer
2973         mov     %rcx, 0+8(%rsp)         # save end of n[]
2974         mov     $tptr,8+8(%rsp)         # save end of t[]
2975
2976         lea     48+8(%rsp),$tptr                # initial t[] window
2977         jmp     .Lsqrx8x_reduction_loop
2978
2979 .align  32
2980 .Lsqrx8x_reduction_loop:
2981         mov     8*1($tptr),%r9
2982         mov     8*2($tptr),%r10
2983         mov     8*3($tptr),%r11
2984         mov     8*4($tptr),%r12
2985         mov     %rdx,%r8
2986         imulq   %rbx,%rdx               # n0*a[i]
2987         mov     8*5($tptr),%r13
2988         mov     8*6($tptr),%r14
2989         mov     8*7($tptr),%r15
2990         mov     %rax,24+8(%rsp)         # store top-most carry bit
2991
2992         lea     8*8($tptr),$tptr
2993         xor     $carry,$carry           # cf=0,of=0
2994         mov     \$-8,%rcx
2995         jmp     .Lsqrx8x_reduce
2996
2997 .align  32
2998 .Lsqrx8x_reduce:
2999         mov     %r8, %rbx
3000         mulx    16*0($nptr),%rax,%r8    # n[0]
3001         adcx    %rbx,%rax               # discarded
3002         adox    %r9,%r8
3003
3004         mulx    16*1($nptr),%rbx,%r9    # n[1]
3005         adcx    %rbx,%r8
3006         adox    %r10,%r9
3007
3008         mulx    16*2($nptr),%rbx,%r10
3009         adcx    %rbx,%r9
3010         adox    %r11,%r10
3011
3012         mulx    16*3($nptr),%rbx,%r11
3013         adcx    %rbx,%r10
3014         adox    %r12,%r11
3015
3016         .byte   0xc4,0x62,0xe3,0xf6,0xa5,0x40,0x00,0x00,0x00    # mulx  16*4($nptr),%rbx,%r12
3017          mov    %rdx,%rax
3018          mov    %r8,%rdx
3019         adcx    %rbx,%r11
3020         adox    %r13,%r12
3021
3022          mulx   32+8(%rsp),%rbx,%rdx    # %rdx discarded
3023          mov    %rax,%rdx
3024          mov    %rax,64+48+8(%rsp,%rcx,8)       # put aside n0*a[i]
3025
3026         mulx    16*5($nptr),%rax,%r13
3027         adcx    %rax,%r12
3028         adox    %r14,%r13
3029
3030         mulx    16*6($nptr),%rax,%r14
3031         adcx    %rax,%r13
3032         adox    %r15,%r14
3033
3034         mulx    16*7($nptr),%rax,%r15
3035          mov    %rbx,%rdx
3036         adcx    %rax,%r14
3037         adox    $carry,%r15             # $carry is 0
3038         adcx    $carry,%r15             # cf=0
3039
3040         .byte   0x67,0x67,0x67
3041         inc     %rcx                    # of=0
3042         jnz     .Lsqrx8x_reduce
3043
3044         mov     $carry,%rax             # xor   %rax,%rax
3045         cmp     0+8(%rsp),$nptr         # end of n[]?
3046         jae     .Lsqrx8x_no_tail
3047
3048         mov     48+8(%rsp),%rdx         # pull n0*a[0]
3049         add     8*0($tptr),%r8
3050         lea     16*8($nptr),$nptr
3051         mov     \$-8,%rcx
3052         adcx    8*1($tptr),%r9
3053         adcx    8*2($tptr),%r10
3054         adc     8*3($tptr),%r11
3055         adc     8*4($tptr),%r12
3056         adc     8*5($tptr),%r13
3057         adc     8*6($tptr),%r14
3058         adc     8*7($tptr),%r15
3059         lea     8*8($tptr),$tptr
3060         sbb     %rax,%rax               # top carry
3061
3062         xor     $carry,$carry           # of=0, cf=0
3063         mov     %rax,16+8(%rsp)
3064         jmp     .Lsqrx8x_tail
3065
3066 .align  32
3067 .Lsqrx8x_tail:
3068         mov     %r8,%rbx
3069         mulx    16*0($nptr),%rax,%r8
3070         adcx    %rax,%rbx
3071         adox    %r9,%r8
3072
3073         mulx    16*1($nptr),%rax,%r9
3074         adcx    %rax,%r8
3075         adox    %r10,%r9
3076
3077         mulx    16*2($nptr),%rax,%r10
3078         adcx    %rax,%r9
3079         adox    %r11,%r10
3080
3081         mulx    16*3($nptr),%rax,%r11
3082         adcx    %rax,%r10
3083         adox    %r12,%r11
3084
3085         .byte   0xc4,0x62,0xfb,0xf6,0xa5,0x40,0x00,0x00,0x00    # mulx  16*4($nptr),%rax,%r12
3086         adcx    %rax,%r11
3087         adox    %r13,%r12
3088
3089         mulx    16*5($nptr),%rax,%r13
3090         adcx    %rax,%r12
3091         adox    %r14,%r13
3092
3093         mulx    16*6($nptr),%rax,%r14
3094         adcx    %rax,%r13
3095         adox    %r15,%r14
3096
3097         mulx    16*7($nptr),%rax,%r15
3098          mov    72+48+8(%rsp,%rcx,8),%rdx       # pull n0*a[i]
3099         adcx    %rax,%r14
3100         adox    $carry,%r15
3101          mov    %rbx,($tptr,%rcx,8)     # save result
3102          mov    %r8,%rbx
3103         adcx    $carry,%r15             # cf=0
3104
3105         inc     %rcx                    # of=0
3106         jnz     .Lsqrx8x_tail
3107
3108         cmp     0+8(%rsp),$nptr         # end of n[]?
3109         jae     .Lsqrx8x_tail_done      # break out of loop
3110
3111         sub     16+8(%rsp),$carry       # mov 16(%rsp),%cf
3112          mov    48+8(%rsp),%rdx         # pull n0*a[0]
3113          lea    16*8($nptr),$nptr
3114         adc     8*0($tptr),%r8
3115         adc     8*1($tptr),%r9
3116         adc     8*2($tptr),%r10
3117         adc     8*3($tptr),%r11
3118         adc     8*4($tptr),%r12
3119         adc     8*5($tptr),%r13
3120         adc     8*6($tptr),%r14
3121         adc     8*7($tptr),%r15
3122         lea     8*8($tptr),$tptr
3123         sbb     %rax,%rax
3124         sub     \$8,%rcx                # mov   \$-8,%rcx
3125
3126         xor     $carry,$carry           # of=0, cf=0
3127         mov     %rax,16+8(%rsp)
3128         jmp     .Lsqrx8x_tail
3129
3130 .align  32
3131 .Lsqrx8x_tail_done:
3132         add     24+8(%rsp),%r8          # can this overflow?
3133         mov     $carry,%rax             # xor   %rax,%rax
3134
3135         sub     16+8(%rsp),$carry       # mov 16(%rsp),%cf
3136 .Lsqrx8x_no_tail:                       # %cf is 0 if jumped here
3137         adc     8*0($tptr),%r8
3138          movq   %xmm3,%rcx
3139         adc     8*1($tptr),%r9
3140          mov    16*7($nptr),$carry
3141          movq   %xmm2,$nptr             # restore $nptr
3142         adc     8*2($tptr),%r10
3143         adc     8*3($tptr),%r11
3144         adc     8*4($tptr),%r12
3145         adc     8*5($tptr),%r13
3146         adc     8*6($tptr),%r14
3147         adc     8*7($tptr),%r15
3148         adc     %rax,%rax               # top-most carry
3149
3150         mov     32+8(%rsp),%rbx         # n0
3151         mov     8*8($tptr,%rcx),%rdx    # modulo-scheduled "%r8"
3152
3153         mov     %r8,8*0($tptr)          # store top 512 bits
3154          lea    8*8($tptr),%r8          # borrow %r8
3155         mov     %r9,8*1($tptr)
3156         mov     %r10,8*2($tptr)
3157         mov     %r11,8*3($tptr)
3158         mov     %r12,8*4($tptr)
3159         mov     %r13,8*5($tptr)
3160         mov     %r14,8*6($tptr)
3161         mov     %r15,8*7($tptr)
3162
3163         lea     8*8($tptr,%rcx),$tptr   # start of current t[] window
3164         cmp     8+8(%rsp),%r8           # end of t[]?
3165         jb      .Lsqrx8x_reduction_loop
3166 ___
3167 }\f
3168 ##############################################################
3169 # Post-condition, 4x unrolled
3170 #
3171 {
3172 my ($rptr,$nptr)=("%rdx","%rbp");
3173 my @ri=map("%r$_",(10..13));
3174 my @ni=map("%r$_",(14..15));
3175 $code.=<<___;
3176         xor     %rbx,%rbx
3177         sub     %r15,%rsi               # compare top-most words
3178         adc     %rbx,%rbx
3179         mov     %rcx,%r10               # -$num
3180         .byte   0x67
3181         or      %rbx,%rax
3182         .byte   0x67
3183         mov     %rcx,%r9                # -$num
3184         xor     \$1,%rax
3185         sar     \$3+2,%rcx              # cf=0
3186         #lea    48+8(%rsp,%r9),$tptr
3187         lea     ($nptr,%rax,8),$nptr
3188         movq    %xmm1,$rptr             # restore $rptr
3189         movq    %xmm1,$aptr             # prepare for back-to-back call
3190         jmp     .Lsqrx4x_sub
3191
3192 .align  32
3193 .Lsqrx4x_sub:
3194         .byte   0x66
3195         mov     8*0($tptr),%r12
3196         mov     8*1($tptr),%r13
3197         sbb     16*0($nptr),%r12
3198         mov     8*2($tptr),%r14
3199         sbb     16*1($nptr),%r13
3200         mov     8*3($tptr),%r15
3201         lea     8*4($tptr),$tptr
3202         sbb     16*2($nptr),%r14
3203         mov     %r12,8*0($rptr)
3204         sbb     16*3($nptr),%r15
3205         lea     16*4($nptr),$nptr
3206         mov     %r13,8*1($rptr)
3207         mov     %r14,8*2($rptr)
3208         mov     %r15,8*3($rptr)
3209         lea     8*4($rptr),$rptr
3210
3211         inc     %rcx
3212         jnz     .Lsqrx4x_sub
3213 ___
3214 }
3215 $code.=<<___;
3216         neg     %r9                     # restore $num
3217
3218         ret
3219 .size   bn_sqrx8x_internal,.-bn_sqrx8x_internal
3220 ___
3221 }}}
3222 {
3223 my ($inp,$num,$tbl,$idx)=$win64?("%rcx","%edx","%r8", "%r9d") : # Win64 order
3224                                 ("%rdi","%esi","%rdx","%ecx");  # Unix order
3225 my $out=$inp;
3226 my $STRIDE=2**5*8;
3227 my $N=$STRIDE/4;
3228
3229 $code.=<<___;
3230 .globl  bn_get_bits5
3231 .type   bn_get_bits5,\@abi-omnipotent
3232 .align  16
3233 bn_get_bits5:
3234         lea     0($inp),%r10
3235         lea     1($inp),%r11
3236         mov     $num,%ecx
3237         shr     \$4,$num
3238         and     \$15,%ecx
3239         lea     -8(%ecx),%eax
3240         cmp     \$11,%ecx
3241         cmova   %r11,%r10
3242         cmova   %eax,%ecx
3243         movzw   (%r10,$num,2),%eax
3244         shrl    %cl,%eax
3245         and     \$31,%eax
3246         ret
3247 .size   bn_get_bits5,.-bn_get_bits5
3248
3249 .globl  bn_scatter5
3250 .type   bn_scatter5,\@abi-omnipotent
3251 .align  16
3252 bn_scatter5:
3253         cmp     \$0, $num
3254         jz      .Lscatter_epilogue
3255         lea     ($tbl,$idx,8),$tbl
3256 .Lscatter:
3257         mov     ($inp),%rax
3258         lea     8($inp),$inp
3259         mov     %rax,($tbl)
3260         lea     32*8($tbl),$tbl
3261         sub     \$1,$num
3262         jnz     .Lscatter
3263 .Lscatter_epilogue:
3264         ret
3265 .size   bn_scatter5,.-bn_scatter5
3266
3267 .globl  bn_gather5
3268 .type   bn_gather5,\@abi-omnipotent
3269 .align  16
3270 bn_gather5:
3271 ___
3272 $code.=<<___ if ($win64);
3273 .LSEH_begin_bn_gather5:
3274         # I can't trust assembler to use specific encoding:-(
3275         .byte   0x48,0x83,0xec,0x28             #sub    \$0x28,%rsp
3276         .byte   0x0f,0x29,0x34,0x24             #movaps %xmm6,(%rsp)
3277         .byte   0x0f,0x29,0x7c,0x24,0x10        #movdqa %xmm7,0x10(%rsp)
3278 ___
3279 $code.=<<___;
3280         mov     $idx,%r11d
3281         shr     \$`log($N/8)/log(2)`,$idx
3282         and     \$`$N/8-1`,%r11
3283         not     $idx
3284         lea     .Lmagic_masks(%rip),%rax
3285         and     \$`2**5/($N/8)-1`,$idx  # 5 is "window size"
3286         lea     128($tbl,%r11,8),$tbl   # pointer within 1st cache line
3287         movq    0(%rax,$idx,8),%xmm4    # set of masks denoting which
3288         movq    8(%rax,$idx,8),%xmm5    # cache line contains element
3289         movq    16(%rax,$idx,8),%xmm6   # denoted by 7th argument
3290         movq    24(%rax,$idx,8),%xmm7
3291         jmp     .Lgather
3292 .align  16
3293 .Lgather:
3294         movq    `0*$STRIDE/4-128`($tbl),%xmm0
3295         movq    `1*$STRIDE/4-128`($tbl),%xmm1
3296         pand    %xmm4,%xmm0
3297         movq    `2*$STRIDE/4-128`($tbl),%xmm2
3298         pand    %xmm5,%xmm1
3299         movq    `3*$STRIDE/4-128`($tbl),%xmm3
3300         pand    %xmm6,%xmm2
3301         por     %xmm1,%xmm0
3302         pand    %xmm7,%xmm3
3303         .byte   0x67,0x67
3304         por     %xmm2,%xmm0
3305         lea     $STRIDE($tbl),$tbl
3306         por     %xmm3,%xmm0
3307
3308         movq    %xmm0,($out)            # m0=bp[0]
3309         lea     8($out),$out
3310         sub     \$1,$num
3311         jnz     .Lgather
3312 ___
3313 $code.=<<___ if ($win64);
3314         movaps  (%rsp),%xmm6
3315         movaps  0x10(%rsp),%xmm7
3316         lea     0x28(%rsp),%rsp
3317 ___
3318 $code.=<<___;
3319         ret
3320 .LSEH_end_bn_gather5:
3321 .size   bn_gather5,.-bn_gather5
3322 ___
3323 }
3324 $code.=<<___;
3325 .align  64
3326 .Lmagic_masks:
3327         .long   0,0, 0,0, 0,0, -1,-1
3328         .long   0,0, 0,0, 0,0,  0,0
3329 .asciz  "Montgomery Multiplication with scatter/gather for x86_64, CRYPTOGAMS by <appro\@openssl.org>"
3330 ___
3331
3332 # EXCEPTION_DISPOSITION handler (EXCEPTION_RECORD *rec,ULONG64 frame,
3333 #               CONTEXT *context,DISPATCHER_CONTEXT *disp)
3334 if ($win64) {
3335 $rec="%rcx";
3336 $frame="%rdx";
3337 $context="%r8";
3338 $disp="%r9";
3339
3340 $code.=<<___;
3341 .extern __imp_RtlVirtualUnwind
3342 .type   mul_handler,\@abi-omnipotent
3343 .align  16
3344 mul_handler:
3345         push    %rsi
3346         push    %rdi
3347         push    %rbx
3348         push    %rbp
3349         push    %r12
3350         push    %r13
3351         push    %r14
3352         push    %r15
3353         pushfq
3354         sub     \$64,%rsp
3355
3356         mov     120($context),%rax      # pull context->Rax
3357         mov     248($context),%rbx      # pull context->Rip
3358
3359         mov     8($disp),%rsi           # disp->ImageBase
3360         mov     56($disp),%r11          # disp->HandlerData
3361
3362         mov     0(%r11),%r10d           # HandlerData[0]
3363         lea     (%rsi,%r10),%r10        # end of prologue label
3364         cmp     %r10,%rbx               # context->Rip<end of prologue label
3365         jb      .Lcommon_seh_tail
3366
3367         mov     152($context),%rax      # pull context->Rsp
3368
3369         mov     4(%r11),%r10d           # HandlerData[1]
3370         lea     (%rsi,%r10),%r10        # epilogue label
3371         cmp     %r10,%rbx               # context->Rip>=epilogue label
3372         jae     .Lcommon_seh_tail
3373
3374         lea     .Lmul_epilogue(%rip),%r10
3375         cmp     %r10,%rbx
3376         jb      .Lbody_40
3377
3378         mov     192($context),%r10      # pull $num
3379         mov     8(%rax,%r10,8),%rax     # pull saved stack pointer
3380         jmp     .Lbody_proceed
3381
3382 .Lbody_40:
3383         mov     40(%rax),%rax           # pull saved stack pointer
3384 .Lbody_proceed:
3385
3386         movaps  -88(%rax),%xmm0
3387         movaps  -72(%rax),%xmm1
3388
3389         mov     -8(%rax),%rbx
3390         mov     -16(%rax),%rbp
3391         mov     -24(%rax),%r12
3392         mov     -32(%rax),%r13
3393         mov     -40(%rax),%r14
3394         mov     -48(%rax),%r15
3395         mov     %rbx,144($context)      # restore context->Rbx
3396         mov     %rbp,160($context)      # restore context->Rbp
3397         mov     %r12,216($context)      # restore context->R12
3398         mov     %r13,224($context)      # restore context->R13
3399         mov     %r14,232($context)      # restore context->R14
3400         mov     %r15,240($context)      # restore context->R15
3401         movups  %xmm0,512($context)     # restore context->Xmm6
3402         movups  %xmm1,528($context)     # restore context->Xmm7
3403
3404 .Lcommon_seh_tail:
3405         mov     8(%rax),%rdi
3406         mov     16(%rax),%rsi
3407         mov     %rax,152($context)      # restore context->Rsp
3408         mov     %rsi,168($context)      # restore context->Rsi
3409         mov     %rdi,176($context)      # restore context->Rdi
3410
3411         mov     40($disp),%rdi          # disp->ContextRecord
3412         mov     $context,%rsi           # context
3413         mov     \$154,%ecx              # sizeof(CONTEXT)
3414         .long   0xa548f3fc              # cld; rep movsq
3415
3416         mov     $disp,%rsi
3417         xor     %rcx,%rcx               # arg1, UNW_FLAG_NHANDLER
3418         mov     8(%rsi),%rdx            # arg2, disp->ImageBase
3419         mov     0(%rsi),%r8             # arg3, disp->ControlPc
3420         mov     16(%rsi),%r9            # arg4, disp->FunctionEntry
3421         mov     40(%rsi),%r10           # disp->ContextRecord
3422         lea     56(%rsi),%r11           # &disp->HandlerData
3423         lea     24(%rsi),%r12           # &disp->EstablisherFrame
3424         mov     %r10,32(%rsp)           # arg5
3425         mov     %r11,40(%rsp)           # arg6
3426         mov     %r12,48(%rsp)           # arg7
3427         mov     %rcx,56(%rsp)           # arg8, (NULL)
3428         call    *__imp_RtlVirtualUnwind(%rip)
3429
3430         mov     \$1,%eax                # ExceptionContinueSearch
3431         add     \$64,%rsp
3432         popfq
3433         pop     %r15
3434         pop     %r14
3435         pop     %r13
3436         pop     %r12
3437         pop     %rbp
3438         pop     %rbx
3439         pop     %rdi
3440         pop     %rsi
3441         ret
3442 .size   mul_handler,.-mul_handler
3443
3444 .section        .pdata
3445 .align  4
3446         .rva    .LSEH_begin_bn_mul_mont_gather5
3447         .rva    .LSEH_end_bn_mul_mont_gather5
3448         .rva    .LSEH_info_bn_mul_mont_gather5
3449
3450         .rva    .LSEH_begin_bn_mul4x_mont_gather5
3451         .rva    .LSEH_end_bn_mul4x_mont_gather5
3452         .rva    .LSEH_info_bn_mul4x_mont_gather5
3453
3454         .rva    .LSEH_begin_bn_power5
3455         .rva    .LSEH_end_bn_power5
3456         .rva    .LSEH_info_bn_power5
3457
3458         .rva    .LSEH_begin_bn_from_mont8x
3459         .rva    .LSEH_end_bn_from_mont8x
3460         .rva    .LSEH_info_bn_from_mont8x
3461 ___
3462 $code.=<<___ if ($addx);
3463         .rva    .LSEH_begin_bn_mulx4x_mont_gather5
3464         .rva    .LSEH_end_bn_mulx4x_mont_gather5
3465         .rva    .LSEH_info_bn_mulx4x_mont_gather5
3466
3467         .rva    .LSEH_begin_bn_powerx5
3468         .rva    .LSEH_end_bn_powerx5
3469         .rva    .LSEH_info_bn_powerx5
3470 ___
3471 $code.=<<___;
3472         .rva    .LSEH_begin_bn_gather5
3473         .rva    .LSEH_end_bn_gather5
3474         .rva    .LSEH_info_bn_gather5
3475
3476 .section        .xdata
3477 .align  8
3478 .LSEH_info_bn_mul_mont_gather5:
3479         .byte   9,0,0,0
3480         .rva    mul_handler
3481         .rva    .Lmul_body,.Lmul_epilogue               # HandlerData[]
3482 .align  8
3483 .LSEH_info_bn_mul4x_mont_gather5:
3484         .byte   9,0,0,0
3485         .rva    mul_handler
3486         .rva    .Lmul4x_body,.Lmul4x_epilogue           # HandlerData[]
3487 .align  8
3488 .LSEH_info_bn_power5:
3489         .byte   9,0,0,0
3490         .rva    mul_handler
3491         .rva    .Lpower5_body,.Lpower5_epilogue         # HandlerData[]
3492 .align  8
3493 .LSEH_info_bn_from_mont8x:
3494         .byte   9,0,0,0
3495         .rva    mul_handler
3496         .rva    .Lfrom_body,.Lfrom_epilogue             # HandlerData[]
3497 ___
3498 $code.=<<___ if ($addx);
3499 .align  8
3500 .LSEH_info_bn_mulx4x_mont_gather5:
3501         .byte   9,0,0,0
3502         .rva    mul_handler
3503         .rva    .Lmulx4x_body,.Lmulx4x_epilogue         # HandlerData[]
3504 .align  8
3505 .LSEH_info_bn_powerx5:
3506         .byte   9,0,0,0
3507         .rva    mul_handler
3508         .rva    .Lpowerx5_body,.Lpowerx5_epilogue       # HandlerData[]
3509 ___
3510 $code.=<<___;
3511 .align  8
3512 .LSEH_info_bn_gather5:
3513         .byte   0x01,0x0d,0x05,0x00
3514         .byte   0x0d,0x78,0x01,0x00     #movaps 0x10(rsp),xmm7
3515         .byte   0x08,0x68,0x00,0x00     #movaps (rsp),xmm6
3516         .byte   0x04,0x42,0x00,0x00     #sub    rsp,0x28
3517 .align  8
3518 ___
3519 }
3520
3521 $code =~ s/\`([^\`]*)\`/eval($1)/gem;
3522
3523 print $code;
3524 close STDOUT;