crypto/bn/x86_64-mont5.pl: constant-time gather procedure.

At the same time remove miniscule bias in final subtraction.
Performance penalty varies from platform to platform, and even with
key length. For rsa2048 sign it was observed to be 4% for Sandy
Bridge and 7% on Broadwell.

CVE-2016-0702

Reviewed-by: Richard Levitte <levitte@openssl.org>
Reviewed-by: Rich Salz <rsalz@openssl.org>
(cherry picked from master)

3 files changed, 678 insertions, 558 deletions

diff --git a/crypto/bn/asm/x86_64-mont.pl b/crypto/bn/asm/x86_64-mont.pl
index e82e451388..69232cbeb6 100755
--- a/crypto/bn/asm/x86_64-mont.pl
+++ b/crypto/bn/asm/x86_64-mont.pl
@@ -775,20 +775,20 @@ bn_sqr8x_mont:
 	# 4096. this is done to allow memory disambiguation logic
 	# do its job.
 	#
-	lea	-64(%rsp,$num,4),%r11
+	lea	-64(%rsp,$num,2),%r11
 	mov	($n0),$n0		# *n0
 	sub	$aptr,%r11
 	and	\$4095,%r11
 	cmp	%r11,%r10
 	jb	.Lsqr8x_sp_alt
 	sub	%r11,%rsp		# align with $aptr
-	lea	-64(%rsp,$num,4),%rsp	# alloca(frame+4*$num)
+	lea	-64(%rsp,$num,2),%rsp	# alloca(frame+2*$num)
 	jmp	.Lsqr8x_sp_done
 
 .align	32
 .Lsqr8x_sp_alt:
-	lea	4096-64(,$num,4),%r10	# 4096-frame-4*$num
-	lea	-64(%rsp,$num,4),%rsp	# alloca(frame+4*$num)
+	lea	4096-64(,$num,2),%r10	# 4096-frame-2*$num
+	lea	-64(%rsp,$num,2),%rsp	# alloca(frame+2*$num)
 	sub	%r10,%r11
 	mov	\$0,%r10
 	cmovc	%r10,%r11
@@ -798,37 +798,17 @@ bn_sqr8x_mont:
 	mov	$num,%r10	
 	neg	$num
 
-	lea	64(%rsp,$num,2),%r11	# copy of modulus
 	mov	$n0,  32(%rsp)
 	mov	%rax, 40(%rsp)		# save original %rsp
 .Lsqr8x_body:
 
-	mov	$num,$i
-	movq	%r11, %xmm2		# save pointer to modulus copy
-	shr	\$3+2,$i
-	mov	OPENSSL_ia32cap_P+8(%rip),%eax
-	jmp	.Lsqr8x_copy_n
-
-.align	32
-.Lsqr8x_copy_n:
-	movq	8*0($nptr),%xmm0
-	movq	8*1($nptr),%xmm1
-	movq	8*2($nptr),%xmm3
-	movq	8*3($nptr),%xmm4
-	lea	8*4($nptr),$nptr
-	movdqa	%xmm0,16*0(%r11)
-	movdqa	%xmm1,16*1(%r11)
-	movdqa	%xmm3,16*2(%r11)
-	movdqa	%xmm4,16*3(%r11)
-	lea	16*4(%r11),%r11
-	dec	$i
-	jnz	.Lsqr8x_copy_n
-
+	movq	$nptr, %xmm2		# save pointer to modulus
 	pxor	%xmm0,%xmm0
 	movq	$rptr,%xmm1		# save $rptr
 	movq	%r10, %xmm3		# -$num
 ___
 $code.=<<___ if ($addx);
+	mov	OPENSSL_ia32cap_P+8(%rip),%eax
 	and	\$0x80100,%eax
 	cmp	\$0x80100,%eax
 	jne	.Lsqr8x_nox
@@ -837,7 +817,6 @@ $code.=<<___ if ($addx);
 
 	pxor	%xmm0,%xmm0
 	lea	48(%rsp),%rax
-	lea	64(%rsp,$num,2),%rdx
 	shr	\$3+2,$num
 	mov	40(%rsp),%rsi		# restore %rsp
 	jmp	.Lsqr8x_zero
@@ -850,7 +829,6 @@ $code.=<<___;
 
 	pxor	%xmm0,%xmm0
 	lea	48(%rsp),%rax
-	lea	64(%rsp,$num,2),%rdx
 	shr	\$3+2,$num
 	mov	40(%rsp),%rsi		# restore %rsp
 	jmp	.Lsqr8x_zero
@@ -862,11 +840,6 @@ $code.=<<___;
 	movdqa	%xmm0,16*2(%rax)
 	movdqa	%xmm0,16*3(%rax)
 	lea	16*4(%rax),%rax
-	movdqa	%xmm0,16*0(%rdx)	# wipe n
-	movdqa	%xmm0,16*1(%rdx)
-	movdqa	%xmm0,16*2(%rdx)
-	movdqa	%xmm0,16*3(%rdx)
-	lea	16*4(%rdx),%rdx
 	dec	$num
 	jnz	.Lsqr8x_zero
 
diff --git a/crypto/bn/asm/x86_64-mont5.pl b/crypto/bn/asm/x86_64-mont5.pl
index 292409c4ff..be91ef09d5 100755
--- a/crypto/bn/asm/x86_64-mont5.pl
+++ b/crypto/bn/asm/x86_64-mont5.pl
@@ -99,7 +99,8 @@ $code.=<<___;
 .Lmul_enter:
 	mov	${num}d,${num}d
 	mov	%rsp,%rax
-	mov	`($win64?56:8)`(%rsp),%r10d	# load 7th argument
+	movd	`($win64?56:8)`(%rsp),%xmm0	# load 7th argument
+	lea	.Lmagic_masks(%rip),%r10
 	push	%rbx
 	push	%rbp
 	push	%r12
@@ -108,9 +109,10 @@ $code.=<<___;
 	push	%r15
 ___
 $code.=<<___ if ($win64);
-	lea	-0x28(%rsp),%rsp
+	lea	-0x38(%rsp),%rsp
 	movaps	%xmm6,(%rsp)
 	movaps	%xmm7,0x10(%rsp)
+	movaps	%xmm8,0x20(%rsp)
 ___
 $code.=<<___;
 	lea	2($num),%r11
@@ -120,36 +122,69 @@ $code.=<<___;
 
 	mov	%rax,8(%rsp,$num,8)	# tp[num+1]=%rsp
 .Lmul_body:
-	mov	$bp,%r12		# reassign $bp
+	lea	128($bp),%r12		# reassign $bp (+size optimization)
 ___
 		$bp="%r12";
 		$STRIDE=2**5*8;		# 5 is "window size"
 		$N=$STRIDE/4;		# should match cache line size
 $code.=<<___;
