bc3fa83cf7398642383e23fac9be4a29b22bcdac
[openssl.git] / 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;