Update to new home page
[openssl.git] / crypto / bn / asm / armv4-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 # January 2007.
11
12 # Montgomery multiplication for ARMv4.
13 #
14 # Performance improvement naturally varies among CPU implementations
15 # and compilers. The code was observed to provide +65-35% improvement
16 # [depending on key length, less for longer keys] on ARM920T, and
17 # +115-80% on Intel IXP425. This is compared to pre-bn_mul_mont code
18 # base and compiler generated code with in-lined umull and even umlal
19 # instructions. The latter means that this code didn't really have an 
20 # "advantage" of utilizing some "secret" instruction.
21 #
22 # The code is interoperable with Thumb ISA and is rather compact, less
23 # than 1/2KB. Windows CE port would be trivial, as it's exclusively
24 # about decorations, ABI and instruction syntax are identical.
25
26 $num="r0";      # starts as num argument, but holds &tp[num-1]
27 $ap="r1";
28 $bp="r2"; $bi="r2"; $rp="r2";
29 $np="r3";
30 $tp="r4";
31 $aj="r5";
32 $nj="r6";
33 $tj="r7";
34 $n0="r8";
35 ###########     # r9 is reserved by ELF as platform specific, e.g. TLS pointer
36 $alo="r10";     # sl, gcc uses it to keep @GOT
37 $ahi="r11";     # fp
38 $nlo="r12";     # ip
39 ###########     # r13 is stack pointer
40 $nhi="r14";     # lr
41 ###########     # r15 is program counter
42
43 #### argument block layout relative to &tp[num-1], a.k.a. $num
44 $_rp="$num,#12*4";
45 # ap permanently resides in r1
46 $_bp="$num,#13*4";
47 # np permanently resides in r3
48 $_n0="$num,#14*4";
49 $_num="$num,#15*4";     $_bpend=$_num;
50
51 $code=<<___;
52 .text
53
54 .global bn_mul_mont
55 .type   bn_mul_mont,%function
56
57 .align  2
58 bn_mul_mont:
59         stmdb   sp!,{r0,r2}             @ sp points at argument block
60         ldr     $num,[sp,#3*4]          @ load num
61         cmp     $num,#2
62         movlt   r0,#0
63         addlt   sp,sp,#2*4
64         blt     .Labort
65
66         stmdb   sp!,{r4-r12,lr}         @ save 10 registers
67
68         mov     $num,$num,lsl#2         @ rescale $num for byte count
69         sub     sp,sp,$num              @ alloca(4*num)
70         sub     sp,sp,#4                @ +extra dword
71         sub     $num,$num,#4            @ "num=num-1"
72         add     $tp,$bp,$num            @ &bp[num-1]
73
74         add     $num,sp,$num            @ $num to point at &tp[num-1]
75         ldr     $n0,[$_n0]              @ &n0
76         ldr     $bi,[$bp]               @ bp[0]
77         ldr     $aj,[$ap],#4            @ ap[0],ap++
78         ldr     $nj,[$np],#4            @ np[0],np++
79         ldr     $n0,[$n0]               @ *n0
80         str     $tp,[$_bpend]           @ save &bp[num]
81
82         umull   $alo,$ahi,$aj,$bi       @ ap[0]*bp[0]
83         str     $n0,[$_n0]              @ save n0 value
84         mul     $n0,$alo,$n0            @ "tp[0]"*n0
85         mov     $nlo,#0
86         umlal   $alo,$nlo,$nj,$n0       @ np[0]*n0+"t[0]"
87         mov     $tp,sp
88
89 .L1st:
90         ldr     $aj,[$ap],#4            @ ap[j],ap++
91         mov     $alo,$ahi
92         mov     $ahi,#0
93         umlal   $alo,$ahi,$aj,$bi       @ ap[j]*bp[0]
94         ldr     $nj,[$np],#4            @ np[j],np++
95         mov     $nhi,#0
96         umlal   $nlo,$nhi,$nj,$n0       @ np[j]*n0
97         adds    $nlo,$nlo,$alo
98         str     $nlo,[$tp],#4           @ tp[j-1]=,tp++
99         adc     $nlo,$nhi,#0
100         cmp     $tp,$num
101         bne     .L1st
102
103         adds    $nlo,$nlo,$ahi
104         mov     $nhi,#0
105         adc     $nhi,$nhi,#0
106         ldr     $tp,[$_bp]              @ restore bp
107         str     $nlo,[$num]             @ tp[num-1]=
108         ldr     $n0,[$_n0]              @ restore n0
109         str     $nhi,[$num,#4]          @ tp[num]=
110 \f
111 .Louter:
112         sub     $tj,$num,sp             @ "original" $num-1 value
113         sub     $ap,$ap,$tj             @ "rewind" ap to &ap[1]
114         sub     $np,$np,$tj             @ "rewind" np to &np[1]
115         ldr     $bi,[$tp,#4]!           @ *(++bp)
116         ldr     $aj,[$ap,#-4]           @ ap[0]
117         ldr     $nj,[$np,#-4]           @ np[0]
118         ldr     $alo,[sp]               @ tp[0]
119         ldr     $tj,[sp,#4]             @ tp[1]
120
121         mov     $ahi,#0
122         umlal   $alo,$ahi,$aj,$bi       @ ap[0]*bp[i]+tp[0]
123         str     $tp,[$_bp]              @ save bp
124         mul     $n0,$alo,$n0
125         mov     $nlo,#0
126         umlal   $alo,$nlo,$nj,$n0       @ np[0]*n0+"tp[0]"
127         mov     $tp,sp
128
129 .Linner:
130         ldr     $aj,[$ap],#4            @ ap[j],ap++
131         adds    $alo,$ahi,$tj           @ +=tp[j]
132         mov     $ahi,#0
133         umlal   $alo,$ahi,$aj,$bi       @ ap[j]*bp[i]
134         ldr     $nj,[$np],#4            @ np[j],np++
135         mov     $nhi,#0
136         umlal   $nlo,$nhi,$nj,$n0       @ np[j]*n0
137         ldr     $tj,[$tp,#8]            @ tp[j+1]
138         adc     $ahi,$ahi,#0
139         adds    $nlo,$nlo,$alo
140         str     $nlo,[$tp],#4           @ tp[j-1]=,tp++
141         adc     $nlo,$nhi,#0
142         cmp     $tp,$num
143         bne     .Linner
144
145         adds    $nlo,$nlo,$ahi
146         mov     $nhi,#0
147         adc     $nhi,$nhi,#0
148         adds    $nlo,$nlo,$tj
149         adc     $nhi,$nhi,#0
150         ldr     $tp,[$_bp]              @ restore bp
151         ldr     $tj,[$_bpend]           @ restore &bp[num]
152         str     $nlo,[$num]             @ tp[num-1]=
153         ldr     $n0,[$_n0]              @ restore n0
154         str     $nhi,[$num,#4]          @ tp[num]=
155
156         cmp     $tp,$tj
157         bne     .Louter
158 \f
159         ldr     $rp,[$_rp]              @ pull rp
160         add     $num,$num,#4            @ $num to point at &tp[num]
161         sub     $aj,$num,sp             @ "original" num value
162         mov     $tp,sp                  @ "rewind" $tp
163         sub     $np,$np,$aj             @ "rewind" $np to &np[0]
164
165         cmp     $nhi,#0                 @ upmost carry
166         bne     .Lsub
167         cmp     $nlo,$nj                @ tp[num-1]-np[num-1]
168         bhs     .Lsub
169
170 .Lcopy: ldr     $tj,[$tp]
171         str     sp,[$tp],#4             @ zap tp
172         str     $tj,[$rp],#4
173         cmp     $tp,$num
174         bne     .Lcopy
175
176 .Lexit: add     sp,$num,#4              @ skip over tp[num+1]
177         ldmia   sp!,{r4-r12,lr}         @ restore registers
178         add     sp,sp,#2*4              @ skip over {r0,r2}
179         mov     r0,#1
180 .Labort:tst     lr,#1
181         moveq   pc,lr                   @ be binary compatible with V4, yet
182         bx      lr                      @ interoperable with Thumb ISA:-)
183
184 .Lsub:  ldr     $tj,[$tp],#4
185         ldr     $nj,[$np],#4
186         sbcs    $tj,$tj,$nj             @ tp[j]-np[j]
187         str     $tj,[$rp],#4            @ rp[j]=
188         teq     $tp,$num                @ preserve carry
189         bne     .Lsub
190         sbcs    $nhi,$nhi,#0            @ upmost carry
191         mov     $tp,sp                  @ "rewind" $tp
192         sub     $rp,$rp,$aj             @ "rewind" $rp
193         blo     .Lcopy                  @ tp was less after all
194
195 .Lzap:  str     sp,[$tp],#4
196         cmp     $tp,$num
197         bne     .Lzap
198         bal     .Lexit
199 .size   bn_mul_mont,.-bn_mul_mont
200 .asciz  "Montgomery multiplication for ARMv4, CRYPTOGAMS by <appro\@openssl.org>"
201 ___
202
203 print $code;
204 close STDOUT;