-	mov	%r10,%r11
-	shr	\$`log($N/8)/log(2)`,%r10
-	and	\$`$N/8-1`,%r11
-	not	%r10
-	lea	.Lmagic_masks(%rip),%rax
-	and	\$`2**5/($N/8)-1`,%r10	# 5 is "window size"
-	lea	96($bp,%r11,8),$bp	# pointer within 1st cache line
-	movq	0(%rax,%r10,8),%xmm4	# set of masks denoting which
-	movq	8(%rax,%r10,8),%xmm5	# cache line contains element
-	movq	16(%rax,%r10,8),%xmm6	# denoted by 7th argument
-	movq	24(%rax,%r10,8),%xmm7
-
-	movq	`0*$STRIDE/4-96`($bp),%xmm0
-	movq	`1*$STRIDE/4-96`($bp),%xmm1
+	################################################################
+	# calculate mask: one of %xmm4..7 will contain 0xff..00 or
+	# 0x00..ff denoting which half of a quarter of corresponding
+	# cache line is significant.
+	#
+	movq	56(%r10),%xmm1		# 0b11001
+	movq	%xmm0,%rdx
+	pand	%xmm1,%xmm0
+	movdqa	0(%r10),%xmm4
+	pshufd	\$0,%xmm0,%xmm0		# broadcast masked index
+	movdqa	16(%r10),%xmm5
+	movdqa	32(%r10),%xmm6
+	pcmpeqd	%xmm0,%xmm4
+	movdqa	48(%r10),%xmm7
+	pcmpeqd	%xmm0,%xmm5
+	pcmpeqd	%xmm0,%xmm6
+	pcmpeqd	%xmm0,%xmm7
+
+	################################################################
+	# calculate index in 1st cache line, but in such manner that
+	# if target data is in another cache line, then relevant
+	# "rotating" reference would land on it...
+	#
+	shr	\$1,%rdx		# idx/=2
+	mov	%rdx,$j
+	shr	\$2,%rdx
+	sub	%rdx,$j
+	and	\$3,$j			# (idx-idx/4)%4
+	shl	\$4,$j			# scale for xmm references
+
+	################################################################
+	# "rotating" references are touching different cache banks in
+	# different cache lines, so that not only all cache lines are
+	# referred in each iteration, but even all cache banks.
+	#
+	lea	16($j),$m0
+	lea	32($j),$m1
+	and	\$63,$m0
+	lea	48($j),%rdx
+	and	\$63,$m1
+	and	\$63,%rdx
+	movdqa	`0*$STRIDE/4-128`($bp,$j),%xmm0
+	movdqa	`1*$STRIDE/4-128`($bp,$m0),%xmm1
+	movdqa	`2*$STRIDE/4-128`($bp,$m1),%xmm2
+	movdqa	`3*$STRIDE/4-128`($bp,%rdx),%xmm3
 	pand	%xmm4,%xmm0
-	movq	`2*$STRIDE/4-96`($bp),%xmm2
 	pand	%xmm5,%xmm1
-	movq	`3*$STRIDE/4-96`($bp),%xmm3
 	pand	%xmm6,%xmm2
 	por	%xmm1,%xmm0
 	pand	%xmm7,%xmm3
 	por	%xmm2,%xmm0
 	lea	$STRIDE($bp),$bp
 	por	%xmm3,%xmm0
+	movq	$j,%xmm8
+
+	pshufd	\$0x4e,%xmm0,%xmm1
+	por	%xmm1,%xmm0		# merge upper and lower halves
 
 	movq	%xmm0,$m0		# m0=bp[0]
 
@@ -159,29 +194,14 @@ $code.=<<___;
 	xor	$i,$i			# i=0
 	xor	$j,$j			# j=0
 
-	movq	`0*$STRIDE/4-96`($bp),%xmm0
-	movq	`1*$STRIDE/4-96`($bp),%xmm1
-	pand	%xmm4,%xmm0
-	movq	`2*$STRIDE/4-96`($bp),%xmm2
-	pand	%xmm5,%xmm1
-
 	mov	$n0,$m1
 	mulq	$m0			# ap[0]*bp[0]
 	mov	%rax,$lo0
 	mov	($np),%rax
 
-	movq	`3*$STRIDE/4-96`($bp),%xmm3
-	pand	%xmm6,%xmm2
-	por	%xmm1,%xmm0
-	pand	%xmm7,%xmm3
-
 	imulq	$lo0,$m1		# "tp[0]"*n0
 	mov	%rdx,$hi0
 
-	por	%xmm2,%xmm0
-	lea	$STRIDE($bp),$bp
-	por	%xmm3,%xmm0
-
 	mulq	$m1			# np[0]*m1
 	add	%rax,$lo0		# discarded
 	mov	8($ap),%rax
@@ -214,14 +234,13 @@ $code.=<<___;
 	cmp	$num,$j
 	jne	.L1st
 
-	movq	%xmm0,$m0		# bp[1]
+	movq	%xmm8,$j
 
 	add	%rax,$hi1
-	mov	($ap),%rax		# ap[0]
 	adc	\$0,%rdx
 	add	$hi0,$hi1		# np[j]*m1+ap[j]*bp[0]
 	adc	\$0,%rdx
-	mov	$hi1,-16(%rsp,$j,8)	# tp[j-1]
+	mov	$hi1,-16(%rsp,$num,8)	# tp[j-1]
 	mov	%rdx,$hi1
 	mov	$lo0,$hi0
 
@@ -235,33 +254,43 @@ $code.=<<___;
 	jmp	.Louter
 .align	16
 .Louter:
+	lea	16($j),$m0
+	lea	32($j),$m1
+	and	\$63,$m0
+	lea	48($j),%rdx
+	and	\$63,$m1
+	and	\$63,%rdx
+	movdqa	`0*$STRIDE/4-128`($bp,$j),%xmm0
+	movdqa	`1*$STRIDE/4-128`($bp,$m0),%xmm1
+	movdqa	`2*$STRIDE/4-128`($bp,$m1),%xmm2
+	movdqa	`3*$STRIDE/4-128`($bp,%rdx),%xmm3
+	pand	%xmm4,%xmm0
+	pand	%xmm5,%xmm1
+	pand	%xmm6,%xmm2
+	por	%xmm1,%xmm0
+	pand	%xmm7,%xmm3
+	por	%xmm2,%xmm0
+	lea	$STRIDE($bp),$bp
+	por	%xmm3,%xmm0
+
+	pshufd	\$0x4e,%xmm0,%xmm1
+	por	%xmm1,%xmm0		# merge upper and lower halves
+
+	mov	($ap),%rax		# ap[0]
+	movq	%xmm0,$m0		# m0=bp[i]
+
 	xor	$j,$j			# j=0
 	mov	$n0,$m1
 	mov	(%rsp),$lo0
 
