crypto/bn/asm/x86_64-mont5.pl

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