crypto/bn/asm/x86_64-mont5.pl

   1 #!/usr/bin/env perl
   2
   3 # ====================================================================
   4 # Written by Andy Polyakov <appro@openssl.org> for the OpenSSL
   5 # project. The module is, however, dual licensed under OpenSSL and
   6 # CRYPTOGAMS licenses depending on where you obtain it. For further
   7 # details see http://www.openssl.org/~appro/cryptogams/.
   8 # ====================================================================
   9
  10 # August 2011.
  11 #
  12 # Companion to x86_64-mont.pl that optimizes cache-timing attack
  13 # countermeasures. The subroutines are produced by replacing bp[i]
  14 # references in their x86_64-mont.pl counterparts with cache-neutral
  15 # references to powers table computed in BN_mod_exp_mont_consttime.
  16 # In addition subroutine that scatters elements of the powers table
  17 # is implemented, so that scatter-/gathering can be tuned without
  18 # bn_exp.c modifications.
  19
  20 $flavour = shift;
  21 $output  = shift;
  22 if ($flavour =~ /\./) { $output = $flavour; undef $flavour; }
  23
  24 $win64=0; $win64=1 if ($flavour =~ /[nm]asm|mingw64/ || $output =~ /\.asm$/);
  25
  26 $0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
  27 ( $xlate="${dir}x86_64-xlate.pl" and -f $xlate ) or
  28 ( $xlate="${dir}../../perlasm/x86_64-xlate.pl" and -f $xlate) or
  29 die "can't locate x86_64-xlate.pl";
  30
  31 open OUT,"| \"$^X\" $xlate $flavour $output";
  32 *STDOUT=*OUT;
  33
  34 if (`$ENV{CC} -Wa,-v -c -o /dev/null -x assembler /dev/null 2>&1`
  35                 =~ /GNU assembler version ([2-9]\.[0-9]+)/) {
  36         $addx = ($1>=2.22);
  37 }
  38
  39 if (!$addx && $win64 && ($flavour =~ /nasm/ || $ENV{ASM} =~ /nasm/) &&
  40             `nasm -v 2>&1` =~ /NASM version ([2-9]\.[0-9]+)/) {
  41         $addx = ($1>=2.10);
  42 }
  43
  44 if (!$addx && $win64 && ($flavour =~ /masm/ || $ENV{ASM} =~ /ml64/) &&
  45             `ml64 2>&1` =~ /Version ([0-9]+)\./) {
  46         $addx = ($1>=11);
  47 }
  48
  49 # int bn_mul_mont_gather5(
  50 $rp="%rdi";     # BN_ULONG *rp,
  51 $ap="%rsi";     # const BN_ULONG *ap,
  52 $bp="%rdx";     # const BN_ULONG *bp,
  53 $np="%rcx";     # const BN_ULONG *np,
  54 $n0="%r8";      # const BN_ULONG *n0,
  55 $num="%r9";     # int num,
  56                 # int idx);     # 0 to 2^5-1, "index" in $bp holding
  57                                 # pre-computed powers of a', interlaced
  58                                 # in such manner that b[0] is $bp[idx],
  59                                 # b[1] is [2^5+idx], etc.
  60 $lo0="%r10";
  61 $hi0="%r11";
  62 $hi1="%r13";
  63 $i="%r14";
  64 $j="%r15";
  65 $m0="%rbx";
  66 $m1="%rbp";
  67
  68 $code=<<___;
  69 .text
  70
  71 .extern OPENSSL_ia32cap_P
  72
  73 .globl  bn_mul_mont_gather5
  74 .type   bn_mul_mont_gather5,\@function,6
  75 .align  64
  76 bn_mul_mont_gather5:
  77         test    \$3,${num}d
  78         jnz     .Lmul_enter
  79         cmp     \$8,${num}d
  80         jb      .Lmul_enter
  81 ___
  82 $code.=<<___ if ($addx);
  83         mov     OPENSSL_ia32cap_P+8(%rip),%r11d
  84 ___
  85 $code.=<<___;
  86         jmp     .Lmul4x_enter
  87
  88 .align  16
  89 .Lmul_enter:
  90         mov     ${num}d,${num}d
  91         mov     `($win64?56:8)`(%rsp),%r10d     # load 7th argument
  92         push    %rbx
  93         push    %rbp
  94         push    %r12
  95         push    %r13
  96         push    %r14
  97         push    %r15
  98 ___
  99 $code.=<<___ if ($win64);
 100         lea     -0x28(%rsp),%rsp
 101         movaps  %xmm6,(%rsp)
 102         movaps  %xmm7,0x10(%rsp)
 103 .Lmul_alloca:
 104 ___
 105 $code.=<<___;
 106         mov     %rsp,%rax
 107         lea     2($num),%r11
 108         neg     %r11
 109         lea     (%rsp,%r11,8),%rsp      # tp=alloca(8*(num+2))
 110         and     \$-1024,%rsp            # minimize TLB usage
 111
 112         mov     %rax,8(%rsp,$num,8)     # tp[num+1]=%rsp
 113 .Lmul_body:
 114         mov     $bp,%r12                # reassign $bp
 115 ___
 116                 $bp="%r12";
 117                 $STRIDE=2**5*8;         # 5 is "window size"
 118                 $N=$STRIDE/4;           # should match cache line size
 119 $code.=<<___;
 120         mov     %r10,%r11
 121         shr     \$`log($N/8)/log(2)`,%r10
 122         and     \$`$N/8-1`,%r11
 123         not     %r10
 124         lea     .Lmagic_masks(%rip),%rax
 125         and     \$`2**5/($N/8)-1`,%r10  # 5 is "window size"
 126         lea     96($bp,%r11,8),$bp      # pointer within 1st cache line
 127         movq    0(%rax,%r10,8),%xmm4    # set of masks denoting which
 128         movq    8(%rax,%r10,8),%xmm5    # cache line contains element
 129         movq    16(%rax,%r10,8),%xmm6   # denoted by 7th argument
 130         movq    24(%rax,%r10,8),%xmm7
 131
 132         movq    `0*$STRIDE/4-96`($bp),%xmm0
 133         movq    `1*$STRIDE/4-96`($bp),%xmm1
 134         pand    %xmm4,%xmm0
 135         movq    `2*$STRIDE/4-96`($bp),%xmm2
 136         pand    %xmm5,%xmm1
 137         movq    `3*$STRIDE/4-96`($bp),%xmm3
 138         pand    %xmm6,%xmm2
 139         por     %xmm1,%xmm0
 140         pand    %xmm7,%xmm3
 141         por     %xmm2,%xmm0
 142         lea     $STRIDE($bp),$bp
 143         por     %xmm3,%xmm0
 144
 145         movq    %xmm0,$m0               # m0=bp[0]
 146
 147         mov     ($n0),$n0               # pull n0[0] value
 148         mov     ($ap),%rax
 149
 150         xor     $i,$i                   # i=0
 151         xor     $j,$j                   # j=0
 152
 153         movq    `0*$STRIDE/4-96`($bp),%xmm0
 154         movq    `1*$STRIDE/4-96`($bp),%xmm1
 155         pand    %xmm4,%xmm0
 156         movq    `2*$STRIDE/4-96`($bp),%xmm2
 157         pand    %xmm5,%xmm1
 158
 159         mov     $n0,$m1
 160         mulq    $m0                     # ap[0]*bp[0]
 161         mov     %rax,$lo0
 162         mov     ($np),%rax
 163
 164         movq    `3*$STRIDE/4-96`($bp),%xmm3
 165         pand    %xmm6,%xmm2
 166         por     %xmm1,%xmm0
 167         pand    %xmm7,%xmm3
 168
 169         imulq   $lo0,$m1                # "tp[0]"*n0
 170         mov     %rdx,$hi0
 171
 172         por     %xmm2,%xmm0
 173         lea     $STRIDE($bp),$bp
 174         por     %xmm3,%xmm0
 175
 176         mulq    $m1                     # np[0]*m1
 177         add     %rax,$lo0               # discarded
 178         mov     8($ap),%rax
 179         adc     \$0,%rdx
 180         mov     %rdx,$hi1
 181
 182         lea     1($j),$j                # j++
 183         jmp     .L1st_enter
 184
 185 .align  16
 186 .L1st:
 187         add     %rax,$hi1
 188         mov     ($ap,$j,8),%rax
 189         adc     \$0,%rdx
 190         add     $hi0,$hi1               # np[j]*m1+ap[j]*bp[0]
 191         mov     $lo0,$hi0
 192         adc     \$0,%rdx
 193         mov     $hi1,-16(%rsp,$j,8)     # tp[j-1]
 194         mov     %rdx,$hi1
 195
 196 .L1st_enter:
 197         mulq    $m0                     # ap[j]*bp[0]
 198         add     %rax,$hi0
 199         mov     ($np,$j,8),%rax
 200         adc     \$0,%rdx
 201         lea     1($j),$j                # j++
 202         mov     %rdx,$lo0
 203
 204         mulq    $m1                     # np[j]*m1
 205         cmp     $num,$j
 206         jne     .L1st
 207
 208         movq    %xmm0,$m0               # bp[1]
 209
 210         add     %rax,$hi1
 211         mov     ($ap),%rax              # ap[0]
 212         adc     \$0,%rdx
 213         add     $hi0,$hi1               # np[j]*m1+ap[j]*bp[0]
 214         adc     \$0,%rdx
 215         mov     $hi1,-16(%rsp,$j,8)     # tp[j-1]
 216         mov     %rdx,$hi1
 217         mov     $lo0,$hi0
 218
 219         xor     %rdx,%rdx
 220         add     $hi0,$hi1
 221         adc     \$0,%rdx
 222         mov     $hi1,-8(%rsp,$num,8)
 223         mov     %rdx,(%rsp,$num,8)      # store upmost overflow bit
 224
 225         lea     1($i),$i                # i++
 226         jmp     .Louter
 227 .align  16
 228 .Louter:
 229         xor     $j,$j                   # j=0
 230         mov     $n0,$m1
 231         mov     (%rsp),$lo0
 232
 233         movq    `0*$STRIDE/4-96`($bp),%xmm0
 234         movq    `1*$STRIDE/4-96`($bp),%xmm1
 235         pand    %xmm4,%xmm0
 236         movq    `2*$STRIDE/4-96`($bp),%xmm2
 237         pand    %xmm5,%xmm1
 238
 239         mulq    $m0                     # ap[0]*bp[i]
 240         add     %rax,$lo0               # ap[0]*bp[i]+tp[0]
 241         mov     ($np),%rax
 242         adc     \$0,%rdx
 243
 244         movq    `3*$STRIDE/4-96`($bp),%xmm3
 245         pand    %xmm6,%xmm2
 246         por     %xmm1,%xmm0
 247         pand    %xmm7,%xmm3
 248
 249         imulq   $lo0,$m1                # tp[0]*n0
 250         mov     %rdx,$hi0
 251
 252         por     %xmm2,%xmm0
 253         lea     $STRIDE($bp),$bp
 254         por     %xmm3,%xmm0
 255
 256         mulq    $m1                     # np[0]*m1
 257         add     %rax,$lo0               # discarded
 258         mov     8($ap),%rax
 259         adc     \$0,%rdx
 260         mov     8(%rsp),$lo0            # tp[1]
 261         mov     %rdx,$hi1
 262
 263         lea     1($j),$j                # j++
 264         jmp     .Linner_enter
 265
 266 .align  16
 267 .Linner:
 268         add     %rax,$hi1
 269         mov     ($ap,$j,8),%rax
 270         adc     \$0,%rdx
 271         add     $lo0,$hi1               # np[j]*m1+ap[j]*bp[i]+tp[j]
 272         mov     (%rsp,$j,8),$lo0
 273         adc     \$0,%rdx
 274         mov     $hi1,-16(%rsp,$j,8)     # tp[j-1]
 275         mov     %rdx,$hi1
 276
 277 .Linner_enter:
 278         mulq    $m0                     # ap[j]*bp[i]
 279         add     %rax,$hi0
 280         mov     ($np,$j,8),%rax
 281         adc     \$0,%rdx
 282         add     $hi0,$lo0               # ap[j]*bp[i]+tp[j]
 283         mov     %rdx,$hi0
 284         adc     \$0,$hi0
 285         lea     1($j),$j                # j++
 286
 287         mulq    $m1                     # np[j]*m1
 288         cmp     $num,$j
 289         jne     .Linner
 290
 291         movq    %xmm0,$m0               # bp[i+1]
 292
 293         add     %rax,$hi1
 294         mov     ($ap),%rax              # ap[0]
 295         adc     \$0,%rdx
 296         add     $lo0,$hi1               # np[j]*m1+ap[j]*bp[i]+tp[j]
 297         mov     (%rsp,$j,8),$lo0
 298         adc     \$0,%rdx
 299         mov     $hi1,-16(%rsp,$j,8)     # tp[j-1]
 300         mov     %rdx,$hi1
 301
 302         xor     %rdx,%rdx
 303         add     $hi0,$hi1
 304         adc     \$0,%rdx
 305         add     $lo0,$hi1               # pull upmost overflow bit
 306         adc     \$0,%rdx
 307         mov     $hi1,-8(%rsp,$num,8)
 308         mov     %rdx,(%rsp,$num,8)      # store upmost overflow bit
 309
 310         lea     1($i),$i                # i++
 311         cmp     $num,$i
 312         jl      .Louter
 313
 314         xor     $i,$i                   # i=0 and clear CF!
 315         mov     (%rsp),%rax             # tp[0]
 316         lea     (%rsp),$ap              # borrow ap for tp
 317         mov     $num,$j                 # j=num
 318         jmp     .Lsub
 319 .align  16
 320 .Lsub:  sbb     ($np,$i,8),%rax
 321         mov     %rax,($rp,$i,8)         # rp[i]=tp[i]-np[i]
 322         mov     8($ap,$i,8),%rax        # tp[i+1]
 323         lea     1($i),$i                # i++
 324         dec     $j                      # doesnn't affect CF!
 325         jnz     .Lsub
 326
 327         sbb     \$0,%rax                # handle upmost overflow bit
 328         xor     $i,$i
 329         and     %rax,$ap
 330         not     %rax
 331         mov     $rp,$np
 332         and     %rax,$np
 333         mov     $num,$j                 # j=num
 334         or      $np,$ap                 # ap=borrow?tp:rp
 335 .align  16
 336 .Lcopy:                                 # copy or in-place refresh
 337         mov     ($ap,$i,8),%rax
 338         mov     $i,(%rsp,$i,8)          # zap temporary vector
 339         mov     %rax,($rp,$i,8)         # rp[i]=tp[i]
 340         lea     1($i),$i
 341         sub     \$1,$j
 342         jnz     .Lcopy
 343
 344         mov     8(%rsp,$num,8),%rsi     # restore %rsp
 345         mov     \$1,%rax
 346 ___
 347 $code.=<<___ if ($win64);
 348         movaps  (%rsi),%xmm6
 349         movaps  0x10(%rsi),%xmm7
 350         lea     0x28(%rsi),%rsi
 351 ___
 352 $code.=<<___;
 353         mov     (%rsi),%r15
 354         mov     8(%rsi),%r14
 355         mov     16(%rsi),%r13
 356         mov     24(%rsi),%r12
 357         mov     32(%rsi),%rbp
 358         mov     40(%rsi),%rbx
 359         lea     48(%rsi),%rsp
 360 .Lmul_epilogue:
 361         ret
 362 .size   bn_mul_mont_gather5,.-bn_mul_mont_gather5
 363 ___
 364 {{{
 365 my @A=("%r10","%r11");
 366 my @N=("%r13","%rdi");
 367 $code.=<<___;
 368 .type   bn_mul4x_mont_gather5,\@function,6
 369 .align  16
 370 bn_mul4x_mont_gather5:
 371 .Lmul4x_enter:
 372 ___
 373 $code.=<<___ if ($addx);
 374         and     \$0x80100,%r11d
 375         cmp     \$0x80100,%r11d
 376         je      .Lmulx4x_enter
 377 ___
 378 $code.=<<___;
 379         mov     ${num}d,${num}d
 380         mov     `($win64?56:8)`(%rsp),%r10d     # load 7th argument
 381         push    %rbx
 382         push    %rbp
 383         push    %r12
 384         push    %r13
 385         push    %r14
 386         push    %r15
 387 ___
 388 $code.=<<___ if ($win64);
 389         lea     -0x28(%rsp),%rsp
 390         movaps  %xmm6,(%rsp)
 391         movaps  %xmm7,0x10(%rsp)
 392 .Lmul4x_alloca:
 393 ___
 394 $code.=<<___;
 395         mov     %rsp,%rax
 396         lea     4($num),%r11
 397         neg     %r11
 398         lea     (%rsp,%r11,8),%rsp      # tp=alloca(8*(num+4))
 399         and     \$-1024,%rsp            # minimize TLB usage
 400
 401         mov     %rax,8(%rsp,$num,8)     # tp[num+1]=%rsp
 402 .Lmul4x_body:
 403         mov     $rp,16(%rsp,$num,8)     # tp[num+2]=$rp
 404         mov     %rdx,%r12               # reassign $bp
 405 ___
 406                 $bp="%r12";
 407                 $STRIDE=2**5*8;         # 5 is "window size"
 408                 $N=$STRIDE/4;           # should match cache line size
 409 $code.=<<___;
 410         mov     %r10,%r11
 411         shr     \$`log($N/8)/log(2)`,%r10
 412         and     \$`$N/8-1`,%r11
 413         not     %r10
 414         lea     .Lmagic_masks(%rip),%rax
 415         and     \$`2**5/($N/8)-1`,%r10  # 5 is "window size"
 416         lea     96($bp,%r11,8),$bp      # pointer within 1st cache line
 417         movq    0(%rax,%r10,8),%xmm4    # set of masks denoting which
 418         movq    8(%rax,%r10,8),%xmm5    # cache line contains element
 419         movq    16(%rax,%r10,8),%xmm6   # denoted by 7th argument
 420         movq    24(%rax,%r10,8),%xmm7
 421
 422         movq    `0*$STRIDE/4-96`($bp),%xmm0
 423         movq    `1*$STRIDE/4-96`($bp),%xmm1
 424         pand    %xmm4,%xmm0
 425         movq    `2*$STRIDE/4-96`($bp),%xmm2
 426         pand    %xmm5,%xmm1
 427         movq    `3*$STRIDE/4-96`($bp),%xmm3
 428         pand    %xmm6,%xmm2
 429         por     %xmm1,%xmm0
 430         pand    %xmm7,%xmm3
 431         por     %xmm2,%xmm0
 432         lea     $STRIDE($bp),$bp
 433         por     %xmm3,%xmm0
 434
 435         movq    %xmm0,$m0               # m0=bp[0]
 436         mov     ($n0),$n0               # pull n0[0] value
 437         mov     ($ap),%rax
 438
 439         xor     $i,$i                   # i=0
 440         xor     $j,$j                   # j=0
 441
 442         movq    `0*$STRIDE/4-96`($bp),%xmm0
 443         movq    `1*$STRIDE/4-96`($bp),%xmm1
 444         pand    %xmm4,%xmm0
 445         movq    `2*$STRIDE/4-96`($bp),%xmm2
 446         pand    %xmm5,%xmm1
 447
 448         mov     $n0,$m1
 449         mulq    $m0                     # ap[0]*bp[0]
 450         mov     %rax,$A[0]
 451         mov     ($np),%rax
 452
 453         movq    `3*$STRIDE/4-96`($bp),%xmm3
 454         pand    %xmm6,%xmm2
 455         por     %xmm1,%xmm0
 456         pand    %xmm7,%xmm3
 457
 458         imulq   $A[0],$m1               # "tp[0]"*n0
 459         mov     %rdx,$A[1]
 460
 461         por     %xmm2,%xmm0
 462         lea     $STRIDE($bp),$bp
 463         por     %xmm3,%xmm0
 464
 465         mulq    $m1                     # np[0]*m1
 466         add     %rax,$A[0]              # discarded
 467         mov     8($ap),%rax
 468         adc     \$0,%rdx
 469         mov     %rdx,$N[1]
 470
 471         mulq    $m0
 472         add     %rax,$A[1]
 473         mov     8($np),%rax
 474         adc     \$0,%rdx
 475         mov     %rdx,$A[0]
 476
 477         mulq    $m1
 478         add     %rax,$N[1]
 479         mov     16($ap),%rax
 480         adc     \$0,%rdx
 481         add     $A[1],$N[1]
 482         lea     4($j),$j                # j++
 483         adc     \$0,%rdx
 484         mov     $N[1],(%rsp)
 485         mov     %rdx,$N[0]
 486         jmp     .L1st4x
 487 .align  16
 488 .L1st4x:
 489         mulq    $m0                     # ap[j]*bp[0]
 490         add     %rax,$A[0]
 491         mov     -16($np,$j,8),%rax
 492         adc     \$0,%rdx
 493         mov     %rdx,$A[1]
 494
 495         mulq    $m1                     # np[j]*m1
 496         add     %rax,$N[0]
 497         mov     -8($ap,$j,8),%rax
 498         adc     \$0,%rdx
 499         add     $A[0],$N[0]             # np[j]*m1+ap[j]*bp[0]
 500         adc     \$0,%rdx
 501         mov     $N[0],-24(%rsp,$j,8)    # tp[j-1]
 502         mov     %rdx,$N[1]
 503
 504         mulq    $m0                     # ap[j]*bp[0]
 505         add     %rax,$A[1]
 506         mov     -8($np,$j,8),%rax
 507         adc     \$0,%rdx
 508         mov     %rdx,$A[0]
 509
 510         mulq    $m1                     # np[j]*m1
 511         add     %rax,$N[1]
 512         mov     ($ap,$j,8),%rax
 513         adc     \$0,%rdx
 514         add     $A[1],$N[1]             # np[j]*m1+ap[j]*bp[0]
 515         adc     \$0,%rdx
 516         mov     $N[1],-16(%rsp,$j,8)    # tp[j-1]
 517         mov     %rdx,$N[0]
 518
 519         mulq    $m0                     # ap[j]*bp[0]
 520         add     %rax,$A[0]
 521         mov     ($np,$j,8),%rax
 522         adc     \$0,%rdx
 523         mov     %rdx,$A[1]
 524
 525         mulq    $m1                     # np[j]*m1
 526         add     %rax,$N[0]
 527         mov     8($ap,$j,8),%rax
 528         adc     \$0,%rdx
 529         add     $A[0],$N[0]             # np[j]*m1+ap[j]*bp[0]
 530         adc     \$0,%rdx
 531         mov     $N[0],-8(%rsp,$j,8)     # tp[j-1]
 532         mov     %rdx,$N[1]
 533
 534         mulq    $m0                     # ap[j]*bp[0]
 535         add     %rax,$A[1]
 536         mov     8($np,$j,8),%rax
 537         adc     \$0,%rdx
 538         lea     4($j),$j                # j++
 539         mov     %rdx,$A[0]
 540
 541         mulq    $m1                     # np[j]*m1
 542         add     %rax,$N[1]
 543         mov     -16($ap,$j,8),%rax
 544         adc     \$0,%rdx
 545         add     $A[1],$N[1]             # np[j]*m1+ap[j]*bp[0]
 546         adc     \$0,%rdx
 547         mov     $N[1],-32(%rsp,$j,8)    # tp[j-1]
 548         mov     %rdx,$N[0]
 549         cmp     $num,$j
 550         jl      .L1st4x
 551
 552         mulq    $m0                     # ap[j]*bp[0]
 553         add     %rax,$A[0]
 554         mov     -16($np,$j,8),%rax
 555         adc     \$0,%rdx
 556         mov     %rdx,$A[1]
 557
 558         mulq    $m1                     # np[j]*m1
 559         add     %rax,$N[0]
 560         mov     -8($ap,$j,8),%rax
 561         adc     \$0,%rdx
 562         add     $A[0],$N[0]             # np[j]*m1+ap[j]*bp[0]
 563         adc     \$0,%rdx
 564         mov     $N[0],-24(%rsp,$j,8)    # tp[j-1]
 565         mov     %rdx,$N[1]
 566
 567         mulq    $m0                     # ap[j]*bp[0]
 568         add     %rax,$A[1]
 569         mov     -8($np,$j,8),%rax
 570         adc     \$0,%rdx
 571         mov     %rdx,$A[0]
 572
 573         mulq    $m1                     # np[j]*m1
 574         add     %rax,$N[1]
 575         mov     ($ap),%rax              # ap[0]
 576         adc     \$0,%rdx
 577         add     $A[1],$N[1]             # np[j]*m1+ap[j]*bp[0]
 578         adc     \$0,%rdx
 579         mov     $N[1],-16(%rsp,$j,8)    # tp[j-1]
 580         mov     %rdx,$N[0]
 581
 582         movq    %xmm0,$m0               # bp[1]
 583
 584         xor     $N[1],$N[1]
 585         add     $A[0],$N[0]
 586         adc     \$0,$N[1]
 587         mov     $N[0],-8(%rsp,$j,8)
 588         mov     $N[1],(%rsp,$j,8)       # store upmost overflow bit
 589
 590         lea     1($i),$i                # i++
 591 .align  4
 592 .Louter4x:
 593         xor     $j,$j                   # j=0
 594         movq    `0*$STRIDE/4-96`($bp),%xmm0
 595         movq    `1*$STRIDE/4-96`($bp),%xmm1
 596         pand    %xmm4,%xmm0
 597         movq    `2*$STRIDE/4-96`($bp),%xmm2
 598         pand    %xmm5,%xmm1
 599
 600         mov     (%rsp),$A[0]
 601         mov     $n0,$m1
 602         mulq    $m0                     # ap[0]*bp[i]
 603         add     %rax,$A[0]              # ap[0]*bp[i]+tp[0]
 604         mov     ($np),%rax
 605         adc     \$0,%rdx
 606
 607         movq    `3*$STRIDE/4-96`($bp),%xmm3
 608         pand    %xmm6,%xmm2
 609         por     %xmm1,%xmm0
 610         pand    %xmm7,%xmm3
 611
 612         imulq   $A[0],$m1               # tp[0]*n0
 613         mov     %rdx,$A[1]
 614
 615         por     %xmm2,%xmm0
 616         lea     $STRIDE($bp),$bp
 617         por     %xmm3,%xmm0
 618
 619         mulq    $m1                     # np[0]*m1
 620         add     %rax,$A[0]              # "$N[0]", discarded
 621         mov     8($ap),%rax
 622         adc     \$0,%rdx
 623         mov     %rdx,$N[1]
 624
 625         mulq    $m0                     # ap[j]*bp[i]
 626         add     %rax,$A[1]
 627         mov     8($np),%rax
 628         adc     \$0,%rdx
 629         add     8(%rsp),$A[1]           # +tp[1]
 630         adc     \$0,%rdx
 631         mov     %rdx,$A[0]
 632
 633         mulq    $m1                     # np[j]*m1
 634         add     %rax,$N[1]
 635         mov     16($ap),%rax
 636         adc     \$0,%rdx
 637         add     $A[1],$N[1]             # np[j]*m1+ap[j]*bp[i]+tp[j]
 638         lea     4($j),$j                # j+=2
 639         adc     \$0,%rdx
 640         mov     %rdx,$N[0]
 641         jmp     .Linner4x
 642 .align  16
 643 .Linner4x:
 644         mulq    $m0                     # ap[j]*bp[i]
 645         add     %rax,$A[0]
 646         mov     -16($np,$j,8),%rax
 647         adc     \$0,%rdx
 648         add     -16(%rsp,$j,8),$A[0]    # ap[j]*bp[i]+tp[j]
 649         adc     \$0,%rdx
 650         mov     %rdx,$A[1]
 651
 652         mulq    $m1                     # np[j]*m1
 653         add     %rax,$N[0]
 654         mov     -8($ap,$j,8),%rax
 655         adc     \$0,%rdx
 656         add     $A[0],$N[0]
 657         adc     \$0,%rdx
 658         mov     $N[1],-32(%rsp,$j,8)    # tp[j-1]
 659         mov     %rdx,$N[1]
 660
 661         mulq    $m0                     # ap[j]*bp[i]
 662         add     %rax,$A[1]
 663         mov     -8($np,$j,8),%rax
 664         adc     \$0,%rdx
 665         add     -8(%rsp,$j,8),$A[1]
 666         adc     \$0,%rdx
 667         mov     %rdx,$A[0]
 668
 669         mulq    $m1                     # np[j]*m1
 670         add     %rax,$N[1]
 671         mov     ($ap,$j,8),%rax
 672         adc     \$0,%rdx
 673         add     $A[1],$N[1]
 674         adc     \$0,%rdx
 675         mov     $N[0],-24(%rsp,$j,8)    # tp[j-1]
 676         mov     %rdx,$N[0]
 677
 678         mulq    $m0                     # ap[j]*bp[i]
 679         add     %rax,$A[0]
 680         mov     ($np,$j,8),%rax
 681         adc     \$0,%rdx
 682         add     (%rsp,$j,8),$A[0]       # ap[j]*bp[i]+tp[j]
 683         adc     \$0,%rdx
 684         mov     %rdx,$A[1]
 685
 686         mulq    $m1                     # np[j]*m1
 687         add     %rax,$N[0]
 688         mov     8($ap,$j,8),%rax
 689         adc     \$0,%rdx
 690         add     $A[0],$N[0]
 691         adc     \$0,%rdx
 692         mov     $N[1],-16(%rsp,$j,8)    # tp[j-1]
 693         mov     %rdx,$N[1]
 694
 695         mulq    $m0                     # ap[j]*bp[i]
 696         add     %rax,$A[1]
 697         mov     8($np,$j,8),%rax
 698         adc     \$0,%rdx
 699         add     8(%rsp,$j,8),$A[1]
 700         adc     \$0,%rdx
 701         lea     4($j),$j                # j++
 702         mov     %rdx,$A[0]
 703
 704         mulq    $m1                     # np[j]*m1
 705         add     %rax,$N[1]
 706         mov     -16($ap,$j,8),%rax
 707         adc     \$0,%rdx
 708         add     $A[1],$N[1]
 709         adc     \$0,%rdx
 710         mov     $N[0],-40(%rsp,$j,8)    # tp[j-1]
 711         mov     %rdx,$N[0]
 712         cmp     $num,$j
 713         jl      .Linner4x
 714
 715         mulq    $m0                     # ap[j]*bp[i]
 716         add     %rax,$A[0]
 717         mov     -16($np,$j,8),%rax
 718         adc     \$0,%rdx
 719         add     -16(%rsp,$j,8),$A[0]    # ap[j]*bp[i]+tp[j]
 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,8),%rax
 726         adc     \$0,%rdx
 727         add     $A[0],$N[0]
 728         adc     \$0,%rdx
 729         mov     $N[1],-32(%rsp,$j,8)    # tp[j-1]
 730         mov     %rdx,$N[1]
 731
 732         mulq    $m0                     # ap[j]*bp[i]
 733         add     %rax,$A[1]
 734         mov     -8($np,$j,8),%rax
 735         adc     \$0,%rdx
 736         add     -8(%rsp,$j,8),$A[1]
 737         adc     \$0,%rdx
 738         lea     1($i),$i                # i++
 739         mov     %rdx,$A[0]
 740
 741         mulq    $m1                     # np[j]*m1
 742         add     %rax,$N[1]
 743         mov     ($ap),%rax              # ap[0]
 744         adc     \$0,%rdx
 745         add     $A[1],$N[1]
 746         adc     \$0,%rdx
 747         mov     $N[0],-24(%rsp,$j,8)    # tp[j-1]
 748         mov     %rdx,$N[0]
 749
 750         movq    %xmm0,$m0               # bp[i+1]
 751         mov     $N[1],-16(%rsp,$j,8)    # tp[j-1]
 752
 753         xor     $N[1],$N[1]
 754         add     $A[0],$N[0]
 755         adc     \$0,$N[1]
 756         add     (%rsp,$num,8),$N[0]     # pull upmost overflow bit
 757         adc     \$0,$N[1]
 758         mov     $N[0],-8(%rsp,$j,8)
 759         mov     $N[1],(%rsp,$j,8)       # store upmost overflow bit
 760
 761         cmp     $num,$i
 762         jl      .Louter4x
 763 ___
 764 {
 765 my @ri=("%rax","%rdx",$m0,$m1);
 766 $code.=<<___;
 767         mov     16(%rsp,$num,8),$rp     # restore $rp
 768         mov     0(%rsp),@ri[0]          # tp[0]
 769         pxor    %xmm0,%xmm0
 770         mov     8(%rsp),@ri[1]          # tp[1]
 771         shr     \$2,$num                # num/=4
 772         lea     (%rsp),$ap              # borrow ap for tp
 773         xor     $i,$i                   # i=0 and clear CF!
 774
 775         sub     0($np),@ri[0]
 776         mov     16($ap),@ri[2]          # tp[2]
 777         mov     24($ap),@ri[3]          # tp[3]
 778         sbb     8($np),@ri[1]
 779         lea     -1($num),$j             # j=num/4-1
 780         jmp     .Lsub4x
 781 .align  16
 782 .Lsub4x:
 783         mov     @ri[0],0($rp,$i,8)      # rp[i]=tp[i]-np[i]
 784         mov     @ri[1],8($rp,$i,8)      # rp[i]=tp[i]-np[i]
 785         sbb     16($np,$i,8),@ri[2]
 786         mov     32($ap,$i,8),@ri[0]     # tp[i+1]
 787         mov     40($ap,$i,8),@ri[1]
 788         sbb     24($np,$i,8),@ri[3]
 789         mov     @ri[2],16($rp,$i,8)     # rp[i]=tp[i]-np[i]
 790         mov     @ri[3],24($rp,$i,8)     # rp[i]=tp[i]-np[i]
 791         sbb     32($np,$i,8),@ri[0]
 792         mov     48($ap,$i,8),@ri[2]
 793         mov     56($ap,$i,8),@ri[3]
 794         sbb     40($np,$i,8),@ri[1]
 795         lea     4($i),$i                # i++
 796         dec     $j                      # doesnn't affect CF!
 797         jnz     .Lsub4x
 798
 799         mov     @ri[0],0($rp,$i,8)      # rp[i]=tp[i]-np[i]
 800         mov     32($ap,$i,8),@ri[0]     # load overflow bit
 801         sbb     16($np,$i,8),@ri[2]
 802         mov     @ri[1],8($rp,$i,8)      # rp[i]=tp[i]-np[i]
 803         sbb     24($np,$i,8),@ri[3]
 804         mov     @ri[2],16($rp,$i,8)     # rp[i]=tp[i]-np[i]
 805
 806         sbb     \$0,@ri[0]              # handle upmost overflow bit
 807         mov     @ri[3],24($rp,$i,8)     # rp[i]=tp[i]-np[i]
 808         xor     $i,$i                   # i=0
 809         and     @ri[0],$ap
 810         not     @ri[0]
 811         mov     $rp,$np
 812         and     @ri[0],$np
 813         lea     -1($num),$j
 814         or      $np,$ap                 # ap=borrow?tp:rp
 815
 816         movdqu  ($ap),%xmm1
 817         movdqa  %xmm0,(%rsp)
 818         movdqu  %xmm1,($rp)
 819         jmp     .Lcopy4x
 820 .align  16
 821 .Lcopy4x:                                       # copy or in-place refresh
 822         movdqu  16($ap,$i),%xmm2
 823         movdqu  32($ap,$i),%xmm1
 824         movdqa  %xmm0,16(%rsp,$i)
 825         movdqu  %xmm2,16($rp,$i)
 826         movdqa  %xmm0,32(%rsp,$i)
 827         movdqu  %xmm1,32($rp,$i)
 828         lea     32($i),$i
 829         dec     $j
 830         jnz     .Lcopy4x
 831
 832         shl     \$2,$num
 833         movdqu  16($ap,$i),%xmm2
 834         movdqa  %xmm0,16(%rsp,$i)
 835         movdqu  %xmm2,16($rp,$i)
 836 ___
 837 }
 838 $code.=<<___;
 839         mov     8(%rsp,$num,8),%rsi     # restore %rsp
 840         mov     \$1,%rax
 841 ___
 842 $code.=<<___ if ($win64);
 843         movaps  (%rsi),%xmm6
 844         movaps  0x10(%rsi),%xmm7
 845         lea     0x28(%rsi),%rsi
 846 ___
 847 $code.=<<___;
 848         mov     (%rsi),%r15
 849         mov     8(%rsi),%r14
 850         mov     16(%rsi),%r13
 851         mov     24(%rsi),%r12
 852         mov     32(%rsi),%rbp
 853         mov     40(%rsi),%rbx
 854         lea     48(%rsi),%rsp
 855 .Lmul4x_epilogue:
 856         ret
 857 .size   bn_mul4x_mont_gather5,.-bn_mul4x_mont_gather5
 858 ___
 859 }}}
 860 if ($addx) {{{
 861 my $bp="%rdx";  # original value
 862
 863 $code.=<<___;
 864 .type   bn_mulx4x_mont_gather5,\@function,6
 865 .align  32
 866 bn_mulx4x_mont_gather5:
 867 .Lmulx4x_enter:
 868         mov     %rsp,%rax
 869         push    %rbx
 870         push    %rbp
 871         push    %r12
 872         push    %r13
 873         push    %r14
 874         push    %r15
 875 ___
 876 $code.=<<___ if ($win64);
 877         lea     -0x28(%rsp),%rsp
 878         movaps  %xmm6,(%rsp)
 879         movaps  %xmm7,0x10(%rsp)
 880 ___
 881 $code.=<<___;
 882         shl     \$3,${num}d             # convert $num to bytes
 883         xor     %r10,%r10
 884         mov     %rsp,%r11               # put aside %rsp
 885         sub     $num,%r10               # -$num
 886         mov     ($n0),$n0               # *n0
 887         lea     -72(%rsp,%r10),%rsp     # alloca(frame+$num+8)
 888         and     \$-128,%rsp
 889         ##############################################################
 890         # Stack layout
 891         # +0    num
 892         # +8    off-loaded &b[i]
 893         # +16   end of b[num]
 894         # +24   saved n0
 895         # +32   saved rp
 896         # +40
 897         # +48   inner counter
 898         # +56   saved %rsp
 899         # +64   tmp[num+1]
 900         #
 901         mov     $num,0(%rsp)            # save $num
 902         shl     \$5,$num
 903         lea     256($bp,$num),%r10
 904         shr     \$5+5,$num
 905         mov     %r10,16(%rsp)           # end of b[num]
 906         sub     \$1,$num
 907         mov     $n0, 24(%rsp)           # save *n0
 908         mov     $rp, 32(%rsp)           # save $rp
 909         mov     $num,48(%rsp)           # inner counter
 910         mov     %r11,56(%rsp)           # save original %rsp
 911         jmp     .Lmulx4x_body
 912
 913 .align  32
 914 .Lmulx4x_body:
 915 ___
 916 my ($aptr, $bptr, $nptr, $tptr, $mi,  $bi,  $zero, $num)=
 917    ("%rsi","%rdi","%rcx","%rbx","%r8","%r9","%rbp","%rax");
 918 my $rptr=$bptr;
 919 my $STRIDE=2**5*8;              # 5 is "window size"
 920 my $N=$STRIDE/4;                # should match cache line size
 921 $code.=<<___;
 922         mov     `($win64?56:8)`(%rax),%r10d     # load 7th argument
 923         mov     %r10,%r11
 924         shr     \$`log($N/8)/log(2)`,%r10
 925         and     \$`$N/8-1`,%r11
 926         not     %r10
 927         lea     .Lmagic_masks(%rip),%rax
 928         and     \$`2**5/($N/8)-1`,%r10  # 5 is "window size"
 929         lea     96($bp,%r11,8),$bptr    # pointer within 1st cache line
 930         movq    0(%rax,%r10,8),%xmm4    # set of masks denoting which
 931         movq    8(%rax,%r10,8),%xmm5    # cache line contains element
 932         movq    16(%rax,%r10,8),%xmm6   # denoted by 7th argument
 933         movq    24(%rax,%r10,8),%xmm7
 934
 935         movq    `0*$STRIDE/4-96`($bptr),%xmm0
 936         movq    `1*$STRIDE/4-96`($bptr),%xmm1
 937         pand    %xmm4,%xmm0
 938         movq    `2*$STRIDE/4-96`($bptr),%xmm2
 939         pand    %xmm5,%xmm1
 940         movq    `3*$STRIDE/4-96`($bptr),%xmm3
 941         pand    %xmm6,%xmm2
 942         por     %xmm1,%xmm0
 943         pand    %xmm7,%xmm3
 944         por     %xmm2,%xmm0
 945         lea     $STRIDE($bptr),$bptr
 946         por     %xmm3,%xmm0
 947
 948         movq    %xmm0,%rdx              # bp[0]
 949         movq    `0*$STRIDE/4-96`($bptr),%xmm0
 950         movq    `1*$STRIDE/4-96`($bptr),%xmm1
 951         pand    %xmm4,%xmm0
 952         movq    `2*$STRIDE/4-96`($bptr),%xmm2
 953         pand    %xmm5,%xmm1
 954
 955         lea     64+32(%rsp),$tptr
 956         mov     %rdx,$bi
 957         xor     $zero,$zero             # of=0,cf=0
 958
 959         mulx    0*8($aptr),$mi,%rax     # a[0]*b[0]
 960         mulx    1*8($aptr),%r11,%r14    # a[1]*b[0]
 961         adcx    %rax,%r11
 962         mulx    2*8($aptr),%r12,%r13    # ...
 963         adcx    %r14,%r12
 964         adcx    $zero,%r13
 965
 966         movq    `3*$STRIDE/4-96`($bptr),%xmm3
 967         lea     $STRIDE($bptr),%r10     # next &b[i]
 968         pand    %xmm6,%xmm2
 969         por     %xmm1,%xmm0
 970         pand    %xmm7,%xmm3
 971
 972         mov     $mi,$bptr               # borrow $bptr
 973         imulq   24(%rsp),$mi            # "t[0]"*n0
 974         xor     $zero,$zero             # cf=0, of=0
 975
 976         por     %xmm2,%xmm0
 977         por     %xmm3,%xmm0
 978         mov     %r10,8(%rsp)            # off-load &b[i]
 979
 980         mulx    3*8($aptr),%rax,%r14
 981          mov    $mi,%rdx
 982         lea     4*8($aptr),$aptr
 983         adcx    %rax,%r13
 984         adcx    $zero,%r14              # cf=0
 985
 986         mulx    0*8($nptr),%rax,%r10
 987         adcx    %rax,$bptr              # discarded
 988         adox    %r11,%r10
 989         mulx    1*8($nptr),%rax,%r11
 990         adcx    %rax,%r10
 991         adox    %r12,%r11
 992         mulx    2*8($nptr),%rax,%r12
 993         mov     48(%rsp),$bptr          # counter value
 994         mov     %r10,-4*8($tptr)
 995         adcx    %rax,%r11
 996         adox    %r13,%r12
 997         mulx    3*8($nptr),%rax,%r15
 998          mov    $bi,%rdx
 999         mov     %r11,-3*8($tptr)
1000         adcx    %rax,%r12
1001         adox    $zero,%r15              # of=0
1002         lea     4*8($nptr),$nptr
1003         mov     %r12,-2*8($tptr)
1004
1005         jmp     .Lmulx4x_1st
1006
1007 .align  32
1008 .Lmulx4x_1st:
1009         adcx    $zero,%r15              # cf=0, modulo-scheduled
1010         mulx    0*8($aptr),%r10,%rax    # a[4]*b[0]
1011         adcx    %r14,%r10
1012         mulx    1*8($aptr),%r11,%r14    # a[5]*b[0]
1013         adcx    %rax,%r11
1014         mulx    2*8($aptr),%r12,%rax    # ...
1015         adcx    %r14,%r12
1016         mulx    3*8($aptr),%r13,%r14
1017          .byte  0x66,0x66
1018          mov    $mi,%rdx
1019         adcx    %rax,%r13
1020         adcx    $zero,%r14              # cf=0
1021         lea     4*8($aptr),$aptr
1022         lea     4*8($tptr),$tptr
1023
1024         adox    %r15,%r10
1025         mulx    0*8($nptr),%rax,%r15
1026         adcx    %rax,%r10
1027         adox    %r15,%r11
1028         mulx    1*8($nptr),%rax,%r15
1029         adcx    %rax,%r11
1030         adox    %r15,%r12
1031         .byte   0x3e
1032         mulx    2*8($nptr),%rax,%r15
1033         mov     %r10,-5*8($tptr)
1034         mov     %r11,-4*8($tptr)
1035         adcx    %rax,%r12
1036         adox    %r15,%r13
1037         mulx    3*8($nptr),%rax,%r15
1038          mov    $bi,%rdx
1039         mov     %r12,-3*8($tptr)
1040         adcx    %rax,%r13
1041         adox    $zero,%r15
1042         lea     4*8($nptr),$nptr
1043         mov     %r13,-2*8($tptr)
1044
1045         dec     $bptr                   # of=0, pass cf
1046         jnz     .Lmulx4x_1st
1047
1048         mov     0(%rsp),$num            # load num
1049         mov     8(%rsp),$bptr           # re-load &b[i]
1050         movq    %xmm0,%rdx              # bp[1]
1051         adc     $zero,%r15              # modulo-scheduled
1052         add     %r15,%r14
1053         sbb     %r15,%r15               # top-most carry
1054         mov     %r14,-1*8($tptr)
1055         jmp     .Lmulx4x_outer
1056
1057 .align  32
1058 .Lmulx4x_outer:
1059         sub     $num,$aptr              # rewind $aptr
1060         mov     %r15,($tptr)            # save top-most carry
1061         mov     64(%rsp),%r10
1062         lea     64(%rsp),$tptr
1063         sub     $num,$nptr              # rewind $nptr
1064         xor     $zero,$zero             # cf=0, of=0
1065         mov     %rdx,$bi
1066
1067         movq    `0*$STRIDE/4-96`($bptr),%xmm0
1068         movq    `1*$STRIDE/4-96`($bptr),%xmm1
1069         pand    %xmm4,%xmm0
1070         movq    `2*$STRIDE/4-96`($bptr),%xmm2
1071         pand    %xmm5,%xmm1
1072
1073         mulx    0*8($aptr),$mi,%rax     # a[0]*b[i]
1074         adox    %r10,$mi
1075         mov     1*8($tptr),%r10
1076         mulx    1*8($aptr),%r11,%r14    # a[1]*b[i]
1077         adcx    %rax,%r11
1078         mulx    2*8($aptr),%r12,%r13    # ...
1079         adox    %r10,%r11
1080         adcx    %r14,%r12
1081         adox    $zero,%r12
1082         adcx    $zero,%r13
1083
1084         movq    `3*$STRIDE/4-96`($bptr),%xmm3
1085         lea     $STRIDE($bptr),%r10     # next &b[i]
1086         pand    %xmm6,%xmm2
1087         por     %xmm1,%xmm0
1088         pand    %xmm7,%xmm3
1089
1090         mov     $mi,$bptr               # borrow $bptr
1091         imulq   24(%rsp),$mi            # "t[0]"*n0
1092         xor     $zero,$zero             # cf=0, of=0
1093
1094         por     %xmm2,%xmm0
1095         por     %xmm3,%xmm0
1096         mov     %r10,8(%rsp)            # off-load &b[i]
1097         mov     2*8($tptr),%r10
1098
1099         mulx    3*8($aptr),%rax,%r14
1100          mov    $mi,%rdx
1101         adox    %r10,%r12
1102         adcx    %rax,%r13
1103         adox    3*8($tptr),%r13
1104         adcx    $zero,%r14
1105         lea     4*8($aptr),$aptr
1106         lea     4*8($tptr),$tptr
1107         adox    $zero,%r14
1108
1109         mulx    0*8($nptr),%rax,%r10
1110         adcx    %rax,$bptr              # discarded
1111         adox    %r11,%r10
1112         mulx    1*8($nptr),%rax,%r11
1113         adcx    %rax,%r10
1114         adox    %r12,%r11
1115         mulx    2*8($nptr),%rax,%r12
1116         .byte   0x3e
1117         mov     %r10,-4*8($tptr)
1118         .byte   0x3e
1119         mov     0*8($tptr),%r10
1120         adcx    %rax,%r11
1121         adox    %r13,%r12
1122         mulx    3*8($nptr),%rax,%r15
1123          mov    $bi,%rdx
1124         mov     %r11,-3*8($tptr)
1125         adcx    %rax,%r12
1126         adox    $zero,%r15              # of=0
1127         mov     48(%rsp),$bptr          # counter value
1128         mov     %r12,-2*8($tptr)
1129         lea     4*8($nptr),$nptr
1130
1131         jmp     .Lmulx4x_inner
1132
1133 .align  32
1134 .Lmulx4x_inner:
1135         adcx    $zero,%r15              # cf=0, modulo-scheduled
1136         adox    %r10,%r14
1137         mulx    0*8($aptr),%r10,%rax    # a[4]*b[i]
1138         mov     1*8($tptr),%r13
1139         adcx    %r14,%r10
1140         mulx    1*8($aptr),%r11,%r14    # a[5]*b[i]
1141         adox    %rax,%r11
1142         mulx    2*8($aptr),%r12,%rax    # ...
1143         adcx    %r13,%r11
1144         adox    %r14,%r12
1145         mulx    3*8($aptr),%r13,%r14
1146          mov    $mi,%rdx
1147         adcx    2*8($tptr),%r12
1148         adox    %rax,%r13
1149         adcx    3*8($tptr),%r13
1150         adox    $zero,%r14              # of=0
1151         lea     4*8($aptr),$aptr
1152         .byte   0x48,0x8d,0x9b,0x20,0x00,0x00,0x00      # lea   4*8($tptr),$tptr
1153         adcx    $zero,%r14              # cf=0
1154
1155         adox    %r15,%r10
1156         .byte   0x3e,0xc4,0x62,0xfb,0xf6,0x79,0x00      # mulx  0*8($nptr),%rax,%r15
1157         adcx    %rax,%r10
1158         adox    %r15,%r11
1159         mulx    1*8($nptr),%rax,%r15
1160         adcx    %rax,%r11
1161         adox    %r15,%r12
1162         mulx    2*8($nptr),%rax,%r15
1163         mov     %r10,-5*8($tptr)
1164         mov     0*8($tptr),%r10
1165         adcx    %rax,%r12
1166         adox    %r15,%r13
1167         mulx    3*8($nptr),%rax,%r15
1168          mov    $bi,%rdx
1169         mov     %r11,-4*8($tptr)
1170         mov     %r12,-3*8($tptr)
1171         adcx    %rax,%r13
1172         adox    $zero,%r15
1173         lea     4*8($nptr),$nptr
1174         mov     %r13,-2*8($tptr)
1175
1176         dec     $bptr                   # of=0, pass cf
1177         jnz     .Lmulx4x_inner
1178
1179         mov     0(%rsp),$num            # load num
1180         mov     8(%rsp),$bptr           # re-load &b[i]
1181         movq    %xmm0,%rdx              # bp[i+1]
1182         adc     $zero,%r15              # modulo-scheduled
1183         sub     %r10,$zero              # pull top-most carry
1184         adc     %r15,%r14
1185         sbb     %r15,%r15               # top-most carry
1186         mov     %r14,-1*8($tptr)
1187
1188         cmp     16(%rsp),$bptr
1189         jb      .Lmulx4x_outer
1190
1191         neg     $num
1192         mov     32(%rsp),$rptr          # restore rp
1193         lea     64(%rsp),$tptr
1194
1195         xor     %rdx,%rdx
1196         pxor    %xmm0,%xmm0
1197         mov     0*8($nptr,$num),%r8
1198         mov     1*8($nptr,$num),%r9
1199         neg     %r8
1200         jmp     .Lmulx4x_sub_entry
1201
1202 .align  32
1203 .Lmulx4x_sub:
1204         mov     0*8($nptr,$num),%r8
1205         mov     1*8($nptr,$num),%r9
1206         not     %r8
1207 .Lmulx4x_sub_entry:
1208         mov     2*8($nptr,$num),%r10
1209         not     %r9
1210         and     %r15,%r8
1211         mov     3*8($nptr,$num),%r11
1212         not     %r10
1213         and     %r15,%r9
1214         not     %r11
1215         and     %r15,%r10
1216         and     %r15,%r11
1217
1218         neg     %rdx                    # mov %rdx,%cf
1219         adc     0*8($tptr),%r8
1220         adc     1*8($tptr),%r9
1221         movdqa  %xmm0,($tptr)
1222         adc     2*8($tptr),%r10
1223         adc     3*8($tptr),%r11
1224         movdqa  %xmm0,16($tptr)
1225         lea     4*8($tptr),$tptr
1226         sbb     %rdx,%rdx               # mov %cf,%rdx
1227
1228         mov     %r8,0*8($rptr)
1229         mov     %r9,1*8($rptr)
1230         mov     %r10,2*8($rptr)
1231         mov     %r11,3*8($rptr)
1232         lea     4*8($rptr),$rptr
1233
1234         add     \$32,$num
1235         jnz     .Lmulx4x_sub
1236
1237         mov     56(%rsp),%rsi           # restore %rsp
1238         mov     \$1,%rax
1239 ___
1240 $code.=<<___ if ($win64);
1241         movaps  (%rsi),%xmm6
1242         movaps  0x10(%rsi),%xmm7
1243         lea     0x28(%rsi),%rsi
1244 ___
1245 $code.=<<___;
1246         mov     (%rsi),%r15
1247         mov     8(%rsi),%r14
1248         mov     16(%rsi),%r13
1249         mov     24(%rsi),%r12
1250         mov     32(%rsi),%rbp
1251         mov     40(%rsi),%rbx
1252         lea     48(%rsi),%rsp
1253 .Lmulx4x_epilogue:
1254         ret
1255 .size   bn_mulx4x_mont_gather5,.-bn_mulx4x_mont_gather5
1256 ___
1257 }}}
1258 {
1259 my ($inp,$num,$tbl,$idx)=$win64?("%rcx","%rdx","%r8", "%r9") : # Win64 order
1260                                 ("%rdi","%rsi","%rdx","%rcx"); # Unix order
1261 my $out=$inp;
1262 my $STRIDE=2**5*8;
1263 my $N=$STRIDE/4;
1264
1265 $code.=<<___;
1266 .globl  bn_scatter5
1267 .type   bn_scatter5,\@abi-omnipotent
1268 .align  16
1269 bn_scatter5:
1270         cmp     \$0, $num
1271         jz      .Lscatter_epilogue
1272         lea     ($tbl,$idx,8),$tbl
1273 .Lscatter:
1274         mov     ($inp),%rax
1275         lea     8($inp),$inp
1276         mov     %rax,($tbl)
1277         lea     32*8($tbl),$tbl
1278         sub     \$1,$num
1279         jnz     .Lscatter
1280 .Lscatter_epilogue:
1281         ret
1282 .size   bn_scatter5,.-bn_scatter5
1283
1284 .globl  bn_gather5
1285 .type   bn_gather5,\@abi-omnipotent
1286 .align  16
1287 bn_gather5:
1288 ___
1289 $code.=<<___ if ($win64);
1290 .LSEH_begin_bn_gather5:
1291         # I can't trust assembler to use specific encoding:-(
1292         .byte   0x48,0x83,0xec,0x28             #sub    \$0x28,%rsp
1293         .byte   0x0f,0x29,0x34,0x24             #movaps %xmm6,(%rsp)
1294         .byte   0x0f,0x29,0x7c,0x24,0x10        #movdqa %xmm7,0x10(%rsp)
1295 ___
1296 $code.=<<___;
1297         mov     $idx,%r11
1298         shr     \$`log($N/8)/log(2)`,$idx
1299         and     \$`$N/8-1`,%r11
1300         not     $idx
1301         lea     .Lmagic_masks(%rip),%rax
1302         and     \$`2**5/($N/8)-1`,$idx  # 5 is "window size"
1303         lea     96($tbl,%r11,8),$tbl    # pointer within 1st cache line
1304         movq    0(%rax,$idx,8),%xmm4    # set of masks denoting which
1305         movq    8(%rax,$idx,8),%xmm5    # cache line contains element
1306         movq    16(%rax,$idx,8),%xmm6   # denoted by 7th argument
1307         movq    24(%rax,$idx,8),%xmm7
1308         jmp     .Lgather
1309 .align  16
1310 .Lgather:
1311         movq    `0*$STRIDE/4-96`($tbl),%xmm0
1312         movq    `1*$STRIDE/4-96`($tbl),%xmm1
1313         pand    %xmm4,%xmm0
1314         movq    `2*$STRIDE/4-96`($tbl),%xmm2
1315         pand    %xmm5,%xmm1
1316         movq    `3*$STRIDE/4-96`($tbl),%xmm3
1317         pand    %xmm6,%xmm2
1318         por     %xmm1,%xmm0
1319         pand    %xmm7,%xmm3
1320         por     %xmm2,%xmm0
1321         lea     $STRIDE($tbl),$tbl
1322         por     %xmm3,%xmm0
1323
1324         movq    %xmm0,($out)            # m0=bp[0]
1325         lea     8($out),$out
1326         sub     \$1,$num
1327         jnz     .Lgather
1328 ___
1329 $code.=<<___ if ($win64);
1330         movaps  %xmm6,(%rsp)
1331         movaps  %xmm7,0x10(%rsp)
1332         lea     0x28(%rsp),%rsp
1333 ___
1334 $code.=<<___;
1335         ret
1336 .LSEH_end_bn_gather5:
1337 .size   bn_gather5,.-bn_gather5
1338 ___
1339 }
1340 $code.=<<___;
1341 .align  64
1342 .Lmagic_masks:
1343         .long   0,0, 0,0, 0,0, -1,-1
1344         .long   0,0, 0,0, 0,0,  0,0
1345 .asciz  "Montgomery Multiplication with scatter/gather for x86_64, CRYPTOGAMS by <appro\@openssl.org>"
1346 ___
1347
1348 # EXCEPTION_DISPOSITION handler (EXCEPTION_RECORD *rec,ULONG64 frame,
1349 #               CONTEXT *context,DISPATCHER_CONTEXT *disp)
1350 if ($win64) {
1351 $rec="%rcx";
1352 $frame="%rdx";
1353 $context="%r8";
1354 $disp="%r9";
1355
1356 $code.=<<___;
1357 .extern __imp_RtlVirtualUnwind
1358 .type   mul_handler,\@abi-omnipotent
1359 .align  16
1360 mul_handler:
1361         push    %rsi
1362         push    %rdi
1363         push    %rbx
1364         push    %rbp
1365         push    %r12
1366         push    %r13
1367         push    %r14
1368         push    %r15
1369         pushfq
1370         sub     \$64,%rsp
1371
1372         mov     120($context),%rax      # pull context->Rax
1373         mov     248($context),%rbx      # pull context->Rip
1374
1375         mov     8($disp),%rsi           # disp->ImageBase
1376         mov     56($disp),%r11          # disp->HandlerData
1377
1378         mov     0(%r11),%r10d           # HandlerData[0]
1379         lea     (%rsi,%r10),%r10        # end of prologue label
1380         cmp     %r10,%rbx               # context->Rip<end of prologue label
1381         jb      .Lcommon_seh_tail
1382
1383         lea     `40+48`(%rax),%rax
1384
1385         mov     4(%r11),%r10d           # HandlerData[1]
1386         lea     (%rsi,%r10),%r10        # end of alloca label
1387         cmp     %r10,%rbx               # context->Rip<end of alloca label
1388         jb      .Lcommon_seh_tail
1389
1390         mov     152($context),%rax      # pull context->Rsp
1391
1392         mov     8(%r11),%r10d           # HandlerData[2]
1393         lea     (%rsi,%r10),%r10        # epilogue label
1394         cmp     %r10,%rbx               # context->Rip>=epilogue label
1395         jae     .Lcommon_seh_tail
1396
1397         mov     192($context),%r10      # pull $num
1398         mov     8(%rax,%r10,8),%rax     # pull saved stack pointer
1399
1400         movaps  (%rax),%xmm0
1401         movaps  16(%rax),%xmm1
1402         lea     `40+48`(%rax),%rax
1403
1404         mov     -8(%rax),%rbx
1405         mov     -16(%rax),%rbp
1406         mov     -24(%rax),%r12
1407         mov     -32(%rax),%r13
1408         mov     -40(%rax),%r14
1409         mov     -48(%rax),%r15
1410         mov     %rbx,144($context)      # restore context->Rbx
1411         mov     %rbp,160($context)      # restore context->Rbp
1412         mov     %r12,216($context)      # restore context->R12
1413         mov     %r13,224($context)      # restore context->R13
1414         mov     %r14,232($context)      # restore context->R14
1415         mov     %r15,240($context)      # restore context->R15
1416         movups  %xmm0,512($context)     # restore context->Xmm6
1417         movups  %xmm1,528($context)     # restore context->Xmm7
1418
1419 .Lcommon_seh_tail:
1420         mov     8(%rax),%rdi
1421         mov     16(%rax),%rsi
1422         mov     %rax,152($context)      # restore context->Rsp
1423         mov     %rsi,168($context)      # restore context->Rsi
1424         mov     %rdi,176($context)      # restore context->Rdi
1425
1426         mov     40($disp),%rdi          # disp->ContextRecord
1427         mov     $context,%rsi           # context
1428         mov     \$154,%ecx              # sizeof(CONTEXT)
1429         .long   0xa548f3fc              # cld; rep movsq
1430
1431         mov     $disp,%rsi
1432         xor     %rcx,%rcx               # arg1, UNW_FLAG_NHANDLER
1433         mov     8(%rsi),%rdx            # arg2, disp->ImageBase
1434         mov     0(%rsi),%r8             # arg3, disp->ControlPc
1435         mov     16(%rsi),%r9            # arg4, disp->FunctionEntry
1436         mov     40(%rsi),%r10           # disp->ContextRecord
1437         lea     56(%rsi),%r11           # &disp->HandlerData
1438         lea     24(%rsi),%r12           # &disp->EstablisherFrame
1439         mov     %r10,32(%rsp)           # arg5
1440         mov     %r11,40(%rsp)           # arg6
1441         mov     %r12,48(%rsp)           # arg7
1442         mov     %rcx,56(%rsp)           # arg8, (NULL)
1443         call    *__imp_RtlVirtualUnwind(%rip)
1444
1445         mov     \$1,%eax                # ExceptionContinueSearch
1446         add     \$64,%rsp
1447         popfq
1448         pop     %r15
1449         pop     %r14
1450         pop     %r13
1451         pop     %r12
1452         pop     %rbp
1453         pop     %rbx
1454         pop     %rdi
1455         pop     %rsi
1456         ret
1457 .size   mul_handler,.-mul_handler
1458
1459 .section        .pdata
1460 .align  4
1461         .rva    .LSEH_begin_bn_mul_mont_gather5
1462         .rva    .LSEH_end_bn_mul_mont_gather5
1463         .rva    .LSEH_info_bn_mul_mont_gather5
1464
1465         .rva    .LSEH_begin_bn_mul4x_mont_gather5
1466         .rva    .LSEH_end_bn_mul4x_mont_gather5
1467         .rva    .LSEH_info_bn_mul4x_mont_gather5
1468
1469         .rva    .LSEH_begin_bn_gather5
1470         .rva    .LSEH_end_bn_gather5
1471         .rva    .LSEH_info_bn_gather5
1472
1473 .section        .xdata
1474 .align  8
1475 .LSEH_info_bn_mul_mont_gather5:
1476         .byte   9,0,0,0
1477         .rva    mul_handler
1478         .rva    .Lmul_alloca,.Lmul_body,.Lmul_epilogue          # HandlerData[]
1479 .align  8
1480 .LSEH_info_bn_mul4x_mont_gather5:
1481         .byte   9,0,0,0
1482         .rva    mul_handler
1483         .rva    .Lmul4x_alloca,.Lmul4x_body,.Lmul4x_epilogue    # HandlerData[]
1484 .align  8
1485 .LSEH_info_bn_gather5:
1486         .byte   0x01,0x0d,0x05,0x00
1487         .byte   0x0d,0x78,0x01,0x00     #movaps 0x10(rsp),xmm7
1488         .byte   0x08,0x68,0x00,0x00     #movaps (rsp),xmm6
1489         .byte   0x04,0x42,0x00,0x00     #sub    rsp,0x28
1490 .align  8
1491 ___
1492 }
1493
1494 $code =~ s/\`([^\`]*)\`/eval($1)/gem;
1495
1496 print $code;
1497 close STDOUT;