Attachment #7513 for bug #40189




.align	16
.Lmul_enter:
	mov	${num}d,${num}d
	movd	`($win64?56:8)`(%rsp),%xmm5	# load 7th argument
	lea	.Linc(%rip),%r10
	push	%rbx
	push	%rbp
	push	%r12
	push	%r13
	push	%r14
	push	%r15

$code.=<<___ if ($win64);
	lea	-0x28(%rsp),%rsp
	movaps	%xmm6,(%rsp)
	movaps	%xmm7,0x10(%rsp)
.Lmul_alloca:
___
$code.=<<___;
	mov	%rsp,%rax
	lea	2($num),%r11
	neg	%r11
	lea	-264(%rsp,%r11,8),%rsp	# tp=alloca(8*(num+2)+256+8)
	and	\$-1024,%rsp		# minimize TLB usage

	mov	%rax,8(%rsp,$num,8)	# tp[num+1]=%rsp
.Lmul_body:
	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.=<<___;
	movdqa	0(%r10),%xmm0		# 00000001000000010000000000000000
	movdqa	16(%r10),%xmm1		# 00000002000000020000000200000002
	lea	24-112(%rsp,$num,8),%r10# place the mask after tp[num+3] (+ICache optimization)
	and	\$-16,%r10

	pshufd	\$0,%xmm5,%xmm5		# broadcast index
	movdqa	%xmm1,%xmm4
	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
	movdqa	%xmm4,%xmm3
___
for($k=0;$k<$STRIDE/16-4;$k+=4) {
$code.=<<___;
	paddd	%xmm1,%xmm2
	pcmpeqd	%xmm5,%xmm1		# compare to 3,2
	movdqa	%xmm0,`16*($k+0)+112`(%r10)
	movdqa	%xmm4,%xmm0

	paddd	%xmm2,%xmm3
	pcmpeqd	%xmm5,%xmm2		# compare to 5,4
	movdqa	%xmm1,`16*($k+1)+112`(%r10)
	movdqa	%xmm4,%xmm1

	paddd	%xmm3,%xmm0
	pcmpeqd	%xmm5,%xmm3		# compare to 7,6
	movdqa	%xmm2,`16*($k+2)+112`(%r10)
	movdqa	%xmm4,%xmm2

	paddd	%xmm0,%xmm1
	pcmpeqd	%xmm5,%xmm0
	movdqa	%xmm3,`16*($k+3)+112`(%r10)
	movdqa	%xmm4,%xmm3
___
}
$code.=<<___;				# last iteration can be optimized
	paddd	%xmm1,%xmm2
	pcmpeqd	%xmm5,%xmm1
	movdqa	%xmm0,`16*($k+0)+112`(%r10)

	paddd	%xmm2,%xmm3
	.byte	0x67
	pcmpeqd	%xmm5,%xmm2
	movdqa	%xmm1,`16*($k+1)+112`(%r10)

	pcmpeqd	%xmm5,%xmm3
	movdqa	%xmm2,`16*($k+2)+112`(%r10)
	pand	`16*($k+0)-128`($bp),%xmm0	# while it's still in register

	pand	`16*($k+1)-128`($bp),%xmm1
	pand	`16*($k+2)-128`($bp),%xmm2
	movdqa	%xmm3,`16*($k+3)+112`(%r10)
	pand	`16*($k+3)-128`($bp),%xmm3
	por	%xmm2,%xmm0
	por	%xmm3,%xmm1
