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
___
}

Lines 110-115 Link Here

(-)a/crypto/bn/bn_exp.c (-18 / +57 lines)
110	*/	110	*/
111		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
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
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	{
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