x86-gf2m.pl revision 291721 
1#!/usr/bin/env perl
2#
3# ====================================================================
4# Written by Andy Polyakov <appro@openssl.org> 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# May 2011
11#
12# The module implements bn_GF2m_mul_2x2 polynomial multiplication used
13# in bn_gf2m.c. It's kind of low-hanging mechanical port from C for
14# the time being... Except that it has three code paths: pure integer
15# code suitable for any x86 CPU, MMX code suitable for PIII and later
16# and PCLMULQDQ suitable for Westmere and later. Improvement varies
17# from one benchmark and ��-arch to another. Below are interval values
18# for 163- and 571-bit ECDH benchmarks relative to compiler-generated
19# code:
20#
21# PIII		16%-30%
22# P4		12%-12%
23# Opteron	18%-40%
24# Core2		19%-44%
25# Atom		38%-64%
26# Westmere	53%-121%(PCLMULQDQ)/20%-32%(MMX)
27# Sandy Bridge	72%-127%(PCLMULQDQ)/27%-23%(MMX)
28#
29# Note that above improvement coefficients are not coefficients for
30# bn_GF2m_mul_2x2 itself. For example 120% ECDH improvement is result
31# of bn_GF2m_mul_2x2 being >4x faster. As it gets faster, benchmark
32# is more and more dominated by other subroutines, most notably by
33# BN_GF2m_mod[_mul]_arr...
34
35$0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
36push(@INC,"${dir}","${dir}../../perlasm");
37require "x86asm.pl";
38
39&asm_init($ARGV[0],$0,$x86only = $ARGV[$#ARGV] eq "386");
40
41$sse2=0;
42for (@ARGV) { $sse2=1 if (/-DOPENSSL_IA32_SSE2/); }
43
44&external_label("OPENSSL_ia32cap_P") if ($sse2);
45
46$a="eax";
47$b="ebx";
48($a1,$a2,$a4)=("ecx","edx","ebp");
49
50$R="mm0";
51@T=("mm1","mm2");
52($A,$B,$B30,$B31)=("mm2","mm3","mm4","mm5");
53@i=("esi","edi");
54
55					if (!$x86only) {
56&function_begin_B("_mul_1x1_mmx");
57	&sub	("esp",32+4);
58	 &mov	($a1,$a);
59	 &lea	($a2,&DWP(0,$a,$a));
60	 &and	($a1,0x3fffffff);
61	 &lea	($a4,&DWP(0,$a2,$a2));
62	 &mov	(&DWP(0*4,"esp"),0);
63	 &and	($a2,0x7fffffff);
64	&movd	($A,$a);
65	&movd	($B,$b);
66	 &mov	(&DWP(1*4,"esp"),$a1);	# a1
67	 &xor	($a1,$a2);		# a1^a2
68	&pxor	($B31,$B31);
69	&pxor	($B30,$B30);
70	 &mov	(&DWP(2*4,"esp"),$a2);	# a2
71	 &xor	($a2,$a4);		# a2^a4
72	 &mov	(&DWP(3*4,"esp"),$a1);	# a1^a2
73	&pcmpgtd($B31,$A);		# broadcast 31st bit
74	&paddd	($A,$A);		# $A<<=1
75	 &xor	($a1,$a2);		# a1^a4=a1^a2^a2^a4
76	 &mov	(&DWP(4*4,"esp"),$a4);	# a4
77	 &xor	($a4,$a2);		# a2=a4^a2^a4
78	&pand	($B31,$B);
79	&pcmpgtd($B30,$A);		# broadcast 30th bit
80	 &mov	(&DWP(5*4,"esp"),$a1);	# a1^a4
81	 &xor	($a4,$a1);		# a1^a2^a4
82	&psllq	($B31,31);
83	&pand	($B30,$B);
84	 &mov	(&DWP(6*4,"esp"),$a2);	# a2^a4
85	&mov	(@i[0],0x7);
86	 &mov	(&DWP(7*4,"esp"),$a4);	# a1^a2^a4
87	 &mov	($a4,@i[0]);
88	&and	(@i[0],$b);
89	&shr	($b,3);
90	&mov	(@i[1],$a4);
91	&psllq	($B30,30);
92	&and	(@i[1],$b);
93	&shr	($b,3);
94	&movd	($R,&DWP(0,"esp",@i[0],4));
95	&mov	(@i[0],$a4);
96	&and	(@i[0],$b);
97	&shr	($b,3);
98	for($n=1;$n<9;$n++) {
99		&movd	(@T[1],&DWP(0,"esp",@i[1],4));
100		&mov	(@i[1],$a4);
101		&psllq	(@T[1],3*$n);
102		&and	(@i[1],$b);
103		&shr	($b,3);
104		&pxor	($R,@T[1]);
105
106		push(@i,shift(@i)); push(@T,shift(@T));
107	}
108	&movd	(@T[1],&DWP(0,"esp",@i[1],4));
109	&pxor	($R,$B30);
110	&psllq	(@T[1],3*$n++);
111	&pxor	($R,@T[1]);
112
113	&movd	(@T[0],&DWP(0,"esp",@i[0],4));
114	&pxor	($R,$B31);
115	&psllq	(@T[0],3*$n);
116	&add	("esp",32+4);
117	&pxor	($R,@T[0]);
118	&ret	();
119&function_end_B("_mul_1x1_mmx");
120					}
121
122($lo,$hi)=("eax","edx");
123@T=("ecx","ebp");
124
125&function_begin_B("_mul_1x1_ialu");
126	&sub	("esp",32+4);
127	 &mov	($a1,$a);
128	 &lea	($a2,&DWP(0,$a,$a));
129	 &lea	($a4,&DWP(0,"",$a,4));
130	 &and	($a1,0x3fffffff);
131	&lea	(@i[1],&DWP(0,$lo,$lo));
132	&sar	($lo,31);		# broadcast 31st bit
133	 &mov	(&DWP(0*4,"esp"),0);
134	 &and	($a2,0x7fffffff);
135	 &mov	(&DWP(1*4,"esp"),$a1);	# a1
136	 &xor	($a1,$a2);		# a1^a2
137	 &mov	(&DWP(2*4,"esp"),$a2);	# a2
138	 &xor	($a2,$a4);		# a2^a4
139	 &mov	(&DWP(3*4,"esp"),$a1);	# a1^a2
140	 &xor	($a1,$a2);		# a1^a4=a1^a2^a2^a4
141	 &mov	(&DWP(4*4,"esp"),$a4);	# a4
142	 &xor	($a4,$a2);		# a2=a4^a2^a4
143	 &mov	(&DWP(5*4,"esp"),$a1);	# a1^a4
144	 &xor	($a4,$a1);		# a1^a2^a4
145	&sar	(@i[1],31);		# broardcast 30th bit
146	&and	($lo,$b);
147	 &mov	(&DWP(6*4,"esp"),$a2);	# a2^a4
148	&and	(@i[1],$b);
149	 &mov	(&DWP(7*4,"esp"),$a4);	# a1^a2^a4
150	&mov	($hi,$lo);
151	&shl	($lo,31);
152	&mov	(@T[0],@i[1]);
153	&shr	($hi,1);
154
155	 &mov	(@i[0],0x7);
156	&shl	(@i[1],30);
157	 &and	(@i[0],$b);
158	&shr	(@T[0],2);
159	&xor	($lo,@i[1]);
160
161	&shr	($b,3);
162	&mov	(@i[1],0x7);		# 5-byte instruction!?
163	&and	(@i[1],$b);
164	&shr	($b,3);
165	 &xor	($hi,@T[0]);
166	&xor	($lo,&DWP(0,"esp",@i[0],4));
167	&mov	(@i[0],0x7);
168	&and	(@i[0],$b);
169	&shr	($b,3);
170	for($n=1;$n<9;$n++) {
171		&mov	(@T[1],&DWP(0,"esp",@i[1],4));
172		&mov	(@i[1],0x7);
173		&mov	(@T[0],@T[1]);
174		&shl	(@T[1],3*$n);
175		&and	(@i[1],$b);
176		&shr	(@T[0],32-3*$n);
177		&xor	($lo,@T[1]);
178		&shr	($b,3);
179		&xor	($hi,@T[0]);
180
181		push(@i,shift(@i)); push(@T,shift(@T));
182	}
183	&mov	(@T[1],&DWP(0,"esp",@i[1],4));
184	&mov	(@T[0],@T[1]);
185	&shl	(@T[1],3*$n);
186	&mov	(@i[1],&DWP(0,"esp",@i[0],4));
187	&shr	(@T[0],32-3*$n);	$n++;
188	&mov	(@i[0],@i[1]);
189	&xor	($lo,@T[1]);
190	&shl	(@i[1],3*$n);
191	&xor	($hi,@T[0]);
192	&shr	(@i[0],32-3*$n);
193	&xor	($lo,@i[1]);
194	&xor	($hi,@i[0]);
195
196	&add	("esp",32+4);
197	&ret	();
198&function_end_B("_mul_1x1_ialu");
199
200# void bn_GF2m_mul_2x2(BN_ULONG *r, BN_ULONG a1, BN_ULONG a0, BN_ULONG b1, BN_ULONG b0);
201&function_begin_B("bn_GF2m_mul_2x2");
202if (!$x86only) {
203	&picmeup("edx","OPENSSL_ia32cap_P");
204	&mov	("eax",&DWP(0,"edx"));
205	&mov	("edx",&DWP(4,"edx"));
206	&test	("eax",1<<23);		# check MMX bit
207	&jz	(&label("ialu"));
208if ($sse2) {
209	&test	("eax",1<<24);		# check FXSR bit
210	&jz	(&label("mmx"));
211	&test	("edx",1<<1);		# check PCLMULQDQ bit
212	&jz	(&label("mmx"));
213
214	&movups		("xmm0",&QWP(8,"esp"));
215	&shufps		("xmm0","xmm0",0b10110001);
216	&pclmulqdq	("xmm0","xmm0",1);
217	&mov		("eax",&DWP(4,"esp"));
218	&movups		(&QWP(0,"eax"),"xmm0");
219	&ret	();
220
221&set_label("mmx",16);
222}
223	&push	("ebp");
224	&push	("ebx");
225	&push	("esi");
226	&push	("edi");
227	&mov	($a,&wparam(1));
228	&mov	($b,&wparam(3));
229	&call	("_mul_1x1_mmx");	# a1��b1
230	&movq	("mm7",$R);
231
232	&mov	($a,&wparam(2));
233	&mov	($b,&wparam(4));
234	&call	("_mul_1x1_mmx");	# a0��b0
235	&movq	("mm6",$R);
236
237	&mov	($a,&wparam(1));
238	&mov	($b,&wparam(3));
239	&xor	($a,&wparam(2));
240	&xor	($b,&wparam(4));
241	&call	("_mul_1x1_mmx");	# (a0+a1)��(b0+b1)
242	&pxor	($R,"mm7");
243	&mov	($a,&wparam(0));
244	&pxor	($R,"mm6");		# (a0+a1)��(b0+b1)-a1��b1-a0��b0
245
246	&movq	($A,$R);
247	&psllq	($R,32);
248	&pop	("edi");
249	&psrlq	($A,32);
250	&pop	("esi");
251	&pxor	($R,"mm6");
252	&pop	("ebx");
253	&pxor	($A,"mm7");
254	&movq	(&QWP(0,$a),$R);
255	&pop	("ebp");
256	&movq	(&QWP(8,$a),$A);
257	&emms	();
258	&ret	();
259&set_label("ialu",16);
260}
261	&push	("ebp");
262	&push	("ebx");
263	&push	("esi");
264	&push	("edi");
265	&stack_push(4+1);
266
267	&mov	($a,&wparam(1));
268	&mov	($b,&wparam(3));
269	&call	("_mul_1x1_ialu");	# a1��b1
270	&mov	(&DWP(8,"esp"),$lo);
271	&mov	(&DWP(12,"esp"),$hi);
272
273	&mov	($a,&wparam(2));
274	&mov	($b,&wparam(4));
275	&call	("_mul_1x1_ialu");	# a0��b0
276	&mov	(&DWP(0,"esp"),$lo);
277	&mov	(&DWP(4,"esp"),$hi);
278
279	&mov	($a,&wparam(1));
280	&mov	($b,&wparam(3));
281	&xor	($a,&wparam(2));
282	&xor	($b,&wparam(4));
283	&call	("_mul_1x1_ialu");	# (a0+a1)��(b0+b1)
284
285	&mov	("ebp",&wparam(0));
286		 @r=("ebx","ecx","edi","esi");
287	&mov	(@r[0],&DWP(0,"esp"));
288	&mov	(@r[1],&DWP(4,"esp"));
289	&mov	(@r[2],&DWP(8,"esp"));
290	&mov	(@r[3],&DWP(12,"esp"));
291
292	&xor	($lo,$hi);
293	&xor	($hi,@r[1]);
294	&xor	($lo,@r[0]);
295	&mov	(&DWP(0,"ebp"),@r[0]);
296	&xor	($hi,@r[2]);
297	&mov	(&DWP(12,"ebp"),@r[3]);
298	&xor	($lo,@r[3]);
299	&stack_pop(4+1);
300	&xor	($hi,@r[3]);
301	&pop	("edi");
302	&xor	($lo,$hi);
303	&pop	("esi");
304	&mov	(&DWP(8,"ebp"),$hi);
305	&pop	("ebx");
306	&mov	(&DWP(4,"ebp"),$lo);
307	&pop	("ebp");
308	&ret	();
309&function_end_B("bn_GF2m_mul_2x2");
310
311&asciz	("GF(2^m) Multiplication for x86, CRYPTOGAMS by <appro\@openssl.org>");
312
313&asm_finish();
314