___
for($k=0;$k<$STRIDE/16-4;$k+=4) {
$code.=<<___;
	movdqa	`16*($k+0)-128`($bp),%xmm4
	movdqa	`16*($k+1)-128`($bp),%xmm5
	movdqa	`16*($k+2)-128`($bp),%xmm2
	pand	`16*($k+0)+112`(%r10),%xmm4
	movdqa	`16*($k+3)-128`($bp),%xmm3
	pand	`16*($k+1)+112`(%r10),%xmm5
	por	%xmm4,%xmm0
	pand	`16*($k+2)+112`(%r10),%xmm2
	por	%xmm5,%xmm1
	pand	`16*($k+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
	por	%xmm3,%xmm0

	movq	%xmm0,$m0		# m0=bp[0]

	mov	($n0),$n0		# pull n0[0] value

	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

	cmp	$num,$j
	jne	.L1st

	movq	%xmm0,$m0		# bp[1]

	add	%rax,$hi1
	mov	($ap),%rax		# ap[0]
	adc	\$0,%rdx

	jmp	.Louter
.align	16
.Louter:
	lea	24+128(%rsp,$num,8),%rdx	# where 256-byte mask is (+size optimization)
	and	\$-16,%rdx
	pxor	%xmm4,%xmm4
	pxor	%xmm5,%xmm5
___
for($k=0;$k<$STRIDE/16;$k+=4) {
$code.=<<___;
	movdqa	`16*($k+0)-128`($bp),%xmm0
	movdqa	`16*($k+1)-128`($bp),%xmm1
	movdqa	`16*($k+2)-128`($bp),%xmm2
	movdqa	`16*($k+3)-128`($bp),%xmm3
	pand	`16*($k+0)-128`(%rdx),%xmm0
	pand	`16*($k+1)-128`(%rdx),%xmm1
	por	%xmm0,%xmm4
	pand	`16*($k+2)-128`(%rdx),%xmm2
	por	%xmm1,%xmm5
	pand	`16*($k+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]

	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

	cmp	$num,$j
	jne	.Linner

	movq	%xmm0,$m0		# bp[i+1]

	add	%rax,$hi1
	mov	($ap),%rax		# ap[0]
	adc	\$0,%rdx


	mov	8(%rsp,$num,8),%rsi	# restore %rsp
	mov	\$1,%rax

$code.=<<___ if ($win64);
	movaps	(%rsi),%xmm6
	movaps	0x10(%rsi),%xmm7
	lea	0x28(%rsi),%rsi
___
$code.=<<___;
	mov	(%rsi),%r15
	mov	8(%rsi),%r14
	mov	16(%rsi),%r13

bn_mul4x_mont_gather5:
.Lmul4x_enter:
	mov	${num}d,${num}d
	movd	`($win64?56:8)`(%rsp),%xmm5	# load 7th argument
	lea	.Linc(%rip),%r10
	push	%rbx
	push	%rbp
	push	%r12
	push	%r13
	push	%r14
	push	%r15

$code.=<<___ if ($win64);
	lea	-0x28(%rsp),%rsp
	movaps	%xmm6,(%rsp)
	movaps	%xmm7,0x10(%rsp)
.Lmul4x_alloca:
___
$code.=<<___;
	mov	%rsp,%rax
	lea	4($num),%r11
	neg	%r11
	lea	-256(%rsp,%r11,8),%rsp	# tp=alloca(8*(num+4)+256)
	and	\$-1024,%rsp		# minimize TLB usage

	mov	%rax,8(%rsp,$num,8)	# tp[num+1]=%rsp
.Lmul4x_body:
	mov	$rp,16(%rsp,$num,8)	# tp[num+2]=$rp
	lea	128(%rdx),%r12		# reassign $bp (+size optimization)
___
		$bp="%r12";
		$STRIDE=2**5*8;		# 5 is "window size"
		$N=$STRIDE/4;		# should match cache line size
$code.=<<___;
	movdqa	0(%r10),%xmm0		# 00000001000000010000000000000000
	movdqa	16(%r10),%xmm1		# 00000002000000020000000200000002
	lea	32-112(%rsp,$num,8),%r10# place the mask after tp[num+4] (+ICache 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
	movdqa	%xmm4,%xmm3
___
for($k=0;$k<$STRIDE/16-4;$k+=4) {
$code.=<<___;
	paddd	%xmm1,%xmm2
	pcmpeqd	%xmm5,%xmm1		# compare to 3,2
	movdqa	%xmm0,`16*($k+0)+112`(%r10)
	movdqa	%xmm4,%xmm0

	paddd	%xmm2,%xmm3
	pcmpeqd	%xmm5,%xmm2		# compare to 5,4
	movdqa	%xmm1,`16*($k+1)+112`(%r10)
	movdqa	%xmm4,%xmm1

	paddd	%xmm3,%xmm0
	pcmpeqd	%xmm5,%xmm3		# compare to 7,6
	movdqa	%xmm2,`16*($k+2)+112`(%r10)
	movdqa	%xmm4,%xmm2

	paddd	%xmm0,%xmm1
	pcmpeqd	%xmm5,%xmm0
	movdqa	%xmm3,`16*($k+3)+112`(%r10)
	movdqa	%xmm4,%xmm3
___
}
$code.=<<___;				# last iteration can be optimized
	paddd	%xmm1,%xmm2
	pcmpeqd	%xmm5,%xmm1
	movdqa	%xmm0,`16*($k+0)+112`(%r10)

	paddd	%xmm2,%xmm3
	.byte	0x67
	pcmpeqd	%xmm5,%xmm2
	movdqa	%xmm1,`16*($k+1)+112`(%r10)

	pcmpeqd	%xmm5,%xmm3
	movdqa	%xmm2,`16*($k+2)+112`(%r10)
	pand	`16*($k+0)-128`($bp),%xmm0	# while it's still in register

	pand	`16*($k+1)-128`($bp),%xmm1
	pand	`16*($k+2)-128`($bp),%xmm2
	movdqa	%xmm3,`16*($k+3)+112`(%r10)
	pand	`16*($k+3)-128`($bp),%xmm3
	por	%xmm2,%xmm0
	por	%xmm3,%xmm1
___
for($k=0;$k<$STRIDE/16-4;$k+=4) {
$code.=<<___;
	movdqa	`16*($k+0)-128`($bp),%xmm4
	movdqa	`16*($k+1)-128`($bp),%xmm5
	movdqa	`16*($k+2)-128`($bp),%xmm2
	pand	`16*($k+0)+112`(%r10),%xmm4
	movdqa	`16*($k+3)-128`($bp),%xmm3
	pand	`16*($k+1)+112`(%r10),%xmm5
	por	%xmm4,%xmm0
	pand	`16*($k+2)+112`(%r10),%xmm2
	por	%xmm5,%xmm1
	pand	`16*($k+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
	por	%xmm3,%xmm0

	movq	%xmm0,$m0		# m0=bp[0]

	mov	($n0),$n0		# pull n0[0] value
	mov	($ap),%rax

	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,$A[0]
	mov	($np),%rax

	movq	`3*$STRIDE/4-96`($bp),%xmm3
	pand	%xmm6,%xmm2
	por	%xmm1,%xmm0
	pand	%xmm7,%xmm3

	imulq	$A[0],$m1		# "tp[0]"*n0
	mov	%rdx,$A[1]

	por	%xmm2,%xmm0
	lea	$STRIDE($bp),$bp
	por	%xmm3,%xmm0

	mulq	$m1			# np[0]*m1
	add	%rax,$A[0]		# discarded
	mov	8($ap),%rax

	mov	$N[1],-16(%rsp,$j,8)	# tp[j-1]
	mov	%rdx,$N[0]

	movq	%xmm0,$m0		# bp[1]

	xor	$N[1],$N[1]
	add	$A[0],$N[0]
	adc	\$0,$N[1]

	lea	1($i),$i		# i++
.align	4
.Louter4x:
	lea	32+128(%rsp,$num,8),%rdx	# where 256-byte mask is (+size optimization)
	pxor	%xmm4,%xmm4
	pxor	%xmm5,%xmm5
___
for($k=0;$k<$STRIDE/16;$k+=4) {
$code.=<<___;
	movdqa	`16*($k+0)-128`($bp),%xmm0
	movdqa	`16*($k+1)-128`($bp),%xmm1
	movdqa	`16*($k+2)-128`($bp),%xmm2
	movdqa	`16*($k+3)-128`($bp),%xmm3
	pand	`16*($k+0)-128`(%rdx),%xmm0
	pand	`16*($k+1)-128`(%rdx),%xmm1
	por	%xmm0,%xmm4
	pand	`16*($k+2)-128`(%rdx),%xmm2
	por	%xmm1,%xmm5
	pand	`16*($k+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]

	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	(%rsp),$A[0]
	mov	$n0,$m1

	mov	($np),%rax
	adc	\$0,%rdx

	movq	`3*$STRIDE/4-96`($bp),%xmm3
	pand	%xmm6,%xmm2
	por	%xmm1,%xmm0
	pand	%xmm7,%xmm3

	imulq	$A[0],$m1		# tp[0]*n0
	mov	%rdx,$A[1]

	por	%xmm2,%xmm0
	lea	$STRIDE($bp),$bp
	por	%xmm3,%xmm0

	mulq	$m1			# np[0]*m1
	add	%rax,$A[0]		# "$N[0]", discarded
	mov	8($ap),%rax

	mov	$N[0],-24(%rsp,$j,8)	# tp[j-1]
	mov	%rdx,$N[0]

	movq	%xmm0,$m0		# bp[i+1]
	mov	$N[1],-16(%rsp,$j,8)	# tp[j-1]

	xor	$N[1],$N[1]

$code.=<<___;
	mov	8(%rsp,$num,8),%rsi	# restore %rsp
	mov	\$1,%rax

$code.=<<___ if ($win64);
	movaps	(%rsi),%xmm6
	movaps	0x10(%rsi),%xmm7
	lea	0x28(%rsi),%rsi
___
$code.=<<___;
	mov	(%rsi),%r15
	mov	8(%rsi),%r14
	mov	16(%rsi),%r13

}}}

