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     %rdx,$N[0]
 611         jmp     .Linner4x
 612 .align  16
 613 .Linner4x:
 614         mulq    $m0                     # ap[j]*bp[i]
 615         add     %rax,$A[0]
 616         mov     -16($np,$j,8),%rax
 617         adc     \$0,%rdx
 618         add     -16(%rsp,$j,8),$A[0]    # ap[j]*bp[i]+tp[j]
 619         adc     \$0,%rdx
 620         mov     %rdx,$A[1]
 621
 622         mulq    $m1                     # np[j]*m1
 623         add     %rax,$N[0]
 624         mov     -8($ap,$j,8),%rax
 625         adc     \$0,%rdx
 626         add     $A[0],$N[0]
 627         adc     \$0,%rdx
 628         mov     $N[1],-32(%rsp,$j,8)    # tp[j-1]
 629         mov     %rdx,$N[1]
 630
 631         mulq    $m0                     # ap[j]*bp[i]
 632         add     %rax,$A[1]
 633         mov     -8($np,$j,8),%rax
 634         adc     \$0,%rdx
 635         add     -8(%rsp,$j,8),$A[1]
 636         adc     \$0,%rdx
 637         mov     %rdx,$A[0]
 638
 639         mulq    $m1                     # np[j]*m1
 640         add     %rax,$N[1]
 641         mov     ($ap,$j,8),%rax
 642         adc     \$0,%rdx
 643         add     $A[1],$N[1]
 644         adc     \$0,%rdx
 645         mov     $N[0],-24(%rsp,$j,8)    # tp[j-1]
 646         mov     %rdx,$N[0]
 647
 648         mulq    $m0                     # ap[j]*bp[i]
 649         add     %rax,$A[0]
 650         mov     ($np,$j,8),%rax
 651         adc     \$0,%rdx
 652         add     (%rsp,$j,8),$A[0]       # ap[j]*bp[i]+tp[j]
 653         adc     \$0,%rdx
 654         mov     %rdx,$A[1]
 655
 656         mulq    $m1                     # np[j]*m1
 657         add     %rax,$N[0]
 658         mov     8($ap,$j,8),%rax
 659         adc     \$0,%rdx
 660         add     $A[0],$N[0]
 661         adc     \$0,%rdx
 662         mov     $N[1],-16(%rsp,$j,8)    # tp[j-1]
 663         mov     %rdx,$N[1]
 664
 665         mulq    $m0                     # ap[j]*bp[i]
 666         add     %rax,$A[1]
 667         mov     8($np,$j,8),%rax
 668         adc     \$0,%rdx
 669         add     8(%rsp,$j,8),$A[1]
 670         adc     \$0,%rdx
 671         lea     4($j),$j                # j++
 672         mov     %rdx,$A[0]
 673
 674         mulq    $m1                     # np[j]*m1
 675         add     %rax,$N[1]
 676         mov     -16($ap,$j,8),%rax
 677         adc     \$0,%rdx
 678         add     $A[1],$N[1]
 679         adc     \$0,%rdx
 680         mov     $N[0],-40(%rsp,$j,8)    # tp[j-1]
 681         mov     %rdx,$N[0]
 682         cmp     $num,$j
 683         jl      .Linner4x
 684
 685         mulq    $m0                     # ap[j]*bp[i]
 686         add     %rax,$A[0]
 687         mov     -16($np,$j,8),%rax
 688         adc     \$0,%rdx
 689         add     -16(%rsp,$j,8),$A[0]    # ap[j]*bp[i]+tp[j]
 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,8),%rax
 696         adc     \$0,%rdx
 697         add     $A[0],$N[0]
 698         adc     \$0,%rdx
 699         mov     $N[1],-32(%rsp,$j,8)    # tp[j-1]
 700         mov     %rdx,$N[1]
 701
 702         mulq    $m0                     # ap[j]*bp[i]
 703         add     %rax,$A[1]
 704         mov     -8($np,$j,8),%rax
 705         adc     \$0,%rdx
 706         add     -8(%rsp,$j,8),$A[1]
 707         adc     \$0,%rdx
 708         lea     1($i),$i                # i++
 709         mov     %rdx,$A[0]
 710
 711         mulq    $m1                     # np[j]*m1
 712         add     %rax,$N[1]
 713         mov     ($ap),%rax              # ap[0]
 714         adc     \$0,%rdx
 715         add     $A[1],$N[1]
 716         adc     \$0,%rdx
 717         mov     $N[0],-24(%rsp,$j,8)    # tp[j-1]
 718         mov     %rdx,$N[0]
 719
 720         movq    %xmm0,$m0               # bp[i+1]
 721         mov     $N[1],-16(%rsp,$j,8)    # tp[j-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 my $out=$inp;
 835 my $STRIDE=2**5*8;
 836 my $N=$STRIDE/4;
 837
 838 $code.=<<___;
 839 .globl  bn_scatter5
 840 .type   bn_scatter5,\@abi-omnipotent
 841 .align  16
 842 bn_scatter5:
 843         cmp     \$0, $num
 844         jz      .Lscatter_epilogue
 845         lea     ($tbl,$idx,8),$tbl
 846 .Lscatter:
 847         mov     ($inp),%rax
 848         lea     8($inp),$inp
 849         mov     %rax,($tbl)
 850         lea     32*8($tbl),$tbl
 851         sub     \$1,$num
 852         jnz     .Lscatter
 853 .Lscatter_epilogue:
 854         ret
 855 .size   bn_scatter5,.-bn_scatter5
 856
 857 .globl  bn_gather5
 858 .type   bn_gather5,\@abi-omnipotent
 859 .align  16
 860 bn_gather5:
 861 ___
 862 $code.=<<___ if ($win64);
 863 .LSEH_begin_bn_gather5:
 864         # I can't trust assembler to use specific encoding:-(
 865         .byte   0x48,0x83,0xec,0x28             #sub    \$0x28,%rsp
 866         .byte   0x0f,0x29,0x34,0x24             #movaps %xmm6,(%rsp)
 867         .byte   0x0f,0x29,0x7c,0x24,0x10        #movdqa %xmm7,0x10(%rsp)
 868 ___
 869 $code.=<<___;
 870         mov     $idx,%r11
 871         shr     \$`log($N/8)/log(2)`,$idx
 872         and     \$`$N/8-1`,%r11
 873         not     $idx
 874         lea     .Lmagic_masks(%rip),%rax
 875         and     \$`2**5/($N/8)-1`,$idx  # 5 is "window size"
 876         lea     96($tbl,%r11,8),$tbl    # pointer within 1st cache line
 877         movq    0(%rax,$idx,8),%xmm4    # set of masks denoting which
 878         movq    8(%rax,$idx,8),%xmm5    # cache line contains element
 879         movq    16(%rax,$idx,8),%xmm6   # denoted by 7th argument
 880         movq    24(%rax,$idx,8),%xmm7
 881         jmp     .Lgather
 882 .align  16
 883 .Lgather:
 884         movq    `0*$STRIDE/4-96`($tbl),%xmm0
 885         movq    `1*$STRIDE/4-96`($tbl),%xmm1
 886         pand    %xmm4,%xmm0
 887         movq    `2*$STRIDE/4-96`($tbl),%xmm2
 888         pand    %xmm5,%xmm1
 889         movq    `3*$STRIDE/4-96`($tbl),%xmm3
 890         pand    %xmm6,%xmm2
 891         por     %xmm1,%xmm0
 892         pand    %xmm7,%xmm3
 893         por     %xmm2,%xmm0
 894         lea     $STRIDE($tbl),$tbl
 895         por     %xmm3,%xmm0
 896
 897         movq    %xmm0,($out)            # m0=bp[0]
 898         lea     8($out),$out
 899         sub     \$1,$num
 900         jnz     .Lgather
 901 ___
 902 $code.=<<___ if ($win64);
 903         movaps  %xmm6,(%rsp)
 904         movaps  %xmm7,0x10(%rsp)
 905         lea     0x28(%rsp),%rsp
 906 ___
 907 $code.=<<___;
 908         ret
 909 .LSEH_end_bn_gather5:
 910 .size   bn_gather5,.-bn_gather5
 911 ___
 912 }
 913 $code.=<<___;
 914 .align  64
 915 .Lmagic_masks:
 916         .long   0,0, 0,0, 0,0, -1,-1
 917         .long   0,0, 0,0, 0,0,  0,0
 918 .asciz  "Montgomery Multiplication with scatter/gather for x86_64, CRYPTOGAMS by <appro\@openssl.org>"
 919 ___
 920
 921 # EXCEPTION_DISPOSITION handler (EXCEPTION_RECORD *rec,ULONG64 frame,
 922 #               CONTEXT *context,DISPATCHER_CONTEXT *disp)
 923 if ($win64) {
 924 $rec="%rcx";
 925 $frame="%rdx";
 926 $context="%r8";
 927 $disp="%r9";
 928
 929 $code.=<<___;
 930 .extern __imp_RtlVirtualUnwind
 931 .type   mul_handler,\@abi-omnipotent
 932 .align  16
 933 mul_handler:
 934         push    %rsi
 935         push    %rdi
 936         push    %rbx
 937         push    %rbp
 938         push    %r12
 939         push    %r13
 940         push    %r14
 941         push    %r15
 942         pushfq
 943         sub     \$64,%rsp
 944
 945         mov     120($context),%rax      # pull context->Rax
 946         mov     248($context),%rbx      # pull context->Rip
 947
 948         mov     8($disp),%rsi           # disp->ImageBase
 949         mov     56($disp),%r11          # disp->HandlerData
 950
 951         mov     0(%r11),%r10d           # HandlerData[0]
 952         lea     (%rsi,%r10),%r10        # end of prologue label
 953         cmp     %r10,%rbx               # context->Rip<end of prologue label
 954         jb      .Lcommon_seh_tail
 955
 956         lea     `40+48`(%rax),%rax
 957
 958         mov     4(%r11),%r10d           # HandlerData[1]
 959         lea     (%rsi,%r10),%r10        # end of alloca label
 960         cmp     %r10,%rbx               # context->Rip<end of alloca label
 961         jb      .Lcommon_seh_tail
 962
 963         mov     152($context),%rax      # pull context->Rsp
 964
 965         mov     8(%r11),%r10d           # HandlerData[2]
 966         lea     (%rsi,%r10),%r10        # epilogue label
 967         cmp     %r10,%rbx               # context->Rip>=epilogue label
 968         jae     .Lcommon_seh_tail
 969
 970         mov     192($context),%r10      # pull $num
 971         mov     8(%rax,%r10,8),%rax     # pull saved stack pointer
 972
 973         movaps  (%rax),%xmm0
 974         movaps  16(%rax),%xmm1
 975         lea     `40+48`(%rax),%rax
 976
 977         mov     -8(%rax),%rbx
 978         mov     -16(%rax),%rbp
 979         mov     -24(%rax),%r12
 980         mov     -32(%rax),%r13
 981         mov     -40(%rax),%r14
 982         mov     -48(%rax),%r15
 983         mov     %rbx,144($context)      # restore context->Rbx
 984         mov     %rbp,160($context)      # restore context->Rbp
 985         mov     %r12,216($context)      # restore context->R12
 986         mov     %r13,224($context)      # restore context->R13
 987         mov     %r14,232($context)      # restore context->R14
 988         mov     %r15,240($context)      # restore context->R15
 989         movups  %xmm0,512($context)     # restore context->Xmm6
 990         movups  %xmm1,528($context)     # restore context->Xmm7
 991
 992 .Lcommon_seh_tail:
 993         mov     8(%rax),%rdi
 994         mov     16(%rax),%rsi
 995         mov     %rax,152($context)      # restore context->Rsp
 996         mov     %rsi,168($context)      # restore context->Rsi
 997         mov     %rdi,176($context)      # restore context->Rdi
 998
 999         mov     40($disp),%rdi          # disp->ContextRecord
1000         mov     $context,%rsi           # context
1001         mov     \$154,%ecx              # sizeof(CONTEXT)
1002         .long   0xa548f3fc              # cld; rep movsq
1003
1004         mov     $disp,%rsi
1005         xor     %rcx,%rcx               # arg1, UNW_FLAG_NHANDLER
1006         mov     8(%rsi),%rdx            # arg2, disp->ImageBase
1007         mov     0(%rsi),%r8             # arg3, disp->ControlPc
1008         mov     16(%rsi),%r9            # arg4, disp->FunctionEntry
1009         mov     40(%rsi),%r10           # disp->ContextRecord
1010         lea     56(%rsi),%r11           # &disp->HandlerData
1011         lea     24(%rsi),%r12           # &disp->EstablisherFrame
1012         mov     %r10,32(%rsp)           # arg5
1013         mov     %r11,40(%rsp)           # arg6
1014         mov     %r12,48(%rsp)           # arg7
1015         mov     %rcx,56(%rsp)           # arg8, (NULL)
1016         call    *__imp_RtlVirtualUnwind(%rip)
1017
1018         mov     \$1,%eax                # ExceptionContinueSearch
1019         add     \$64,%rsp
1020         popfq
1021         pop     %r15
1022         pop     %r14
1023         pop     %r13
1024         pop     %r12
1025         pop     %rbp
1026         pop     %rbx
1027         pop     %rdi
1028         pop     %rsi
1029         ret
1030 .size   mul_handler,.-mul_handler
1031
1032 .section        .pdata
1033 .align  4
1034         .rva    .LSEH_begin_bn_mul_mont_gather5
1035         .rva    .LSEH_end_bn_mul_mont_gather5
1036         .rva    .LSEH_info_bn_mul_mont_gather5
1037
1038         .rva    .LSEH_begin_bn_mul4x_mont_gather5
1039         .rva    .LSEH_end_bn_mul4x_mont_gather5
1040         .rva    .LSEH_info_bn_mul4x_mont_gather5
1041
1042         .rva    .LSEH_begin_bn_gather5
1043         .rva    .LSEH_end_bn_gather5
1044         .rva    .LSEH_info_bn_gather5
1045
1046 .section        .xdata
1047 .align  8
1048 .LSEH_info_bn_mul_mont_gather5:
1049         .byte   9,0,0,0
1050         .rva    mul_handler
1051         .rva    .Lmul_alloca,.Lmul_body,.Lmul_epilogue          # HandlerData[]
1052 .align  8
1053 .LSEH_info_bn_mul4x_mont_gather5:
1054         .byte   9,0,0,0
1055         .rva    mul_handler
1056         .rva    .Lmul4x_alloca,.Lmul4x_body,.Lmul4x_epilogue    # HandlerData[]
1057 .align  8
1058 .LSEH_info_bn_gather5:
1059         .byte   0x01,0x0d,0x05,0x00
1060         .byte   0x0d,0x78,0x01,0x00     #movaps 0x10(rsp),xmm7
1061         .byte   0x08,0x68,0x00,0x00     #movaps (rsp),xmm6
1062         .byte   0x04,0x42,0x00,0x00     #sub    rsp,0x28
1063 .align  8
1064 ___
1065 }
1066
1067 $code =~ s/\`([^\`]*)\`/eval($1)/gem;
1068
1069 print $code;
1070 close STDOUT;