1#! /usr/bin/env perl
2# Copyright 2011-2020 The OpenSSL Project Authors. All Rights Reserved.
3#
4# Licensed under the Apache License 2.0 (the "License").  You may not use
5# this file except in compliance with the License.  You can obtain a copy
6# in the file LICENSE in the source distribution or at
7# https://www.openssl.org/source/license.html
8
9#
10# ====================================================================
11# Written by Andy Polyakov <appro@openssl.org> for the OpenSSL
12# project. The module is, however, dual licensed under OpenSSL and
13# CRYPTOGAMS licenses depending on where you obtain it. For further
14# details see http://www.openssl.org/~appro/cryptogams/.
15# ====================================================================
16#
17# May 2011
18#
19# The module implements bn_GF2m_mul_2x2 polynomial multiplication
20# used in bn_gf2m.c. It's kind of low-hanging mechanical port from
21# C for the time being... Except that it has two code paths: pure
22# integer code suitable for any ARMv4 and later CPU and NEON code
23# suitable for ARMv7. Pure integer 1x1 multiplication subroutine runs
24# in ~45 cycles on dual-issue core such as Cortex A8, which is ~50%
25# faster than compiler-generated code. For ECDH and ECDSA verify (but
26# not for ECDSA sign) it means 25%-45% improvement depending on key
27# length, more for longer keys. Even though NEON 1x1 multiplication
28# runs in even less cycles, ~30, improvement is measurable only on
29# longer keys. One has to optimize code elsewhere to get NEON glow...
30#
31# April 2014
32#
33# Double bn_GF2m_mul_2x2 performance by using algorithm from paper
34# referred below, which improves ECDH and ECDSA verify benchmarks
35# by 18-40%.
36#
37# Câmara, D.; Gouvêa, C. P. L.; López, J. & Dahab, R.: Fast Software
38# Polynomial Multiplication on ARM Processors using the NEON Engine.
39#
40# http://conradoplg.cryptoland.net/files/2010/12/mocrysen13.pdf
41
42# $output is the last argument if it looks like a file (it has an extension)
43# $flavour is the first argument if it doesn't look like a file
44$output = $#ARGV >= 0 && $ARGV[$#ARGV] =~ m|\.\w+$| ? pop : undef;
45$flavour = $#ARGV >= 0 && $ARGV[0] !~ m|\.| ? shift : undef;
46
47if ($flavour && $flavour ne "void") {
48    $0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
49    ( $xlate="${dir}arm-xlate.pl" and -f $xlate ) or
50    ( $xlate="${dir}../../perlasm/arm-xlate.pl" and -f $xlate) or
51    die "can't locate arm-xlate.pl";
52
53    open STDOUT,"| \"$^X\" $xlate $flavour \"$output\""
54        or die "can't call $xlate: $1";
55} else {
56    $output and open STDOUT,">$output";
57}
58
59$code=<<___;
60#include "arm_arch.h"
61
62#if defined(__thumb2__)
63.syntax	unified
64.thumb
65#else
66.code	32
67#endif
68
69.text
70___
71################
72# private interface to mul_1x1_ialu
73#
74$a="r1";
75$b="r0";
76
77($a0,$a1,$a2,$a12,$a4,$a14)=
78($hi,$lo,$t0,$t1, $i0,$i1 )=map("r$_",(4..9),12);
79
80$mask="r12";
81
82$code.=<<___;
83.type	mul_1x1_ialu,%function
84.align	5
85mul_1x1_ialu:
86	mov	$a0,#0
87	bic	$a1,$a,#3<<30		@ a1=a&0x3fffffff
88	str	$a0,[sp,#0]		@ tab[0]=0
89	add	$a2,$a1,$a1		@ a2=a1<<1
90	str	$a1,[sp,#4]		@ tab[1]=a1
91	eor	$a12,$a1,$a2		@ a1^a2
92	str	$a2,[sp,#8]		@ tab[2]=a2
93	mov	$a4,$a1,lsl#2		@ a4=a1<<2
94	str	$a12,[sp,#12]		@ tab[3]=a1^a2
95	eor	$a14,$a1,$a4		@ a1^a4
96	str	$a4,[sp,#16]		@ tab[4]=a4
97	eor	$a0,$a2,$a4		@ a2^a4
98	str	$a14,[sp,#20]		@ tab[5]=a1^a4
99	eor	$a12,$a12,$a4		@ a1^a2^a4
100	str	$a0,[sp,#24]		@ tab[6]=a2^a4
101	and	$i0,$mask,$b,lsl#2
102	str	$a12,[sp,#28]		@ tab[7]=a1^a2^a4
103
104	and	$i1,$mask,$b,lsr#1
105	ldr	$lo,[sp,$i0]		@ tab[b       & 0x7]
106	and	$i0,$mask,$b,lsr#4
107	ldr	$t1,[sp,$i1]		@ tab[b >>  3 & 0x7]
108	and	$i1,$mask,$b,lsr#7
109	ldr	$t0,[sp,$i0]		@ tab[b >>  6 & 0x7]
110	eor	$lo,$lo,$t1,lsl#3	@ stall
111	mov	$hi,$t1,lsr#29
112	ldr	$t1,[sp,$i1]		@ tab[b >>  9 & 0x7]
113
114	and	$i0,$mask,$b,lsr#10
115	eor	$lo,$lo,$t0,lsl#6
116	eor	$hi,$hi,$t0,lsr#26
117	ldr	$t0,[sp,$i0]		@ tab[b >> 12 & 0x7]
118
119	and	$i1,$mask,$b,lsr#13
120	eor	$lo,$lo,$t1,lsl#9
121	eor	$hi,$hi,$t1,lsr#23
122	ldr	$t1,[sp,$i1]		@ tab[b >> 15 & 0x7]
123
124	and	$i0,$mask,$b,lsr#16
125	eor	$lo,$lo,$t0,lsl#12
126	eor	$hi,$hi,$t0,lsr#20
127	ldr	$t0,[sp,$i0]		@ tab[b >> 18 & 0x7]
128
129	and	$i1,$mask,$b,lsr#19
130	eor	$lo,$lo,$t1,lsl#15
131	eor	$hi,$hi,$t1,lsr#17
132	ldr	$t1,[sp,$i1]		@ tab[b >> 21 & 0x7]
133
134	and	$i0,$mask,$b,lsr#22
135	eor	$lo,$lo,$t0,lsl#18
136	eor	$hi,$hi,$t0,lsr#14
137	ldr	$t0,[sp,$i0]		@ tab[b >> 24 & 0x7]
138
139	and	$i1,$mask,$b,lsr#25
140	eor	$lo,$lo,$t1,lsl#21
141	eor	$hi,$hi,$t1,lsr#11
142	ldr	$t1,[sp,$i1]		@ tab[b >> 27 & 0x7]
143
144	tst	$a,#1<<30
145	and	$i0,$mask,$b,lsr#28
146	eor	$lo,$lo,$t0,lsl#24
147	eor	$hi,$hi,$t0,lsr#8
148	ldr	$t0,[sp,$i0]		@ tab[b >> 30      ]
149
150#ifdef	__thumb2__
151	itt	ne
152#endif
153	eorne	$lo,$lo,$b,lsl#30
154	eorne	$hi,$hi,$b,lsr#2
155	tst	$a,#1<<31
156	eor	$lo,$lo,$t1,lsl#27
157	eor	$hi,$hi,$t1,lsr#5
158#ifdef	__thumb2__
159	itt	ne
160#endif
161	eorne	$lo,$lo,$b,lsl#31
162	eorne	$hi,$hi,$b,lsr#1
163	eor	$lo,$lo,$t0,lsl#30
164	eor	$hi,$hi,$t0,lsr#2
165
166	mov	pc,lr
167.size	mul_1x1_ialu,.-mul_1x1_ialu
168___
169################
170# void	bn_GF2m_mul_2x2(BN_ULONG *r,
171#	BN_ULONG a1,BN_ULONG a0,
172#	BN_ULONG b1,BN_ULONG b0);	# r[3..0]=a1a0·b1b0
173{
174$code.=<<___;
175.global	bn_GF2m_mul_2x2
176.type	bn_GF2m_mul_2x2,%function
177.align	5
178bn_GF2m_mul_2x2:
179#if __ARM_MAX_ARCH__>=7
180	stmdb	sp!,{r10,lr}
181	ldr	r12,.LOPENSSL_armcap
182# if !defined(_WIN32)
183	adr	r10,.LOPENSSL_armcap
184	ldr	r12,[r12,r10]
185# endif
186# if defined(__APPLE__) || defined(_WIN32)
187	ldr	r12,[r12]
188# endif
189	tst	r12,#ARMV7_NEON
190	itt	ne
191	ldrne	r10,[sp],#8
192	bne	.LNEON
193	stmdb	sp!,{r4-r9}
194#else
195	stmdb	sp!,{r4-r10,lr}
196#endif
197___
198$ret="r10";	# reassigned 1st argument
199$code.=<<___;
200	mov	$ret,r0			@ reassign 1st argument
201	mov	$b,r3			@ $b=b1
202	sub	r7,sp,#36
203	mov	r8,sp
204	and	r7,r7,#-32
205	ldr	r3,[sp,#32]		@ load b0
206	mov	$mask,#7<<2
207	mov	sp,r7			@ allocate tab[8]
208	str	r8,[r7,#32]
209
210	bl	mul_1x1_ialu		@ a1·b1
211	str	$lo,[$ret,#8]
212	str	$hi,[$ret,#12]
213
214	eor	$b,$b,r3		@ flip b0 and b1
215	 eor	$a,$a,r2		@ flip a0 and a1
216	eor	r3,r3,$b
217	 eor	r2,r2,$a
218	eor	$b,$b,r3
219	 eor	$a,$a,r2
220	bl	mul_1x1_ialu		@ a0·b0
221	str	$lo,[$ret]
222	str	$hi,[$ret,#4]
223
224	eor	$a,$a,r2
225	eor	$b,$b,r3
226	bl	mul_1x1_ialu		@ (a1+a0)·(b1+b0)
227___
228@r=map("r$_",(6..9));
229$code.=<<___;
230	ldmia	$ret,{@r[0]-@r[3]}
231	eor	$lo,$lo,$hi
232	ldr	sp,[sp,#32]		@ destroy tab[8]
233	eor	$hi,$hi,@r[1]
234	eor	$lo,$lo,@r[0]
235	eor	$hi,$hi,@r[2]
236	eor	$lo,$lo,@r[3]
237	eor	$hi,$hi,@r[3]
238	str	$hi,[$ret,#8]
239	eor	$lo,$lo,$hi
240	str	$lo,[$ret,#4]
241
242#if __ARM_ARCH__>=5
243	ldmia	sp!,{r4-r10,pc}
244#else
245	ldmia	sp!,{r4-r10,lr}
246	tst	lr,#1
247	moveq	pc,lr			@ be binary compatible with V4, yet
248	bx	lr			@ interoperable with Thumb ISA:-)
249#endif
250___
251}
252{
253my ($r,$t0,$t1,$t2,$t3)=map("q$_",(0..3,8..12));
254my ($a,$b,$k48,$k32,$k16)=map("d$_",(26..31));
255
256$code.=<<___;
257#if __ARM_MAX_ARCH__>=7
258.arch	armv7-a
259.fpu	neon
260
261.align	5
262.LNEON:
263	ldr		r12, [sp]		@ 5th argument
264	vmov		$a, r2, r1
265	vmov		$b, r12, r3
266	vmov.i64	$k48, #0x0000ffffffffffff
267	vmov.i64	$k32, #0x00000000ffffffff
268	vmov.i64	$k16, #0x000000000000ffff
269
270	vext.8		$t0#lo, $a, $a, #1	@ A1
271	vmull.p8	$t0, $t0#lo, $b		@ F = A1*B
272	vext.8		$r#lo, $b, $b, #1	@ B1
273	vmull.p8	$r, $a, $r#lo		@ E = A*B1
274	vext.8		$t1#lo, $a, $a, #2	@ A2
275	vmull.p8	$t1, $t1#lo, $b		@ H = A2*B
276	vext.8		$t3#lo, $b, $b, #2	@ B2
277	vmull.p8	$t3, $a, $t3#lo		@ G = A*B2
278	vext.8		$t2#lo, $a, $a, #3	@ A3
279	veor		$t0, $t0, $r		@ L = E + F
280	vmull.p8	$t2, $t2#lo, $b		@ J = A3*B
281	vext.8		$r#lo, $b, $b, #3	@ B3
282	veor		$t1, $t1, $t3		@ M = G + H
283	vmull.p8	$r, $a, $r#lo		@ I = A*B3
284	veor		$t0#lo, $t0#lo, $t0#hi	@ t0 = (L) (P0 + P1) << 8
285	vand		$t0#hi, $t0#hi, $k48
286	vext.8		$t3#lo, $b, $b, #4	@ B4
287	veor		$t1#lo, $t1#lo, $t1#hi	@ t1 = (M) (P2 + P3) << 16
288	vand		$t1#hi, $t1#hi, $k32
289	vmull.p8	$t3, $a, $t3#lo		@ K = A*B4
290	veor		$t2, $t2, $r		@ N = I + J
291	veor		$t0#lo, $t0#lo, $t0#hi
292	veor		$t1#lo, $t1#lo, $t1#hi
293	veor		$t2#lo, $t2#lo, $t2#hi	@ t2 = (N) (P4 + P5) << 24
294	vand		$t2#hi, $t2#hi, $k16
295	vext.8		$t0, $t0, $t0, #15
296	veor		$t3#lo, $t3#lo, $t3#hi	@ t3 = (K) (P6 + P7) << 32
297	vmov.i64	$t3#hi, #0
298	vext.8		$t1, $t1, $t1, #14
299	veor		$t2#lo, $t2#lo, $t2#hi
300	vmull.p8	$r, $a, $b		@ D = A*B
301	vext.8		$t3, $t3, $t3, #12
302	vext.8		$t2, $t2, $t2, #13
303	veor		$t0, $t0, $t1
304	veor		$t2, $t2, $t3
305	veor		$r, $r, $t0
306	veor		$r, $r, $t2
307
308	vst1.32		{$r}, [r0]
309	ret		@ bx lr
310#endif
311___
312}
313$code.=<<___;
314.size	bn_GF2m_mul_2x2,.-bn_GF2m_mul_2x2
315#if __ARM_MAX_ARCH__>=7
316.align	5
317.LOPENSSL_armcap:
318# ifdef	_WIN32
319.word	OPENSSL_armcap_P
320# else
321.word	OPENSSL_armcap_P-.
322# endif
323#endif
324.asciz	"GF(2^m) Multiplication for ARMv4/NEON, CRYPTOGAMS by <appro\@openssl.org>"
325.align	5
326
327#if __ARM_MAX_ARCH__>=7
328.comm	OPENSSL_armcap_P,4,4
329#endif
330___
331
332foreach (split("\n",$code)) {
333	s/\`([^\`]*)\`/eval $1/geo;
334
335	s/\bq([0-9]+)#(lo|hi)/sprintf "d%d",2*$1+($2 eq "hi")/geo	or
336	s/\bret\b/bx	lr/go		or
337	s/\bbx\s+lr\b/.word\t0xe12fff1e/go;    # make it possible to compile with -march=armv4
338
339	print $_,"\n";
340}
341close STDOUT or die "error closing STDOUT: $!";   # enforce flush
342