• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1#! /usr/bin/env perl
2# Copyright 2011-2016 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 <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# August 2011.
18#
19# Companion to x86_64-mont.pl that optimizes cache-timing attack
20# countermeasures. The subroutines are produced by replacing bp[i]
21# references in their x86_64-mont.pl counterparts with cache-neutral
22# references to powers table computed in BN_mod_exp_mont_consttime.
23# In addition subroutine that scatters elements of the powers table
24# is implemented, so that scatter-/gathering can be tuned without
25# bn_exp.c modifications.
26
27# August 2013.
28#
29# Add MULX/AD*X code paths and additional interfaces to optimize for
30# branch prediction unit. For input lengths that are multiples of 8
31# the np argument is not just modulus value, but one interleaved
32# with 0. This is to optimize post-condition...
33
34$flavour = shift;
35$output  = shift;
36if ($flavour =~ /\./) { $output = $flavour; undef $flavour; }
37
38$win64=0; $win64=1 if ($flavour =~ /[nm]asm|mingw64/ || $output =~ /\.asm$/);
39
40$0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
41( $xlate="${dir}x86_64-xlate.pl" and -f $xlate ) or
42( $xlate="${dir}../../../perlasm/x86_64-xlate.pl" and -f $xlate) or
43die "can't locate x86_64-xlate.pl";
44
45open OUT,"| \"$^X\" \"$xlate\" $flavour \"$output\"";
46*STDOUT=*OUT;
47
48# In upstream, this is controlled by shelling out to the compiler to check
49# versions, but BoringSSL is intended to be used with pre-generated perlasm
50# output, so this isn't useful anyway.
51$addx = 1;
52
53# int bn_mul_mont_gather5(
54$rp="%rdi";	# BN_ULONG *rp,
55$ap="%rsi";	# const BN_ULONG *ap,
56$bp="%rdx";	# const BN_ULONG *bp,
57$np="%rcx";	# const BN_ULONG *np,
58$n0="%r8";	# const BN_ULONG *n0,
59$num="%r9";	# int num,
60		# int idx);	# 0 to 2^5-1, "index" in $bp holding
61				# pre-computed powers of a', interlaced
62				# in such manner that b[0] is $bp[idx],
63				# b[1] is [2^5+idx], etc.
64$lo0="%r10";
65$hi0="%r11";
66$hi1="%r13";
67$i="%r14";
68$j="%r15";
69$m0="%rbx";
70$m1="%rbp";
71
72$code=<<___;
73.text
74
75.extern	OPENSSL_ia32cap_P
76
77.globl	bn_mul_mont_gather5
78.type	bn_mul_mont_gather5,\@function,6
79.align	64
80bn_mul_mont_gather5:
81.cfi_startproc
82	mov	${num}d,${num}d
83	mov	%rsp,%rax
84.cfi_def_cfa_register	%rax
85	test	\$7,${num}d
86	jnz	.Lmul_enter
87___
88$code.=<<___ if ($addx);
89	leaq	OPENSSL_ia32cap_P(%rip),%r11
90	mov	8(%r11),%r11d
91___
92$code.=<<___;
93	jmp	.Lmul4x_enter
94
95.align	16
96.Lmul_enter:
97	movd	`($win64?56:8)`(%rsp),%xmm5	# load 7th argument
98	push	%rbx
99.cfi_push	%rbx
100	push	%rbp
101.cfi_push	%rbp
102	push	%r12
103.cfi_push	%r12
104	push	%r13
105.cfi_push	%r13
106	push	%r14
107.cfi_push	%r14
108	push	%r15
109.cfi_push	%r15
110
111	neg	$num
112	mov	%rsp,%r11
113	lea	-280(%rsp,$num,8),%r10	# future alloca(8*(num+2)+256+8)
114	neg	$num			# restore $num
115	and	\$-1024,%r10		# minimize TLB usage
116
117	# An OS-agnostic version of __chkstk.
118	#
119	# Some OSes (Windows) insist on stack being "wired" to
120	# physical memory in strictly sequential manner, i.e. if stack
121	# allocation spans two pages, then reference to farmost one can
122	# be punishable by SEGV. But page walking can do good even on
123	# other OSes, because it guarantees that villain thread hits
124	# the guard page before it can make damage to innocent one...
125	sub	%r10,%r11
126	and	\$-4096,%r11
127	lea	(%r10,%r11),%rsp
128	mov	(%rsp),%r11
129	cmp	%r10,%rsp
130	ja	.Lmul_page_walk
131	jmp	.Lmul_page_walk_done
132
133.Lmul_page_walk:
134	lea	-4096(%rsp),%rsp
135	mov	(%rsp),%r11
136	cmp	%r10,%rsp
137	ja	.Lmul_page_walk
138.Lmul_page_walk_done:
139
140	lea	.Linc(%rip),%r10
141	mov	%rax,8(%rsp,$num,8)	# tp[num+1]=%rsp
142.cfi_cfa_expression	%rsp+8,$num,8,mul,plus,deref,+8
143.Lmul_body:
144
145	lea	128($bp),%r12		# reassign $bp (+size optimization)
146___
147		$bp="%r12";
148		$STRIDE=2**5*8;		# 5 is "window size"
149		$N=$STRIDE/4;		# should match cache line size
150$code.=<<___;
151	movdqa	0(%r10),%xmm0		# 00000001000000010000000000000000
152	movdqa	16(%r10),%xmm1		# 00000002000000020000000200000002
153	lea	24-112(%rsp,$num,8),%r10# place the mask after tp[num+3] (+ICache optimization)
154	and	\$-16,%r10
155
156	pshufd	\$0,%xmm5,%xmm5		# broadcast index
157	movdqa	%xmm1,%xmm4
158	movdqa	%xmm1,%xmm2
159___
160########################################################################
161# calculate mask by comparing 0..31 to index and save result to stack
162#
163$code.=<<___;
164	paddd	%xmm0,%xmm1
165	pcmpeqd	%xmm5,%xmm0		# compare to 1,0
166	.byte	0x67
167	movdqa	%xmm4,%xmm3
168___
169for($k=0;$k<$STRIDE/16-4;$k+=4) {
170$code.=<<___;
171	paddd	%xmm1,%xmm2
172	pcmpeqd	%xmm5,%xmm1		# compare to 3,2
173	movdqa	%xmm0,`16*($k+0)+112`(%r10)
174	movdqa	%xmm4,%xmm0
175
176	paddd	%xmm2,%xmm3
177	pcmpeqd	%xmm5,%xmm2		# compare to 5,4
178	movdqa	%xmm1,`16*($k+1)+112`(%r10)
179	movdqa	%xmm4,%xmm1
180
181	paddd	%xmm3,%xmm0
182	pcmpeqd	%xmm5,%xmm3		# compare to 7,6
183	movdqa	%xmm2,`16*($k+2)+112`(%r10)
184	movdqa	%xmm4,%xmm2
185
186	paddd	%xmm0,%xmm1
187	pcmpeqd	%xmm5,%xmm0
188	movdqa	%xmm3,`16*($k+3)+112`(%r10)
189	movdqa	%xmm4,%xmm3
190___
191}
192$code.=<<___;				# last iteration can be optimized
193	paddd	%xmm1,%xmm2
194	pcmpeqd	%xmm5,%xmm1
195	movdqa	%xmm0,`16*($k+0)+112`(%r10)
196
197	paddd	%xmm2,%xmm3
198	.byte	0x67
199	pcmpeqd	%xmm5,%xmm2
200	movdqa	%xmm1,`16*($k+1)+112`(%r10)
201
202	pcmpeqd	%xmm5,%xmm3
203	movdqa	%xmm2,`16*($k+2)+112`(%r10)
204	pand	`16*($k+0)-128`($bp),%xmm0	# while it's still in register
205
206	pand	`16*($k+1)-128`($bp),%xmm1
207	pand	`16*($k+2)-128`($bp),%xmm2
208	movdqa	%xmm3,`16*($k+3)+112`(%r10)
209	pand	`16*($k+3)-128`($bp),%xmm3
210	por	%xmm2,%xmm0
211	por	%xmm3,%xmm1
212___
213for($k=0;$k<$STRIDE/16-4;$k+=4) {
214$code.=<<___;
215	movdqa	`16*($k+0)-128`($bp),%xmm4
216	movdqa	`16*($k+1)-128`($bp),%xmm5
217	movdqa	`16*($k+2)-128`($bp),%xmm2
218	pand	`16*($k+0)+112`(%r10),%xmm4
219	movdqa	`16*($k+3)-128`($bp),%xmm3
220	pand	`16*($k+1)+112`(%r10),%xmm5
221	por	%xmm4,%xmm0
222	pand	`16*($k+2)+112`(%r10),%xmm2
223	por	%xmm5,%xmm1
224	pand	`16*($k+3)+112`(%r10),%xmm3
225	por	%xmm2,%xmm0
226	por	%xmm3,%xmm1
227___
228}
229$code.=<<___;
230	por	%xmm1,%xmm0
231	pshufd	\$0x4e,%xmm0,%xmm1
232	por	%xmm1,%xmm0
233	lea	$STRIDE($bp),$bp
234	movq	%xmm0,$m0		# m0=bp[0]
235
236	mov	($n0),$n0		# pull n0[0] value
237	mov	($ap),%rax
238
239	xor	$i,$i			# i=0
240	xor	$j,$j			# j=0
241
242	mov	$n0,$m1
243	mulq	$m0			# ap[0]*bp[0]
244	mov	%rax,$lo0
245	mov	($np),%rax
246
247	imulq	$lo0,$m1		# "tp[0]"*n0
248	mov	%rdx,$hi0
249
250	mulq	$m1			# np[0]*m1
251	add	%rax,$lo0		# discarded
252	mov	8($ap),%rax
253	adc	\$0,%rdx
254	mov	%rdx,$hi1
255
256	lea	1($j),$j		# j++
257	jmp	.L1st_enter
258
259.align	16
260.L1st:
261	add	%rax,$hi1
262	mov	($ap,$j,8),%rax
263	adc	\$0,%rdx
264	add	$hi0,$hi1		# np[j]*m1+ap[j]*bp[0]
265	mov	$lo0,$hi0
266	adc	\$0,%rdx
267	mov	$hi1,-16(%rsp,$j,8)	# tp[j-1]
268	mov	%rdx,$hi1
269
270.L1st_enter:
271	mulq	$m0			# ap[j]*bp[0]
272	add	%rax,$hi0
273	mov	($np,$j,8),%rax
274	adc	\$0,%rdx
275	lea	1($j),$j		# j++
276	mov	%rdx,$lo0
277
278	mulq	$m1			# np[j]*m1
279	cmp	$num,$j
280	jne	.L1st			# note that upon exit $j==$num, so
281					# they can be used interchangeably
282
283	add	%rax,$hi1
284	adc	\$0,%rdx
285	add	$hi0,$hi1		# np[j]*m1+ap[j]*bp[0]
286	adc	\$0,%rdx
287	mov	$hi1,-16(%rsp,$num,8)	# tp[num-1]
288	mov	%rdx,$hi1
289	mov	$lo0,$hi0
290
291	xor	%rdx,%rdx
292	add	$hi0,$hi1
293	adc	\$0,%rdx
294	mov	$hi1,-8(%rsp,$num,8)
295	mov	%rdx,(%rsp,$num,8)	# store upmost overflow bit
296
297	lea	1($i),$i		# i++
298	jmp	.Louter
299.align	16
300.Louter:
301	lea	24+128(%rsp,$num,8),%rdx	# where 256-byte mask is (+size optimization)
302	and	\$-16,%rdx
303	pxor	%xmm4,%xmm4
304	pxor	%xmm5,%xmm5
305___
306for($k=0;$k<$STRIDE/16;$k+=4) {
307$code.=<<___;
308	movdqa	`16*($k+0)-128`($bp),%xmm0
309	movdqa	`16*($k+1)-128`($bp),%xmm1
310	movdqa	`16*($k+2)-128`($bp),%xmm2
311	movdqa	`16*($k+3)-128`($bp),%xmm3
312	pand	`16*($k+0)-128`(%rdx),%xmm0
313	pand	`16*($k+1)-128`(%rdx),%xmm1
314	por	%xmm0,%xmm4
315	pand	`16*($k+2)-128`(%rdx),%xmm2
316	por	%xmm1,%xmm5
317	pand	`16*($k+3)-128`(%rdx),%xmm3
318	por	%xmm2,%xmm4
319	por	%xmm3,%xmm5
320___
321}
322$code.=<<___;
323	por	%xmm5,%xmm4
324	pshufd	\$0x4e,%xmm4,%xmm0
325	por	%xmm4,%xmm0
326	lea	$STRIDE($bp),$bp
327
328	mov	($ap),%rax		# ap[0]
329	movq	%xmm0,$m0		# m0=bp[i]
330
331	xor	$j,$j			# j=0
332	mov	$n0,$m1
333	mov	(%rsp),$lo0
334
335	mulq	$m0			# ap[0]*bp[i]
336	add	%rax,$lo0		# ap[0]*bp[i]+tp[0]
337	mov	($np),%rax
338	adc	\$0,%rdx
339
340	imulq	$lo0,$m1		# tp[0]*n0
341	mov	%rdx,$hi0
342
343	mulq	$m1			# np[0]*m1
344	add	%rax,$lo0		# discarded
345	mov	8($ap),%rax
346	adc	\$0,%rdx
347	mov	8(%rsp),$lo0		# tp[1]
348	mov	%rdx,$hi1
349
350	lea	1($j),$j		# j++
351	jmp	.Linner_enter
352
353.align	16
354.Linner:
355	add	%rax,$hi1
356	mov	($ap,$j,8),%rax
357	adc	\$0,%rdx
358	add	$lo0,$hi1		# np[j]*m1+ap[j]*bp[i]+tp[j]
359	mov	(%rsp,$j,8),$lo0
360	adc	\$0,%rdx
361	mov	$hi1,-16(%rsp,$j,8)	# tp[j-1]
362	mov	%rdx,$hi1
363
364.Linner_enter:
365	mulq	$m0			# ap[j]*bp[i]
366	add	%rax,$hi0
367	mov	($np,$j,8),%rax
368	adc	\$0,%rdx
369	add	$hi0,$lo0		# ap[j]*bp[i]+tp[j]
370	mov	%rdx,$hi0
371	adc	\$0,$hi0
372	lea	1($j),$j		# j++
373
374	mulq	$m1			# np[j]*m1
375	cmp	$num,$j
376	jne	.Linner			# note that upon exit $j==$num, so
377					# they can be used interchangeably
378	add	%rax,$hi1
379	adc	\$0,%rdx
380	add	$lo0,$hi1		# np[j]*m1+ap[j]*bp[i]+tp[j]
381	mov	(%rsp,$num,8),$lo0
382	adc	\$0,%rdx
383	mov	$hi1,-16(%rsp,$num,8)	# tp[num-1]
384	mov	%rdx,$hi1
385
386	xor	%rdx,%rdx
387	add	$hi0,$hi1
388	adc	\$0,%rdx
389	add	$lo0,$hi1		# pull upmost overflow bit
390	adc	\$0,%rdx
391	mov	$hi1,-8(%rsp,$num,8)
392	mov	%rdx,(%rsp,$num,8)	# store upmost overflow bit
393
394	lea	1($i),$i		# i++
395	cmp	$num,$i
396	jb	.Louter
397
398	xor	$i,$i			# i=0 and clear CF!
399	mov	(%rsp),%rax		# tp[0]
400	lea	(%rsp),$ap		# borrow ap for tp
401	mov	$num,$j			# j=num
402	jmp	.Lsub
403.align	16
404.Lsub:	sbb	($np,$i,8),%rax
405	mov	%rax,($rp,$i,8)		# rp[i]=tp[i]-np[i]
406	mov	8($ap,$i,8),%rax	# tp[i+1]
407	lea	1($i),$i		# i++
408	dec	$j			# doesn't affect CF!
409	jnz	.Lsub
410
411	sbb	\$0,%rax		# handle upmost overflow bit
412	mov	\$-1,%rbx
413	xor	%rax,%rbx
414	xor	$i,$i
415	mov	$num,$j			# j=num
416
417.Lcopy:					# conditional copy
418	mov	($rp,$i,8),%rcx
419	mov	(%rsp,$i,8),%rdx
420	and	%rbx,%rcx
421	and	%rax,%rdx
422	mov	$i,(%rsp,$i,8)		# zap temporary vector
423	or	%rcx,%rdx
424	mov	%rdx,($rp,$i,8)		# rp[i]=tp[i]
425	lea	1($i),$i
426	sub	\$1,$j
427	jnz	.Lcopy
428
429	mov	8(%rsp,$num,8),%rsi	# restore %rsp
430.cfi_def_cfa	%rsi,8
431	mov	\$1,%rax
432
433	mov	-48(%rsi),%r15
434.cfi_restore	%r15
435	mov	-40(%rsi),%r14
436.cfi_restore	%r14
437	mov	-32(%rsi),%r13
438.cfi_restore	%r13
439	mov	-24(%rsi),%r12
440.cfi_restore	%r12
441	mov	-16(%rsi),%rbp
442.cfi_restore	%rbp
443	mov	-8(%rsi),%rbx
444.cfi_restore	%rbx
445	lea	(%rsi),%rsp
446.cfi_def_cfa_register	%rsp
447.Lmul_epilogue:
448	ret
449.cfi_endproc
450.size	bn_mul_mont_gather5,.-bn_mul_mont_gather5
451___
452{{{
453my @A=("%r10","%r11");
454my @N=("%r13","%rdi");
455$code.=<<___;
456.type	bn_mul4x_mont_gather5,\@function,6
457.align	32
458bn_mul4x_mont_gather5:
459.cfi_startproc
460	.byte	0x67
461	mov	%rsp,%rax
462.cfi_def_cfa_register	%rax
463.Lmul4x_enter:
464___
465$code.=<<___ if ($addx);
466	and	\$0x80108,%r11d
467	cmp	\$0x80108,%r11d		# check for AD*X+BMI2+BMI1
468	je	.Lmulx4x_enter
469___
470$code.=<<___;
471	push	%rbx
472.cfi_push	%rbx
473	push	%rbp
474.cfi_push	%rbp
475	push	%r12
476.cfi_push	%r12
477	push	%r13
478.cfi_push	%r13
479	push	%r14
480.cfi_push	%r14
481	push	%r15
482.cfi_push	%r15
483.Lmul4x_prologue:
484
485	.byte	0x67
486	shl	\$3,${num}d		# convert $num to bytes
487	lea	($num,$num,2),%r10	# 3*$num in bytes
488	neg	$num			# -$num
489
490	##############################################################
491	# Ensure that stack frame doesn't alias with $rptr+3*$num
492	# modulo 4096, which covers ret[num], am[num] and n[num]
493	# (see bn_exp.c). This is done to allow memory disambiguation
494	# logic do its magic. [Extra [num] is allocated in order
495	# to align with bn_power5's frame, which is cleansed after
496	# completing exponentiation. Extra 256 bytes is for power mask
497	# calculated from 7th argument, the index.]
498	#
499	lea	-320(%rsp,$num,2),%r11
500	mov	%rsp,%rbp
501	sub	$rp,%r11
502	and	\$4095,%r11
503	cmp	%r11,%r10
504	jb	.Lmul4xsp_alt
505	sub	%r11,%rbp		# align with $rp
506	lea	-320(%rbp,$num,2),%rbp	# future alloca(frame+2*num*8+256)
507	jmp	.Lmul4xsp_done
508
509.align	32
510.Lmul4xsp_alt:
511	lea	4096-320(,$num,2),%r10
512	lea	-320(%rbp,$num,2),%rbp	# future alloca(frame+2*num*8+256)
513	sub	%r10,%r11
514	mov	\$0,%r10
515	cmovc	%r10,%r11
516	sub	%r11,%rbp
517.Lmul4xsp_done:
518	and	\$-64,%rbp
519	mov	%rsp,%r11
520	sub	%rbp,%r11
521	and	\$-4096,%r11
522	lea	(%rbp,%r11),%rsp
523	mov	(%rsp),%r10
524	cmp	%rbp,%rsp
525	ja	.Lmul4x_page_walk
526	jmp	.Lmul4x_page_walk_done
527
528.Lmul4x_page_walk:
529	lea	-4096(%rsp),%rsp
530	mov	(%rsp),%r10
531	cmp	%rbp,%rsp
532	ja	.Lmul4x_page_walk
533.Lmul4x_page_walk_done:
534
535	neg	$num
536
537	mov	%rax,40(%rsp)
538.cfi_cfa_expression	%rsp+40,deref,+8
539.Lmul4x_body:
540
541	call	mul4x_internal
542
543	mov	40(%rsp),%rsi		# restore %rsp
544.cfi_def_cfa	%rsi,8
545	mov	\$1,%rax
546
547	mov	-48(%rsi),%r15
548.cfi_restore	%r15
549	mov	-40(%rsi),%r14
550.cfi_restore	%r14
551	mov	-32(%rsi),%r13
552.cfi_restore	%r13
553	mov	-24(%rsi),%r12
554.cfi_restore	%r12
555	mov	-16(%rsi),%rbp
556.cfi_restore	%rbp
557	mov	-8(%rsi),%rbx
558.cfi_restore	%rbx
559	lea	(%rsi),%rsp
560.cfi_def_cfa_register	%rsp
561.Lmul4x_epilogue:
562	ret
563.cfi_endproc
564.size	bn_mul4x_mont_gather5,.-bn_mul4x_mont_gather5
565
566.type	mul4x_internal,\@abi-omnipotent
567.align	32
568mul4x_internal:
569.cfi_startproc
570	shl	\$5,$num		# $num was in bytes
571	movd	`($win64?56:8)`(%rax),%xmm5	# load 7th argument, index
572	lea	.Linc(%rip),%rax
573	lea	128(%rdx,$num),%r13	# end of powers table (+size optimization)
574	shr	\$5,$num		# restore $num
575___
576		$bp="%r12";
577		$STRIDE=2**5*8;		# 5 is "window size"
578		$N=$STRIDE/4;		# should match cache line size
579		$tp=$i;
580$code.=<<___;
581	movdqa	0(%rax),%xmm0		# 00000001000000010000000000000000
582	movdqa	16(%rax),%xmm1		# 00000002000000020000000200000002
583	lea	88-112(%rsp,$num),%r10	# place the mask after tp[num+1] (+ICache optimization)
584	lea	128(%rdx),$bp		# size optimization
585
586	pshufd	\$0,%xmm5,%xmm5		# broadcast index
587	movdqa	%xmm1,%xmm4
588	.byte	0x67,0x67
589	movdqa	%xmm1,%xmm2
590___
591########################################################################
592# calculate mask by comparing 0..31 to index and save result to stack
593#
594$code.=<<___;
595	paddd	%xmm0,%xmm1
596	pcmpeqd	%xmm5,%xmm0		# compare to 1,0
597	.byte	0x67
598	movdqa	%xmm4,%xmm3
599___
600for($i=0;$i<$STRIDE/16-4;$i+=4) {
601$code.=<<___;
602	paddd	%xmm1,%xmm2
603	pcmpeqd	%xmm5,%xmm1		# compare to 3,2
604	movdqa	%xmm0,`16*($i+0)+112`(%r10)
605	movdqa	%xmm4,%xmm0
606
607	paddd	%xmm2,%xmm3
608	pcmpeqd	%xmm5,%xmm2		# compare to 5,4
609	movdqa	%xmm1,`16*($i+1)+112`(%r10)
610	movdqa	%xmm4,%xmm1
611
612	paddd	%xmm3,%xmm0
613	pcmpeqd	%xmm5,%xmm3		# compare to 7,6
614	movdqa	%xmm2,`16*($i+2)+112`(%r10)
615	movdqa	%xmm4,%xmm2
616
617	paddd	%xmm0,%xmm1
618	pcmpeqd	%xmm5,%xmm0
619	movdqa	%xmm3,`16*($i+3)+112`(%r10)
620	movdqa	%xmm4,%xmm3
621___
622}
623$code.=<<___;				# last iteration can be optimized
624	paddd	%xmm1,%xmm2
625	pcmpeqd	%xmm5,%xmm1
626	movdqa	%xmm0,`16*($i+0)+112`(%r10)
627
628	paddd	%xmm2,%xmm3
629	.byte	0x67
630	pcmpeqd	%xmm5,%xmm2
631	movdqa	%xmm1,`16*($i+1)+112`(%r10)
632
633	pcmpeqd	%xmm5,%xmm3
634	movdqa	%xmm2,`16*($i+2)+112`(%r10)
635	pand	`16*($i+0)-128`($bp),%xmm0	# while it's still in register
636
637	pand	`16*($i+1)-128`($bp),%xmm1
638	pand	`16*($i+2)-128`($bp),%xmm2
639	movdqa	%xmm3,`16*($i+3)+112`(%r10)
640	pand	`16*($i+3)-128`($bp),%xmm3
641	por	%xmm2,%xmm0
642	por	%xmm3,%xmm1
643___
644for($i=0;$i<$STRIDE/16-4;$i+=4) {
645$code.=<<___;
646	movdqa	`16*($i+0)-128`($bp),%xmm4
647	movdqa	`16*($i+1)-128`($bp),%xmm5
648	movdqa	`16*($i+2)-128`($bp),%xmm2
649	pand	`16*($i+0)+112`(%r10),%xmm4
650	movdqa	`16*($i+3)-128`($bp),%xmm3
651	pand	`16*($i+1)+112`(%r10),%xmm5
652	por	%xmm4,%xmm0
653	pand	`16*($i+2)+112`(%r10),%xmm2
654	por	%xmm5,%xmm1
655	pand	`16*($i+3)+112`(%r10),%xmm3
656	por	%xmm2,%xmm0
657	por	%xmm3,%xmm1
658___
659}
660$code.=<<___;
661	por	%xmm1,%xmm0
662	pshufd	\$0x4e,%xmm0,%xmm1
663	por	%xmm1,%xmm0
664	lea	$STRIDE($bp),$bp
665	movq	%xmm0,$m0		# m0=bp[0]
666
667	mov	%r13,16+8(%rsp)		# save end of b[num]
668	mov	$rp, 56+8(%rsp)		# save $rp
669
670	mov	($n0),$n0		# pull n0[0] value
671	mov	($ap),%rax
672	lea	($ap,$num),$ap		# end of a[num]
673	neg	$num
674
675	mov	$n0,$m1
676	mulq	$m0			# ap[0]*bp[0]
677	mov	%rax,$A[0]
678	mov	($np),%rax
679
680	imulq	$A[0],$m1		# "tp[0]"*n0
681	lea	64+8(%rsp),$tp
682	mov	%rdx,$A[1]
683
684	mulq	$m1			# np[0]*m1
685	add	%rax,$A[0]		# discarded
686	mov	8($ap,$num),%rax
687	adc	\$0,%rdx
688	mov	%rdx,$N[1]
689
690	mulq	$m0
691	add	%rax,$A[1]
692	mov	8*1($np),%rax
693	adc	\$0,%rdx
694	mov	%rdx,$A[0]
695
696	mulq	$m1
697	add	%rax,$N[1]
698	mov	16($ap,$num),%rax
699	adc	\$0,%rdx
700	add	$A[1],$N[1]
701	lea	4*8($num),$j		# j=4
702	lea	8*4($np),$np
703	adc	\$0,%rdx
704	mov	$N[1],($tp)
705	mov	%rdx,$N[0]
706	jmp	.L1st4x
707
708.align	32
709.L1st4x:
710	mulq	$m0			# ap[j]*bp[0]
711	add	%rax,$A[0]
712	mov	-8*2($np),%rax
713	lea	32($tp),$tp
714	adc	\$0,%rdx
715	mov	%rdx,$A[1]
716
717	mulq	$m1			# np[j]*m1
718	add	%rax,$N[0]
719	mov	-8($ap,$j),%rax
720	adc	\$0,%rdx
721	add	$A[0],$N[0]		# np[j]*m1+ap[j]*bp[0]
722	adc	\$0,%rdx
723	mov	$N[0],-24($tp)		# tp[j-1]
724	mov	%rdx,$N[1]
725
726	mulq	$m0			# ap[j]*bp[0]
727	add	%rax,$A[1]
728	mov	-8*1($np),%rax
729	adc	\$0,%rdx
730	mov	%rdx,$A[0]
731
732	mulq	$m1			# np[j]*m1
733	add	%rax,$N[1]
734	mov	($ap,$j),%rax
735	adc	\$0,%rdx
736	add	$A[1],$N[1]		# np[j]*m1+ap[j]*bp[0]
737	adc	\$0,%rdx
738	mov	$N[1],-16($tp)		# tp[j-1]
739	mov	%rdx,$N[0]
740
741	mulq	$m0			# ap[j]*bp[0]
742	add	%rax,$A[0]
743	mov	8*0($np),%rax
744	adc	\$0,%rdx
745	mov	%rdx,$A[1]
746
747	mulq	$m1			# np[j]*m1
748	add	%rax,$N[0]
749	mov	8($ap,$j),%rax
750	adc	\$0,%rdx
751	add	$A[0],$N[0]		# np[j]*m1+ap[j]*bp[0]
752	adc	\$0,%rdx
753	mov	$N[0],-8($tp)		# tp[j-1]
754	mov	%rdx,$N[1]
755
756	mulq	$m0			# ap[j]*bp[0]
757	add	%rax,$A[1]
758	mov	8*1($np),%rax
759	adc	\$0,%rdx
760	mov	%rdx,$A[0]
761
762	mulq	$m1			# np[j]*m1
763	add	%rax,$N[1]
764	mov	16($ap,$j),%rax
765	adc	\$0,%rdx
766	add	$A[1],$N[1]		# np[j]*m1+ap[j]*bp[0]
767	lea	8*4($np),$np
768	adc	\$0,%rdx
769	mov	$N[1],($tp)		# tp[j-1]
770	mov	%rdx,$N[0]
771
772	add	\$32,$j			# j+=4
773	jnz	.L1st4x
774
775	mulq	$m0			# ap[j]*bp[0]
776	add	%rax,$A[0]
777	mov	-8*2($np),%rax
778	lea	32($tp),$tp
779	adc	\$0,%rdx
780	mov	%rdx,$A[1]
781
782	mulq	$m1			# np[j]*m1
783	add	%rax,$N[0]
784	mov	-8($ap),%rax
785	adc	\$0,%rdx
786	add	$A[0],$N[0]		# np[j]*m1+ap[j]*bp[0]
787	adc	\$0,%rdx
788	mov	$N[0],-24($tp)		# tp[j-1]
789	mov	%rdx,$N[1]
790
791	mulq	$m0			# ap[j]*bp[0]
792	add	%rax,$A[1]
793	mov	-8*1($np),%rax
794	adc	\$0,%rdx
795	mov	%rdx,$A[0]
796
797	mulq	$m1			# np[j]*m1
798	add	%rax,$N[1]
799	mov	($ap,$num),%rax		# ap[0]
800	adc	\$0,%rdx
801	add	$A[1],$N[1]		# np[j]*m1+ap[j]*bp[0]
802	adc	\$0,%rdx
803	mov	$N[1],-16($tp)		# tp[j-1]
804	mov	%rdx,$N[0]
805
806	lea	($np,$num),$np		# rewind $np
807
808	xor	$N[1],$N[1]
809	add	$A[0],$N[0]
810	adc	\$0,$N[1]
811	mov	$N[0],-8($tp)
812
813	jmp	.Louter4x
814
815.align	32
816.Louter4x:
817	lea	16+128($tp),%rdx	# where 256-byte mask is (+size optimization)
818	pxor	%xmm4,%xmm4
819	pxor	%xmm5,%xmm5
820___
821for($i=0;$i<$STRIDE/16;$i+=4) {
822$code.=<<___;
823	movdqa	`16*($i+0)-128`($bp),%xmm0
824	movdqa	`16*($i+1)-128`($bp),%xmm1
825	movdqa	`16*($i+2)-128`($bp),%xmm2
826	movdqa	`16*($i+3)-128`($bp),%xmm3
827	pand	`16*($i+0)-128`(%rdx),%xmm0
828	pand	`16*($i+1)-128`(%rdx),%xmm1
829	por	%xmm0,%xmm4
830	pand	`16*($i+2)-128`(%rdx),%xmm2
831	por	%xmm1,%xmm5
832	pand	`16*($i+3)-128`(%rdx),%xmm3
833	por	%xmm2,%xmm4
834	por	%xmm3,%xmm5
835___
836}
837$code.=<<___;
838	por	%xmm5,%xmm4
839	pshufd	\$0x4e,%xmm4,%xmm0
840	por	%xmm4,%xmm0
841	lea	$STRIDE($bp),$bp
842	movq	%xmm0,$m0		# m0=bp[i]
843
844	mov	($tp,$num),$A[0]
845	mov	$n0,$m1
846	mulq	$m0			# ap[0]*bp[i]
847	add	%rax,$A[0]		# ap[0]*bp[i]+tp[0]
848	mov	($np),%rax
849	adc	\$0,%rdx
850
851	imulq	$A[0],$m1		# tp[0]*n0
852	mov	%rdx,$A[1]
853	mov	$N[1],($tp)		# store upmost overflow bit
854
855	lea	($tp,$num),$tp		# rewind $tp
856
857	mulq	$m1			# np[0]*m1
858	add	%rax,$A[0]		# "$N[0]", discarded
859	mov	8($ap,$num),%rax
860	adc	\$0,%rdx
861	mov	%rdx,$N[1]
862
863	mulq	$m0			# ap[j]*bp[i]
864	add	%rax,$A[1]
865	mov	8*1($np),%rax
866	adc	\$0,%rdx
867	add	8($tp),$A[1]		# +tp[1]
868	adc	\$0,%rdx
869	mov	%rdx,$A[0]
870
871	mulq	$m1			# np[j]*m1
872	add	%rax,$N[1]
873	mov	16($ap,$num),%rax
874	adc	\$0,%rdx
875	add	$A[1],$N[1]		# np[j]*m1+ap[j]*bp[i]+tp[j]
876	lea	4*8($num),$j		# j=4
877	lea	8*4($np),$np
878	adc	\$0,%rdx
879	mov	%rdx,$N[0]
880	jmp	.Linner4x
881
882.align	32
883.Linner4x:
884	mulq	$m0			# ap[j]*bp[i]
885	add	%rax,$A[0]
886	mov	-8*2($np),%rax
887	adc	\$0,%rdx
888	add	16($tp),$A[0]		# ap[j]*bp[i]+tp[j]
889	lea	32($tp),$tp
890	adc	\$0,%rdx
891	mov	%rdx,$A[1]
892
893	mulq	$m1			# np[j]*m1
894	add	%rax,$N[0]
895	mov	-8($ap,$j),%rax
896	adc	\$0,%rdx
897	add	$A[0],$N[0]
898	adc	\$0,%rdx
899	mov	$N[1],-32($tp)		# tp[j-1]
900	mov	%rdx,$N[1]
901
902	mulq	$m0			# ap[j]*bp[i]
903	add	%rax,$A[1]
904	mov	-8*1($np),%rax
905	adc	\$0,%rdx
906	add	-8($tp),$A[1]
907	adc	\$0,%rdx
908	mov	%rdx,$A[0]
909
910	mulq	$m1			# np[j]*m1
911	add	%rax,$N[1]
912	mov	($ap,$j),%rax
913	adc	\$0,%rdx
914	add	$A[1],$N[1]
915	adc	\$0,%rdx
916	mov	$N[0],-24($tp)		# tp[j-1]
917	mov	%rdx,$N[0]
918
919	mulq	$m0			# ap[j]*bp[i]
920	add	%rax,$A[0]
921	mov	8*0($np),%rax
922	adc	\$0,%rdx
923	add	($tp),$A[0]		# ap[j]*bp[i]+tp[j]
924	adc	\$0,%rdx
925	mov	%rdx,$A[1]
926
927	mulq	$m1			# np[j]*m1
928	add	%rax,$N[0]
929	mov	8($ap,$j),%rax
930	adc	\$0,%rdx
931	add	$A[0],$N[0]
932	adc	\$0,%rdx
933	mov	$N[1],-16($tp)		# tp[j-1]
934	mov	%rdx,$N[1]
935
936	mulq	$m0			# ap[j]*bp[i]
937	add	%rax,$A[1]
938	mov	8*1($np),%rax
939	adc	\$0,%rdx
940	add	8($tp),$A[1]
941	adc	\$0,%rdx
942	mov	%rdx,$A[0]
943
944	mulq	$m1			# np[j]*m1
945	add	%rax,$N[1]
946	mov	16($ap,$j),%rax
947	adc	\$0,%rdx
948	add	$A[1],$N[1]
949	lea	8*4($np),$np
950	adc	\$0,%rdx
951	mov	$N[0],-8($tp)		# tp[j-1]
952	mov	%rdx,$N[0]
953
954	add	\$32,$j			# j+=4
955	jnz	.Linner4x
956
957	mulq	$m0			# ap[j]*bp[i]
958	add	%rax,$A[0]
959	mov	-8*2($np),%rax
960	adc	\$0,%rdx
961	add	16($tp),$A[0]		# ap[j]*bp[i]+tp[j]
962	lea	32($tp),$tp
963	adc	\$0,%rdx
964	mov	%rdx,$A[1]
965
966	mulq	$m1			# np[j]*m1
967	add	%rax,$N[0]
968	mov	-8($ap),%rax
969	adc	\$0,%rdx
970	add	$A[0],$N[0]
971	adc	\$0,%rdx
972	mov	$N[1],-32($tp)		# tp[j-1]
973	mov	%rdx,$N[1]
974
975	mulq	$m0			# ap[j]*bp[i]
976	add	%rax,$A[1]
977	mov	$m1,%rax
978	mov	-8*1($np),$m1
979	adc	\$0,%rdx
980	add	-8($tp),$A[1]
981	adc	\$0,%rdx
982	mov	%rdx,$A[0]
983
984	mulq	$m1			# np[j]*m1
985	add	%rax,$N[1]
986	mov	($ap,$num),%rax		# ap[0]
987	adc	\$0,%rdx
988	add	$A[1],$N[1]
989	adc	\$0,%rdx
990	mov	$N[0],-24($tp)		# tp[j-1]
991	mov	%rdx,$N[0]
992
993	mov	$N[1],-16($tp)		# tp[j-1]
994	lea	($np,$num),$np		# rewind $np
995
996	xor	$N[1],$N[1]
997	add	$A[0],$N[0]
998	adc	\$0,$N[1]
999	add	($tp),$N[0]		# pull upmost overflow bit
1000	adc	\$0,$N[1]		# upmost overflow bit
1001	mov	$N[0],-8($tp)
1002
1003	cmp	16+8(%rsp),$bp
1004	jb	.Louter4x
1005___
1006if (1) {
1007$code.=<<___;
1008	xor	%rax,%rax
1009	sub	$N[0],$m1		# compare top-most words
1010	adc	$j,$j			# $j is zero
1011	or	$j,$N[1]
1012	sub	$N[1],%rax		# %rax=-$N[1]
1013	lea	($tp,$num),%rbx		# tptr in .sqr4x_sub
1014	mov	($np),%r12
1015	lea	($np),%rbp		# nptr in .sqr4x_sub
1016	mov	%r9,%rcx
1017	sar	\$3+2,%rcx
1018	mov	56+8(%rsp),%rdi		# rptr in .sqr4x_sub
1019	dec	%r12			# so that after 'not' we get -n[0]
1020	xor	%r10,%r10
1021	mov	8*1(%rbp),%r13
1022	mov	8*2(%rbp),%r14
1023	mov	8*3(%rbp),%r15
1024	jmp	.Lsqr4x_sub_entry
1025___
1026} else {
1027my @ri=("%rax",$bp,$m0,$m1);
1028my $rp="%rdx";
1029$code.=<<___
1030	xor	\$1,$N[1]
1031	lea	($tp,$num),$tp		# rewind $tp
1032	sar	\$5,$num		# cf=0
1033	lea	($np,$N[1],8),$np
1034	mov	56+8(%rsp),$rp		# restore $rp
1035	jmp	.Lsub4x
1036
1037.align	32
1038.Lsub4x:
1039	.byte	0x66
1040	mov	8*0($tp),@ri[0]
1041	mov	8*1($tp),@ri[1]
1042	.byte	0x66
1043	sbb	16*0($np),@ri[0]
1044	mov	8*2($tp),@ri[2]
1045	sbb	16*1($np),@ri[1]
1046	mov	3*8($tp),@ri[3]
1047	lea	4*8($tp),$tp
1048	sbb	16*2($np),@ri[2]
1049	mov	@ri[0],8*0($rp)
1050	sbb	16*3($np),@ri[3]
1051	lea	16*4($np),$np
1052	mov	@ri[1],8*1($rp)
1053	mov	@ri[2],8*2($rp)
1054	mov	@ri[3],8*3($rp)
1055	lea	8*4($rp),$rp
1056
1057	inc	$num
1058	jnz	.Lsub4x
1059
1060	ret
1061___
1062}
1063$code.=<<___;
1064.cfi_endproc
1065.size	mul4x_internal,.-mul4x_internal
1066___
1067}}}
1068{{{
1069######################################################################
1070# void bn_power5(
1071my $rptr="%rdi";	# BN_ULONG *rptr,
1072my $aptr="%rsi";	# const BN_ULONG *aptr,
1073my $bptr="%rdx";	# const void *table,
1074my $nptr="%rcx";	# const BN_ULONG *nptr,
1075my $n0  ="%r8";		# const BN_ULONG *n0);
1076my $num ="%r9";		# int num, has to be divisible by 8
1077			# int pwr
1078
1079my ($i,$j,$tptr)=("%rbp","%rcx",$rptr);
1080my @A0=("%r10","%r11");
1081my @A1=("%r12","%r13");
1082my ($a0,$a1,$ai)=("%r14","%r15","%rbx");
1083
1084$code.=<<___;
1085.globl	bn_power5
1086.type	bn_power5,\@function,6
1087.align	32
1088bn_power5:
1089.cfi_startproc
1090	mov	%rsp,%rax
1091.cfi_def_cfa_register	%rax
1092___
1093$code.=<<___ if ($addx);
1094	leaq	OPENSSL_ia32cap_P(%rip),%r11
1095	mov	8(%r11),%r11d
1096	and	\$0x80108,%r11d
1097	cmp	\$0x80108,%r11d		# check for AD*X+BMI2+BMI1
1098	je	.Lpowerx5_enter
1099___
1100$code.=<<___;
1101	push	%rbx
1102.cfi_push	%rbx
1103	push	%rbp
1104.cfi_push	%rbp
1105	push	%r12
1106.cfi_push	%r12
1107	push	%r13
1108.cfi_push	%r13
1109	push	%r14
1110.cfi_push	%r14
1111	push	%r15
1112.cfi_push	%r15
1113.Lpower5_prologue:
1114
1115	shl	\$3,${num}d		# convert $num to bytes
1116	lea	($num,$num,2),%r10d	# 3*$num
1117	neg	$num
1118	mov	($n0),$n0		# *n0
1119
1120	##############################################################
1121	# Ensure that stack frame doesn't alias with $rptr+3*$num
1122	# modulo 4096, which covers ret[num], am[num] and n[num]
1123	# (see bn_exp.c). This is done to allow memory disambiguation
1124	# logic do its magic. [Extra 256 bytes is for power mask
1125	# calculated from 7th argument, the index.]
1126	#
1127	lea	-320(%rsp,$num,2),%r11
1128	mov	%rsp,%rbp
1129	sub	$rptr,%r11
1130	and	\$4095,%r11
1131	cmp	%r11,%r10
1132	jb	.Lpwr_sp_alt
1133	sub	%r11,%rbp		# align with $aptr
1134	lea	-320(%rbp,$num,2),%rbp	# future alloca(frame+2*num*8+256)
1135	jmp	.Lpwr_sp_done
1136
1137.align	32
1138.Lpwr_sp_alt:
1139	lea	4096-320(,$num,2),%r10
1140	lea	-320(%rbp,$num,2),%rbp	# future alloca(frame+2*num*8+256)
1141	sub	%r10,%r11
1142	mov	\$0,%r10
1143	cmovc	%r10,%r11
1144	sub	%r11,%rbp
1145.Lpwr_sp_done:
1146	and	\$-64,%rbp
1147	mov	%rsp,%r11
1148	sub	%rbp,%r11
1149	and	\$-4096,%r11
1150	lea	(%rbp,%r11),%rsp
1151	mov	(%rsp),%r10
1152	cmp	%rbp,%rsp
1153	ja	.Lpwr_page_walk
1154	jmp	.Lpwr_page_walk_done
1155
1156.Lpwr_page_walk:
1157	lea	-4096(%rsp),%rsp
1158	mov	(%rsp),%r10
1159	cmp	%rbp,%rsp
1160	ja	.Lpwr_page_walk
1161.Lpwr_page_walk_done:
1162
1163	mov	$num,%r10
1164	neg	$num
1165
1166	##############################################################
1167	# Stack layout
1168	#
1169	# +0	saved $num, used in reduction section
1170	# +8	&t[2*$num], used in reduction section
1171	# +32	saved *n0
1172	# +40	saved %rsp
1173	# +48	t[2*$num]
1174	#
1175	mov	$n0,  32(%rsp)
1176	mov	%rax, 40(%rsp)		# save original %rsp
1177.cfi_cfa_expression	%rsp+40,deref,+8
1178.Lpower5_body:
1179	movq	$rptr,%xmm1		# save $rptr, used in sqr8x
1180	movq	$nptr,%xmm2		# save $nptr
1181	movq	%r10, %xmm3		# -$num, used in sqr8x
1182	movq	$bptr,%xmm4
1183
1184	call	__bn_sqr8x_internal
1185	call	__bn_post4x_internal
1186	call	__bn_sqr8x_internal
1187	call	__bn_post4x_internal
1188	call	__bn_sqr8x_internal
1189	call	__bn_post4x_internal
1190	call	__bn_sqr8x_internal
1191	call	__bn_post4x_internal
1192	call	__bn_sqr8x_internal
1193	call	__bn_post4x_internal
1194
1195	movq	%xmm2,$nptr
1196	movq	%xmm4,$bptr
1197	mov	$aptr,$rptr
1198	mov	40(%rsp),%rax
1199	lea	32(%rsp),$n0
1200
1201	call	mul4x_internal
1202
1203	mov	40(%rsp),%rsi		# restore %rsp
1204.cfi_def_cfa	%rsi,8
1205	mov	\$1,%rax
1206	mov	-48(%rsi),%r15
1207.cfi_restore	%r15
1208	mov	-40(%rsi),%r14
1209.cfi_restore	%r14
1210	mov	-32(%rsi),%r13
1211.cfi_restore	%r13
1212	mov	-24(%rsi),%r12
1213.cfi_restore	%r12
1214	mov	-16(%rsi),%rbp
1215.cfi_restore	%rbp
1216	mov	-8(%rsi),%rbx
1217.cfi_restore	%rbx
1218	lea	(%rsi),%rsp
1219.cfi_def_cfa_register	%rsp
1220.Lpower5_epilogue:
1221	ret
1222.cfi_endproc
1223.size	bn_power5,.-bn_power5
1224
1225.globl	bn_sqr8x_internal
1226.hidden	bn_sqr8x_internal
1227.type	bn_sqr8x_internal,\@abi-omnipotent
1228.align	32
1229bn_sqr8x_internal:
1230__bn_sqr8x_internal:
1231.cfi_startproc
1232	##############################################################
1233	# Squaring part:
1234	#
1235	# a) multiply-n-add everything but a[i]*a[i];
1236	# b) shift result of a) by 1 to the left and accumulate
1237	#    a[i]*a[i] products;
1238	#
1239	##############################################################
1240	#                                                     a[1]a[0]
1241	#                                                 a[2]a[0]
1242	#                                             a[3]a[0]
1243	#                                             a[2]a[1]
1244	#                                         a[4]a[0]
1245	#                                         a[3]a[1]
1246	#                                     a[5]a[0]
1247	#                                     a[4]a[1]
1248	#                                     a[3]a[2]
1249	#                                 a[6]a[0]
1250	#                                 a[5]a[1]
1251	#                                 a[4]a[2]
1252	#                             a[7]a[0]
1253	#                             a[6]a[1]
1254	#                             a[5]a[2]
1255	#                             a[4]a[3]
1256	#                         a[7]a[1]
1257	#                         a[6]a[2]
1258	#                         a[5]a[3]
1259	#                     a[7]a[2]
1260	#                     a[6]a[3]
1261	#                     a[5]a[4]
1262	#                 a[7]a[3]
1263	#                 a[6]a[4]
1264	#             a[7]a[4]
1265	#             a[6]a[5]
1266	#         a[7]a[5]
1267	#     a[7]a[6]
1268	#                                                     a[1]a[0]
1269	#                                                 a[2]a[0]
1270	#                                             a[3]a[0]
1271	#                                         a[4]a[0]
1272	#                                     a[5]a[0]
1273	#                                 a[6]a[0]
1274	#                             a[7]a[0]
1275	#                                             a[2]a[1]
1276	#                                         a[3]a[1]
1277	#                                     a[4]a[1]
1278	#                                 a[5]a[1]
1279	#                             a[6]a[1]
1280	#                         a[7]a[1]
1281	#                                     a[3]a[2]
1282	#                                 a[4]a[2]
1283	#                             a[5]a[2]
1284	#                         a[6]a[2]
1285	#                     a[7]a[2]
1286	#                             a[4]a[3]
1287	#                         a[5]a[3]
1288	#                     a[6]a[3]
1289	#                 a[7]a[3]
1290	#                     a[5]a[4]
1291	#                 a[6]a[4]
1292	#             a[7]a[4]
1293	#             a[6]a[5]
1294	#         a[7]a[5]
1295	#     a[7]a[6]
1296	#                                                         a[0]a[0]
1297	#                                                 a[1]a[1]
1298	#                                         a[2]a[2]
1299	#                                 a[3]a[3]
1300	#                         a[4]a[4]
1301	#                 a[5]a[5]
1302	#         a[6]a[6]
1303	# a[7]a[7]
1304
1305	lea	32(%r10),$i		# $i=-($num-32)
1306	lea	($aptr,$num),$aptr	# end of a[] buffer, ($aptr,$i)=&ap[2]
1307
1308	mov	$num,$j			# $j=$num
1309
1310					# comments apply to $num==8 case
1311	mov	-32($aptr,$i),$a0	# a[0]
1312	lea	48+8(%rsp,$num,2),$tptr	# end of tp[] buffer, &tp[2*$num]
1313	mov	-24($aptr,$i),%rax	# a[1]
1314	lea	-32($tptr,$i),$tptr	# end of tp[] window, &tp[2*$num-"$i"]
1315	mov	-16($aptr,$i),$ai	# a[2]
1316	mov	%rax,$a1
1317
1318	mul	$a0			# a[1]*a[0]
1319	mov	%rax,$A0[0]		# a[1]*a[0]
1320	 mov	$ai,%rax		# a[2]
1321	mov	%rdx,$A0[1]
1322	mov	$A0[0],-24($tptr,$i)	# t[1]
1323
1324	mul	$a0			# a[2]*a[0]
1325	add	%rax,$A0[1]
1326	 mov	$ai,%rax
1327	adc	\$0,%rdx
1328	mov	$A0[1],-16($tptr,$i)	# t[2]
1329	mov	%rdx,$A0[0]
1330
1331
1332	 mov	-8($aptr,$i),$ai	# a[3]
1333	mul	$a1			# a[2]*a[1]
1334	mov	%rax,$A1[0]		# a[2]*a[1]+t[3]
1335	 mov	$ai,%rax
1336	mov	%rdx,$A1[1]
1337
1338	 lea	($i),$j
1339	mul	$a0			# a[3]*a[0]
1340	add	%rax,$A0[0]		# a[3]*a[0]+a[2]*a[1]+t[3]
1341	 mov	$ai,%rax
1342	mov	%rdx,$A0[1]
1343	adc	\$0,$A0[1]
1344	add	$A1[0],$A0[0]
1345	adc	\$0,$A0[1]
1346	mov	$A0[0],-8($tptr,$j)	# t[3]
1347	jmp	.Lsqr4x_1st
1348
1349.align	32
1350.Lsqr4x_1st:
1351	 mov	($aptr,$j),$ai		# a[4]
1352	mul	$a1			# a[3]*a[1]
1353	add	%rax,$A1[1]		# a[3]*a[1]+t[4]
1354	 mov	$ai,%rax
1355	mov	%rdx,$A1[0]
1356	adc	\$0,$A1[0]
1357
1358	mul	$a0			# a[4]*a[0]
1359	add	%rax,$A0[1]		# a[4]*a[0]+a[3]*a[1]+t[4]
1360	 mov	$ai,%rax		# a[3]
1361	 mov	8($aptr,$j),$ai		# a[5]
1362	mov	%rdx,$A0[0]
1363	adc	\$0,$A0[0]
1364	add	$A1[1],$A0[1]
1365	adc	\$0,$A0[0]
1366
1367
1368	mul	$a1			# a[4]*a[3]
1369	add	%rax,$A1[0]		# a[4]*a[3]+t[5]
1370	 mov	$ai,%rax
1371	 mov	$A0[1],($tptr,$j)	# t[4]
1372	mov	%rdx,$A1[1]
1373	adc	\$0,$A1[1]
1374
1375	mul	$a0			# a[5]*a[2]
1376	add	%rax,$A0[0]		# a[5]*a[2]+a[4]*a[3]+t[5]
1377	 mov	$ai,%rax
1378	 mov	16($aptr,$j),$ai	# a[6]
1379	mov	%rdx,$A0[1]
1380	adc	\$0,$A0[1]
1381	add	$A1[0],$A0[0]
1382	adc	\$0,$A0[1]
1383
1384	mul	$a1			# a[5]*a[3]
1385	add	%rax,$A1[1]		# a[5]*a[3]+t[6]
1386	 mov	$ai,%rax
1387	 mov	$A0[0],8($tptr,$j)	# t[5]
1388	mov	%rdx,$A1[0]
1389	adc	\$0,$A1[0]
1390
1391	mul	$a0			# a[6]*a[2]
1392	add	%rax,$A0[1]		# a[6]*a[2]+a[5]*a[3]+t[6]
1393	 mov	$ai,%rax		# a[3]
1394	 mov	24($aptr,$j),$ai	# a[7]
1395	mov	%rdx,$A0[0]
1396	adc	\$0,$A0[0]
1397	add	$A1[1],$A0[1]
1398	adc	\$0,$A0[0]
1399
1400
1401	mul	$a1			# a[6]*a[5]
1402	add	%rax,$A1[0]		# a[6]*a[5]+t[7]
1403	 mov	$ai,%rax
1404	 mov	$A0[1],16($tptr,$j)	# t[6]
1405	mov	%rdx,$A1[1]
1406	adc	\$0,$A1[1]
1407	 lea	32($j),$j
1408
1409	mul	$a0			# a[7]*a[4]
1410	add	%rax,$A0[0]		# a[7]*a[4]+a[6]*a[5]+t[6]
1411	 mov	$ai,%rax
1412	mov	%rdx,$A0[1]
1413	adc	\$0,$A0[1]
1414	add	$A1[0],$A0[0]
1415	adc	\$0,$A0[1]
1416	mov	$A0[0],-8($tptr,$j)	# t[7]
1417
1418	cmp	\$0,$j
1419	jne	.Lsqr4x_1st
1420
1421	mul	$a1			# a[7]*a[5]
1422	add	%rax,$A1[1]
1423	lea	16($i),$i
1424	adc	\$0,%rdx
1425	add	$A0[1],$A1[1]
1426	adc	\$0,%rdx
1427
1428	mov	$A1[1],($tptr)		# t[8]
1429	mov	%rdx,$A1[0]
1430	mov	%rdx,8($tptr)		# t[9]
1431	jmp	.Lsqr4x_outer
1432
1433.align	32
1434.Lsqr4x_outer:				# comments apply to $num==6 case
1435	mov	-32($aptr,$i),$a0	# a[0]
1436	lea	48+8(%rsp,$num,2),$tptr	# end of tp[] buffer, &tp[2*$num]
1437	mov	-24($aptr,$i),%rax	# a[1]
1438	lea	-32($tptr,$i),$tptr	# end of tp[] window, &tp[2*$num-"$i"]
1439	mov	-16($aptr,$i),$ai	# a[2]
1440	mov	%rax,$a1
1441
1442	mul	$a0			# a[1]*a[0]
1443	mov	-24($tptr,$i),$A0[0]	# t[1]
1444	add	%rax,$A0[0]		# a[1]*a[0]+t[1]
1445	 mov	$ai,%rax		# a[2]
1446	adc	\$0,%rdx
1447	mov	$A0[0],-24($tptr,$i)	# t[1]
1448	mov	%rdx,$A0[1]
1449
1450	mul	$a0			# a[2]*a[0]
1451	add	%rax,$A0[1]
1452	 mov	$ai,%rax
1453	adc	\$0,%rdx
1454	add	-16($tptr,$i),$A0[1]	# a[2]*a[0]+t[2]
1455	mov	%rdx,$A0[0]
1456	adc	\$0,$A0[0]
1457	mov	$A0[1],-16($tptr,$i)	# t[2]
1458
1459	xor	$A1[0],$A1[0]
1460
1461	 mov	-8($aptr,$i),$ai	# a[3]
1462	mul	$a1			# a[2]*a[1]
1463	add	%rax,$A1[0]		# a[2]*a[1]+t[3]
1464	 mov	$ai,%rax
1465	adc	\$0,%rdx
1466	add	-8($tptr,$i),$A1[0]
1467	mov	%rdx,$A1[1]
1468	adc	\$0,$A1[1]
1469
1470	mul	$a0			# a[3]*a[0]
1471	add	%rax,$A0[0]		# a[3]*a[0]+a[2]*a[1]+t[3]
1472	 mov	$ai,%rax
1473	adc	\$0,%rdx
1474	add	$A1[0],$A0[0]
1475	mov	%rdx,$A0[1]
1476	adc	\$0,$A0[1]
1477	mov	$A0[0],-8($tptr,$i)	# t[3]
1478
1479	lea	($i),$j
1480	jmp	.Lsqr4x_inner
1481
1482.align	32
1483.Lsqr4x_inner:
1484	 mov	($aptr,$j),$ai		# a[4]
1485	mul	$a1			# a[3]*a[1]
1486	add	%rax,$A1[1]		# a[3]*a[1]+t[4]
1487	 mov	$ai,%rax
1488	mov	%rdx,$A1[0]
1489	adc	\$0,$A1[0]
1490	add	($tptr,$j),$A1[1]
1491	adc	\$0,$A1[0]
1492
1493	.byte	0x67
1494	mul	$a0			# a[4]*a[0]
1495	add	%rax,$A0[1]		# a[4]*a[0]+a[3]*a[1]+t[4]
1496	 mov	$ai,%rax		# a[3]
1497	 mov	8($aptr,$j),$ai		# a[5]
1498	mov	%rdx,$A0[0]
1499	adc	\$0,$A0[0]
1500	add	$A1[1],$A0[1]
1501	adc	\$0,$A0[0]
1502
1503	mul	$a1			# a[4]*a[3]
1504	add	%rax,$A1[0]		# a[4]*a[3]+t[5]
1505	mov	$A0[1],($tptr,$j)	# t[4]
1506	 mov	$ai,%rax
1507	mov	%rdx,$A1[1]
1508	adc	\$0,$A1[1]
1509	add	8($tptr,$j),$A1[0]
1510	lea	16($j),$j		# j++
1511	adc	\$0,$A1[1]
1512
1513	mul	$a0			# a[5]*a[2]
1514	add	%rax,$A0[0]		# a[5]*a[2]+a[4]*a[3]+t[5]
1515	 mov	$ai,%rax
1516	adc	\$0,%rdx
1517	add	$A1[0],$A0[0]
1518	mov	%rdx,$A0[1]
1519	adc	\$0,$A0[1]
1520	mov	$A0[0],-8($tptr,$j)	# t[5], "preloaded t[1]" below
1521
1522	cmp	\$0,$j
1523	jne	.Lsqr4x_inner
1524
1525	.byte	0x67
1526	mul	$a1			# a[5]*a[3]
1527	add	%rax,$A1[1]
1528	adc	\$0,%rdx
1529	add	$A0[1],$A1[1]
1530	adc	\$0,%rdx
1531
1532	mov	$A1[1],($tptr)		# t[6], "preloaded t[2]" below
1533	mov	%rdx,$A1[0]
1534	mov	%rdx,8($tptr)		# t[7], "preloaded t[3]" below
1535
1536	add	\$16,$i
1537	jnz	.Lsqr4x_outer
1538
1539					# comments apply to $num==4 case
1540	mov	-32($aptr),$a0		# a[0]
1541	lea	48+8(%rsp,$num,2),$tptr	# end of tp[] buffer, &tp[2*$num]
1542	mov	-24($aptr),%rax		# a[1]
1543	lea	-32($tptr,$i),$tptr	# end of tp[] window, &tp[2*$num-"$i"]
1544	mov	-16($aptr),$ai		# a[2]
1545	mov	%rax,$a1
1546
1547	mul	$a0			# a[1]*a[0]
1548	add	%rax,$A0[0]		# a[1]*a[0]+t[1], preloaded t[1]
1549	 mov	$ai,%rax		# a[2]
1550	mov	%rdx,$A0[1]
1551	adc	\$0,$A0[1]
1552
1553	mul	$a0			# a[2]*a[0]
1554	add	%rax,$A0[1]
1555	 mov	$ai,%rax
1556	 mov	$A0[0],-24($tptr)	# t[1]
1557	mov	%rdx,$A0[0]
1558	adc	\$0,$A0[0]
1559	add	$A1[1],$A0[1]		# a[2]*a[0]+t[2], preloaded t[2]
1560	 mov	-8($aptr),$ai		# a[3]
1561	adc	\$0,$A0[0]
1562
1563	mul	$a1			# a[2]*a[1]
1564	add	%rax,$A1[0]		# a[2]*a[1]+t[3], preloaded t[3]
1565	 mov	$ai,%rax
1566	 mov	$A0[1],-16($tptr)	# t[2]
1567	mov	%rdx,$A1[1]
1568	adc	\$0,$A1[1]
1569
1570	mul	$a0			# a[3]*a[0]
1571	add	%rax,$A0[0]		# a[3]*a[0]+a[2]*a[1]+t[3]
1572	 mov	$ai,%rax
1573	mov	%rdx,$A0[1]
1574	adc	\$0,$A0[1]
1575	add	$A1[0],$A0[0]
1576	adc	\$0,$A0[1]
1577	mov	$A0[0],-8($tptr)	# t[3]
1578
1579	mul	$a1			# a[3]*a[1]
1580	add	%rax,$A1[1]
1581	 mov	-16($aptr),%rax		# a[2]
1582	adc	\$0,%rdx
1583	add	$A0[1],$A1[1]
1584	adc	\$0,%rdx
1585
1586	mov	$A1[1],($tptr)		# t[4]
1587	mov	%rdx,$A1[0]
1588	mov	%rdx,8($tptr)		# t[5]
1589
1590	mul	$ai			# a[2]*a[3]
1591___
1592{
1593my ($shift,$carry)=($a0,$a1);
1594my @S=(@A1,$ai,$n0);
1595$code.=<<___;
1596	 add	\$16,$i
1597	 xor	$shift,$shift
1598	 sub	$num,$i			# $i=16-$num
1599	 xor	$carry,$carry
1600
1601	add	$A1[0],%rax		# t[5]
1602	adc	\$0,%rdx
1603	mov	%rax,8($tptr)		# t[5]
1604	mov	%rdx,16($tptr)		# t[6]
1605	mov	$carry,24($tptr)	# t[7]
1606
1607	 mov	-16($aptr,$i),%rax	# a[0]
1608	lea	48+8(%rsp),$tptr
1609	 xor	$A0[0],$A0[0]		# t[0]
1610	 mov	8($tptr),$A0[1]		# t[1]
1611
1612	lea	($shift,$A0[0],2),$S[0]	# t[2*i]<<1 | shift
1613	shr	\$63,$A0[0]
1614	lea	($j,$A0[1],2),$S[1]	# t[2*i+1]<<1 |
1615	shr	\$63,$A0[1]
1616	or	$A0[0],$S[1]		# | t[2*i]>>63
1617	 mov	16($tptr),$A0[0]	# t[2*i+2]	# prefetch
1618	mov	$A0[1],$shift		# shift=t[2*i+1]>>63
1619	mul	%rax			# a[i]*a[i]
1620	neg	$carry			# mov $carry,cf
1621	 mov	24($tptr),$A0[1]	# t[2*i+2+1]	# prefetch
1622	adc	%rax,$S[0]
1623	 mov	-8($aptr,$i),%rax	# a[i+1]	# prefetch
1624	mov	$S[0],($tptr)
1625	adc	%rdx,$S[1]
1626
1627	lea	($shift,$A0[0],2),$S[2]	# t[2*i]<<1 | shift
1628	 mov	$S[1],8($tptr)
1629	 sbb	$carry,$carry		# mov cf,$carry
1630	shr	\$63,$A0[0]
1631	lea	($j,$A0[1],2),$S[3]	# t[2*i+1]<<1 |
1632	shr	\$63,$A0[1]
1633	or	$A0[0],$S[3]		# | t[2*i]>>63
1634	 mov	32($tptr),$A0[0]	# t[2*i+2]	# prefetch
1635	mov	$A0[1],$shift		# shift=t[2*i+1]>>63
1636	mul	%rax			# a[i]*a[i]
1637	neg	$carry			# mov $carry,cf
1638	 mov	40($tptr),$A0[1]	# t[2*i+2+1]	# prefetch
1639	adc	%rax,$S[2]
1640	 mov	0($aptr,$i),%rax	# a[i+1]	# prefetch
1641	mov	$S[2],16($tptr)
1642	adc	%rdx,$S[3]
1643	lea	16($i),$i
1644	mov	$S[3],24($tptr)
1645	sbb	$carry,$carry		# mov cf,$carry
1646	lea	64($tptr),$tptr
1647	jmp	.Lsqr4x_shift_n_add
1648
1649.align	32
1650.Lsqr4x_shift_n_add:
1651	lea	($shift,$A0[0],2),$S[0]	# t[2*i]<<1 | shift
1652	shr	\$63,$A0[0]
1653	lea	($j,$A0[1],2),$S[1]	# t[2*i+1]<<1 |
1654	shr	\$63,$A0[1]
1655	or	$A0[0],$S[1]		# | t[2*i]>>63
1656	 mov	-16($tptr),$A0[0]	# t[2*i+2]	# prefetch
1657	mov	$A0[1],$shift		# shift=t[2*i+1]>>63
1658	mul	%rax			# a[i]*a[i]
1659	neg	$carry			# mov $carry,cf
1660	 mov	-8($tptr),$A0[1]	# t[2*i+2+1]	# prefetch
1661	adc	%rax,$S[0]
1662	 mov	-8($aptr,$i),%rax	# a[i+1]	# prefetch
1663	mov	$S[0],-32($tptr)
1664	adc	%rdx,$S[1]
1665
1666	lea	($shift,$A0[0],2),$S[2]	# t[2*i]<<1 | shift
1667	 mov	$S[1],-24($tptr)
1668	 sbb	$carry,$carry		# mov cf,$carry
1669	shr	\$63,$A0[0]
1670	lea	($j,$A0[1],2),$S[3]	# t[2*i+1]<<1 |
1671	shr	\$63,$A0[1]
1672	or	$A0[0],$S[3]		# | t[2*i]>>63
1673	 mov	0($tptr),$A0[0]		# t[2*i+2]	# prefetch
1674	mov	$A0[1],$shift		# shift=t[2*i+1]>>63
1675	mul	%rax			# a[i]*a[i]
1676	neg	$carry			# mov $carry,cf
1677	 mov	8($tptr),$A0[1]		# t[2*i+2+1]	# prefetch
1678	adc	%rax,$S[2]
1679	 mov	0($aptr,$i),%rax	# a[i+1]	# prefetch
1680	mov	$S[2],-16($tptr)
1681	adc	%rdx,$S[3]
1682
1683	lea	($shift,$A0[0],2),$S[0]	# t[2*i]<<1 | shift
1684	 mov	$S[3],-8($tptr)
1685	 sbb	$carry,$carry		# mov cf,$carry
1686	shr	\$63,$A0[0]
1687	lea	($j,$A0[1],2),$S[1]	# t[2*i+1]<<1 |
1688	shr	\$63,$A0[1]
1689	or	$A0[0],$S[1]		# | t[2*i]>>63
1690	 mov	16($tptr),$A0[0]	# t[2*i+2]	# prefetch
1691	mov	$A0[1],$shift		# shift=t[2*i+1]>>63
1692	mul	%rax			# a[i]*a[i]
1693	neg	$carry			# mov $carry,cf
1694	 mov	24($tptr),$A0[1]	# t[2*i+2+1]	# prefetch
1695	adc	%rax,$S[0]
1696	 mov	8($aptr,$i),%rax	# a[i+1]	# prefetch
1697	mov	$S[0],0($tptr)
1698	adc	%rdx,$S[1]
1699
1700	lea	($shift,$A0[0],2),$S[2]	# t[2*i]<<1 | shift
1701	 mov	$S[1],8($tptr)
1702	 sbb	$carry,$carry		# mov cf,$carry
1703	shr	\$63,$A0[0]
1704	lea	($j,$A0[1],2),$S[3]	# t[2*i+1]<<1 |
1705	shr	\$63,$A0[1]
1706	or	$A0[0],$S[3]		# | t[2*i]>>63
1707	 mov	32($tptr),$A0[0]	# t[2*i+2]	# prefetch
1708	mov	$A0[1],$shift		# shift=t[2*i+1]>>63
1709	mul	%rax			# a[i]*a[i]
1710	neg	$carry			# mov $carry,cf
1711	 mov	40($tptr),$A0[1]	# t[2*i+2+1]	# prefetch
1712	adc	%rax,$S[2]
1713	 mov	16($aptr,$i),%rax	# a[i+1]	# prefetch
1714	mov	$S[2],16($tptr)
1715	adc	%rdx,$S[3]
1716	mov	$S[3],24($tptr)
1717	sbb	$carry,$carry		# mov cf,$carry
1718	lea	64($tptr),$tptr
1719	add	\$32,$i
1720	jnz	.Lsqr4x_shift_n_add
1721
1722	lea	($shift,$A0[0],2),$S[0]	# t[2*i]<<1 | shift
1723	.byte	0x67
1724	shr	\$63,$A0[0]
1725	lea	($j,$A0[1],2),$S[1]	# t[2*i+1]<<1 |
1726	shr	\$63,$A0[1]
1727	or	$A0[0],$S[1]		# | t[2*i]>>63
1728	 mov	-16($tptr),$A0[0]	# t[2*i+2]	# prefetch
1729	mov	$A0[1],$shift		# shift=t[2*i+1]>>63
1730	mul	%rax			# a[i]*a[i]
1731	neg	$carry			# mov $carry,cf
1732	 mov	-8($tptr),$A0[1]	# t[2*i+2+1]	# prefetch
1733	adc	%rax,$S[0]
1734	 mov	-8($aptr),%rax		# a[i+1]	# prefetch
1735	mov	$S[0],-32($tptr)
1736	adc	%rdx,$S[1]
1737
1738	lea	($shift,$A0[0],2),$S[2]	# t[2*i]<<1|shift
1739	 mov	$S[1],-24($tptr)
1740	 sbb	$carry,$carry		# mov cf,$carry
1741	shr	\$63,$A0[0]
1742	lea	($j,$A0[1],2),$S[3]	# t[2*i+1]<<1 |
1743	shr	\$63,$A0[1]
1744	or	$A0[0],$S[3]		# | t[2*i]>>63
1745	mul	%rax			# a[i]*a[i]
1746	neg	$carry			# mov $carry,cf
1747	adc	%rax,$S[2]
1748	adc	%rdx,$S[3]
1749	mov	$S[2],-16($tptr)
1750	mov	$S[3],-8($tptr)
1751___
1752}
1753######################################################################
1754# Montgomery reduction part, "word-by-word" algorithm.
1755#
1756# This new path is inspired by multiple submissions from Intel, by
1757# Shay Gueron, Vlad Krasnov, Erdinc Ozturk, James Guilford,
1758# Vinodh Gopal...
1759{
1760my ($nptr,$tptr,$carry,$m0)=("%rbp","%rdi","%rsi","%rbx");
1761
1762$code.=<<___;
1763	movq	%xmm2,$nptr
1764__bn_sqr8x_reduction:
1765	xor	%rax,%rax
1766	lea	($nptr,$num),%rcx	# end of n[]
1767	lea	48+8(%rsp,$num,2),%rdx	# end of t[] buffer
1768	mov	%rcx,0+8(%rsp)
1769	lea	48+8(%rsp,$num),$tptr	# end of initial t[] window
1770	mov	%rdx,8+8(%rsp)
1771	neg	$num
1772	jmp	.L8x_reduction_loop
1773
1774.align	32
1775.L8x_reduction_loop:
1776	lea	($tptr,$num),$tptr	# start of current t[] window
1777	.byte	0x66
1778	mov	8*0($tptr),$m0
1779	mov	8*1($tptr),%r9
1780	mov	8*2($tptr),%r10
1781	mov	8*3($tptr),%r11
1782	mov	8*4($tptr),%r12
1783	mov	8*5($tptr),%r13
1784	mov	8*6($tptr),%r14
1785	mov	8*7($tptr),%r15
1786	mov	%rax,(%rdx)		# store top-most carry bit
1787	lea	8*8($tptr),$tptr
1788
1789	.byte	0x67
1790	mov	$m0,%r8
1791	imulq	32+8(%rsp),$m0		# n0*a[0]
1792	mov	8*0($nptr),%rax		# n[0]
1793	mov	\$8,%ecx
1794	jmp	.L8x_reduce
1795
1796.align	32
1797.L8x_reduce:
1798	mulq	$m0
1799	 mov	8*1($nptr),%rax		# n[1]
1800	neg	%r8
1801	mov	%rdx,%r8
1802	adc	\$0,%r8
1803
1804	mulq	$m0
1805	add	%rax,%r9
1806	 mov	8*2($nptr),%rax
1807	adc	\$0,%rdx
1808	add	%r9,%r8
1809	 mov	$m0,48-8+8(%rsp,%rcx,8)	# put aside n0*a[i]
1810	mov	%rdx,%r9
1811	adc	\$0,%r9
1812
1813	mulq	$m0
1814	add	%rax,%r10
1815	 mov	8*3($nptr),%rax
1816	adc	\$0,%rdx
1817	add	%r10,%r9
1818	 mov	32+8(%rsp),$carry	# pull n0, borrow $carry
1819	mov	%rdx,%r10
1820	adc	\$0,%r10
1821
1822	mulq	$m0
1823	add	%rax,%r11
1824	 mov	8*4($nptr),%rax
1825	adc	\$0,%rdx
1826	 imulq	%r8,$carry		# modulo-scheduled
1827	add	%r11,%r10
1828	mov	%rdx,%r11
1829	adc	\$0,%r11
1830
1831	mulq	$m0
1832	add	%rax,%r12
1833	 mov	8*5($nptr),%rax
1834	adc	\$0,%rdx
1835	add	%r12,%r11
1836	mov	%rdx,%r12
1837	adc	\$0,%r12
1838
1839	mulq	$m0
1840	add	%rax,%r13
1841	 mov	8*6($nptr),%rax
1842	adc	\$0,%rdx
1843	add	%r13,%r12
1844	mov	%rdx,%r13
1845	adc	\$0,%r13
1846
1847	mulq	$m0
1848	add	%rax,%r14
1849	 mov	8*7($nptr),%rax
1850	adc	\$0,%rdx
1851	add	%r14,%r13
1852	mov	%rdx,%r14
1853	adc	\$0,%r14
1854
1855	mulq	$m0
1856	 mov	$carry,$m0		# n0*a[i]
1857	add	%rax,%r15
1858	 mov	8*0($nptr),%rax		# n[0]
1859	adc	\$0,%rdx
1860	add	%r15,%r14
1861	mov	%rdx,%r15
1862	adc	\$0,%r15
1863
1864	dec	%ecx
1865	jnz	.L8x_reduce
1866
1867	lea	8*8($nptr),$nptr
1868	xor	%rax,%rax
1869	mov	8+8(%rsp),%rdx		# pull end of t[]
1870	cmp	0+8(%rsp),$nptr		# end of n[]?
1871	jae	.L8x_no_tail
1872
1873	.byte	0x66
1874	add	8*0($tptr),%r8
1875	adc	8*1($tptr),%r9
1876	adc	8*2($tptr),%r10
1877	adc	8*3($tptr),%r11
1878	adc	8*4($tptr),%r12
1879	adc	8*5($tptr),%r13
1880	adc	8*6($tptr),%r14
1881	adc	8*7($tptr),%r15
1882	sbb	$carry,$carry		# top carry
1883
1884	mov	48+56+8(%rsp),$m0	# pull n0*a[0]
1885	mov	\$8,%ecx
1886	mov	8*0($nptr),%rax
1887	jmp	.L8x_tail
1888
1889.align	32
1890.L8x_tail:
1891	mulq	$m0
1892	add	%rax,%r8
1893	 mov	8*1($nptr),%rax
1894	 mov	%r8,($tptr)		# save result
1895	mov	%rdx,%r8
1896	adc	\$0,%r8
1897
1898	mulq	$m0
1899	add	%rax,%r9
1900	 mov	8*2($nptr),%rax
1901	adc	\$0,%rdx
1902	add	%r9,%r8
1903	 lea	8($tptr),$tptr		# $tptr++
1904	mov	%rdx,%r9
1905	adc	\$0,%r9
1906
1907	mulq	$m0
1908	add	%rax,%r10
1909	 mov	8*3($nptr),%rax
1910	adc	\$0,%rdx
1911	add	%r10,%r9
1912	mov	%rdx,%r10
1913	adc	\$0,%r10
1914
1915	mulq	$m0
1916	add	%rax,%r11
1917	 mov	8*4($nptr),%rax
1918	adc	\$0,%rdx
1919	add	%r11,%r10
1920	mov	%rdx,%r11
1921	adc	\$0,%r11
1922
1923	mulq	$m0
1924	add	%rax,%r12
1925	 mov	8*5($nptr),%rax
1926	adc	\$0,%rdx
1927	add	%r12,%r11
1928	mov	%rdx,%r12
1929	adc	\$0,%r12
1930
1931	mulq	$m0
1932	add	%rax,%r13
1933	 mov	8*6($nptr),%rax
1934	adc	\$0,%rdx
1935	add	%r13,%r12
1936	mov	%rdx,%r13
1937	adc	\$0,%r13
1938
1939	mulq	$m0
1940	add	%rax,%r14
1941	 mov	8*7($nptr),%rax
1942	adc	\$0,%rdx
1943	add	%r14,%r13
1944	mov	%rdx,%r14
1945	adc	\$0,%r14
1946
1947	mulq	$m0
1948	 mov	48-16+8(%rsp,%rcx,8),$m0# pull n0*a[i]
1949	add	%rax,%r15
1950	adc	\$0,%rdx
1951	add	%r15,%r14
1952	 mov	8*0($nptr),%rax		# pull n[0]
1953	mov	%rdx,%r15
1954	adc	\$0,%r15
1955
1956	dec	%ecx
1957	jnz	.L8x_tail
1958
1959	lea	8*8($nptr),$nptr
1960	mov	8+8(%rsp),%rdx		# pull end of t[]
1961	cmp	0+8(%rsp),$nptr		# end of n[]?
1962	jae	.L8x_tail_done		# break out of loop
1963
1964	 mov	48+56+8(%rsp),$m0	# pull n0*a[0]
1965	neg	$carry
1966	 mov	8*0($nptr),%rax		# pull n[0]
1967	adc	8*0($tptr),%r8
1968	adc	8*1($tptr),%r9
1969	adc	8*2($tptr),%r10
1970	adc	8*3($tptr),%r11
1971	adc	8*4($tptr),%r12
1972	adc	8*5($tptr),%r13
1973	adc	8*6($tptr),%r14
1974	adc	8*7($tptr),%r15
1975	sbb	$carry,$carry		# top carry
1976
1977	mov	\$8,%ecx
1978	jmp	.L8x_tail
1979
1980.align	32
1981.L8x_tail_done:
1982	xor	%rax,%rax
1983	add	(%rdx),%r8		# can this overflow?
1984	adc	\$0,%r9
1985	adc	\$0,%r10
1986	adc	\$0,%r11
1987	adc	\$0,%r12
1988	adc	\$0,%r13
1989	adc	\$0,%r14
1990	adc	\$0,%r15
1991	adc	\$0,%rax
1992
1993	neg	$carry
1994.L8x_no_tail:
1995	adc	8*0($tptr),%r8
1996	adc	8*1($tptr),%r9
1997	adc	8*2($tptr),%r10
1998	adc	8*3($tptr),%r11
1999	adc	8*4($tptr),%r12
2000	adc	8*5($tptr),%r13
2001	adc	8*6($tptr),%r14
2002	adc	8*7($tptr),%r15
2003	adc	\$0,%rax		# top-most carry
2004	 mov	-8($nptr),%rcx		# np[num-1]
2005	 xor	$carry,$carry
2006
2007	movq	%xmm2,$nptr		# restore $nptr
2008
2009	mov	%r8,8*0($tptr)		# store top 512 bits
2010	mov	%r9,8*1($tptr)
2011	 movq	%xmm3,$num		# $num is %r9, can't be moved upwards
2012	mov	%r10,8*2($tptr)
2013	mov	%r11,8*3($tptr)
2014	mov	%r12,8*4($tptr)
2015	mov	%r13,8*5($tptr)
2016	mov	%r14,8*6($tptr)
2017	mov	%r15,8*7($tptr)
2018	lea	8*8($tptr),$tptr
2019
2020	cmp	%rdx,$tptr		# end of t[]?
2021	jb	.L8x_reduction_loop
2022	ret
2023.cfi_endproc
2024.size	bn_sqr8x_internal,.-bn_sqr8x_internal
2025___
2026}
2027##############################################################
2028# Post-condition, 4x unrolled
2029#
2030{
2031my ($tptr,$nptr)=("%rbx","%rbp");
2032$code.=<<___;
2033.type	__bn_post4x_internal,\@abi-omnipotent
2034.align	32
2035__bn_post4x_internal:
2036.cfi_startproc
2037	mov	8*0($nptr),%r12
2038	lea	(%rdi,$num),$tptr	# %rdi was $tptr above
2039	mov	$num,%rcx
2040	movq	%xmm1,$rptr		# restore $rptr
2041	neg	%rax
2042	movq	%xmm1,$aptr		# prepare for back-to-back call
2043	sar	\$3+2,%rcx
2044	dec	%r12			# so that after 'not' we get -n[0]
2045	xor	%r10,%r10
2046	mov	8*1($nptr),%r13
2047	mov	8*2($nptr),%r14
2048	mov	8*3($nptr),%r15
2049	jmp	.Lsqr4x_sub_entry
2050
2051.align	16
2052.Lsqr4x_sub:
2053	mov	8*0($nptr),%r12
2054	mov	8*1($nptr),%r13
2055	mov	8*2($nptr),%r14
2056	mov	8*3($nptr),%r15
2057.Lsqr4x_sub_entry:
2058	lea	8*4($nptr),$nptr
2059	not	%r12
2060	not	%r13
2061	not	%r14
2062	not	%r15
2063	and	%rax,%r12
2064	and	%rax,%r13
2065	and	%rax,%r14
2066	and	%rax,%r15
2067
2068	neg	%r10			# mov %r10,%cf
2069	adc	8*0($tptr),%r12
2070	adc	8*1($tptr),%r13
2071	adc	8*2($tptr),%r14
2072	adc	8*3($tptr),%r15
2073	mov	%r12,8*0($rptr)
2074	lea	8*4($tptr),$tptr
2075	mov	%r13,8*1($rptr)
2076	sbb	%r10,%r10		# mov %cf,%r10
2077	mov	%r14,8*2($rptr)
2078	mov	%r15,8*3($rptr)
2079	lea	8*4($rptr),$rptr
2080
2081	inc	%rcx			# pass %cf
2082	jnz	.Lsqr4x_sub
2083
2084	mov	$num,%r10		# prepare for back-to-back call
2085	neg	$num			# restore $num
2086	ret
2087.cfi_endproc
2088.size	__bn_post4x_internal,.-__bn_post4x_internal
2089___
2090}
2091{
2092$code.=<<___;
2093.globl	bn_from_montgomery
2094.type	bn_from_montgomery,\@abi-omnipotent
2095.align	32
2096bn_from_montgomery:
2097.cfi_startproc
2098	testl	\$7,`($win64?"48(%rsp)":"%r9d")`
2099	jz	bn_from_mont8x
2100	xor	%eax,%eax
2101	ret
2102.cfi_endproc
2103.size	bn_from_montgomery,.-bn_from_montgomery
2104
2105.type	bn_from_mont8x,\@function,6
2106.align	32
2107bn_from_mont8x:
2108.cfi_startproc
2109	.byte	0x67
2110	mov	%rsp,%rax
2111.cfi_def_cfa_register	%rax
2112	push	%rbx
2113.cfi_push	%rbx
2114	push	%rbp
2115.cfi_push	%rbp
2116	push	%r12
2117.cfi_push	%r12
2118	push	%r13
2119.cfi_push	%r13
2120	push	%r14
2121.cfi_push	%r14
2122	push	%r15
2123.cfi_push	%r15
2124.Lfrom_prologue:
2125
2126	shl	\$3,${num}d		# convert $num to bytes
2127	lea	($num,$num,2),%r10	# 3*$num in bytes
2128	neg	$num
2129	mov	($n0),$n0		# *n0
2130
2131	##############################################################
2132	# Ensure that stack frame doesn't alias with $rptr+3*$num
2133	# modulo 4096, which covers ret[num], am[num] and n[num]
2134	# (see bn_exp.c). The stack is allocated to aligned with
2135	# bn_power5's frame, and as bn_from_montgomery happens to be
2136	# last operation, we use the opportunity to cleanse it.
2137	#
2138	lea	-320(%rsp,$num,2),%r11
2139	mov	%rsp,%rbp
2140	sub	$rptr,%r11
2141	and	\$4095,%r11
2142	cmp	%r11,%r10
2143	jb	.Lfrom_sp_alt
2144	sub	%r11,%rbp		# align with $aptr
2145	lea	-320(%rbp,$num,2),%rbp	# future alloca(frame+2*$num*8+256)
2146	jmp	.Lfrom_sp_done
2147
2148.align	32
2149.Lfrom_sp_alt:
2150	lea	4096-320(,$num,2),%r10
2151	lea	-320(%rbp,$num,2),%rbp	# future alloca(frame+2*$num*8+256)
2152	sub	%r10,%r11
2153	mov	\$0,%r10
2154	cmovc	%r10,%r11
2155	sub	%r11,%rbp
2156.Lfrom_sp_done:
2157	and	\$-64,%rbp
2158	mov	%rsp,%r11
2159	sub	%rbp,%r11
2160	and	\$-4096,%r11
2161	lea	(%rbp,%r11),%rsp
2162	mov	(%rsp),%r10
2163	cmp	%rbp,%rsp
2164	ja	.Lfrom_page_walk
2165	jmp	.Lfrom_page_walk_done
2166
2167.Lfrom_page_walk:
2168	lea	-4096(%rsp),%rsp
2169	mov	(%rsp),%r10
2170	cmp	%rbp,%rsp
2171	ja	.Lfrom_page_walk
2172.Lfrom_page_walk_done:
2173
2174	mov	$num,%r10
2175	neg	$num
2176
2177	##############################################################
2178	# Stack layout
2179	#
2180	# +0	saved $num, used in reduction section
2181	# +8	&t[2*$num], used in reduction section
2182	# +32	saved *n0
2183	# +40	saved %rsp
2184	# +48	t[2*$num]
2185	#
2186	mov	$n0,  32(%rsp)
2187	mov	%rax, 40(%rsp)		# save original %rsp
2188.cfi_cfa_expression	%rsp+40,deref,+8
2189.Lfrom_body:
2190	mov	$num,%r11
2191	lea	48(%rsp),%rax
2192	pxor	%xmm0,%xmm0
2193	jmp	.Lmul_by_1
2194
2195.align	32
2196.Lmul_by_1:
2197	movdqu	($aptr),%xmm1
2198	movdqu	16($aptr),%xmm2
2199	movdqu	32($aptr),%xmm3
2200	movdqa	%xmm0,(%rax,$num)
2201	movdqu	48($aptr),%xmm4
2202	movdqa	%xmm0,16(%rax,$num)
2203	.byte	0x48,0x8d,0xb6,0x40,0x00,0x00,0x00	# lea	64($aptr),$aptr
2204	movdqa	%xmm1,(%rax)
2205	movdqa	%xmm0,32(%rax,$num)
2206	movdqa	%xmm2,16(%rax)
2207	movdqa	%xmm0,48(%rax,$num)
2208	movdqa	%xmm3,32(%rax)
2209	movdqa	%xmm4,48(%rax)
2210	lea	64(%rax),%rax
2211	sub	\$64,%r11
2212	jnz	.Lmul_by_1
2213
2214	movq	$rptr,%xmm1
2215	movq	$nptr,%xmm2
2216	.byte	0x67
2217	mov	$nptr,%rbp
2218	movq	%r10, %xmm3		# -num
2219___
2220$code.=<<___ if ($addx);
2221	leaq	OPENSSL_ia32cap_P(%rip),%r11
2222	mov	8(%r11),%r11d
2223	and	\$0x80108,%r11d
2224	cmp	\$0x80108,%r11d		# check for AD*X+BMI2+BMI1
2225	jne	.Lfrom_mont_nox
2226
2227	lea	(%rax,$num),$rptr
2228	call	__bn_sqrx8x_reduction
2229	call	__bn_postx4x_internal
2230
2231	pxor	%xmm0,%xmm0
2232	lea	48(%rsp),%rax
2233	jmp	.Lfrom_mont_zero
2234
2235.align	32
2236.Lfrom_mont_nox:
2237___
2238$code.=<<___;
2239	call	__bn_sqr8x_reduction
2240	call	__bn_post4x_internal
2241
2242	pxor	%xmm0,%xmm0
2243	lea	48(%rsp),%rax
2244	jmp	.Lfrom_mont_zero
2245
2246.align	32
2247.Lfrom_mont_zero:
2248	mov	40(%rsp),%rsi		# restore %rsp
2249.cfi_def_cfa	%rsi,8
2250	movdqa	%xmm0,16*0(%rax)
2251	movdqa	%xmm0,16*1(%rax)
2252	movdqa	%xmm0,16*2(%rax)
2253	movdqa	%xmm0,16*3(%rax)
2254	lea	16*4(%rax),%rax
2255	sub	\$32,$num
2256	jnz	.Lfrom_mont_zero
2257
2258	mov	\$1,%rax
2259	mov	-48(%rsi),%r15
2260.cfi_restore	%r15
2261	mov	-40(%rsi),%r14
2262.cfi_restore	%r14
2263	mov	-32(%rsi),%r13
2264.cfi_restore	%r13
2265	mov	-24(%rsi),%r12
2266.cfi_restore	%r12
2267	mov	-16(%rsi),%rbp
2268.cfi_restore	%rbp
2269	mov	-8(%rsi),%rbx
2270.cfi_restore	%rbx
2271	lea	(%rsi),%rsp
2272.cfi_def_cfa_register	%rsp
2273.Lfrom_epilogue:
2274	ret
2275.cfi_endproc
2276.size	bn_from_mont8x,.-bn_from_mont8x
2277___
2278}
2279}}}
2280
2281if ($addx) {{{
2282my $bp="%rdx";	# restore original value
2283
2284$code.=<<___;
2285.type	bn_mulx4x_mont_gather5,\@function,6
2286.align	32
2287bn_mulx4x_mont_gather5:
2288.cfi_startproc
2289	mov	%rsp,%rax
2290.cfi_def_cfa_register	%rax
2291.Lmulx4x_enter:
2292	push	%rbx
2293.cfi_push	%rbx
2294	push	%rbp
2295.cfi_push	%rbp
2296	push	%r12
2297.cfi_push	%r12
2298	push	%r13
2299.cfi_push	%r13
2300	push	%r14
2301.cfi_push	%r14
2302	push	%r15
2303.cfi_push	%r15
2304.Lmulx4x_prologue:
2305
2306	shl	\$3,${num}d		# convert $num to bytes
2307	lea	($num,$num,2),%r10	# 3*$num in bytes
2308	neg	$num			# -$num
2309	mov	($n0),$n0		# *n0
2310
2311	##############################################################
2312	# Ensure that stack frame doesn't alias with $rptr+3*$num
2313	# modulo 4096, which covers ret[num], am[num] and n[num]
2314	# (see bn_exp.c). This is done to allow memory disambiguation
2315	# logic do its magic. [Extra [num] is allocated in order
2316	# to align with bn_power5's frame, which is cleansed after
2317	# completing exponentiation. Extra 256 bytes is for power mask
2318	# calculated from 7th argument, the index.]
2319	#
2320	lea	-320(%rsp,$num,2),%r11
2321	mov	%rsp,%rbp
2322	sub	$rp,%r11
2323	and	\$4095,%r11
2324	cmp	%r11,%r10
2325	jb	.Lmulx4xsp_alt
2326	sub	%r11,%rbp		# align with $aptr
2327	lea	-320(%rbp,$num,2),%rbp	# future alloca(frame+2*$num*8+256)
2328	jmp	.Lmulx4xsp_done
2329
2330.Lmulx4xsp_alt:
2331	lea	4096-320(,$num,2),%r10
2332	lea	-320(%rbp,$num,2),%rbp	# future alloca(frame+2*$num*8+256)
2333	sub	%r10,%r11
2334	mov	\$0,%r10
2335	cmovc	%r10,%r11
2336	sub	%r11,%rbp
2337.Lmulx4xsp_done:
2338	and	\$-64,%rbp		# ensure alignment
2339	mov	%rsp,%r11
2340	sub	%rbp,%r11
2341	and	\$-4096,%r11
2342	lea	(%rbp,%r11),%rsp
2343	mov	(%rsp),%r10
2344	cmp	%rbp,%rsp
2345	ja	.Lmulx4x_page_walk
2346	jmp	.Lmulx4x_page_walk_done
2347
2348.Lmulx4x_page_walk:
2349	lea	-4096(%rsp),%rsp
2350	mov	(%rsp),%r10
2351	cmp	%rbp,%rsp
2352	ja	.Lmulx4x_page_walk
2353.Lmulx4x_page_walk_done:
2354
2355	##############################################################
2356	# Stack layout
2357	# +0	-num
2358	# +8	off-loaded &b[i]
2359	# +16	end of b[num]
2360	# +24	inner counter
2361	# +32	saved n0
2362	# +40	saved %rsp
2363	# +48
2364	# +56	saved rp
2365	# +64	tmp[num+1]
2366	#
2367	mov	$n0, 32(%rsp)		# save *n0
2368	mov	%rax,40(%rsp)		# save original %rsp
2369.cfi_cfa_expression	%rsp+40,deref,+8
2370.Lmulx4x_body:
2371	call	mulx4x_internal
2372
2373	mov	40(%rsp),%rsi		# restore %rsp
2374.cfi_def_cfa	%rsi,8
2375	mov	\$1,%rax
2376
2377	mov	-48(%rsi),%r15
2378.cfi_restore	%r15
2379	mov	-40(%rsi),%r14
2380.cfi_restore	%r14
2381	mov	-32(%rsi),%r13
2382.cfi_restore	%r13
2383	mov	-24(%rsi),%r12
2384.cfi_restore	%r12
2385	mov	-16(%rsi),%rbp
2386.cfi_restore	%rbp
2387	mov	-8(%rsi),%rbx
2388.cfi_restore	%rbx
2389	lea	(%rsi),%rsp
2390.cfi_def_cfa_register	%rsp
2391.Lmulx4x_epilogue:
2392	ret
2393.cfi_endproc
2394.size	bn_mulx4x_mont_gather5,.-bn_mulx4x_mont_gather5
2395
2396.type	mulx4x_internal,\@abi-omnipotent
2397.align	32
2398mulx4x_internal:
2399.cfi_startproc
2400	mov	$num,8(%rsp)		# save -$num (it was in bytes)
2401	mov	$num,%r10
2402	neg	$num			# restore $num
2403	shl	\$5,$num
2404	neg	%r10			# restore $num
2405	lea	128($bp,$num),%r13	# end of powers table (+size optimization)
2406	shr	\$5+5,$num
2407	movd	`($win64?56:8)`(%rax),%xmm5	# load 7th argument
2408	sub	\$1,$num
2409	lea	.Linc(%rip),%rax
2410	mov	%r13,16+8(%rsp)		# end of b[num]
2411	mov	$num,24+8(%rsp)		# inner counter
2412	mov	$rp, 56+8(%rsp)		# save $rp
2413___
2414my ($aptr, $bptr, $nptr, $tptr, $mi,  $bi,  $zero, $num)=
2415   ("%rsi","%rdi","%rcx","%rbx","%r8","%r9","%rbp","%rax");
2416my $rptr=$bptr;
2417my $STRIDE=2**5*8;		# 5 is "window size"
2418my $N=$STRIDE/4;		# should match cache line size
2419$code.=<<___;
2420	movdqa	0(%rax),%xmm0		# 00000001000000010000000000000000
2421	movdqa	16(%rax),%xmm1		# 00000002000000020000000200000002
2422	lea	88-112(%rsp,%r10),%r10	# place the mask after tp[num+1] (+ICache optimization)
2423	lea	128($bp),$bptr		# size optimization
2424
2425	pshufd	\$0,%xmm5,%xmm5		# broadcast index
2426	movdqa	%xmm1,%xmm4
2427	.byte	0x67
2428	movdqa	%xmm1,%xmm2
2429___
2430########################################################################
2431# calculate mask by comparing 0..31 to index and save result to stack
2432#
2433$code.=<<___;
2434	.byte	0x67
2435	paddd	%xmm0,%xmm1
2436	pcmpeqd	%xmm5,%xmm0		# compare to 1,0
2437	movdqa	%xmm4,%xmm3
2438___
2439for($i=0;$i<$STRIDE/16-4;$i+=4) {
2440$code.=<<___;
2441	paddd	%xmm1,%xmm2
2442	pcmpeqd	%xmm5,%xmm1		# compare to 3,2
2443	movdqa	%xmm0,`16*($i+0)+112`(%r10)
2444	movdqa	%xmm4,%xmm0
2445
2446	paddd	%xmm2,%xmm3
2447	pcmpeqd	%xmm5,%xmm2		# compare to 5,4
2448	movdqa	%xmm1,`16*($i+1)+112`(%r10)
2449	movdqa	%xmm4,%xmm1
2450
2451	paddd	%xmm3,%xmm0
2452	pcmpeqd	%xmm5,%xmm3		# compare to 7,6
2453	movdqa	%xmm2,`16*($i+2)+112`(%r10)
2454	movdqa	%xmm4,%xmm2
2455
2456	paddd	%xmm0,%xmm1
2457	pcmpeqd	%xmm5,%xmm0
2458	movdqa	%xmm3,`16*($i+3)+112`(%r10)
2459	movdqa	%xmm4,%xmm3
2460___
2461}
2462$code.=<<___;				# last iteration can be optimized
2463	.byte	0x67
2464	paddd	%xmm1,%xmm2
2465	pcmpeqd	%xmm5,%xmm1
2466	movdqa	%xmm0,`16*($i+0)+112`(%r10)
2467
2468	paddd	%xmm2,%xmm3
2469	pcmpeqd	%xmm5,%xmm2
2470	movdqa	%xmm1,`16*($i+1)+112`(%r10)
2471
2472	pcmpeqd	%xmm5,%xmm3
2473	movdqa	%xmm2,`16*($i+2)+112`(%r10)
2474
2475	pand	`16*($i+0)-128`($bptr),%xmm0	# while it's still in register
2476	pand	`16*($i+1)-128`($bptr),%xmm1
2477	pand	`16*($i+2)-128`($bptr),%xmm2
2478	movdqa	%xmm3,`16*($i+3)+112`(%r10)
2479	pand	`16*($i+3)-128`($bptr),%xmm3
2480	por	%xmm2,%xmm0
2481	por	%xmm3,%xmm1
2482___
2483for($i=0;$i<$STRIDE/16-4;$i+=4) {
2484$code.=<<___;
2485	movdqa	`16*($i+0)-128`($bptr),%xmm4
2486	movdqa	`16*($i+1)-128`($bptr),%xmm5
2487	movdqa	`16*($i+2)-128`($bptr),%xmm2
2488	pand	`16*($i+0)+112`(%r10),%xmm4
2489	movdqa	`16*($i+3)-128`($bptr),%xmm3
2490	pand	`16*($i+1)+112`(%r10),%xmm5
2491	por	%xmm4,%xmm0
2492	pand	`16*($i+2)+112`(%r10),%xmm2
2493	por	%xmm5,%xmm1
2494	pand	`16*($i+3)+112`(%r10),%xmm3
2495	por	%xmm2,%xmm0
2496	por	%xmm3,%xmm1
2497___
2498}
2499$code.=<<___;
2500	pxor	%xmm1,%xmm0
2501	pshufd	\$0x4e,%xmm0,%xmm1
2502	por	%xmm1,%xmm0
2503	lea	$STRIDE($bptr),$bptr
2504	movq	%xmm0,%rdx		# bp[0]
2505	lea	64+8*4+8(%rsp),$tptr
2506
2507	mov	%rdx,$bi
2508	mulx	0*8($aptr),$mi,%rax	# a[0]*b[0]
2509	mulx	1*8($aptr),%r11,%r12	# a[1]*b[0]
2510	add	%rax,%r11
2511	mulx	2*8($aptr),%rax,%r13	# ...
2512	adc	%rax,%r12
2513	adc	\$0,%r13
2514	mulx	3*8($aptr),%rax,%r14
2515
2516	mov	$mi,%r15
2517	imulq	32+8(%rsp),$mi		# "t[0]"*n0
2518	xor	$zero,$zero		# cf=0, of=0
2519	mov	$mi,%rdx
2520
2521	mov	$bptr,8+8(%rsp)		# off-load &b[i]
2522
2523	lea	4*8($aptr),$aptr
2524	adcx	%rax,%r13
2525	adcx	$zero,%r14		# cf=0
2526
2527	mulx	0*8($nptr),%rax,%r10
2528	adcx	%rax,%r15		# discarded
2529	adox	%r11,%r10
2530	mulx	1*8($nptr),%rax,%r11
2531	adcx	%rax,%r10
2532	adox	%r12,%r11
2533	mulx	2*8($nptr),%rax,%r12
2534	mov	24+8(%rsp),$bptr	# counter value
2535	mov	%r10,-8*4($tptr)
2536	adcx	%rax,%r11
2537	adox	%r13,%r12
2538	mulx	3*8($nptr),%rax,%r15
2539	 mov	$bi,%rdx
2540	mov	%r11,-8*3($tptr)
2541	adcx	%rax,%r12
2542	adox	$zero,%r15		# of=0
2543	lea	4*8($nptr),$nptr
2544	mov	%r12,-8*2($tptr)
2545	jmp	.Lmulx4x_1st
2546
2547.align	32
2548.Lmulx4x_1st:
2549	adcx	$zero,%r15		# cf=0, modulo-scheduled
2550	mulx	0*8($aptr),%r10,%rax	# a[4]*b[0]
2551	adcx	%r14,%r10
2552	mulx	1*8($aptr),%r11,%r14	# a[5]*b[0]
2553	adcx	%rax,%r11
2554	mulx	2*8($aptr),%r12,%rax	# ...
2555	adcx	%r14,%r12
2556	mulx	3*8($aptr),%r13,%r14
2557	 .byte	0x67,0x67
2558	 mov	$mi,%rdx
2559	adcx	%rax,%r13
2560	adcx	$zero,%r14		# cf=0
2561	lea	4*8($aptr),$aptr
2562	lea	4*8($tptr),$tptr
2563
2564	adox	%r15,%r10
2565	mulx	0*8($nptr),%rax,%r15
2566	adcx	%rax,%r10
2567	adox	%r15,%r11
2568	mulx	1*8($nptr),%rax,%r15
2569	adcx	%rax,%r11
2570	adox	%r15,%r12
2571	mulx	2*8($nptr),%rax,%r15
2572	mov	%r10,-5*8($tptr)
2573	adcx	%rax,%r12
2574	mov	%r11,-4*8($tptr)
2575	adox	%r15,%r13
2576	mulx	3*8($nptr),%rax,%r15
2577	 mov	$bi,%rdx
2578	mov	%r12,-3*8($tptr)
2579	adcx	%rax,%r13
2580	adox	$zero,%r15
2581	lea	4*8($nptr),$nptr
2582	mov	%r13,-2*8($tptr)
2583
2584	dec	$bptr			# of=0, pass cf
2585	jnz	.Lmulx4x_1st
2586
2587	mov	8(%rsp),$num		# load -num
2588	adc	$zero,%r15		# modulo-scheduled
2589	lea	($aptr,$num),$aptr	# rewind $aptr
2590	add	%r15,%r14
2591	mov	8+8(%rsp),$bptr		# re-load &b[i]
2592	adc	$zero,$zero		# top-most carry
2593	mov	%r14,-1*8($tptr)
2594	jmp	.Lmulx4x_outer
2595
2596.align	32
2597.Lmulx4x_outer:
2598	lea	16-256($tptr),%r10	# where 256-byte mask is (+density control)
2599	pxor	%xmm4,%xmm4
2600	.byte	0x67,0x67
2601	pxor	%xmm5,%xmm5
2602___
2603for($i=0;$i<$STRIDE/16;$i+=4) {
2604$code.=<<___;
2605	movdqa	`16*($i+0)-128`($bptr),%xmm0
2606	movdqa	`16*($i+1)-128`($bptr),%xmm1
2607	movdqa	`16*($i+2)-128`($bptr),%xmm2
2608	pand	`16*($i+0)+256`(%r10),%xmm0
2609	movdqa	`16*($i+3)-128`($bptr),%xmm3
2610	pand	`16*($i+1)+256`(%r10),%xmm1
2611	por	%xmm0,%xmm4
2612	pand	`16*($i+2)+256`(%r10),%xmm2
2613	por	%xmm1,%xmm5
2614	pand	`16*($i+3)+256`(%r10),%xmm3
2615	por	%xmm2,%xmm4
2616	por	%xmm3,%xmm5
2617___
2618}
2619$code.=<<___;
2620	por	%xmm5,%xmm4
2621	pshufd	\$0x4e,%xmm4,%xmm0
2622	por	%xmm4,%xmm0
2623	lea	$STRIDE($bptr),$bptr
2624	movq	%xmm0,%rdx		# m0=bp[i]
2625
2626	mov	$zero,($tptr)		# save top-most carry
2627	lea	4*8($tptr,$num),$tptr	# rewind $tptr
2628	mulx	0*8($aptr),$mi,%r11	# a[0]*b[i]
2629	xor	$zero,$zero		# cf=0, of=0
2630	mov	%rdx,$bi
2631	mulx	1*8($aptr),%r14,%r12	# a[1]*b[i]
2632	adox	-4*8($tptr),$mi		# +t[0]
2633	adcx	%r14,%r11
2634	mulx	2*8($aptr),%r15,%r13	# ...
2635	adox	-3*8($tptr),%r11
2636	adcx	%r15,%r12
2637	mulx	3*8($aptr),%rdx,%r14
2638	adox	-2*8($tptr),%r12
2639	adcx	%rdx,%r13
2640	lea	($nptr,$num),$nptr	# rewind $nptr
2641	lea	4*8($aptr),$aptr
2642	adox	-1*8($tptr),%r13
2643	adcx	$zero,%r14
2644	adox	$zero,%r14
2645
2646	mov	$mi,%r15
2647	imulq	32+8(%rsp),$mi		# "t[0]"*n0
2648
2649	mov	$mi,%rdx
2650	xor	$zero,$zero		# cf=0, of=0
2651	mov	$bptr,8+8(%rsp)		# off-load &b[i]
2652
2653	mulx	0*8($nptr),%rax,%r10
2654	adcx	%rax,%r15		# discarded
2655	adox	%r11,%r10
2656	mulx	1*8($nptr),%rax,%r11
2657	adcx	%rax,%r10
2658	adox	%r12,%r11
2659	mulx	2*8($nptr),%rax,%r12
2660	adcx	%rax,%r11
2661	adox	%r13,%r12
2662	mulx	3*8($nptr),%rax,%r15
2663	 mov	$bi,%rdx
2664	mov	24+8(%rsp),$bptr	# counter value
2665	mov	%r10,-8*4($tptr)
2666	adcx	%rax,%r12
2667	mov	%r11,-8*3($tptr)
2668	adox	$zero,%r15		# of=0
2669	mov	%r12,-8*2($tptr)
2670	lea	4*8($nptr),$nptr
2671	jmp	.Lmulx4x_inner
2672
2673.align	32
2674.Lmulx4x_inner:
2675	mulx	0*8($aptr),%r10,%rax	# a[4]*b[i]
2676	adcx	$zero,%r15		# cf=0, modulo-scheduled
2677	adox	%r14,%r10
2678	mulx	1*8($aptr),%r11,%r14	# a[5]*b[i]
2679	adcx	0*8($tptr),%r10
2680	adox	%rax,%r11
2681	mulx	2*8($aptr),%r12,%rax	# ...
2682	adcx	1*8($tptr),%r11
2683	adox	%r14,%r12
2684	mulx	3*8($aptr),%r13,%r14
2685	 mov	$mi,%rdx
2686	adcx	2*8($tptr),%r12
2687	adox	%rax,%r13
2688	adcx	3*8($tptr),%r13
2689	adox	$zero,%r14		# of=0
2690	lea	4*8($aptr),$aptr
2691	lea	4*8($tptr),$tptr
2692	adcx	$zero,%r14		# cf=0
2693
2694	adox	%r15,%r10
2695	mulx	0*8($nptr),%rax,%r15
2696	adcx	%rax,%r10
2697	adox	%r15,%r11
2698	mulx	1*8($nptr),%rax,%r15
2699	adcx	%rax,%r11
2700	adox	%r15,%r12
2701	mulx	2*8($nptr),%rax,%r15
2702	mov	%r10,-5*8($tptr)
2703	adcx	%rax,%r12
2704	adox	%r15,%r13
2705	mov	%r11,-4*8($tptr)
2706	mulx	3*8($nptr),%rax,%r15
2707	 mov	$bi,%rdx
2708	lea	4*8($nptr),$nptr
2709	mov	%r12,-3*8($tptr)
2710	adcx	%rax,%r13
2711	adox	$zero,%r15
2712	mov	%r13,-2*8($tptr)
2713
2714	dec	$bptr			# of=0, pass cf
2715	jnz	.Lmulx4x_inner
2716
2717	mov	0+8(%rsp),$num		# load -num
2718	adc	$zero,%r15		# modulo-scheduled
2719	sub	0*8($tptr),$bptr	# pull top-most carry to %cf
2720	mov	8+8(%rsp),$bptr		# re-load &b[i]
2721	mov	16+8(%rsp),%r10
2722	adc	%r15,%r14
2723	lea	($aptr,$num),$aptr	# rewind $aptr
2724	adc	$zero,$zero		# top-most carry
2725	mov	%r14,-1*8($tptr)
2726
2727	cmp	%r10,$bptr
2728	jb	.Lmulx4x_outer
2729
2730	mov	-8($nptr),%r10
2731	mov	$zero,%r8
2732	mov	($nptr,$num),%r12
2733	lea	($nptr,$num),%rbp	# rewind $nptr
2734	mov	$num,%rcx
2735	lea	($tptr,$num),%rdi	# rewind $tptr
2736	xor	%eax,%eax
2737	xor	%r15,%r15
2738	sub	%r14,%r10		# compare top-most words
2739	adc	%r15,%r15
2740	or	%r15,%r8
2741	sar	\$3+2,%rcx
2742	sub	%r8,%rax		# %rax=-%r8
2743	mov	56+8(%rsp),%rdx		# restore rp
2744	dec	%r12			# so that after 'not' we get -n[0]
2745	mov	8*1(%rbp),%r13
2746	xor	%r8,%r8
2747	mov	8*2(%rbp),%r14
2748	mov	8*3(%rbp),%r15
2749	jmp	.Lsqrx4x_sub_entry	# common post-condition
2750.cfi_endproc
2751.size	mulx4x_internal,.-mulx4x_internal
2752___
2753}{
2754######################################################################
2755# void bn_power5(
2756my $rptr="%rdi";	# BN_ULONG *rptr,
2757my $aptr="%rsi";	# const BN_ULONG *aptr,
2758my $bptr="%rdx";	# const void *table,
2759my $nptr="%rcx";	# const BN_ULONG *nptr,
2760my $n0  ="%r8";		# const BN_ULONG *n0);
2761my $num ="%r9";		# int num, has to be divisible by 8
2762			# int pwr);
2763
2764my ($i,$j,$tptr)=("%rbp","%rcx",$rptr);
2765my @A0=("%r10","%r11");
2766my @A1=("%r12","%r13");
2767my ($a0,$a1,$ai)=("%r14","%r15","%rbx");
2768
2769$code.=<<___;
2770.type	bn_powerx5,\@function,6
2771.align	32
2772bn_powerx5:
2773.cfi_startproc
2774	mov	%rsp,%rax
2775.cfi_def_cfa_register	%rax
2776.Lpowerx5_enter:
2777	push	%rbx
2778.cfi_push	%rbx
2779	push	%rbp
2780.cfi_push	%rbp
2781	push	%r12
2782.cfi_push	%r12
2783	push	%r13
2784.cfi_push	%r13
2785	push	%r14
2786.cfi_push	%r14
2787	push	%r15
2788.cfi_push	%r15
2789.Lpowerx5_prologue:
2790
2791	shl	\$3,${num}d		# convert $num to bytes
2792	lea	($num,$num,2),%r10	# 3*$num in bytes
2793	neg	$num
2794	mov	($n0),$n0		# *n0
2795
2796	##############################################################
2797	# Ensure that stack frame doesn't alias with $rptr+3*$num
2798	# modulo 4096, which covers ret[num], am[num] and n[num]
2799	# (see bn_exp.c). This is done to allow memory disambiguation
2800	# logic do its magic. [Extra 256 bytes is for power mask
2801	# calculated from 7th argument, the index.]
2802	#
2803	lea	-320(%rsp,$num,2),%r11
2804	mov	%rsp,%rbp
2805	sub	$rptr,%r11
2806	and	\$4095,%r11
2807	cmp	%r11,%r10
2808	jb	.Lpwrx_sp_alt
2809	sub	%r11,%rbp		# align with $aptr
2810	lea	-320(%rbp,$num,2),%rbp	# future alloca(frame+2*$num*8+256)
2811	jmp	.Lpwrx_sp_done
2812
2813.align	32
2814.Lpwrx_sp_alt:
2815	lea	4096-320(,$num,2),%r10
2816	lea	-320(%rbp,$num,2),%rbp	# alloca(frame+2*$num*8+256)
2817	sub	%r10,%r11
2818	mov	\$0,%r10
2819	cmovc	%r10,%r11
2820	sub	%r11,%rbp
2821.Lpwrx_sp_done:
2822	and	\$-64,%rbp
2823	mov	%rsp,%r11
2824	sub	%rbp,%r11
2825	and	\$-4096,%r11
2826	lea	(%rbp,%r11),%rsp
2827	mov	(%rsp),%r10
2828	cmp	%rbp,%rsp
2829	ja	.Lpwrx_page_walk
2830	jmp	.Lpwrx_page_walk_done
2831
2832.Lpwrx_page_walk:
2833	lea	-4096(%rsp),%rsp
2834	mov	(%rsp),%r10
2835	cmp	%rbp,%rsp
2836	ja	.Lpwrx_page_walk
2837.Lpwrx_page_walk_done:
2838
2839	mov	$num,%r10
2840	neg	$num
2841
2842	##############################################################
2843	# Stack layout
2844	#
2845	# +0	saved $num, used in reduction section
2846	# +8	&t[2*$num], used in reduction section
2847	# +16	intermediate carry bit
2848	# +24	top-most carry bit, used in reduction section
2849	# +32	saved *n0
2850	# +40	saved %rsp
2851	# +48	t[2*$num]
2852	#
2853	pxor	%xmm0,%xmm0
2854	movq	$rptr,%xmm1		# save $rptr
2855	movq	$nptr,%xmm2		# save $nptr
2856	movq	%r10, %xmm3		# -$num
2857	movq	$bptr,%xmm4
2858	mov	$n0,  32(%rsp)
2859	mov	%rax, 40(%rsp)		# save original %rsp
2860.cfi_cfa_expression	%rsp+40,deref,+8
2861.Lpowerx5_body:
2862
2863	call	__bn_sqrx8x_internal
2864	call	__bn_postx4x_internal
2865	call	__bn_sqrx8x_internal
2866	call	__bn_postx4x_internal
2867	call	__bn_sqrx8x_internal
2868	call	__bn_postx4x_internal
2869	call	__bn_sqrx8x_internal
2870	call	__bn_postx4x_internal
2871	call	__bn_sqrx8x_internal
2872	call	__bn_postx4x_internal
2873
2874	mov	%r10,$num		# -num
2875	mov	$aptr,$rptr
2876	movq	%xmm2,$nptr
2877	movq	%xmm4,$bptr
2878	mov	40(%rsp),%rax
2879
2880	call	mulx4x_internal
2881
2882	mov	40(%rsp),%rsi		# restore %rsp
2883.cfi_def_cfa	%rsi,8
2884	mov	\$1,%rax
2885
2886	mov	-48(%rsi),%r15
2887.cfi_restore	%r15
2888	mov	-40(%rsi),%r14
2889.cfi_restore	%r14
2890	mov	-32(%rsi),%r13
2891.cfi_restore	%r13
2892	mov	-24(%rsi),%r12
2893.cfi_restore	%r12
2894	mov	-16(%rsi),%rbp
2895.cfi_restore	%rbp
2896	mov	-8(%rsi),%rbx
2897.cfi_restore	%rbx
2898	lea	(%rsi),%rsp
2899.cfi_def_cfa_register	%rsp
2900.Lpowerx5_epilogue:
2901	ret
2902.cfi_endproc
2903.size	bn_powerx5,.-bn_powerx5
2904
2905.globl	bn_sqrx8x_internal
2906.type	bn_sqrx8x_internal,\@abi-omnipotent
2907.align	32
2908bn_sqrx8x_internal:
2909__bn_sqrx8x_internal:
2910.cfi_startproc
2911	##################################################################
2912	# Squaring part:
2913	#
2914	# a) multiply-n-add everything but a[i]*a[i];
2915	# b) shift result of a) by 1 to the left and accumulate
2916	#    a[i]*a[i] products;
2917	#
2918	##################################################################
2919	# a[7]a[7]a[6]a[6]a[5]a[5]a[4]a[4]a[3]a[3]a[2]a[2]a[1]a[1]a[0]a[0]
2920	#                                                     a[1]a[0]
2921	#                                                 a[2]a[0]
2922	#                                             a[3]a[0]
2923	#                                             a[2]a[1]
2924	#                                         a[3]a[1]
2925	#                                     a[3]a[2]
2926	#
2927	#                                         a[4]a[0]
2928	#                                     a[5]a[0]
2929	#                                 a[6]a[0]
2930	#                             a[7]a[0]
2931	#                                     a[4]a[1]
2932	#                                 a[5]a[1]
2933	#                             a[6]a[1]
2934	#                         a[7]a[1]
2935	#                                 a[4]a[2]
2936	#                             a[5]a[2]
2937	#                         a[6]a[2]
2938	#                     a[7]a[2]
2939	#                             a[4]a[3]
2940	#                         a[5]a[3]
2941	#                     a[6]a[3]
2942	#                 a[7]a[3]
2943	#
2944	#                     a[5]a[4]
2945	#                 a[6]a[4]
2946	#             a[7]a[4]
2947	#             a[6]a[5]
2948	#         a[7]a[5]
2949	#     a[7]a[6]
2950	# a[7]a[7]a[6]a[6]a[5]a[5]a[4]a[4]a[3]a[3]a[2]a[2]a[1]a[1]a[0]a[0]
2951___
2952{
2953my ($zero,$carry)=("%rbp","%rcx");
2954my $aaptr=$zero;
2955$code.=<<___;
2956	lea	48+8(%rsp),$tptr
2957	lea	($aptr,$num),$aaptr
2958	mov	$num,0+8(%rsp)			# save $num
2959	mov	$aaptr,8+8(%rsp)		# save end of $aptr
2960	jmp	.Lsqr8x_zero_start
2961
2962.align	32
2963.byte	0x66,0x66,0x66,0x2e,0x0f,0x1f,0x84,0x00,0x00,0x00,0x00,0x00
2964.Lsqrx8x_zero:
2965	.byte	0x3e
2966	movdqa	%xmm0,0*8($tptr)
2967	movdqa	%xmm0,2*8($tptr)
2968	movdqa	%xmm0,4*8($tptr)
2969	movdqa	%xmm0,6*8($tptr)
2970.Lsqr8x_zero_start:			# aligned at 32
2971	movdqa	%xmm0,8*8($tptr)
2972	movdqa	%xmm0,10*8($tptr)
2973	movdqa	%xmm0,12*8($tptr)
2974	movdqa	%xmm0,14*8($tptr)
2975	lea	16*8($tptr),$tptr
2976	sub	\$64,$num
2977	jnz	.Lsqrx8x_zero
2978
2979	mov	0*8($aptr),%rdx		# a[0], modulo-scheduled
2980	#xor	%r9,%r9			# t[1], ex-$num, zero already
2981	xor	%r10,%r10
2982	xor	%r11,%r11
2983	xor	%r12,%r12
2984	xor	%r13,%r13
2985	xor	%r14,%r14
2986	xor	%r15,%r15
2987	lea	48+8(%rsp),$tptr
2988	xor	$zero,$zero		# cf=0, cf=0
2989	jmp	.Lsqrx8x_outer_loop
2990
2991.align	32
2992.Lsqrx8x_outer_loop:
2993	mulx	1*8($aptr),%r8,%rax	# a[1]*a[0]
2994	adcx	%r9,%r8			# a[1]*a[0]+=t[1]
2995	adox	%rax,%r10
2996	mulx	2*8($aptr),%r9,%rax	# a[2]*a[0]
2997	adcx	%r10,%r9
2998	adox	%rax,%r11
2999	.byte	0xc4,0xe2,0xab,0xf6,0x86,0x18,0x00,0x00,0x00	# mulx	3*8($aptr),%r10,%rax	# ...
3000	adcx	%r11,%r10
3001	adox	%rax,%r12
3002	.byte	0xc4,0xe2,0xa3,0xf6,0x86,0x20,0x00,0x00,0x00	# mulx	4*8($aptr),%r11,%rax
3003	adcx	%r12,%r11
3004	adox	%rax,%r13
3005	mulx	5*8($aptr),%r12,%rax
3006	adcx	%r13,%r12
3007	adox	%rax,%r14
3008	mulx	6*8($aptr),%r13,%rax
3009	adcx	%r14,%r13
3010	adox	%r15,%rax
3011	mulx	7*8($aptr),%r14,%r15
3012	 mov	1*8($aptr),%rdx		# a[1]
3013	adcx	%rax,%r14
3014	adox	$zero,%r15
3015	adc	8*8($tptr),%r15
3016	mov	%r8,1*8($tptr)		# t[1]
3017	mov	%r9,2*8($tptr)		# t[2]
3018	sbb	$carry,$carry		# mov %cf,$carry
3019	xor	$zero,$zero		# cf=0, of=0
3020
3021
3022	mulx	2*8($aptr),%r8,%rbx	# a[2]*a[1]
3023	mulx	3*8($aptr),%r9,%rax	# a[3]*a[1]
3024	adcx	%r10,%r8
3025	adox	%rbx,%r9
3026	mulx	4*8($aptr),%r10,%rbx	# ...
3027	adcx	%r11,%r9
3028	adox	%rax,%r10
3029	.byte	0xc4,0xe2,0xa3,0xf6,0x86,0x28,0x00,0x00,0x00	# mulx	5*8($aptr),%r11,%rax
3030	adcx	%r12,%r10
3031	adox	%rbx,%r11
3032	.byte	0xc4,0xe2,0x9b,0xf6,0x9e,0x30,0x00,0x00,0x00	# mulx	6*8($aptr),%r12,%rbx
3033	adcx	%r13,%r11
3034	adox	%r14,%r12
3035	.byte	0xc4,0x62,0x93,0xf6,0xb6,0x38,0x00,0x00,0x00	# mulx	7*8($aptr),%r13,%r14
3036	 mov	2*8($aptr),%rdx		# a[2]
3037	adcx	%rax,%r12
3038	adox	%rbx,%r13
3039	adcx	%r15,%r13
3040	adox	$zero,%r14		# of=0
3041	adcx	$zero,%r14		# cf=0
3042
3043	mov	%r8,3*8($tptr)		# t[3]
3044	mov	%r9,4*8($tptr)		# t[4]
3045
3046	mulx	3*8($aptr),%r8,%rbx	# a[3]*a[2]
3047	mulx	4*8($aptr),%r9,%rax	# a[4]*a[2]
3048	adcx	%r10,%r8
3049	adox	%rbx,%r9
3050	mulx	5*8($aptr),%r10,%rbx	# ...
3051	adcx	%r11,%r9
3052	adox	%rax,%r10
3053	.byte	0xc4,0xe2,0xa3,0xf6,0x86,0x30,0x00,0x00,0x00	# mulx	6*8($aptr),%r11,%rax
3054	adcx	%r12,%r10
3055	adox	%r13,%r11
3056	.byte	0xc4,0x62,0x9b,0xf6,0xae,0x38,0x00,0x00,0x00	# mulx	7*8($aptr),%r12,%r13
3057	.byte	0x3e
3058	 mov	3*8($aptr),%rdx		# a[3]
3059	adcx	%rbx,%r11
3060	adox	%rax,%r12
3061	adcx	%r14,%r12
3062	mov	%r8,5*8($tptr)		# t[5]
3063	mov	%r9,6*8($tptr)		# t[6]
3064	 mulx	4*8($aptr),%r8,%rax	# a[4]*a[3]
3065	adox	$zero,%r13		# of=0
3066	adcx	$zero,%r13		# cf=0
3067
3068	mulx	5*8($aptr),%r9,%rbx	# a[5]*a[3]
3069	adcx	%r10,%r8
3070	adox	%rax,%r9
3071	mulx	6*8($aptr),%r10,%rax	# ...
3072	adcx	%r11,%r9
3073	adox	%r12,%r10
3074	mulx	7*8($aptr),%r11,%r12
3075	 mov	4*8($aptr),%rdx		# a[4]
3076	 mov	5*8($aptr),%r14		# a[5]
3077	adcx	%rbx,%r10
3078	adox	%rax,%r11
3079	 mov	6*8($aptr),%r15		# a[6]
3080	adcx	%r13,%r11
3081	adox	$zero,%r12		# of=0
3082	adcx	$zero,%r12		# cf=0
3083
3084	mov	%r8,7*8($tptr)		# t[7]
3085	mov	%r9,8*8($tptr)		# t[8]
3086
3087	mulx	%r14,%r9,%rax		# a[5]*a[4]
3088	 mov	7*8($aptr),%r8		# a[7]
3089	adcx	%r10,%r9
3090	mulx	%r15,%r10,%rbx		# a[6]*a[4]
3091	adox	%rax,%r10
3092	adcx	%r11,%r10
3093	mulx	%r8,%r11,%rax		# a[7]*a[4]
3094	 mov	%r14,%rdx		# a[5]
3095	adox	%rbx,%r11
3096	adcx	%r12,%r11
3097	#adox	$zero,%rax		# of=0
3098	adcx	$zero,%rax		# cf=0
3099
3100	mulx	%r15,%r14,%rbx		# a[6]*a[5]
3101	mulx	%r8,%r12,%r13		# a[7]*a[5]
3102	 mov	%r15,%rdx		# a[6]
3103	 lea	8*8($aptr),$aptr
3104	adcx	%r14,%r11
3105	adox	%rbx,%r12
3106	adcx	%rax,%r12
3107	adox	$zero,%r13
3108
3109	.byte	0x67,0x67
3110	mulx	%r8,%r8,%r14		# a[7]*a[6]
3111	adcx	%r8,%r13
3112	adcx	$zero,%r14
3113
3114	cmp	8+8(%rsp),$aptr
3115	je	.Lsqrx8x_outer_break
3116
3117	neg	$carry			# mov $carry,%cf
3118	mov	\$-8,%rcx
3119	mov	$zero,%r15
3120	mov	8*8($tptr),%r8
3121	adcx	9*8($tptr),%r9		# +=t[9]
3122	adcx	10*8($tptr),%r10	# ...
3123	adcx	11*8($tptr),%r11
3124	adc	12*8($tptr),%r12
3125	adc	13*8($tptr),%r13
3126	adc	14*8($tptr),%r14
3127	adc	15*8($tptr),%r15
3128	lea	($aptr),$aaptr
3129	lea	2*64($tptr),$tptr
3130	sbb	%rax,%rax		# mov %cf,$carry
3131
3132	mov	-64($aptr),%rdx		# a[0]
3133	mov	%rax,16+8(%rsp)		# offload $carry
3134	mov	$tptr,24+8(%rsp)
3135
3136	#lea	8*8($tptr),$tptr	# see 2*8*8($tptr) above
3137	xor	%eax,%eax		# cf=0, of=0
3138	jmp	.Lsqrx8x_loop
3139
3140.align	32
3141.Lsqrx8x_loop:
3142	mov	%r8,%rbx
3143	mulx	0*8($aaptr),%rax,%r8	# a[8]*a[i]
3144	adcx	%rax,%rbx		# +=t[8]
3145	adox	%r9,%r8
3146
3147	mulx	1*8($aaptr),%rax,%r9	# ...
3148	adcx	%rax,%r8
3149	adox	%r10,%r9
3150
3151	mulx	2*8($aaptr),%rax,%r10
3152	adcx	%rax,%r9
3153	adox	%r11,%r10
3154
3155	mulx	3*8($aaptr),%rax,%r11
3156	adcx	%rax,%r10
3157	adox	%r12,%r11
3158
3159	.byte	0xc4,0x62,0xfb,0xf6,0xa5,0x20,0x00,0x00,0x00	# mulx	4*8($aaptr),%rax,%r12
3160	adcx	%rax,%r11
3161	adox	%r13,%r12
3162
3163	mulx	5*8($aaptr),%rax,%r13
3164	adcx	%rax,%r12
3165	adox	%r14,%r13
3166
3167	mulx	6*8($aaptr),%rax,%r14
3168	 mov	%rbx,($tptr,%rcx,8)	# store t[8+i]
3169	 mov	\$0,%ebx
3170	adcx	%rax,%r13
3171	adox	%r15,%r14
3172
3173	.byte	0xc4,0x62,0xfb,0xf6,0xbd,0x38,0x00,0x00,0x00	# mulx	7*8($aaptr),%rax,%r15
3174	 mov	8($aptr,%rcx,8),%rdx	# a[i]
3175	adcx	%rax,%r14
3176	adox	%rbx,%r15		# %rbx is 0, of=0
3177	adcx	%rbx,%r15		# cf=0
3178
3179	.byte	0x67
3180	inc	%rcx			# of=0
3181	jnz	.Lsqrx8x_loop
3182
3183	lea	8*8($aaptr),$aaptr
3184	mov	\$-8,%rcx
3185	cmp	8+8(%rsp),$aaptr	# done?
3186	je	.Lsqrx8x_break
3187
3188	sub	16+8(%rsp),%rbx		# mov 16(%rsp),%cf
3189	.byte	0x66
3190	mov	-64($aptr),%rdx
3191	adcx	0*8($tptr),%r8
3192	adcx	1*8($tptr),%r9
3193	adc	2*8($tptr),%r10
3194	adc	3*8($tptr),%r11
3195	adc	4*8($tptr),%r12
3196	adc	5*8($tptr),%r13
3197	adc	6*8($tptr),%r14
3198	adc	7*8($tptr),%r15
3199	lea	8*8($tptr),$tptr
3200	.byte	0x67
3201	sbb	%rax,%rax		# mov %cf,%rax
3202	xor	%ebx,%ebx		# cf=0, of=0
3203	mov	%rax,16+8(%rsp)		# offload carry
3204	jmp	.Lsqrx8x_loop
3205
3206.align	32
3207.Lsqrx8x_break:
3208	xor	$zero,$zero
3209	sub	16+8(%rsp),%rbx		# mov 16(%rsp),%cf
3210	adcx	$zero,%r8
3211	mov	24+8(%rsp),$carry	# initial $tptr, borrow $carry
3212	adcx	$zero,%r9
3213	mov	0*8($aptr),%rdx		# a[8], modulo-scheduled
3214	adc	\$0,%r10
3215	mov	%r8,0*8($tptr)
3216	adc	\$0,%r11
3217	adc	\$0,%r12
3218	adc	\$0,%r13
3219	adc	\$0,%r14
3220	adc	\$0,%r15
3221	cmp	$carry,$tptr		# cf=0, of=0
3222	je	.Lsqrx8x_outer_loop
3223
3224	mov	%r9,1*8($tptr)
3225	 mov	1*8($carry),%r9
3226	mov	%r10,2*8($tptr)
3227	 mov	2*8($carry),%r10
3228	mov	%r11,3*8($tptr)
3229	 mov	3*8($carry),%r11
3230	mov	%r12,4*8($tptr)
3231	 mov	4*8($carry),%r12
3232	mov	%r13,5*8($tptr)
3233	 mov	5*8($carry),%r13
3234	mov	%r14,6*8($tptr)
3235	 mov	6*8($carry),%r14
3236	mov	%r15,7*8($tptr)
3237	 mov	7*8($carry),%r15
3238	mov	$carry,$tptr
3239	jmp	.Lsqrx8x_outer_loop
3240
3241.align	32
3242.Lsqrx8x_outer_break:
3243	mov	%r9,9*8($tptr)		# t[9]
3244	 movq	%xmm3,%rcx		# -$num
3245	mov	%r10,10*8($tptr)	# ...
3246	mov	%r11,11*8($tptr)
3247	mov	%r12,12*8($tptr)
3248	mov	%r13,13*8($tptr)
3249	mov	%r14,14*8($tptr)
3250___
3251}{
3252my $i="%rcx";
3253$code.=<<___;
3254	lea	48+8(%rsp),$tptr
3255	mov	($aptr,$i),%rdx		# a[0]
3256
3257	mov	8($tptr),$A0[1]		# t[1]
3258	xor	$A0[0],$A0[0]		# t[0], of=0, cf=0
3259	mov	0+8(%rsp),$num		# restore $num
3260	adox	$A0[1],$A0[1]
3261	 mov	16($tptr),$A1[0]	# t[2]	# prefetch
3262	 mov	24($tptr),$A1[1]	# t[3]	# prefetch
3263	#jmp	.Lsqrx4x_shift_n_add	# happens to be aligned
3264
3265.align	32
3266.Lsqrx4x_shift_n_add:
3267	mulx	%rdx,%rax,%rbx
3268	 adox	$A1[0],$A1[0]
3269	adcx	$A0[0],%rax
3270	 .byte	0x48,0x8b,0x94,0x0e,0x08,0x00,0x00,0x00	# mov	8($aptr,$i),%rdx	# a[i+1]	# prefetch
3271	 .byte	0x4c,0x8b,0x97,0x20,0x00,0x00,0x00	# mov	32($tptr),$A0[0]	# t[2*i+4]	# prefetch
3272	 adox	$A1[1],$A1[1]
3273	adcx	$A0[1],%rbx
3274	 mov	40($tptr),$A0[1]		# t[2*i+4+1]	# prefetch
3275	mov	%rax,0($tptr)
3276	mov	%rbx,8($tptr)
3277
3278	mulx	%rdx,%rax,%rbx
3279	 adox	$A0[0],$A0[0]
3280	adcx	$A1[0],%rax
3281	 mov	16($aptr,$i),%rdx	# a[i+2]	# prefetch
3282	 mov	48($tptr),$A1[0]	# t[2*i+6]	# prefetch
3283	 adox	$A0[1],$A0[1]
3284	adcx	$A1[1],%rbx
3285	 mov	56($tptr),$A1[1]	# t[2*i+6+1]	# prefetch
3286	mov	%rax,16($tptr)
3287	mov	%rbx,24($tptr)
3288
3289	mulx	%rdx,%rax,%rbx
3290	 adox	$A1[0],$A1[0]
3291	adcx	$A0[0],%rax
3292	 mov	24($aptr,$i),%rdx	# a[i+3]	# prefetch
3293	 lea	32($i),$i
3294	 mov	64($tptr),$A0[0]	# t[2*i+8]	# prefetch
3295	 adox	$A1[1],$A1[1]
3296	adcx	$A0[1],%rbx
3297	 mov	72($tptr),$A0[1]	# t[2*i+8+1]	# prefetch
3298	mov	%rax,32($tptr)
3299	mov	%rbx,40($tptr)
3300
3301	mulx	%rdx,%rax,%rbx
3302	 adox	$A0[0],$A0[0]
3303	adcx	$A1[0],%rax
3304	jrcxz	.Lsqrx4x_shift_n_add_break
3305	 .byte	0x48,0x8b,0x94,0x0e,0x00,0x00,0x00,0x00	# mov	0($aptr,$i),%rdx	# a[i+4]	# prefetch
3306	 adox	$A0[1],$A0[1]
3307	adcx	$A1[1],%rbx
3308	 mov	80($tptr),$A1[0]	# t[2*i+10]	# prefetch
3309	 mov	88($tptr),$A1[1]	# t[2*i+10+1]	# prefetch
3310	mov	%rax,48($tptr)
3311	mov	%rbx,56($tptr)
3312	lea	64($tptr),$tptr
3313	nop
3314	jmp	.Lsqrx4x_shift_n_add
3315
3316.align	32
3317.Lsqrx4x_shift_n_add_break:
3318	adcx	$A1[1],%rbx
3319	mov	%rax,48($tptr)
3320	mov	%rbx,56($tptr)
3321	lea	64($tptr),$tptr		# end of t[] buffer
3322___
3323}
3324######################################################################
3325# Montgomery reduction part, "word-by-word" algorithm.
3326#
3327# This new path is inspired by multiple submissions from Intel, by
3328# Shay Gueron, Vlad Krasnov, Erdinc Ozturk, James Guilford,
3329# Vinodh Gopal...
3330{
3331my ($nptr,$carry,$m0)=("%rbp","%rsi","%rdx");
3332
3333$code.=<<___;
3334	movq	%xmm2,$nptr
3335__bn_sqrx8x_reduction:
3336	xor	%eax,%eax		# initial top-most carry bit
3337	mov	32+8(%rsp),%rbx		# n0
3338	mov	48+8(%rsp),%rdx		# "%r8", 8*0($tptr)
3339	lea	-8*8($nptr,$num),%rcx	# end of n[]
3340	#lea	48+8(%rsp,$num,2),$tptr	# end of t[] buffer
3341	mov	%rcx, 0+8(%rsp)		# save end of n[]
3342	mov	$tptr,8+8(%rsp)		# save end of t[]
3343
3344	lea	48+8(%rsp),$tptr		# initial t[] window
3345	jmp	.Lsqrx8x_reduction_loop
3346
3347.align	32
3348.Lsqrx8x_reduction_loop:
3349	mov	8*1($tptr),%r9
3350	mov	8*2($tptr),%r10
3351	mov	8*3($tptr),%r11
3352	mov	8*4($tptr),%r12
3353	mov	%rdx,%r8
3354	imulq	%rbx,%rdx		# n0*a[i]
3355	mov	8*5($tptr),%r13
3356	mov	8*6($tptr),%r14
3357	mov	8*7($tptr),%r15
3358	mov	%rax,24+8(%rsp)		# store top-most carry bit
3359
3360	lea	8*8($tptr),$tptr
3361	xor	$carry,$carry		# cf=0,of=0
3362	mov	\$-8,%rcx
3363	jmp	.Lsqrx8x_reduce
3364
3365.align	32
3366.Lsqrx8x_reduce:
3367	mov	%r8, %rbx
3368	mulx	8*0($nptr),%rax,%r8	# n[0]
3369	adcx	%rbx,%rax		# discarded
3370	adox	%r9,%r8
3371
3372	mulx	8*1($nptr),%rbx,%r9	# n[1]
3373	adcx	%rbx,%r8
3374	adox	%r10,%r9
3375
3376	mulx	8*2($nptr),%rbx,%r10
3377	adcx	%rbx,%r9
3378	adox	%r11,%r10
3379
3380	mulx	8*3($nptr),%rbx,%r11
3381	adcx	%rbx,%r10
3382	adox	%r12,%r11
3383
3384	.byte	0xc4,0x62,0xe3,0xf6,0xa5,0x20,0x00,0x00,0x00	# mulx	8*4($nptr),%rbx,%r12
3385	 mov	%rdx,%rax
3386	 mov	%r8,%rdx
3387	adcx	%rbx,%r11
3388	adox	%r13,%r12
3389
3390	 mulx	32+8(%rsp),%rbx,%rdx	# %rdx discarded
3391	 mov	%rax,%rdx
3392	 mov	%rax,64+48+8(%rsp,%rcx,8)	# put aside n0*a[i]
3393
3394	mulx	8*5($nptr),%rax,%r13
3395	adcx	%rax,%r12
3396	adox	%r14,%r13
3397
3398	mulx	8*6($nptr),%rax,%r14
3399	adcx	%rax,%r13
3400	adox	%r15,%r14
3401
3402	mulx	8*7($nptr),%rax,%r15
3403	 mov	%rbx,%rdx
3404	adcx	%rax,%r14
3405	adox	$carry,%r15		# $carry is 0
3406	adcx	$carry,%r15		# cf=0
3407
3408	.byte	0x67,0x67,0x67
3409	inc	%rcx			# of=0
3410	jnz	.Lsqrx8x_reduce
3411
3412	mov	$carry,%rax		# xor	%rax,%rax
3413	cmp	0+8(%rsp),$nptr		# end of n[]?
3414	jae	.Lsqrx8x_no_tail
3415
3416	mov	48+8(%rsp),%rdx		# pull n0*a[0]
3417	add	8*0($tptr),%r8
3418	lea	8*8($nptr),$nptr
3419	mov	\$-8,%rcx
3420	adcx	8*1($tptr),%r9
3421	adcx	8*2($tptr),%r10
3422	adc	8*3($tptr),%r11
3423	adc	8*4($tptr),%r12
3424	adc	8*5($tptr),%r13
3425	adc	8*6($tptr),%r14
3426	adc	8*7($tptr),%r15
3427	lea	8*8($tptr),$tptr
3428	sbb	%rax,%rax		# top carry
3429
3430	xor	$carry,$carry		# of=0, cf=0
3431	mov	%rax,16+8(%rsp)
3432	jmp	.Lsqrx8x_tail
3433
3434.align	32
3435.Lsqrx8x_tail:
3436	mov	%r8,%rbx
3437	mulx	8*0($nptr),%rax,%r8
3438	adcx	%rax,%rbx
3439	adox	%r9,%r8
3440
3441	mulx	8*1($nptr),%rax,%r9
3442	adcx	%rax,%r8
3443	adox	%r10,%r9
3444
3445	mulx	8*2($nptr),%rax,%r10
3446	adcx	%rax,%r9
3447	adox	%r11,%r10
3448
3449	mulx	8*3($nptr),%rax,%r11
3450	adcx	%rax,%r10
3451	adox	%r12,%r11
3452
3453	.byte	0xc4,0x62,0xfb,0xf6,0xa5,0x20,0x00,0x00,0x00	# mulx	8*4($nptr),%rax,%r12
3454	adcx	%rax,%r11
3455	adox	%r13,%r12
3456
3457	mulx	8*5($nptr),%rax,%r13
3458	adcx	%rax,%r12
3459	adox	%r14,%r13
3460
3461	mulx	8*6($nptr),%rax,%r14
3462	adcx	%rax,%r13
3463	adox	%r15,%r14
3464
3465	mulx	8*7($nptr),%rax,%r15
3466	 mov	72+48+8(%rsp,%rcx,8),%rdx	# pull n0*a[i]
3467	adcx	%rax,%r14
3468	adox	$carry,%r15
3469	 mov	%rbx,($tptr,%rcx,8)	# save result
3470	 mov	%r8,%rbx
3471	adcx	$carry,%r15		# cf=0
3472
3473	inc	%rcx			# of=0
3474	jnz	.Lsqrx8x_tail
3475
3476	cmp	0+8(%rsp),$nptr		# end of n[]?
3477	jae	.Lsqrx8x_tail_done	# break out of loop
3478
3479	sub	16+8(%rsp),$carry	# mov 16(%rsp),%cf
3480	 mov	48+8(%rsp),%rdx		# pull n0*a[0]
3481	 lea	8*8($nptr),$nptr
3482	adc	8*0($tptr),%r8
3483	adc	8*1($tptr),%r9
3484	adc	8*2($tptr),%r10
3485	adc	8*3($tptr),%r11
3486	adc	8*4($tptr),%r12
3487	adc	8*5($tptr),%r13
3488	adc	8*6($tptr),%r14
3489	adc	8*7($tptr),%r15
3490	lea	8*8($tptr),$tptr
3491	sbb	%rax,%rax
3492	sub	\$8,%rcx		# mov	\$-8,%rcx
3493
3494	xor	$carry,$carry		# of=0, cf=0
3495	mov	%rax,16+8(%rsp)
3496	jmp	.Lsqrx8x_tail
3497
3498.align	32
3499.Lsqrx8x_tail_done:
3500	xor	%rax,%rax
3501	add	24+8(%rsp),%r8		# can this overflow?
3502	adc	\$0,%r9
3503	adc	\$0,%r10
3504	adc	\$0,%r11
3505	adc	\$0,%r12
3506	adc	\$0,%r13
3507	adc	\$0,%r14
3508	adc	\$0,%r15
3509	adc	\$0,%rax
3510
3511	sub	16+8(%rsp),$carry	# mov 16(%rsp),%cf
3512.Lsqrx8x_no_tail:			# %cf is 0 if jumped here
3513	adc	8*0($tptr),%r8
3514	 movq	%xmm3,%rcx
3515	adc	8*1($tptr),%r9
3516	 mov	8*7($nptr),$carry
3517	 movq	%xmm2,$nptr		# restore $nptr
3518	adc	8*2($tptr),%r10
3519	adc	8*3($tptr),%r11
3520	adc	8*4($tptr),%r12
3521	adc	8*5($tptr),%r13
3522	adc	8*6($tptr),%r14
3523	adc	8*7($tptr),%r15
3524	adc	\$0,%rax		# top-most carry
3525
3526	mov	32+8(%rsp),%rbx		# n0
3527	mov	8*8($tptr,%rcx),%rdx	# modulo-scheduled "%r8"
3528
3529	mov	%r8,8*0($tptr)		# store top 512 bits
3530	 lea	8*8($tptr),%r8		# borrow %r8
3531	mov	%r9,8*1($tptr)
3532	mov	%r10,8*2($tptr)
3533	mov	%r11,8*3($tptr)
3534	mov	%r12,8*4($tptr)
3535	mov	%r13,8*5($tptr)
3536	mov	%r14,8*6($tptr)
3537	mov	%r15,8*7($tptr)
3538
3539	lea	8*8($tptr,%rcx),$tptr	# start of current t[] window
3540	cmp	8+8(%rsp),%r8		# end of t[]?
3541	jb	.Lsqrx8x_reduction_loop
3542	ret
3543.cfi_endproc
3544.size	bn_sqrx8x_internal,.-bn_sqrx8x_internal
3545___
3546}
3547##############################################################
3548# Post-condition, 4x unrolled
3549#
3550{
3551my ($rptr,$nptr)=("%rdx","%rbp");
3552$code.=<<___;
3553.align	32
3554.type	__bn_postx4x_internal,\@abi-omnipotent
3555__bn_postx4x_internal:
3556.cfi_startproc
3557	mov	8*0($nptr),%r12
3558	mov	%rcx,%r10		# -$num
3559	mov	%rcx,%r9		# -$num
3560	neg	%rax
3561	sar	\$3+2,%rcx
3562	#lea	48+8(%rsp,%r9),$tptr
3563	movq	%xmm1,$rptr		# restore $rptr
3564	movq	%xmm1,$aptr		# prepare for back-to-back call
3565	dec	%r12			# so that after 'not' we get -n[0]
3566	mov	8*1($nptr),%r13
3567	xor	%r8,%r8
3568	mov	8*2($nptr),%r14
3569	mov	8*3($nptr),%r15
3570	jmp	.Lsqrx4x_sub_entry
3571
3572.align	16
3573.Lsqrx4x_sub:
3574	mov	8*0($nptr),%r12
3575	mov	8*1($nptr),%r13
3576	mov	8*2($nptr),%r14
3577	mov	8*3($nptr),%r15
3578.Lsqrx4x_sub_entry:
3579	andn	%rax,%r12,%r12
3580	lea	8*4($nptr),$nptr
3581	andn	%rax,%r13,%r13
3582	andn	%rax,%r14,%r14
3583	andn	%rax,%r15,%r15
3584
3585	neg	%r8			# mov %r8,%cf
3586	adc	8*0($tptr),%r12
3587	adc	8*1($tptr),%r13
3588	adc	8*2($tptr),%r14
3589	adc	8*3($tptr),%r15
3590	mov	%r12,8*0($rptr)
3591	lea	8*4($tptr),$tptr
3592	mov	%r13,8*1($rptr)
3593	sbb	%r8,%r8			# mov %cf,%r8
3594	mov	%r14,8*2($rptr)
3595	mov	%r15,8*3($rptr)
3596	lea	8*4($rptr),$rptr
3597
3598	inc	%rcx
3599	jnz	.Lsqrx4x_sub
3600
3601	neg	%r9			# restore $num
3602
3603	ret
3604.cfi_endproc
3605.size	__bn_postx4x_internal,.-__bn_postx4x_internal
3606___
3607}
3608}}}
3609{
3610my ($inp,$num,$tbl,$idx)=$win64?("%rcx","%edx","%r8", "%r9d") : # Win64 order
3611				("%rdi","%esi","%rdx","%ecx");  # Unix order
3612my $out=$inp;
3613my $STRIDE=2**5*8;
3614my $N=$STRIDE/4;
3615
3616$code.=<<___;
3617.globl	bn_scatter5
3618.type	bn_scatter5,\@abi-omnipotent
3619.align	16
3620bn_scatter5:
3621.cfi_startproc
3622	cmp	\$0, $num
3623	jz	.Lscatter_epilogue
3624	lea	($tbl,$idx,8),$tbl
3625.Lscatter:
3626	mov	($inp),%rax
3627	lea	8($inp),$inp
3628	mov	%rax,($tbl)
3629	lea	32*8($tbl),$tbl
3630	sub	\$1,$num
3631	jnz	.Lscatter
3632.Lscatter_epilogue:
3633	ret
3634.cfi_endproc
3635.size	bn_scatter5,.-bn_scatter5
3636
3637.globl	bn_gather5
3638.type	bn_gather5,\@abi-omnipotent
3639.align	32
3640bn_gather5:
3641.cfi_startproc
3642.LSEH_begin_bn_gather5:			# Win64 thing, but harmless in other cases
3643	# I can't trust assembler to use specific encoding:-(
3644	.byte	0x4c,0x8d,0x14,0x24			#lea    (%rsp),%r10
3645.cfi_def_cfa_register	%r10
3646	.byte	0x48,0x81,0xec,0x08,0x01,0x00,0x00	#sub	$0x108,%rsp
3647	lea	.Linc(%rip),%rax
3648	and	\$-16,%rsp		# shouldn't be formally required
3649
3650	movd	$idx,%xmm5
3651	movdqa	0(%rax),%xmm0		# 00000001000000010000000000000000
3652	movdqa	16(%rax),%xmm1		# 00000002000000020000000200000002
3653	lea	128($tbl),%r11		# size optimization
3654	lea	128(%rsp),%rax		# size optimization
3655
3656	pshufd	\$0,%xmm5,%xmm5		# broadcast $idx
3657	movdqa	%xmm1,%xmm4
3658	movdqa	%xmm1,%xmm2
3659___
3660########################################################################
3661# calculate mask by comparing 0..31 to $idx and save result to stack
3662#
3663for($i=0;$i<$STRIDE/16;$i+=4) {
3664$code.=<<___;
3665	paddd	%xmm0,%xmm1
3666	pcmpeqd	%xmm5,%xmm0		# compare to 1,0
3667___
3668$code.=<<___	if ($i);
3669	movdqa	%xmm3,`16*($i-1)-128`(%rax)
3670___
3671$code.=<<___;
3672	movdqa	%xmm4,%xmm3
3673
3674	paddd	%xmm1,%xmm2
3675	pcmpeqd	%xmm5,%xmm1		# compare to 3,2
3676	movdqa	%xmm0,`16*($i+0)-128`(%rax)
3677	movdqa	%xmm4,%xmm0
3678
3679	paddd	%xmm2,%xmm3
3680	pcmpeqd	%xmm5,%xmm2		# compare to 5,4
3681	movdqa	%xmm1,`16*($i+1)-128`(%rax)
3682	movdqa	%xmm4,%xmm1
3683
3684	paddd	%xmm3,%xmm0
3685	pcmpeqd	%xmm5,%xmm3		# compare to 7,6
3686	movdqa	%xmm2,`16*($i+2)-128`(%rax)
3687	movdqa	%xmm4,%xmm2
3688___
3689}
3690$code.=<<___;
3691	movdqa	%xmm3,`16*($i-1)-128`(%rax)
3692	jmp	.Lgather
3693
3694.align	32
3695.Lgather:
3696	pxor	%xmm4,%xmm4
3697	pxor	%xmm5,%xmm5
3698___
3699for($i=0;$i<$STRIDE/16;$i+=4) {
3700$code.=<<___;
3701	movdqa	`16*($i+0)-128`(%r11),%xmm0
3702	movdqa	`16*($i+1)-128`(%r11),%xmm1
3703	movdqa	`16*($i+2)-128`(%r11),%xmm2
3704	pand	`16*($i+0)-128`(%rax),%xmm0
3705	movdqa	`16*($i+3)-128`(%r11),%xmm3
3706	pand	`16*($i+1)-128`(%rax),%xmm1
3707	por	%xmm0,%xmm4
3708	pand	`16*($i+2)-128`(%rax),%xmm2
3709	por	%xmm1,%xmm5
3710	pand	`16*($i+3)-128`(%rax),%xmm3
3711	por	%xmm2,%xmm4
3712	por	%xmm3,%xmm5
3713___
3714}
3715$code.=<<___;
3716	por	%xmm5,%xmm4
3717	lea	$STRIDE(%r11),%r11
3718	pshufd	\$0x4e,%xmm4,%xmm0
3719	por	%xmm4,%xmm0
3720	movq	%xmm0,($out)		# m0=bp[0]
3721	lea	8($out),$out
3722	sub	\$1,$num
3723	jnz	.Lgather
3724
3725	lea	(%r10),%rsp
3726.cfi_def_cfa_register	%rsp
3727	ret
3728.LSEH_end_bn_gather5:
3729.cfi_endproc
3730.size	bn_gather5,.-bn_gather5
3731___
3732}
3733$code.=<<___;
3734.align	64
3735.Linc:
3736	.long	0,0, 1,1
3737	.long	2,2, 2,2
3738.asciz	"Montgomery Multiplication with scatter/gather for x86_64, CRYPTOGAMS by <appro\@openssl.org>"
3739___
3740
3741# EXCEPTION_DISPOSITION handler (EXCEPTION_RECORD *rec,ULONG64 frame,
3742#		CONTEXT *context,DISPATCHER_CONTEXT *disp)
3743if ($win64) {
3744$rec="%rcx";
3745$frame="%rdx";
3746$context="%r8";
3747$disp="%r9";
3748
3749$code.=<<___;
3750.extern	__imp_RtlVirtualUnwind
3751.type	mul_handler,\@abi-omnipotent
3752.align	16
3753mul_handler:
3754	push	%rsi
3755	push	%rdi
3756	push	%rbx
3757	push	%rbp
3758	push	%r12
3759	push	%r13
3760	push	%r14
3761	push	%r15
3762	pushfq
3763	sub	\$64,%rsp
3764
3765	mov	120($context),%rax	# pull context->Rax
3766	mov	248($context),%rbx	# pull context->Rip
3767
3768	mov	8($disp),%rsi		# disp->ImageBase
3769	mov	56($disp),%r11		# disp->HandlerData
3770
3771	mov	0(%r11),%r10d		# HandlerData[0]
3772	lea	(%rsi,%r10),%r10	# end of prologue label
3773	cmp	%r10,%rbx		# context->Rip<end of prologue label
3774	jb	.Lcommon_seh_tail
3775
3776	mov	4(%r11),%r10d		# HandlerData[1]
3777	lea	(%rsi,%r10),%r10	# beginning of body label
3778	cmp	%r10,%rbx		# context->Rip<body label
3779	jb	.Lcommon_pop_regs
3780
3781	mov	152($context),%rax	# pull context->Rsp
3782
3783	mov	8(%r11),%r10d		# HandlerData[2]
3784	lea	(%rsi,%r10),%r10	# epilogue label
3785	cmp	%r10,%rbx		# context->Rip>=epilogue label
3786	jae	.Lcommon_seh_tail
3787
3788	lea	.Lmul_epilogue(%rip),%r10
3789	cmp	%r10,%rbx
3790	ja	.Lbody_40
3791
3792	mov	192($context),%r10	# pull $num
3793	mov	8(%rax,%r10,8),%rax	# pull saved stack pointer
3794
3795	jmp	.Lcommon_pop_regs
3796
3797.Lbody_40:
3798	mov	40(%rax),%rax		# pull saved stack pointer
3799.Lcommon_pop_regs:
3800	mov	-8(%rax),%rbx
3801	mov	-16(%rax),%rbp
3802	mov	-24(%rax),%r12
3803	mov	-32(%rax),%r13
3804	mov	-40(%rax),%r14
3805	mov	-48(%rax),%r15
3806	mov	%rbx,144($context)	# restore context->Rbx
3807	mov	%rbp,160($context)	# restore context->Rbp
3808	mov	%r12,216($context)	# restore context->R12
3809	mov	%r13,224($context)	# restore context->R13
3810	mov	%r14,232($context)	# restore context->R14
3811	mov	%r15,240($context)	# restore context->R15
3812
3813.Lcommon_seh_tail:
3814	mov	8(%rax),%rdi
3815	mov	16(%rax),%rsi
3816	mov	%rax,152($context)	# restore context->Rsp
3817	mov	%rsi,168($context)	# restore context->Rsi
3818	mov	%rdi,176($context)	# restore context->Rdi
3819
3820	mov	40($disp),%rdi		# disp->ContextRecord
3821	mov	$context,%rsi		# context
3822	mov	\$154,%ecx		# sizeof(CONTEXT)
3823	.long	0xa548f3fc		# cld; rep movsq
3824
3825	mov	$disp,%rsi
3826	xor	%rcx,%rcx		# arg1, UNW_FLAG_NHANDLER
3827	mov	8(%rsi),%rdx		# arg2, disp->ImageBase
3828	mov	0(%rsi),%r8		# arg3, disp->ControlPc
3829	mov	16(%rsi),%r9		# arg4, disp->FunctionEntry
3830	mov	40(%rsi),%r10		# disp->ContextRecord
3831	lea	56(%rsi),%r11		# &disp->HandlerData
3832	lea	24(%rsi),%r12		# &disp->EstablisherFrame
3833	mov	%r10,32(%rsp)		# arg5
3834	mov	%r11,40(%rsp)		# arg6
3835	mov	%r12,48(%rsp)		# arg7
3836	mov	%rcx,56(%rsp)		# arg8, (NULL)
3837	call	*__imp_RtlVirtualUnwind(%rip)
3838
3839	mov	\$1,%eax		# ExceptionContinueSearch
3840	add	\$64,%rsp
3841	popfq
3842	pop	%r15
3843	pop	%r14
3844	pop	%r13
3845	pop	%r12
3846	pop	%rbp
3847	pop	%rbx
3848	pop	%rdi
3849	pop	%rsi
3850	ret
3851.size	mul_handler,.-mul_handler
3852
3853.section	.pdata
3854.align	4
3855	.rva	.LSEH_begin_bn_mul_mont_gather5
3856	.rva	.LSEH_end_bn_mul_mont_gather5
3857	.rva	.LSEH_info_bn_mul_mont_gather5
3858
3859	.rva	.LSEH_begin_bn_mul4x_mont_gather5
3860	.rva	.LSEH_end_bn_mul4x_mont_gather5
3861	.rva	.LSEH_info_bn_mul4x_mont_gather5
3862
3863	.rva	.LSEH_begin_bn_power5
3864	.rva	.LSEH_end_bn_power5
3865	.rva	.LSEH_info_bn_power5
3866
3867	.rva	.LSEH_begin_bn_from_mont8x
3868	.rva	.LSEH_end_bn_from_mont8x
3869	.rva	.LSEH_info_bn_from_mont8x
3870___
3871$code.=<<___ if ($addx);
3872	.rva	.LSEH_begin_bn_mulx4x_mont_gather5
3873	.rva	.LSEH_end_bn_mulx4x_mont_gather5
3874	.rva	.LSEH_info_bn_mulx4x_mont_gather5
3875
3876	.rva	.LSEH_begin_bn_powerx5
3877	.rva	.LSEH_end_bn_powerx5
3878	.rva	.LSEH_info_bn_powerx5
3879___
3880$code.=<<___;
3881	.rva	.LSEH_begin_bn_gather5
3882	.rva	.LSEH_end_bn_gather5
3883	.rva	.LSEH_info_bn_gather5
3884
3885.section	.xdata
3886.align	8
3887.LSEH_info_bn_mul_mont_gather5:
3888	.byte	9,0,0,0
3889	.rva	mul_handler
3890	.rva	.Lmul_body,.Lmul_body,.Lmul_epilogue		# HandlerData[]
3891.align	8
3892.LSEH_info_bn_mul4x_mont_gather5:
3893	.byte	9,0,0,0
3894	.rva	mul_handler
3895	.rva	.Lmul4x_prologue,.Lmul4x_body,.Lmul4x_epilogue		# HandlerData[]
3896.align	8
3897.LSEH_info_bn_power5:
3898	.byte	9,0,0,0
3899	.rva	mul_handler
3900	.rva	.Lpower5_prologue,.Lpower5_body,.Lpower5_epilogue	# HandlerData[]
3901.align	8
3902.LSEH_info_bn_from_mont8x:
3903	.byte	9,0,0,0
3904	.rva	mul_handler
3905	.rva	.Lfrom_prologue,.Lfrom_body,.Lfrom_epilogue		# HandlerData[]
3906___
3907$code.=<<___ if ($addx);
3908.align	8
3909.LSEH_info_bn_mulx4x_mont_gather5:
3910	.byte	9,0,0,0
3911	.rva	mul_handler
3912	.rva	.Lmulx4x_prologue,.Lmulx4x_body,.Lmulx4x_epilogue	# HandlerData[]
3913.align	8
3914.LSEH_info_bn_powerx5:
3915	.byte	9,0,0,0
3916	.rva	mul_handler
3917	.rva	.Lpowerx5_prologue,.Lpowerx5_body,.Lpowerx5_epilogue	# HandlerData[]
3918___
3919$code.=<<___;
3920.align	8
3921.LSEH_info_bn_gather5:
3922	.byte	0x01,0x0b,0x03,0x0a
3923	.byte	0x0b,0x01,0x21,0x00	# sub	rsp,0x108
3924	.byte	0x04,0xa3,0x00,0x00	# lea	r10,(rsp)
3925.align	8
3926___
3927}
3928
3929$code =~ s/\`([^\`]*)\`/eval($1)/gem;
3930
3931print $code;
3932close STDOUT or die "error closing STDOUT";
3933