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 STDOUT,"| $^X $xlate $flavour $output";
  32
  33 # int bn_mul_mont_gather5(
  34 $rp="%rdi";     # BN_ULONG *rp,
  35 $ap="%rsi";     # const BN_ULONG *ap,
  36 $bp="%rdx";     # const BN_ULONG *bp,
  37 $np="%rcx";     # const BN_ULONG *np,
  38 $n0="%r8";      # const BN_ULONG *n0,
  39 $num="%r9";     # int num,
  40                 # int idx);     # 0 to 2^5-1, "index" in $bp holding
  41                                 # pre-computed powers of a', interlaced
  42                                 # in such manner that b[0] is $bp[idx],
  43                                 # b[1] is [2^5+idx], etc.
  44 $lo0="%r10";
  45 $hi0="%r11";
  46 $hi1="%r13";
  47 $i="%r14";
  48 $j="%r15";
  49 $m0="%rbx";
  50 $m1="%rbp";
  51
  52 $code=<<___;
  53 .text
  54
  55 .globl  bn_mul_mont_gather5
  56 .type   bn_mul_mont_gather5,\@function,6
  57 .align  64
  58 bn_mul_mont_gather5:
  59         test    \$3,${num}d
  60         jnz     .Lmul_enter
  61         cmp     \$8,${num}d
  62         jb      .Lmul_enter
  63         jmp     .Lmul4x_enter
  64
  65 .align  16
  66 .Lmul_enter:
  67         mov     ${num}d,${num}d
  68         mov     `($win64?56:8)`(%rsp),%r10d     # load 7th argument
  69         push    %rbx
  70         push    %rbp
  71         push    %r12
  72         push    %r13
  73         push    %r14
  74         push    %r15
  75 ___
  76 $code.=<<___ if ($win64);
  77         lea     -0x28(%rsp),%rsp
  78         movaps  %xmm6,(%rsp)
  79         movaps  %xmm7,0x10(%rsp)
  80 .Lmul_alloca:
  81 ___
  82 $code.=<<___;
  83         mov     %rsp,%rax
  84         lea     2($num),%r11
  85         neg     %r11
  86         lea     (%rsp,%r11,8),%rsp      # tp=alloca(8*(num+2))
  87         and     \$-1024,%rsp            # minimize TLB usage
  88
  89         mov     %rax,8(%rsp,$num,8)     # tp[num+1]=%rsp
  90 .Lmul_body:
  91         mov     $bp,%r12                # reassign $bp
  92 ___
  93                 $bp="%r12";
  94                 $STRIDE=2**5*8;         # 5 is "window size"
  95                 $N=$STRIDE/4;           # should match cache line size
  96 $code.=<<___;
  97         mov     %r10,%r11
  98         shr     \$`log($N/8)/log(2)`,%r10
  99         and     \$`$N/8-1`,%r11
 100         not     %r10
 101         lea     .Lmagic_masks(%rip),%rax
 102         and     \$`2**5/($N/8)-1`,%r10  # 5 is "window size"
 103         lea     96($bp,%r11,8),$bp      # pointer within 1st cache line
 104         movq    0(%rax,%r10,8),%xmm4    # set of masks denoting which
 105         movq    8(%rax,%r10,8),%xmm5    # cache line contains element
 106         movq    16(%rax,%r10,8),%xmm6   # denoted by 7th argument
 107         movq    24(%rax,%r10,8),%xmm7
 108
 109         movq    `0*$STRIDE/4-96`($bp),%xmm0
 110         movq    `1*$STRIDE/4-96`($bp),%xmm1
 111         pand    %xmm4,%xmm0
 112         movq    `2*$STRIDE/4-96`($bp),%xmm2
 113         pand    %xmm5,%xmm1
 114         movq    `3*$STRIDE/4-96`($bp),%xmm3
 115         pand    %xmm6,%xmm2
 116         por     %xmm1,%xmm0
 117         pand    %xmm7,%xmm3
 118         por     %xmm2,%xmm0
 119         lea     $STRIDE($bp),$bp
 120         por     %xmm3,%xmm0
 121
 122         movq    %xmm0,$m0               # m0=bp[0]
 123
 124         mov     ($n0),$n0               # pull n0[0] value
 125         mov     ($ap),%rax
 126
 127         xor     $i,$i                   # i=0
 128         xor     $j,$j                   # j=0
 129
 130         movq    `0*$STRIDE/4-96`($bp),%xmm0
 131         movq    `1*$STRIDE/4-96`($bp),%xmm1
 132         pand    %xmm4,%xmm0
 133         movq    `2*$STRIDE/4-96`($bp),%xmm2
 134         pand    %xmm5,%xmm1
 135
 136         mov     $n0,$m1
 137         mulq    $m0                     # ap[0]*bp[0]
 138         mov     %rax,$lo0
 139         mov     ($np),%rax
 140
 141         movq    `3*$STRIDE/4-96`($bp),%xmm3
 142         pand    %xmm6,%xmm2
 143         por     %xmm1,%xmm0
 144         pand    %xmm7,%xmm3
 145
 146         imulq   $lo0,$m1                # "tp[0]"*n0
 147         mov     %rdx,$hi0
 148
 149         por     %xmm2,%xmm0
 150         lea     $STRIDE($bp),$bp
 151         por     %xmm3,%xmm0
 152
 153         mulq    $m1                     # np[0]*m1
 154         add     %rax,$lo0               # discarded
 155         mov     8($ap),%rax
 156         adc     \$0,%rdx
 157         mov     %rdx,$hi1
 158
 159         lea     1($j),$j                # j++
 160         jmp     .L1st_enter
 161
 162 .align  16
 163 .L1st:
 164         add     %rax,$hi1
 165         mov     ($ap,$j,8),%rax
 166         adc     \$0,%rdx
 167         add     $hi0,$hi1               # np[j]*m1+ap[j]*bp[0]
 168         mov     $lo0,$hi0
 169         adc     \$0,%rdx
 170         mov     $hi1,-16(%rsp,$j,8)     # tp[j-1]
 171         mov     %rdx,$hi1
 172
 173 .L1st_enter:
 174         mulq    $m0                     # ap[j]*bp[0]
 175         add     %rax,$hi0
 176         mov     ($np,$j,8),%rax
 177         adc     \$0,%rdx
 178         lea     1($j),$j                # j++
 179         mov     %rdx,$lo0
 180
 181         mulq    $m1                     # np[j]*m1
 182         cmp     $num,$j
 183         jne     .L1st
 184
 185         movq    %xmm0,$m0               # bp[1]
 186
 187         add     %rax,$hi1
 188         mov     ($ap),%rax              # ap[0]
 189         adc     \$0,%rdx
 190         add     $hi0,$hi1               # np[j]*m1+ap[j]*bp[0]
 191         adc     \$0,%rdx
 192         mov     $hi1,-16(%rsp,$j,8)     # tp[j-1]
 193         mov     %rdx,$hi1
 194         mov     $lo0,$hi0
 195
 196         xor     %rdx,%rdx
 197         add     $hi0,$hi1
 198         adc     \$0,%rdx
 199         mov     $hi1,-8(%rsp,$num,8)
 200         mov     %rdx,(%rsp,$num,8)      # store upmost overflow bit
 201
 202         lea     1($i),$i                # i++
 203         jmp     .Louter
 204 .align  16
 205 .Louter:
 206         xor     $j,$j                   # j=0
 207         mov     $n0,$m1
 208         mov     (%rsp),$lo0
 209
 210         movq    `0*$STRIDE/4-96`($bp),%xmm0
 211         movq    `1*$STRIDE/4-96`($bp),%xmm1
 212         pand    %xmm4,%xmm0
 213         movq    `2*$STRIDE/4-96`($bp),%xmm2
 214         pand    %xmm5,%xmm1
 215
 216         mulq    $m0                     # ap[0]*bp[i]
 217         add     %rax,$lo0               # ap[0]*bp[i]+tp[0]
 218         mov     ($np),%rax
 219         adc     \$0,%rdx
 220
 221         movq    `3*$STRIDE/4-96`($bp),%xmm3
 222         pand    %xmm6,%xmm2
 223         por     %xmm1,%xmm0
 224         pand    %xmm7,%xmm3
 225
 226         imulq   $lo0,$m1                # tp[0]*n0
 227         mov     %rdx,$hi0
 228
 229         por     %xmm2,%xmm0
 230         lea     $STRIDE($bp),$bp
 231         por     %xmm3,%xmm0
 232
 233         mulq    $m1                     # np[0]*m1
 234         add     %rax,$lo0               # discarded
 235         mov     8($ap),%rax
 236         adc     \$0,%rdx
 237         mov     8(%rsp),$lo0            # tp[1]
 238         mov     %rdx,$hi1
 239
 240         lea     1($j),$j                # j++
 241         jmp     .Linner_enter
 242
 243 .align  16
 244 .Linner:
 245         add     %rax,$hi1
 246         mov     ($ap,$j,8),%rax
 247         adc     \$0,%rdx
 248         add     $lo0,$hi1               # np[j]*m1+ap[j]*bp[i]+tp[j]
 249         mov     (%rsp,$j,8),$lo0
 250         adc     \$0,%rdx
 251         mov     $hi1,-16(%rsp,$j,8)     # tp[j-1]
 252         mov     %rdx,$hi1
 253
 254 .Linner_enter:
 255         mulq    $m0                     # ap[j]*bp[i]
 256         add     %rax,$hi0
 257         mov     ($np,$j,8),%rax
 258         adc     \$0,%rdx
 259         add     $hi0,$lo0               # ap[j]*bp[i]+tp[j]
 260         mov     %rdx,$hi0
 261         adc     \$0,$hi0
 262         lea     1($j),$j                # j++
 263
 264         mulq    $m1                     # np[j]*m1
 265         cmp     $num,$j
 266         jne     .Linner
 267
 268         movq    %xmm0,$m0               # bp[i+1]
 269
 270         add     %rax,$hi1
 271         mov     ($ap),%rax              # ap[0]
 272         adc     \$0,%rdx
 273         add     $lo0,$hi1               # np[j]*m1+ap[j]*bp[i]+tp[j]
 274         mov     (%rsp,$j,8),$lo0
 275         adc     \$0,%rdx
 276         mov     $hi1,-16(%rsp,$j,8)     # tp[j-1]
 277         mov     %rdx,$hi1
 278
 279         xor     %rdx,%rdx
 280         add     $hi0,$hi1
 281         adc     \$0,%rdx
 282         add     $lo0,$hi1               # pull upmost overflow bit
 283         adc     \$0,%rdx
 284         mov     $hi1,-8(%rsp,$num,8)
 285         mov     %rdx,(%rsp,$num,8)      # store upmost overflow bit
 286
 287         lea     1($i),$i                # i++
 288         cmp     $num,$i
 289         jl      .Louter
 290
 291         xor     $i,$i                   # i=0 and clear CF!
 292         mov     (%rsp),%rax             # tp[0]
 293         lea     (%rsp),$ap              # borrow ap for tp
 294         mov     $num,$j                 # j=num
 295         jmp     .Lsub
 296 .align  16
 297 .Lsub:  sbb     ($np,$i,8),%rax
 298         mov     %rax,($rp,$i,8)         # rp[i]=tp[i]-np[i]
 299         mov     8($ap,$i,8),%rax        # tp[i+1]
 300         lea     1($i),$i                # i++
 301         dec     $j                      # doesnn't affect CF!
 302         jnz     .Lsub
 303
 304         sbb     \$0,%rax                # handle upmost overflow bit
 305         xor     $i,$i
 306         and     %rax,$ap
 307         not     %rax
 308         mov     $rp,$np
 309         and     %rax,$np
 310         mov     $num,$j                 # j=num
 311         or      $np,$ap                 # ap=borrow?tp:rp
 312 .align  16
 313 .Lcopy:                                 # copy or in-place refresh
 314         mov     ($ap,$i,8),%rax
 315         mov     $i,(%rsp,$i,8)          # zap temporary vector
 316         mov     %rax,($rp,$i,8)         # rp[i]=tp[i]
 317         lea     1($i),$i
 318         sub     \$1,$j
 319         jnz     .Lcopy
 320
 321         mov     8(%rsp,$num,8),%rsi     # restore %rsp
 322         mov     \$1,%rax
 323 ___
 324 $code.=<<___ if ($win64);
 325         movaps  (%rsi),%xmm6
 326         movaps  0x10(%rsi),%xmm7
 327         lea     0x28(%rsi),%rsi
 328 ___
 329 $code.=<<___;
 330         mov     (%rsi),%r15
 331         mov     8(%rsi),%r14
 332         mov     16(%rsi),%r13
 333         mov     24(%rsi),%r12
 334         mov     32(%rsi),%rbp
 335         mov     40(%rsi),%rbx
 336         lea     48(%rsi),%rsp
 337 .Lmul_epilogue:
 338         ret
 339 .size   bn_mul_mont_gather5,.-bn_mul_mont_gather5
 340 ___
 341 {{{
 342 my @A=("%r10","%r11");
 343 my @N=("%r13","%rdi");
 344 $code.=<<___;
 345 .type   bn_mul4x_mont_gather5,\@function,6
 346 .align  16
 347 bn_mul4x_mont_gather5:
 348 .Lmul4x_enter:
 349         mov     ${num}d,${num}d
 350         mov     `($win64?56:8)`(%rsp),%r10d     # load 7th argument
 351         push    %rbx
 352         push    %rbp
 353         push    %r12
 354         push    %r13
 355         push    %r14
 356         push    %r15
 357 ___
 358 $code.=<<___ if ($win64);
 359         lea     -0x28(%rsp),%rsp
 360         movaps  %xmm6,(%rsp)
 361         movaps  %xmm7,0x10(%rsp)
 362 .Lmul4x_alloca:
 363 ___
 364 $code.=<<___;
 365         mov     %rsp,%rax
 366         lea     4($num),%r11
 367         neg     %r11
 368         lea     (%rsp,%r11,8),%rsp      # tp=alloca(8*(num+4))
 369         and     \$-1024,%rsp            # minimize TLB usage
 370
 371         mov     %rax,8(%rsp,$num,8)     # tp[num+1]=%rsp
 372 .Lmul4x_body:
 373         mov     $rp,16(%rsp,$num,8)     # tp[num+2]=$rp
 374         mov     %rdx,%r12               # reassign $bp
 375 ___
 376                 $bp="%r12";
 377                 $STRIDE=2**5*8;         # 5 is "window size"
 378                 $N=$STRIDE/4;           # should match cache line size
 379 $code.=<<___;
 380         mov     %r10,%r11
 381         shr     \$`log($N/8)/log(2)`,%r10
 382         and     \$`$N/8-1`,%r11
 383         not     %r10
 384         lea     .Lmagic_masks(%rip),%rax
 385         and     \$`2**5/($N/8)-1`,%r10  # 5 is "window size"
 386         lea     96($bp,%r11,8),$bp      # pointer within 1st cache line
 387         movq    0(%rax,%r10,8),%xmm4    # set of masks denoting which
 388         movq    8(%rax,%r10,8),%xmm5    # cache line contains element
 389         movq    16(%rax,%r10,8),%xmm6   # denoted by 7th argument
 390         movq    24(%rax,%r10,8),%xmm7
 391
 392         movq    `0*$STRIDE/4-96`($bp),%xmm0
 393         movq    `1*$STRIDE/4-96`($bp),%xmm1
 394         pand    %xmm4,%xmm0
 395         movq    `2*$STRIDE/4-96`($bp),%xmm2
 396         pand    %xmm5,%xmm1
 397         movq    `3*$STRIDE/4-96`($bp),%xmm3
 398         pand    %xmm6,%xmm2
 399         por     %xmm1,%xmm0
 400         pand    %xmm7,%xmm3
 401         por     %xmm2,%xmm0
 402         lea     $STRIDE($bp),$bp
 403         por     %xmm3,%xmm0
 404
 405         movq    %xmm0,$m0               # m0=bp[0]
 406         mov     ($n0),$n0               # pull n0[0] value
 407         mov     ($ap),%rax
 408
 409         xor     $i,$i                   # i=0
 410         xor     $j,$j                   # j=0
 411
 412         movq    `0*$STRIDE/4-96`($bp),%xmm0
 413         movq    `1*$STRIDE/4-96`($bp),%xmm1
 414         pand    %xmm4,%xmm0
 415         movq    `2*$STRIDE/4-96`($bp),%xmm2
 416         pand    %xmm5,%xmm1
 417
 418         mov     $n0,$m1
 419         mulq    $m0                     # ap[0]*bp[0]
 420         mov     %rax,$A[0]
 421         mov     ($np),%rax
 422
 423         movq    `3*$STRIDE/4-96`($bp),%xmm3
 424         pand    %xmm6,%xmm2
 425         por     %xmm1,%xmm0
 426         pand    %xmm7,%xmm3
 427
 428         imulq   $A[0],$m1               # "tp[0]"*n0
 429         mov     %rdx,$A[1]
 430
 431         por     %xmm2,%xmm0
 432         lea     $STRIDE($bp),$bp
 433         por     %xmm3,%xmm0
 434
 435         mulq    $m1                     # np[0]*m1
 436         add     %rax,$A[0]              # discarded
 437         mov     8($ap),%rax
 438         adc     \$0,%rdx
 439         mov     %rdx,$N[1]
 440
 441         mulq    $m0
 442         add     %rax,$A[1]
 443         mov     8($np),%rax
 444         adc     \$0,%rdx
 445         mov     %rdx,$A[0]
 446
 447         mulq    $m1
 448         add     %rax,$N[1]
 449         mov     16($ap),%rax
 450         adc     \$0,%rdx
 451         add     $A[1],$N[1]
 452         lea     4($j),$j                # j++
 453         adc     \$0,%rdx
 454         mov     $N[1],(%rsp)
 455         mov     %rdx,$N[0]
 456         jmp     .L1st4x
 457 .align  16
 458 .L1st4x:
 459         mulq    $m0                     # ap[j]*bp[0]
 460         add     %rax,$A[0]
 461         mov     -16($np,$j,8),%rax
 462         adc     \$0,%rdx
 463         mov     %rdx,$A[1]
 464
 465         mulq    $m1                     # np[j]*m1
 466         add     %rax,$N[0]
 467         mov     -8($ap,$j,8),%rax
 468         adc     \$0,%rdx
 469         add     $A[0],$N[0]             # np[j]*m1+ap[j]*bp[0]
 470         adc     \$0,%rdx
 471         mov     $N[0],-24(%rsp,$j,8)    # tp[j-1]
 472         mov     %rdx,$N[1]
 473
 474         mulq    $m0                     # ap[j]*bp[0]
 475         add     %rax,$A[1]
 476         mov     -8($np,$j,8),%rax
 477         adc     \$0,%rdx
 478         mov     %rdx,$A[0]
 479
 480         mulq    $m1                     # np[j]*m1
 481         add     %rax,$N[1]
 482         mov     ($ap,$j,8),%rax
 483         adc     \$0,%rdx
 484         add     $A[1],$N[1]             # np[j]*m1+ap[j]*bp[0]
 485         adc     \$0,%rdx
 486         mov     $N[1],-16(%rsp,$j,8)    # tp[j-1]
 487         mov     %rdx,$N[0]
 488
 489         mulq    $m0                     # ap[j]*bp[0]
 490         add     %rax,$A[0]
 491         mov     ($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],-8(%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         lea     4($j),$j                # j++
 509         mov     %rdx,$A[0]
 510
 511         mulq    $m1                     # np[j]*m1
 512         add     %rax,$N[1]
 513         mov     -16($ap,$j,8),%rax
 514         adc     \$0,%rdx
 515         add     $A[1],$N[1]             # np[j]*m1+ap[j]*bp[0]
 516         adc     \$0,%rdx
 517         mov     $N[1],-32(%rsp,$j,8)    # tp[j-1]
 518         mov     %rdx,$N[0]
 519         cmp     $num,$j
 520         jl      .L1st4x
 521
 522         mulq    $m0                     # ap[j]*bp[0]
 523         add     %rax,$A[0]
 524         mov     -16($np,$j,8),%rax
 525         adc     \$0,%rdx
 526         mov     %rdx,$A[1]
 527
 528         mulq    $m1                     # np[j]*m1
 529         add     %rax,$N[0]
 530         mov     -8($ap,$j,8),%rax
 531         adc     \$0,%rdx
 532         add     $A[0],$N[0]             # np[j]*m1+ap[j]*bp[0]
 533         adc     \$0,%rdx
 534         mov     $N[0],-24(%rsp,$j,8)    # tp[j-1]
 535         mov     %rdx,$N[1]
 536
 537         mulq    $m0                     # ap[j]*bp[0]
 538         add     %rax,$A[1]
 539         mov     -8($np,$j,8),%rax
 540         adc     \$0,%rdx
 541         mov     %rdx,$A[0]
 542
 543         mulq    $m1                     # np[j]*m1
 544         add     %rax,$N[1]
 545         mov     ($ap),%rax              # ap[0]
 546         adc     \$0,%rdx
 547         add     $A[1],$N[1]             # np[j]*m1+ap[j]*bp[0]
 548         adc     \$0,%rdx
 549         mov     $N[1],-16(%rsp,$j,8)    # tp[j-1]
 550         mov     %rdx,$N[0]
 551
 552         movq    %xmm0,$m0               # bp[1]
 553
 554         xor     $N[1],$N[1]
 555         add     $A[0],$N[0]
 556         adc     \$0,$N[1]
 557         mov     $N[0],-8(%rsp,$j,8)
 558         mov     $N[1],(%rsp,$j,8)       # store upmost overflow bit
 559
 560         lea     1($i),$i                # i++
 561 .align  4
 562 .Louter4x:
 563         xor     $j,$j                   # j=0
 564         movq    `0*$STRIDE/4-96`($bp),%xmm0
 565         movq    `1*$STRIDE/4-96`($bp),%xmm1
 566         pand    %xmm4,%xmm0
 567         movq    `2*$STRIDE/4-96`($bp),%xmm2
 568         pand    %xmm5,%xmm1
 569
 570         mov     (%rsp),$A[0]
 571         mov     $n0,$m1
 572         mulq    $m0                     # ap[0]*bp[i]
 573         add     %rax,$A[0]              # ap[0]*bp[i]+tp[0]
 574         mov     ($np),%rax
 575         adc     \$0,%rdx
 576
 577         movq    `3*$STRIDE/4-96`($bp),%xmm3
 578         pand    %xmm6,%xmm2
 579         por     %xmm1,%xmm0
 580         pand    %xmm7,%xmm3
 581
 582         imulq   $A[0],$m1               # tp[0]*n0
 583         mov     %rdx,$A[1]
 584
 585         por     %xmm2,%xmm0
 586         lea     $STRIDE($bp),$bp
 587         por     %xmm3,%xmm0
 588
 589         mulq    $m1                     # np[0]*m1
 590         add     %rax,$A[0]              # "$N[0]", discarded
 591         mov     8($ap),%rax
 592         adc     \$0,%rdx
 593         mov     %rdx,$N[1]
 594
 595         mulq    $m0                     # ap[j]*bp[i]
 596         add     %rax,$A[1]
 597         mov     8($np),%rax
 598         adc     \$0,%rdx
 599         add     8(%rsp),$A[1]           # +tp[1]
 600         adc     \$0,%rdx
 601         mov     %rdx,$A[0]
 602
 603         mulq    $m1                     # np[j]*m1
 604         add     %rax,$N[1]
 605         mov     16($ap),%rax
 606         adc     \$0,%rdx
 607         add     $A[1],$N[1]             # np[j]*m1+ap[j]*bp[i]+tp[j]
 608         lea     4($j),$j                # j+=2
 609         adc     \$0,%rdx
 610         mov     $N[1],(%rsp)            # tp[j-1]
 611         mov     %rdx,$N[0]
 612         jmp     .Linner4x
 613 .align  16
 614 .Linner4x:
 615         mulq    $m0                     # ap[j]*bp[i]
 616         add     %rax,$A[0]
 617         mov     -16($np,$j,8),%rax
 618         adc     \$0,%rdx
 619         add     -16(%rsp,$j,8),$A[0]    # ap[j]*bp[i]+tp[j]
 620         adc     \$0,%rdx
 621         mov     %rdx,$A[1]
 622
 623         mulq    $m1                     # np[j]*m1
 624         add     %rax,$N[0]
 625         mov     -8($ap,$j,8),%rax
 626         adc     \$0,%rdx
 627         add     $A[0],$N[0]
 628         adc     \$0,%rdx
 629         mov     $N[0],-24(%rsp,$j,8)    # tp[j-1]
 630         mov     %rdx,$N[1]
 631
 632         mulq    $m0                     # ap[j]*bp[i]
 633         add     %rax,$A[1]
 634         mov     -8($np,$j,8),%rax
 635         adc     \$0,%rdx
 636         add     -8(%rsp,$j,8),$A[1]
 637         adc     \$0,%rdx
 638         mov     %rdx,$A[0]
 639
 640         mulq    $m1                     # np[j]*m1
 641         add     %rax,$N[1]
 642         mov     ($ap,$j,8),%rax
 643         adc     \$0,%rdx
 644         add     $A[1],$N[1]
 645         adc     \$0,%rdx
 646         mov     $N[1],-16(%rsp,$j,8)    # tp[j-1]
 647         mov     %rdx,$N[0]
 648
 649         mulq    $m0                     # ap[j]*bp[i]
 650         add     %rax,$A[0]
 651         mov     ($np,$j,8),%rax
 652         adc     \$0,%rdx
 653         add     (%rsp,$j,8),$A[0]       # ap[j]*bp[i]+tp[j]
 654         adc     \$0,%rdx
 655         mov     %rdx,$A[1]
 656
 657         mulq    $m1                     # np[j]*m1
 658         add     %rax,$N[0]
 659         mov     8($ap,$j,8),%rax
 660         adc     \$0,%rdx
 661         add     $A[0],$N[0]
 662         adc     \$0,%rdx
 663         mov     $N[0],-8(%rsp,$j,8)     # tp[j-1]
 664         mov     %rdx,$N[1]
 665
 666         mulq    $m0                     # ap[j]*bp[i]
 667         add     %rax,$A[1]
 668         mov     8($np,$j,8),%rax
 669         adc     \$0,%rdx
 670         add     8(%rsp,$j,8),$A[1]
 671         adc     \$0,%rdx
 672         lea     4($j),$j                # j++
 673         mov     %rdx,$A[0]
 674
 675         mulq    $m1                     # np[j]*m1
 676         add     %rax,$N[1]
 677         mov     -16($ap,$j,8),%rax
 678         adc     \$0,%rdx
 679         add     $A[1],$N[1]
 680         adc     \$0,%rdx
 681         mov     $N[1],-32(%rsp,$j,8)    # tp[j-1]
 682         mov     %rdx,$N[0]
 683         cmp     $num,$j
 684         jl      .Linner4x
 685
 686         mulq    $m0                     # ap[j]*bp[i]
 687         add     %rax,$A[0]
 688         mov     -16($np,$j,8),%rax
 689         adc     \$0,%rdx
 690         add     -16(%rsp,$j,8),$A[0]    # ap[j]*bp[i]+tp[j]
 691         adc     \$0,%rdx
 692         mov     %rdx,$A[1]
 693
 694         mulq    $m1                     # np[j]*m1
 695         add     %rax,$N[0]
 696         mov     -8($ap,$j,8),%rax
 697         adc     \$0,%rdx
 698         add     $A[0],$N[0]
 699         adc     \$0,%rdx
 700         mov     $N[0],-24(%rsp,$j,8)    # tp[j-1]
 701         mov     %rdx,$N[1]
 702
 703         mulq    $m0                     # ap[j]*bp[i]
 704         add     %rax,$A[1]
 705         mov     -8($np,$j,8),%rax
 706         adc     \$0,%rdx
 707         add     -8(%rsp,$j,8),$A[1]
 708         adc     \$0,%rdx
 709         lea     1($i),$i                # i++
 710         mov     %rdx,$A[0]
 711
 712         mulq    $m1                     # np[j]*m1
 713         add     %rax,$N[1]
 714         mov     ($ap),%rax              # ap[0]
 715         adc     \$0,%rdx
 716         add     $A[1],$N[1]
 717         adc     \$0,%rdx
 718         mov     $N[1],-16(%rsp,$j,8)    # tp[j-1]
 719         mov     %rdx,$N[0]
 720
 721         movq    %xmm0,$m0               # bp[i+1]
 722
 723         xor     $N[1],$N[1]
 724         add     $A[0],$N[0]
 725         adc     \$0,$N[1]
 726         add     (%rsp,$num,8),$N[0]     # pull upmost overflow bit
 727         adc     \$0,$N[1]
 728         mov     $N[0],-8(%rsp,$j,8)
 729         mov     $N[1],(%rsp,$j,8)       # store upmost overflow bit
 730
 731         cmp     $num,$i
 732         jl      .Louter4x
 733 ___
 734 {
 735 my @ri=("%rax","%rdx",$m0,$m1);
 736 $code.=<<___;
 737         mov     16(%rsp,$num,8),$rp     # restore $rp
 738         mov     0(%rsp),@ri[0]          # tp[0]
 739         pxor    %xmm0,%xmm0
 740         mov     8(%rsp),@ri[1]          # tp[1]
 741         shr     \$2,$num                # num/=4
 742         lea     (%rsp),$ap              # borrow ap for tp
 743         xor     $i,$i                   # i=0 and clear CF!
 744
 745         sub     0($np),@ri[0]
 746         mov     16($ap),@ri[2]          # tp[2]
 747         mov     24($ap),@ri[3]          # tp[3]
 748         sbb     8($np),@ri[1]
 749         lea     -1($num),$j             # j=num/4-1
 750         jmp     .Lsub4x
 751 .align  16
 752 .Lsub4x:
 753         mov     @ri[0],0($rp,$i,8)      # rp[i]=tp[i]-np[i]
 754         mov     @ri[1],8($rp,$i,8)      # rp[i]=tp[i]-np[i]
 755         sbb     16($np,$i,8),@ri[2]
 756         mov     32($ap,$i,8),@ri[0]     # tp[i+1]
 757         mov     40($ap,$i,8),@ri[1]
 758         sbb     24($np,$i,8),@ri[3]
 759         mov     @ri[2],16($rp,$i,8)     # rp[i]=tp[i]-np[i]
 760         mov     @ri[3],24($rp,$i,8)     # rp[i]=tp[i]-np[i]
 761         sbb     32($np,$i,8),@ri[0]
 762         mov     48($ap,$i,8),@ri[2]
 763         mov     56($ap,$i,8),@ri[3]
 764         sbb     40($np,$i,8),@ri[1]
 765         lea     4($i),$i                # i++
 766         dec     $j                      # doesnn't affect CF!
 767         jnz     .Lsub4x
 768
 769         mov     @ri[0],0($rp,$i,8)      # rp[i]=tp[i]-np[i]
 770         mov     32($ap,$i,8),@ri[0]     # load overflow bit
 771         sbb     16($np,$i,8),@ri[2]
 772         mov     @ri[1],8($rp,$i,8)      # rp[i]=tp[i]-np[i]
 773         sbb     24($np,$i,8),@ri[3]
 774         mov     @ri[2],16($rp,$i,8)     # rp[i]=tp[i]-np[i]
 775
 776         sbb     \$0,@ri[0]              # handle upmost overflow bit
 777         mov     @ri[3],24($rp,$i,8)     # rp[i]=tp[i]-np[i]
 778         xor     $i,$i                   # i=0
 779         and     @ri[0],$ap
 780         not     @ri[0]
 781         mov     $rp,$np
 782         and     @ri[0],$np
 783         lea     -1($num),$j
 784         or      $np,$ap                 # ap=borrow?tp:rp
 785
 786         movdqu  ($ap),%xmm1
 787         movdqa  %xmm0,(%rsp)
 788         movdqu  %xmm1,($rp)
 789         jmp     .Lcopy4x
 790 .align  16
 791 .Lcopy4x:                                       # copy or in-place refresh
 792         movdqu  16($ap,$i),%xmm2
 793         movdqu  32($ap,$i),%xmm1
 794         movdqa  %xmm0,16(%rsp,$i)
 795         movdqu  %xmm2,16($rp,$i)
 796         movdqa  %xmm0,32(%rsp,$i)
 797         movdqu  %xmm1,32($rp,$i)
 798         lea     32($i),$i
 799         dec     $j
 800         jnz     .Lcopy4x
 801
 802         shl     \$2,$num
 803         movdqu  16($ap,$i),%xmm2
 804         movdqa  %xmm0,16(%rsp,$i)
 805         movdqu  %xmm2,16($rp,$i)
 806 ___
 807 }
 808 $code.=<<___;
 809         mov     8(%rsp,$num,8),%rsi     # restore %rsp
 810         mov     \$1,%rax
 811 ___
 812 $code.=<<___ if ($win64);
 813         movaps  (%rsi),%xmm6
 814         movaps  0x10(%rsi),%xmm7
 815         lea     0x28(%rsi),%rsi
 816 ___
 817 $code.=<<___;
 818         mov     (%rsi),%r15
 819         mov     8(%rsi),%r14
 820         mov     16(%rsi),%r13
 821         mov     24(%rsi),%r12
 822         mov     32(%rsi),%rbp
 823         mov     40(%rsi),%rbx
 824         lea     48(%rsi),%rsp
 825 .Lmul4x_epilogue:
 826         ret
 827 .size   bn_mul4x_mont_gather5,.-bn_mul4x_mont_gather5
 828 ___
 829 }}}
 830
 831 {
 832 my ($inp,$num,$tbl,$idx)=$win64?("%rcx","%rdx","%r8", "%r9") : # Win64 order
 833                                 ("%rdi","%rsi","%rdx","%rcx"); # Unix order
 834 $code.=<<___;
 835 .globl  bn_scatter5
 836 .type   bn_scatter5,\@abi-omnipotent
 837 .align  16
 838 bn_scatter5:
 839         lea     ($tbl,$idx,8),$tbl
 840 .Lscatter:
 841         mov     ($inp),%rax
 842         lea     8($inp),$inp
 843         mov     %rax,($tbl)
 844         lea     32*8($tbl),$tbl
 845         sub     \$1,$num
 846         jnz     .Lscatter
 847         ret
 848 .size   bn_scatter5,.-bn_scatter5
 849 ___
 850 }
 851 $code.=<<___;
 852 .align  64
 853 .Lmagic_masks:
 854         .long   0,0, 0,0, 0,0, -1,-1
 855         .long   0,0, 0,0, 0,0,  0,0
 856 .asciz  "Montgomery Multiplication with scatter/gather for x86_64, CRYPTOGAMS by <appro\@openssl.org>"
 857 ___
 858
 859 # EXCEPTION_DISPOSITION handler (EXCEPTION_RECORD *rec,ULONG64 frame,
 860 #               CONTEXT *context,DISPATCHER_CONTEXT *disp)
 861 if ($win64) {
 862 $rec="%rcx";
 863 $frame="%rdx";
 864 $context="%r8";
 865 $disp="%r9";
 866
 867 $code.=<<___;
 868 .extern __imp_RtlVirtualUnwind
 869 .type   mul_handler,\@abi-omnipotent
 870 .align  16
 871 mul_handler:
 872         push    %rsi
 873         push    %rdi
 874         push    %rbx
 875         push    %rbp
 876         push    %r12
 877         push    %r13
 878         push    %r14
 879         push    %r15
 880         pushfq
 881         sub     \$64,%rsp
 882
 883         mov     120($context),%rax      # pull context->Rax
 884         mov     248($context),%rbx      # pull context->Rip
 885
 886         mov     8($disp),%rsi           # disp->ImageBase
 887         mov     56($disp),%r11          # disp->HandlerData
 888
 889         mov     0(%r11),%r10d           # HandlerData[0]
 890         lea     (%rsi,%r10),%r10        # end of prologue label
 891         cmp     %r10,%rbx               # context->Rip<end of prologue label
 892         jb      .Lcommon_seh_tail
 893
 894         lea     `40+48`(%rax),%rax
 895
 896         mov     4(%r11),%r10d           # HandlerData[1]
 897         lea     (%rsi,%r10),%r10        # end of alloca label
 898         cmp     %r10,%rbx               # context->Rip<end of alloca label
 899         jb      .Lcommon_seh_tail
 900
 901         mov     152($context),%rax      # pull context->Rsp
 902
 903         mov     8(%r11),%r10d           # HandlerData[2]
 904         lea     (%rsi,%r10),%r10        # epilogue label
 905         cmp     %r10,%rbx               # context->Rip>=epilogue label
 906         jae     .Lcommon_seh_tail
 907
 908         mov     192($context),%r10      # pull $num
 909         mov     8(%rax,%r10,8),%rax     # pull saved stack pointer
 910
 911         movaps  (%rax),%xmm0
 912         movaps  16(%rax),%xmm1
 913         lea     `40+48`(%rax),%rax
 914
 915         mov     -8(%rax),%rbx
 916         mov     -16(%rax),%rbp
 917         mov     -24(%rax),%r12
 918         mov     -32(%rax),%r13
 919         mov     -40(%rax),%r14
 920         mov     -48(%rax),%r15
 921         mov     %rbx,144($context)      # restore context->Rbx
 922         mov     %rbp,160($context)      # restore context->Rbp
 923         mov     %r12,216($context)      # restore context->R12
 924         mov     %r13,224($context)      # restore context->R13
 925         mov     %r14,232($context)      # restore context->R14
 926         mov     %r15,240($context)      # restore context->R15
 927         movups  %xmm0,512($context)     # restore context->Xmm6
 928         movups  %xmm1,528($context)     # restore context->Xmm7
 929
 930 .Lcommon_seh_tail:
 931         mov     8(%rax),%rdi
 932         mov     16(%rax),%rsi
 933         mov     %rax,152($context)      # restore context->Rsp
 934         mov     %rsi,168($context)      # restore context->Rsi
 935         mov     %rdi,176($context)      # restore context->Rdi
 936
 937         mov     40($disp),%rdi          # disp->ContextRecord
 938         mov     $context,%rsi           # context
 939         mov     \$154,%ecx              # sizeof(CONTEXT)
 940         .long   0xa548f3fc              # cld; rep movsq
 941
 942         mov     $disp,%rsi
 943         xor     %rcx,%rcx               # arg1, UNW_FLAG_NHANDLER
 944         mov     8(%rsi),%rdx            # arg2, disp->ImageBase
 945         mov     0(%rsi),%r8             # arg3, disp->ControlPc
 946         mov     16(%rsi),%r9            # arg4, disp->FunctionEntry
 947         mov     40(%rsi),%r10           # disp->ContextRecord
 948         lea     56(%rsi),%r11           # &disp->HandlerData
 949         lea     24(%rsi),%r12           # &disp->EstablisherFrame
 950         mov     %r10,32(%rsp)           # arg5
 951         mov     %r11,40(%rsp)           # arg6
 952         mov     %r12,48(%rsp)           # arg7
 953         mov     %rcx,56(%rsp)           # arg8, (NULL)
 954         call    *__imp_RtlVirtualUnwind(%rip)
 955
 956         mov     \$1,%eax                # ExceptionContinueSearch
 957         add     \$64,%rsp
 958         popfq
 959         pop     %r15
 960         pop     %r14
 961         pop     %r13
 962         pop     %r12
 963         pop     %rbp
 964         pop     %rbx
 965         pop     %rdi
 966         pop     %rsi
 967         ret
 968 .size   mul_handler,.-mul_handler
 969
 970 .section        .pdata
 971 .align  4
 972         .rva    .LSEH_begin_bn_mul_mont_gather5
 973         .rva    .LSEH_end_bn_mul_mont_gather5
 974         .rva    .LSEH_info_bn_mul_mont_gather5
 975
 976         .rva    .LSEH_begin_bn_mul4x_mont_gather5
 977         .rva    .LSEH_end_bn_mul4x_mont_gather5
 978         .rva    .LSEH_info_bn_mul4x_mont_gather5
 979
 980 .section        .xdata
 981 .align  8
 982 .LSEH_info_bn_mul_mont_gather5:
 983         .byte   9,0,0,0
 984         .rva    mul_handler
 985         .rva    .Lmul_alloca,.Lmul_body,.Lmul_epilogue          # HandlerData[]
 986 .align  8
 987 .LSEH_info_bn_mul4x_mont_gather5:
 988         .byte   9,0,0,0
 989         .rva    mul_handler
 990         .rva    .Lmul4x_alloca,.Lmul4x_body,.Lmul4x_epilogue    # HandlerData[]
 991 .align  8
 992 ___
 993 }
 994
 995 $code =~ s/\`([^\`]*)\`/eval($1)/gem;
 996
 997 print $code;
 998 close STDOUT;