{
my ($inp,$num,$tbl,$idx)=$win64?("%rcx","%rdx","%r8", "%r9d") : # Win64 order
				("%rdi","%rsi","%rdx","%ecx"); # Unix order
my $out=$inp;
my $STRIDE=2**5*8;
my $N=$STRIDE/4;

.type	bn_gather5,\@abi-omnipotent
.align	16
bn_gather5:
.LSEH_begin_bn_gather5:			# Win64 thing, but harmless in other cases
$code.=<<___ if ($win64);
.LSEH_begin_bn_gather5:
	# I can't trust assembler to use specific encoding:-(
	.byte	0x4c,0x8d,0x14,0x24			# lea    (%rsp),%r10
	.byte	0x48,0x81,0xec,0x08,0x01,0x00,0x00	# sub	$0x108,%rsp
	lea	.Linc(%rip),%rax
	and	\$-16,%rsp		# shouldn't be formally required

	movd	$idx,%xmm5
	movdqa	0(%rax),%xmm0		# 00000001000000010000000000000000
	movdqa	16(%rax),%xmm1		# 00000002000000020000000200000002
	lea	128($tbl),%r11		# size optimization
	lea	128(%rsp),%rax		# size optimization

	pshufd	\$0,%xmm5,%xmm5		# broadcast $idx
	movdqa	%xmm1,%xmm4
	movdqa	%xmm1,%xmm2
___
########################################################################
# calculate mask by comparing 0..31 to $idx and save result to stack
#
for($i=0;$i<$STRIDE/16;$i+=4) {
$code.=<<___;
	paddd	%xmm0,%xmm1
	pcmpeqd	%xmm5,%xmm0		# compare to 1,0
___
$code.=<<___	if ($i);
	movdqa	%xmm3,`16*($i-1)-128`(%rax)
___
$code.=<<___;
	movdqa	%xmm4,%xmm3

	paddd	%xmm1,%xmm2
	pcmpeqd	%xmm5,%xmm1		# compare to 3,2
	movdqa	%xmm0,`16*($i+0)-128`(%rax)
	movdqa	%xmm4,%xmm0

	paddd	%xmm2,%xmm3
	pcmpeqd	%xmm5,%xmm2		# compare to 5,4
	movdqa	%xmm1,`16*($i+1)-128`(%rax)
	movdqa	%xmm4,%xmm1

	paddd	%xmm3,%xmm0
	pcmpeqd	%xmm5,%xmm3		# compare to 7,6
	movdqa	%xmm2,`16*($i+2)-128`(%rax)
	movdqa	%xmm4,%xmm2
___
}
$code.=<<___;
	movdqa	%xmm3,`16*($i-1)-128`(%rax)
	shr	\$`log($N/8)/log(2)`,$idx
	and	\$`$N/8-1`,%r11
	not	$idx
	lea	.Lmagic_masks(%rip),%rax
	and	\$`2**5/($N/8)-1`,$idx	# 5 is "window size"
	lea	96($tbl,%r11,8),$tbl	# pointer within 1st cache line
	movq	0(%rax,$idx,8),%xmm4	# set of masks denoting which
	movq	8(%rax,$idx,8),%xmm5	# cache line contains element
	movq	16(%rax,$idx,8),%xmm6	# denoted by 7th argument
	movq	24(%rax,$idx,8),%xmm7
	jmp	.Lgather
.align	16
.Lgather:
	movq	`0*$STRIDE/4-96`($tbl),%xmm0
	movq	`1*$STRIDE/4-96`($tbl),%xmm1
	pand	%xmm4,%xmm0
	movq	`2*$STRIDE/4-96`($tbl),%xmm2
	pand	%xmm5,%xmm1
	movq	`3*$STRIDE/4-96`($tbl),%xmm3
	pand	%xmm6,%xmm2
	por	%xmm1,%xmm0
	pand	%xmm7,%xmm3
	por	%xmm2,%xmm0
	lea	$STRIDE($tbl),$tbl
	por	%xmm3,%xmm0

.align	32
.Lgather:
	pxor	%xmm4,%xmm4
	pxor	%xmm5,%xmm5
___
for($i=0;$i<$STRIDE/16;$i+=4) {
$code.=<<___;
	movdqa	`16*($i+0)-128`(%r11),%xmm0
	movdqa	`16*($i+1)-128`(%r11),%xmm1
	movdqa	`16*($i+2)-128`(%r11),%xmm2
	pand	`16*($i+0)-128`(%rax),%xmm0
	movdqa	`16*($i+3)-128`(%r11),%xmm3
	pand	`16*($i+1)-128`(%rax),%xmm1
	por	%xmm0,%xmm4
	pand	`16*($i+2)-128`(%rax),%xmm2
	por	%xmm1,%xmm5
	pand	`16*($i+3)-128`(%rax),%xmm3
	por	%xmm2,%xmm4
	por	%xmm3,%xmm5
___
}
$code.=<<___;
	por	%xmm5,%xmm4
	lea	$STRIDE(%r11),%r11
	pshufd	\$0x4e,%xmm4,%xmm0
	por	%xmm4,%xmm0
	movq	%xmm0,($out)		# m0=bp[0]
	lea	8($out),$out
	sub	\$1,$num
	jnz	.Lgather

	lea	(%r10),%rsp
	movaps	(%rsp),%xmm6
	movaps	0x10(%rsp),%xmm7
	lea	0x28(%rsp),%rsp
___
$code.=<<___;
	ret
.LSEH_end_bn_gather5:
.size	bn_gather5,.-bn_gather5

}
$code.=<<___;
.align	64
.Linc:
	.long	0,0, 1,1
	.long	2,2, 2,2
