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