Montgomery multiplication routine for Alpha.
[openssl.git] / crypto / bn / asm / alpha-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 # On 21264 RSA sign performance improves by 70/35/20/15 percent for
11 # 512/1024/2048/4096 bit key lengths. This is against vendor compiler
12 # instructed to '-tune host' code with in-line assembler. Other
13 # benchmarks improve by 15-20%. To anchor it to something else, the
14 # code provides approximately the same performance per GHz as AMD64.
15 # I.e. if you compare 1GHz 21264 and 2GHz Opteron, you'll observe ~2x
16 # difference.
17
18 # int bn_mul_mont(
19 $rp="a0";       # BN_ULONG *rp,
20 $ap="a1";       # const BN_ULONG *ap,
21 $bp="a2";       # const BN_ULONG *bp,
22 $np="a3";       # const BN_ULONG *np,
23 $n0="a4";       # const BN_ULONG *n0,
24 $num="a5";      # int num);
25
26 $lo0="t0";
27 $hi0="t1";
28 $lo1="t2";
29 $hi1="t3";
30 $aj="t4";
31 $bi="t5";
32 $nj="t6";
33 $tp="t7";
34 $alo="t8";
35 $ahi="t9";
36 $nlo="t10";
37 $nhi="t11";
38 $tj="t12";
39 $i="s3";
40 $j="s4";
41 $m1="s5";
42
43 $code=<<___;
44 #include <asm.h>
45 #include <regdef.h>
46
47 .text
48
49 .set    noat
50 .set    noreorder
51
52 .globl  bn_mul_mont
53 .align  5
54 bn_mul_mont:
55         .ent    bn_mul_mont
56         lda     sp,-40(sp)
57         stq     ra,0(sp)
58         stq     s3,8(sp)
59         stq     s4,16(sp)
60         stq     s5,24(sp)
61         stq     fp,32(sp)
62         mov     sp,fp
63         .mask   0x0400f000,-40
64         .frame  fp,40,ra
65         .prologue 0
66
67         .align  4
68         sextl   $num,$num
69         mov     0,v0
70         cmplt   $num,4,AT
71         bne     AT,.Lexit
72
73         ldq     $hi0,0($ap)     # ap[0]
74         s8addq  $num,16,AT
75         ldq     $aj,8($ap)
76         subq    sp,AT,sp
77         ldq     $bi,0($bp)      # bp[0]
78         mov     -4096,AT
79         ldq     $n0,0($n0)
80         and     sp,AT,sp
81
82         mulq    $hi0,$bi,$lo0
83         ldq     $hi1,0($np)     # np[0]
84         umulh   $hi0,$bi,$hi0
85         ldq     $nj,8($np)
86
87         mulq    $lo0,$n0,$m1
88
89         mulq    $hi1,$m1,$lo1
90         umulh   $hi1,$m1,$hi1
91
92         addq    $lo1,$lo0,$lo1
93         cmpult  $lo1,$lo0,AT
94         addq    $hi1,AT,$hi1
95
96         mulq    $aj,$bi,$alo
97         mov     2,$j
98         umulh   $aj,$bi,$ahi
99         mov     sp,$tp
100
101         mulq    $nj,$m1,$nlo
102         s8addq  $j,$ap,$aj
103         umulh   $nj,$m1,$nhi
104         s8addq  $j,$np,$nj
105 .align  4
106 .L1st:
107         ldq     $aj,($aj)
108         addl    $j,1,$j
109         ldq     $nj,($nj)
110         lda     $tp,8($tp)
111
112         addq    $alo,$hi0,$lo0
113         mulq    $aj,$bi,$alo
114         cmpult  $lo0,$hi0,AT
115         addq    $nlo,$hi1,$lo1
116
117         mulq    $nj,$m1,$nlo
118         addq    $ahi,AT,$hi0
119         cmpult  $lo1,$hi1,v0
120         cmplt   $j,$num,$tj
121
122         umulh   $aj,$bi,$ahi
123         addq    $nhi,v0,$hi1
124         addq    $lo1,$lo0,$lo1
125         s8addq  $j,$ap,$aj
126
127         umulh   $nj,$m1,$nhi
128         cmpult  $lo1,$lo0,v0
129         addq    $hi1,v0,$hi1
130         s8addq  $j,$np,$nj
131
132         stq     $lo1,-8($tp)
133         nop
134         unop
135         bne     $tj,.L1st
136
137         addq    $alo,$hi0,$lo0
138         addq    $nlo,$hi1,$lo1
139         cmpult  $lo0,$hi0,AT
140         cmpult  $lo1,$hi1,v0
141         addq    $ahi,AT,$hi0
142         addq    $nhi,v0,$hi1
143
144         addq    $lo1,$lo0,$lo1
145         cmpult  $lo1,$lo0,v0
146         addq    $hi1,v0,$hi1
147
148         stq     $lo1,0($tp)
149
150         addq    $hi1,$hi0,$hi1
151         cmpult  $hi1,$hi0,AT
152         stq     $hi1,8($tp)
153         stq     AT,16($tp)
154
155         mov     1,$i
156 .align  4
157 .Louter:
158         s8addq  $i,$bp,$bi
159         ldq     $hi0,($ap)
160         ldq     $aj,8($ap)
161         ldq     $bi,($bi)
162         ldq     $hi1,($np)
163         ldq     $nj,8($np)
164         ldq     $tj,(sp)
165
166         mulq    $hi0,$bi,$lo0
167         umulh   $hi0,$bi,$hi0
168
169         addq    $lo0,$tj,$lo0
170         cmpult  $lo0,$tj,AT
171         addq    $hi0,AT,$hi0
172
173         mulq    $lo0,$n0,$m1
174
175         mulq    $hi1,$m1,$lo1
176         umulh   $hi1,$m1,$hi1
177
178         addq    $lo1,$lo0,$lo1
179         cmpult  $lo1,$lo0,AT
180         mov     2,$j
181         addq    $hi1,AT,$hi1
182
183         mulq    $aj,$bi,$alo
184         mov     sp,$tp
185         umulh   $aj,$bi,$ahi
186
187         mulq    $nj,$m1,$nlo
188         s8addq  $j,$ap,$aj
189         umulh   $nj,$m1,$nhi
190         .set    noreorder
191 .align  4
192 .Linner:
193         ldq     $tj,8($tp)      #L0
194         nop                     #U1
195         ldq     $aj,($aj)       #L1
196         s8addq  $j,$np,$nj      #U0
197
198         ldq     $nj,($nj)       #L0
199         nop                     #U1
200         addq    $alo,$hi0,$lo0  #L1
201         lda     $tp,8($tp)
202
203         mulq    $aj,$bi,$alo    #U1
204         cmpult  $lo0,$hi0,AT    #L0
205         addq    $nlo,$hi1,$lo1  #L1
206         addl    $j,1,$j
207
208         mulq    $nj,$m1,$nlo    #U1
209         addq    $ahi,AT,$hi0    #L0
210         addq    $lo0,$tj,$lo0   #L1
211         cmpult  $lo1,$hi1,v0    #U0
212
213         umulh   $aj,$bi,$ahi    #U1
214         cmpult  $lo0,$tj,AT     #L0
215         addq    $lo1,$lo0,$lo1  #L1
216         addq    $nhi,v0,$hi1    #U0
217
218         umulh   $nj,$m1,$nhi    #U1
219         s8addq  $j,$ap,$aj      #L0
220         cmpult  $lo1,$lo0,v0    #L1
221         cmplt   $j,$num,$tj     #U0     # borrow $tj
222
223         addq    $hi0,AT,$hi0    #L0
224         addq    $hi1,v0,$hi1    #U1
225         stq     $lo1,-8($tp)    #L1
226         bne     $tj,.Linner     #U0
227
228         ldq     $tj,8($tp)
229         addq    $alo,$hi0,$lo0
230         addq    $nlo,$hi1,$lo1
231         cmpult  $lo0,$hi0,AT
232         cmpult  $lo1,$hi1,v0
233         addq    $ahi,AT,$hi0
234         addq    $nhi,v0,$hi1
235
236         addq    $lo0,$tj,$lo0
237         cmpult  $lo0,$tj,AT
238         addq    $hi0,AT,$hi0
239
240         ldq     $tj,16($tp)
241         addq    $lo1,$lo0,$j
242         cmpult  $j,$lo0,v0
243         addq    $hi1,v0,$hi1
244
245         addq    $hi1,$hi0,$lo1
246         stq     $j,($tp)
247         cmpult  $lo1,$hi0,$hi1
248         addq    $lo1,$tj,$lo1
249         cmpult  $lo1,$tj,AT
250         addl    $i,1,$i
251         addq    $hi1,AT,$hi1
252         stq     $lo1,8($tp)
253         cmplt   $i,$num,$tj     # borrow $tj
254         stq     $hi1,16($tp)
255         bne     $tj,.Louter
256 \f
257         s8addq  $num,sp,$ap
258         mov     $rp,$bp
259         mov     sp,$tp
260         mov     0,$hi0
261
262         bne     $hi1,.Lsub
263         cmpult  $nj,$lo1,AT
264         bne     AT,.Lsub
265
266 .align  4
267 .Lcopy: ldq     AT,($tp)
268         lda     $tp,8($tp)
269         stq     AT,($rp)
270         cmpult  $tp,$ap,AT
271         stq     zero,-8($tp)
272         nop
273         lda     $rp,8($rp)
274         bne     AT,.Lcopy
275         mov     1,v0
276         br      .Lexit
277
278 .align  4
279 .Lsub:  ldq     $lo0,($tp)
280         ldq     $lo1,($np)
281         subq    $lo0,$lo1,$lo1
282         cmpult  $lo0,$lo1,AT
283         subq    $lo1,$hi0,$lo0
284         cmpult  $lo1,$lo0,$hi0
285         lda     $tp,8($tp)
286         or      $hi0,AT,$hi0
287         lda     $np,8($np)
288         stq     $lo0,($rp)
289         cmpult  $tp,$ap,v0
290         lda     $rp,8($rp)
291         bne     v0,.Lsub
292
293         subq    $hi1,$hi0,$hi0
294         mov     sp,$tp
295         cmpule  $hi1,$hi0,AT
296         mov     $bp,$rp
297         bne     AT,.Lcopy
298
299 .align  4
300 .Lzap:  stq     zero,($tp)
301         cmpult  $tp,$ap,AT
302         lda     $tp,8($tp)
303         bne     AT,.Lzap
304         mov     1,v0
305
306 .align  4
307 .Lexit: mov     fp,sp
308         #ldq    ra,0(sp)
309         ldq     s3,8(sp)
310         ldq     s4,16(sp)
311         ldq     s5,24(sp)
312         ldq     fp,32(sp)
313         lda     sp,40(sp)
314         ret     (ra)
315 .end    bn_mul_mont
316 .rdata
317 .asciiz "Montgomery Multiplication for Alpha, CRYPTOGAMS by <appro\@openssl.org>"
318 ___
319
320 print $code;
321 close STDOUT;