.asciz	"Montgomery Multiplication with scatter/gather for x86_64, CRYPTOGAMS by <appro\@openssl.org>"
___


	cmp	%r10,%rbx		# context->Rip<end of prologue label
	jb	.Lcommon_seh_tail

	lea	48(%rax),%rax

	mov	4(%r11),%r10d		# HandlerData[1]
	lea	(%rsi,%r10),%r10	# end of alloca label

	mov	192($context),%r10	# pull $num
	mov	8(%rax,%r10,8),%rax	# pull saved stack pointer

	lea	48(%rax),%rax
	movaps	16(%rax),%xmm1
	lea	`40+48`(%rax),%rax

	mov	-8(%rax),%rbx
	mov	-16(%rax),%rbp

	mov	%r13,224($context)	# restore context->R13
	mov	%r14,232($context)	# restore context->R14
	mov	%r15,240($context)	# restore context->R15
	movups	%xmm0,512($context)	# restore context->Xmm6
	movups	%xmm1,528($context)	# restore context->Xmm7

.Lcommon_seh_tail:
	mov	8(%rax),%rdi

	.rva	.Lmul4x_alloca,.Lmul4x_body,.Lmul4x_epilogue	# HandlerData[]
.align	8
.LSEH_info_bn_gather5:
	.byte	0x01,0x0b,0x03,0x0a
	.byte	0x0b,0x01,0x21,0x00	# sub	rsp,0x108
	.byte	0x04,0xa3,0x00,0x00	# lea	r10,(rsp), set_frame r10
        .byte   0x04,0x42,0x00,0x00	#sub	rsp,0x28
