crypto/bn/asm/x86_64-mont5.pl

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