9257b2cd7153b21477e1e457aeac04239b399f35
[openssl.git] / crypto / bn / asm / ppc-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 # April 2006
11
12 # "Teaser" Montgomery multiplication module for PowerPC. It's possible
13 # to gain a bit more by modulo-scheduling outer loop, then dedicated
14 # squaring procedure should give further 20% and code can be adapted
15 # for 32-bit application running on 64-bit CPU. As for the latter.
16 # It won't be able to achieve "native" 64-bit performance, because in
17 # 32-bit application context every addc instruction will have to be
18 # expanded as addc, twice right shift by 32 and finally adde, etc.
19 # So far RSA *sign* performance improvement over pre-bn_mul_mont asm
20 # for 64-bit application running on PPC970/G5 is:
21 #
22 # 512-bit       +65%    
23 # 1024-bit      +35%
24 # 2048-bit      +18%
25 # 4096-bit      +4%
26
27 $flavour = shift;
28
29 if ($flavour =~ /32/) {
30         $BITS=  32;
31         $BNSZ=  $BITS/8;
32         $SIZE_T=4;
33         $RZONE= 224;
34         $FRAME= $SIZE_T*16;
35
36         $LD=    "lwz";          # load
37         $LDU=   "lwzu";         # load and update
38         $LDX=   "lwzx";         # load indexed
39         $ST=    "stw";          # store
40         $STU=   "stwu";         # store and update
41         $STX=   "stwx";         # store indexed
42         $STUX=  "stwux";        # store indexed and update
43         $UMULL= "mullw";        # unsigned multiply low
44         $UMULH= "mulhwu";       # unsigned multiply high
45         $UCMP=  "cmplw";        # unsigned compare
46         $SHRI=  "srwi";         # unsigned shift right by immediate     
47         $PUSH=  $ST;
48         $POP=   $LD;
49 } elsif ($flavour =~ /64/) {
50         $BITS=  64;
51         $BNSZ=  $BITS/8;
52         $SIZE_T=8;
53         $RZONE= 288;
54         $FRAME= $SIZE_T*16;
55
56         # same as above, but 64-bit mnemonics...
57         $LD=    "ld";           # load
58         $LDU=   "ldu";          # load and update
59         $LDX=   "ldx";          # load indexed
60         $ST=    "std";          # store
61         $STU=   "stdu";         # store and update
62         $STX=   "stdx";         # store indexed
63         $STUX=  "stdux";        # store indexed and update
64         $UMULL= "mulld";        # unsigned multiply low
65         $UMULH= "mulhdu";       # unsigned multiply high
66         $UCMP=  "cmpld";        # unsigned compare
67         $SHRI=  "srdi";         # unsigned shift right by immediate     
68         $PUSH=  $ST;
69         $POP=   $LD;
70 } else { die "nonsense $flavour"; }
71
72 $0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
73 ( $xlate="${dir}ppc-xlate.pl" and -f $xlate ) or
74 ( $xlate="${dir}../../perlasm/ppc-xlate.pl" and -f $xlate) or
75 die "can't locate ppc-xlate.pl";
76
77 open STDOUT,"| $^X $xlate $flavour ".shift || die "can't call $xlate: $!";
78
79 $sp="r1";
80 $toc="r2";
81 $rp="r3";       $ovf="r3";
82 $ap="r4";
83 $bp="r5";
84 $np="r6";
85 $n0="r7";
86 $num="r8";
87 $rp="r9";       # $rp is reassigned
88 $aj="r10";
89 $nj="r11";
90 $tj="r12";
91 # non-volatile registers
92 $i="r14";
93 $j="r15";
94 $tp="r16";
95 $m0="r17";
96 $m1="r18";
97 $lo0="r19";
98 $hi0="r20";
99 $lo1="r21";
100 $hi1="r22";
101 $alo="r23";
102 $ahi="r24";
103 $nlo="r25";
104 #
105 $nhi="r0";
106
107 $code=<<___;
108 .machine "any"
109 .text
110
111 .globl  .bn_mul_mont_int
112 .align  4
113 .bn_mul_mont_int:
114         cmpwi   $num,4
115         mr      $rp,r3          ; $rp is reassigned
116         li      r3,0
117         bltlr
118 ___
119 $code.=<<___ if ($BNSZ==4);
120         cmpwi   $num,32         ; longer key performance is not better
121         bgelr
122 ___
123 $code.=<<___;
124         slwi    $num,$num,`log($BNSZ)/log(2)`
125         li      $tj,-4096
126         addi    $ovf,$num,`$FRAME+$RZONE`
127         subf    $ovf,$ovf,$sp   ; $sp-$ovf
128         and     $ovf,$ovf,$tj   ; minimize TLB usage
129         subf    $ovf,$sp,$ovf   ; $ovf-$sp
130         srwi    $num,$num,`log($BNSZ)/log(2)`
131         $STUX   $sp,$sp,$ovf
132
133         $PUSH   r14,`4*$SIZE_T`($sp)
134         $PUSH   r15,`5*$SIZE_T`($sp)
135         $PUSH   r16,`6*$SIZE_T`($sp)
136         $PUSH   r17,`7*$SIZE_T`($sp)
137         $PUSH   r18,`8*$SIZE_T`($sp)
138         $PUSH   r19,`9*$SIZE_T`($sp)
139         $PUSH   r20,`10*$SIZE_T`($sp)
140         $PUSH   r21,`11*$SIZE_T`($sp)
141         $PUSH   r22,`12*$SIZE_T`($sp)
142         $PUSH   r23,`13*$SIZE_T`($sp)
143         $PUSH   r24,`14*$SIZE_T`($sp)
144         $PUSH   r25,`15*$SIZE_T`($sp)
145
146         $LD     $n0,0($n0)      ; pull n0[0] value
147         addi    $num,$num,-2    ; adjust $num for counter register
148 \f
149         $LD     $m0,0($bp)      ; m0=bp[0]
150         $LD     $aj,0($ap)      ; ap[0]
151         addi    $tp,$sp,$FRAME
152         $UMULL  $lo0,$aj,$m0    ; ap[0]*bp[0]
153         $UMULH  $hi0,$aj,$m0
154
155         $LD     $aj,$BNSZ($ap)  ; ap[1]
156         $LD     $nj,0($np)      ; np[0]
157
158         $UMULL  $m1,$lo0,$n0    ; "tp[0]"*n0
159
160         $UMULL  $alo,$aj,$m0    ; ap[1]*bp[0]
161         $UMULH  $ahi,$aj,$m0
162
163         $UMULL  $lo1,$nj,$m1    ; np[0]*m1
164         $UMULH  $hi1,$nj,$m1
165         $LD     $nj,$BNSZ($np)  ; np[1]
166         addc    $lo1,$lo1,$lo0
167         addze   $hi1,$hi1
168
169         $UMULL  $nlo,$nj,$m1    ; np[1]*m1
170         $UMULH  $nhi,$nj,$m1
171
172         mtctr   $num
173         li      $j,`2*$BNSZ`
174 .align  4
175 L1st:
176         $LDX    $aj,$ap,$j      ; ap[j]
177         addc    $lo0,$alo,$hi0
178         $LDX    $nj,$np,$j      ; np[j]
179         addze   $hi0,$ahi
180         $UMULL  $alo,$aj,$m0    ; ap[j]*bp[0]
181         addc    $lo1,$nlo,$hi1
182         $UMULH  $ahi,$aj,$m0
183         addze   $hi1,$nhi
184         $UMULL  $nlo,$nj,$m1    ; np[j]*m1
185         addc    $lo1,$lo1,$lo0  ; np[j]*m1+ap[j]*bp[0]
186         $UMULH  $nhi,$nj,$m1
187         addze   $hi1,$hi1
188         $ST     $lo1,0($tp)     ; tp[j-1]
189
190         addi    $j,$j,$BNSZ     ; j++
191         addi    $tp,$tp,$BNSZ   ; tp++
192         bdnz-   L1st
193 ;L1st
194         addc    $lo0,$alo,$hi0
195         addze   $hi0,$ahi
196
197         addc    $lo1,$nlo,$hi1
198         addze   $hi1,$nhi
199         addc    $lo1,$lo1,$lo0  ; np[j]*m1+ap[j]*bp[0]
200         addze   $hi1,$hi1
201         $ST     $lo1,0($tp)     ; tp[j-1]
202
203         li      $ovf,0
204         addc    $hi1,$hi1,$hi0
205         addze   $ovf,$ovf       ; upmost overflow bit
206         $ST     $hi1,$BNSZ($tp)
207 \f
208         li      $i,$BNSZ
209 .align  4
210 Louter:
211         $LDX    $m0,$bp,$i      ; m0=bp[i]
212         $LD     $aj,0($ap)      ; ap[0]
213         addi    $tp,$sp,$FRAME
214         $LD     $tj,$FRAME($sp) ; tp[0]
215         $UMULL  $lo0,$aj,$m0    ; ap[0]*bp[i]
216         $UMULH  $hi0,$aj,$m0
217         $LD     $aj,$BNSZ($ap)  ; ap[1]
218         $LD     $nj,0($np)      ; np[0]
219         addc    $lo0,$lo0,$tj   ; ap[0]*bp[i]+tp[0]
220         $UMULL  $alo,$aj,$m0    ; ap[j]*bp[i]
221         addze   $hi0,$hi0
222         $UMULL  $m1,$lo0,$n0    ; tp[0]*n0
223         $UMULH  $ahi,$aj,$m0
224         $UMULL  $lo1,$nj,$m1    ; np[0]*m1
225         $UMULH  $hi1,$nj,$m1
226         $LD     $nj,$BNSZ($np)  ; np[1]
227         addc    $lo1,$lo1,$lo0
228         $UMULL  $nlo,$nj,$m1    ; np[1]*m1
229         addze   $hi1,$hi1
230         $UMULH  $nhi,$nj,$m1
231 \f
232         mtctr   $num
233         li      $j,`2*$BNSZ`
234 .align  4
235 Linner:
236         $LDX    $aj,$ap,$j      ; ap[j]
237         addc    $lo0,$alo,$hi0
238         $LD     $tj,$BNSZ($tp)  ; tp[j]
239         addze   $hi0,$ahi
240         $LDX    $nj,$np,$j      ; np[j]
241         addc    $lo1,$nlo,$hi1
242         $UMULL  $alo,$aj,$m0    ; ap[j]*bp[i]
243         addze   $hi1,$nhi
244         $UMULH  $ahi,$aj,$m0
245         addc    $lo0,$lo0,$tj   ; ap[j]*bp[i]+tp[j]
246         $UMULL  $nlo,$nj,$m1    ; np[j]*m1
247         addze   $hi0,$hi0
248         $UMULH  $nhi,$nj,$m1
249         addc    $lo1,$lo1,$lo0  ; np[j]*m1+ap[j]*bp[i]+tp[j]
250         addi    $j,$j,$BNSZ     ; j++
251         addze   $hi1,$hi1
252         $ST     $lo1,0($tp)     ; tp[j-1]
253         addi    $tp,$tp,$BNSZ   ; tp++
254         bdnz-   Linner
255 ;Linner
256         $LD     $tj,$BNSZ($tp)  ; tp[j]
257         addc    $lo0,$alo,$hi0
258         addze   $hi0,$ahi
259         addc    $lo0,$lo0,$tj   ; ap[j]*bp[i]+tp[j]
260         addze   $hi0,$hi0
261
262         addc    $lo1,$nlo,$hi1
263         addze   $hi1,$nhi
264         addc    $lo1,$lo1,$lo0  ; np[j]*m1+ap[j]*bp[i]+tp[j]
265         addze   $hi1,$hi1
266         $ST     $lo1,0($tp)     ; tp[j-1]
267
268         addic   $ovf,$ovf,-1    ; move upmost overflow to XER[CA]
269         li      $ovf,0
270         adde    $hi1,$hi1,$hi0
271         addze   $ovf,$ovf
272         $ST     $hi1,$BNSZ($tp)
273 ;
274         slwi    $tj,$num,`log($BNSZ)/log(2)`
275         $UCMP   $i,$tj
276         addi    $i,$i,$BNSZ
277         ble-    Louter
278 \f
279         addi    $num,$num,2     ; restore $num
280         subfc   $j,$j,$j        ; j=0 and "clear" XER[CA]
281         addi    $tp,$sp,$FRAME
282         mtctr   $num
283
284 .align  4
285 Lsub:   $LDX    $tj,$tp,$j
286         $LDX    $nj,$np,$j
287         subfe   $aj,$nj,$tj     ; tp[j]-np[j]
288         $STX    $aj,$rp,$j
289         addi    $j,$j,$BNSZ
290         bdnz-   Lsub
291
292         li      $j,0
293         mtctr   $num
294         subfe   $ovf,$j,$ovf    ; handle upmost overflow bit
295         and     $ap,$tp,$ovf
296         andc    $np,$rp,$ovf
297         or      $ap,$ap,$np     ; ap=borrow?tp:rp
298
299 .align  4
300 Lcopy:                          ; copy or in-place refresh
301         $LDX    $tj,$ap,$j
302         $STX    $tj,$rp,$j
303         $STX    $j,$tp,$j       ; zap at once
304         addi    $j,$j,$BNSZ
305         bdnz-   Lcopy
306
307         $POP    r14,`4*$SIZE_T`($sp)
308         $POP    r15,`5*$SIZE_T`($sp)
309         $POP    r16,`6*$SIZE_T`($sp)
310         $POP    r17,`7*$SIZE_T`($sp)
311         $POP    r18,`8*$SIZE_T`($sp)
312         $POP    r19,`9*$SIZE_T`($sp)
313         $POP    r20,`10*$SIZE_T`($sp)
314         $POP    r21,`11*$SIZE_T`($sp)
315         $POP    r22,`12*$SIZE_T`($sp)
316         $POP    r23,`13*$SIZE_T`($sp)
317         $POP    r24,`14*$SIZE_T`($sp)
318         $POP    r25,`15*$SIZE_T`($sp)
319         $POP    $sp,0($sp)
320         li      r3,1
321         blr
322         .long   0
323 .asciz  "Montgomery Multiplication for PPC, CRYPTOGAMS by <appro\@fy.chalmers.se>"
324 ___
325
326 $code =~ s/\`([^\`]*)\`/eval $1/gem;
327 print $code;
328 close STDOUT;