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 $flavour = shift;
  19 $output  = shift;
  20 if ($flavour =~ /\./) { $output = $flavour; undef $flavour; }
  21
  22 $win64=0; $win64=1 if ($flavour =~ /[nm]asm|mingw64/ || $output =~ /\.asm$/);
  23
  24 $0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
  25 ( $xlate="${dir}x86_64-xlate.pl" and -f $xlate ) or
  26 ( $xlate="${dir}../../perlasm/x86_64-xlate.pl" and -f $xlate) or
  27 die "can't locate x86_64-xlate.pl";
  28
  29 open STDOUT,"| $^X $xlate $flavour $output";
  30
  31 # int bn_mul_mont(
  32 $rp="%rdi";     # BN_ULONG *rp,
  33 $ap="%rsi";     # const BN_ULONG *ap,
  34 $bp="%rdx";     # const BN_ULONG *bp,
  35 $np="%rcx";     # const BN_ULONG *np,
  36 $n0="%r8";      # const BN_ULONG *n0,
  37 $num="%r9";     # int num);
  38 $lo0="%r10";
  39 $hi0="%r11";
  40 $bp="%r12";     # reassign $bp
  41 $hi1="%r13";
  42 $i="%r14";
  43 $j="%r15";
  44 $m0="%rbx";
  45 $m1="%rbp";
  46
  47 $code=<<___;
  48 .section .note.GNU-stack,"",\@progbits
  49 .text
  50
  51 .globl  bn_mul_mont
  52 .type   bn_mul_mont,\@function,6
  53 .align  16
  54 bn_mul_mont:
  55         push    %rbx
  56         push    %rbp
  57         push    %r12
  58         push    %r13
  59         push    %r14
  60         push    %r15
  61
  62         mov     ${num}d,${num}d
  63         lea     2($num),%r10
  64         mov     %rsp,%r11
  65         neg     %r10
  66         lea     (%rsp,%r10,8),%rsp      # tp=alloca(8*(num+2))
  67         and     \$-1024,%rsp            # minimize TLB usage
  68
  69         mov     %r11,8(%rsp,$num,8)     # tp[num+1]=%rsp
  70 .Lprologue:
  71         mov     %rdx,$bp                # $bp reassigned, remember?
  72
  73         mov     ($n0),$n0               # pull n0[0] value
  74
  75         xor     $i,$i                   # i=0
  76         xor     $j,$j                   # j=0
  77
  78         mov     ($bp),$m0               # m0=bp[0]
  79         mov     ($ap),%rax
  80         mulq    $m0                     # ap[0]*bp[0]
  81         mov     %rax,$lo0
  82         mov     %rdx,$hi0
  83
  84         imulq   $n0,%rax                # "tp[0]"*n0
  85         mov     %rax,$m1
  86
  87         mulq    ($np)                   # np[0]*m1
  88         add     $lo0,%rax               # discarded
  89         adc     \$0,%rdx
  90         mov     %rdx,$hi1
  91
  92         lea     1($j),$j                # j++
  93 .L1st:
  94         mov     ($ap,$j,8),%rax
  95         mulq    $m0                     # ap[j]*bp[0]
  96         add     $hi0,%rax
  97         adc     \$0,%rdx
  98         mov     %rax,$lo0
  99         mov     ($np,$j,8),%rax
 100         mov     %rdx,$hi0
 101
 102         mulq    $m1                     # np[j]*m1
 103         add     $hi1,%rax
 104         lea     1($j),$j                # j++
 105         adc     \$0,%rdx
 106         add     $lo0,%rax               # np[j]*m1+ap[j]*bp[0]
 107         adc     \$0,%rdx
 108         mov     %rax,-16(%rsp,$j,8)     # tp[j-1]
 109         cmp     $num,$j
 110         mov     %rdx,$hi1
 111         jl      .L1st
 112
 113         xor     %rdx,%rdx
 114         add     $hi0,$hi1
 115         adc     \$0,%rdx
 116         mov     $hi1,-8(%rsp,$num,8)
 117         mov     %rdx,(%rsp,$num,8)      # store upmost overflow bit
 118
 119         lea     1($i),$i                # i++
 120 .align  4
 121 .Louter:
 122         xor     $j,$j                   # j=0
 123
 124         mov     ($bp,$i,8),$m0          # m0=bp[i]
 125         mov     ($ap),%rax              # ap[0]
 126         mulq    $m0                     # ap[0]*bp[i]
 127         add     (%rsp),%rax             # ap[0]*bp[i]+tp[0]
 128         adc     \$0,%rdx
 129         mov     %rax,$lo0
 130         mov     %rdx,$hi0
 131
 132         imulq   $n0,%rax                # tp[0]*n0
 133         mov     %rax,$m1
 134
 135         mulq    ($np,$j,8)              # np[0]*m1
 136         add     $lo0,%rax               # discarded
 137         mov     8(%rsp),$lo0            # tp[1]
 138         adc     \$0,%rdx
 139         mov     %rdx,$hi1
 140
 141         lea     1($j),$j                # j++
 142 .align  4
 143 .Linner:
 144         mov     ($ap,$j,8),%rax
 145         mulq    $m0                     # ap[j]*bp[i]
 146         add     $hi0,%rax
 147         adc     \$0,%rdx
 148         add     %rax,$lo0               # ap[j]*bp[i]+tp[j]
 149         mov     ($np,$j,8),%rax
 150         adc     \$0,%rdx
 151         mov     %rdx,$hi0
 152
 153         mulq    $m1                     # np[j]*m1
 154         add     $hi1,%rax
 155         lea     1($j),$j                # j++
 156         adc     \$0,%rdx
 157         add     $lo0,%rax               # np[j]*m1+ap[j]*bp[i]+tp[j]
 158         adc     \$0,%rdx
 159         mov     (%rsp,$j,8),$lo0
 160         cmp     $num,$j
 161         mov     %rax,-16(%rsp,$j,8)     # tp[j-1]
 162         mov     %rdx,$hi1
 163         jl      .Linner
 164
 165         xor     %rdx,%rdx
 166         add     $hi0,$hi1
 167         adc     \$0,%rdx
 168         add     $lo0,$hi1               # pull upmost overflow bit
 169         adc     \$0,%rdx
 170         mov     $hi1,-8(%rsp,$num,8)
 171         mov     %rdx,(%rsp,$num,8)      # store upmost overflow bit
 172
 173         lea     1($i),$i                # i++
 174         cmp     $num,$i
 175         jl      .Louter
 176
 177         lea     (%rsp),$ap              # borrow ap for tp
 178         lea     -1($num),$j             # j=num-1
 179
 180         mov     ($ap),%rax              # tp[0]
 181         xor     $i,$i                   # i=0 and clear CF!
 182         jmp     .Lsub
 183 .align  16
 184 .Lsub:  sbb     ($np,$i,8),%rax
 185         mov     %rax,($rp,$i,8)         # rp[i]=tp[i]-np[i]
 186         dec     $j                      # doesn't affect CF!
 187         mov     8($ap,$i,8),%rax        # tp[i+1]
 188         lea     1($i),$i                # i++
 189         jge     .Lsub
 190
 191         sbb     \$0,%rax                # handle upmost overflow bit
 192         and     %rax,$ap
 193         not     %rax
 194         mov     $rp,$np
 195         and     %rax,$np
 196         lea     -1($num),$j
 197         or      $np,$ap                 # ap=borrow?tp:rp
 198 .align  16
 199 .Lcopy:                                 # copy or in-place refresh
 200         mov     ($ap,$j,8),%rax
 201         mov     %rax,($rp,$j,8)         # rp[i]=tp[i]
 202         mov     $i,(%rsp,$j,8)          # zap temporary vector
 203         dec     $j
 204         jge     .Lcopy
 205
 206         mov     8(%rsp,$num,8),%rsi     # restore %rsp
 207         mov     \$1,%rax
 208         mov     (%rsi),%r15
 209         mov     8(%rsi),%r14
 210         mov     16(%rsi),%r13
 211         mov     24(%rsi),%r12
 212         mov     32(%rsi),%rbp
 213         mov     40(%rsi),%rbx
 214         lea     48(%rsi),%rsp
 215 .Lepilogue:
 216         ret
 217 .size   bn_mul_mont,.-bn_mul_mont
 218 .asciz  "Montgomery Multiplication for x86_64, CRYPTOGAMS by <appro\@openssl.org>"
 219 .align  16
 220 ___
 221
 222 # EXCEPTION_DISPOSITION handler (EXCEPTION_RECORD *rec,ULONG64 frame,
 223 #               CONTEXT *context,DISPATCHER_CONTEXT *disp)
 224 if ($win64) {
 225 $rec="%rcx";
 226 $frame="%rdx";
 227 $context="%r8";
 228 $disp="%r9";
 229
 230 $code.=<<___;
 231 .extern __imp_RtlVirtualUnwind
 232 .type   se_handler,\@abi-omnipotent
 233 .align  16
 234 se_handler:
 235         push    %rsi
 236         push    %rdi
 237         push    %rbx
 238         push    %rbp
 239         push    %r12
 240         push    %r13
 241         push    %r14
 242         push    %r15
 243         pushfq
 244         sub     \$64,%rsp
 245
 246         mov     120($context),%rax      # pull context->Rax
 247         mov     248($context),%rbx      # pull context->Rip
 248
 249         lea     .Lprologue(%rip),%r10
 250         cmp     %r10,%rbx               # context->Rip<.Lprologue
 251         jb      .Lin_prologue
 252
 253         mov     152($context),%rax      # pull context->Rsp
 254
 255         lea     .Lepilogue(%rip),%r10
 256         cmp     %r10,%rbx               # context->Rip>=.Lepilogue
 257         jae     .Lin_prologue
 258
 259         mov     192($context),%r10      # pull $num
 260         mov     8(%rax,%r10,8),%rax     # pull saved stack pointer
 261         lea     48(%rax),%rax
 262
 263         mov     -8(%rax),%rbx
 264         mov     -16(%rax),%rbp
 265         mov     -24(%rax),%r12
 266         mov     -32(%rax),%r13
 267         mov     -40(%rax),%r14
 268         mov     -48(%rax),%r15
 269         mov     %rbx,144($context)      # restore context->Rbx
 270         mov     %rbp,160($context)      # restore context->Rbp
 271         mov     %r12,216($context)      # restore context->R12
 272         mov     %r13,224($context)      # restore context->R13
 273         mov     %r14,232($context)      # restore context->R14
 274         mov     %r15,240($context)      # restore context->R15
 275
 276 .Lin_prologue:
 277         mov     8(%rax),%rdi
 278         mov     16(%rax),%rsi
 279         mov     %rax,152($context)      # restore context->Rsp
 280         mov     %rsi,168($context)      # restore context->Rsi
 281         mov     %rdi,176($context)      # restore context->Rdi
 282
 283         mov     40($disp),%rdi          # disp->ContextRecord
 284         mov     $context,%rsi           # context
 285         mov     \$154,%ecx              # sizeof(CONTEXT)
 286         .long   0xa548f3fc              # cld; rep movsq
 287
 288         mov     $disp,%rsi
 289         xor     %rcx,%rcx               # arg1, UNW_FLAG_NHANDLER
 290         mov     8(%rsi),%rdx            # arg2, disp->ImageBase
 291         mov     0(%rsi),%r8             # arg3, disp->ControlPc
 292         mov     16(%rsi),%r9            # arg4, disp->FunctionEntry
 293         mov     40(%rsi),%r10           # disp->ContextRecord
 294         lea     56(%rsi),%r11           # &disp->HandlerData
 295         lea     24(%rsi),%r12           # &disp->EstablisherFrame
 296         mov     %r10,32(%rsp)           # arg5
 297         mov     %r11,40(%rsp)           # arg6
 298         mov     %r12,48(%rsp)           # arg7
 299         mov     %rcx,56(%rsp)           # arg8, (NULL)
 300         call    *__imp_RtlVirtualUnwind(%rip)
 301
 302         mov     \$1,%eax                # ExceptionContinueSearch
 303         add     \$64,%rsp
 304         popfq
 305         pop     %r15
 306         pop     %r14
 307         pop     %r13
 308         pop     %r12
 309         pop     %rbp
 310         pop     %rbx
 311         pop     %rdi
 312         pop     %rsi
 313         ret
 314 .size   se_handler,.-se_handler
 315
 316 .section        .pdata
 317 .align  4
 318         .rva    .LSEH_begin_bn_mul_mont
 319         .rva    .LSEH_end_bn_mul_mont
 320         .rva    .LSEH_info_bn_mul_mont
 321
 322 .section        .xdata
 323 .align  8
 324 .LSEH_info_bn_mul_mont:
 325         .byte   9,0,0,0
 326         .rva    se_handler
 327 ___
 328 }
 329
 330 print $code;
 331 close STDOUT;