crypto/bn/asm/x86_64-mont.pl

   1 #!/usr/bin/env perl
   2
   3 # ====================================================================
   4 # Written by Andy Polyakov <appro@fy.chalmers.se> 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 # October 2005.
  11 #
  12 # Montgomery multiplication routine for x86_64. While it gives modest
  13 # 9% improvement of rsa4096 sign on Opteron, rsa512 sign runs more
  14 # than twice, >2x, as fast. Most common rsa1024 sign is improved by
  15 # respectful 50%. It remains to be seen if loop unrolling and
  16 # dedicated squaring routine can provide further improvement...
  17
  18 # July 2011.
  19 #
  20 # Add dedicated squaring procedure. Performance improvement varies
  21 # from platform to platform, but in average it's ~5%/15%/25%/33%
  22 # for 512-/1024-/2048-/4096-bit RSA *sign* benchmarks respectively.
  23
  24 $flavour = shift;
  25 $output  = shift;
  26 if ($flavour =~ /\./) { $output = $flavour; undef $flavour; }
  27
  28 $win64=0; $win64=1 if ($flavour =~ /[nm]asm|mingw64/ || $output =~ /\.asm$/);
  29
  30 $0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
  31 ( $xlate="${dir}x86_64-xlate.pl" and -f $xlate ) or
  32 ( $xlate="${dir}../../perlasm/x86_64-xlate.pl" and -f $xlate) or
  33 die "can't locate x86_64-xlate.pl";
  34
  35 open STDOUT,"| $^X $xlate $flavour $output";
  36
  37 # int bn_mul_mont(
  38 $rp="%rdi";     # BN_ULONG *rp,
  39 $ap="%rsi";     # const BN_ULONG *ap,
  40 $bp="%rdx";     # const BN_ULONG *bp,
  41 $np="%rcx";     # const BN_ULONG *np,
  42 $n0="%r8";      # const BN_ULONG *n0,
  43 $num="%r9";     # int num);
  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
  56 .type   bn_mul_mont,\@function,6
  57 .align  16
  58 bn_mul_mont:
  59         cmp     $ap,$bp
  60         jne     .Lmul_enter
  61         test    \$1,${num}d
  62         jnz     .Lmul_enter
  63         cmp     \$4,${num}d
  64         jb      .Lmul_enter
  65         jmp     __bn_sqr_enter
  66
  67 .align  16
  68 .Lmul_enter:
  69         push    %rbx
  70         push    %rbp
  71         push    %r12
  72         push    %r13
  73         push    %r14
  74         push    %r15
  75
  76         mov     ${num}d,${num}d
  77         lea     2($num),%r10
  78         mov     %rsp,%r11
  79         neg     %r10
  80         lea     (%rsp,%r10,8),%rsp      # tp=alloca(8*(num+2))
  81         and     \$-1024,%rsp            # minimize TLB usage
  82
  83         mov     %r11,8(%rsp,$num,8)     # tp[num+1]=%rsp
  84 .Lprologue:
  85         mov     $bp,%r12                # reassign $bp
  86 ___
  87                 $bp="%r12";
  88 $code.=<<___;
  89         mov     ($n0),$n0               # pull n0[0] value
  90
  91         xor     $i,$i                   # i=0
  92         xor     $j,$j                   # j=0
  93
  94         mov     ($bp),$m0               # m0=bp[0]
  95         mov     ($ap),%rax
  96         mulq    $m0                     # ap[0]*bp[0]
  97         mov     %rax,$lo0
  98         mov     %rdx,$hi0
  99
 100         imulq   $n0,%rax                # "tp[0]"*n0
 101         mov     %rax,$m1
 102
 103         mulq    ($np)                   # np[0]*m1
 104         add     $lo0,%rax               # discarded
 105         adc     \$0,%rdx
 106         mov     %rdx,$hi1
 107
 108         lea     1($j),$j                # j++
 109 .L1st:
 110         mov     ($ap,$j,8),%rax
 111         mulq    $m0                     # ap[j]*bp[0]
 112         add     $hi0,%rax
 113         adc     \$0,%rdx
 114         mov     %rax,$lo0
 115         mov     ($np,$j,8),%rax
 116         mov     %rdx,$hi0
 117
 118         mulq    $m1                     # np[j]*m1
 119         add     $hi1,%rax
 120         lea     1($j),$j                # j++
 121         adc     \$0,%rdx
 122         add     $lo0,%rax               # np[j]*m1+ap[j]*bp[0]
 123         adc     \$0,%rdx
 124         mov     %rax,-16(%rsp,$j,8)     # tp[j-1]
 125         cmp     $num,$j
 126         mov     %rdx,$hi1
 127         jl      .L1st
 128
 129         xor     %rdx,%rdx
 130         add     $hi0,$hi1
 131         adc     \$0,%rdx
 132         mov     $hi1,-8(%rsp,$num,8)
 133         mov     %rdx,(%rsp,$num,8)      # store upmost overflow bit
 134
 135         lea     1($i),$i                # i++
 136 .align  4
 137 .Louter:
 138         xor     $j,$j                   # j=0
 139
 140         mov     ($bp,$i,8),$m0          # m0=bp[i]
 141         mov     ($ap),%rax              # ap[0]
 142         mulq    $m0                     # ap[0]*bp[i]
 143         add     (%rsp),%rax             # ap[0]*bp[i]+tp[0]
 144         adc     \$0,%rdx
 145         mov     %rax,$lo0
 146         mov     %rdx,$hi0
 147
 148         imulq   $n0,%rax                # tp[0]*n0
 149         mov     %rax,$m1
 150
 151         mulq    ($np,$j,8)              # np[0]*m1
 152         add     $lo0,%rax               # discarded
 153         mov     8(%rsp),$lo0            # tp[1]
 154         adc     \$0,%rdx
 155         mov     %rdx,$hi1
 156
 157         lea     1($j),$j                # j++
 158         jmp     .Linner
 159 .align  16
 160 .Linner:
 161         mov     ($ap,$j,8),%rax
 162         mulq    $m0                     # ap[j]*bp[i]
 163         add     $hi0,%rax
 164         adc     \$0,%rdx
 165         add     %rax,$lo0               # ap[j]*bp[i]+tp[j]
 166         mov     ($np,$j,8),%rax
 167         adc     \$0,%rdx
 168         mov     %rdx,$hi0
 169
 170         mulq    $m1                     # np[j]*m1
 171         add     $hi1,%rax
 172         lea     1($j),$j                # j++
 173         adc     \$0,%rdx
 174         add     $lo0,%rax               # np[j]*m1+ap[j]*bp[i]+tp[j]
 175         adc     \$0,%rdx
 176         mov     (%rsp,$j,8),$lo0
 177         cmp     $num,$j
 178         mov     %rax,-16(%rsp,$j,8)     # tp[j-1]
 179         mov     %rdx,$hi1
 180         jl      .Linner
 181
 182         xor     %rdx,%rdx
 183         add     $hi0,$hi1
 184         adc     \$0,%rdx
 185         add     $lo0,$hi1               # pull upmost overflow bit
 186         adc     \$0,%rdx
 187         mov     $hi1,-8(%rsp,$num,8)
 188         mov     %rdx,(%rsp,$num,8)      # store upmost overflow bit
 189
 190         lea     1($i),$i                # i++
 191         cmp     $num,$i
 192         jl      .Louter
 193
 194         lea     (%rsp),$ap              # borrow ap for tp
 195         lea     -1($num),$j             # j=num-1
 196
 197         mov     ($ap),%rax              # tp[0]
 198         xor     $i,$i                   # i=0 and clear CF!
 199         jmp     .Lsub
 200 .align  16
 201 .Lsub:  sbb     ($np,$i,8),%rax
 202         mov     %rax,($rp,$i,8)         # rp[i]=tp[i]-np[i]
 203         dec     $j                      # doesn't affect CF!
 204         mov     8($ap,$i,8),%rax        # tp[i+1]
 205         lea     1($i),$i                # i++
 206         jge     .Lsub
 207
 208         sbb     \$0,%rax                # handle upmost overflow bit
 209         and     %rax,$ap
 210         not     %rax
 211         mov     $rp,$np
 212         and     %rax,$np
 213         lea     -1($num),$j
 214         or      $np,$ap                 # ap=borrow?tp:rp
 215 .align  16
 216 .Lcopy:                                 # copy or in-place refresh
 217         mov     ($ap,$j,8),%rax
 218         mov     %rax,($rp,$j,8)         # rp[i]=tp[i]
 219         mov     $i,(%rsp,$j,8)          # zap temporary vector
 220         dec     $j
 221         jge     .Lcopy
 222
 223         mov     8(%rsp,$num,8),%rsi     # restore %rsp
 224         mov     \$1,%rax
 225         mov     (%rsi),%r15
 226         mov     8(%rsi),%r14
 227         mov     16(%rsi),%r13
 228         mov     24(%rsi),%r12
 229         mov     32(%rsi),%rbp
 230         mov     40(%rsi),%rbx
 231         lea     48(%rsi),%rsp
 232 .Lepilogue:
 233         ret
 234 .size   bn_mul_mont,.-bn_mul_mont
 235 ___
 236 \f{{{
 237 ######################################################################
 238 # void bn_sqr_mont(
 239 my $rptr="%rdi";        # const BN_ULONG *rptr,
 240 my $aptr="%rsi";        # const BN_ULONG *aptr,
 241 my $bptr="%rdx";        # not used
 242 my $nptr="%rcx";        # const BN_ULONG *nptr,
 243 my $n0  ="%r8";         # const BN_ULONG *n0);
 244 my $num ="%r9";         # int num, has to be even and not less than 4
 245
 246 my ($i,$j,$tptr)=("%rbp","%rcx",$rptr);
 247 my @A0=("%r10","%r11");
 248 my @A1=("%r12","%r13");
 249 my ($a0,$a1,$ai)=("%r14","%r15","%rbx");
 250
 251 $code.=<<___;
 252 .type   bn_sqr_mont,\@function,5
 253 .align  16
 254 bn_sqr_mont:
 255 __bn_sqr_enter:
 256         push    %rbx
 257         push    %rbp
 258         push    %r12
 259         push    %r13
 260         push    %r14
 261         push    %r15
 262
 263         shl     \$3,${num}d             # convert $num to bytes
 264         xor     %r10,%r10
 265         mov     %rsp,%r11               # put aside %rsp
 266         sub     $num,%r10               # -$num
 267         mov     ($n0),$n0               # *n0
 268         lea     -72(%rsp,%r10,2),%rsp   # alloca(frame+2*$num)
 269         and     \$-1024,%rsp            # minimize TLB usage
 270         ##############################################################
 271         # Stack layout
 272         #
 273         # +0    saved $num, used in reduction section
 274         # +8    &t[2*$num], used in reduction section
 275         # +32   saved $rptr
 276         # +40   saved $nptr
 277         # +48   saved *n0
 278         # +56   saved %rsp
 279         # +64   t[2*$num]
 280         #
 281         mov     $rptr,32(%rsp)          # save $rptr
 282         mov     $nptr,40(%rsp)
 283         mov     $n0,  48(%rsp)
 284         mov     %r11, 56(%rsp)          # save original %rsp
 285 .Lsqr_body:
 286         ##############################################################
 287         # Squaring part:
 288         #
 289         # a) multiply-n-add everything but a[i]*a[i];
 290         # b) shift result of a) by 1 to the left and accumulate
 291         #    a[i]*a[i] products;
 292         #
 293         lea     16(%r10),$i             # $i=-($num-16)
 294         lea     ($aptr,$num),$aptr      # end of a[] buffer, ($aptr,$i)=&ap[2]
 295
 296         mov     $num,$j                 # $j=$num
 297         pxor    %xmm0,%xmm0
 298         lea     64(%rsp),$tptr
 299 .Lbzero:                                # clear t[$num]
 300         movdqa  %xmm0,($tptr)
 301         lea     16($tptr),$tptr
 302         sub     \$16,$j
 303         jnz     .Lbzero
 304         jmp     .Lsqr_outer
 305
 306 .align  16
 307 .Lsqr_outer:                            # comments apply to $num==4 case
 308         mov     -16($aptr,$i),$a0       # a[0]
 309         lea     64(%rsp,$num,2),$tptr   # end of tp[] buffer, &tp[2*$num]
 310         mov     -8($aptr,$i),%rax       # a[1]
 311         lea     -16($tptr,$i),$tptr     # end of tp[] window, &tp[2*$num-"$i"]
 312         mov     ($aptr,$i),$ai          # a[2]
 313         mov     %rax,$a1
 314
 315         mov     -8($tptr,$i),$A0[0]     # t[1]
 316         xor     $A0[1],$A0[1]
 317         mul     $a0                     # a[1]*a[0]
 318         add     %rax,$A0[0]             # a[1]*a[0]+t[1]
 319          mov    $ai,%rax                # a[2]
 320         adc     %rdx,$A0[1]
 321         mov     $A0[0],-8($tptr,$i)     # t[1]
 322
 323         xor     $A0[0],$A0[0]
 324         add     ($tptr,$i),$A0[1]       # a[2]*a[0]+t[2]
 325         adc     \$0,$A0[0]
 326         mul     $a0                     # a[2]*a[0]
 327         add     %rax,$A0[1]
 328          mov    $ai,%rax
 329         adc     %rdx,$A0[0]
 330         mov     $A0[1],($tptr,$i)       # t[2]
 331
 332         lea     ($i),$j                 # j=-16
 333         xor     $A1[0],$A1[0]
 334         jmp     .Lsqr_inner
 335
 336 .align  16
 337 .Lsqr_inner:
 338          mov    8($aptr,$j),$ai         # a[3]
 339         xor     $A1[1],$A1[1]
 340         add     8($tptr,$j),$A1[0]
 341         adc     \$0,$A1[1]
 342         mul     $a1                     # a[2]*a[1]
 343         add     %rax,$A1[0]             # a[2]*a[1]+t[3]
 344          mov    $ai,%rax
 345         adc     %rdx,$A1[1]
 346
 347         xor     $A0[1],$A0[1]
 348         add     $A1[0],$A0[0]
 349         adc     \$0,$A0[1]
 350         mul     $a0                     # a[3]*a[0]
 351         add     %rax,$A0[0]             # a[3]*a[0]+a[2]*a[1]+t[3]
 352          mov    $ai,%rax
 353         adc     %rdx,$A0[1]
 354         mov     $A0[0],8($tptr,$j)      # t[3]
 355
 356         add     \$16,$j
 357         jz      .Lsqr_inner_done
 358
 359          mov    ($aptr,$j),$ai          # a[4]
 360         xor     $A1[0],$A1[0]
 361         add     ($tptr,$j),$A1[1]
 362         adc     \$0,$A1[0]
 363         mul     $a1                     # a[3]*a[1]
 364         add     %rax,$A1[1]             # a[3]*a[1]+t[4]
 365          mov    $ai,%rax
 366         adc     %rdx,$A1[0]
 367
 368         xor     $A0[0],$A0[0]
 369         add     $A1[1],$A0[1]
 370         adc     \$0,$A0[0]
 371         mul     $a0                     # a[4]*a[0]
 372         add     %rax,$A0[1]             # a[4]*a[0]+a[3]*a[1]+t[4]
 373          mov    $ai,%rax                # a[3]
 374         adc     %rdx,$A0[0]
 375         mov     $A0[1],($tptr,$j)       # t[4]
 376         jmp     .Lsqr_inner
 377
 378 .align  16
 379 .Lsqr_inner_done:
 380         xor     $A1[0],$A1[0]
 381         add     $A0[1],$A1[1]
 382         adc     \$0,$A1[0]
 383         mul     $a1                     # a[3]*a[1]
 384         add     %rax,$A1[1]
 385          mov    -16($aptr),%rax         # a[2]
 386         adc     %rdx,$A1[0]
 387
 388         mov     $A1[1],($tptr)          # t[4]
 389         mov     $A1[0],8($tptr)         # t[5]
 390
 391         add     \$16,$i
 392         jnz     .Lsqr_outer
 393
 394         mul     $ai                     # a[2]*a[3]
 395 ___
 396 {
 397 my ($shift,$carry)=($a0,$a1);
 398 $code.=<<___;
 399          add    \$8,$i
 400          xor    $shift,$shift
 401          sub    $num,$i                 # $i=8-$num
 402          xor    $carry,$carry
 403
 404         add     $A1[0],%rax             # t[5]
 405         adc     \$0,%rdx
 406         mov     %rax,8($tptr)           # t[5]
 407         mov     %rdx,16($tptr)          # t[6]
 408         mov     $carry,24($tptr)        # t[7]
 409
 410          mov    -8($aptr,$i),%rax       # a[0]
 411         lea     64(%rsp,$num,2),$tptr
 412          mov    -16($tptr,$i,2),$A0[0]  # t[0]
 413          mov    -8($tptr,$i,2),$A0[1]   # t[1]
 414         jmp     .Lsqr_shift_n_add
 415
 416 .align  16
 417 .Lsqr_shift_n_add:
 418         lea     ($shift,$A0[0],2),$A1[0]# t[2*i]<<1 | shift
 419         shr     \$63,$A0[0]
 420         lea     (,$A0[1],2),$A1[1]      # t[2*i+1]<<1 |
 421         shr     \$63,$A0[1]
 422         or      $A0[0],$A1[1]           # | t[2*i]>>63
 423          mov    0($tptr,$i,2),$A0[0]    # t[2*i+2]      # prefetch
 424         mov     $A0[1],$shift           # shift=t[2*i+1]>>63
 425         mul     %rax                    # a[i]*a[i]
 426          mov    8($tptr,$i,2),$A0[1]    # t[2*i+2+1]    # prefetch
 427         neg     $carry                  # mov $carry,cf
 428         adc     %rax,$A1[0]
 429          mov    0($aptr,$i),%rax        # a[i+1]        # prefetch
 430         adc     %rdx,$A1[1]
 431         mov     $A1[0],-16($tptr,$i,2)
 432         sbb     $carry,$carry           # mov cf,$carry
 433         mov     $A1[1],-8($tptr,$i,2)
 434         add     \$8,$i
 435         jnz     .Lsqr_shift_n_add
 436
 437         lea     ($shift,$A0[0],2),$A1[0]# t[2*i]<<1|shift
 438         shr     \$63,$A0[0]
 439         lea     (,$A0[1],2),$A1[1]      # t[2*i+1]<<1 |
 440         shr     \$63,$A0[1]
 441         or      $A0[0],$A1[1]           # | t[2*i]>>63
 442         mul     %rax                    # a[i]*a[i]
 443         neg     $carry                  # mov $carry,cf
 444         adc     %rax,$A1[0]
 445         adc     %rdx,$A1[1]
 446         mov     $A1[0],-16($tptr)
 447         mov     $A1[1],-8($tptr)
 448 ___
 449 }\f
 450 ##############################################################
 451 # Montgomery reduction part, "word-by-word" algorithm.
 452 #
 453 {
 454 my ($topbit,$nptr)=("%rbp",$aptr);
 455 my ($m0,$m1)=($a0,$a1);
 456 my @Ni=("%rbx","%r9");
 457 $code.=<<___;
 458         mov     40(%rsp),$nptr          # restore $nptr
 459         xor     $j,$j
 460         mov     $num,0(%rsp)            # save $num
 461         sub     $num,$j                 # $j=-$num
 462          mov    64(%rsp),$A0[0]         # t[0]          # modsched #
 463          mov    $n0,$m0                 #               # modsched #
 464         lea     64(%rsp,$num,2),%rax    # end of t[] buffer
 465         lea     64(%rsp,$num),$tptr     # end of t[] window
 466         mov     %rax,8(%rsp)            # save end of t[] buffer
 467         lea     ($nptr,$num),$nptr      # end of n[] buffer
 468         xor     $topbit,$topbit         # $topbit=0
 469
 470         mov     0($nptr,$j),%rax        # n[0]          # modsched #
 471         mov     8($nptr,$j),$Ni[1]      # n[1]          # modsched #
 472          imulq  $A0[0],$m0              # m0=t[0]*n0    # modsched #
 473          mov    %rax,$Ni[0]             #               # modsched #
 474         jmp     .Lmont_outer
 475
 476 .align  16
 477 .Lmont_outer:
 478         xor     $A0[1],$A0[1]
 479         mul     $m0                     # n[0]*m0
 480         add     %rax,$A0[0]             # n[0]*m0+t[0]
 481          mov    $Ni[1],%rax
 482         adc     %rdx,$A0[1]
 483         mov     $n0,$m1
 484
 485         xor     $A0[0],$A0[0]
 486         add     8($tptr,$j),$A0[1]
 487         adc     \$0,$A0[0]
 488         mul     $m0                     # n[1]*m0
 489         add     %rax,$A0[1]             # n[1]*m0+t[1]
 490          mov    $Ni[0],%rax
 491         adc     %rdx,$A0[0]
 492
 493         imulq   $A0[1],$m1
 494         lea     16($j),$j
 495         jmp     .Lmont_inner
 496
 497 .align  16
 498 .Lmont_inner:
 499         mov     ($nptr,$j),$Ni[0]       # n[2]
 500         xor     $A1[1],$A1[1]
 501         add     $A0[1],$A1[0]
 502         adc     \$0,$A1[1]
 503         mul     $m1                     # n[0]*m1
 504         add     %rax,$A1[0]             # n[0]*m1+"t[1]"
 505          mov    $Ni[0],%rax
 506         adc     %rdx,$A1[1]
 507         mov     $A1[0],-8($tptr,$j)     # "t[1]"
 508
 509         xor     $A0[1],$A0[1]
 510         add     ($tptr,$j),$A0[0]
 511         adc     \$0,$A0[1]
 512         mul     $m0                     # n[2]*m0
 513         add     %rax,$A0[0]             # n[2]*m0+t[2]
 514          mov    $Ni[1],%rax
 515         adc     %rdx,$A0[1]
 516
 517         mov     8($nptr,$j),$Ni[1]      # n[3]
 518         xor     $A1[0],$A1[0]
 519         add     $A0[0],$A1[1]
 520         adc     \$0,$A1[0]
 521         mul     $m1                     # n[1]*m1
 522         add     %rax,$A1[1]             # n[1]*m1+"t[2]"
 523          mov    $Ni[1],%rax
 524         adc     %rdx,$A1[0]
 525         mov     $A1[1],($tptr,$j)       # "t[2]"
 526
 527         xor     $A0[0],$A0[0]
 528         add     8($tptr,$j),$A0[1]
 529         lea     16($j),$j
 530         adc     \$0,$A0[0]
 531         mul     $m0                     # n[3]*m0
 532         add     %rax,$A0[1]             # n[3]*m0+t[3]
 533          mov    $Ni[0],%rax
 534         adc     %rdx,$A0[0]
 535         cmp     \$0,$j
 536         jne     .Lmont_inner
 537
 538          sub    0(%rsp),$j              # $j=-$num      # modsched #
 539          mov    $n0,$m0                 #               # modsched #
 540
 541         xor     $A1[1],$A1[1]
 542         add     $A0[1],$A1[0]
 543         adc     \$0,$A1[1]
 544         mul     $m1                     # n[2]*m1
 545         add     %rax,$A1[0]             # n[2]*m1+"t[3]"
 546         mov     $Ni[1],%rax
 547         adc     %rdx,$A1[1]
 548         mov     $A1[0],-8($tptr)        # "t[3]"
 549
 550         xor     $A0[1],$A0[1]
 551         add     ($tptr),$A0[0]          # +t[4]
 552         adc     \$0,$A0[1]
 553          mov    0($nptr,$j),$Ni[0]      # n[0]          # modsched #
 554         add     $topbit,$A0[0]
 555         adc     \$0,$A0[1]
 556
 557          imulq  16($tptr,$j),$m0        # m0=t[0]*n0    # modsched #
 558         xor     $A1[0],$A1[0]
 559          mov    8($nptr,$j),$Ni[1]      # n[1]          # modsched #
 560         add     $A0[0],$A1[1]
 561          mov    16($tptr,$j),$A0[0]     # t[0]          # modsched #
 562         adc     \$0,$A1[0]
 563         mul     $m1                     # n[3]*m1
 564         add     %rax,$A1[1]             # n[3]*m1+"t[4]"
 565          mov    $Ni[0],%rax             #               # modsched #
 566         adc     %rdx,$A1[0]
 567         mov     $A1[1],($tptr)          # "t[4]"
 568
 569         xor     $topbit,$topbit
 570         add     8($tptr),$A1[0]         # +t[5]
 571         adc     $topbit,$topbit
 572         add     $A0[1],$A1[0]
 573         lea     16($tptr),$tptr         # "t[$num]>>128"
 574         adc     \$0,$topbit
 575         mov     $A1[0],-8($tptr)        # "t[5]"
 576         cmp     8(%rsp),$tptr           # are we done?
 577         jb      .Lmont_outer
 578
 579         mov     0(%rsp),$num            # restore $num
 580         mov     $topbit,($tptr)         # save $topbit
 581 ___
 582 }\f
 583 ##############################################################
 584 # Post-condition, 2x unrolled copy from bn_mul_mont
 585 #
 586 {
 587 my ($tptr,$nptr)=("%rbx",$aptr);
 588 $code.=<<___;
 589         lea     64(%rsp,$num),$tptr     # upper half of t[2*$num] holds result
 590         shr     \$4,$num                # num/2
 591         mov     32(%rsp),$rptr          # restore $rptr
 592         mov     40(%rsp),$nptr          # restore $nptr
 593         lea     -1($num),$j             # j=num/2-1
 594
 595         mov     ($tptr),%rax            # tp[0]
 596         xor     $i,$i                   # i=0 and clear CF!
 597         jmp     .Lsqr_sub
 598 .align  16
 599 .Lsqr_sub:
 600         mov     8($tptr,$i,8),%rdx
 601         sbb     0($nptr,$i,8),%rax
 602         sbb     8($nptr,$i,8),%rdx
 603         mov     %rax,0($rptr,$i,8)      # rp[i]=tp[i]-np[i]
 604         mov     %rdx,8($rptr,$i,8)      # rp[i]=tp[i]-np[i]
 605         mov     16($tptr,$i,8),%rax     # tp[i+1]
 606         lea     2($i),$i                # i++
 607         dec     $j                      # doesn't affect CF!
 608         jge     .Lsqr_sub
 609
 610         sbb     \$0,%rax                # handle upmost overflow bit
 611         xor     $i,$i                   # i=0
 612         and     %rax,$tptr
 613         not     %rax
 614         mov     $rptr,$nptr
 615         and     %rax,$nptr
 616         lea     -1($num),$j
 617         or      $nptr,$tptr             # tp=borrow?tp:rp
 618
 619         lea     64(%rsp,$num,8),$nptr
 620         lea     ($nptr,$num,8),$nptr
 621         jmp     .Lsqr_copy
 622 .align  16
 623 .Lsqr_copy:                             # copy or in-place refresh
 624         movdqu  ($tptr,$i),%xmm1
 625         movdqa  %xmm0,64(%rsp,$i)       # zap lower half of temporary vector
 626         movdqa  %xmm0,($nptr,$i)        # zap upper half of temporary vector
 627         movdqu  %xmm1,($rptr,$i)
 628         lea     16($i),$i
 629         dec     $j
 630         jge     .Lsqr_copy
 631 ___
 632 }
 633 $code.=<<___;
 634         mov     56(%rsp),%rsi           # restore %rsp
 635         mov     \$1,%rax
 636         mov     0(%rsi),%r15
 637         mov     8(%rsi),%r14
 638         mov     16(%rsi),%r13
 639         mov     24(%rsi),%r12
 640         mov     32(%rsi),%rbp
 641         mov     40(%rsi),%rbx
 642         lea     48(%rsi),%rsp
 643 .Lsqr_epilogue:
 644         ret
 645 .size   bn_sqr_mont,.-bn_sqr_mont
 646 ___
 647 }}}
 648 $code.=<<___;
 649 .asciz  "Montgomery Multiplication for x86_64, CRYPTOGAMS by <appro\@openssl.org>"
 650 .align  16
 651 ___
 652
 653 # EXCEPTION_DISPOSITION handler (EXCEPTION_RECORD *rec,ULONG64 frame,
 654 #               CONTEXT *context,DISPATCHER_CONTEXT *disp)
 655 if ($win64) {
 656 $rec="%rcx";
 657 $frame="%rdx";
 658 $context="%r8";
 659 $disp="%r9";
 660
 661 $code.=<<___;
 662 .extern __imp_RtlVirtualUnwind
 663 .type   mul_handler,\@abi-omnipotent
 664 .align  16
 665 mul_handler:
 666         push    %rsi
 667         push    %rdi
 668         push    %rbx
 669         push    %rbp
 670         push    %r12
 671         push    %r13
 672         push    %r14
 673         push    %r15
 674         pushfq
 675         sub     \$64,%rsp
 676
 677         mov     120($context),%rax      # pull context->Rax
 678         mov     248($context),%rbx      # pull context->Rip
 679
 680         lea     .Lprologue(%rip),%r10
 681         cmp     %r10,%rbx               # context->Rip<.Lprologue
 682         jb      .Lcommon_seh_tail
 683
 684         mov     152($context),%rax      # pull context->Rsp
 685
 686         lea     .Lepilogue(%rip),%r10
 687         cmp     %r10,%rbx               # context->Rip>=.Lepilogue
 688         jae     .Lcommon_seh_tail
 689
 690         mov     192($context),%r10      # pull $num
 691         mov     8(%rax,%r10,8),%rax     # pull saved stack pointer
 692         lea     48(%rax),%rax
 693
 694         mov     -8(%rax),%rbx
 695         mov     -16(%rax),%rbp
 696         mov     -24(%rax),%r12
 697         mov     -32(%rax),%r13
 698         mov     -40(%rax),%r14
 699         mov     -48(%rax),%r15
 700         mov     %rbx,144($context)      # restore context->Rbx
 701         mov     %rbp,160($context)      # restore context->Rbp
 702         mov     %r12,216($context)      # restore context->R12
 703         mov     %r13,224($context)      # restore context->R13
 704         mov     %r14,232($context)      # restore context->R14
 705         mov     %r15,240($context)      # restore context->R15
 706
 707         jmp     .Lcommon_seh_tail
 708 .size   mul_handler,.-mul_handler
 709
 710 .type   sqr_handler,\@abi-omnipotent
 711 .align  16
 712 sqr_handler:
 713         push    %rsi
 714         push    %rdi
 715         push    %rbx
 716         push    %rbp
 717         push    %r12
 718         push    %r13
 719         push    %r14
 720         push    %r15
 721         pushfq
 722         sub     \$64,%rsp
 723
 724         mov     120($context),%rax      # pull context->Rax
 725         mov     248($context),%rbx      # pull context->Rip
 726
 727         lea     .Lsqr_body(%rip),%r10
 728         cmp     %r10,%rbx               # context->Rip<.Lsqr_body
 729         jb      .Lcommon_seh_tail
 730
 731         mov     152($context),%rax      # pull context->Rsp
 732
 733         lea     .Lsqr_epilogue(%rip),%r10
 734         cmp     %r10,%rbx               # context->Rip>=.Lsqr_epilogue
 735         jae     .Lcommon_seh_tail
 736
 737         mov     56(%rax),%rax           # pull saved stack pointer
 738         lea     48(%rax),%rax
 739
 740         mov     -8(%rax),%rbx
 741         mov     -16(%rax),%rbp
 742         mov     -24(%rax),%r12
 743         mov     -32(%rax),%r13
 744         mov     -40(%rax),%r14
 745         mov     -48(%rax),%r15
 746         mov     %rbx,144($context)      # restore context->Rbx
 747         mov     %rbp,160($context)      # restore context->Rbp
 748         mov     %r12,216($context)      # restore context->R12
 749         mov     %r13,224($context)      # restore context->R13
 750         mov     %r14,232($context)      # restore context->R14
 751         mov     %r15,240($context)      # restore context->R15
 752
 753 .Lcommon_seh_tail:
 754         mov     8(%rax),%rdi
 755         mov     16(%rax),%rsi
 756         mov     %rax,152($context)      # restore context->Rsp
 757         mov     %rsi,168($context)      # restore context->Rsi
 758         mov     %rdi,176($context)      # restore context->Rdi
 759
 760         mov     40($disp),%rdi          # disp->ContextRecord
 761         mov     $context,%rsi           # context
 762         mov     \$154,%ecx              # sizeof(CONTEXT)
 763         .long   0xa548f3fc              # cld; rep movsq
 764
 765         mov     $disp,%rsi
 766         xor     %rcx,%rcx               # arg1, UNW_FLAG_NHANDLER
 767         mov     8(%rsi),%rdx            # arg2, disp->ImageBase
 768         mov     0(%rsi),%r8             # arg3, disp->ControlPc
 769         mov     16(%rsi),%r9            # arg4, disp->FunctionEntry
 770         mov     40(%rsi),%r10           # disp->ContextRecord
 771         lea     56(%rsi),%r11           # &disp->HandlerData
 772         lea     24(%rsi),%r12           # &disp->EstablisherFrame
 773         mov     %r10,32(%rsp)           # arg5
 774         mov     %r11,40(%rsp)           # arg6
 775         mov     %r12,48(%rsp)           # arg7
 776         mov     %rcx,56(%rsp)           # arg8, (NULL)
 777         call    *__imp_RtlVirtualUnwind(%rip)
 778
 779         mov     \$1,%eax                # ExceptionContinueSearch
 780         add     \$64,%rsp
 781         popfq
 782         pop     %r15
 783         pop     %r14
 784         pop     %r13
 785         pop     %r12
 786         pop     %rbp
 787         pop     %rbx
 788         pop     %rdi
 789         pop     %rsi
 790         ret
 791 .size   sqr_handler,.-sqr_handler
 792
 793 .section        .pdata
 794 .align  4
 795         .rva    .LSEH_begin_bn_mul_mont
 796         .rva    .LSEH_end_bn_mul_mont
 797         .rva    .LSEH_info_bn_mul_mont
 798
 799         .rva    .LSEH_begin_bn_sqr_mont
 800         .rva    .LSEH_end_bn_sqr_mont
 801         .rva    .LSEH_info_bn_sqr_mont
 802
 803 .section        .xdata
 804 .align  8
 805 .LSEH_info_bn_mul_mont:
 806         .byte   9,0,0,0
 807         .rva    mul_handler
 808 .LSEH_info_bn_sqr_mont:
 809         .byte   9,0,0,0
 810         .rva    sqr_handler
 811 ___
 812 }
 813
 814 print $code;
 815 close STDOUT;