-	movq	`0*$STRIDE/4-96`($bp),%xmm0
-	movq	`1*$STRIDE/4-96`($bp),%xmm1
-	pand	%xmm4,%xmm0
-	movq	`2*$STRIDE/4-96`($bp),%xmm2
-	pand	%xmm5,%xmm1
-
 	mulq	$m0			# ap[0]*bp[i]
 	add	%rax,$lo0		# ap[0]*bp[i]+tp[0]
 	mov	($np),%rax
 	adc	\$0,%rdx
 
-	movq	`3*$STRIDE/4-96`($bp),%xmm3
-	pand	%xmm6,%xmm2
-	por	%xmm1,%xmm0
-	pand	%xmm7,%xmm3
-
 	imulq	$lo0,$m1		# tp[0]*n0
 	mov	%rdx,$hi0
 
-	por	%xmm2,%xmm0
-	lea	$STRIDE($bp),$bp
-	por	%xmm3,%xmm0
-
 	mulq	$m1			# np[0]*m1
 	add	%rax,$lo0		# discarded
 	mov	8($ap),%rax
@@ -297,15 +326,14 @@ $code.=<<___;
 	cmp	$num,$j
 	jne	.Linner
 
-	movq	%xmm0,$m0		# bp[i+1]
+	movq	%xmm8,$j
 
 	add	%rax,$hi1
-	mov	($ap),%rax		# ap[0]
 	adc	\$0,%rdx
 	add	$lo0,$hi1		# np[j]*m1+ap[j]*bp[i]+tp[j]
-	mov	(%rsp,$j,8),$lo0
+	mov	(%rsp,$num,8),$lo0
 	adc	\$0,%rdx
-	mov	$hi1,-16(%rsp,$j,8)	# tp[j-1]
+	mov	$hi1,-16(%rsp,$num,8)	# tp[j-1]
 	mov	%rdx,$hi1
 
 	xor	%rdx,%rdx
@@ -354,8 +382,9 @@ $code.=<<___;
 	mov	\$1,%rax
 ___
 $code.=<<___ if ($win64);
-	movaps	-88(%rsi),%xmm6
-	movaps	-72(%rsi),%xmm7
+	movaps	-104(%rsi),%xmm6
+	movaps	-88(%rsi),%xmm7
+	movaps	-72(%rsi),%xmm8
 ___
 $code.=<<___;
 	mov	-48(%rsi),%r15
@@ -379,8 +408,8 @@ bn_mul4x_mont_gather5:
 .Lmul4x_enter:
 ___
 $code.=<<___ if ($addx);
-	and	\$0x80100,%r11d
-	cmp	\$0x80100,%r11d
+	and	\$0x80108,%r11d
+	cmp	\$0x80108,%r11d		# check for AD*X+BMI2+BMI1
 	je	.Lmulx4x_enter
 ___
 $code.=<<___;
@@ -392,39 +421,34 @@ $code.=<<___;
 	push	%r13
 	push	%r14
 	push	%r15
-___
-$code.=<<___ if ($win64);
-	lea	-0x28(%rsp),%rsp
-	movaps	%xmm6,(%rsp)
-	movaps	%xmm7,0x10(%rsp)
-___
-$code.=<<___;
+
 	.byte	0x67
-	mov	${num}d,%r10d
-	shl	\$3,${num}d
-	shl	\$3+2,%r10d		# 4*$num
+	shl	\$3,${num}d		# convert $num to bytes
+	lea	($num,$num,2),%r10	# 3*$num in bytes
 	neg	$num			# -$num
 
 	##############################################################
-	# ensure that stack frame doesn't alias with $aptr+4*$num
-	# modulo 4096, which covers ret[num], am[num] and n[2*num]
-	# (see bn_exp.c). this is done to allow memory disambiguation
-	# logic do its magic. [excessive frame is allocated in order
-	# to allow bn_from_mont8x to clear it.]
+	# Ensure that stack frame doesn't alias with $rptr+3*$num
+	# modulo 4096, which covers ret[num], am[num] and n[num]
+	# (see bn_exp.c). This is done to allow memory disambiguation
+	# logic do its magic. [Extra [num] is allocated in order
+	# to align with bn_power5's frame, which is cleansed after
+	# completing exponentiation. Extra 256 bytes is for power mask
+	# calculated from 7th argument, the index.]
 	#
-	lea	-64(%rsp,$num,2),%r11
-	sub	$ap,%r11
+	lea	-320(%rsp,$num,2),%r11
+	sub	$rp,%r11
 	and	\$4095,%r11
 	cmp	%r11,%r10
 	jb	.Lmul4xsp_alt
-	sub	%r11,%rsp		# align with $ap
-	lea	-64(%rsp,$num,2),%rsp	# alloca(128+num*8)
+	sub	%r11,%rsp		# align with $rp
+	lea	-320(%rsp,$num,2),%rsp	# alloca(frame+2*num*8+256)
 	jmp	.Lmul4xsp_done
 
 .align	32
 .Lmul4xsp_alt:
-	lea	4096-64(,$num,2),%r10
-	lea	-64(%rsp,$num,2),%rsp	# alloca(128+num*8)
+	lea	4096-320(,$num,2),%r10
+	lea	-320(%rsp,$num,2),%rsp	# alloca(frame+2*num*8+256)
 	sub	%r10,%r11
 	mov	\$0,%r10
 	cmovc	%r10,%r11
@@ -440,12 +464,7 @@ $code.=<<___;
 
 	mov	40(%rsp),%rsi		# restore %rsp
 	mov	\$1,%rax
-___
-$code.=<<___ if ($win64);
-	movaps	-88(%rsi),%xmm6
-	movaps	-72(%rsi),%xmm7
-___
-$code.=<<___;
+
 	mov	-48(%rsi),%r15
 	mov	-40(%rsi),%r14
 	mov	-32(%rsi),%r13
@@ -460,9 +479,10 @@ $code.=<<___;
 .type	mul4x_internal,\@abi-omnipotent
 .align	32
 mul4x_internal:
-	shl	\$5,$num
-	mov	`($win64?56:8)`(%rax),%r10d	# load 7th argument
-	lea	256(%rdx,$num),%r13
+	shl	\$5,$num		# $num was in bytes
+	movd	`($win64?56:8)`(%rax),%xmm5	# load 7th argument, index
+	lea	.Linc(%rip),%rax
+	lea	128(%rdx,$num),%r13	# end of powers table (+size optimization)
 	shr	\$5,$num		# restore $num
 ___
 		$bp="%r12";