.align	8
___
}

(-)a/crypto/bn/bn_exp.c (-18 / +57 lines)

Lines 110-115	Link Here

110

*/

110

*/

111

112

#include "cryptlib.h"

112

#include "cryptlib.h"

113

#include "constant_time_locl.h"

113

#include "bn_lcl.h"

114

#include "bn_lcl.h"

114

115

#include <stdlib.h>

116

#include <stdlib.h>

Lines 546-560 int BN_mod_exp_mont(BIGNUM rr, const BIGNUM a, const BIGNUM *p,	Link Here

546

547

static int MOD_EXP_CTIME_COPY_TO_PREBUF(const BIGNUM *b, int top,

548

static int MOD_EXP_CTIME_COPY_TO_PREBUF(const BIGNUM *b, int top,

548

                                        unsigned char *buf, int idx,

549

                                        unsigned char *buf, int idx,

549

                                        int width)

550

                                        int window)

550

551

    size_t i, j;

552

    int i, j;

553

    int width = 1 << window;

554

    BN_ULONG *table = (BN_ULONG *)buf;

552

555

553

    if (top > b->top)

556

    if (top > b->top)

554

        top = b->top;           /* this works because 'buf' is explicitly

557

        top = b->top;           /* this works because 'buf' is explicitly

555

                                 * zeroed */

558

                                 * zeroed */

556

    for (i = 0, j = idx; i < top * sizeof b->d[0]; i++, j += width) {

559

    for (i = 0, j = idx; i < top; i++, j += width) {

557

        buf[j] = ((unsigned char *)b->d)[i];

560

        table[j] = b->d[i];

558

561

559

562

560

    return 1;

563

    return 1;

Lines 562-576 static int MOD_EXP_CTIME_COPY_TO_PREBUF(const BIGNUM *b, int top,	Link Here

562

565

563

static int MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM *b, int top,

566

static int MOD_EXP_CTIME_COPY_FROM_PREBUF(BIGNUM *b, int top,

564

                                          unsigned char *buf, int idx,

567

                                          unsigned char *buf, int idx,

565

                                          int width)

568

                                          int window)

566

569

567

    size_t i, j;

570

    int i, j;

571

    int width = 1 << window;

572

    volatile BN_ULONG *table = (volatile BN_ULONG *)buf;

568

573

569

    if (bn_wexpand(b, top) == NULL)

574

    if (bn_wexpand(b, top) == NULL)

570

        return 0;

575

        return 0;

571

576

572

    for (i = 0, j = idx; i < top * sizeof b->d[0]; i++, j += width) {

577

    if (window <= 3) {

573

        ((unsigned char *)b->d)[i] = buf[j];

578

        for (i = 0; i < top; i++, table += width) {

579

            BN_ULONG acc = 0;

580

581

            for (j = 0; j < width; j++) {

582

                acc |= table[j] &

583

                       ((BN_ULONG)0 - (constant_time_eq_int(j,idx)&1));

584

585

586

            b->d[i] = acc;

587

588

    } else {

589

        int xstride = 1 << (window - 2);

590

        BN_ULONG y0, y1, y2, y3;

591

592

        i = idx >> (window - 2);        /* equivalent of idx / xstride */

593

        idx &= xstride - 1;             /* equivalent of idx % xstride */

594

595

        y0 = (BN_ULONG)0 - (constant_time_eq_int(i,0)&1);

596

        y1 = (BN_ULONG)0 - (constant_time_eq_int(i,1)&1);

597

        y2 = (BN_ULONG)0 - (constant_time_eq_int(i,2)&1);

598

        y3 = (BN_ULONG)0 - (constant_time_eq_int(i,3)&1);

599

600

        for (i = 0; i < top; i++, table += width) {

601

            BN_ULONG acc = 0;

602

603

            for (j = 0; j < xstride; j++) {

604

                acc |= ( (table[j + 0 * xstride] & y0) |

605

                         (table[j + 1 * xstride] & y1) |

606

                         (table[j + 2 * xstride] & y2) |

607

                         (table[j + 3 * xstride] & y3) )

608

                       & ((BN_ULONG)0 - (constant_time_eq_int(j,idx)&1));

609

610

611

            b->d[i] = acc;

612

574

613

575

614

576

    b->top = top;

615

    b->top = top;

Lines 800-808 int BN_mod_exp_mont_consttime(BIGNUM rr, const BIGNUM a, const BIGNUM *p,	Link Here

800

    } else

839

    } else

801

#endif

840

#endif

802

841

803

        if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, powerbuf, 0, numPowers))

842

        if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, powerbuf, 0, window))

804

            goto err;

843

            goto err;

805

        if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&am, top, powerbuf, 1, numPowers))

844

        if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&am, top, powerbuf, 1, window))

