ppc-mont.pl@ 83531

Last change on this file since 83531 was 83531, checked in by vboxsync, 5 years ago
setting svn:sync-process=export for openssl-1.1.1f, all files except tests
File size: 47.6 KB

Line
1	#! /usr/bin/env perl
2	# Copyright 2006-2020 The OpenSSL Project Authors. All Rights Reserved.
3	#
4	# Licensed under the OpenSSL license (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 <[email protected]> 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	# April 2006
18
19	# "Teaser" Montgomery multiplication module for PowerPC. It's possible
20	# to gain a bit more by modulo-scheduling outer loop, then dedicated
21	# squaring procedure should give further 20% and code can be adapted
22	# for 32-bit application running on 64-bit CPU. As for the latter.
23	# It won't be able to achieve "native" 64-bit performance, because in
24	# 32-bit application context every addc instruction will have to be
25	# expanded as addc, twice right shift by 32 and finally adde, etc.
26	# So far RSA sign performance improvement over pre-bn_mul_mont asm
27	# for 64-bit application running on PPC970/G5 is:
28	#
29	# 512-bit +65%
30	# 1024-bit +35%
31	# 2048-bit +18%
32	# 4096-bit +4%
33
34	# September 2016
35	#
36	# Add multiplication procedure operating on lengths divisible by 4
37	# and squaring procedure operating on lengths divisible by 8. Length
38	# is expressed in number of limbs. RSA private key operations are
39	# ~35-50% faster (more for longer keys) on contemporary high-end POWER
40	# processors in 64-bit builds, [mysteriously enough] more in 32-bit
41	# builds. On low-end 32-bit processors performance improvement turned
42	# to be marginal...
43
44	$flavour = shift;
45
46	if ($flavour =~ /32/) {
47	$BITS= 32;
48	$BNSZ= $BITS/8;
49	$SIZE_T=4;
50	$RZONE= 224;
51
52	$LD= "lwz"; # load
53	$LDU= "lwzu"; # load and update
54	$LDX= "lwzx"; # load indexed
55	$ST= "stw"; # store
56	$STU= "stwu"; # store and update
57	$STX= "stwx"; # store indexed
58	$STUX= "stwux"; # store indexed and update
59	$UMULL= "mullw"; # unsigned multiply low
60	$UMULH= "mulhwu"; # unsigned multiply high
61	$UCMP= "cmplw"; # unsigned compare
62	$SHRI= "srwi"; # unsigned shift right by immediate
63	$SHLI= "slwi"; # unsigned shift left by immediate
64	$PUSH= $ST;
65	$POP= $LD;
66	} elsif ($flavour =~ /64/) {
67	$BITS= 64;
68	$BNSZ= $BITS/8;
69	$SIZE_T=8;
70	$RZONE= 288;
71
72	# same as above, but 64-bit mnemonics...
73	$LD= "ld"; # load
74	$LDU= "ldu"; # load and update
75	$LDX= "ldx"; # load indexed
76	$ST= "std"; # store
77	$STU= "stdu"; # store and update
78	$STX= "stdx"; # store indexed
79	$STUX= "stdux"; # store indexed and update
80	$UMULL= "mulld"; # unsigned multiply low
81	$UMULH= "mulhdu"; # unsigned multiply high
82	$UCMP= "cmpld"; # unsigned compare
83	$SHRI= "srdi"; # unsigned shift right by immediate
84	$SHLI= "sldi"; # unsigned shift left by immediate
85	$PUSH= $ST;
86	$POP= $LD;
87	} else { die "nonsense $flavour"; }
88
89	$FRAME=8*$SIZE_T+$RZONE;
90	$LOCALS=8*$SIZE_T;
91
92	$0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
93	( $xlate="${dir}ppc-xlate.pl" and -f $xlate ) or
94	( $xlate="${dir}../../perlasm/ppc-xlate.pl" and -f $xlate) or
95	die "can't locate ppc-xlate.pl";
96
97	open STDOUT,"\| $^X $xlate $flavour ".shift \|\| die "can't call $xlate: $!";
98
99	$sp="r1";
100	$toc="r2";
101	$rp="r3";
102	$ap="r4";
103	$bp="r5";
104	$np="r6";
105	$n0="r7";
106	$num="r8";
107
108	{
109	my $ovf=$rp;
110	my $rp="r9"; # $rp is reassigned
111	my $aj="r10";
112	my $nj="r11";
113	my $tj="r12";
114	# non-volatile registers
115	my $i="r20";
116	my $j="r21";
117	my $tp="r22";
118	my $m0="r23";
119	my $m1="r24";
120	my $lo0="r25";
121	my $hi0="r26";
122	my $lo1="r27";
123	my $hi1="r28";
124	my $alo="r29";
125	my $ahi="r30";
126	my $nlo="r31";
127	#
128	my $nhi="r0";
129
130	$code=<<___;
131	.machine "any"
132	.text
133
134	.globl .bn_mul_mont_int
135	.align 5
136	.bn_mul_mont_int:
137	mr $rp,r3 ; $rp is reassigned
138	li r3,0
139	___
140	$code.=<<___ if ($BNSZ==4);
141	cmpwi $num,32 ; longer key performance is not better
142	bgelr
143	___
144	$code.=<<___;
145	slwi $num,$num,`log($BNSZ)/log(2)`
146	li $tj,-4096
147	addi $ovf,$num,$FRAME
148	subf $ovf,$ovf,$sp ; $sp-$ovf
149	and $ovf,$ovf,$tj ; minimize TLB usage
150	subf $ovf,$sp,$ovf ; $ovf-$sp
151	mr $tj,$sp
152	srwi $num,$num,`log($BNSZ)/log(2)`
153	$STUX $sp,$sp,$ovf
154
155	$PUSH r20,`-12*$SIZE_T`($tj)
156	$PUSH r21,`-11*$SIZE_T`($tj)
157	$PUSH r22,`-10*$SIZE_T`($tj)
158	$PUSH r23,`-9*$SIZE_T`($tj)
159	$PUSH r24,`-8*$SIZE_T`($tj)
160	$PUSH r25,`-7*$SIZE_T`($tj)
161	$PUSH r26,`-6*$SIZE_T`($tj)
162	$PUSH r27,`-5*$SIZE_T`($tj)
163	$PUSH r28,`-4*$SIZE_T`($tj)
164	$PUSH r29,`-3*$SIZE_T`($tj)
165	$PUSH r30,`-2*$SIZE_T`($tj)
166	$PUSH r31,`-1*$SIZE_T`($tj)
167
168	$LD $n0,0($n0) ; pull n0[0] value
169	addi $num,$num,-2 ; adjust $num for counter register
170
171
172	$LD $m0,0($bp) ; m0=bp[0]
173	$LD $aj,0($ap) ; ap[0]
174	addi $tp,$sp,$LOCALS
175	$UMULL $lo0,$aj,$m0 ; ap[0]*bp[0]
176	$UMULH $hi0,$aj,$m0
177
178	$LD $aj,$BNSZ($ap) ; ap[1]
179	$LD $nj,0($np) ; np[0]
180
181	$UMULL $m1,$lo0,$n0 ; "tp[0]"*n0
182
183	$UMULL $alo,$aj,$m0 ; ap[1]*bp[0]
184	$UMULH $ahi,$aj,$m0
185
186	$UMULL $lo1,$nj,$m1 ; np[0]*m1
187	$UMULH $hi1,$nj,$m1
188	$LD $nj,$BNSZ($np) ; np[1]
189	addc $lo1,$lo1,$lo0
190	addze $hi1,$hi1
191
192	$UMULL $nlo,$nj,$m1 ; np[1]*m1
193	$UMULH $nhi,$nj,$m1
194
195	mtctr $num
196	li $j,`2*$BNSZ`
197	.align 4
198	L1st:
199	$LDX $aj,$ap,$j ; ap[j]
200	addc $lo0,$alo,$hi0
201	$LDX $nj,$np,$j ; np[j]
202	addze $hi0,$ahi
203	$UMULL $alo,$aj,$m0 ; ap[j]*bp[0]
204	addc $lo1,$nlo,$hi1
205	$UMULH $ahi,$aj,$m0
206	addze $hi1,$nhi
207	$UMULL $nlo,$nj,$m1 ; np[j]*m1
208	addc $lo1,$lo1,$lo0 ; np[j]m1+ap[j]bp[0]
209	$UMULH $nhi,$nj,$m1
210	addze $hi1,$hi1
211	$ST $lo1,0($tp) ; tp[j-1]
212
213	addi $j,$j,$BNSZ ; j++
214	addi $tp,$tp,$BNSZ ; tp++
215	bdnz L1st
216	;L1st
217	addc $lo0,$alo,$hi0
218	addze $hi0,$ahi
219
220	addc $lo1,$nlo,$hi1
221	addze $hi1,$nhi
222	addc $lo1,$lo1,$lo0 ; np[j]m1+ap[j]bp[0]
223	addze $hi1,$hi1
224	$ST $lo1,0($tp) ; tp[j-1]
225
226	li $ovf,0
227	addc $hi1,$hi1,$hi0
228	addze $ovf,$ovf ; upmost overflow bit
229	$ST $hi1,$BNSZ($tp)
230
231
232	li $i,$BNSZ
233	.align 4
234	Louter:
235	$LDX $m0,$bp,$i ; m0=bp[i]
236	$LD $aj,0($ap) ; ap[0]
237	addi $tp,$sp,$LOCALS
238	$LD $tj,$LOCALS($sp); tp[0]
239	$UMULL $lo0,$aj,$m0 ; ap[0]*bp[i]
240	$UMULH $hi0,$aj,$m0
241	$LD $aj,$BNSZ($ap) ; ap[1]
242	$LD $nj,0($np) ; np[0]
243	addc $lo0,$lo0,$tj ; ap[0]*bp[i]+tp[0]
244	$UMULL $alo,$aj,$m0 ; ap[j]*bp[i]
245	addze $hi0,$hi0
246	$UMULL $m1,$lo0,$n0 ; tp[0]*n0
247	$UMULH $ahi,$aj,$m0
248	$UMULL $lo1,$nj,$m1 ; np[0]*m1
249	$UMULH $hi1,$nj,$m1
250	$LD $nj,$BNSZ($np) ; np[1]
251	addc $lo1,$lo1,$lo0
252	$UMULL $nlo,$nj,$m1 ; np[1]*m1
253	addze $hi1,$hi1
254	$UMULH $nhi,$nj,$m1
255
256
257	mtctr $num
258	li $j,`2*$BNSZ`
259	.align 4
260	Linner:
261	$LDX $aj,$ap,$j ; ap[j]
262	addc $lo0,$alo,$hi0
263	$LD $tj,$BNSZ($tp) ; tp[j]
264	addze $hi0,$ahi
265	$LDX $nj,$np,$j ; np[j]
266	addc $lo1,$nlo,$hi1
267	$UMULL $alo,$aj,$m0 ; ap[j]*bp[i]
268	addze $hi1,$nhi
269	$UMULH $ahi,$aj,$m0
270	addc $lo0,$lo0,$tj ; ap[j]*bp[i]+tp[j]
271	$UMULL $nlo,$nj,$m1 ; np[j]*m1
272	addze $hi0,$hi0
273	$UMULH $nhi,$nj,$m1
274	addc $lo1,$lo1,$lo0 ; np[j]m1+ap[j]bp[i]+tp[j]
275	addi $j,$j,$BNSZ ; j++
276	addze $hi1,$hi1
277	$ST $lo1,0($tp) ; tp[j-1]
278	addi $tp,$tp,$BNSZ ; tp++
279	bdnz Linner
280	;Linner
281	$LD $tj,$BNSZ($tp) ; tp[j]
282	addc $lo0,$alo,$hi0
283	addze $hi0,$ahi
284	addc $lo0,$lo0,$tj ; ap[j]*bp[i]+tp[j]
285	addze $hi0,$hi0
286
287	addc $lo1,$nlo,$hi1
288	addze $hi1,$nhi
289	addc $lo1,$lo1,$lo0 ; np[j]m1+ap[j]bp[i]+tp[j]
290	addze $hi1,$hi1
291	$ST $lo1,0($tp) ; tp[j-1]
292
293	addic $ovf,$ovf,-1 ; move upmost overflow to XER[CA]
294	li $ovf,0
295	adde $hi1,$hi1,$hi0
296	addze $ovf,$ovf
297	$ST $hi1,$BNSZ($tp)
298	;
299	slwi $tj,$num,`log($BNSZ)/log(2)`
300	$UCMP $i,$tj
301	addi $i,$i,$BNSZ
302	ble Louter
303
304
305	addi $num,$num,2 ; restore $num
306	subfc $j,$j,$j ; j=0 and "clear" XER[CA]
307	addi $tp,$sp,$LOCALS
308	mtctr $num
309
310	.align 4
311	Lsub: $LDX $tj,$tp,$j
312	$LDX $nj,$np,$j
313	subfe $aj,$nj,$tj ; tp[j]-np[j]
314	$STX $aj,$rp,$j
315	addi $j,$j,$BNSZ
316	bdnz Lsub
317
318	li $j,0
319	mtctr $num
320	subfe $ovf,$j,$ovf ; handle upmost overflow bit
321
322	.align 4
323	Lcopy: ; conditional copy
324	$LDX $tj,$tp,$j
325	$LDX $aj,$rp,$j
326	and $tj,$tj,$ovf
327	andc $aj,$aj,$ovf
328	$STX $j,$tp,$j ; zap at once
329	or $aj,$aj,$tj
330	$STX $aj,$rp,$j
331	addi $j,$j,$BNSZ
332	bdnz Lcopy
333
334	$POP $tj,0($sp)
335	li r3,1
336	$POP r20,`-12*$SIZE_T`($tj)
337	$POP r21,`-11*$SIZE_T`($tj)
338	$POP r22,`-10*$SIZE_T`($tj)
339	$POP r23,`-9*$SIZE_T`($tj)
340	$POP r24,`-8*$SIZE_T`($tj)
341	$POP r25,`-7*$SIZE_T`($tj)
342	$POP r26,`-6*$SIZE_T`($tj)
343	$POP r27,`-5*$SIZE_T`($tj)
344	$POP r28,`-4*$SIZE_T`($tj)
345	$POP r29,`-3*$SIZE_T`($tj)
346	$POP r30,`-2*$SIZE_T`($tj)
347	$POP r31,`-1*$SIZE_T`($tj)
348	mr $sp,$tj
349	blr
350	.long 0
351	.byte 0,12,4,0,0x80,12,6,0
352	.long 0
353	.size .bn_mul_mont_int,.-.bn_mul_mont_int
354	___
355	}
356	if (1) {
357	my ($a0,$a1,$a2,$a3,
358	$t0,$t1,$t2,$t3,
359	$m0,$m1,$m2,$m3,
360	$acc0,$acc1,$acc2,$acc3,$acc4,
361	$bi,$mi,$tp,$ap_end,$cnt) = map("r$_",(9..12,14..31));
362	my ($carry,$zero) = ($rp,"r0");
363
364	# sp----------->+-------------------------------+
365	# \| saved sp \|
366	# +-------------------------------+
367	# . .
368	# +8*size_t +-------------------------------+
369	# \| 4 "n0*t0" \|
370	# . .
371	# . .
372	# +12*size_t +-------------------------------+
373	# \| size_t tmp[num] \|
374	# . .
375	# . .
376	# . .
377	# +-------------------------------+
378	# \| topmost carry \|
379	# . .
380	# -18*size_t +-------------------------------+
381	# \| 18 saved gpr, r14-r31 \|
382	# . .
383	# . .
384	# +-------------------------------+
385	$code.=<<___;
386	.globl .bn_mul4x_mont_int
387	.align 5
388	.bn_mul4x_mont_int:
389	andi. r0,$num,7
390	bne .Lmul4x_do
391	$UCMP $ap,$bp
392	bne .Lmul4x_do
393	b .Lsqr8x_do
394	.Lmul4x_do:
395	slwi $num,$num,`log($SIZE_T)/log(2)`
396	mr $a0,$sp
397	li $a1,-32*$SIZE_T
398	sub $a1,$a1,$num
399	$STUX $sp,$sp,$a1 # alloca
400
401	$PUSH r14,-$SIZE_T*18($a0)
402	$PUSH r15,-$SIZE_T*17($a0)
403	$PUSH r16,-$SIZE_T*16($a0)
404	$PUSH r17,-$SIZE_T*15($a0)
405	$PUSH r18,-$SIZE_T*14($a0)
406	$PUSH r19,-$SIZE_T*13($a0)
407	$PUSH r20,-$SIZE_T*12($a0)
408	$PUSH r21,-$SIZE_T*11($a0)
409	$PUSH r22,-$SIZE_T*10($a0)
410	$PUSH r23,-$SIZE_T*9($a0)
411	$PUSH r24,-$SIZE_T*8($a0)
412	$PUSH r25,-$SIZE_T*7($a0)
413	$PUSH r26,-$SIZE_T*6($a0)
414	$PUSH r27,-$SIZE_T*5($a0)
415	$PUSH r28,-$SIZE_T*4($a0)
416	$PUSH r29,-$SIZE_T*3($a0)
417	$PUSH r30,-$SIZE_T*2($a0)
418	$PUSH r31,-$SIZE_T*1($a0)
419
420	subi $ap,$ap,$SIZE_T # bias by -1
421	subi $np,$np,$SIZE_T # bias by -1
422	subi $rp,$rp,$SIZE_T # bias by -1
423	$LD $n0,0($n0) # *n0
424
425	add $t0,$bp,$num
426	add $ap_end,$ap,$num
427	subi $t0,$t0,$SIZE_T*4 # &b[num-4]
428
429	$LD $bi,$SIZE_T*0($bp) # b[0]
430	li $acc0,0
431	$LD $a0,$SIZE_T*1($ap) # a[0..3]
432	li $acc1,0
433	$LD $a1,$SIZE_T*2($ap)
434	li $acc2,0
435	$LD $a2,$SIZE_T*3($ap)
436	li $acc3,0
437	$LDU $a3,$SIZE_T*4($ap)
438	$LD $m0,$SIZE_T*1($np) # n[0..3]
439	$LD $m1,$SIZE_T*2($np)
440	$LD $m2,$SIZE_T*3($np)
441	$LDU $m3,$SIZE_T*4($np)
442
443	$PUSH $rp,$SIZE_T*6($sp) # offload rp and &b[num-4]
444	$PUSH $t0,$SIZE_T*7($sp)
445	li $carry,0
446	addic $tp,$sp,$SIZE_T*7 # &t[-1], clear carry bit
447	li $cnt,0
448	li $zero,0
449	b .Loop_mul4x_1st_reduction
450
451	.align 5
452	.Loop_mul4x_1st_reduction:
453	$UMULL $t0,$a0,$bi # lo(a[0..3]*b[0])
454	addze $carry,$carry # modulo-scheduled
455	$UMULL $t1,$a1,$bi
456	addi $cnt,$cnt,$SIZE_T
457	$UMULL $t2,$a2,$bi
458	andi. $cnt,$cnt,$SIZE_T*4-1
459	$UMULL $t3,$a3,$bi
460	addc $acc0,$acc0,$t0
461	$UMULH $t0,$a0,$bi # hi(a[0..3]*b[0])
462	adde $acc1,$acc1,$t1
463	$UMULH $t1,$a1,$bi
464	adde $acc2,$acc2,$t2
465	$UMULL $mi,$acc0,$n0 # t[0]*n0
466	adde $acc3,$acc3,$t3
467	$UMULH $t2,$a2,$bi
468	addze $acc4,$zero
469	$UMULH $t3,$a3,$bi
470	$LDX $bi,$bp,$cnt # next b[i] (or b[0])
471	addc $acc1,$acc1,$t0
472	# () mul $t0,$m0,$mi # lo(n[0..3]t[0]*n0)
473	$STU $mi,$SIZE_T($tp) # put aside t[0]*n0 for tail processing
474	adde $acc2,$acc2,$t1
475	$UMULL $t1,$m1,$mi
476	adde $acc3,$acc3,$t2
477	$UMULL $t2,$m2,$mi
478	adde $acc4,$acc4,$t3 # can't overflow
479	$UMULL $t3,$m3,$mi
480	# (*) addc $acc0,$acc0,$t0
481	# (*) As for removal of first multiplication and addition
482	# instructions. The outcome of first addition is
483	# guaranteed to be zero, which leaves two computationally
484	# significant outcomes: it either carries or not. Then
485	# question is when does it carry? Is there alternative
486	# way to deduce it? If you follow operations, you can
487	# observe that condition for carry is quite simple:
488	# $acc0 being non-zero. So that carry can be calculated
489	# by adding -1 to $acc0. That's what next instruction does.
490	addic $acc0,$acc0,-1 # (*), discarded
491	$UMULH $t0,$m0,$mi # hi(n[0..3]t[0]n0)
492	adde $acc0,$acc1,$t1
493	$UMULH $t1,$m1,$mi
494	adde $acc1,$acc2,$t2
495	$UMULH $t2,$m2,$mi
496	adde $acc2,$acc3,$t3
497	$UMULH $t3,$m3,$mi
498	adde $acc3,$acc4,$carry
499	addze $carry,$zero
500	addc $acc0,$acc0,$t0
501	adde $acc1,$acc1,$t1
502	adde $acc2,$acc2,$t2
503	adde $acc3,$acc3,$t3
504	#addze $carry,$carry
505	bne .Loop_mul4x_1st_reduction
506
507	$UCMP $ap_end,$ap
508	beq .Lmul4x4_post_condition
509
510	$LD $a0,$SIZE_T*1($ap) # a[4..7]
511	$LD $a1,$SIZE_T*2($ap)
512	$LD $a2,$SIZE_T*3($ap)
513	$LDU $a3,$SIZE_T*4($ap)
514	$LD $mi,$SIZE_T8($sp) # a[0]n0
515	$LD $m0,$SIZE_T*1($np) # n[4..7]
516	$LD $m1,$SIZE_T*2($np)
517	$LD $m2,$SIZE_T*3($np)
518	$LDU $m3,$SIZE_T*4($np)
519	b .Loop_mul4x_1st_tail
520
521	.align 5
522	.Loop_mul4x_1st_tail:
523	$UMULL $t0,$a0,$bi # lo(a[4..7]*b[i])
524	addze $carry,$carry # modulo-scheduled
525	$UMULL $t1,$a1,$bi
526	addi $cnt,$cnt,$SIZE_T
527	$UMULL $t2,$a2,$bi
528	andi. $cnt,$cnt,$SIZE_T*4-1
529	$UMULL $t3,$a3,$bi
530	addc $acc0,$acc0,$t0
531	$UMULH $t0,$a0,$bi # hi(a[4..7]*b[i])
532	adde $acc1,$acc1,$t1
533	$UMULH $t1,$a1,$bi
534	adde $acc2,$acc2,$t2
535	$UMULH $t2,$a2,$bi
536	adde $acc3,$acc3,$t3
537	$UMULH $t3,$a3,$bi
538	addze $acc4,$zero
539	$LDX $bi,$bp,$cnt # next b[i] (or b[0])
540	addc $acc1,$acc1,$t0
541	$UMULL $t0,$m0,$mi # lo(n[4..7]a[0]n0)
542	adde $acc2,$acc2,$t1
543	$UMULL $t1,$m1,$mi
544	adde $acc3,$acc3,$t2
545	$UMULL $t2,$m2,$mi
546	adde $acc4,$acc4,$t3 # can't overflow
547	$UMULL $t3,$m3,$mi
548	addc $acc0,$acc0,$t0
549	$UMULH $t0,$m0,$mi # hi(n[4..7]a[0]n0)
550	adde $acc1,$acc1,$t1
551	$UMULH $t1,$m1,$mi
552	adde $acc2,$acc2,$t2
553	$UMULH $t2,$m2,$mi
554	adde $acc3,$acc3,$t3
555	adde $acc4,$acc4,$carry
556	$UMULH $t3,$m3,$mi
557	addze $carry,$zero
558	addi $mi,$sp,$SIZE_T*8
559	$LDX $mi,$mi,$cnt # next t[0]*n0
560	$STU $acc0,$SIZE_T($tp) # word of result
561	addc $acc0,$acc1,$t0
562	adde $acc1,$acc2,$t1
563	adde $acc2,$acc3,$t2
564	adde $acc3,$acc4,$t3
565	#addze $carry,$carry
566	bne .Loop_mul4x_1st_tail
567
568	sub $t1,$ap_end,$num # rewinded $ap
569	$UCMP $ap_end,$ap # done yet?
570	beq .Lmul4x_proceed
571
572	$LD $a0,$SIZE_T*1($ap)
573	$LD $a1,$SIZE_T*2($ap)
574	$LD $a2,$SIZE_T*3($ap)
575	$LDU $a3,$SIZE_T*4($ap)
576	$LD $m0,$SIZE_T*1($np)
577	$LD $m1,$SIZE_T*2($np)
578	$LD $m2,$SIZE_T*3($np)
579	$LDU $m3,$SIZE_T*4($np)
580	b .Loop_mul4x_1st_tail
581
582	.align 5
583	.Lmul4x_proceed:
584	$LDU $bi,$SIZE_T4($bp) # ++b
585	addze $carry,$carry # topmost carry
586	$LD $a0,$SIZE_T*1($t1)
587	$LD $a1,$SIZE_T*2($t1)
588	$LD $a2,$SIZE_T*3($t1)
589	$LD $a3,$SIZE_T*4($t1)
590	addi $ap,$t1,$SIZE_T*4
591	sub $np,$np,$num # rewind np
592
593	$ST $acc0,$SIZE_T*1($tp) # result
594	$ST $acc1,$SIZE_T*2($tp)
595	$ST $acc2,$SIZE_T*3($tp)
596	$ST $acc3,$SIZE_T*4($tp)
597	$ST $carry,$SIZE_T*5($tp) # save topmost carry
598	$LD $acc0,$SIZE_T*12($sp) # t[0..3]
599	$LD $acc1,$SIZE_T*13($sp)
600	$LD $acc2,$SIZE_T*14($sp)
601	$LD $acc3,$SIZE_T*15($sp)
602
603	$LD $m0,$SIZE_T*1($np) # n[0..3]
604	$LD $m1,$SIZE_T*2($np)
605	$LD $m2,$SIZE_T*3($np)
606	$LDU $m3,$SIZE_T*4($np)
607	addic $tp,$sp,$SIZE_T*7 # &t[-1], clear carry bit
608	li $carry,0
609	b .Loop_mul4x_reduction
610
611	.align 5
612	.Loop_mul4x_reduction:
613	$UMULL $t0,$a0,$bi # lo(a[0..3]*b[4])
614	addze $carry,$carry # modulo-scheduled
615	$UMULL $t1,$a1,$bi
616	addi $cnt,$cnt,$SIZE_T
617	$UMULL $t2,$a2,$bi
618	andi. $cnt,$cnt,$SIZE_T*4-1
619	$UMULL $t3,$a3,$bi
620	addc $acc0,$acc0,$t0
621	$UMULH $t0,$a0,$bi # hi(a[0..3]*b[4])
622	adde $acc1,$acc1,$t1
623	$UMULH $t1,$a1,$bi
624	adde $acc2,$acc2,$t2
625	$UMULL $mi,$acc0,$n0 # t[0]*n0
626	adde $acc3,$acc3,$t3
627	$UMULH $t2,$a2,$bi
628	addze $acc4,$zero
629	$UMULH $t3,$a3,$bi
630	$LDX $bi,$bp,$cnt # next b[i]
631	addc $acc1,$acc1,$t0
632	# (*) mul $t0,$m0,$mi
633	$STU $mi,$SIZE_T($tp) # put aside t[0]*n0 for tail processing
634	adde $acc2,$acc2,$t1
635	$UMULL $t1,$m1,$mi # lo(n[0..3]t[0]n0
636	adde $acc3,$acc3,$t2
637	$UMULL $t2,$m2,$mi
638	adde $acc4,$acc4,$t3 # can't overflow
639	$UMULL $t3,$m3,$mi
640	# (*) addc $acc0,$acc0,$t0
641	addic $acc0,$acc0,-1 # (*), discarded
642	$UMULH $t0,$m0,$mi # hi(n[0..3]t[0]n0
643	adde $acc0,$acc1,$t1
644	$UMULH $t1,$m1,$mi
645	adde $acc1,$acc2,$t2
646	$UMULH $t2,$m2,$mi
647	adde $acc2,$acc3,$t3
648	$UMULH $t3,$m3,$mi
649	adde $acc3,$acc4,$carry
650	addze $carry,$zero
651	addc $acc0,$acc0,$t0
652	adde $acc1,$acc1,$t1
653	adde $acc2,$acc2,$t2
654	adde $acc3,$acc3,$t3
655	#addze $carry,$carry
656	bne .Loop_mul4x_reduction
657
658	$LD $t0,$SIZE_T*5($tp) # t[4..7]
659	addze $carry,$carry
660	$LD $t1,$SIZE_T*6($tp)
661	$LD $t2,$SIZE_T*7($tp)
662	$LD $t3,$SIZE_T*8($tp)
663	$LD $a0,$SIZE_T*1($ap) # a[4..7]
664	$LD $a1,$SIZE_T*2($ap)
665	$LD $a2,$SIZE_T*3($ap)
666	$LDU $a3,$SIZE_T*4($ap)
667	addc $acc0,$acc0,$t0
668	adde $acc1,$acc1,$t1
669	adde $acc2,$acc2,$t2
670	adde $acc3,$acc3,$t3
671	#addze $carry,$carry
672
673	$LD $mi,$SIZE_T8($sp) # t[0]n0
674	$LD $m0,$SIZE_T*1($np) # n[4..7]
675	$LD $m1,$SIZE_T*2($np)
676	$LD $m2,$SIZE_T*3($np)
677	$LDU $m3,$SIZE_T*4($np)
678	b .Loop_mul4x_tail
679
680	.align 5
681	.Loop_mul4x_tail:
682	$UMULL $t0,$a0,$bi # lo(a[4..7]*b[4])
683	addze $carry,$carry # modulo-scheduled
684	$UMULL $t1,$a1,$bi
685	addi $cnt,$cnt,$SIZE_T
686	$UMULL $t2,$a2,$bi
687	andi. $cnt,$cnt,$SIZE_T*4-1
688	$UMULL $t3,$a3,$bi
689	addc $acc0,$acc0,$t0
690	$UMULH $t0,$a0,$bi # hi(a[4..7]*b[4])
691	adde $acc1,$acc1,$t1
692	$UMULH $t1,$a1,$bi
693	adde $acc2,$acc2,$t2
694	$UMULH $t2,$a2,$bi
695	adde $acc3,$acc3,$t3
696	$UMULH $t3,$a3,$bi
697	addze $acc4,$zero
698	$LDX $bi,$bp,$cnt # next b[i]
699	addc $acc1,$acc1,$t0
700	$UMULL $t0,$m0,$mi # lo(n[4..7]t[0]n0)
701	adde $acc2,$acc2,$t1
702	$UMULL $t1,$m1,$mi
703	adde $acc3,$acc3,$t2
704	$UMULL $t2,$m2,$mi
705	adde $acc4,$acc4,$t3 # can't overflow
706	$UMULL $t3,$m3,$mi
707	addc $acc0,$acc0,$t0
708	$UMULH $t0,$m0,$mi # hi(n[4..7]t[0]n0)
709	adde $acc1,$acc1,$t1
710	$UMULH $t1,$m1,$mi
711	adde $acc2,$acc2,$t2
712	$UMULH $t2,$m2,$mi
713	adde $acc3,$acc3,$t3
714	$UMULH $t3,$m3,$mi
715	adde $acc4,$acc4,$carry
716	addi $mi,$sp,$SIZE_T*8
717	$LDX $mi,$mi,$cnt # next a[0]*n0
718	addze $carry,$zero
719	$STU $acc0,$SIZE_T($tp) # word of result
720	addc $acc0,$acc1,$t0
721	adde $acc1,$acc2,$t1
722	adde $acc2,$acc3,$t2
723	adde $acc3,$acc4,$t3
724	#addze $carry,$carry
725	bne .Loop_mul4x_tail
726
727	$LD $t0,$SIZE_T*5($tp) # next t[i] or topmost carry
728	sub $t1,$np,$num # rewinded np?
729	addze $carry,$carry
730	$UCMP $ap_end,$ap # done yet?
731	beq .Loop_mul4x_break
732
733	$LD $t1,$SIZE_T*6($tp)
734	$LD $t2,$SIZE_T*7($tp)
735	$LD $t3,$SIZE_T*8($tp)
736	$LD $a0,$SIZE_T*1($ap)
737	$LD $a1,$SIZE_T*2($ap)
738	$LD $a2,$SIZE_T*3($ap)
739	$LDU $a3,$SIZE_T*4($ap)
740	addc $acc0,$acc0,$t0
741	adde $acc1,$acc1,$t1
742	adde $acc2,$acc2,$t2
743	adde $acc3,$acc3,$t3
744	#addze $carry,$carry
745
746	$LD $m0,$SIZE_T*1($np) # n[4..7]
747	$LD $m1,$SIZE_T*2($np)
748	$LD $m2,$SIZE_T*3($np)
749	$LDU $m3,$SIZE_T*4($np)
750	b .Loop_mul4x_tail
751
752	.align 5
753	.Loop_mul4x_break:
754	$POP $t2,$SIZE_T*6($sp) # pull rp and &b[num-4]
755	$POP $t3,$SIZE_T*7($sp)
756	addc $a0,$acc0,$t0 # accumulate topmost carry
757	$LD $acc0,$SIZE_T*12($sp) # t[0..3]
758	addze $a1,$acc1
759	$LD $acc1,$SIZE_T*13($sp)
760	addze $a2,$acc2
761	$LD $acc2,$SIZE_T*14($sp)
762	addze $a3,$acc3
763	$LD $acc3,$SIZE_T*15($sp)
764	addze $carry,$carry # topmost carry
765	$ST $a0,$SIZE_T*1($tp) # result
766	sub $ap,$ap_end,$num # rewind ap
767	$ST $a1,$SIZE_T*2($tp)
768	$ST $a2,$SIZE_T*3($tp)
769	$ST $a3,$SIZE_T*4($tp)
770	$ST $carry,$SIZE_T*5($tp) # store topmost carry
771
772	$LD $m0,$SIZE_T*1($t1) # n[0..3]
773	$LD $m1,$SIZE_T*2($t1)
774	$LD $m2,$SIZE_T*3($t1)
775	$LD $m3,$SIZE_T*4($t1)
776	addi $np,$t1,$SIZE_T*4
777	$UCMP $bp,$t3 # done yet?
778	beq .Lmul4x_post
779
780	$LDU $bi,$SIZE_T*4($bp)
781	$LD $a0,$SIZE_T*1($ap) # a[0..3]
782	$LD $a1,$SIZE_T*2($ap)
783	$LD $a2,$SIZE_T*3($ap)
784	$LDU $a3,$SIZE_T*4($ap)
785	li $carry,0
786	addic $tp,$sp,$SIZE_T*7 # &t[-1], clear carry bit
787	b .Loop_mul4x_reduction
788
789	.align 5
790	.Lmul4x_post:
791	# Final step. We see if result is larger than modulus, and
792	# if it is, subtract the modulus. But comparison implies
793	# subtraction. So we subtract modulus, see if it borrowed,
794	# and conditionally copy original value.
795	srwi $cnt,$num,`log($SIZE_T)/log(2)+2`
796	mr $bp,$t2 # &rp[-1]
797	subi $cnt,$cnt,1
798	mr $ap_end,$t2 # &rp[-1] copy
799	subfc $t0,$m0,$acc0
800	addi $tp,$sp,$SIZE_T*15
801	subfe $t1,$m1,$acc1
802
803	mtctr $cnt
804	.Lmul4x_sub:
805	$LD $m0,$SIZE_T*1($np)
806	$LD $acc0,$SIZE_T*1($tp)
807	subfe $t2,$m2,$acc2
808	$LD $m1,$SIZE_T*2($np)
809	$LD $acc1,$SIZE_T*2($tp)
810	subfe $t3,$m3,$acc3
811	$LD $m2,$SIZE_T*3($np)
812	$LD $acc2,$SIZE_T*3($tp)
813	$LDU $m3,$SIZE_T*4($np)
814	$LDU $acc3,$SIZE_T*4($tp)
815	$ST $t0,$SIZE_T*1($bp)
816	$ST $t1,$SIZE_T*2($bp)
817	subfe $t0,$m0,$acc0
818	$ST $t2,$SIZE_T*3($bp)
819	$STU $t3,$SIZE_T*4($bp)
820	subfe $t1,$m1,$acc1
821	bdnz .Lmul4x_sub
822
823	$LD $a0,$SIZE_T*1($ap_end)
824	$ST $t0,$SIZE_T*1($bp)
825	$LD $t0,$SIZE_T*12($sp)
826	subfe $t2,$m2,$acc2
827	$LD $a1,$SIZE_T*2($ap_end)
828	$ST $t1,$SIZE_T*2($bp)
829	$LD $t1,$SIZE_T*13($sp)
830	subfe $t3,$m3,$acc3
831	subfe $carry,$zero,$carry # did it borrow?
832	addi $tp,$sp,$SIZE_T*12
833	$LD $a2,$SIZE_T*3($ap_end)
834	$ST $t2,$SIZE_T*3($bp)
835	$LD $t2,$SIZE_T*14($sp)
836	$LD $a3,$SIZE_T*4($ap_end)
837	$ST $t3,$SIZE_T*4($bp)
838	$LD $t3,$SIZE_T*15($sp)
839
840	mtctr $cnt
841	.Lmul4x_cond_copy:
842	and $t0,$t0,$carry
843	andc $a0,$a0,$carry
844	$ST $zero,$SIZE_T*0($tp) # wipe stack clean
845	and $t1,$t1,$carry
846	andc $a1,$a1,$carry
847	$ST $zero,$SIZE_T*1($tp)
848	and $t2,$t2,$carry
849	andc $a2,$a2,$carry
850	$ST $zero,$SIZE_T*2($tp)
851	and $t3,$t3,$carry
852	andc $a3,$a3,$carry
853	$ST $zero,$SIZE_T*3($tp)
854	or $acc0,$t0,$a0
855	$LD $a0,$SIZE_T*5($ap_end)
856	$LD $t0,$SIZE_T*4($tp)
857	or $acc1,$t1,$a1
858	$LD $a1,$SIZE_T*6($ap_end)
859	$LD $t1,$SIZE_T*5($tp)
860	or $acc2,$t2,$a2
861	$LD $a2,$SIZE_T*7($ap_end)
862	$LD $t2,$SIZE_T*6($tp)
863	or $acc3,$t3,$a3
864	$LD $a3,$SIZE_T*8($ap_end)
865	$LD $t3,$SIZE_T*7($tp)
866	addi $tp,$tp,$SIZE_T*4
867	$ST $acc0,$SIZE_T*1($ap_end)
868	$ST $acc1,$SIZE_T*2($ap_end)
869	$ST $acc2,$SIZE_T*3($ap_end)
870	$STU $acc3,$SIZE_T*4($ap_end)
871	bdnz .Lmul4x_cond_copy
872
873	$POP $bp,0($sp) # pull saved sp
874	and $t0,$t0,$carry
875	andc $a0,$a0,$carry
876	$ST $zero,$SIZE_T*0($tp)
877	and $t1,$t1,$carry
878	andc $a1,$a1,$carry
879	$ST $zero,$SIZE_T*1($tp)
880	and $t2,$t2,$carry
881	andc $a2,$a2,$carry
882	$ST $zero,$SIZE_T*2($tp)
883	and $t3,$t3,$carry
884	andc $a3,$a3,$carry
885	$ST $zero,$SIZE_T*3($tp)
886	or $acc0,$t0,$a0
887	or $acc1,$t1,$a1
888	$ST $zero,$SIZE_T*4($tp)
889	or $acc2,$t2,$a2
890	or $acc3,$t3,$a3
891	$ST $acc0,$SIZE_T*1($ap_end)
892	$ST $acc1,$SIZE_T*2($ap_end)
893	$ST $acc2,$SIZE_T*3($ap_end)
894	$ST $acc3,$SIZE_T*4($ap_end)
895
896	b .Lmul4x_done
897
898	.align 4
899	.Lmul4x4_post_condition:
900	$POP $ap,$SIZE_T*6($sp) # pull &rp[-1]
901	$POP $bp,0($sp) # pull saved sp
902	addze $carry,$carry # modulo-scheduled
903	# $acc0-3,$carry hold result, $m0-3 hold modulus
904	subfc $a0,$m0,$acc0
905	subfe $a1,$m1,$acc1
906	subfe $a2,$m2,$acc2
907	subfe $a3,$m3,$acc3
908	subfe $carry,$zero,$carry # did it borrow?
909
910	and $m0,$m0,$carry
911	and $m1,$m1,$carry
912	addc $a0,$a0,$m0
913	and $m2,$m2,$carry
914	adde $a1,$a1,$m1
915	and $m3,$m3,$carry
916	adde $a2,$a2,$m2
917	adde $a3,$a3,$m3
918
919	$ST $a0,$SIZE_T*1($ap) # write result
920	$ST $a1,$SIZE_T*2($ap)
921	$ST $a2,$SIZE_T*3($ap)
922	$ST $a3,$SIZE_T*4($ap)
923
924	.Lmul4x_done:
925	$ST $zero,$SIZE_T*8($sp) # wipe stack clean
926	$ST $zero,$SIZE_T*9($sp)
927	$ST $zero,$SIZE_T*10($sp)
928	$ST $zero,$SIZE_T*11($sp)
929	li r3,1 # signal "done"
930	$POP r14,-$SIZE_T*18($bp)
931	$POP r15,-$SIZE_T*17($bp)
932	$POP r16,-$SIZE_T*16($bp)
933	$POP r17,-$SIZE_T*15($bp)
934	$POP r18,-$SIZE_T*14($bp)
935	$POP r19,-$SIZE_T*13($bp)
936	$POP r20,-$SIZE_T*12($bp)
937	$POP r21,-$SIZE_T*11($bp)
938	$POP r22,-$SIZE_T*10($bp)
939	$POP r23,-$SIZE_T*9($bp)
940	$POP r24,-$SIZE_T*8($bp)
941	$POP r25,-$SIZE_T*7($bp)
942	$POP r26,-$SIZE_T*6($bp)
943	$POP r27,-$SIZE_T*5($bp)
944	$POP r28,-$SIZE_T*4($bp)
945	$POP r29,-$SIZE_T*3($bp)
946	$POP r30,-$SIZE_T*2($bp)
947	$POP r31,-$SIZE_T*1($bp)
948	mr $sp,$bp
949	blr
950	.long 0
951	.byte 0,12,4,0x20,0x80,18,6,0
952	.long 0
953	.size .bn_mul4x_mont_int,.-.bn_mul4x_mont_int
954	___
955	}
956
957	if (1) {
958	########################################################################
959	# Following is PPC adaptation of sqrx8x_mont from x86_64-mont5 module.
960
961	my ($a0,$a1,$a2,$a3,$a4,$a5,$a6,$a7)=map("r$_",(9..12,14..17));
962	my ($t0,$t1,$t2,$t3)=map("r$_",(18..21));
963	my ($acc0,$acc1,$acc2,$acc3,$acc4,$acc5,$acc6,$acc7)=map("r$_",(22..29));
964	my ($cnt,$carry,$zero)=("r30","r31","r0");
965	my ($tp,$ap_end,$na0)=($bp,$np,$carry);
966
967	# sp----------->+-------------------------------+
968	# \| saved sp \|
969	# +-------------------------------+
970	# . .
971	# +12*size_t +-------------------------------+
972	# \| size_t tmp[2*num] \|
973	# . .
974	# . .
975	# . .
976	# +-------------------------------+
977	# . .
978	# -18*size_t +-------------------------------+
979	# \| 18 saved gpr, r14-r31 \|
980	# . .
981	# . .
982	# +-------------------------------+
983	$code.=<<___;
984	.align 5
985	__bn_sqr8x_mont:
986	.Lsqr8x_do:
987	mr $a0,$sp
988	slwi $a1,$num,`log($SIZE_T)/log(2)+1`
989	li $a2,-32*$SIZE_T
990	sub $a1,$a2,$a1
991	slwi $num,$num,`log($SIZE_T)/log(2)`
992	$STUX $sp,$sp,$a1 # alloca
993
994	$PUSH r14,-$SIZE_T*18($a0)
995	$PUSH r15,-$SIZE_T*17($a0)
996	$PUSH r16,-$SIZE_T*16($a0)
997	$PUSH r17,-$SIZE_T*15($a0)
998	$PUSH r18,-$SIZE_T*14($a0)
999	$PUSH r19,-$SIZE_T*13($a0)
1000	$PUSH r20,-$SIZE_T*12($a0)
1001	$PUSH r21,-$SIZE_T*11($a0)
1002	$PUSH r22,-$SIZE_T*10($a0)
1003	$PUSH r23,-$SIZE_T*9($a0)
1004	$PUSH r24,-$SIZE_T*8($a0)
1005	$PUSH r25,-$SIZE_T*7($a0)
1006	$PUSH r26,-$SIZE_T*6($a0)
1007	$PUSH r27,-$SIZE_T*5($a0)
1008	$PUSH r28,-$SIZE_T*4($a0)
1009	$PUSH r29,-$SIZE_T*3($a0)
1010	$PUSH r30,-$SIZE_T*2($a0)
1011	$PUSH r31,-$SIZE_T*1($a0)
1012
1013	subi $ap,$ap,$SIZE_T # bias by -1
1014	subi $t0,$np,$SIZE_T # bias by -1
1015	subi $rp,$rp,$SIZE_T # bias by -1
1016	$LD $n0,0($n0) # *n0
1017	li $zero,0
1018
1019	add $ap_end,$ap,$num
1020	$LD $a0,$SIZE_T*1($ap)
1021	#li $acc0,0
1022	$LD $a1,$SIZE_T*2($ap)
1023	li $acc1,0
1024	$LD $a2,$SIZE_T*3($ap)
1025	li $acc2,0
1026	$LD $a3,$SIZE_T*4($ap)
1027	li $acc3,0
1028	$LD $a4,$SIZE_T*5($ap)
1029	li $acc4,0
1030	$LD $a5,$SIZE_T*6($ap)
1031	li $acc5,0
1032	$LD $a6,$SIZE_T*7($ap)
1033	li $acc6,0
1034	$LDU $a7,$SIZE_T*8($ap)
1035	li $acc7,0
1036
1037	addi $tp,$sp,$SIZE_T*11 # &tp[-1]
1038	subic. $cnt,$num,$SIZE_T*8
1039	b .Lsqr8x_zero_start
1040
1041	.align 5
1042	.Lsqr8x_zero:
1043	subic. $cnt,$cnt,$SIZE_T*8
1044	$ST $zero,$SIZE_T*1($tp)
1045	$ST $zero,$SIZE_T*2($tp)
1046	$ST $zero,$SIZE_T*3($tp)
1047	$ST $zero,$SIZE_T*4($tp)
1048	$ST $zero,$SIZE_T*5($tp)
1049	$ST $zero,$SIZE_T*6($tp)
1050	$ST $zero,$SIZE_T*7($tp)
1051	$ST $zero,$SIZE_T*8($tp)
1052	.Lsqr8x_zero_start:
1053	$ST $zero,$SIZE_T*9($tp)
1054	$ST $zero,$SIZE_T*10($tp)
1055	$ST $zero,$SIZE_T*11($tp)
1056	$ST $zero,$SIZE_T*12($tp)
1057	$ST $zero,$SIZE_T*13($tp)
1058	$ST $zero,$SIZE_T*14($tp)
1059	$ST $zero,$SIZE_T*15($tp)
1060	$STU $zero,$SIZE_T*16($tp)
1061	bne .Lsqr8x_zero
1062
1063	$PUSH $rp,$SIZE_T*6($sp) # offload &rp[-1]
1064	$PUSH $t0,$SIZE_T*7($sp) # offload &np[-1]
1065	$PUSH $n0,$SIZE_T*8($sp) # offload n0
1066	$PUSH $tp,$SIZE_T9($sp) # &tp[2num-1]
1067	$PUSH $zero,$SIZE_T*10($sp) # initial top-most carry
1068	addi $tp,$sp,$SIZE_T*11 # &tp[-1]
1069
1070	# Multiply everything but a[i]*a[i]
1071	.align 5
1072	.Lsqr8x_outer_loop:
1073	# a[1]a[0] (i)
1074	# a[2]a[0]
1075	# a[3]a[0]
1076	# a[4]a[0]
1077	# a[5]a[0]
1078	# a[6]a[0]
1079	# a[7]a[0]
1080	# a[2]a[1] (ii)
1081	# a[3]a[1]
1082	# a[4]a[1]
1083	# a[5]a[1]
1084	# a[6]a[1]
1085	# a[7]a[1]
1086	# a[3]a[2] (iii)
1087	# a[4]a[2]
1088	# a[5]a[2]
1089	# a[6]a[2]
1090	# a[7]a[2]
1091	# a[4]a[3] (iv)
1092	# a[5]a[3]
1093	# a[6]a[3]
1094	# a[7]a[3]
1095	# a[5]a[4] (v)
1096	# a[6]a[4]
1097	# a[7]a[4]
1098	# a[6]a[5] (vi)
1099	# a[7]a[5]
1100	# a[7]a[6] (vii)
1101
1102	$UMULL $t0,$a1,$a0 # lo(a[1..7]*a[0]) (i)
1103	$UMULL $t1,$a2,$a0
1104	$UMULL $t2,$a3,$a0
1105	$UMULL $t3,$a4,$a0
1106	addc $acc1,$acc1,$t0 # t[1]+lo(a[1]*a[0])
1107	$UMULL $t0,$a5,$a0
1108	adde $acc2,$acc2,$t1
1109	$UMULL $t1,$a6,$a0
1110	adde $acc3,$acc3,$t2
1111	$UMULL $t2,$a7,$a0
1112	adde $acc4,$acc4,$t3
1113	$UMULH $t3,$a1,$a0 # hi(a[1..7]*a[0])
1114	adde $acc5,$acc5,$t0
1115	$UMULH $t0,$a2,$a0
1116	adde $acc6,$acc6,$t1
1117	$UMULH $t1,$a3,$a0
1118	adde $acc7,$acc7,$t2
1119	$UMULH $t2,$a4,$a0
1120	$ST $acc0,$SIZE_T*1($tp) # t[0]
1121	addze $acc0,$zero # t[8]
1122	$ST $acc1,$SIZE_T*2($tp) # t[1]
1123	addc $acc2,$acc2,$t3 # t[2]+lo(a[1]*a[0])
1124	$UMULH $t3,$a5,$a0
1125	adde $acc3,$acc3,$t0
1126	$UMULH $t0,$a6,$a0
1127	adde $acc4,$acc4,$t1
1128	$UMULH $t1,$a7,$a0
1129	adde $acc5,$acc5,$t2
1130	$UMULL $t2,$a2,$a1 # lo(a[2..7]*a[1]) (ii)
1131	adde $acc6,$acc6,$t3
1132	$UMULL $t3,$a3,$a1
1133	adde $acc7,$acc7,$t0
1134	$UMULL $t0,$a4,$a1
1135	adde $acc0,$acc0,$t1
1136
1137	$UMULL $t1,$a5,$a1
1138	addc $acc3,$acc3,$t2
1139	$UMULL $t2,$a6,$a1
1140	adde $acc4,$acc4,$t3
1141	$UMULL $t3,$a7,$a1
1142	adde $acc5,$acc5,$t0
1143	$UMULH $t0,$a2,$a1 # hi(a[2..7]*a[1])
1144	adde $acc6,$acc6,$t1
1145	$UMULH $t1,$a3,$a1
1146	adde $acc7,$acc7,$t2
1147	$UMULH $t2,$a4,$a1
1148	adde $acc0,$acc0,$t3
1149	$UMULH $t3,$a5,$a1
1150	$ST $acc2,$SIZE_T*3($tp) # t[2]
1151	addze $acc1,$zero # t[9]
1152	$ST $acc3,$SIZE_T*4($tp) # t[3]
1153	addc $acc4,$acc4,$t0
1154	$UMULH $t0,$a6,$a1
1155	adde $acc5,$acc5,$t1
1156	$UMULH $t1,$a7,$a1
1157	adde $acc6,$acc6,$t2
1158	$UMULL $t2,$a3,$a2 # lo(a[3..7]*a[2]) (iii)
1159	adde $acc7,$acc7,$t3
1160	$UMULL $t3,$a4,$a2
1161	adde $acc0,$acc0,$t0
1162	$UMULL $t0,$a5,$a2
1163	adde $acc1,$acc1,$t1
1164
1165	$UMULL $t1,$a6,$a2
1166	addc $acc5,$acc5,$t2
1167	$UMULL $t2,$a7,$a2
1168	adde $acc6,$acc6,$t3
1169	$UMULH $t3,$a3,$a2 # hi(a[3..7]*a[2])
1170	adde $acc7,$acc7,$t0
1171	$UMULH $t0,$a4,$a2
1172	adde $acc0,$acc0,$t1
1173	$UMULH $t1,$a5,$a2
1174	adde $acc1,$acc1,$t2
1175	$UMULH $t2,$a6,$a2
1176	$ST $acc4,$SIZE_T*5($tp) # t[4]
1177	addze $acc2,$zero # t[10]
1178	$ST $acc5,$SIZE_T*6($tp) # t[5]
1179	addc $acc6,$acc6,$t3
1180	$UMULH $t3,$a7,$a2
1181	adde $acc7,$acc7,$t0
1182	$UMULL $t0,$a4,$a3 # lo(a[4..7]*a[3]) (iv)
1183	adde $acc0,$acc0,$t1
1184	$UMULL $t1,$a5,$a3
1185	adde $acc1,$acc1,$t2
1186	$UMULL $t2,$a6,$a3
1187	adde $acc2,$acc2,$t3
1188
1189	$UMULL $t3,$a7,$a3
1190	addc $acc7,$acc7,$t0
1191	$UMULH $t0,$a4,$a3 # hi(a[4..7]*a[3])
1192	adde $acc0,$acc0,$t1
1193	$UMULH $t1,$a5,$a3
1194	adde $acc1,$acc1,$t2
1195	$UMULH $t2,$a6,$a3
1196	adde $acc2,$acc2,$t3
1197	$UMULH $t3,$a7,$a3
1198	$ST $acc6,$SIZE_T*7($tp) # t[6]
1199	addze $acc3,$zero # t[11]
1200	$STU $acc7,$SIZE_T*8($tp) # t[7]
1201	addc $acc0,$acc0,$t0
1202	$UMULL $t0,$a5,$a4 # lo(a[5..7]*a[4]) (v)
1203	adde $acc1,$acc1,$t1
1204	$UMULL $t1,$a6,$a4
1205	adde $acc2,$acc2,$t2
1206	$UMULL $t2,$a7,$a4
1207	adde $acc3,$acc3,$t3
1208
1209	$UMULH $t3,$a5,$a4 # hi(a[5..7]*a[4])
1210	addc $acc1,$acc1,$t0
1211	$UMULH $t0,$a6,$a4
1212	adde $acc2,$acc2,$t1
1213	$UMULH $t1,$a7,$a4
1214	adde $acc3,$acc3,$t2
1215	$UMULL $t2,$a6,$a5 # lo(a[6..7]*a[5]) (vi)
1216	addze $acc4,$zero # t[12]
1217	addc $acc2,$acc2,$t3
1218	$UMULL $t3,$a7,$a5
1219	adde $acc3,$acc3,$t0
1220	$UMULH $t0,$a6,$a5 # hi(a[6..7]*a[5])
1221	adde $acc4,$acc4,$t1
1222
1223	$UMULH $t1,$a7,$a5
1224	addc $acc3,$acc3,$t2
1225	$UMULL $t2,$a7,$a6 # lo(a[7]*a[6]) (vii)
1226	adde $acc4,$acc4,$t3
1227	$UMULH $t3,$a7,$a6 # hi(a[7]*a[6])
1228	addze $acc5,$zero # t[13]
1229	addc $acc4,$acc4,$t0
1230	$UCMP $ap_end,$ap # done yet?
1231	adde $acc5,$acc5,$t1
1232
1233	addc $acc5,$acc5,$t2
1234	sub $t0,$ap_end,$num # rewinded ap
1235	addze $acc6,$zero # t[14]
1236	add $acc6,$acc6,$t3
1237
1238	beq .Lsqr8x_outer_break
1239
1240	mr $n0,$a0
1241	$LD $a0,$SIZE_T*1($tp)
1242	$LD $a1,$SIZE_T*2($tp)
1243	$LD $a2,$SIZE_T*3($tp)
1244	$LD $a3,$SIZE_T*4($tp)
1245	$LD $a4,$SIZE_T*5($tp)
1246	$LD $a5,$SIZE_T*6($tp)
1247	$LD $a6,$SIZE_T*7($tp)
1248	$LD $a7,$SIZE_T*8($tp)
1249	addc $acc0,$acc0,$a0
1250	$LD $a0,$SIZE_T*1($ap)
1251	adde $acc1,$acc1,$a1
1252	$LD $a1,$SIZE_T*2($ap)
1253	adde $acc2,$acc2,$a2
1254	$LD $a2,$SIZE_T*3($ap)
1255	adde $acc3,$acc3,$a3
1256	$LD $a3,$SIZE_T*4($ap)
1257	adde $acc4,$acc4,$a4
1258	$LD $a4,$SIZE_T*5($ap)
1259	adde $acc5,$acc5,$a5
1260	$LD $a5,$SIZE_T*6($ap)
1261	adde $acc6,$acc6,$a6
1262	$LD $a6,$SIZE_T*7($ap)
1263	subi $rp,$ap,$SIZE_T*7
1264	addze $acc7,$a7
1265	$LDU $a7,$SIZE_T*8($ap)
1266	#addze $carry,$zero # moved below
1267	li $cnt,0
1268	b .Lsqr8x_mul
1269
1270	# a[8]a[0]
1271	# a[9]a[0]
1272	# a[a]a[0]
1273	# a[b]a[0]
1274	# a[c]a[0]
1275	# a[d]a[0]
1276	# a[e]a[0]
1277	# a[f]a[0]
1278	# a[8]a[1]
1279	# a[f]a[1]........................
1280	# a[8]a[2]
1281	# a[f]a[2]........................
1282	# a[8]a[3]
1283	# a[f]a[3]........................
1284	# a[8]a[4]
1285	# a[f]a[4]........................
1286	# a[8]a[5]
1287	# a[f]a[5]........................
1288	# a[8]a[6]
1289	# a[f]a[6]........................
1290	# a[8]a[7]
1291	# a[f]a[7]........................
1292	.align 5
1293	.Lsqr8x_mul:
1294	$UMULL $t0,$a0,$n0
1295	addze $carry,$zero # carry bit, modulo-scheduled
1296	$UMULL $t1,$a1,$n0
1297	addi $cnt,$cnt,$SIZE_T
1298	$UMULL $t2,$a2,$n0
1299	andi. $cnt,$cnt,$SIZE_T*8-1
1300	$UMULL $t3,$a3,$n0
1301	addc $acc0,$acc0,$t0
1302	$UMULL $t0,$a4,$n0
1303	adde $acc1,$acc1,$t1
1304	$UMULL $t1,$a5,$n0
1305	adde $acc2,$acc2,$t2
1306	$UMULL $t2,$a6,$n0
1307	adde $acc3,$acc3,$t3
1308	$UMULL $t3,$a7,$n0
1309	adde $acc4,$acc4,$t0
1310	$UMULH $t0,$a0,$n0
1311	adde $acc5,$acc5,$t1
1312	$UMULH $t1,$a1,$n0
1313	adde $acc6,$acc6,$t2
1314	$UMULH $t2,$a2,$n0
1315	adde $acc7,$acc7,$t3
1316	$UMULH $t3,$a3,$n0
1317	addze $carry,$carry
1318	$STU $acc0,$SIZE_T($tp)
1319	addc $acc0,$acc1,$t0
1320	$UMULH $t0,$a4,$n0
1321	adde $acc1,$acc2,$t1
1322	$UMULH $t1,$a5,$n0
1323	adde $acc2,$acc3,$t2
1324	$UMULH $t2,$a6,$n0
1325	adde $acc3,$acc4,$t3
1326	$UMULH $t3,$a7,$n0
1327	$LDX $n0,$rp,$cnt
1328	adde $acc4,$acc5,$t0
1329	adde $acc5,$acc6,$t1
1330	adde $acc6,$acc7,$t2
1331	adde $acc7,$carry,$t3
1332	#addze $carry,$zero # moved above
1333	bne .Lsqr8x_mul
1334	# note that carry flag is guaranteed
1335	# to be zero at this point
1336	$UCMP $ap,$ap_end # done yet?
1337	beq .Lsqr8x_break
1338
1339	$LD $a0,$SIZE_T*1($tp)
1340	$LD $a1,$SIZE_T*2($tp)
1341	$LD $a2,$SIZE_T*3($tp)
1342	$LD $a3,$SIZE_T*4($tp)
1343	$LD $a4,$SIZE_T*5($tp)
1344	$LD $a5,$SIZE_T*6($tp)
1345	$LD $a6,$SIZE_T*7($tp)
1346	$LD $a7,$SIZE_T*8($tp)
1347	addc $acc0,$acc0,$a0
1348	$LD $a0,$SIZE_T*1($ap)
1349	adde $acc1,$acc1,$a1
1350	$LD $a1,$SIZE_T*2($ap)
1351	adde $acc2,$acc2,$a2
1352	$LD $a2,$SIZE_T*3($ap)
1353	adde $acc3,$acc3,$a3
1354	$LD $a3,$SIZE_T*4($ap)
1355	adde $acc4,$acc4,$a4
1356	$LD $a4,$SIZE_T*5($ap)
1357	adde $acc5,$acc5,$a5
1358	$LD $a5,$SIZE_T*6($ap)
1359	adde $acc6,$acc6,$a6
1360	$LD $a6,$SIZE_T*7($ap)
1361	adde $acc7,$acc7,$a7
1362	$LDU $a7,$SIZE_T*8($ap)
1363	#addze $carry,$zero # moved above
1364	b .Lsqr8x_mul
1365
1366	.align 5
1367	.Lsqr8x_break:
1368	$LD $a0,$SIZE_T*8($rp)
1369	addi $ap,$rp,$SIZE_T*15
1370	$LD $a1,$SIZE_T*9($rp)
1371	sub. $t0,$ap_end,$ap # is it last iteration?
1372	$LD $a2,$SIZE_T*10($rp)
1373	sub $t1,$tp,$t0
1374	$LD $a3,$SIZE_T*11($rp)
1375	$LD $a4,$SIZE_T*12($rp)
1376	$LD $a5,$SIZE_T*13($rp)
1377	$LD $a6,$SIZE_T*14($rp)
1378	$LD $a7,$SIZE_T*15($rp)
1379	beq .Lsqr8x_outer_loop
1380
1381	$ST $acc0,$SIZE_T*1($tp)
1382	$LD $acc0,$SIZE_T*1($t1)
1383	$ST $acc1,$SIZE_T*2($tp)
1384	$LD $acc1,$SIZE_T*2($t1)
1385	$ST $acc2,$SIZE_T*3($tp)
1386	$LD $acc2,$SIZE_T*3($t1)
1387	$ST $acc3,$SIZE_T*4($tp)
1388	$LD $acc3,$SIZE_T*4($t1)
1389	$ST $acc4,$SIZE_T*5($tp)
1390	$LD $acc4,$SIZE_T*5($t1)
1391	$ST $acc5,$SIZE_T*6($tp)
1392	$LD $acc5,$SIZE_T*6($t1)
1393	$ST $acc6,$SIZE_T*7($tp)
1394	$LD $acc6,$SIZE_T*7($t1)
1395	$ST $acc7,$SIZE_T*8($tp)
1396	$LD $acc7,$SIZE_T*8($t1)
1397	mr $tp,$t1
1398	b .Lsqr8x_outer_loop
1399
1400	.align 5
1401	.Lsqr8x_outer_break:
1402	####################################################################
1403	# Now multiply above result by 2 and add a[n-1]a[n-1]\|...\|a[0]a[0]
1404	$LD $a1,$SIZE_T*1($t0) # recall that $t0 is &a[-1]
1405	$LD $a3,$SIZE_T*2($t0)
1406	$LD $a5,$SIZE_T*3($t0)
1407	$LD $a7,$SIZE_T*4($t0)
1408	addi $ap,$t0,$SIZE_T*4
1409	# "tp[x]" comments are for num==8 case
1410	$LD $t1,$SIZE_T*13($sp) # =tp[1], t[0] is not interesting
1411	$LD $t2,$SIZE_T*14($sp)
1412	$LD $t3,$SIZE_T*15($sp)
1413	$LD $t0,$SIZE_T*16($sp)
1414
1415	$ST $acc0,$SIZE_T*1($tp) # tp[8]=
1416	srwi $cnt,$num,`log($SIZE_T)/log(2)+2`
1417	$ST $acc1,$SIZE_T*2($tp)
1418	subi $cnt,$cnt,1
1419	$ST $acc2,$SIZE_T*3($tp)
1420	$ST $acc3,$SIZE_T*4($tp)
1421	$ST $acc4,$SIZE_T*5($tp)
1422	$ST $acc5,$SIZE_T*6($tp)
1423	$ST $acc6,$SIZE_T*7($tp)
1424	#$ST $acc7,$SIZE_T*8($tp) # tp[15] is not interesting
1425	addi $tp,$sp,$SIZE_T*11 # &tp[-1]
1426	$UMULL $acc0,$a1,$a1
1427	$UMULH $a1,$a1,$a1
1428	add $acc1,$t1,$t1 # <<1
1429	$SHRI $t1,$t1,$BITS-1
1430	$UMULL $a2,$a3,$a3
1431	$UMULH $a3,$a3,$a3
1432	addc $acc1,$acc1,$a1
1433	add $acc2,$t2,$t2
1434	$SHRI $t2,$t2,$BITS-1
1435	add $acc3,$t3,$t3
1436	$SHRI $t3,$t3,$BITS-1
1437	or $acc2,$acc2,$t1
1438
1439	mtctr $cnt
1440	.Lsqr4x_shift_n_add:
1441	$UMULL $a4,$a5,$a5
1442	$UMULH $a5,$a5,$a5
1443	$LD $t1,$SIZE_T*6($tp) # =tp[5]
1444	$LD $a1,$SIZE_T*1($ap)
1445	adde $acc2,$acc2,$a2
1446	add $acc4,$t0,$t0
1447	$SHRI $t0,$t0,$BITS-1
1448	or $acc3,$acc3,$t2
1449	$LD $t2,$SIZE_T*7($tp) # =tp[6]
1450	adde $acc3,$acc3,$a3
1451	$LD $a3,$SIZE_T*2($ap)
1452	add $acc5,$t1,$t1
1453	$SHRI $t1,$t1,$BITS-1
1454	or $acc4,$acc4,$t3
1455	$LD $t3,$SIZE_T*8($tp) # =tp[7]
1456	$UMULL $a6,$a7,$a7
1457	$UMULH $a7,$a7,$a7
1458	adde $acc4,$acc4,$a4
1459	add $acc6,$t2,$t2
1460	$SHRI $t2,$t2,$BITS-1
1461	or $acc5,$acc5,$t0
1462	$LD $t0,$SIZE_T*9($tp) # =tp[8]
1463	adde $acc5,$acc5,$a5
1464	$LD $a5,$SIZE_T*3($ap)
1465	add $acc7,$t3,$t3
1466	$SHRI $t3,$t3,$BITS-1
1467	or $acc6,$acc6,$t1
1468	$LD $t1,$SIZE_T*10($tp) # =tp[9]
1469	$UMULL $a0,$a1,$a1
1470	$UMULH $a1,$a1,$a1
1471	adde $acc6,$acc6,$a6
1472	$ST $acc0,$SIZE_T*1($tp) # tp[0]=
1473	add $acc0,$t0,$t0
1474	$SHRI $t0,$t0,$BITS-1
1475	or $acc7,$acc7,$t2
1476	$LD $t2,$SIZE_T*11($tp) # =tp[10]
1477	adde $acc7,$acc7,$a7
1478	$LDU $a7,$SIZE_T*4($ap)
1479	$ST $acc1,$SIZE_T*2($tp) # tp[1]=
1480	add $acc1,$t1,$t1
1481	$SHRI $t1,$t1,$BITS-1
1482	or $acc0,$acc0,$t3
1483	$LD $t3,$SIZE_T*12($tp) # =tp[11]
1484	$UMULL $a2,$a3,$a3
1485	$UMULH $a3,$a3,$a3
1486	adde $acc0,$acc0,$a0
1487	$ST $acc2,$SIZE_T*3($tp) # tp[2]=
1488	add $acc2,$t2,$t2
1489	$SHRI $t2,$t2,$BITS-1
1490	or $acc1,$acc1,$t0
1491	$LD $t0,$SIZE_T*13($tp) # =tp[12]
1492	adde $acc1,$acc1,$a1
1493	$ST $acc3,$SIZE_T*4($tp) # tp[3]=
1494	$ST $acc4,$SIZE_T*5($tp) # tp[4]=
1495	$ST $acc5,$SIZE_T*6($tp) # tp[5]=
1496	$ST $acc6,$SIZE_T*7($tp) # tp[6]=
1497	$STU $acc7,$SIZE_T*8($tp) # tp[7]=
1498	add $acc3,$t3,$t3
1499	$SHRI $t3,$t3,$BITS-1
1500	or $acc2,$acc2,$t1
1501	bdnz .Lsqr4x_shift_n_add
1502	___
1503	my ($np,$np_end)=($ap,$ap_end);
1504	$code.=<<___;
1505	$POP $np,$SIZE_T*7($sp) # pull &np[-1] and n0
1506	$POP $n0,$SIZE_T*8($sp)
1507
1508	$UMULL $a4,$a5,$a5
1509	$UMULH $a5,$a5,$a5
1510	$ST $acc0,$SIZE_T*1($tp) # tp[8]=
1511	$LD $acc0,$SIZE_T*12($sp) # =tp[0]
1512	$LD $t1,$SIZE_T*6($tp) # =tp[13]
1513	adde $acc2,$acc2,$a2
1514	add $acc4,$t0,$t0
1515	$SHRI $t0,$t0,$BITS-1
1516	or $acc3,$acc3,$t2
1517	$LD $t2,$SIZE_T*7($tp) # =tp[14]
1518	adde $acc3,$acc3,$a3
1519	add $acc5,$t1,$t1
1520	$SHRI $t1,$t1,$BITS-1
1521	or $acc4,$acc4,$t3
1522	$UMULL $a6,$a7,$a7
1523	$UMULH $a7,$a7,$a7
1524	adde $acc4,$acc4,$a4
1525	add $acc6,$t2,$t2
1526	$SHRI $t2,$t2,$BITS-1
1527	or $acc5,$acc5,$t0
1528	$ST $acc1,$SIZE_T*2($tp) # tp[9]=
1529	$LD $acc1,$SIZE_T*13($sp) # =tp[1]
1530	adde $acc5,$acc5,$a5
1531	or $acc6,$acc6,$t1
1532	$LD $a0,$SIZE_T*1($np)
1533	$LD $a1,$SIZE_T*2($np)
1534	adde $acc6,$acc6,$a6
1535	$LD $a2,$SIZE_T*3($np)
1536	$LD $a3,$SIZE_T*4($np)
1537	adde $acc7,$a7,$t2
1538	$LD $a4,$SIZE_T*5($np)
1539	$LD $a5,$SIZE_T*6($np)
1540
1541	################################################################
1542	# Reduce by 8 limbs per iteration
1543	$UMULL $na0,$n0,$acc0 # t[0]*n0
1544	li $cnt,8
1545	$LD $a6,$SIZE_T*7($np)
1546	add $np_end,$np,$num
1547	$LDU $a7,$SIZE_T*8($np)
1548	$ST $acc2,$SIZE_T*3($tp) # tp[10]=
1549	$LD $acc2,$SIZE_T*14($sp)
1550	$ST $acc3,$SIZE_T*4($tp) # tp[11]=
1551	$LD $acc3,$SIZE_T*15($sp)
1552	$ST $acc4,$SIZE_T*5($tp) # tp[12]=
1553	$LD $acc4,$SIZE_T*16($sp)
1554	$ST $acc5,$SIZE_T*6($tp) # tp[13]=
1555	$LD $acc5,$SIZE_T*17($sp)
1556	$ST $acc6,$SIZE_T*7($tp) # tp[14]=
1557	$LD $acc6,$SIZE_T*18($sp)
1558	$ST $acc7,$SIZE_T*8($tp) # tp[15]=
1559	$LD $acc7,$SIZE_T*19($sp)
1560	addi $tp,$sp,$SIZE_T*11 # &tp[-1]
1561	mtctr $cnt
1562	b .Lsqr8x_reduction
1563
1564	.align 5
1565	.Lsqr8x_reduction:
1566	# () $UMULL $t0,$a0,$na0 # lo(n[0-7])lo(t[0]*n0)
1567	$UMULL $t1,$a1,$na0
1568	$UMULL $t2,$a2,$na0
1569	$STU $na0,$SIZE_T($tp) # put aside t[0]*n0 for tail processing
1570	$UMULL $t3,$a3,$na0
1571	# (*) addc $acc0,$acc0,$t0
1572	addic $acc0,$acc0,-1 # (*)
1573	$UMULL $t0,$a4,$na0
1574	adde $acc0,$acc1,$t1
1575	$UMULL $t1,$a5,$na0
1576	adde $acc1,$acc2,$t2
1577	$UMULL $t2,$a6,$na0
1578	adde $acc2,$acc3,$t3
1579	$UMULL $t3,$a7,$na0
1580	adde $acc3,$acc4,$t0
1581	$UMULH $t0,$a0,$na0 # hi(n[0-7])lo(t[0]n0)
1582	adde $acc4,$acc5,$t1
1583	$UMULH $t1,$a1,$na0
1584	adde $acc5,$acc6,$t2
1585	$UMULH $t2,$a2,$na0
1586	adde $acc6,$acc7,$t3
1587	$UMULH $t3,$a3,$na0
1588	addze $acc7,$zero
1589	addc $acc0,$acc0,$t0
1590	$UMULH $t0,$a4,$na0
1591	adde $acc1,$acc1,$t1
1592	$UMULH $t1,$a5,$na0
1593	adde $acc2,$acc2,$t2
1594	$UMULH $t2,$a6,$na0
1595	adde $acc3,$acc3,$t3
1596	$UMULH $t3,$a7,$na0
1597	$UMULL $na0,$n0,$acc0 # next t[0]*n0
1598	adde $acc4,$acc4,$t0
1599	adde $acc5,$acc5,$t1
1600	adde $acc6,$acc6,$t2
1601	adde $acc7,$acc7,$t3
1602	bdnz .Lsqr8x_reduction
1603
1604	$LD $t0,$SIZE_T*1($tp)
1605	$LD $t1,$SIZE_T*2($tp)
1606	$LD $t2,$SIZE_T*3($tp)
1607	$LD $t3,$SIZE_T*4($tp)
1608	subi $rp,$tp,$SIZE_T*7
1609	$UCMP $np_end,$np # done yet?
1610	addc $acc0,$acc0,$t0
1611	$LD $t0,$SIZE_T*5($tp)
1612	adde $acc1,$acc1,$t1
1613	$LD $t1,$SIZE_T*6($tp)
1614	adde $acc2,$acc2,$t2
1615	$LD $t2,$SIZE_T*7($tp)
1616	adde $acc3,$acc3,$t3
1617	$LD $t3,$SIZE_T*8($tp)
1618	adde $acc4,$acc4,$t0
1619	adde $acc5,$acc5,$t1
1620	adde $acc6,$acc6,$t2
1621	adde $acc7,$acc7,$t3
1622	#addze $carry,$zero # moved below
1623	beq .Lsqr8x8_post_condition
1624
1625	$LD $n0,$SIZE_T*0($rp)
1626	$LD $a0,$SIZE_T*1($np)
1627	$LD $a1,$SIZE_T*2($np)
1628	$LD $a2,$SIZE_T*3($np)
1629	$LD $a3,$SIZE_T*4($np)
1630	$LD $a4,$SIZE_T*5($np)
1631	$LD $a5,$SIZE_T*6($np)
1632	$LD $a6,$SIZE_T*7($np)
1633	$LDU $a7,$SIZE_T*8($np)
1634	li $cnt,0
1635
1636	.align 5
1637	.Lsqr8x_tail:
1638	$UMULL $t0,$a0,$n0
1639	addze $carry,$zero # carry bit, modulo-scheduled
1640	$UMULL $t1,$a1,$n0
1641	addi $cnt,$cnt,$SIZE_T
1642	$UMULL $t2,$a2,$n0
1643	andi. $cnt,$cnt,$SIZE_T*8-1
1644	$UMULL $t3,$a3,$n0
1645	addc $acc0,$acc0,$t0
1646	$UMULL $t0,$a4,$n0
1647	adde $acc1,$acc1,$t1
1648	$UMULL $t1,$a5,$n0
1649	adde $acc2,$acc2,$t2
1650	$UMULL $t2,$a6,$n0
1651	adde $acc3,$acc3,$t3
1652	$UMULL $t3,$a7,$n0
1653	adde $acc4,$acc4,$t0
1654	$UMULH $t0,$a0,$n0
1655	adde $acc5,$acc5,$t1
1656	$UMULH $t1,$a1,$n0
1657	adde $acc6,$acc6,$t2
1658	$UMULH $t2,$a2,$n0
1659	adde $acc7,$acc7,$t3
1660	$UMULH $t3,$a3,$n0
1661	addze $carry,$carry
1662	$STU $acc0,$SIZE_T($tp)
1663	addc $acc0,$acc1,$t0
1664	$UMULH $t0,$a4,$n0
1665	adde $acc1,$acc2,$t1
1666	$UMULH $t1,$a5,$n0
1667	adde $acc2,$acc3,$t2
1668	$UMULH $t2,$a6,$n0
1669	adde $acc3,$acc4,$t3
1670	$UMULH $t3,$a7,$n0
1671	$LDX $n0,$rp,$cnt
1672	adde $acc4,$acc5,$t0
1673	adde $acc5,$acc6,$t1
1674	adde $acc6,$acc7,$t2
1675	adde $acc7,$carry,$t3
1676	#addze $carry,$zero # moved above
1677	bne .Lsqr8x_tail
1678	# note that carry flag is guaranteed
1679	# to be zero at this point
1680	$LD $a0,$SIZE_T*1($tp)
1681	$POP $carry,$SIZE_T*10($sp) # pull top-most carry in case we break
1682	$UCMP $np_end,$np # done yet?
1683	$LD $a1,$SIZE_T*2($tp)
1684	sub $t2,$np_end,$num # rewinded np
1685	$LD $a2,$SIZE_T*3($tp)
1686	$LD $a3,$SIZE_T*4($tp)
1687	$LD $a4,$SIZE_T*5($tp)
1688	$LD $a5,$SIZE_T*6($tp)
1689	$LD $a6,$SIZE_T*7($tp)
1690	$LD $a7,$SIZE_T*8($tp)
1691	beq .Lsqr8x_tail_break
1692
1693	addc $acc0,$acc0,$a0
1694	$LD $a0,$SIZE_T*1($np)
1695	adde $acc1,$acc1,$a1
1696	$LD $a1,$SIZE_T*2($np)
1697	adde $acc2,$acc2,$a2
1698	$LD $a2,$SIZE_T*3($np)
1699	adde $acc3,$acc3,$a3
1700	$LD $a3,$SIZE_T*4($np)
1701	adde $acc4,$acc4,$a4
1702	$LD $a4,$SIZE_T*5($np)
1703	adde $acc5,$acc5,$a5
1704	$LD $a5,$SIZE_T*6($np)
1705	adde $acc6,$acc6,$a6
1706	$LD $a6,$SIZE_T*7($np)
1707	adde $acc7,$acc7,$a7
1708	$LDU $a7,$SIZE_T*8($np)
1709	#addze $carry,$zero # moved above
1710	b .Lsqr8x_tail
1711
1712	.align 5
1713	.Lsqr8x_tail_break:
1714	$POP $n0,$SIZE_T*8($sp) # pull n0
1715	$POP $t3,$SIZE_T9($sp) # &tp[2num-1]
1716	addi $cnt,$tp,$SIZE_T*8 # end of current t[num] window
1717
1718	addic $carry,$carry,-1 # "move" top-most carry to carry bit
1719	adde $t0,$acc0,$a0
1720	$LD $acc0,$SIZE_T*8($rp)
1721	$LD $a0,$SIZE_T*1($t2) # recall that $t2 is &n[-1]
1722	adde $t1,$acc1,$a1
1723	$LD $acc1,$SIZE_T*9($rp)
1724	$LD $a1,$SIZE_T*2($t2)
1725	adde $acc2,$acc2,$a2
1726	$LD $a2,$SIZE_T*3($t2)
1727	adde $acc3,$acc3,$a3
1728	$LD $a3,$SIZE_T*4($t2)
1729	adde $acc4,$acc4,$a4
1730	$LD $a4,$SIZE_T*5($t2)
1731	adde $acc5,$acc5,$a5
1732	$LD $a5,$SIZE_T*6($t2)
1733	adde $acc6,$acc6,$a6
1734	$LD $a6,$SIZE_T*7($t2)
1735	adde $acc7,$acc7,$a7
1736	$LD $a7,$SIZE_T*8($t2)
1737	addi $np,$t2,$SIZE_T*8
1738	addze $t2,$zero # top-most carry
1739	$UMULL $na0,$n0,$acc0
1740	$ST $t0,$SIZE_T*1($tp)
1741	$UCMP $cnt,$t3 # did we hit the bottom?
1742	$ST $t1,$SIZE_T*2($tp)
1743	li $cnt,8
1744	$ST $acc2,$SIZE_T*3($tp)
1745	$LD $acc2,$SIZE_T*10($rp)
1746	$ST $acc3,$SIZE_T*4($tp)
1747	$LD $acc3,$SIZE_T*11($rp)
1748	$ST $acc4,$SIZE_T*5($tp)
1749	$LD $acc4,$SIZE_T*12($rp)
1750	$ST $acc5,$SIZE_T*6($tp)
1751	$LD $acc5,$SIZE_T*13($rp)
1752	$ST $acc6,$SIZE_T*7($tp)
1753	$LD $acc6,$SIZE_T*14($rp)
1754	$ST $acc7,$SIZE_T*8($tp)
1755	$LD $acc7,$SIZE_T*15($rp)
1756	$PUSH $t2,$SIZE_T*10($sp) # off-load top-most carry
1757	addi $tp,$rp,$SIZE_T*7 # slide the window
1758	mtctr $cnt
1759	bne .Lsqr8x_reduction
1760
1761	################################################################
1762	# Final step. We see if result is larger than modulus, and
1763	# if it is, subtract the modulus. But comparison implies
1764	# subtraction. So we subtract modulus, see if it borrowed,
1765	# and conditionally copy original value.
1766	$POP $rp,$SIZE_T*6($sp) # pull &rp[-1]
1767	srwi $cnt,$num,`log($SIZE_T)/log(2)+3`
1768	mr $n0,$tp # put tp aside
1769	addi $tp,$tp,$SIZE_T*8
1770	subi $cnt,$cnt,1
1771	subfc $t0,$a0,$acc0
1772	subfe $t1,$a1,$acc1
1773	mr $carry,$t2
1774	mr $ap_end,$rp # $rp copy
1775
1776	mtctr $cnt
1777	b .Lsqr8x_sub
1778
1779	.align 5
1780	.Lsqr8x_sub:
1781	$LD $a0,$SIZE_T*1($np)
1782	$LD $acc0,$SIZE_T*1($tp)
1783	$LD $a1,$SIZE_T*2($np)
1784	$LD $acc1,$SIZE_T*2($tp)
1785	subfe $t2,$a2,$acc2
1786	$LD $a2,$SIZE_T*3($np)
1787	$LD $acc2,$SIZE_T*3($tp)
1788	subfe $t3,$a3,$acc3
1789	$LD $a3,$SIZE_T*4($np)
1790	$LD $acc3,$SIZE_T*4($tp)
1791	$ST $t0,$SIZE_T*1($rp)
1792	subfe $t0,$a4,$acc4
1793	$LD $a4,$SIZE_T*5($np)
1794	$LD $acc4,$SIZE_T*5($tp)
1795	$ST $t1,$SIZE_T*2($rp)
1796	subfe $t1,$a5,$acc5
1797	$LD $a5,$SIZE_T*6($np)
1798	$LD $acc5,$SIZE_T*6($tp)
1799	$ST $t2,$SIZE_T*3($rp)
1800	subfe $t2,$a6,$acc6
1801	$LD $a6,$SIZE_T*7($np)
1802	$LD $acc6,$SIZE_T*7($tp)
1803	$ST $t3,$SIZE_T*4($rp)
1804	subfe $t3,$a7,$acc7
1805	$LDU $a7,$SIZE_T*8($np)
1806	$LDU $acc7,$SIZE_T*8($tp)
1807	$ST $t0,$SIZE_T*5($rp)
1808	subfe $t0,$a0,$acc0
1809	$ST $t1,$SIZE_T*6($rp)
1810	subfe $t1,$a1,$acc1
1811	$ST $t2,$SIZE_T*7($rp)
1812	$STU $t3,$SIZE_T*8($rp)
1813	bdnz .Lsqr8x_sub
1814
1815	srwi $cnt,$num,`log($SIZE_T)/log(2)+2`
1816	$LD $a0,$SIZE_T*1($ap_end) # original $rp
1817	$LD $acc0,$SIZE_T*1($n0) # original $tp
1818	subi $cnt,$cnt,1
1819	$LD $a1,$SIZE_T*2($ap_end)
1820	$LD $acc1,$SIZE_T*2($n0)
1821	subfe $t2,$a2,$acc2
1822	$LD $a2,$SIZE_T*3($ap_end)
1823	$LD $acc2,$SIZE_T*3($n0)
1824	subfe $t3,$a3,$acc3
1825	$LD $a3,$SIZE_T*4($ap_end)
1826	$LDU $acc3,$SIZE_T*4($n0)
1827	$ST $t0,$SIZE_T*1($rp)
1828	subfe $t0,$a4,$acc4
1829	$ST $t1,$SIZE_T*2($rp)
1830	subfe $t1,$a5,$acc5
1831	$ST $t2,$SIZE_T*3($rp)
1832	subfe $t2,$a6,$acc6
1833	$ST $t3,$SIZE_T*4($rp)
1834	subfe $t3,$a7,$acc7
1835	$ST $t0,$SIZE_T*5($rp)
1836	subfe $carry,$zero,$carry # did it borrow?
1837	$ST $t1,$SIZE_T*6($rp)
1838	$ST $t2,$SIZE_T*7($rp)
1839	$ST $t3,$SIZE_T*8($rp)
1840
1841	addi $tp,$sp,$SIZE_T*11
1842	mtctr $cnt
1843
1844	.Lsqr4x_cond_copy:
1845	andc $a0,$a0,$carry
1846	$ST $zero,-$SIZE_T*3($n0) # wipe stack clean
1847	and $acc0,$acc0,$carry
1848	$ST $zero,-$SIZE_T*2($n0)
1849	andc $a1,$a1,$carry
1850	$ST $zero,-$SIZE_T*1($n0)
1851	and $acc1,$acc1,$carry
1852	$ST $zero,-$SIZE_T*0($n0)
1853	andc $a2,$a2,$carry
1854	$ST $zero,$SIZE_T*1($tp)
1855	and $acc2,$acc2,$carry
1856	$ST $zero,$SIZE_T*2($tp)
1857	andc $a3,$a3,$carry
1858	$ST $zero,$SIZE_T*3($tp)
1859	and $acc3,$acc3,$carry
1860	$STU $zero,$SIZE_T*4($tp)
1861	or $t0,$a0,$acc0
1862	$LD $a0,$SIZE_T*5($ap_end)
1863	$LD $acc0,$SIZE_T*1($n0)
1864	or $t1,$a1,$acc1
1865	$LD $a1,$SIZE_T*6($ap_end)
1866	$LD $acc1,$SIZE_T*2($n0)
1867	or $t2,$a2,$acc2
1868	$LD $a2,$SIZE_T*7($ap_end)
1869	$LD $acc2,$SIZE_T*3($n0)
1870	or $t3,$a3,$acc3
1871	$LD $a3,$SIZE_T*8($ap_end)
1872	$LDU $acc3,$SIZE_T*4($n0)
1873	$ST $t0,$SIZE_T*1($ap_end)
1874	$ST $t1,$SIZE_T*2($ap_end)
1875	$ST $t2,$SIZE_T*3($ap_end)
1876	$STU $t3,$SIZE_T*4($ap_end)
1877	bdnz .Lsqr4x_cond_copy
1878
1879	$POP $ap,0($sp) # pull saved sp
1880	andc $a0,$a0,$carry
1881	and $acc0,$acc0,$carry
1882	andc $a1,$a1,$carry
1883	and $acc1,$acc1,$carry
1884	andc $a2,$a2,$carry
1885	and $acc2,$acc2,$carry
1886	andc $a3,$a3,$carry
1887	and $acc3,$acc3,$carry
1888	or $t0,$a0,$acc0
1889	or $t1,$a1,$acc1
1890	or $t2,$a2,$acc2
1891	or $t3,$a3,$acc3
1892	$ST $t0,$SIZE_T*1($ap_end)
1893	$ST $t1,$SIZE_T*2($ap_end)
1894	$ST $t2,$SIZE_T*3($ap_end)
1895	$ST $t3,$SIZE_T*4($ap_end)
1896
1897	b .Lsqr8x_done
1898
1899	.align 5
1900	.Lsqr8x8_post_condition:
1901	$POP $rp,$SIZE_T*6($sp) # pull rp
1902	$POP $ap,0($sp) # pull saved sp
1903	addze $carry,$zero
1904
1905	# $acc0-7,$carry hold result, $a0-7 hold modulus
1906	subfc $acc0,$a0,$acc0
1907	subfe $acc1,$a1,$acc1
1908	$ST $zero,$SIZE_T*12($sp) # wipe stack clean
1909	$ST $zero,$SIZE_T*13($sp)
1910	subfe $acc2,$a2,$acc2
1911	$ST $zero,$SIZE_T*14($sp)
1912	$ST $zero,$SIZE_T*15($sp)
1913	subfe $acc3,$a3,$acc3
1914	$ST $zero,$SIZE_T*16($sp)
1915	$ST $zero,$SIZE_T*17($sp)
1916	subfe $acc4,$a4,$acc4
1917	$ST $zero,$SIZE_T*18($sp)
1918	$ST $zero,$SIZE_T*19($sp)
1919	subfe $acc5,$a5,$acc5
1920	$ST $zero,$SIZE_T*20($sp)
1921	$ST $zero,$SIZE_T*21($sp)
1922	subfe $acc6,$a6,$acc6
1923	$ST $zero,$SIZE_T*22($sp)
1924	$ST $zero,$SIZE_T*23($sp)
1925	subfe $acc7,$a7,$acc7
1926	$ST $zero,$SIZE_T*24($sp)
1927	$ST $zero,$SIZE_T*25($sp)
1928	subfe $carry,$zero,$carry # did it borrow?
1929	$ST $zero,$SIZE_T*26($sp)
1930	$ST $zero,$SIZE_T*27($sp)
1931
1932	and $a0,$a0,$carry
1933	and $a1,$a1,$carry
1934	addc $acc0,$acc0,$a0 # add modulus back if borrowed
1935	and $a2,$a2,$carry
1936	adde $acc1,$acc1,$a1
1937	and $a3,$a3,$carry
1938	adde $acc2,$acc2,$a2
1939	and $a4,$a4,$carry
1940	adde $acc3,$acc3,$a3
1941	and $a5,$a5,$carry
1942	adde $acc4,$acc4,$a4
1943	and $a6,$a6,$carry
1944	adde $acc5,$acc5,$a5
1945	and $a7,$a7,$carry
1946	adde $acc6,$acc6,$a6
1947	adde $acc7,$acc7,$a7
1948	$ST $acc0,$SIZE_T*1($rp)
1949	$ST $acc1,$SIZE_T*2($rp)
1950	$ST $acc2,$SIZE_T*3($rp)
1951	$ST $acc3,$SIZE_T*4($rp)
1952	$ST $acc4,$SIZE_T*5($rp)
1953	$ST $acc5,$SIZE_T*6($rp)
1954	$ST $acc6,$SIZE_T*7($rp)
1955	$ST $acc7,$SIZE_T*8($rp)
1956
1957	.Lsqr8x_done:
1958	$PUSH $zero,$SIZE_T*8($sp)
1959	$PUSH $zero,$SIZE_T*10($sp)
1960
1961	$POP r14,-$SIZE_T*18($ap)
1962	li r3,1 # signal "done"
1963	$POP r15,-$SIZE_T*17($ap)
1964	$POP r16,-$SIZE_T*16($ap)
1965	$POP r17,-$SIZE_T*15($ap)
1966	$POP r18,-$SIZE_T*14($ap)
1967	$POP r19,-$SIZE_T*13($ap)
1968	$POP r20,-$SIZE_T*12($ap)
1969	$POP r21,-$SIZE_T*11($ap)
1970	$POP r22,-$SIZE_T*10($ap)
1971	$POP r23,-$SIZE_T*9($ap)
1972	$POP r24,-$SIZE_T*8($ap)
1973	$POP r25,-$SIZE_T*7($ap)
1974	$POP r26,-$SIZE_T*6($ap)
1975	$POP r27,-$SIZE_T*5($ap)
1976	$POP r28,-$SIZE_T*4($ap)
1977	$POP r29,-$SIZE_T*3($ap)
1978	$POP r30,-$SIZE_T*2($ap)
1979	$POP r31,-$SIZE_T*1($ap)
1980	mr $sp,$ap
1981	blr
1982	.long 0
1983	.byte 0,12,4,0x20,0x80,18,6,0
1984	.long 0
1985	.size __bn_sqr8x_mont,.-__bn_sqr8x_mont
1986	___
1987	}
1988	$code.=<<___;
1989	.asciz "Montgomery Multiplication for PPC, CRYPTOGAMS by <appro\@openssl.org>"
1990	___
1991
1992	$code =~ s/\`([^\`]*)\`/eval $1/gem;
1993	print $code;
1994	close STDOUT or die "error closing STDOUT: $!";

Note: See TracBrowser for help on using the repository browser.

source: vbox/trunk/src/libs/openssl-1.1.1f/crypto/bn/asm/ppc-mont.pl@ 83531

Download in other formats: