OLD | NEW |
| (Empty) |
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 # Wrapper around 'rep montmul', VIA-specific instruction accessing | |
11 # PadLock Montgomery Multiplier. The wrapper is designed as drop-in | |
12 # replacement for OpenSSL bn_mul_mont [first implemented in 0.9.9]. | |
13 # | |
14 # Below are interleaved outputs from 'openssl speed rsa dsa' for 4 | |
15 # different software configurations on 1.5GHz VIA Esther processor. | |
16 # Lines marked with "software integer" denote performance of hand- | |
17 # coded integer-only assembler found in OpenSSL 0.9.7. "Software SSE2" | |
18 # refers to hand-coded SSE2 Montgomery multiplication procedure found | |
19 # OpenSSL 0.9.9. "Hardware VIA SDK" refers to padlock_pmm routine from | |
20 # Padlock SDK 2.0.1 available for download from VIA, which naturally | |
21 # utilizes the magic 'repz montmul' instruction. And finally "hardware | |
22 # this" refers to *this* implementation which also uses 'repz montmul' | |
23 # | |
24 # sign verify sign/s verify/s | |
25 # rsa 512 bits 0.001720s 0.000140s 581.4 7149.7 software integer | |
26 # rsa 512 bits 0.000690s 0.000086s 1450.3 11606.0 software SSE2 | |
27 # rsa 512 bits 0.006136s 0.000201s 163.0 4974.5 hardware VIA SDK | |
28 # rsa 512 bits 0.000712s 0.000050s 1404.9 19858.5 hardware this | |
29 # | |
30 # rsa 1024 bits 0.008518s 0.000413s 117.4 2420.8 software integer | |
31 # rsa 1024 bits 0.004275s 0.000277s 233.9 3609.7 software SSE2 | |
32 # rsa 1024 bits 0.012136s 0.000260s 82.4 3844.5 hardware VIA SDK | |
33 # rsa 1024 bits 0.002522s 0.000116s 396.5 8650.9 hardware this | |
34 # | |
35 # rsa 2048 bits 0.050101s 0.001371s 20.0 729.6 software integer | |
36 # rsa 2048 bits 0.030273s 0.001008s 33.0 991.9 software SSE2 | |
37 # rsa 2048 bits 0.030833s 0.000976s 32.4 1025.1 hardware VIA SDK | |
38 # rsa 2048 bits 0.011879s 0.000342s 84.2 2921.7 hardware this | |
39 # | |
40 # rsa 4096 bits 0.327097s 0.004859s 3.1 205.8 software integer | |
41 # rsa 4096 bits 0.229318s 0.003859s 4.4 259.2 software SSE2 | |
42 # rsa 4096 bits 0.233953s 0.003274s 4.3 305.4 hardware VIA SDK | |
43 # rsa 4096 bits 0.070493s 0.001166s 14.2 857.6 hardware this | |
44 # | |
45 # dsa 512 bits 0.001342s 0.001651s 745.2 605.7 software integer | |
46 # dsa 512 bits 0.000844s 0.000987s 1185.3 1013.1 software SSE2 | |
47 # dsa 512 bits 0.001902s 0.002247s 525.6 444.9 hardware VIA SDK | |
48 # dsa 512 bits 0.000458s 0.000524s 2182.2 1909.1 hardware this | |
49 # | |
50 # dsa 1024 bits 0.003964s 0.004926s 252.3 203.0 software integer | |
51 # dsa 1024 bits 0.002686s 0.003166s 372.3 315.8 software SSE2 | |
52 # dsa 1024 bits 0.002397s 0.002823s 417.1 354.3 hardware VIA SDK | |
53 # dsa 1024 bits 0.000978s 0.001170s 1022.2 855.0 hardware this | |
54 # | |
55 # dsa 2048 bits 0.013280s 0.016518s 75.3 60.5 software integer | |
56 # dsa 2048 bits 0.009911s 0.011522s 100.9 86.8 software SSE2 | |
57 # dsa 2048 bits 0.009542s 0.011763s 104.8 85.0 hardware VIA SDK | |
58 # dsa 2048 bits 0.002884s 0.003352s 346.8 298.3 hardware this | |
59 # | |
60 # To give you some other reference point here is output for 2.4GHz P4 | |
61 # running hand-coded SSE2 bn_mul_mont found in 0.9.9, i.e. "software | |
62 # SSE2" in above terms. | |
63 # | |
64 # rsa 512 bits 0.000407s 0.000047s 2454.2 21137.0 | |
65 # rsa 1024 bits 0.002426s 0.000141s 412.1 7100.0 | |
66 # rsa 2048 bits 0.015046s 0.000491s 66.5 2034.9 | |
67 # rsa 4096 bits 0.109770s 0.002379s 9.1 420.3 | |
68 # dsa 512 bits 0.000438s 0.000525s 2281.1 1904.1 | |
69 # dsa 1024 bits 0.001346s 0.001595s 742.7 627.0 | |
70 # dsa 2048 bits 0.004745s 0.005582s 210.7 179.1 | |
71 # | |
72 # Conclusions: | |
73 # - VIA SDK leaves a *lot* of room for improvement (which this | |
74 # implementation successfully fills:-); | |
75 # - 'rep montmul' gives up to >3x performance improvement depending on | |
76 # key length; | |
77 # - in terms of absolute performance it delivers approximately as much | |
78 # as modern out-of-order 32-bit cores [again, for longer keys]. | |
79 | |
80 $0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1; | |
81 push(@INC,"${dir}","${dir}../../perlasm"); | |
82 require "x86asm.pl"; | |
83 | |
84 &asm_init($ARGV[0],"via-mont.pl"); | |
85 | |
86 # int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp, const BN
_ULONG *np,const BN_ULONG *n0, int num); | |
87 $func="bn_mul_mont_padlock"; | |
88 | |
89 $pad=16*1; # amount of reserved bytes on top of every vector | |
90 | |
91 # stack layout | |
92 $mZeroPrime=&DWP(0,"esp"); # these are specified by VIA | |
93 $A=&DWP(4,"esp"); | |
94 $B=&DWP(8,"esp"); | |
95 $T=&DWP(12,"esp"); | |
96 $M=&DWP(16,"esp"); | |
97 $scratch=&DWP(20,"esp"); | |
98 $rp=&DWP(24,"esp"); # these are mine | |
99 $sp=&DWP(28,"esp"); | |
100 # &DWP(32,"esp") # 32 byte scratch area | |
101 # &DWP(64+(4*$num+$pad)*0,"esp") # padded tp[num] | |
102 # &DWP(64+(4*$num+$pad)*1,"esp") # padded copy of ap[num] | |
103 # &DWP(64+(4*$num+$pad)*2,"esp") # padded copy of bp[num] | |
104 # &DWP(64+(4*$num+$pad)*3,"esp") # padded copy of np[num] | |
105 # Note that SDK suggests to unconditionally allocate 2K per vector. This | |
106 # has quite an impact on performance. It naturally depends on key length, | |
107 # but to give an example 1024 bit private RSA key operations suffer >30% | |
108 # penalty. I allocate only as much as actually required... | |
109 | |
110 &function_begin($func); | |
111 &xor ("eax","eax"); | |
112 &mov ("ecx",&wparam(5)); # num | |
113 # meet VIA's limitations for num [note that the specification | |
114 # expresses them in bits, while we work with amount of 32-bit words] | |
115 &test ("ecx",3); | |
116 &jnz (&label("leave")); # num % 4 != 0 | |
117 &cmp ("ecx",8); | |
118 &jb (&label("leave")); # num < 8 | |
119 &cmp ("ecx",1024); | |
120 &ja (&label("leave")); # num > 1024 | |
121 | |
122 &pushf (); | |
123 &cld (); | |
124 | |
125 &mov ("edi",&wparam(0)); # rp | |
126 &mov ("eax",&wparam(1)); # ap | |
127 &mov ("ebx",&wparam(2)); # bp | |
128 &mov ("edx",&wparam(3)); # np | |
129 &mov ("esi",&wparam(4)); # n0 | |
130 &mov ("esi",&DWP(0,"esi")); # *n0 | |
131 | |
132 &lea ("ecx",&DWP($pad,"","ecx",4)); # ecx becomes vector size in byt
es | |
133 &lea ("ebp",&DWP(64,"","ecx",4)); # allocate 4 vectors + 64 bytes | |
134 &neg ("ebp"); | |
135 &add ("ebp","esp"); | |
136 &and ("ebp",-64); # align to cache-line | |
137 &xchg ("ebp","esp"); # alloca | |
138 | |
139 &mov ($rp,"edi"); # save rp | |
140 &mov ($sp,"ebp"); # save esp | |
141 | |
142 &mov ($mZeroPrime,"esi"); | |
143 &lea ("esi",&DWP(64,"esp")); # tp | |
144 &mov ($T,"esi"); | |
145 &lea ("edi",&DWP(32,"esp")); # scratch area | |
146 &mov ($scratch,"edi"); | |
147 &mov ("esi","eax"); | |
148 | |
149 &lea ("ebp",&DWP(-$pad,"ecx")); | |
150 &shr ("ebp",2); # restore original num value in ebp | |
151 | |
152 &xor ("eax","eax"); | |
153 | |
154 &mov ("ecx","ebp"); | |
155 &lea ("ecx",&DWP((32+$pad)/4,"ecx"));# padded tp + scratch | |
156 &data_byte(0xf3,0xab); # rep stosl, bzero | |
157 | |
158 &mov ("ecx","ebp"); | |
159 &lea ("edi",&DWP(64+$pad,"esp","ecx",4));# pointer to ap copy | |
160 &mov ($A,"edi"); | |
161 &data_byte(0xf3,0xa5); # rep movsl, memcpy | |
162 &mov ("ecx",$pad/4); | |
163 &data_byte(0xf3,0xab); # rep stosl, bzero pad | |
164 # edi points at the end of padded ap copy... | |
165 | |
166 &mov ("ecx","ebp"); | |
167 &mov ("esi","ebx"); | |
168 &mov ($B,"edi"); | |
169 &data_byte(0xf3,0xa5); # rep movsl, memcpy | |
170 &mov ("ecx",$pad/4); | |
171 &data_byte(0xf3,0xab); # rep stosl, bzero pad | |
172 # edi points at the end of padded bp copy... | |
173 | |
174 &mov ("ecx","ebp"); | |
175 &mov ("esi","edx"); | |
176 &mov ($M,"edi"); | |
177 &data_byte(0xf3,0xa5); # rep movsl, memcpy | |
178 &mov ("ecx",$pad/4); | |
179 &data_byte(0xf3,0xab); # rep stosl, bzero pad | |
180 # edi points at the end of padded np copy... | |
181 | |
182 # let magic happen... | |
183 &mov ("ecx","ebp"); | |
184 &mov ("esi","esp"); | |
185 &shl ("ecx",5); # convert word counter to bit counter | |
186 &align (4); | |
187 &data_byte(0xf3,0x0f,0xa6,0xc0);# rep montmul | |
188 | |
189 &mov ("ecx","ebp"); | |
190 &lea ("esi",&DWP(64,"esp")); # tp | |
191 # edi still points at the end of padded np copy... | |
192 &neg ("ebp"); | |
193 &lea ("ebp",&DWP(-$pad,"edi","ebp",4)); # so just "rewind" | |
194 &mov ("edi",$rp); # restore rp | |
195 &xor ("edx","edx"); # i=0 and clear CF | |
196 | |
197 &set_label("sub",8); | |
198 &mov ("eax",&DWP(0,"esi","edx",4)); | |
199 &sbb ("eax",&DWP(0,"ebp","edx",4)); | |
200 &mov (&DWP(0,"edi","edx",4),"eax"); # rp[i]=tp[i]-np[i] | |
201 &lea ("edx",&DWP(1,"edx")); # i++ | |
202 &loop (&label("sub")); # doesn't affect CF! | |
203 | |
204 &mov ("eax",&DWP(0,"esi","edx",4)); # upmost overflow bit | |
205 &sbb ("eax",0); | |
206 &and ("esi","eax"); | |
207 ¬ ("eax"); | |
208 &mov ("ebp","edi"); | |
209 &and ("ebp","eax"); | |
210 &or ("esi","ebp"); # tp=carry?tp:rp | |
211 | |
212 &mov ("ecx","edx"); # num | |
213 &xor ("edx","edx"); # i=0 | |
214 | |
215 &set_label("copy",8); | |
216 &mov ("eax",&DWP(0,"esi","edx",4)); | |
217 &mov (&DWP(64,"esp","edx",4),"ecx"); # zap tp | |
218 &mov (&DWP(0,"edi","edx",4),"eax"); | |
219 &lea ("edx",&DWP(1,"edx")); # i++ | |
220 &loop (&label("copy")); | |
221 | |
222 &mov ("ebp",$sp); | |
223 &xor ("eax","eax"); | |
224 | |
225 &mov ("ecx",64/4); | |
226 &mov ("edi","esp"); # zap frame including scratch area | |
227 &data_byte(0xf3,0xab); # rep stosl, bzero | |
228 | |
229 # zap copies of ap, bp and np | |
230 &lea ("edi",&DWP(64+$pad,"esp","edx",4));# pointer to ap | |
231 &lea ("ecx",&DWP(3*$pad/4,"edx","edx",2)); | |
232 &data_byte(0xf3,0xab); # rep stosl, bzero | |
233 | |
234 &mov ("esp","ebp"); | |
235 &inc ("eax"); # signal "done" | |
236 &popf (); | |
237 &set_label("leave"); | |
238 &function_end($func); | |
239 | |
240 &asciz("Padlock Montgomery Multiplication, CRYPTOGAMS by <appro\@openssl.org>"); | |
241 | |
242 &asm_finish(); | |
OLD | NEW |