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