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         add     (%rdx),%r8              # can this overflow?
1938         adc     \$0,%r9
1939         adc     \$0,%r10
1940         adc     \$0,%r11
1941         adc     \$0,%r12
1942         adc     \$0,%r13
1943         adc     \$0,%r14
1944         adc     \$0,%r15                # can't overflow, because we
1945                                         # started with "overhung" part
1946                                         # of multiplication
1947         xor     %rax,%rax
1948
1949         neg     $carry
1950 .L8x_no_tail:
1951         adc     8*0($tptr),%r8
1952         adc     8*1($tptr),%r9
1953         adc     8*2($tptr),%r10
1954         adc     8*3($tptr),%r11
1955         adc     8*4($tptr),%r12
1956         adc     8*5($tptr),%r13
1957         adc     8*6($tptr),%r14
1958         adc     8*7($tptr),%r15
1959         adc     \$0,%rax                # top-most carry
1960          mov    -8($nptr),%rcx          # np[num-1]
1961          xor    $carry,$carry
1962
1963         movq    %xmm2,$nptr             # restore $nptr
1964
1965         mov     %r8,8*0($tptr)          # store top 512 bits
1966         mov     %r9,8*1($tptr)
1967          movq   %xmm3,$num              # $num is %r9, can't be moved upwards
1968         mov     %r10,8*2($tptr)
1969         mov     %r11,8*3($tptr)
1970         mov     %r12,8*4($tptr)
1971         mov     %r13,8*5($tptr)
1972         mov     %r14,8*6($tptr)
1973         mov     %r15,8*7($tptr)
1974         lea     8*8($tptr),$tptr
1975
1976         cmp     %rdx,$tptr              # end of t[]?
1977         jb      .L8x_reduction_loop
1978         ret
1979 .size   bn_sqr8x_internal,.-bn_sqr8x_internal
1980 ___
1981 }\f
1982 ##############################################################
1983 # Post-condition, 4x unrolled
1984 #
1985 {
1986 my ($tptr,$nptr)=("%rbx","%rbp");
1987 $code.=<<___;
1988 .type   __bn_post4x_internal,\@abi-omnipotent
1989 .align  32
1990 __bn_post4x_internal:
1991         mov     8*0($nptr),%r12
1992         lea     (%rdi,$num),$tptr       # %rdi was $tptr above
1993         mov     $num,%rcx
1994         movq    %xmm1,$rptr             # restore $rptr
1995         neg     %rax
1996         movq    %xmm1,$aptr             # prepare for back-to-back call
1997         sar     \$3+2,%rcx
1998         dec     %r12                    # so that after 'not' we get -n[0]
1999         xor     %r10,%r10
2000         mov     8*1($nptr),%r13
2001         mov     8*2($nptr),%r14
2002         mov     8*3($nptr),%r15
2003         jmp     .Lsqr4x_sub_entry
2004
2005 .align  16
2006 .Lsqr4x_sub:
2007         mov     8*0($nptr),%r12
2008         mov     8*1($nptr),%r13
2009         mov     8*2($nptr),%r14
2010         mov     8*3($nptr),%r15
2011 .Lsqr4x_sub_entry:
2012         lea     8*4($nptr),$nptr
2013         not     %r12
2014         not     %r13
2015         not     %r14
2016         not     %r15
2017         and     %rax,%r12
2018         and     %rax,%r13
2019         and     %rax,%r14
2020         and     %rax,%r15
2021
2022         neg     %r10                    # mov %r10,%cf
2023         adc     8*0($tptr),%r12
2024         adc     8*1($tptr),%r13
2025         adc     8*2($tptr),%r14
2026         adc     8*3($tptr),%r15
2027         mov     %r12,8*0($rptr)
2028         lea     8*4($tptr),$tptr
2029         mov     %r13,8*1($rptr)
2030         sbb     %r10,%r10               # mov %cf,%r10
2031         mov     %r14,8*2($rptr)
2032         mov     %r15,8*3($rptr)
2033         lea     8*4($rptr),$rptr
2034
2035         inc     %rcx                    # pass %cf
2036         jnz     .Lsqr4x_sub
2037
2038         mov     $num,%r10               # prepare for back-to-back call
2039         neg     $num                    # restore $num
2040         ret
2041 .size   __bn_post4x_internal,.-__bn_post4x_internal
2042 ___
2043 }
2044 {
2045 $code.=<<___;
2046 .globl  bn_from_montgomery
2047 .type   bn_from_montgomery,\@abi-omnipotent
2048 .align  32
2049 bn_from_montgomery:
2050         testl   \$7,`($win64?"48(%rsp)":"%r9d")`
2051         jz      bn_from_mont8x
2052         xor     %eax,%eax
2053         ret
2054 .size   bn_from_montgomery,.-bn_from_montgomery
2055
2056 .type   bn_from_mont8x,\@function,6
2057 .align  32
2058 bn_from_mont8x:
2059         .byte   0x67
2060         mov     %rsp,%rax
2061         push    %rbx
2062         push    %rbp
2063         push    %r12
2064         push    %r13
2065         push    %r14
2066         push    %r15
2067 .Lfrom_prologue:
2068
2069         shl     \$3,${num}d             # convert $num to bytes
2070         lea     ($num,$num,2),%r10      # 3*$num in bytes
2071         neg     $num
2072         mov     ($n0),$n0               # *n0
2073
2074         ##############################################################
2075         # Ensure that stack frame doesn't alias with $rptr+3*$num
2076         # modulo 4096, which covers ret[num], am[num] and n[num]
2077         # (see bn_exp.c). The stack is allocated to aligned with
2078         # bn_power5's frame, and as bn_from_montgomery happens to be
2079         # last operation, we use the opportunity to cleanse it.
2080         #
2081         lea     -320(%rsp,$num,2),%r11
2082         mov     %rsp,%rbp
2083         sub     $rptr,%r11
2084         and     \$4095,%r11
2085         cmp     %r11,%r10
2086         jb      .Lfrom_sp_alt
2087         sub     %r11,%rbp               # align with $aptr
2088         lea     -320(%rbp,$num,2),%rbp  # future alloca(frame+2*$num*8+256)
2089         jmp     .Lfrom_sp_done
2090
2091 .align  32
2092 .Lfrom_sp_alt:
2093         lea     4096-320(,$num,2),%r10
2094         lea     -320(%rbp,$num,2),%rbp  # future alloca(frame+2*$num*8+256)
2095         sub     %r10,%r11
2096         mov     \$0,%r10
2097         cmovc   %r10,%r11
2098         sub     %r11,%rbp
2099 .Lfrom_sp_done:
2100         and     \$-64,%rbp
2101         mov     %rsp,%r11
2102         sub     %rbp,%r11
2103         and     \$-4096,%r11
2104         lea     (%rbp,%r11),%rsp
2105         mov     (%rsp),%r10
2106         cmp     %rbp,%rsp
2107         ja      .Lfrom_page_walk
2108         jmp     .Lfrom_page_walk_done
2109
2110 .Lfrom_page_walk:
2111         lea     -4096(%rsp),%rsp
2112         mov     (%rsp),%r10
2113         cmp     %rbp,%rsp
2114         ja      .Lfrom_page_walk
2115 .Lfrom_page_walk_done:
2116
2117         mov     $num,%r10
2118         neg     $num
2119
2120         ##############################################################
2121         # Stack layout
2122         #
2123         # +0    saved $num, used in reduction section
2124         # +8    &t[2*$num], used in reduction section
2125         # +32   saved *n0
2126         # +40   saved %rsp
2127         # +48   t[2*$num]
2128         #
2129         mov     $n0,  32(%rsp)
2130         mov     %rax, 40(%rsp)          # save original %rsp
2131 .Lfrom_body:
2132         mov     $num,%r11
2133         lea     48(%rsp),%rax
2134         pxor    %xmm0,%xmm0
2135         jmp     .Lmul_by_1
2136
2137 .align  32
2138 .Lmul_by_1:
2139         movdqu  ($aptr),%xmm1
2140         movdqu  16($aptr),%xmm2
2141         movdqu  32($aptr),%xmm3
2142         movdqa  %xmm0,(%rax,$num)
2143         movdqu  48($aptr),%xmm4
2144         movdqa  %xmm0,16(%rax,$num)
2145         .byte   0x48,0x8d,0xb6,0x40,0x00,0x00,0x00      # lea   64($aptr),$aptr
2146         movdqa  %xmm1,(%rax)
2147         movdqa  %xmm0,32(%rax,$num)
2148         movdqa  %xmm2,16(%rax)
2149         movdqa  %xmm0,48(%rax,$num)
2150         movdqa  %xmm3,32(%rax)
2151         movdqa  %xmm4,48(%rax)
2152         lea     64(%rax),%rax
2153         sub     \$64,%r11
2154         jnz     .Lmul_by_1
2155
2156         movq    $rptr,%xmm1
2157         movq    $nptr,%xmm2
2158         .byte   0x67
2159         mov     $nptr,%rbp
2160         movq    %r10, %xmm3             # -num
2161 ___
2162 $code.=<<___ if ($addx);
2163         mov     OPENSSL_ia32cap_P+8(%rip),%r11d
2164         and     \$0x80108,%r11d
2165         cmp     \$0x80108,%r11d         # check for AD*X+BMI2+BMI1
2166         jne     .Lfrom_mont_nox
2167
2168         lea     (%rax,$num),$rptr
2169         call    __bn_sqrx8x_reduction
2170         call    __bn_postx4x_internal
2171
2172         pxor    %xmm0,%xmm0
2173         lea     48(%rsp),%rax
2174         mov     40(%rsp),%rsi           # restore %rsp
2175         jmp     .Lfrom_mont_zero
2176
2177 .align  32
2178 .Lfrom_mont_nox:
2179 ___
2180 $code.=<<___;
2181         call    __bn_sqr8x_reduction
2182         call    __bn_post4x_internal
2183
2184         pxor    %xmm0,%xmm0
2185         lea     48(%rsp),%rax
2186         mov     40(%rsp),%rsi           # restore %rsp
2187         jmp     .Lfrom_mont_zero
2188
2189 .align  32
2190 .Lfrom_mont_zero:
2191         movdqa  %xmm0,16*0(%rax)
2192         movdqa  %xmm0,16*1(%rax)
2193         movdqa  %xmm0,16*2(%rax)
2194         movdqa  %xmm0,16*3(%rax)
2195         lea     16*4(%rax),%rax
2196         sub     \$32,$num
2197         jnz     .Lfrom_mont_zero
2198
2199         mov     \$1,%rax
2200         mov     -48(%rsi),%r15
2201         mov     -40(%rsi),%r14
2202         mov     -32(%rsi),%r13
2203         mov     -24(%rsi),%r12
2204         mov     -16(%rsi),%rbp
2205         mov     -8(%rsi),%rbx
2206         lea     (%rsi),%rsp
2207 .Lfrom_epilogue:
2208         ret
2209 .size   bn_from_mont8x,.-bn_from_mont8x
2210 ___
2211 }
2212 }}}
2213 \f
2214 if ($addx) {{{
2215 my $bp="%rdx";  # restore original value
2216
2217 $code.=<<___;
2218 .type   bn_mulx4x_mont_gather5,\@function,6
2219 .align  32
2220 bn_mulx4x_mont_gather5:
2221         mov     %rsp,%rax
2222 .Lmulx4x_enter:
2223         push    %rbx
2224         push    %rbp
2225         push    %r12
2226         push    %r13
2227         push    %r14
2228         push    %r15
2229 .Lmulx4x_prologue:
2230
2231         shl     \$3,${num}d             # convert $num to bytes
2232         lea     ($num,$num,2),%r10      # 3*$num in bytes
2233         neg     $num                    # -$num
2234         mov     ($n0),$n0               # *n0
2235
2236         ##############################################################
2237         # Ensure that stack frame doesn't alias with $rptr+3*$num
2238         # modulo 4096, which covers ret[num], am[num] and n[num]
2239         # (see bn_exp.c). This is done to allow memory disambiguation
2240         # logic do its magic. [Extra [num] is allocated in order
2241         # to align with bn_power5's frame, which is cleansed after
2242         # completing exponentiation. Extra 256 bytes is for power mask
2243         # calculated from 7th argument, the index.]
2244         #
2245         lea     -320(%rsp,$num,2),%r11
2246         mov     %rsp,%rbp
2247         sub     $rp,%r11
2248         and     \$4095,%r11
2249         cmp     %r11,%r10
2250         jb      .Lmulx4xsp_alt
2251         sub     %r11,%rbp               # align with $aptr
2252         lea     -320(%rbp,$num,2),%rbp  # future alloca(frame+2*$num*8+256)
2253         jmp     .Lmulx4xsp_done
2254
2255 .Lmulx4xsp_alt:
2256         lea     4096-320(,$num,2),%r10
2257         lea     -320(%rbp,$num,2),%rbp  # future alloca(frame+2*$num*8+256)
2258         sub     %r10,%r11
2259         mov     \$0,%r10
2260         cmovc   %r10,%r11
2261         sub     %r11,%rbp
2262 .Lmulx4xsp_done:
2263         and     \$-64,%rbp              # ensure alignment
2264         mov     %rsp,%r11
2265         sub     %rbp,%r11
2266         and     \$-4096,%r11
2267         lea     (%rbp,%r11),%rsp
2268         mov     (%rsp),%r10
2269         cmp     %rbp,%rsp
2270         ja      .Lmulx4x_page_walk
2271         jmp     .Lmulx4x_page_walk_done
2272
2273 .Lmulx4x_page_walk:
2274         lea     -4096(%rsp),%rsp
2275         mov     (%rsp),%r10
2276         cmp     %rbp,%rsp
2277         ja      .Lmulx4x_page_walk
2278 .Lmulx4x_page_walk_done:
2279
2280         ##############################################################
2281         # Stack layout
2282         # +0    -num
2283         # +8    off-loaded &b[i]
2284         # +16   end of b[num]
2285         # +24   inner counter
2286         # +32   saved n0
2287         # +40   saved %rsp
2288         # +48
2289         # +56   saved rp
2290         # +64   tmp[num+1]
2291         #
2292         mov     $n0, 32(%rsp)           # save *n0
2293         mov     %rax,40(%rsp)           # save original %rsp
2294 .Lmulx4x_body:
2295         call    mulx4x_internal
2296
2297         mov     40(%rsp),%rsi           # restore %rsp
2298         mov     \$1,%rax
2299
2300         mov     -48(%rsi),%r15
2301         mov     -40(%rsi),%r14
2302         mov     -32(%rsi),%r13
2303         mov     -24(%rsi),%r12
2304         mov     -16(%rsi),%rbp
2305         mov     -8(%rsi),%rbx
2306         lea     (%rsi),%rsp
2307 .Lmulx4x_epilogue:
2308         ret
2309 .size   bn_mulx4x_mont_gather5,.-bn_mulx4x_mont_gather5
2310
2311 .type   mulx4x_internal,\@abi-omnipotent
2312 .align  32
2313 mulx4x_internal:
2314         mov     $num,8(%rsp)            # save -$num (it was in bytes)
2315         mov     $num,%r10
2316         neg     $num                    # restore $num
2317         shl     \$5,$num
2318         neg     %r10                    # restore $num
2319         lea     128($bp,$num),%r13      # end of powers table (+size optimization)
2320         shr     \$5+5,$num
2321         movd    `($win64?56:8)`(%rax),%xmm5     # load 7th argument
2322         sub     \$1,$num
2323         lea     .Linc(%rip),%rax
2324         mov     %r13,16+8(%rsp)         # end of b[num]
2325         mov     $num,24+8(%rsp)         # inner counter
2326         mov     $rp, 56+8(%rsp)         # save $rp
2327 ___
2328 my ($aptr, $bptr, $nptr, $tptr, $mi,  $bi,  $zero, $num)=
2329    ("%rsi","%rdi","%rcx","%rbx","%r8","%r9","%rbp","%rax");
2330 my $rptr=$bptr;
2331 my $STRIDE=2**5*8;              # 5 is "window size"
2332 my $N=$STRIDE/4;                # should match cache line size
2333 $code.=<<___;
2334         movdqa  0(%rax),%xmm0           # 00000001000000010000000000000000
2335         movdqa  16(%rax),%xmm1          # 00000002000000020000000200000002
2336         lea     88-112(%rsp,%r10),%r10  # place the mask after tp[num+1] (+ICache optimizaton)
2337         lea     128($bp),$bptr          # size optimization
2338
2339         pshufd  \$0,%xmm5,%xmm5         # broadcast index
2340         movdqa  %xmm1,%xmm4
2341         .byte   0x67
2342         movdqa  %xmm1,%xmm2
2343 ___
2344 ########################################################################
2345 # calculate mask by comparing 0..31 to index and save result to stack
2346 #
2347 $code.=<<___;
2348         .byte   0x67
2349         paddd   %xmm0,%xmm1
2350         pcmpeqd %xmm5,%xmm0             # compare to 1,0
2351         movdqa  %xmm4,%xmm3
2352 ___
2353 for($i=0;$i<$STRIDE/16-4;$i+=4) {
2354 $code.=<<___;
2355         paddd   %xmm1,%xmm2
2356         pcmpeqd %xmm5,%xmm1             # compare to 3,2
2357         movdqa  %xmm0,`16*($i+0)+112`(%r10)
2358         movdqa  %xmm4,%xmm0
2359
2360         paddd   %xmm2,%xmm3
2361         pcmpeqd %xmm5,%xmm2             # compare to 5,4
2362         movdqa  %xmm1,`16*($i+1)+112`(%r10)
2363         movdqa  %xmm4,%xmm1
2364
2365         paddd   %xmm3,%xmm0
2366         pcmpeqd %xmm5,%xmm3             # compare to 7,6
2367         movdqa  %xmm2,`16*($i+2)+112`(%r10)
2368         movdqa  %xmm4,%xmm2
2369
2370         paddd   %xmm0,%xmm1
2371         pcmpeqd %xmm5,%xmm0
2372         movdqa  %xmm3,`16*($i+3)+112`(%r10)
2373         movdqa  %xmm4,%xmm3
2374 ___
2375 }
2376 $code.=<<___;                           # last iteration can be optimized
2377         .byte   0x67
2378         paddd   %xmm1,%xmm2
2379         pcmpeqd %xmm5,%xmm1
2380         movdqa  %xmm0,`16*($i+0)+112`(%r10)
2381
2382         paddd   %xmm2,%xmm3
2383         pcmpeqd %xmm5,%xmm2
2384         movdqa  %xmm1,`16*($i+1)+112`(%r10)
2385
2386         pcmpeqd %xmm5,%xmm3
2387         movdqa  %xmm2,`16*($i+2)+112`(%r10)
2388
2389         pand    `16*($i+0)-128`($bptr),%xmm0    # while it's still in register
2390         pand    `16*($i+1)-128`($bptr),%xmm1
2391         pand    `16*($i+2)-128`($bptr),%xmm2
2392         movdqa  %xmm3,`16*($i+3)+112`(%r10)
2393         pand    `16*($i+3)-128`($bptr),%xmm3
2394         por     %xmm2,%xmm0
2395         por     %xmm3,%xmm1
2396 ___
2397 for($i=0;$i<$STRIDE/16-4;$i+=4) {
2398 $code.=<<___;
2399         movdqa  `16*($i+0)-128`($bptr),%xmm4
2400         movdqa  `16*($i+1)-128`($bptr),%xmm5
2401         movdqa  `16*($i+2)-128`($bptr),%xmm2
2402         pand    `16*($i+0)+112`(%r10),%xmm4
2403         movdqa  `16*($i+3)-128`($bptr),%xmm3
2404         pand    `16*($i+1)+112`(%r10),%xmm5
2405         por     %xmm4,%xmm0
2406         pand    `16*($i+2)+112`(%r10),%xmm2
2407         por     %xmm5,%xmm1
2408         pand    `16*($i+3)+112`(%r10),%xmm3
2409         por     %xmm2,%xmm0
2410         por     %xmm3,%xmm1
2411 ___
2412 }
2413 $code.=<<___;
2414         pxor    %xmm1,%xmm0
2415         pshufd  \$0x4e,%xmm0,%xmm1
2416         por     %xmm1,%xmm0
2417         lea     $STRIDE($bptr),$bptr
2418         movq    %xmm0,%rdx              # bp[0]
2419         lea     64+8*4+8(%rsp),$tptr
2420
2421         mov     %rdx,$bi
2422         mulx    0*8($aptr),$mi,%rax     # a[0]*b[0]
2423         mulx    1*8($aptr),%r11,%r12    # a[1]*b[0]
2424         add     %rax,%r11
2425         mulx    2*8($aptr),%rax,%r13    # ...
2426         adc     %rax,%r12
2427         adc     \$0,%r13
2428         mulx    3*8($aptr),%rax,%r14
2429
2430         mov     $mi,%r15
2431         imulq   32+8(%rsp),$mi          # "t[0]"*n0
2432         xor     $zero,$zero             # cf=0, of=0
2433         mov     $mi,%rdx
2434
2435         mov     $bptr,8+8(%rsp)         # off-load &b[i]
2436
2437         lea     4*8($aptr),$aptr
2438         adcx    %rax,%r13
2439         adcx    $zero,%r14              # cf=0
2440
2441         mulx    0*8($nptr),%rax,%r10
2442         adcx    %rax,%r15               # discarded
2443         adox    %r11,%r10
2444         mulx    1*8($nptr),%rax,%r11
2445         adcx    %rax,%r10
2446         adox    %r12,%r11
2447         mulx    2*8($nptr),%rax,%r12
2448         mov     24+8(%rsp),$bptr        # counter value
2449         mov     %r10,-8*4($tptr)
2450         adcx    %rax,%r11
2451         adox    %r13,%r12
2452         mulx    3*8($nptr),%rax,%r15
2453          mov    $bi,%rdx
2454         mov     %r11,-8*3($tptr)
2455         adcx    %rax,%r12
2456         adox    $zero,%r15              # of=0
2457         lea     4*8($nptr),$nptr
2458         mov     %r12,-8*2($tptr)
2459         jmp     .Lmulx4x_1st
2460
2461 .align  32
2462 .Lmulx4x_1st:
2463         adcx    $zero,%r15              # cf=0, modulo-scheduled
2464         mulx    0*8($aptr),%r10,%rax    # a[4]*b[0]
2465         adcx    %r14,%r10
2466         mulx    1*8($aptr),%r11,%r14    # a[5]*b[0]
2467         adcx    %rax,%r11
2468         mulx    2*8($aptr),%r12,%rax    # ...
2469         adcx    %r14,%r12
2470         mulx    3*8($aptr),%r13,%r14
2471          .byte  0x67,0x67
2472          mov    $mi,%rdx
2473         adcx    %rax,%r13
2474         adcx    $zero,%r14              # cf=0
2475         lea     4*8($aptr),$aptr
2476         lea     4*8($tptr),$tptr
2477
2478         adox    %r15,%r10
2479         mulx    0*8($nptr),%rax,%r15
2480         adcx    %rax,%r10
2481         adox    %r15,%r11
2482         mulx    1*8($nptr),%rax,%r15
2483         adcx    %rax,%r11
2484         adox    %r15,%r12
2485         mulx    2*8($nptr),%rax,%r15
2486         mov     %r10,-5*8($tptr)
2487         adcx    %rax,%r12
2488         mov     %r11,-4*8($tptr)
2489         adox    %r15,%r13
2490         mulx    3*8($nptr),%rax,%r15
2491          mov    $bi,%rdx
2492         mov     %r12,-3*8($tptr)
2493         adcx    %rax,%r13
2494         adox    $zero,%r15
2495         lea     4*8($nptr),$nptr
2496         mov     %r13,-2*8($tptr)
2497
2498         dec     $bptr                   # of=0, pass cf
2499         jnz     .Lmulx4x_1st
2500
2501         mov     8(%rsp),$num            # load -num
2502         adc     $zero,%r15              # modulo-scheduled
2503         lea     ($aptr,$num),$aptr      # rewind $aptr
2504         add     %r15,%r14
2505         mov     8+8(%rsp),$bptr         # re-load &b[i]
2506         adc     $zero,$zero             # top-most carry
2507         mov     %r14,-1*8($tptr)
2508         jmp     .Lmulx4x_outer
2509
2510 .align  32
2511 .Lmulx4x_outer:
2512         lea     16-256($tptr),%r10      # where 256-byte mask is (+density control)
2513         pxor    %xmm4,%xmm4
2514         .byte   0x67,0x67
2515         pxor    %xmm5,%xmm5
2516 ___
2517 for($i=0;$i<$STRIDE/16;$i+=4) {
2518 $code.=<<___;
2519         movdqa  `16*($i+0)-128`($bptr),%xmm0
2520         movdqa  `16*($i+1)-128`($bptr),%xmm1
2521         movdqa  `16*($i+2)-128`($bptr),%xmm2
2522         pand    `16*($i+0)+256`(%r10),%xmm0
2523         movdqa  `16*($i+3)-128`($bptr),%xmm3
2524         pand    `16*($i+1)+256`(%r10),%xmm1
2525         por     %xmm0,%xmm4
2526         pand    `16*($i+2)+256`(%r10),%xmm2
2527         por     %xmm1,%xmm5
2528         pand    `16*($i+3)+256`(%r10),%xmm3
2529         por     %xmm2,%xmm4
2530         por     %xmm3,%xmm5
2531 ___
2532 }
2533 $code.=<<___;
2534         por     %xmm5,%xmm4
2535         pshufd  \$0x4e,%xmm4,%xmm0
2536         por     %xmm4,%xmm0
2537         lea     $STRIDE($bptr),$bptr
2538         movq    %xmm0,%rdx              # m0=bp[i]
2539
2540         mov     $zero,($tptr)           # save top-most carry
2541         lea     4*8($tptr,$num),$tptr   # rewind $tptr
2542         mulx    0*8($aptr),$mi,%r11     # a[0]*b[i]
2543         xor     $zero,$zero             # cf=0, of=0
2544         mov     %rdx,$bi
2545         mulx    1*8($aptr),%r14,%r12    # a[1]*b[i]
2546         adox    -4*8($tptr),$mi         # +t[0]
2547         adcx    %r14,%r11
2548         mulx    2*8($aptr),%r15,%r13    # ...
2549         adox    -3*8($tptr),%r11
2550         adcx    %r15,%r12
2551         mulx    3*8($aptr),%rdx,%r14
2552         adox    -2*8($tptr),%r12
2553         adcx    %rdx,%r13
2554         lea     ($nptr,$num),$nptr      # rewind $nptr
2555         lea     4*8($aptr),$aptr
2556         adox    -1*8($tptr),%r13
2557         adcx    $zero,%r14
2558         adox    $zero,%r14
2559
2560         mov     $mi,%r15
2561         imulq   32+8(%rsp),$mi          # "t[0]"*n0
2562
2563         mov     $mi,%rdx
2564         xor     $zero,$zero             # cf=0, of=0
2565         mov     $bptr,8+8(%rsp)         # off-load &b[i]
2566
2567         mulx    0*8($nptr),%rax,%r10
2568         adcx    %rax,%r15               # discarded
2569         adox    %r11,%r10
2570         mulx    1*8($nptr),%rax,%r11
2571         adcx    %rax,%r10
2572         adox    %r12,%r11
2573         mulx    2*8($nptr),%rax,%r12
2574         adcx    %rax,%r11
2575         adox    %r13,%r12
2576         mulx    3*8($nptr),%rax,%r15
2577          mov    $bi,%rdx
2578         mov     24+8(%rsp),$bptr        # counter value
2579         mov     %r10,-8*4($tptr)
2580         adcx    %rax,%r12
2581         mov     %r11,-8*3($tptr)
2582         adox    $zero,%r15              # of=0
2583         mov     %r12,-8*2($tptr)
2584         lea     4*8($nptr),$nptr
2585         jmp     .Lmulx4x_inner
2586
2587 .align  32
2588 .Lmulx4x_inner:
2589         mulx    0*8($aptr),%r10,%rax    # a[4]*b[i]
2590         adcx    $zero,%r15              # cf=0, modulo-scheduled
2591         adox    %r14,%r10
2592         mulx    1*8($aptr),%r11,%r14    # a[5]*b[i]
2593         adcx    0*8($tptr),%r10
2594         adox    %rax,%r11
2595         mulx    2*8($aptr),%r12,%rax    # ...
2596         adcx    1*8($tptr),%r11
2597         adox    %r14,%r12
2598         mulx    3*8($aptr),%r13,%r14
2599          mov    $mi,%rdx
2600         adcx    2*8($tptr),%r12
2601         adox    %rax,%r13
2602         adcx    3*8($tptr),%r13
2603         adox    $zero,%r14              # of=0
2604         lea     4*8($aptr),$aptr
2605         lea     4*8($tptr),$tptr
2606         adcx    $zero,%r14              # cf=0
2607
2608         adox    %r15,%r10
2609         mulx    0*8($nptr),%rax,%r15
2610         adcx    %rax,%r10
2611         adox    %r15,%r11
2612         mulx    1*8($nptr),%rax,%r15
2613         adcx    %rax,%r11
2614         adox    %r15,%r12
2615         mulx    2*8($nptr),%rax,%r15
2616         mov     %r10,-5*8($tptr)
2617         adcx    %rax,%r12
2618         adox    %r15,%r13
2619         mov     %r11,-4*8($tptr)
2620         mulx    3*8($nptr),%rax,%r15
2621          mov    $bi,%rdx
2622         lea     4*8($nptr),$nptr
2623         mov     %r12,-3*8($tptr)
2624         adcx    %rax,%r13
2625         adox    $zero,%r15
2626         mov     %r13,-2*8($tptr)
2627
2628         dec     $bptr                   # of=0, pass cf
2629         jnz     .Lmulx4x_inner
2630
2631         mov     0+8(%rsp),$num          # load -num
2632         adc     $zero,%r15              # modulo-scheduled
2633         sub     0*8($tptr),$bptr        # pull top-most carry to %cf
2634         mov     8+8(%rsp),$bptr         # re-load &b[i]
2635         mov     16+8(%rsp),%r10
2636         adc     %r15,%r14
2637         lea     ($aptr,$num),$aptr      # rewind $aptr
2638         adc     $zero,$zero             # top-most carry
2639         mov     %r14,-1*8($tptr)
2640
2641         cmp     %r10,$bptr
2642         jb      .Lmulx4x_outer
2643
2644         mov     -8($nptr),%r10
2645         mov     $zero,%r8
2646         mov     ($nptr,$num),%r12
2647         lea     ($nptr,$num),%rbp       # rewind $nptr
2648         mov     $num,%rcx
2649         lea     ($tptr,$num),%rdi       # rewind $tptr
2650         xor     %eax,%eax
2651         xor     %r15,%r15
2652         sub     %r14,%r10               # compare top-most words
2653         adc     %r15,%r15
2654         or      %r15,%r8
2655         sar     \$3+2,%rcx
2656         sub     %r8,%rax                # %rax=-%r8
2657         mov     56+8(%rsp),%rdx         # restore rp
2658         dec     %r12                    # so that after 'not' we get -n[0]
2659         mov     8*1(%rbp),%r13
2660         xor     %r8,%r8
2661         mov     8*2(%rbp),%r14
2662         mov     8*3(%rbp),%r15
2663         jmp     .Lsqrx4x_sub_entry      # common post-condition
2664 .size   mulx4x_internal,.-mulx4x_internal
2665 ___
2666 }\f{
2667 ######################################################################
2668 # void bn_power5(
2669 my $rptr="%rdi";        # BN_ULONG *rptr,
2670 my $aptr="%rsi";        # const BN_ULONG *aptr,
2671 my $bptr="%rdx";        # const void *table,
2672 my $nptr="%rcx";        # const BN_ULONG *nptr,
2673 my $n0  ="%r8";         # const BN_ULONG *n0);
2674 my $num ="%r9";         # int num, has to be divisible by 8
2675                         # int pwr);
2676
2677 my ($i,$j,$tptr)=("%rbp","%rcx",$rptr);
2678 my @A0=("%r10","%r11");
2679 my @A1=("%r12","%r13");
2680 my ($a0,$a1,$ai)=("%r14","%r15","%rbx");
2681
2682 $code.=<<___;
2683 .type   bn_powerx5,\@function,6
2684 .align  32
2685 bn_powerx5:
2686         mov     %rsp,%rax
2687 .Lpowerx5_enter:
2688         push    %rbx
2689         push    %rbp
2690         push    %r12
2691         push    %r13
2692         push    %r14
2693         push    %r15
2694 .Lpowerx5_prologue:
2695
2696         shl     \$3,${num}d             # convert $num to bytes
2697         lea     ($num,$num,2),%r10      # 3*$num in bytes
2698         neg     $num
2699         mov     ($n0),$n0               # *n0
2700
2701         ##############################################################
2702         # Ensure that stack frame doesn't alias with $rptr+3*$num
2703         # modulo 4096, which covers ret[num], am[num] and n[num]
2704         # (see bn_exp.c). This is done to allow memory disambiguation
2705         # logic do its magic. [Extra 256 bytes is for power mask
2706         # calculated from 7th argument, the index.]
2707         #
2708         lea     -320(%rsp,$num,2),%r11
2709         mov     %rsp,%rbp
2710         sub     $rptr,%r11
2711         and     \$4095,%r11
2712         cmp     %r11,%r10
2713         jb      .Lpwrx_sp_alt
2714         sub     %r11,%rbp               # align with $aptr
2715         lea     -320(%rbp,$num,2),%rbp  # future alloca(frame+2*$num*8+256)
2716         jmp     .Lpwrx_sp_done
2717
2718 .align  32
2719 .Lpwrx_sp_alt:
2720         lea     4096-320(,$num,2),%r10
2721         lea     -320(%rbp,$num,2),%rbp  # alloca(frame+2*$num*8+256)
2722         sub     %r10,%r11
2723         mov     \$0,%r10
2724         cmovc   %r10,%r11
2725         sub     %r11,%rbp
2726 .Lpwrx_sp_done:
2727         and     \$-64,%rbp
2728         mov     %rsp,%r11
2729         sub     %rbp,%r11
2730         and     \$-4096,%r11
2731         lea     (%rbp,%r11),%rsp
2732         mov     (%rsp),%r10
2733         cmp     %rbp,%rsp
2734         ja      .Lpwrx_page_walk
2735         jmp     .Lpwrx_page_walk_done
2736
2737 .Lpwrx_page_walk:
2738         lea     -4096(%rsp),%rsp
2739         mov     (%rsp),%r10
2740         cmp     %rbp,%rsp
2741         ja      .Lpwrx_page_walk
2742 .Lpwrx_page_walk_done:
2743
2744         mov     $num,%r10
2745         neg     $num
2746
2747         ##############################################################
2748         # Stack layout
2749         #
2750         # +0    saved $num, used in reduction section
2751         # +8    &t[2*$num], used in reduction section
2752         # +16   intermediate carry bit
2753         # +24   top-most carry bit, used in reduction section
2754         # +32   saved *n0
2755         # +40   saved %rsp
2756         # +48   t[2*$num]
2757         #
2758         pxor    %xmm0,%xmm0
2759         movq    $rptr,%xmm1             # save $rptr
2760         movq    $nptr,%xmm2             # save $nptr
2761         movq    %r10, %xmm3             # -$num
2762         movq    $bptr,%xmm4
2763         mov     $n0,  32(%rsp)
2764         mov     %rax, 40(%rsp)          # save original %rsp
2765 .Lpowerx5_body:
2766
2767         call    __bn_sqrx8x_internal
2768         call    __bn_postx4x_internal
2769         call    __bn_sqrx8x_internal
2770         call    __bn_postx4x_internal
2771         call    __bn_sqrx8x_internal
2772         call    __bn_postx4x_internal
2773         call    __bn_sqrx8x_internal
2774         call    __bn_postx4x_internal
2775         call    __bn_sqrx8x_internal
2776         call    __bn_postx4x_internal
2777
2778         mov     %r10,$num               # -num
2779         mov     $aptr,$rptr
2780         movq    %xmm2,$nptr
2781         movq    %xmm4,$bptr
2782         mov     40(%rsp),%rax
2783
2784         call    mulx4x_internal
2785
2786         mov     40(%rsp),%rsi           # restore %rsp
2787         mov     \$1,%rax
2788
2789         mov     -48(%rsi),%r15
2790         mov     -40(%rsi),%r14
2791         mov     -32(%rsi),%r13
2792         mov     -24(%rsi),%r12
2793         mov     -16(%rsi),%rbp
2794         mov     -8(%rsi),%rbx
2795         lea     (%rsi),%rsp
2796 .Lpowerx5_epilogue:
2797         ret
2798 .size   bn_powerx5,.-bn_powerx5
2799
2800 .globl  bn_sqrx8x_internal
2801 .hidden bn_sqrx8x_internal
2802 .type   bn_sqrx8x_internal,\@abi-omnipotent
2803 .align  32
2804 bn_sqrx8x_internal:
2805 __bn_sqrx8x_internal:
2806         ##################################################################
2807         # Squaring part:
2808         #
2809         # a) multiply-n-add everything but a[i]*a[i];
2810         # b) shift result of a) by 1 to the left and accumulate
2811         #    a[i]*a[i] products;
2812         #
2813         ##################################################################
2814         # a[7]a[7]a[6]a[6]a[5]a[5]a[4]a[4]a[3]a[3]a[2]a[2]a[1]a[1]a[0]a[0]
2815         #                                                     a[1]a[0]
2816         #                                                 a[2]a[0]
2817         #                                             a[3]a[0]
2818         #                                             a[2]a[1]
2819         #                                         a[3]a[1]
2820         #                                     a[3]a[2]
2821         #
2822         #                                         a[4]a[0]
2823         #                                     a[5]a[0]
2824         #                                 a[6]a[0]
2825         #                             a[7]a[0]
2826         #                                     a[4]a[1]
2827         #                                 a[5]a[1]
2828         #                             a[6]a[1]
2829         #                         a[7]a[1]
2830         #                                 a[4]a[2]
2831         #                             a[5]a[2]
2832         #                         a[6]a[2]
2833         #                     a[7]a[2]
2834         #                             a[4]a[3]
2835         #                         a[5]a[3]
2836         #                     a[6]a[3]
2837         #                 a[7]a[3]
2838         #
2839         #                     a[5]a[4]
2840         #                 a[6]a[4]
2841         #             a[7]a[4]
2842         #             a[6]a[5]
2843         #         a[7]a[5]
2844         #     a[7]a[6]
2845         # a[7]a[7]a[6]a[6]a[5]a[5]a[4]a[4]a[3]a[3]a[2]a[2]a[1]a[1]a[0]a[0]
2846 ___
2847 {
2848 my ($zero,$carry)=("%rbp","%rcx");
2849 my $aaptr=$zero;
2850 $code.=<<___;
2851         lea     48+8(%rsp),$tptr
2852         lea     ($aptr,$num),$aaptr
2853         mov     $num,0+8(%rsp)                  # save $num
2854         mov     $aaptr,8+8(%rsp)                # save end of $aptr
2855         jmp     .Lsqr8x_zero_start
2856
2857 .align  32
2858 .byte   0x66,0x66,0x66,0x2e,0x0f,0x1f,0x84,0x00,0x00,0x00,0x00,0x00
2859 .Lsqrx8x_zero:
2860         .byte   0x3e
2861         movdqa  %xmm0,0*8($tptr)
2862         movdqa  %xmm0,2*8($tptr)
2863         movdqa  %xmm0,4*8($tptr)
2864         movdqa  %xmm0,6*8($tptr)
2865 .Lsqr8x_zero_start:                     # aligned at 32
2866         movdqa  %xmm0,8*8($tptr)
2867         movdqa  %xmm0,10*8($tptr)
2868         movdqa  %xmm0,12*8($tptr)
2869         movdqa  %xmm0,14*8($tptr)
2870         lea     16*8($tptr),$tptr
2871         sub     \$64,$num
2872         jnz     .Lsqrx8x_zero
2873
2874         mov     0*8($aptr),%rdx         # a[0], modulo-scheduled
2875         #xor    %r9,%r9                 # t[1], ex-$num, zero already
2876         xor     %r10,%r10
2877         xor     %r11,%r11
2878         xor     %r12,%r12
2879         xor     %r13,%r13
2880         xor     %r14,%r14
2881         xor     %r15,%r15
2882         lea     48+8(%rsp),$tptr
2883         xor     $zero,$zero             # cf=0, cf=0
2884         jmp     .Lsqrx8x_outer_loop
2885
2886 .align  32
2887 .Lsqrx8x_outer_loop:
2888         mulx    1*8($aptr),%r8,%rax     # a[1]*a[0]
2889         adcx    %r9,%r8                 # a[1]*a[0]+=t[1]
2890         adox    %rax,%r10
2891         mulx    2*8($aptr),%r9,%rax     # a[2]*a[0]
2892         adcx    %r10,%r9
2893         adox    %rax,%r11
2894         .byte   0xc4,0xe2,0xab,0xf6,0x86,0x18,0x00,0x00,0x00    # mulx  3*8($aptr),%r10,%rax    # ...
2895         adcx    %r11,%r10
2896         adox    %rax,%r12
2897         .byte   0xc4,0xe2,0xa3,0xf6,0x86,0x20,0x00,0x00,0x00    # mulx  4*8($aptr),%r11,%rax
2898         adcx    %r12,%r11
2899         adox    %rax,%r13
2900         mulx    5*8($aptr),%r12,%rax
2901         adcx    %r13,%r12
2902         adox    %rax,%r14
2903         mulx    6*8($aptr),%r13,%rax
2904         adcx    %r14,%r13
2905         adox    %r15,%rax
2906         mulx    7*8($aptr),%r14,%r15
2907          mov    1*8($aptr),%rdx         # a[1]
2908         adcx    %rax,%r14
2909         adox    $zero,%r15
2910         adc     8*8($tptr),%r15
2911         mov     %r8,1*8($tptr)          # t[1]
2912         mov     %r9,2*8($tptr)          # t[2]
2913         sbb     $carry,$carry           # mov %cf,$carry
2914         xor     $zero,$zero             # cf=0, of=0
2915
2916
2917         mulx    2*8($aptr),%r8,%rbx     # a[2]*a[1]
2918         mulx    3*8($aptr),%r9,%rax     # a[3]*a[1]
2919         adcx    %r10,%r8
2920         adox    %rbx,%r9
2921         mulx    4*8($aptr),%r10,%rbx    # ...
2922         adcx    %r11,%r9
2923         adox    %rax,%r10
2924         .byte   0xc4,0xe2,0xa3,0xf6,0x86,0x28,0x00,0x00,0x00    # mulx  5*8($aptr),%r11,%rax
2925         adcx    %r12,%r10
2926         adox    %rbx,%r11
2927         .byte   0xc4,0xe2,0x9b,0xf6,0x9e,0x30,0x00,0x00,0x00    # mulx  6*8($aptr),%r12,%rbx
2928         adcx    %r13,%r11
2929         adox    %r14,%r12
2930         .byte   0xc4,0x62,0x93,0xf6,0xb6,0x38,0x00,0x00,0x00    # mulx  7*8($aptr),%r13,%r14
2931          mov    2*8($aptr),%rdx         # a[2]
2932         adcx    %rax,%r12
2933         adox    %rbx,%r13
2934         adcx    %r15,%r13
2935         adox    $zero,%r14              # of=0
2936         adcx    $zero,%r14              # cf=0
2937
2938         mov     %r8,3*8($tptr)          # t[3]
2939         mov     %r9,4*8($tptr)          # t[4]
2940
2941         mulx    3*8($aptr),%r8,%rbx     # a[3]*a[2]
2942         mulx    4*8($aptr),%r9,%rax     # a[4]*a[2]
2943         adcx    %r10,%r8
2944         adox    %rbx,%r9
2945         mulx    5*8($aptr),%r10,%rbx    # ...
2946         adcx    %r11,%r9
2947         adox    %rax,%r10
2948         .byte   0xc4,0xe2,0xa3,0xf6,0x86,0x30,0x00,0x00,0x00    # mulx  6*8($aptr),%r11,%rax
2949         adcx    %r12,%r10
2950         adox    %r13,%r11
2951         .byte   0xc4,0x62,0x9b,0xf6,0xae,0x38,0x00,0x00,0x00    # mulx  7*8($aptr),%r12,%r13
2952         .byte   0x3e
2953          mov    3*8($aptr),%rdx         # a[3]
2954         adcx    %rbx,%r11
2955         adox    %rax,%r12
2956         adcx    %r14,%r12
2957         mov     %r8,5*8($tptr)          # t[5]
2958         mov     %r9,6*8($tptr)          # t[6]
2959          mulx   4*8($aptr),%r8,%rax     # a[4]*a[3]
2960         adox    $zero,%r13              # of=0
2961         adcx    $zero,%r13              # cf=0
2962
2963         mulx    5*8($aptr),%r9,%rbx     # a[5]*a[3]
2964         adcx    %r10,%r8
2965         adox    %rax,%r9
2966         mulx    6*8($aptr),%r10,%rax    # ...
2967         adcx    %r11,%r9
2968         adox    %r12,%r10
2969         mulx    7*8($aptr),%r11,%r12
2970          mov    4*8($aptr),%rdx         # a[4]
2971          mov    5*8($aptr),%r14         # a[5]
2972         adcx    %rbx,%r10
2973         adox    %rax,%r11
2974          mov    6*8($aptr),%r15         # a[6]
2975         adcx    %r13,%r11
2976         adox    $zero,%r12              # of=0
2977         adcx    $zero,%r12              # cf=0
2978
2979         mov     %r8,7*8($tptr)          # t[7]
2980         mov     %r9,8*8($tptr)          # t[8]
2981
2982         mulx    %r14,%r9,%rax           # a[5]*a[4]
2983          mov    7*8($aptr),%r8          # a[7]
2984         adcx    %r10,%r9
2985         mulx    %r15,%r10,%rbx          # a[6]*a[4]
2986         adox    %rax,%r10
2987         adcx    %r11,%r10
2988         mulx    %r8,%r11,%rax           # a[7]*a[4]
2989          mov    %r14,%rdx               # a[5]
2990         adox    %rbx,%r11
2991         adcx    %r12,%r11
2992         #adox   $zero,%rax              # of=0
2993         adcx    $zero,%rax              # cf=0
2994
2995         mulx    %r15,%r14,%rbx          # a[6]*a[5]
2996         mulx    %r8,%r12,%r13           # a[7]*a[5]
2997          mov    %r15,%rdx               # a[6]
2998          lea    8*8($aptr),$aptr
2999         adcx    %r14,%r11
3000         adox    %rbx,%r12
3001         adcx    %rax,%r12
3002         adox    $zero,%r13
3003
3004         .byte   0x67,0x67
3005         mulx    %r8,%r8,%r14            # a[7]*a[6]
3006         adcx    %r8,%r13
3007         adcx    $zero,%r14
3008
3009         cmp     8+8(%rsp),$aptr
3010         je      .Lsqrx8x_outer_break
3011
3012         neg     $carry                  # mov $carry,%cf
3013         mov     \$-8,%rcx
3014         mov     $zero,%r15
3015         mov     8*8($tptr),%r8
3016         adcx    9*8($tptr),%r9          # +=t[9]
3017         adcx    10*8($tptr),%r10        # ...
3018         adcx    11*8($tptr),%r11
3019         adc     12*8($tptr),%r12
3020         adc     13*8($tptr),%r13
3021         adc     14*8($tptr),%r14
3022         adc     15*8($tptr),%r15
3023         lea     ($aptr),$aaptr
3024         lea     2*64($tptr),$tptr
3025         sbb     %rax,%rax               # mov %cf,$carry
3026
3027         mov     -64($aptr),%rdx         # a[0]
3028         mov     %rax,16+8(%rsp)         # offload $carry
3029         mov     $tptr,24+8(%rsp)
3030
3031         #lea    8*8($tptr),$tptr        # see 2*8*8($tptr) above
3032         xor     %eax,%eax               # cf=0, of=0
3033         jmp     .Lsqrx8x_loop
3034
3035 .align  32
3036 .Lsqrx8x_loop:
3037         mov     %r8,%rbx
3038         mulx    0*8($aaptr),%rax,%r8    # a[8]*a[i]
3039         adcx    %rax,%rbx               # +=t[8]
3040         adox    %r9,%r8
3041
3042         mulx    1*8($aaptr),%rax,%r9    # ...
3043         adcx    %rax,%r8
3044         adox    %r10,%r9
3045
3046         mulx    2*8($aaptr),%rax,%r10
3047         adcx    %rax,%r9
3048         adox    %r11,%r10
3049
3050         mulx    3*8($aaptr),%rax,%r11
3051         adcx    %rax,%r10
3052         adox    %r12,%r11
3053
3054         .byte   0xc4,0x62,0xfb,0xf6,0xa5,0x20,0x00,0x00,0x00    # mulx  4*8($aaptr),%rax,%r12
3055         adcx    %rax,%r11
3056         adox    %r13,%r12
3057
3058         mulx    5*8($aaptr),%rax,%r13
3059         adcx    %rax,%r12
3060         adox    %r14,%r13
3061
3062         mulx    6*8($aaptr),%rax,%r14
3063          mov    %rbx,($tptr,%rcx,8)     # store t[8+i]
3064          mov    \$0,%ebx
3065         adcx    %rax,%r13
3066         adox    %r15,%r14
3067
3068         .byte   0xc4,0x62,0xfb,0xf6,0xbd,0x38,0x00,0x00,0x00    # mulx  7*8($aaptr),%rax,%r15
3069          mov    8($aptr,%rcx,8),%rdx    # a[i]
3070         adcx    %rax,%r14
3071         adox    %rbx,%r15               # %rbx is 0, of=0
3072         adcx    %rbx,%r15               # cf=0
3073
3074         .byte   0x67
3075         inc     %rcx                    # of=0
3076         jnz     .Lsqrx8x_loop
3077
3078         lea     8*8($aaptr),$aaptr
3079         mov     \$-8,%rcx
3080         cmp     8+8(%rsp),$aaptr        # done?
3081         je      .Lsqrx8x_break
3082
3083         sub     16+8(%rsp),%rbx         # mov 16(%rsp),%cf
3084         .byte   0x66
3085         mov     -64($aptr),%rdx
3086         adcx    0*8($tptr),%r8
3087         adcx    1*8($tptr),%r9
3088         adc     2*8($tptr),%r10
3089         adc     3*8($tptr),%r11
3090         adc     4*8($tptr),%r12
3091         adc     5*8($tptr),%r13
3092         adc     6*8($tptr),%r14
3093         adc     7*8($tptr),%r15
3094         lea     8*8($tptr),$tptr
3095         .byte   0x67
3096         sbb     %rax,%rax               # mov %cf,%rax
3097         xor     %ebx,%ebx               # cf=0, of=0
3098         mov     %rax,16+8(%rsp)         # offload carry
3099         jmp     .Lsqrx8x_loop
3100
3101 .align  32
3102 .Lsqrx8x_break:
3103         sub     16+8(%rsp),%r8          # consume last carry
3104         mov     24+8(%rsp),$carry       # initial $tptr, borrow $carry
3105         mov     0*8($aptr),%rdx         # a[8], modulo-scheduled
3106         xor     %ebp,%ebp               # xor   $zero,$zero
3107         mov     %r8,0*8($tptr)
3108         cmp     $carry,$tptr            # cf=0, of=0
3109         je      .Lsqrx8x_outer_loop
3110
3111         mov     %r9,1*8($tptr)
3112          mov    1*8($carry),%r9
3113         mov     %r10,2*8($tptr)
3114          mov    2*8($carry),%r10
3115         mov     %r11,3*8($tptr)
3116          mov    3*8($carry),%r11
3117         mov     %r12,4*8($tptr)
3118          mov    4*8($carry),%r12
3119         mov     %r13,5*8($tptr)
3120          mov    5*8($carry),%r13
3121         mov     %r14,6*8($tptr)
3122          mov    6*8($carry),%r14
3123         mov     %r15,7*8($tptr)
3124          mov    7*8($carry),%r15
3125         mov     $carry,$tptr
3126         jmp     .Lsqrx8x_outer_loop
3127
3128 .align  32
3129 .Lsqrx8x_outer_break:
3130         mov     %r9,9*8($tptr)          # t[9]
3131          movq   %xmm3,%rcx              # -$num
3132         mov     %r10,10*8($tptr)        # ...
3133         mov     %r11,11*8($tptr)
3134         mov     %r12,12*8($tptr)
3135         mov     %r13,13*8($tptr)
3136         mov     %r14,14*8($tptr)
3137 ___
3138 }\f{
3139 my $i="%rcx";
3140 $code.=<<___;
3141         lea     48+8(%rsp),$tptr
3142         mov     ($aptr,$i),%rdx         # a[0]
3143
3144         mov     8($tptr),$A0[1]         # t[1]
3145         xor     $A0[0],$A0[0]           # t[0], of=0, cf=0
3146         mov     0+8(%rsp),$num          # restore $num
3147         adox    $A0[1],$A0[1]
3148          mov    16($tptr),$A1[0]        # t[2]  # prefetch
3149          mov    24($tptr),$A1[1]        # t[3]  # prefetch
3150         #jmp    .Lsqrx4x_shift_n_add    # happens to be aligned
3151
3152 .align  32
3153 .Lsqrx4x_shift_n_add:
3154         mulx    %rdx,%rax,%rbx
3155          adox   $A1[0],$A1[0]
3156         adcx    $A0[0],%rax
3157          .byte  0x48,0x8b,0x94,0x0e,0x08,0x00,0x00,0x00 # mov   8($aptr,$i),%rdx        # a[i+1]        # prefetch
3158          .byte  0x4c,0x8b,0x97,0x20,0x00,0x00,0x00      # mov   32($tptr),$A0[0]        # t[2*i+4]      # prefetch
3159          adox   $A1[1],$A1[1]
3160         adcx    $A0[1],%rbx
3161          mov    40($tptr),$A0[1]                # t[2*i+4+1]    # prefetch
3162         mov     %rax,0($tptr)
3163         mov     %rbx,8($tptr)
3164
3165         mulx    %rdx,%rax,%rbx
3166          adox   $A0[0],$A0[0]
3167         adcx    $A1[0],%rax
3168          mov    16($aptr,$i),%rdx       # a[i+2]        # prefetch
3169          mov    48($tptr),$A1[0]        # t[2*i+6]      # prefetch
3170          adox   $A0[1],$A0[1]
3171         adcx    $A1[1],%rbx
3172          mov    56($tptr),$A1[1]        # t[2*i+6+1]    # prefetch
3173         mov     %rax,16($tptr)
3174         mov     %rbx,24($tptr)
3175
3176         mulx    %rdx,%rax,%rbx
3177          adox   $A1[0],$A1[0]
3178         adcx    $A0[0],%rax
3179          mov    24($aptr,$i),%rdx       # a[i+3]        # prefetch
3180          lea    32($i),$i
3181          mov    64($tptr),$A0[0]        # t[2*i+8]      # prefetch
3182          adox   $A1[1],$A1[1]
3183         adcx    $A0[1],%rbx
3184          mov    72($tptr),$A0[1]        # t[2*i+8+1]    # prefetch
3185         mov     %rax,32($tptr)
3186         mov     %rbx,40($tptr)
3187
3188         mulx    %rdx,%rax,%rbx
3189          adox   $A0[0],$A0[0]
3190         adcx    $A1[0],%rax
3191         jrcxz   .Lsqrx4x_shift_n_add_break
3192          .byte  0x48,0x8b,0x94,0x0e,0x00,0x00,0x00,0x00 # mov   0($aptr,$i),%rdx        # a[i+4]        # prefetch
3193          adox   $A0[1],$A0[1]
3194         adcx    $A1[1],%rbx
3195          mov    80($tptr),$A1[0]        # t[2*i+10]     # prefetch
3196          mov    88($tptr),$A1[1]        # t[2*i+10+1]   # prefetch
3197         mov     %rax,48($tptr)
3198         mov     %rbx,56($tptr)
3199         lea     64($tptr),$tptr
3200         nop
3201         jmp     .Lsqrx4x_shift_n_add
3202
3203 .align  32
3204 .Lsqrx4x_shift_n_add_break:
3205         adcx    $A1[1],%rbx
3206         mov     %rax,48($tptr)
3207         mov     %rbx,56($tptr)
3208         lea     64($tptr),$tptr         # end of t[] buffer
3209 ___
3210 }\f
3211 ######################################################################
3212 # Montgomery reduction part, "word-by-word" algorithm.
3213 #
3214 # This new path is inspired by multiple submissions from Intel, by
3215 # Shay Gueron, Vlad Krasnov, Erdinc Ozturk, James Guilford,
3216 # Vinodh Gopal...
3217 {
3218 my ($nptr,$carry,$m0)=("%rbp","%rsi","%rdx");
3219
3220 $code.=<<___;
3221         movq    %xmm2,$nptr
3222 __bn_sqrx8x_reduction:
3223         xor     %eax,%eax               # initial top-most carry bit
3224         mov     32+8(%rsp),%rbx         # n0
3225         mov     48+8(%rsp),%rdx         # "%r8", 8*0($tptr)
3226         lea     -8*8($nptr,$num),%rcx   # end of n[]
3227         #lea    48+8(%rsp,$num,2),$tptr # end of t[] buffer
3228         mov     %rcx, 0+8(%rsp)         # save end of n[]
3229         mov     $tptr,8+8(%rsp)         # save end of t[]
3230
3231         lea     48+8(%rsp),$tptr                # initial t[] window
3232         jmp     .Lsqrx8x_reduction_loop
3233
3234 .align  32
3235 .Lsqrx8x_reduction_loop:
3236         mov     8*1($tptr),%r9
3237         mov     8*2($tptr),%r10
3238         mov     8*3($tptr),%r11
3239         mov     8*4($tptr),%r12
3240         mov     %rdx,%r8
3241         imulq   %rbx,%rdx               # n0*a[i]
3242         mov     8*5($tptr),%r13
3243         mov     8*6($tptr),%r14
3244         mov     8*7($tptr),%r15
3245         mov     %rax,24+8(%rsp)         # store top-most carry bit
3246
3247         lea     8*8($tptr),$tptr
3248         xor     $carry,$carry           # cf=0,of=0
3249         mov     \$-8,%rcx
3250         jmp     .Lsqrx8x_reduce
3251
3252 .align  32
3253 .Lsqrx8x_reduce:
3254         mov     %r8, %rbx
3255         mulx    8*0($nptr),%rax,%r8     # n[0]
3256         adcx    %rbx,%rax               # discarded
3257         adox    %r9,%r8
3258
3259         mulx    8*1($nptr),%rbx,%r9     # n[1]
3260         adcx    %rbx,%r8
3261         adox    %r10,%r9
3262
3263         mulx    8*2($nptr),%rbx,%r10
3264         adcx    %rbx,%r9
3265         adox    %r11,%r10
3266
3267         mulx    8*3($nptr),%rbx,%r11
3268         adcx    %rbx,%r10
3269         adox    %r12,%r11
3270
3271         .byte   0xc4,0x62,0xe3,0xf6,0xa5,0x20,0x00,0x00,0x00    # mulx  8*4($nptr),%rbx,%r12
3272          mov    %rdx,%rax
3273          mov    %r8,%rdx
3274         adcx    %rbx,%r11
3275         adox    %r13,%r12
3276
3277          mulx   32+8(%rsp),%rbx,%rdx    # %rdx discarded
3278          mov    %rax,%rdx
3279          mov    %rax,64+48+8(%rsp,%rcx,8)       # put aside n0*a[i]
3280
3281         mulx    8*5($nptr),%rax,%r13
3282         adcx    %rax,%r12
3283         adox    %r14,%r13
3284
3285         mulx    8*6($nptr),%rax,%r14
3286         adcx    %rax,%r13
3287         adox    %r15,%r14
3288
3289         mulx    8*7($nptr),%rax,%r15
3290          mov    %rbx,%rdx
3291         adcx    %rax,%r14
3292         adox    $carry,%r15             # $carry is 0
3293         adcx    $carry,%r15             # cf=0
3294
3295         .byte   0x67,0x67,0x67
3296         inc     %rcx                    # of=0
3297         jnz     .Lsqrx8x_reduce
3298
3299         mov     $carry,%rax             # xor   %rax,%rax
3300         cmp     0+8(%rsp),$nptr         # end of n[]?
3301         jae     .Lsqrx8x_no_tail
3302
3303         mov     48+8(%rsp),%rdx         # pull n0*a[0]
3304         add     8*0($tptr),%r8
3305         lea     8*8($nptr),$nptr
3306         mov     \$-8,%rcx
3307         adcx    8*1($tptr),%r9
3308         adcx    8*2($tptr),%r10
3309         adc     8*3($tptr),%r11
3310         adc     8*4($tptr),%r12
3311         adc     8*5($tptr),%r13
3312         adc     8*6($tptr),%r14
3313         adc     8*7($tptr),%r15
3314         lea     8*8($tptr),$tptr
3315         sbb     %rax,%rax               # top carry
3316
3317         xor     $carry,$carry           # of=0, cf=0
3318         mov     %rax,16+8(%rsp)
3319         jmp     .Lsqrx8x_tail
3320
3321 .align  32
3322 .Lsqrx8x_tail:
3323         mov     %r8,%rbx
3324         mulx    8*0($nptr),%rax,%r8
3325         adcx    %rax,%rbx
3326         adox    %r9,%r8
3327
3328         mulx    8*1($nptr),%rax,%r9
3329         adcx    %rax,%r8
3330         adox    %r10,%r9
3331
3332         mulx    8*2($nptr),%rax,%r10
3333         adcx    %rax,%r9
3334         adox    %r11,%r10
3335
3336         mulx    8*3($nptr),%rax,%r11
3337         adcx    %rax,%r10
3338         adox    %r12,%r11
3339
3340         .byte   0xc4,0x62,0xfb,0xf6,0xa5,0x20,0x00,0x00,0x00    # mulx  8*4($nptr),%rax,%r12
3341         adcx    %rax,%r11
3342         adox    %r13,%r12
3343
3344         mulx    8*5($nptr),%rax,%r13
3345         adcx    %rax,%r12
3346         adox    %r14,%r13
3347
3348         mulx    8*6($nptr),%rax,%r14
3349         adcx    %rax,%r13
3350         adox    %r15,%r14
3351
3352         mulx    8*7($nptr),%rax,%r15
3353          mov    72+48+8(%rsp,%rcx,8),%rdx       # pull n0*a[i]
3354         adcx    %rax,%r14
3355         adox    $carry,%r15
3356          mov    %rbx,($tptr,%rcx,8)     # save result
3357          mov    %r8,%rbx
3358         adcx    $carry,%r15             # cf=0
3359
3360         inc     %rcx                    # of=0
3361         jnz     .Lsqrx8x_tail
3362
3363         cmp     0+8(%rsp),$nptr         # end of n[]?
3364         jae     .Lsqrx8x_tail_done      # break out of loop
3365
3366         sub     16+8(%rsp),$carry       # mov 16(%rsp),%cf
3367          mov    48+8(%rsp),%rdx         # pull n0*a[0]
3368          lea    8*8($nptr),$nptr
3369         adc     8*0($tptr),%r8
3370         adc     8*1($tptr),%r9
3371         adc     8*2($tptr),%r10
3372         adc     8*3($tptr),%r11
3373         adc     8*4($tptr),%r12
3374         adc     8*5($tptr),%r13
3375         adc     8*6($tptr),%r14
3376         adc     8*7($tptr),%r15
3377         lea     8*8($tptr),$tptr
3378         sbb     %rax,%rax
3379         sub     \$8,%rcx                # mov   \$-8,%rcx
3380
3381         xor     $carry,$carry           # of=0, cf=0
3382         mov     %rax,16+8(%rsp)
3383         jmp     .Lsqrx8x_tail
3384
3385 .align  32
3386 .Lsqrx8x_tail_done:
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                # can't overflow, because we
3395                                         # started with "overhung" part
3396                                         # of multiplication
3397         mov     $carry,%rax             # xor   %rax,%rax
3398
3399         sub     16+8(%rsp),$carry       # mov 16(%rsp),%cf
3400 .Lsqrx8x_no_tail:                       # %cf is 0 if jumped here
3401         adc     8*0($tptr),%r8
3402          movq   %xmm3,%rcx
3403         adc     8*1($tptr),%r9
3404          mov    8*7($nptr),$carry
3405          movq   %xmm2,$nptr             # restore $nptr
3406         adc     8*2($tptr),%r10
3407         adc     8*3($tptr),%r11
3408         adc     8*4($tptr),%r12
3409         adc     8*5($tptr),%r13
3410         adc     8*6($tptr),%r14
3411         adc     8*7($tptr),%r15
3412         adc     %rax,%rax               # top-most carry
3413
3414         mov     32+8(%rsp),%rbx         # n0
3415         mov     8*8($tptr,%rcx),%rdx    # modulo-scheduled "%r8"
3416
3417         mov     %r8,8*0($tptr)          # store top 512 bits
3418          lea    8*8($tptr),%r8          # borrow %r8
3419         mov     %r9,8*1($tptr)
3420         mov     %r10,8*2($tptr)
3421         mov     %r11,8*3($tptr)
3422         mov     %r12,8*4($tptr)
3423         mov     %r13,8*5($tptr)
3424         mov     %r14,8*6($tptr)
3425         mov     %r15,8*7($tptr)
3426
3427         lea     8*8($tptr,%rcx),$tptr   # start of current t[] window
3428         cmp     8+8(%rsp),%r8           # end of t[]?
3429         jb      .Lsqrx8x_reduction_loop
3430         ret
3431 .size   bn_sqrx8x_internal,.-bn_sqrx8x_internal
3432 ___
3433 }\f
3434 ##############################################################
3435 # Post-condition, 4x unrolled
3436 #
3437 {
3438 my ($rptr,$nptr)=("%rdx","%rbp");
3439 $code.=<<___;
3440 .align  32
3441 __bn_postx4x_internal:
3442         mov     8*0($nptr),%r12
3443         mov     %rcx,%r10               # -$num
3444         mov     %rcx,%r9                # -$num
3445         neg     %rax
3446         sar     \$3+2,%rcx
3447         #lea    48+8(%rsp,%r9),$tptr
3448         movq    %xmm1,$rptr             # restore $rptr
3449         movq    %xmm1,$aptr             # prepare for back-to-back call
3450         dec     %r12                    # so that after 'not' we get -n[0]
3451         mov     8*1($nptr),%r13
3452         xor     %r8,%r8
3453         mov     8*2($nptr),%r14
3454         mov     8*3($nptr),%r15
3455         jmp     .Lsqrx4x_sub_entry
3456
3457 .align  16
3458 .Lsqrx4x_sub:
3459         mov     8*0($nptr),%r12
3460         mov     8*1($nptr),%r13
3461         mov     8*2($nptr),%r14
3462         mov     8*3($nptr),%r15
3463 .Lsqrx4x_sub_entry:
3464         andn    %rax,%r12,%r12
3465         lea     8*4($nptr),$nptr
3466         andn    %rax,%r13,%r13
3467         andn    %rax,%r14,%r14
3468         andn    %rax,%r15,%r15
3469
3470         neg     %r8                     # mov %r8,%cf
3471         adc     8*0($tptr),%r12
3472         adc     8*1($tptr),%r13
3473         adc     8*2($tptr),%r14
3474         adc     8*3($tptr),%r15
3475         mov     %r12,8*0($rptr)
3476         lea     8*4($tptr),$tptr
3477         mov     %r13,8*1($rptr)
3478         sbb     %r8,%r8                 # mov %cf,%r8
3479         mov     %r14,8*2($rptr)
3480         mov     %r15,8*3($rptr)
3481         lea     8*4($rptr),$rptr
3482
3483         inc     %rcx
3484         jnz     .Lsqrx4x_sub
3485
3486         neg     %r9                     # restore $num
3487
3488         ret
3489 .size   __bn_postx4x_internal,.-__bn_postx4x_internal
3490 ___
3491 }
3492 }}}
3493 {
3494 my ($inp,$num,$tbl,$idx)=$win64?("%rcx","%edx","%r8", "%r9d") : # Win64 order
3495                                 ("%rdi","%esi","%rdx","%ecx");  # Unix order
3496 my $out=$inp;
3497 my $STRIDE=2**5*8;
3498 my $N=$STRIDE/4;
3499
3500 $code.=<<___;
3501 .globl  bn_get_bits5
3502 .type   bn_get_bits5,\@abi-omnipotent
3503 .align  16
3504 bn_get_bits5:
3505         lea     0($inp),%r10
3506         lea     1($inp),%r11
3507         mov     $num,%ecx
3508         shr     \$4,$num
3509         and     \$15,%ecx
3510         lea     -8(%ecx),%eax
3511         cmp     \$11,%ecx
3512         cmova   %r11,%r10
3513         cmova   %eax,%ecx
3514         movzw   (%r10,$num,2),%eax
3515         shrl    %cl,%eax
3516         and     \$31,%eax
3517         ret
3518 .size   bn_get_bits5,.-bn_get_bits5
3519
3520 .globl  bn_scatter5
3521 .type   bn_scatter5,\@abi-omnipotent
3522 .align  16
3523 bn_scatter5:
3524         cmp     \$0, $num
3525         jz      .Lscatter_epilogue
3526         lea     ($tbl,$idx,8),$tbl
3527 .Lscatter:
3528         mov     ($inp),%rax
3529         lea     8($inp),$inp
3530         mov     %rax,($tbl)
3531         lea     32*8($tbl),$tbl
3532         sub     \$1,$num
3533         jnz     .Lscatter
3534 .Lscatter_epilogue:
3535         ret
3536 .size   bn_scatter5,.-bn_scatter5
3537
3538 .globl  bn_gather5
3539 .type   bn_gather5,\@abi-omnipotent
3540 .align  32
3541 bn_gather5:
3542 .LSEH_begin_bn_gather5:                 # Win64 thing, but harmless in other cases
3543         # I can't trust assembler to use specific encoding:-(
3544         .byte   0x4c,0x8d,0x14,0x24                     #lea    (%rsp),%r10
3545         .byte   0x48,0x81,0xec,0x08,0x01,0x00,0x00      #sub    $0x108,%rsp
3546         lea     .Linc(%rip),%rax
3547         and     \$-16,%rsp              # shouldn't be formally required
3548
3549         movd    $idx,%xmm5
3550         movdqa  0(%rax),%xmm0           # 00000001000000010000000000000000
3551         movdqa  16(%rax),%xmm1          # 00000002000000020000000200000002
3552         lea     128($tbl),%r11          # size optimization
3553         lea     128(%rsp),%rax          # size optimization
3554
3555         pshufd  \$0,%xmm5,%xmm5         # broadcast $idx
3556         movdqa  %xmm1,%xmm4
3557         movdqa  %xmm1,%xmm2
3558 ___
3559 ########################################################################
3560 # calculate mask by comparing 0..31 to $idx and save result to stack
3561 #
3562 for($i=0;$i<$STRIDE/16;$i+=4) {
3563 $code.=<<___;
3564         paddd   %xmm0,%xmm1
3565         pcmpeqd %xmm5,%xmm0             # compare to 1,0
3566 ___
3567 $code.=<<___    if ($i);
3568         movdqa  %xmm3,`16*($i-1)-128`(%rax)
3569 ___
3570 $code.=<<___;
3571         movdqa  %xmm4,%xmm3
3572
3573         paddd   %xmm1,%xmm2
3574         pcmpeqd %xmm5,%xmm1             # compare to 3,2
3575         movdqa  %xmm0,`16*($i+0)-128`(%rax)
3576         movdqa  %xmm4,%xmm0
3577
3578         paddd   %xmm2,%xmm3
3579         pcmpeqd %xmm5,%xmm2             # compare to 5,4
3580         movdqa  %xmm1,`16*($i+1)-128`(%rax)
3581         movdqa  %xmm4,%xmm1
3582
3583         paddd   %xmm3,%xmm0
3584         pcmpeqd %xmm5,%xmm3             # compare to 7,6
3585         movdqa  %xmm2,`16*($i+2)-128`(%rax)
3586         movdqa  %xmm4,%xmm2
3587 ___
3588 }
3589 $code.=<<___;
3590         movdqa  %xmm3,`16*($i-1)-128`(%rax)
3591         jmp     .Lgather
3592
3593 .align  32
3594 .Lgather:
3595         pxor    %xmm4,%xmm4
3596         pxor    %xmm5,%xmm5
3597 ___
3598 for($i=0;$i<$STRIDE/16;$i+=4) {
3599 $code.=<<___;
3600         movdqa  `16*($i+0)-128`(%r11),%xmm0
3601         movdqa  `16*($i+1)-128`(%r11),%xmm1
3602         movdqa  `16*($i+2)-128`(%r11),%xmm2
3603         pand    `16*($i+0)-128`(%rax),%xmm0
3604         movdqa  `16*($i+3)-128`(%r11),%xmm3
3605         pand    `16*($i+1)-128`(%rax),%xmm1
3606         por     %xmm0,%xmm4
3607         pand    `16*($i+2)-128`(%rax),%xmm2
3608         por     %xmm1,%xmm5
3609         pand    `16*($i+3)-128`(%rax),%xmm3
3610         por     %xmm2,%xmm4
3611         por     %xmm3,%xmm5
3612 ___
3613 }
3614 $code.=<<___;
3615         por     %xmm5,%xmm4
3616         lea     $STRIDE(%r11),%r11
3617         pshufd  \$0x4e,%xmm4,%xmm0
3618         por     %xmm4,%xmm0
3619         movq    %xmm0,($out)            # m0=bp[0]
3620         lea     8($out),$out
3621         sub     \$1,$num
3622         jnz     .Lgather
3623
3624         lea     (%r10),%rsp
3625         ret
3626 .LSEH_end_bn_gather5:
3627 .size   bn_gather5,.-bn_gather5
3628 ___
3629 }
3630 $code.=<<___;
3631 .align  64
3632 .Linc:
3633         .long   0,0, 1,1
3634         .long   2,2, 2,2
3635 .asciz  "Montgomery Multiplication with scatter/gather for x86_64, CRYPTOGAMS by <appro\@openssl.org>"
3636 ___
3637
3638 # EXCEPTION_DISPOSITION handler (EXCEPTION_RECORD *rec,ULONG64 frame,
3639 #               CONTEXT *context,DISPATCHER_CONTEXT *disp)
3640 if ($win64) {
3641 $rec="%rcx";
3642 $frame="%rdx";
3643 $context="%r8";
3644 $disp="%r9";
3645
3646 $code.=<<___;
3647 .extern __imp_RtlVirtualUnwind
3648 .type   mul_handler,\@abi-omnipotent
3649 .align  16
3650 mul_handler:
3651         push    %rsi
3652         push    %rdi
3653         push    %rbx
3654         push    %rbp
3655         push    %r12
3656         push    %r13
3657         push    %r14
3658         push    %r15
3659         pushfq
3660         sub     \$64,%rsp
3661
3662         mov     120($context),%rax      # pull context->Rax
3663         mov     248($context),%rbx      # pull context->Rip
3664
3665         mov     8($disp),%rsi           # disp->ImageBase
3666         mov     56($disp),%r11          # disp->HandlerData
3667
3668         mov     0(%r11),%r10d           # HandlerData[0]
3669         lea     (%rsi,%r10),%r10        # end of prologue label
3670         cmp     %r10,%rbx               # context->Rip<end of prologue label
3671         jb      .Lcommon_seh_tail
3672
3673         mov     4(%r11),%r10d           # HandlerData[1]
3674         lea     (%rsi,%r10),%r10        # epilogue label
3675         cmp     %r10,%rbx               # context->Rip>=epilogue label
3676         jb      .Lcommon_pop_regs
3677
3678         mov     152($context),%rax      # pull context->Rsp
3679
3680         mov     8(%r11),%r10d           # HandlerData[2]
3681         lea     (%rsi,%r10),%r10        # epilogue label
3682         cmp     %r10,%rbx               # context->Rip>=epilogue label
3683         jae     .Lcommon_seh_tail
3684
3685         lea     .Lmul_epilogue(%rip),%r10
3686         cmp     %r10,%rbx
3687         ja      .Lbody_40
3688
3689         mov     192($context),%r10      # pull $num
3690         mov     8(%rax,%r10,8),%rax     # pull saved stack pointer
3691
3692         jmp     .Lcommon_pop_regs
3693
3694 .Lbody_40:
3695         mov     40(%rax),%rax           # pull saved stack pointer
3696 .Lcommon_pop_regs:
3697         mov     -8(%rax),%rbx
3698         mov     -16(%rax),%rbp
3699         mov     -24(%rax),%r12
3700         mov     -32(%rax),%r13
3701         mov     -40(%rax),%r14
3702         mov     -48(%rax),%r15
3703         mov     %rbx,144($context)      # restore context->Rbx
3704         mov     %rbp,160($context)      # restore context->Rbp
3705         mov     %r12,216($context)      # restore context->R12
3706         mov     %r13,224($context)      # restore context->R13
3707         mov     %r14,232($context)      # restore context->R14
3708         mov     %r15,240($context)      # restore context->R15
3709
3710 .Lcommon_seh_tail:
3711         mov     8(%rax),%rdi
3712         mov     16(%rax),%rsi
3713         mov     %rax,152($context)      # restore context->Rsp
3714         mov     %rsi,168($context)      # restore context->Rsi
3715         mov     %rdi,176($context)      # restore context->Rdi
3716
3717         mov     40($disp),%rdi          # disp->ContextRecord
3718         mov     $context,%rsi           # context
3719         mov     \$154,%ecx              # sizeof(CONTEXT)
3720         .long   0xa548f3fc              # cld; rep movsq
3721
3722         mov     $disp,%rsi
3723         xor     %rcx,%rcx               # arg1, UNW_FLAG_NHANDLER
3724         mov     8(%rsi),%rdx            # arg2, disp->ImageBase
3725         mov     0(%rsi),%r8             # arg3, disp->ControlPc
3726         mov     16(%rsi),%r9            # arg4, disp->FunctionEntry
3727         mov     40(%rsi),%r10           # disp->ContextRecord
3728         lea     56(%rsi),%r11           # &disp->HandlerData
3729         lea     24(%rsi),%r12           # &disp->EstablisherFrame
3730         mov     %r10,32(%rsp)           # arg5
3731         mov     %r11,40(%rsp)           # arg6
3732         mov     %r12,48(%rsp)           # arg7
3733         mov     %rcx,56(%rsp)           # arg8, (NULL)
3734         call    *__imp_RtlVirtualUnwind(%rip)
3735
3736         mov     \$1,%eax                # ExceptionContinueSearch
3737         add     \$64,%rsp
3738         popfq
3739         pop     %r15
3740         pop     %r14
3741         pop     %r13
3742         pop     %r12
3743         pop     %rbp
3744         pop     %rbx
3745         pop     %rdi
3746         pop     %rsi
3747         ret
3748 .size   mul_handler,.-mul_handler
3749
3750 .section        .pdata
3751 .align  4
3752         .rva    .LSEH_begin_bn_mul_mont_gather5
3753         .rva    .LSEH_end_bn_mul_mont_gather5
3754         .rva    .LSEH_info_bn_mul_mont_gather5
3755
3756         .rva    .LSEH_begin_bn_mul4x_mont_gather5
3757         .rva    .LSEH_end_bn_mul4x_mont_gather5
3758         .rva    .LSEH_info_bn_mul4x_mont_gather5
3759
3760         .rva    .LSEH_begin_bn_power5
3761         .rva    .LSEH_end_bn_power5
3762         .rva    .LSEH_info_bn_power5
3763
3764         .rva    .LSEH_begin_bn_from_mont8x
3765         .rva    .LSEH_end_bn_from_mont8x
3766         .rva    .LSEH_info_bn_from_mont8x
3767 ___
3768 $code.=<<___ if ($addx);
3769         .rva    .LSEH_begin_bn_mulx4x_mont_gather5
3770         .rva    .LSEH_end_bn_mulx4x_mont_gather5
3771         .rva    .LSEH_info_bn_mulx4x_mont_gather5
3772
3773         .rva    .LSEH_begin_bn_powerx5
3774         .rva    .LSEH_end_bn_powerx5
3775         .rva    .LSEH_info_bn_powerx5
3776 ___
3777 $code.=<<___;
3778         .rva    .LSEH_begin_bn_gather5
3779         .rva    .LSEH_end_bn_gather5
3780         .rva    .LSEH_info_bn_gather5
3781
3782 .section        .xdata
3783 .align  8
3784 .LSEH_info_bn_mul_mont_gather5:
3785         .byte   9,0,0,0
3786         .rva    mul_handler
3787         .rva    .Lmul_body,.Lmul_body,.Lmul_epilogue            # HandlerData[]
3788 .align  8
3789 .LSEH_info_bn_mul4x_mont_gather5:
3790         .byte   9,0,0,0
3791         .rva    mul_handler
3792         .rva    .Lmul4x_prologue,.Lmul4x_body,.Lmul4x_epilogue          # HandlerData[]
3793 .align  8
3794 .LSEH_info_bn_power5:
3795         .byte   9,0,0,0
3796         .rva    mul_handler
3797         .rva    .Lpower5_prologue,.Lpower5_body,.Lpower5_epilogue       # HandlerData[]
3798 .align  8
3799 .LSEH_info_bn_from_mont8x:
3800         .byte   9,0,0,0
3801         .rva    mul_handler
3802         .rva    .Lfrom_prologue,.Lfrom_body,.Lfrom_epilogue             # HandlerData[]
3803 ___
3804 $code.=<<___ if ($addx);
3805 .align  8
3806 .LSEH_info_bn_mulx4x_mont_gather5:
3807         .byte   9,0,0,0
3808         .rva    mul_handler
3809         .rva    .Lmulx4x_prologue,.Lmulx4x_body,.Lmulx4x_epilogue       # HandlerData[]
3810 .align  8
3811 .LSEH_info_bn_powerx5:
3812         .byte   9,0,0,0
3813         .rva    mul_handler
3814         .rva    .Lpowerx5_prologue,.Lpowerx5_body,.Lpowerx5_epilogue    # HandlerData[]
3815 ___
3816 $code.=<<___;
3817 .align  8
3818 .LSEH_info_bn_gather5:
3819         .byte   0x01,0x0b,0x03,0x0a
3820         .byte   0x0b,0x01,0x21,0x00     # sub   rsp,0x108
3821         .byte   0x04,0xa3,0x00,0x00     # lea   r10,(rsp)
3822 .align  8
3823 ___
3824 }
3825
3826 $code =~ s/\`([^\`]*)\`/eval($1)/gem;
3827
3828 print $code;
3829 close STDOUT;