@@ -470,44 +490,92 @@ ___
 		$N=$STRIDE/4;		# should match cache line size
 		$tp=$i;
 $code.=<<___;
-	mov	%r10,%r11
-	shr	\$`log($N/8)/log(2)`,%r10
-	and	\$`$N/8-1`,%r11
-	not	%r10
-	lea	.Lmagic_masks(%rip),%rax
-	and	\$`2**5/($N/8)-1`,%r10	# 5 is "window size"
-	lea	96(%rdx,%r11,8),$bp	# pointer within 1st cache line
-	movq	0(%rax,%r10,8),%xmm4	# set of masks denoting which
-	movq	8(%rax,%r10,8),%xmm5	# cache line contains element
-	add	\$7,%r11
-	movq	16(%rax,%r10,8),%xmm6	# denoted by 7th argument
-	movq	24(%rax,%r10,8),%xmm7
-	and	\$7,%r11
-
-	movq	`0*$STRIDE/4-96`($bp),%xmm0
-	lea	$STRIDE($bp),$tp	# borrow $tp
-	movq	`1*$STRIDE/4-96`($bp),%xmm1
-	pand	%xmm4,%xmm0
-	movq	`2*$STRIDE/4-96`($bp),%xmm2
-	pand	%xmm5,%xmm1
-	movq	`3*$STRIDE/4-96`($bp),%xmm3
-	pand	%xmm6,%xmm2
-	.byte	0x67
-	por	%xmm1,%xmm0
-	movq	`0*$STRIDE/4-96`($tp),%xmm1
-	.byte	0x67
-	pand	%xmm7,%xmm3
-	.byte	0x67
-	por	%xmm2,%xmm0
-	movq	`1*$STRIDE/4-96`($tp),%xmm2
+	movdqa	0(%rax),%xmm0		# 00000001000000010000000000000000
+	movdqa	16(%rax),%xmm1		# 00000002000000020000000200000002
+	lea	88-112(%rsp,$num),%r10	# place the mask after tp[num+1] (+ICache optimization)
+	lea	128(%rdx),$bp		# size optimization
+
+	pshufd	\$0,%xmm5,%xmm5		# broadcast index
+	movdqa	%xmm1,%xmm4
+	.byte	0x67,0x67
+	movdqa	%xmm1,%xmm2
+___
+########################################################################
+# calculate mask by comparing 0..31 to index and save result to stack
+#
+$code.=<<___;
+	paddd	%xmm0,%xmm1
+	pcmpeqd	%xmm5,%xmm0		# compare to 1,0
 	.byte	0x67
-	pand	%xmm4,%xmm1
+	movdqa	%xmm4,%xmm3
+___
+for($i=0;$i<$STRIDE/16-4;$i+=4) {
+$code.=<<___;
+	paddd	%xmm1,%xmm2
+	pcmpeqd	%xmm5,%xmm1		# compare to 3,2
+	movdqa	%xmm0,`16*($i+0)+112`(%r10)
+	movdqa	%xmm4,%xmm0
+
+	paddd	%xmm2,%xmm3
+	pcmpeqd	%xmm5,%xmm2		# compare to 5,4
+	movdqa	%xmm1,`16*($i+1)+112`(%r10)
+	movdqa	%xmm4,%xmm1
+
+	paddd	%xmm3,%xmm0
+	pcmpeqd	%xmm5,%xmm3		# compare to 7,6
+	movdqa	%xmm2,`16*($i+2)+112`(%r10)
+	movdqa	%xmm4,%xmm2
+
+	paddd	%xmm0,%xmm1
+	pcmpeqd	%xmm5,%xmm0
+	movdqa	%xmm3,`16*($i+3)+112`(%r10)
+	movdqa	%xmm4,%xmm3
+___
+}
+$code.=<<___;				# last iteration can be optimized
+	paddd	%xmm1,%xmm2
+	pcmpeqd	%xmm5,%xmm1
+	movdqa	%xmm0,`16*($i+0)+112`(%r10)
+
+	paddd	%xmm2,%xmm3
 	.byte	0x67
-	por	%xmm3,%xmm0
-	movq	`2*$STRIDE/4-96`($tp),%xmm3
+	pcmpeqd	%xmm5,%xmm2
+	movdqa	%xmm1,`16*($i+1)+112`(%r10)
 
+	pcmpeqd	%xmm5,%xmm3
+	movdqa	%xmm2,`16*($i+2)+112`(%r10)
+	pand	`16*($i+0)-128`($bp),%xmm0	# while it's still in register
+
+	pand	`16*($i+1)-128`($bp),%xmm1
+	pand	`16*($i+2)-128`($bp),%xmm2
+	movdqa	%xmm3,`16*($i+3)+112`(%r10)
+	pand	`16*($i+3)-128`($bp),%xmm3
+	por	%xmm2,%xmm0
+	por	%xmm3,%xmm1
+___
+for($i=0;$i<$STRIDE/16-4;$i+=4) {
+$code.=<<___;
+	movdqa	`16*($i+0)-128`($bp),%xmm4
+	movdqa	`16*($i+1)-128`($bp),%xmm5
+	movdqa	`16*($i+2)-128`($bp),%xmm2
+	pand	`16*($i+0)+112`(%r10),%xmm4
+	movdqa	`16*($i+3)-128`($bp),%xmm3
+	pand	`16*($i+1)+112`(%r10),%xmm5
+	por	%xmm4,%xmm0
+	pand	`16*($i+2)+112`(%r10),%xmm2
+	por	%xmm5,%xmm1
+	pand	`16*($i+3)+112`(%r10),%xmm3
+	por	%xmm2,%xmm0
+	por	%xmm3,%xmm1
+___
+}
+$code.=<<___;
+	por	%xmm1,%xmm0
+	pshufd	\$0x4e,%xmm0,%xmm1
+	por	%xmm1,%xmm0
+	lea	$STRIDE($bp),$bp
 	movq	%xmm0,$m0		# m0=bp[0]
-	movq	`3*$STRIDE/4-96`($tp),%xmm0
+
 	mov	%r13,16+8(%rsp)		# save end of b[num]
 	mov	$rp, 56+8(%rsp)		# save $rp
 
@@ -521,26 +589,10 @@ $code.=<<___;
 	mov	%rax,$A[0]
 	mov	($np),%rax
 
-	pand	%xmm5,%xmm2
-	pand	%xmm6,%xmm3
-	por	%xmm2,%xmm1
-
 	imulq	$A[0],$m1		# "tp[0]"*n0
