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