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 $output=shift;
  19
  20 $0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
  21 ( $xlate="${dir}x86_64-xlate.pl" and -f $xlate ) or
  22 ( $xlate="${dir}../../perlasm/x86_64-xlate.pl" and -f $xlate) or
  23 die "can't locate x86_64-xlate.pl";
  24
  25 open STDOUT,"| $^X $xlate $output";
  26
  27 # int bn_mul_mont(
  28 $rp="%rdi";     # BN_ULONG *rp,
  29 $ap="%rsi";     # const BN_ULONG *ap,
  30 $bp="%rdx";     # const BN_ULONG *bp,
  31 $np="%rcx";     # const BN_ULONG *np,
  32 $n0="%r8";      # const BN_ULONG *n0,
  33 $num="%r9";     # int num);
  34 $lo0="%r10";
  35 $hi0="%r11";
  36 $bp="%r12";     # reassign $bp
  37 $hi1="%r13";
  38 $i="%r14";
  39 $j="%r15";
  40 $m0="%rbx";
  41 $m1="%rbp";
  42
  43 $code=<<___;
  44 .text
  45
  46 .globl  bn_mul_mont
  47 .type   bn_mul_mont,\@function,6
  48 .align  16
  49 bn_mul_mont:
  50         push    %rbx
  51         push    %rbp
  52         push    %r12
  53         push    %r13
  54         push    %r14
  55         push    %r15
  56
  57         lea     2($num),%rax
  58         mov     %rsp,%rbp
  59         neg     %rax
  60         lea     (%rsp,%rax,8),%rsp      # tp=alloca(8*(num+2))
  61         and     \$-1024,%rsp            # minimize TLB usage
  62         mov     %rbp,8(%rsp,$num,8)     # tp[num+1]=%rsp
  63         mov     %rdx,$bp                # $bp reassigned, remember?
  64
  65         mov     ($n0),$n0               # pull n0[0] value
  66
  67         xor     $i,$i                   # i=0
  68         xor     $j,$j                   # j=0
  69
  70         mov     ($bp),$m0               # m0=bp[0]
  71         mov     ($ap),%rax
  72         mulq    $m0                     # ap[0]*bp[0]
  73         mov     %rax,$lo0
  74         mov     %rdx,$hi0
  75
  76         imulq   $n0,%rax                # "tp[0]"*n0
  77         mov     %rax,$m1
  78
  79         mulq    ($np)                   # np[0]*m1
  80         add     $lo0,%rax               # discarded
  81         adc     \$0,%rdx
  82         mov     %rdx,$hi1
  83
  84         lea     1($j),$j                # j++
  85 .L1st:
  86         mov     ($ap,$j,8),%rax
  87         mulq    $m0                     # ap[j]*bp[0]
  88         add     $hi0,%rax
  89         adc     \$0,%rdx
  90         mov     %rax,$lo0
  91         mov     ($np,$j,8),%rax
  92         mov     %rdx,$hi0
  93
  94         mulq    $m1                     # np[j]*m1
  95         add     $hi1,%rax
  96         lea     1($j),$j                # j++
  97         adc     \$0,%rdx
  98         add     $lo0,%rax               # np[j]*m1+ap[j]*bp[0]
  99         adc     \$0,%rdx
 100         mov     %rax,-16(%rsp,$j,8)     # tp[j-1]
 101         cmp     $num,$j
 102         mov     %rdx,$hi1
 103         jl      .L1st
 104
 105         xor     %rdx,%rdx
 106         add     $hi0,$hi1
 107         adc     \$0,%rdx
 108         mov     $hi1,-8(%rsp,$num,8)
 109         mov     %rdx,(%rsp,$num,8)      # store upmost overflow bit
 110
 111         lea     1($i),$i                # i++
 112 .align  4
 113 .Louter:
 114         xor     $j,$j                   # j=0
 115
 116         mov     ($bp,$i,8),$m0          # m0=bp[i]
 117         mov     ($ap),%rax              # ap[0]
 118         mulq    $m0                     # ap[0]*bp[i]
 119         add     (%rsp),%rax             # ap[0]*bp[i]+tp[0]
 120         adc     \$0,%rdx
 121         mov     %rax,$lo0
 122         mov     %rdx,$hi0
 123
 124         imulq   $n0,%rax                # tp[0]*n0
 125         mov     %rax,$m1
 126
 127         mulq    ($np,$j,8)              # np[0]*m1
 128         add     $lo0,%rax               # discarded
 129         mov     8(%rsp),$lo0            # tp[1]
 130         adc     \$0,%rdx
 131         mov     %rdx,$hi1
 132
 133         lea     1($j),$j                # j++
 134 .align  4
 135 .Linner:
 136         mov     ($ap,$j,8),%rax
 137         mulq    $m0                     # ap[j]*bp[i]
 138         add     $hi0,%rax
 139         adc     \$0,%rdx
 140         add     %rax,$lo0               # ap[j]*bp[i]+tp[j]
 141         mov     ($np,$j,8),%rax
 142         adc     \$0,%rdx
 143         mov     %rdx,$hi0
 144
 145         mulq    $m1                     # np[j]*m1
 146         add     $hi1,%rax
 147         lea     1($j),$j                # j++
 148         adc     \$0,%rdx
 149         add     $lo0,%rax               # np[j]*m1+ap[j]*bp[i]+tp[j]
 150         adc     \$0,%rdx
 151         mov     (%rsp,$j,8),$lo0
 152         cmp     $num,$j
 153         mov     %rax,-16(%rsp,$j,8)     # tp[j-1]
 154         mov     %rdx,$hi1
 155         jl      .Linner
 156
 157         xor     %rdx,%rdx
 158         add     $hi0,$hi1
 159         adc     \$0,%rdx
 160         add     $lo0,$hi1               # pull upmost overflow bit
 161         adc     \$0,%rdx
 162         mov     $hi1,-8(%rsp,$num,8)
 163         mov     %rdx,(%rsp,$num,8)      # store upmost overflow bit
 164
 165         lea     1($i),$i                # i++
 166         cmp     $num,$i
 167         jl      .Louter
 168
 169         xor     $i,$i                   # i=0
 170         lea     -1($num),$j             # j=num-1
 171         cmp     \$0,%rdx                # %rdx still holds upmost overflow bit
 172         jnz     .Lsub                   # CF is cleared by compare with 0
 173         mov     (%rsp,$j,8),%rax
 174         cmp     ($np,$j,8),%rax         # tp[num-1]-np[num-1]
 175         jae     .Lsub                   # if taken CF was cleared by above cmp
 176 .align  4
 177 .Lcopy:
 178         mov     (%rsp,$j,8),%rax
 179         mov     %rax,($rp,$j,8)         # rp[i]=tp[i]
 180         mov     $i,(%rsp,$j,8)          # zap temporary vector
 181         dec     $j
 182         jge     .Lcopy
 183 .align  4
 184 .Lexit:
 185         mov     8(%rsp,$num,8),%rsp     # restore %rsp
 186         mov     \$1,%rax
 187         pop     %r15
 188         pop     %r14
 189         pop     %r13
 190         pop     %r12
 191         pop     %rbp
 192         pop     %rbx
 193         ret
 194
 195 .align  16
 196 .Lsub:  mov     (%rsp,$i,8),%rax
 197         sbb     ($np,$i,8),%rax
 198         mov     %rax,($rp,$i,8)         # rp[i]=tp[i]-np[j]
 199         lea     1($i),$i                # i++
 200         dec     $j                      # doesn't affect CF!
 201         jge     .Lsub
 202         lea     -1($num),$j             # j=num-1
 203         sbb     \$0,%rdx
 204         jc      .Lcopy                  # tp was less than np
 205 .align  4
 206 .Lzap:  mov     $i,(%rsp,$j,8)          # zap temporary vector
 207         dec     $j
 208         jge     .Lzap
 209         jmp     .Lexit
 210 .size   bn_mul_mont,.-bn_mul_mont
 211 .asciz  "Montgomery Multiplication for x86_64, CRYPTOGAMS by <appro\@openssl.org>"
 212 ___
 213
 214 print $code;
 215 close STDOUT;