-	##############################################################
-	# $tp is chosen so that writing to top-most element of the
-	# vector occurs just "above" references to powers table,
-	# "above" modulo cache-line size, which effectively precludes
-	# possibility of memory disambiguation logic failure when
-	# accessing the table.
-	# 
-	lea	64+8(%rsp,%r11,8),$tp
+	lea	64+8(%rsp),$tp
 	mov	%rdx,$A[1]
 
-	pand	%xmm7,%xmm0
-	por	%xmm3,%xmm1
-	lea	2*$STRIDE($bp),$bp
-	por	%xmm1,%xmm0
-
 	mulq	$m1			# np[0]*m1
 	add	%rax,$A[0]		# discarded
 	mov	8($ap,$num),%rax
@@ -549,7 +601,7 @@ $code.=<<___;
 
 	mulq	$m0
 	add	%rax,$A[1]
-	mov	16*1($np),%rax		# interleaved with 0, therefore 16*n
+	mov	8*1($np),%rax
 	adc	\$0,%rdx
 	mov	%rdx,$A[0]
 
@@ -559,7 +611,7 @@ $code.=<<___;
 	adc	\$0,%rdx
 	add	$A[1],$N[1]
 	lea	4*8($num),$j		# j=4
-	lea	16*4($np),$np
+	lea	8*4($np),$np
 	adc	\$0,%rdx
 	mov	$N[1],($tp)
 	mov	%rdx,$N[0]
@@ -569,7 +621,7 @@ $code.=<<___;
 .L1st4x:
 	mulq	$m0			# ap[j]*bp[0]
 	add	%rax,$A[0]
-	mov	-16*2($np),%rax
+	mov	-8*2($np),%rax
 	lea	32($tp),$tp
 	adc	\$0,%rdx
 	mov	%rdx,$A[1]
@@ -585,7 +637,7 @@ $code.=<<___;
 
 	mulq	$m0			# ap[j]*bp[0]
 	add	%rax,$A[1]
-	mov	-16*1($np),%rax
+	mov	-8*1($np),%rax
 	adc	\$0,%rdx
 	mov	%rdx,$A[0]
 
@@ -600,7 +652,7 @@ $code.=<<___;
 
 	mulq	$m0			# ap[j]*bp[0]
 	add	%rax,$A[0]
-	mov	16*0($np),%rax
+	mov	8*0($np),%rax
 	adc	\$0,%rdx
 	mov	%rdx,$A[1]
 
@@ -615,7 +667,7 @@ $code.=<<___;
 
 	mulq	$m0			# ap[j]*bp[0]
 	add	%rax,$A[1]
-	mov	16*1($np),%rax
+	mov	8*1($np),%rax
 	adc	\$0,%rdx
 	mov	%rdx,$A[0]
 
@@ -624,7 +676,7 @@ $code.=<<___;
 	mov	16($ap,$j),%rax
 	adc	\$0,%rdx
 	add	$A[1],$N[1]		# np[j]*m1+ap[j]*bp[0]
-	lea	16*4($np),$np
+	lea	8*4($np),$np
 	adc	\$0,%rdx
 	mov	$N[1],($tp)		# tp[j-1]
 	mov	%rdx,$N[0]
@@ -634,7 +686,7 @@ $code.=<<___;
 
 	mulq	$m0			# ap[j]*bp[0]
 	add	%rax,$A[0]
-	mov	-16*2($np),%rax
+	mov	-8*2($np),%rax
 	lea	32($tp),$tp
 	adc	\$0,%rdx
 	mov	%rdx,$A[1]
@@ -650,7 +702,7 @@ $code.=<<___;
 
 	mulq	$m0			# ap[j]*bp[0]
 	add	%rax,$A[1]
-	mov	-16*1($np),%rax
+	mov	-8*1($np),%rax
 	adc	\$0,%rdx
 	mov	%rdx,$A[0]
 
@@ -663,8 +715,7 @@ $code.=<<___;
 	mov	$N[1],-16($tp)		# tp[j-1]
 	mov	%rdx,$N[0]
 
-	movq	%xmm0,$m0		# bp[1]
-	lea	($np,$num,2),$np	# rewind $np
+	lea	($np,$num),$np		# rewind $np
 
 	xor	$N[1],$N[1]
 	add	$A[0],$N[0]
@@ -675,6 +726,33 @@ $code.=<<___;
 
 .align	32
 .Louter4x:
+	lea	16+128($tp),%rdx	# where 256-byte mask is (+size optimization)
+	pxor	%xmm4,%xmm4
+	pxor	%xmm5,%xmm5
+___
+for($i=0;$i<$STRIDE/16;$i+=4) {
+$code.=<<___;
+	movdqa	`16*($i+0)-128`($bp),%xmm0
+	movdqa	`16*($i+1)-128`($bp),%xmm1
+	movdqa	`16*($i+2)-128`($bp),%xmm2
+	movdqa	`16*($i+3)-128`($bp),%xmm3
+	pand	`16*($i+0)-128`(%rdx),%xmm0
+	pand	`16*($i+1)-128`(%rdx),%xmm1
+	por	%xmm0,%xmm4
+	pand	`16*($i+2)-128`(%rdx),%xmm2
+	por	%xmm1,%xmm5
+	pand	`16*($i+3)-128`(%rdx),%xmm3
+	por	%xmm2,%xmm4
+	por	%xmm3,%xmm5
+___
+}
+$code.=<<___;
+	por	%xmm5,%xmm4
+	pshufd	\$0x4e,%xmm4,%xmm0
+	por	%xmm4,%xmm0
+	lea	$STRIDE($bp),$bp
+	movq	%xmm0,$m0		# m0=bp[i]
+
 	mov	($tp,$num),$A[0]
 	mov	$n0,$m1
 	mulq	$m0			# ap[0]*bp[i]
@@ -682,25 +760,11 @@ $code.=<<___;
 	mov	($np),%rax
 	adc	\$0,%rdx
 
-	movq	`0*$STRIDE/4-96`($bp),%xmm0
-	movq	`1*$STRIDE/4-96`($bp),%xmm1
-	pand	%xmm4,%xmm0
-	movq	`2*$STRIDE/4-96`($bp),%xmm2
-	pand	%xmm5,%xmm1
-	movq	`3*$STRIDE/4-96`($bp),%xmm3
-
 	imulq	$A[0],$m1		# tp[0]*n0
-	.byte	0x67
 	mov	%rdx,$A[1]
 	mov	$N[1],($tp)		# store upmost overflow bit
 
