crypto/bn/asm/x86_64-mont5.pl

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