crypto/openssl/crypto/bn/asm/x86_64-mont5.pl

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