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