-	pand	%xmm6,%xmm2
-	por	%xmm1,%xmm0
-	pand	%xmm7,%xmm3
-	por	%xmm2,%xmm0
 	lea	($tp,$num),$tp		# rewind $tp
-	lea	$STRIDE($bp),$bp
-	por	%xmm3,%xmm0
 
 	mulq	$m1			# np[0]*m1
 	add	%rax,$A[0]		# "$N[0]", discarded
@@ -710,7 +774,7 @@ $code.=<<___;
 
 	mulq	$m0			# ap[j]*bp[i]
 	add	%rax,$A[1]
-	mov	16*1($np),%rax		# interleaved with 0, therefore 16*n
+	mov	8*1($np),%rax
 	adc	\$0,%rdx
 	add	8($tp),$A[1]		# +tp[1]
 	adc	\$0,%rdx
@@ -722,7 +786,7 @@ $code.=<<___;
 	adc	\$0,%rdx
 	add	$A[1],$N[1]		# np[j]*m1+ap[j]*bp[i]+tp[j]
 	lea	4*8($num),$j		# j=4
-	lea	16*4($np),$np
+	lea	8*4($np),$np
 	adc	\$0,%rdx
 	mov	%rdx,$N[0]
 	jmp	.Linner4x
@@ -731,7 +795,7 @@ $code.=<<___;
 .Linner4x:
 	mulq	$m0			# ap[j]*bp[i]
 	add	%rax,$A[0]
-	mov	-16*2($np),%rax
+	mov	-8*2($np),%rax
 	adc	\$0,%rdx
 	add	16($tp),$A[0]		# ap[j]*bp[i]+tp[j]
 	lea	32($tp),$tp
@@ -749,7 +813,7 @@ $code.=<<___;
 
 	mulq	$m0			# ap[j]*bp[i]
 	add	%rax,$A[1]
-	mov	-16*1($np),%rax
+	mov	-8*1($np),%rax
 	adc	\$0,%rdx
 	add	-8($tp),$A[1]
 	adc	\$0,%rdx
@@ -766,7 +830,7 @@ $code.=<<___;
 
 	mulq	$m0			# ap[j]*bp[i]
 	add	%rax,$A[0]
-	mov	16*0($np),%rax
+	mov	8*0($np),%rax
 	adc	\$0,%rdx
 	add	($tp),$A[0]		# ap[j]*bp[i]+tp[j]
 	adc	\$0,%rdx
@@ -783,7 +847,7 @@ $code.=<<___;
 
 	mulq	$m0			# ap[j]*bp[i]
 	add	%rax,$A[1]
-	mov	16*1($np),%rax
+	mov	8*1($np),%rax
 	adc	\$0,%rdx
 	add	8($tp),$A[1]
 	adc	\$0,%rdx
@@ -794,7 +858,7 @@ $code.=<<___;
 	mov	16($ap,$j),%rax
 	adc	\$0,%rdx
 	add	$A[1],$N[1]
-	lea	16*4($np),$np
+	lea	8*4($np),$np
 	adc	\$0,%rdx
 	mov	$N[0],-8($tp)		# tp[j-1]
 	mov	%rdx,$N[0]
@@ -804,7 +868,7 @@ $code.=<<___;
 
 	mulq	$m0			# ap[j]*bp[i]
 	add	%rax,$A[0]
-	mov	-16*2($np),%rax
+	mov	-8*2($np),%rax
 	adc	\$0,%rdx
 	add	16($tp),$A[0]		# ap[j]*bp[i]+tp[j]
 	lea	32($tp),$tp
@@ -823,7 +887,7 @@ $code.=<<___;
 	mulq	$m0			# ap[j]*bp[i]
 	add	%rax,$A[1]
 	mov	$m1,%rax
-	mov	-16*1($np),$m1
+	mov	-8*1($np),$m1
 	adc	\$0,%rdx
 	add	-8($tp),$A[1]
 	adc	\$0,%rdx
@@ -838,9 +902,8 @@ $code.=<<___;
 	mov	$N[0],-24($tp)		# tp[j-1]
 	mov	%rdx,$N[0]
 
-	movq	%xmm0,$m0		# bp[i+1]
 	mov	$N[1],-16($tp)		# tp[j-1]
-	lea	($np,$num,2),$np	# rewind $np
+	lea	($np,$num),$np		# rewind $np
 
 	xor	$N[1],$N[1]
 	add	$A[0],$N[0]