806

            goto err;

845

            goto err;

807

846

808

/*

847

/*

Lines 814-828 int BN_mod_exp_mont_consttime(BIGNUM rr, const BIGNUM a, const BIGNUM *p,	Link Here

814

        if (window > 1) {

853

        if (window > 1) {

815

            if (!BN_mod_mul_montgomery(&tmp, &am, &am, mont, ctx))

854

            if (!BN_mod_mul_montgomery(&tmp, &am, &am, mont, ctx))

816

                goto err;

855

                goto err;

817

            if (!MOD_EXP_CTIME_COPY_TO_PREBUF

856

            if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, powerbuf, 2,

818

                (&tmp, top, powerbuf, 2, numPowers))

857

                                              window))

819

                goto err;

858

                goto err;

820

            for (i = 3; i < numPowers; i++) {

859

            for (i = 3; i < numPowers; i++) {

821

                /* Calculate a^i = a^(i-1) * a */

860

                /* Calculate a^i = a^(i-1) * a */

822

                if (!BN_mod_mul_montgomery(&tmp, &am, &tmp, mont, ctx))

861

                if (!BN_mod_mul_montgomery(&tmp, &am, &tmp, mont, ctx))

823

                    goto err;

862

                    goto err;

824

                if (!MOD_EXP_CTIME_COPY_TO_PREBUF

863

                if (!MOD_EXP_CTIME_COPY_TO_PREBUF(&tmp, top, powerbuf, i,

825

                    (&tmp, top, powerbuf, i, numPowers))

864

                                                  window))

