1238384Sjkim#!/usr/bin/env perl
2238384Sjkim#
3238384Sjkim# ====================================================================
4238384Sjkim# Written by Andy Polyakov <appro@fy.chalmers.se> for the OpenSSL
5238384Sjkim# project. The module is, however, dual licensed under OpenSSL and
6238384Sjkim# CRYPTOGAMS licenses depending on where you obtain it. For further
7238384Sjkim# details see http://www.openssl.org/~appro/cryptogams/.
8238384Sjkim# ====================================================================
9238384Sjkim#
10238384Sjkim# Wrapper around 'rep montmul', VIA-specific instruction accessing
11238384Sjkim# PadLock Montgomery Multiplier. The wrapper is designed as drop-in
12238384Sjkim# replacement for OpenSSL bn_mul_mont [first implemented in 0.9.9].
13238384Sjkim#
14238384Sjkim# Below are interleaved outputs from 'openssl speed rsa dsa' for 4
15238384Sjkim# different software configurations on 1.5GHz VIA Esther processor.
16238384Sjkim# Lines marked with "software integer" denote performance of hand-
17238384Sjkim# coded integer-only assembler found in OpenSSL 0.9.7. "Software SSE2"
18238384Sjkim# refers to hand-coded SSE2 Montgomery multiplication procedure found
19238384Sjkim# OpenSSL 0.9.9. "Hardware VIA SDK" refers to padlock_pmm routine from
20238384Sjkim# Padlock SDK 2.0.1 available for download from VIA, which naturally
21238384Sjkim# utilizes the magic 'repz montmul' instruction. And finally "hardware
22238384Sjkim# this" refers to *this* implementation which also uses 'repz montmul'
23238384Sjkim#
24238384Sjkim#                   sign    verify    sign/s verify/s
25238384Sjkim# rsa  512 bits 0.001720s 0.000140s    581.4   7149.7	software integer
26238384Sjkim# rsa  512 bits 0.000690s 0.000086s   1450.3  11606.0	software SSE2
27238384Sjkim# rsa  512 bits 0.006136s 0.000201s    163.0   4974.5	hardware VIA SDK
28238384Sjkim# rsa  512 bits 0.000712s 0.000050s   1404.9  19858.5	hardware this
29238384Sjkim#
30238384Sjkim# rsa 1024 bits 0.008518s 0.000413s    117.4   2420.8	software integer
31238384Sjkim# rsa 1024 bits 0.004275s 0.000277s    233.9   3609.7	software SSE2
32238384Sjkim# rsa 1024 bits 0.012136s 0.000260s     82.4   3844.5	hardware VIA SDK
33238384Sjkim# rsa 1024 bits 0.002522s 0.000116s    396.5   8650.9	hardware this
34238384Sjkim#
35238384Sjkim# rsa 2048 bits 0.050101s 0.001371s     20.0    729.6	software integer
36238384Sjkim# rsa 2048 bits 0.030273s 0.001008s     33.0    991.9	software SSE2
37238384Sjkim# rsa 2048 bits 0.030833s 0.000976s     32.4   1025.1	hardware VIA SDK
38238384Sjkim# rsa 2048 bits 0.011879s 0.000342s     84.2   2921.7	hardware this
39238384Sjkim#
40238384Sjkim# rsa 4096 bits 0.327097s 0.004859s      3.1    205.8	software integer
41238384Sjkim# rsa 4096 bits 0.229318s 0.003859s      4.4    259.2	software SSE2
42238384Sjkim# rsa 4096 bits 0.233953s 0.003274s      4.3    305.4	hardware VIA SDK
43238384Sjkim# rsa 4096 bits 0.070493s 0.001166s     14.2    857.6	hardware this
44238384Sjkim#
45238384Sjkim# dsa  512 bits 0.001342s 0.001651s    745.2    605.7	software integer
46238384Sjkim# dsa  512 bits 0.000844s 0.000987s   1185.3   1013.1	software SSE2
47238384Sjkim# dsa  512 bits 0.001902s 0.002247s    525.6    444.9	hardware VIA SDK
48238384Sjkim# dsa  512 bits 0.000458s 0.000524s   2182.2   1909.1	hardware this
49238384Sjkim#
50238384Sjkim# dsa 1024 bits 0.003964s 0.004926s    252.3    203.0	software integer
51238384Sjkim# dsa 1024 bits 0.002686s 0.003166s    372.3    315.8	software SSE2
52238384Sjkim# dsa 1024 bits 0.002397s 0.002823s    417.1    354.3	hardware VIA SDK
53238384Sjkim# dsa 1024 bits 0.000978s 0.001170s   1022.2    855.0	hardware this
54238384Sjkim#
55238384Sjkim# dsa 2048 bits 0.013280s 0.016518s     75.3     60.5	software integer
56238384Sjkim# dsa 2048 bits 0.009911s 0.011522s    100.9     86.8	software SSE2
57238384Sjkim# dsa 2048 bits 0.009542s 0.011763s    104.8     85.0	hardware VIA SDK
58238384Sjkim# dsa 2048 bits 0.002884s 0.003352s    346.8    298.3	hardware this
59238384Sjkim#
60238384Sjkim# To give you some other reference point here is output for 2.4GHz P4
61238384Sjkim# running hand-coded SSE2 bn_mul_mont found in 0.9.9, i.e. "software
62238384Sjkim# SSE2" in above terms.
63238384Sjkim#
64238384Sjkim# rsa  512 bits 0.000407s 0.000047s   2454.2  21137.0
65238384Sjkim# rsa 1024 bits 0.002426s 0.000141s    412.1   7100.0
66238384Sjkim# rsa 2048 bits 0.015046s 0.000491s     66.5   2034.9
67238384Sjkim# rsa 4096 bits 0.109770s 0.002379s      9.1    420.3
68238384Sjkim# dsa  512 bits 0.000438s 0.000525s   2281.1   1904.1
69238384Sjkim# dsa 1024 bits 0.001346s 0.001595s    742.7    627.0
70238384Sjkim# dsa 2048 bits 0.004745s 0.005582s    210.7    179.1
71238384Sjkim#
72238384Sjkim# Conclusions:
73238384Sjkim# - VIA SDK leaves a *lot* of room for improvement (which this
74238384Sjkim#   implementation successfully fills:-);
75238384Sjkim# - 'rep montmul' gives up to >3x performance improvement depending on
76238384Sjkim#   key length;
77238384Sjkim# - in terms of absolute performance it delivers approximately as much
78238384Sjkim#   as modern out-of-order 32-bit cores [again, for longer keys].
79238384Sjkim
80238384Sjkim$0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
81238384Sjkimpush(@INC,"${dir}","${dir}../../perlasm");
82238384Sjkimrequire "x86asm.pl";
83238384Sjkim
84238384Sjkim&asm_init($ARGV[0],"via-mont.pl");
85238384Sjkim
86238384Sjkim# 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);
87238384Sjkim$func="bn_mul_mont_padlock";
88238384Sjkim
89238384Sjkim$pad=16*1;	# amount of reserved bytes on top of every vector
90238384Sjkim
91238384Sjkim# stack layout
92238384Sjkim$mZeroPrime=&DWP(0,"esp");		# these are specified by VIA
93238384Sjkim$A=&DWP(4,"esp");
94238384Sjkim$B=&DWP(8,"esp");
95238384Sjkim$T=&DWP(12,"esp");
96238384Sjkim$M=&DWP(16,"esp");
97238384Sjkim$scratch=&DWP(20,"esp");
98238384Sjkim$rp=&DWP(24,"esp");			# these are mine
99238384Sjkim$sp=&DWP(28,"esp");
100238384Sjkim# &DWP(32,"esp")			# 32 byte scratch area
101238384Sjkim# &DWP(64+(4*$num+$pad)*0,"esp")	# padded tp[num]
102238384Sjkim# &DWP(64+(4*$num+$pad)*1,"esp")	# padded copy of ap[num]
103238384Sjkim# &DWP(64+(4*$num+$pad)*2,"esp")	# padded copy of bp[num]
104238384Sjkim# &DWP(64+(4*$num+$pad)*3,"esp")	# padded copy of np[num]
105238384Sjkim# Note that SDK suggests to unconditionally allocate 2K per vector. This
106238384Sjkim# has quite an impact on performance. It naturally depends on key length,
107238384Sjkim# but to give an example 1024 bit private RSA key operations suffer >30%
108238384Sjkim# penalty. I allocate only as much as actually required...
109238384Sjkim
110238384Sjkim&function_begin($func);
111238384Sjkim	&xor	("eax","eax");
112238384Sjkim	&mov	("ecx",&wparam(5));	# num
113238384Sjkim	# meet VIA's limitations for num [note that the specification
114238384Sjkim	# expresses them in bits, while we work with amount of 32-bit words]
115238384Sjkim	&test	("ecx",3);
116238384Sjkim	&jnz	(&label("leave"));	# num % 4 != 0
117238384Sjkim	&cmp	("ecx",8);
118238384Sjkim	&jb	(&label("leave"));	# num < 8
119238384Sjkim	&cmp	("ecx",1024);
120238384Sjkim	&ja	(&label("leave"));	# num > 1024
121238384Sjkim
122238384Sjkim	&pushf	();
123238384Sjkim	&cld	();
124238384Sjkim
125238384Sjkim	&mov	("edi",&wparam(0));	# rp
126238384Sjkim	&mov	("eax",&wparam(1));	# ap
127238384Sjkim	&mov	("ebx",&wparam(2));	# bp
128238384Sjkim	&mov	("edx",&wparam(3));	# np
129238384Sjkim	&mov	("esi",&wparam(4));	# n0
130238384Sjkim	&mov	("esi",&DWP(0,"esi"));	# *n0
131238384Sjkim
132238384Sjkim	&lea	("ecx",&DWP($pad,"","ecx",4));	# ecx becomes vector size in bytes
133238384Sjkim	&lea	("ebp",&DWP(64,"","ecx",4));	# allocate 4 vectors + 64 bytes
134238384Sjkim	&neg	("ebp");
135238384Sjkim	&add	("ebp","esp");
136238384Sjkim	&and	("ebp",-64);		# align to cache-line
137238384Sjkim	&xchg	("ebp","esp");		# alloca
138238384Sjkim
139238384Sjkim	&mov	($rp,"edi");		# save rp
140238384Sjkim	&mov	($sp,"ebp");		# save esp
141238384Sjkim
142238384Sjkim	&mov	($mZeroPrime,"esi");
143238384Sjkim	&lea	("esi",&DWP(64,"esp"));	# tp
144238384Sjkim	&mov	($T,"esi");
145238384Sjkim	&lea	("edi",&DWP(32,"esp"));	# scratch area
146238384Sjkim	&mov	($scratch,"edi");
147238384Sjkim	&mov	("esi","eax");
148238384Sjkim
149238384Sjkim	&lea	("ebp",&DWP(-$pad,"ecx"));
150238384Sjkim	&shr	("ebp",2);		# restore original num value in ebp
151238384Sjkim
152238384Sjkim	&xor	("eax","eax");
153238384Sjkim
154238384Sjkim	&mov	("ecx","ebp");
155238384Sjkim	&lea	("ecx",&DWP((32+$pad)/4,"ecx"));# padded tp + scratch
156238384Sjkim	&data_byte(0xf3,0xab);		# rep stosl, bzero
157238384Sjkim
158238384Sjkim	&mov	("ecx","ebp");
159238384Sjkim	&lea	("edi",&DWP(64+$pad,"esp","ecx",4));# pointer to ap copy
160238384Sjkim	&mov	($A,"edi");
161238384Sjkim	&data_byte(0xf3,0xa5);		# rep movsl, memcpy
162238384Sjkim	&mov	("ecx",$pad/4);
163238384Sjkim	&data_byte(0xf3,0xab);		# rep stosl, bzero pad
164238384Sjkim	# edi points at the end of padded ap copy...
165238384Sjkim
166238384Sjkim	&mov	("ecx","ebp");
167238384Sjkim	&mov	("esi","ebx");
168238384Sjkim	&mov	($B,"edi");
169238384Sjkim	&data_byte(0xf3,0xa5);		# rep movsl, memcpy
170238384Sjkim	&mov	("ecx",$pad/4);
171238384Sjkim	&data_byte(0xf3,0xab);		# rep stosl, bzero pad
172238384Sjkim	# edi points at the end of padded bp copy...
173238384Sjkim
174238384Sjkim	&mov	("ecx","ebp");
175238384Sjkim	&mov	("esi","edx");
176238384Sjkim	&mov	($M,"edi");
177238384Sjkim	&data_byte(0xf3,0xa5);		# rep movsl, memcpy
178238384Sjkim	&mov	("ecx",$pad/4);
179238384Sjkim	&data_byte(0xf3,0xab);		# rep stosl, bzero pad
180238384Sjkim	# edi points at the end of padded np copy...
181238384Sjkim
182238384Sjkim	# let magic happen...
183238384Sjkim	&mov	("ecx","ebp");
184238384Sjkim	&mov	("esi","esp");
185238384Sjkim	&shl	("ecx",5);		# convert word counter to bit counter
186238384Sjkim	&align	(4);
187238384Sjkim	&data_byte(0xf3,0x0f,0xa6,0xc0);# rep montmul
188238384Sjkim
189238384Sjkim	&mov	("ecx","ebp");
190238384Sjkim	&lea	("esi",&DWP(64,"esp"));		# tp
191238384Sjkim	# edi still points at the end of padded np copy...
192238384Sjkim	&neg	("ebp");
193238384Sjkim	&lea	("ebp",&DWP(-$pad,"edi","ebp",4));	# so just "rewind"
194238384Sjkim	&mov	("edi",$rp);			# restore rp
195238384Sjkim	&xor	("edx","edx");			# i=0 and clear CF
196238384Sjkim
197238384Sjkim&set_label("sub",8);
198238384Sjkim	&mov	("eax",&DWP(0,"esi","edx",4));
199238384Sjkim	&sbb	("eax",&DWP(0,"ebp","edx",4));
200238384Sjkim	&mov	(&DWP(0,"edi","edx",4),"eax");	# rp[i]=tp[i]-np[i]
201238384Sjkim	&lea	("edx",&DWP(1,"edx"));		# i++
202238384Sjkim	&loop	(&label("sub"));		# doesn't affect CF!
203238384Sjkim
204238384Sjkim	&mov	("eax",&DWP(0,"esi","edx",4));	# upmost overflow bit
205238384Sjkim	&sbb	("eax",0);
206238384Sjkim	&and	("esi","eax");
207238384Sjkim	&not	("eax");
208238384Sjkim	&mov	("ebp","edi");
209238384Sjkim	&and	("ebp","eax");
210238384Sjkim	&or	("esi","ebp");			# tp=carry?tp:rp
211238384Sjkim
212238384Sjkim	&mov	("ecx","edx");			# num
213238384Sjkim	&xor	("edx","edx");			# i=0
214238384Sjkim
215238384Sjkim&set_label("copy",8);
216238384Sjkim	&mov	("eax",&DWP(0,"esi","edx",4));
217238384Sjkim	&mov	(&DWP(64,"esp","edx",4),"ecx");	# zap tp
218238384Sjkim	&mov	(&DWP(0,"edi","edx",4),"eax");
219238384Sjkim	&lea	("edx",&DWP(1,"edx"));		# i++
220238384Sjkim	&loop	(&label("copy"));
221238384Sjkim
222238384Sjkim	&mov	("ebp",$sp);
223238384Sjkim	&xor	("eax","eax");
224238384Sjkim
225238384Sjkim	&mov	("ecx",64/4);
226238384Sjkim	&mov	("edi","esp");		# zap frame including scratch area
227238384Sjkim	&data_byte(0xf3,0xab);		# rep stosl, bzero
228238384Sjkim
229238384Sjkim	# zap copies of ap, bp and np
230238384Sjkim	&lea	("edi",&DWP(64+$pad,"esp","edx",4));# pointer to ap
231238384Sjkim	&lea	("ecx",&DWP(3*$pad/4,"edx","edx",2));
232238384Sjkim	&data_byte(0xf3,0xab);		# rep stosl, bzero
233238384Sjkim
234238384Sjkim	&mov	("esp","ebp");
235238384Sjkim	&inc	("eax");		# signal "done"
236238384Sjkim	&popf	();
237238384Sjkim&set_label("leave");
238238384Sjkim&function_end($func);
239238384Sjkim
240238384Sjkim&asciz("Padlock Montgomery Multiplication, CRYPTOGAMS by <appro\@openssl.org>");
241238384Sjkim
242238384Sjkim&asm_finish();
243