@@ -854,16 +917,23 @@ $code.=<<___;
 ___
 if (1) {
 $code.=<<___;
+	xor	%rax,%rax
 	sub	$N[0],$m1		# compare top-most words
 	adc	$j,$j			# $j is zero
 	or	$j,$N[1]
-	xor	\$1,$N[1]
+	sub	$N[1],%rax		# %rax=-$N[1]
 	lea	($tp,$num),%rbx		# tptr in .sqr4x_sub
-	lea	($np,$N[1],8),%rbp	# nptr in .sqr4x_sub
+	mov	($np),%r12
+	lea	($np),%rbp		# nptr in .sqr4x_sub
 	mov	%r9,%rcx
-	sar	\$3+2,%rcx		# cf=0
+	sar	\$3+2,%rcx
 	mov	56+8(%rsp),%rdi		# rptr in .sqr4x_sub
-	jmp	.Lsqr4x_sub
+	dec	%r12			# so that after 'not' we get -n[0]
+	xor	%r10,%r10
+	mov	8*1(%rbp),%r13
+	mov	8*2(%rbp),%r14
+	mov	8*3(%rbp),%r15
+	jmp	.Lsqr4x_sub_entry
 ___
 } else {
 my @ri=("%rax",$bp,$m0,$m1);
@@ -930,8 +1000,8 @@ bn_power5:
 ___
 $code.=<<___ if ($addx);
 	mov	OPENSSL_ia32cap_P+8(%rip),%r11d
-	and	\$0x80100,%r11d
-	cmp	\$0x80100,%r11d
+	and	\$0x80108,%r11d
+	cmp	\$0x80108,%r11d		# check for AD*X+BMI2+BMI1
 	je	.Lpowerx5_enter
 ___
 $code.=<<___;
@@ -942,38 +1012,32 @@ $code.=<<___;
 	push	%r13
 	push	%r14
 	push	%r15
-___
-$code.=<<___ if ($win64);
-	lea	-0x28(%rsp),%rsp
-	movaps	%xmm6,(%rsp)
-	movaps	%xmm7,0x10(%rsp)
-___
-$code.=<<___;
-	mov	${num}d,%r10d
+
 	shl	\$3,${num}d		# convert $num to bytes
-	shl	\$3+2,%r10d		# 4*$num
+	lea	($num,$num,2),%r10d	# 3*$num
 	neg	$num
 	mov	($n0),$n0		# *n0
 
 	##############################################################
-	# ensure that stack frame doesn't alias with $aptr+4*$num
-	# modulo 4096, which covers ret[num], am[num] and n[2*num]
-	# (see bn_exp.c). this is done to allow memory disambiguation
-	# logic do its magic.
+	# Ensure that stack frame doesn't alias with $rptr+3*$num
+	# modulo 4096, which covers ret[num], am[num] and n[num]
+	# (see bn_exp.c). This is done to allow memory disambiguation
+	# logic do its magic. [Extra 256 bytes is for power mask
+	# calculated from 7th argument, the index.]
 	#
-	lea	-64(%rsp,$num,2),%r11
-	sub	$aptr,%r11
+	lea	-320(%rsp,$num,2),%r11
+	sub	$rptr,%r11
 	and	\$4095,%r11
 	cmp	%r11,%r10
 	jb	.Lpwr_sp_alt
 	sub	%r11,%rsp		# align with $aptr
-	lea	-64(%rsp,$num,2),%rsp	# alloca(frame+2*$num)
+	lea	-320(%rsp,$num,2),%rsp	# alloca(frame+2*num*8+256)
 	jmp	.Lpwr_sp_done
 
 .align	32
 .Lpwr_sp_alt:
-	lea	4096-64(,$num,2),%r10	# 4096-frame-2*$num
-	lea	-64(%rsp,$num,2),%rsp	# alloca(frame+2*$num)
+	lea	4096-320(,$num,2),%r10
+	lea	-320(%rsp,$num,2),%rsp	# alloca(frame+2*num*8+256)
 	sub	%r10,%r11
 	mov	\$0,%r10
 	cmovc	%r10,%r11
@@ -995,9 +1059,9 @@ $code.=<<___;
 	mov	$n0,  32(%rsp)
 	mov	%rax, 40(%rsp)		# save original %rsp
 .Lpower5_body:
-	movq	$rptr,%xmm1		# save $rptr
+	movq	$rptr,%xmm1		# save $rptr, used in sqr8x
 	movq	$nptr,%xmm2		# save $nptr
-	movq	%r10, %xmm3		# -$num
+	movq	%r10, %xmm3		# -$num, used in sqr8x
 	movq	$bptr,%xmm4
 
 	call	__bn_sqr8x_internal
@@ -1567,7 +1631,7 @@ $code.=<<___;
 	movq	%xmm2,$nptr
 sqr8x_reduction:
 	xor	%rax,%rax
-	lea	($nptr,$num,2),%rcx	# end of n[]
+	lea	($nptr,$num),%rcx	# end of n[]
 	lea	48+8(%rsp,$num,2),%rdx	# end of t[] buffer
 	mov	%rcx,0+8(%rsp)
 	lea	48+8(%rsp,$num),$tptr	# end of initial t[] window
@@ -1593,21 +1657,21 @@ sqr8x_reduction:
 	.byte	0x67
 	mov	$m0,%r8
 	imulq	32+8(%rsp),$m0		# n0*a[0]
-	mov	16*0($nptr),%rax	# n[0]
+	mov	8*0($nptr),%rax		# n[0]
 	mov	\$8,%ecx
 	jmp	.L8x_reduce
 
 .align	32
 .L8x_reduce:
 	mulq	$m0
-	 mov	16*1($nptr),%rax	# n[1]
+	 mov	8*1($nptr),%rax		# n[1]
 	neg	%r8
 	mov	%rdx,%r8
 	adc	\$0,%r8
 
 	mulq	$m0
 	add	%rax,%r9
-	 mov	16*2($nptr),%rax
+	 mov	8*2($nptr),%rax
 	adc	\$0,%rdx
 	add	%r9,%r8
 	 mov	$m0,48-8+8(%rsp,%rcx,8)	# put aside n0*a[i]
@@ -1616,7 +1680,7 @@ sqr8x_reduction:
 
 	mulq	$m0
 	add	%rax,%r10
-	 mov	16*3($nptr),%rax
+	 mov	8*3($nptr),%rax
 	adc	\$0,%rdx
 	add	%r10,%r9
 	 mov	32+8(%rsp),$carry	# pull n0, borrow $carry
@@ -1625,7 +1689,7 @@ sqr8x_reduction:
 
 	mulq	$m0
 	add	%rax,%r11
-	 mov	16*4($nptr),%rax
+	 mov	8*4($nptr),%rax
 	adc	\$0,%rdx
 	 imulq	%r8,$carry		# modulo-scheduled
 	add	%r11,%r10
@@ -1634,7 +1698,7 @@ sqr8x_reduction:
 
 	mulq	$m0
 	add	%rax,%r12
-	 mov	16*5($nptr),%rax
+	 mov	8*5($nptr),%rax
 	adc	\$0,%rdx
 	add	%r12,%r11
 	mov	%rdx,%r12
@@ -1642,7 +1706,7 @@ sqr8x_reduction:
 
 	mulq	$m0
 	add	%rax,%r13
-	 mov	16*6($nptr),%rax
+	 mov	8*6($nptr),%rax
 	adc	\$0,%rdx
 	add	%r13,%r12
 	mov	%rdx,%r13
@@ -1650,7 +1714,7 @@ sqr8x_reduction:
 
 	mulq	$m0
 	add	%rax,%r14
-	 mov	16*7($nptr),%rax
+	 mov	8*7($nptr),%rax
 	adc	\$0,%rdx
 	add	%r14,%r13
 	mov	%rdx,%r14
@@ -1659,7 +1723,7 @@ sqr8x_reduction:
 	mulq	$m0
 	 mov	$carry,$m0		# n0*a[i]
 	add	%rax,%r15
-	 mov	16*0($nptr),%rax	# n[0]
+	 mov	8*0($nptr),%rax		# n[0]
 	adc	\$0,%rdx
 	add	%r15,%r14
 	mov	%rdx,%r15
@@ -1668,7 +1732,7 @@ sqr8x_reduction:
 	dec	%ecx
 	jnz	.L8x_reduce
 
-	lea	16*8($nptr),$nptr
+	lea	8*8($nptr),$nptr
 	xor	%rax,%rax
 	mov	8+8(%rsp),%rdx		# pull end of t[]
 	cmp	0+8(%rsp),$nptr		# end of n[]?
@@ -1687,21 +1751,21 @@ sqr8x_reduction:
 
 	mov	48+56+8(%rsp),$m0	# pull n0*a[0]
 	mov	\$8,%ecx
-	mov	16*0($nptr),%rax
+	mov	8*0($nptr),%rax
 	jmp	.L8x_tail
 
 .align	32
 .L8x_tail:
 	mulq	$m0
 	add	%rax,%r8
-	 mov	16*1($nptr),%rax
+	 mov	8*1($nptr),%rax
 	 mov	%r8,($tptr)		# save result
 	mov	%rdx,%r8
 	adc	\$0,%r8
 
 	mulq	$m0
 	add	%rax,%r9
-	 mov	16*2($nptr),%rax
+	 mov	8*2($nptr),%rax
 	adc	\$0,%rdx
 	add	%r9,%r8
 	 lea	8($tptr),$tptr		# $tptr++
@@ -1710,7 +1774,7 @@ sqr8x_reduction:
 
 	mulq	$m0
 	add	%rax,%r10
-	 mov	16*3($nptr),%rax
+	 mov	8*3($nptr),%rax
 	adc	\$0,%rdx
 	add	%r10,%r9
 	mov	%rdx,%r10
@@ -1718,7 +1782,7 @@ sqr8x_reduction:
 
 	mulq	$m0
 	add	%rax,%r11
-	 mov	16*4($nptr),%rax
+	 mov	8*4($nptr),%rax
 	adc	\$0,%rdx
 	add	%r11,%r10
 	mov	%rdx,%r11
@@ -1726,7 +1790,7 @@ sqr8x_reduction:
 
 	mulq	$m0
 	add	%rax,%r12
-	 mov	16*5($nptr),%rax
+	 mov	8*5($nptr),%rax
 	adc	\$0,%rdx
 	add	%r12,%r11
 	mov	%rdx,%r12
@@ -1734,7 +1798,7 @@ sqr8x_reduction:
 
 	mulq	$m0
 	add	%rax,%r13
-	 mov	16*6($nptr),%rax
+	 mov	8*6($nptr),%rax
 	adc	\$0,%rdx
 	add	%r13,%r12
 	mov	%rdx,%r13
@@ -1742,7 +1806,7 @@ sqr8x_reduction:
 
 	mulq	$m0
 	add	%rax,%r14
-	 mov	16*7($nptr),%rax
+	 mov	8*7($nptr),%rax
 	adc	\$0,%rdx
 	add	%r14,%r13
 	mov	%rdx,%r14
@@ -1753,14 +1817,14 @@ sqr8x_reduction:
 	add	%rax,%r15
 	adc	\$0,%rdx
 	add	%r15,%r14
-	 mov	16*0($nptr),%rax	# pull n[0]
+	 mov	8*0($nptr),%rax		# pull n[0]
 	mov	%rdx,%r15
 	adc	\$0,%r15
 
 	dec	%ecx
 	jnz	.L8x_tail
 
-	lea	16*8($nptr),$nptr
+	lea	8*8($nptr),$nptr
 	mov	8+8(%rsp),%rdx		# pull end of t[]
 	cmp	0+8(%rsp),$nptr		# end of n[]?
 	jae	.L8x_tail_done		# break out of loop
@@ -1806,7 +1870,7 @@ sqr8x_reduction:
 	adc	8*6($tptr),%r14
 	adc	8*7($tptr),%r15
 	adc	\$0,%rax		# top-most carry
-	 mov	-16($nptr),%rcx		# np[num-1]
+	 mov	-8($nptr),%rcx		# np[num-1]
 	 xor	$carry,$carry
 
 	movq	%xmm2,$nptr		# restore $nptr
@@ -1833,33 +1897,49 @@ ___
 my ($tptr,$nptr)=("%rbx","%rbp");
 $code.=<<___;
 	#xor	%rsi,%rsi		# %rsi was $carry above
+	mov	8*0($nptr),%r12
 	sub	%r15,%rcx		# compare top-most words
 	lea	(%rdi,$num),$tptr	# %rdi was $tptr above
 	adc	%rsi,%rsi
 	mov	$num,%rcx
 	or	%rsi,%rax
 	movq	%xmm1,$rptr		# restore $rptr
-	xor	\$1,%rax
+	neg	%rax
 	movq	%xmm1,$aptr		# prepare for back-to-back call
-	lea	($nptr,%rax,8),$nptr
-	sar	\$3+2,%rcx		# cf=0
-	jmp	.Lsqr4x_sub
+	sar	\$3+2,%rcx
+	dec	%r12			# so that after 'not' we get -n[0]
+	xor	%r10,%r10
+	mov	8*1($nptr),%r13
+	mov	8*2($nptr),%r14
+	mov	8*3($nptr),%r15
+	jmp	.Lsqr4x_sub_entry
 
-.align	32
+.align	16
 .Lsqr4x_sub:
-	.byte	0x66
-	mov	8*0($tptr),%r12
-	mov	8*1($tptr),%r13
-	sbb	16*0($nptr),%r12
-	mov	8*2($tptr),%r14
-	sbb	16*1($nptr),%r13
-	mov	8*3($tptr),%r15
-	lea	8*4($tptr),$tptr
-	sbb	16*2($nptr),%r14
+	mov	8*0($nptr),%r12
+	mov	8*1($nptr),%r13
+	mov	8*2($nptr),%r14
+	mov	8*3($nptr),%r15
+.Lsqr4x_sub_entry:
+	lea	8*4($nptr),$nptr
+	not	%r12
+	not	%r13
+	not	%r14
+	not	%r15
+	and	%rax,%r12
+	and	%rax,%r13
+	and	%rax,%r14
+	and	%rax,%r15
+
+	neg	%r10			# mov %r10,%cf
+	adc	8*0($tptr),%r12
+	adc	8*1($tptr),%r13
+	adc	8*2($tptr),%r14
+	adc	8*3($tptr),%r15
 	mov	%r12,8*0($rptr)
-	sbb	16*3($nptr),%r15
-	lea	16*4($nptr),$nptr
+	lea	8*4($tptr),$tptr
 	mov	%r13,8*1($rptr)
+	sbb	%r10,%r10		# mov %cf,%r10
 	mov	%r14,8*2($rptr)
 	mov	%r15,8*3($rptr)
 	lea	8*4($rptr),$rptr
@@ -1897,39 +1977,32 @@ bn_from_mont8x:
 	push	%r13
 	push	%r14
 	push	%r15
-___
-$code.=<<___ if ($win64);
-	lea	-0x28(%rsp),%rsp
-	movaps	%xmm6,(%rsp)
-	movaps	%xmm7,0x10(%rsp)
-___
-$code.=<<___;
-	.byte	0x67
-	mov	${num}d,%r10d
+
 	shl	\$3,${num}d		# convert $num to bytes
-	shl	\$3+2,%r10d		# 4*$num
+	lea	($num,$num,2),%r10	# 3*$num in bytes
 	neg	$num
 	mov	(