826

                    goto err;

865

                    goto err;

827

866

828

867

Lines 830-837 int BN_mod_exp_mont_consttime(BIGNUM rr, const BIGNUM a, const BIGNUM *p,	Link Here

830

        bits--;

869

        bits--;

831

        for (wvalue = 0, i = bits % window; i >= 0; i--, bits--)

870

        for (wvalue = 0, i = bits % window; i >= 0; i--, bits--)

832

            wvalue = (wvalue << 1) + BN_is_bit_set(p, bits);

871

            wvalue = (wvalue << 1) + BN_is_bit_set(p, bits);

833

        if (!MOD_EXP_CTIME_COPY_FROM_PREBUF

872

        if (!MOD_EXP_CTIME_COPY_FROM_PREBUF(&tmp, top, powerbuf, wvalue,

834

            (&tmp, top, powerbuf, wvalue, numPowers))

873

                                            window))

835

            goto err;

874

            goto err;

836

875

837

/*

876

/*

Lines 851-858 int BN_mod_exp_mont_consttime(BIGNUM rr, const BIGNUM a, const BIGNUM *p,	Link Here

851

/*

890

/*

852

             * Fetch the appropriate pre-computed value from the pre-buf

891

             * Fetch the appropriate pre-computed value from the pre-buf

853

*/

892

*/

854

            if (!MOD_EXP_CTIME_COPY_FROM_PREBUF

893

            if (!MOD_EXP_CTIME_COPY_FROM_PREBUF(&am, top, powerbuf, wvalue,

855

                (&am, top, powerbuf, wvalue, numPowers))

894

                                                window))

856

                goto err;

895

                goto err;

857

896

858

            /* Multiply the result into the intermediate result */

897

            /* Multiply the result into the intermediate result */

Return to bug 40189