[thirdparty/openssl.git] / crypto / bn / asm / x86-mont.pl

#!/usr/bin/env perl

# ====================================================================
# Written by Andy Polyakov <appro@fy.chalmers.se> for the OpenSSL
# project. The module is, however, dual licensed under OpenSSL and
# CRYPTOGAMS licenses depending on where you obtain it. For further
# details see http://www.openssl.org/~appro/cryptogams/.
# ====================================================================

# October 2005
#
# This is a "teaser" code, as it can be improved in several ways...
# First of all non-SSE2 path should be implemented (yes, for now it
# performs Montgomery multiplication/convolution only on SSE2-capable
# CPUs such as P4, others fall down to original code). Then inner loop
# can be unrolled and modulo-scheduled to improve ILP and possibly
# moved to 128-bit XMM register bank (though it would require input
# rearrangement and/or increase bus bandwidth utilization). Dedicated
# squaring procedure should give further performance improvement...
# Yet, for being draft, the code improves rsa512 *sign* benchmark by
# 110%(!), rsa1024 one - by 70% and rsa4096 - by 20%:-)

# December 2006
#
# Modulo-scheduling SSE2 loops results in further 15-20% improvement.
# Integer-only code [being equipped with dedicated squaring procedure]
# gives >=30% on rsa512 sign benchmark...

$0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
push(@INC,"${dir}","${dir}../../perlasm");
require "x86asm.pl";

&asm_init($ARGV[0],$0);

$sse2=0;
for (@ARGV) { $sse2=1 if (/-DOPENSSL_IA32_SSE2/); }

&external_label("OPENSSL_ia32cap_P") if ($sse2);

&function_begin("bn_mul_mont");

$i="edx";
$j="ecx";
$ap="esi";
$rp="edi";	$bp="edi";		# overlapping variables!!!
$np="ebp";
$num="ebx";

$_rp=&DWP(4*0,"esp");			# stack top layout
$_ap=&DWP(4*1,"esp");
$_bp=&DWP(4*2,"esp");
$_np=&DWP(4*3,"esp");
$_n0=&DWP(4*4,"esp");
$_num=&DWP(4*5,"esp");
$_sp=&DWP(4*6,"esp");
$_bpend=&DWP(4*7,"esp");
$frame=32;				# size of above frame rounded up to 16n

	&xor	("eax","eax");
	&mov	("edi",&wparam(5));	# int num
	&cmp	("edi",4);
	&jl	(&label("just_leave"));

	################################# load argument block...
	&mov	("eax",&wparam(0));	# BN_ULONG *rp
	&mov	("ebx",&wparam(1));	# const BN_ULONG *ap
	&mov	("ecx",&wparam(2));	# const BN_ULONG *bp
	&mov	("edx",&wparam(3));	# const BN_ULONG *np
	&mov	("esi",&wparam(4));	# const BN_ULONG *n0
	#&mov	("edi",&wparam(5));	# int num

	&mov	("ebp","esp");		# saved stack pointer!
	&add	("edi",2);		# extra two words on top of tp
	&neg	("edi");
	&lea	("esp",&DWP(-$frame,"esp","edi",4));	# alloca($frame+4*(num+2))
	&neg	("edi");
	&and	("esp",-4096);		# minimize TLB utilization

	&mov	("esi",&DWP(0,"esi"));	# pull n0[0]
	&mov	($_rp,"eax");		# ... save a copy of argument block
	&mov	($_ap,"ebx");
	&mov	($_bp,"ecx");
	&mov	($_np,"edx");
	&mov	($_n0,"esi");
	&lea	($num,&DWP(-3,"edi"));	# num=num-1 to assist modulo-scheduling
	#&mov	($_num,$num);		# redundant as $num is not reused
	&mov	($_sp,"ebp");		# saved stack pointer!
\f
if($sse2) {
$acc0="mm0";	# mmx register bank layout
$acc1="mm1";
$car0="mm2";
$car1="mm3";
$mul0="mm4";
$mul1="mm5";
$temp="mm6";
$mask="mm7";

	&picmeup("eax","OPENSSL_ia32cap_P");
	&bt	(&DWP(0,"eax"),26);
	&jnc	(&label("non_sse2"));

	&mov	("eax",-1);
	&movd	($mask,"eax");		# mask 32 lower bits

	&mov	($ap,$_ap);		# load input pointers
	&mov	($bp,$_bp);
	&mov	($np,$_np);

	&xor	($i,$i);		# i=0
	&xor	($j,$j);		# j=0

	&movd	($mul0,&DWP(0,$bp));		# bp[0]
	&movd	($mul1,&DWP(0,$ap));		# ap[0]
	&movd	($car1,&DWP(0,$np));		# np[0]

	&pmuludq($mul1,$mul0);			# ap[0]*bp[0]
	&movq	($car0,$mul1);
	&movq	($acc0,$mul1);			# I wish movd worked for
	&pand	($acc0,$mask);			# inter-register transfers

	&pmuludq($mul1,$_n0);			# *=n0

	&pmuludq($car1,$mul1);			# "t[0]"*np[0]*n0
	&paddq	($car1,$acc0);

	&movd	($acc1,&DWP(4,$np));		# np[1]
	&movd	($acc0,&DWP(4,$ap));		# ap[1]

	&psrlq	($car0,32);
	&psrlq	($car1,32);

	&inc	($j);				# j++
&set_label("1st");
	&pmuludq($acc0,$mul0);			# ap[j]*bp[0]
	&pmuludq($acc1,$mul1);			# np[j]*m1
	&paddq	($car0,$acc0);			# +=c0
	&paddq	($car1,$acc1);			# +=c1

	&movq	($acc0,$car0);
	&pand	($acc0,$mask);
	&movd	($acc1,&DWP(4,$np,$j,4));	# np[j+1]
	&paddq	($car1,$acc0);			# +=ap[j]*bp[0];
	&movd	($acc0,&DWP(4,$ap,$j,4));	# ap[j+1]
	&psrlq	($car0,32);
	&movd	(&DWP($frame-4,"esp",$j,4),$car1);	# tp[j-1]=
	&psrlq	($car1,32);

	&lea	($j,&DWP(1,$j));
	&cmp	($j,$num);
	&jl	(&label("1st"));

	&pmuludq($acc0,$mul0);			# ap[num-1]*bp[0]
	&pmuludq($acc1,$mul1);			# np[num-1]*m1
	&paddq	($car0,$acc0);			# +=c0
	&paddq	($car1,$acc1);			# +=c1

	&movq	($acc0,$car0);
	&pand	($acc0,$mask);
	&paddq	($car1,$acc0);			# +=ap[num-1]*bp[0];
	&movd	(&DWP($frame-4,"esp",$j,4),$car1);	# tp[num-2]=

	&psrlq	($car0,32);
	&psrlq	($car1,32);

	&paddq	($car1,$car0);
	&movq	(&DWP($frame,"esp",$num,4),$car1);	# tp[num].tp[num-1]
\f
	&inc	($i);				# i++
&set_label("outer");
	&xor	($j,$j);			# j=0

	&movd	($mul0,&DWP(0,$bp,$i,4));	# bp[i]
	&movd	($mul1,&DWP(0,$ap));		# ap[0]
	&movd	($temp,&DWP($frame,"esp"));	# tp[0]
	&movd	($car1,&DWP(0,$np));		# np[0]
	&pmuludq($mul1,$mul0);			# ap[0]*bp[i]

	&paddq	($mul1,$temp);			# +=tp[0]
	&movq	($acc0,$mul1);
	&movq	($car0,$mul1);
	&pand	($acc0,$mask);

	&pmuludq($mul1,$_n0);			# *=n0

	&pmuludq($car1,$mul1);
	&paddq	($car1,$acc0);

	&movd	($temp,&DWP($frame+4,"esp"));	# tp[1]
	&movd	($acc1,&DWP(4,$np));		# np[1]
	&movd	($acc0,&DWP(4,$ap));		# ap[1]

	&psrlq	($car0,32);
	&psrlq	($car1,32);
	&paddq	($car0,$temp);			# +=tp[1]

	&inc	($j);				# j++
	&dec	($num);
&set_label("inner");
	&pmuludq($acc0,$mul0);			# ap[j]*bp[i]
	&pmuludq($acc1,$mul1);			# np[j]*m1
	&paddq	($car0,$acc0);			# +=c0
	&paddq	($car1,$acc1);			# +=c1

	&movq	($acc0,$car0);
	&movd	($temp,&DWP($frame+4,"esp",$j,4));# tp[j+1]
	&pand	($acc0,$mask);
	&movd	($acc1,&DWP(4,$np,$j,4));	# np[j+1]
	&paddq	($car1,$acc0);			# +=ap[j]*bp[i]+tp[j]
	&movd	($acc0,&DWP(4,$ap,$j,4));	# ap[j+1]
	&psrlq	($car0,32);
	&movd	(&DWP($frame-4,"esp",$j,4),$car1);# tp[j-1]=
	&psrlq	($car1,32);
	&paddq	($car0,$temp);			# +=tp[j+1]

	&dec	($num);
	&lea	($j,&DWP(1,$j));		# j++
	&jnz	(&label("inner"));

	&mov	($num,$j);
	&pmuludq($acc0,$mul0);			# ap[num-1]*bp[i]
	&pmuludq($acc1,$mul1);			# np[num-1]*m1
	&paddq	($car0,$acc0);			# +=c0
	&paddq	($car1,$acc1);			# +=c1

	&movq	($acc0,$car0);
	&pand	($acc0,$mask);
	&paddq	($car1,$acc0);			# +=ap[num-1]*bp[i]+tp[num-1]
	&movd	(&DWP($frame-4,"esp",$j,4),$car1);	# tp[num-2]=
	&psrlq	($car0,32);
	&psrlq	($car1,32);

	&movd	($temp,&DWP($frame+4,"esp",$num,4));	# += tp[num]
	&paddq	($car1,$car0);
	&paddq	($car1,$temp);
	&movq	(&DWP($frame,"esp",$num,4),$car1);	# tp[num].tp[num-1]

	&lea	($i,&DWP(1,$i));		# i++
	&cmp	($i,$num);
	&jle	(&label("outer"));

	&emms	();				# done with mmx bank
	&jmp	(&label("common_tail"));

&set_label("non_sse2",16);
}
\f
if (0) {
	&mov	("esp",$_sp);
	&xor	("eax","eax");	# signal "not fast enough [yet]"
	&jmp	(&label("just_leave"));
	# While the below code provides competitive performance for
	# all key lengthes on modern cores, it's still a tad slower
	# for >=2048-bits keys on *elder* CPUs:-( "Competitive" means
	# compared to the original integer-only assembler. 512-bit
	# RSA sign is better by >=30%, but that's about all one can
	# say about all CPUs...
} else {
$inp="esi";	# integer path uses these registers differently
$word="edi";
$carry="ebp";

	&mov	($inp,$_ap);
	&lea	($carry,&DWP(1,$num));
	&mov	($word,$_bp);
	&xor	($j,$j);				# j=0
	&mov	("edx",$inp);
	&and	($carry,1);				# see if num is even
	&sub	("edx",$word);				# see if ap==bp
	&lea	("eax",&DWP(4,$word,$num,4));		# &bp[num]
	&or	($carry,"edx");
	&mov	($word,&DWP(0,$word));			# bp[0]
	&jz	(&label("bn_sqr_mont"));
	&mov	($_bpend,"eax");
	&mov	("eax",&DWP(0,$inp));
	&xor	("edx","edx");

&set_label("mull",16);
	&mov	($carry,"edx");
	&mul	($word);				# ap[j]*bp[0]
	&add	($carry,"eax");
	&lea	($j,&DWP(1,$j));
	&adc	("edx",0);
	&mov	("eax",&DWP(0,$inp,$j,4));		# ap[j+1]
	&cmp	($j,$num);
	&mov	(&DWP($frame-4,"esp",$j,4),$carry);	# tp[j]=
	&jl	(&label("mull"));

	&mov	($carry,"edx");
	&mul	($word);				# ap[num-1]*bp[0]
	 &mov	($word,$_n0);
	&add	("eax",$carry);
	 &mov	($inp,$_np);
	&adc	("edx",0);
	 &imul	($word,&DWP($frame,"esp"));		# n0*tp[0]

	&mov	(&DWP($frame,"esp",$num,4),"eax");	# tp[num-1]=
	&xor	($j,$j);
	&mov	(&DWP($frame+4,"esp",$num,4),"edx");	# tp[num]=
	&mov	(&DWP($frame+8,"esp",$num,4),$j);	# tp[num+1]=

	&mov	("eax",&DWP(0,$inp));			# np[0]
	&mul	($word);				# np[0]*m
	&add	("eax",&DWP($frame,"esp"));		# +=tp[0]
	&mov	("eax",&DWP(4,$inp));			# np[1]
	&adc	("edx",0);
	&inc	($j);

	&jmp	(&label("2ndmadd"));
\f\f
&set_label("1stmadd",16);
	&mov	($carry,"edx");
	&mul	($word);				# ap[j]*bp[i]
	&add	($carry,&DWP($frame,"esp",$j,4));	# +=tp[j]
	&lea	($j,&DWP(1,$j));
	&adc	("edx",0);
	&add	($carry,"eax");
	&mov	("eax",&DWP(0,$inp,$j,4));		# ap[j+1]
	&adc	("edx",0);
	&cmp	($j,$num);
	&mov	(&DWP($frame-4,"esp",$j,4),$carry);	# tp[j]=
	&jl	(&label("1stmadd"));

	&mov	($carry,"edx");
	&mul	($word);				# ap[num-1]*bp[i]
	&add	("eax",&DWP($frame,"esp",$num,4));	# +=tp[num-1]
	 &mov	($word,$_n0);
	&adc	("edx",0);
	 &mov	($inp,$_np);
	&add	($carry,"eax");
	&adc	("edx",0);
	 &imul	($word,&DWP($frame,"esp"));		# n0*tp[0]

	&xor	($j,$j);
	&add	("edx",&DWP($frame+4,"esp",$num,4));	# carry+=tp[num]
	&mov	(&DWP($frame,"esp",$num,4),$carry);	# tp[num-1]=
	&adc	($j,0);
	 &mov	("eax",&DWP(0,$inp));			# np[0]
	&mov	(&DWP($frame+4,"esp",$num,4),"edx");	# tp[num]=
	&mov	(&DWP($frame+8,"esp",$num,4),$j);	# tp[num+1]=

	&mul	($word);				# np[0]*m
	&add	("eax",&DWP($frame,"esp"));		# +=tp[0]
	&mov	("eax",&DWP(4,$inp));			# np[1]
	&adc	("edx",0);
	&mov	($j,1);
\f
&set_label("2ndmadd",16);
	&mov	($carry,"edx");
	&mul	($word);				# np[j]*m
	&add	($carry,&DWP($frame,"esp",$j,4));	# +=tp[j]
	&lea	($j,&DWP(1,$j));
	&adc	("edx",0);
	&add	($carry,"eax");
	&mov	("eax",&DWP(0,$inp,$j,4));		# np[j+1]
	&adc	("edx",0);
	&cmp	($j,$num);
	&mov	(&DWP($frame-8,"esp",$j,4),$carry);	# tp[j-1]=
	&jl	(&label("2ndmadd"));

	&mov	($carry,"edx");
	&mul	($word);				# np[j]*m
	&add	($carry,&DWP($frame,"esp",$j,4));	# +=tp[j]
	&adc	("edx",0);
	&add	($carry,"eax");
	&adc	("edx",0);
	&mov	(&DWP($frame-4,"esp",$num,4),$carry);	# tp[num-2]=

	&xor	("eax","eax");
	 &mov	($j,$_bp);				# &bp[i]
	&add	("edx",&DWP($frame+4,"esp",$num,4));	# carry+=tp[num]
	&adc	("eax",&DWP($frame+8,"esp",$num,4));	# +=tp[num+1]
	 &lea	($j,&DWP(4,$j));
	&mov	(&DWP($frame,"esp",$num,4),"edx");	# tp[num-1]=
	 &cmp	($j,$_bpend);
	&mov	(&DWP($frame+4,"esp",$num,4),"eax");	# tp[num]=
	&je	(&label("x86done"));

	&mov	($word,&DWP(0,$j));			# bp[i]
	&mov	($inp,$_ap);
	&mov	($_bp,$j);				# &bp[++i]
	&xor	($j,$j);
	&xor	("edx","edx");
	&mov	("eax",&DWP(0,$inp));
	&jmp	(&label("1stmadd"));
\f
&set_label("bn_sqr_mont",16);
$sbit=$num;
	&mov	($_num,$num);
	&mov	($_bp,$j);				# i=0

	&mov	("eax",$word);				# ap[0]
	&mul	($word);				# ap[0]*ap[0]
	&mov	(&DWP($frame,"esp"),"eax");		# tp[0]=
	&mov	($sbit,"edx");
	&shr	("edx",1);
	&and	($sbit,1);
	&inc	($j);
&set_label("sqr",16);
	&mov	("eax",&DWP(0,$inp,$j,4));		# ap[j]
	&mov	($carry,"edx");
	&mul	($word);				# ap[j]*ap[0]
	&add	("eax",$carry);
	&lea	($j,&DWP(1,$j));
	&adc	("edx",0);
	&lea	($carry,&DWP(0,$sbit,"eax",2));
	&shr	("eax",31);
	&cmp	($j,$_num);
	&mov	($sbit,"eax");
	&mov	(&DWP($frame-4,"esp",$j,4),$carry);	# tp[j]=
	&jl	(&label("sqr"));

	&mov	("eax",&DWP(0,$inp,$j,4));		# ap[num-1]
	&mov	($carry,"edx");
	&mul	($word);				# ap[num-1]*ap[0]
	&add	("eax",$carry);
	 &mov	($word,$_n0);
	&adc	("edx",0);
	 &mov	($inp,$_np);
	&lea	($carry,&DWP(0,$sbit,"eax",2));
	 &imul	($word,&DWP($frame,"esp"));		# n0*tp[0]
	&shr	("eax",31);
	&mov	(&DWP($frame,"esp",$j,4),$carry);	# tp[num-1]=

	&lea	($carry,&DWP(0,"eax","edx",2));
	 &mov	("eax",&DWP(0,$inp));			# np[0]
	&shr	("edx",31);
	&mov	(&DWP($frame+4,"esp",$j,4),$carry);	# tp[num]=
	&mov	(&DWP($frame+8,"esp",$j,4),"edx");	# tp[num+1]=

	&mul	($word);				# np[0]*m
	&add	("eax",&DWP($frame,"esp"));		# +=tp[0]
	&mov	($num,$j);
	&adc	("edx",0);
	&mov	("eax",&DWP(4,$inp));			# np[1]
	&mov	($j,1);
\f\f
&set_label("3rdmadd",16);
	&mov	($carry,"edx");
	&mul	($word);				# np[j]*m
	&add	($carry,&DWP($frame,"esp",$j,4));	# +=tp[j]
	&adc	("edx",0);
	&add	($carry,"eax");
	&mov	("eax",&DWP(4,$inp,$j,4));		# np[j+1]
	&adc	("edx",0);
	&mov	(&DWP($frame-4,"esp",$j,4),$carry);	# tp[j-1]=

	&mov	($carry,"edx");
	&mul	($word);				# np[j+1]*m
	&add	($carry,&DWP($frame+4,"esp",$j,4));	# +=tp[j+1]
	&lea	($j,&DWP(2,$j));
	&adc	("edx",0);
	&add	($carry,"eax");
	&mov	("eax",&DWP(0,$inp,$j,4));		# np[j+2]
	&adc	("edx",0);
	&cmp	($j,$num);
	&mov	(&DWP($frame-8,"esp",$j,4),$carry);	# tp[j]=
	&jl	(&label("3rdmadd"));

	&mov	($carry,"edx");
	&mul	($word);				# np[j]*m
	&add	($carry,&DWP($frame,"esp",$num,4));	# +=tp[num-1]
	&adc	("edx",0);
	&add	($carry,"eax");
	&adc	("edx",0);
	&mov	(&DWP($frame-4,"esp",$num,4),$carry);	# tp[num-2]=

	&mov	($j,$_bp);				# i
	&xor	("eax","eax");
	&mov	($inp,$_ap);
	&add	("edx",&DWP($frame+4,"esp",$num,4));	# carry+=tp[num]
	&adc	("eax",&DWP($frame+8,"esp",$num,4));	# +=tp[num+1]
	&mov	(&DWP($frame,"esp",$num,4),"edx");	# tp[num-1]=
	&cmp	($j,$num);
	&mov	(&DWP($frame+4,"esp",$num,4),"eax");	# tp[num]=
	&je	(&label("x86done"));
\f
	&mov	($word,&DWP(4,$inp,$j,4));		# ap[i]
	&lea	($j,&DWP(1,$j));
	&mov	("eax",$word);
	&mov	($_bp,$j);				# ++i
	&mul	($word);				# ap[i]*ap[i]
	&add	("eax",&DWP($frame,"esp",$j,4));	# +=tp[i]
	&adc	("edx",0);
	&mov	(&DWP($frame,"esp",$j,4),"eax");	# tp[i]=
	&xor	($carry,$carry);
	&cmp	($j,$num);
	&lea	($j,&DWP(1,$j));
	&je	(&label("sqrlast"));

	&mov	($sbit,"edx");				# zaps $num
	&shr	("edx",1);
	&and	($sbit,1);
&set_label("sqradd",16);
	&mov	("eax",&DWP(0,$inp,$j,4));		# ap[j]
	&mov	($carry,"edx");
	&mul	($word);				# ap[j]*ap[i]
	&add	("eax",$carry);
	&lea	($j,&DWP(1,$j));
	&adc	("edx",0);
	&lea	($carry,&DWP(0,$sbit,"eax",2));
	&shr	("eax",31);
	&add	($carry,&DWP($frame-4,"esp",$j,4));	# +=tp[j]
	&adc	("eax",0);
	&cmp	($j,$_num);
	&mov	(&DWP($frame-4,"esp",$j,4),$carry);	# tp[j]=
	&mov	($sbit,"eax");
	&jle	(&label("sqradd"));

	&mov	($carry,"edx");
	&lea	("edx",&DWP(0,$sbit,"edx",2));
	&shr	($carry,31);
&set_label("sqrlast");
	&mov	($word,$_n0);
	&mov	($inp,$_np);
	&imul	($word,&DWP($frame,"esp"));		# n0*tp[0]

	&add	("edx",&DWP($frame,"esp",$j,4));	# +=tp[num]
	&mov	("eax",&DWP(0,$inp));			# np[0]
	&adc	($carry,0);
	&mov	(&DWP($frame,"esp",$j,4),"edx");	# tp[num]=
	&mov	(&DWP($frame+4,"esp",$j,4),$carry);	# tp[num+1]=

	&mul	($word);				# np[0]*m
	&add	("eax",&DWP($frame,"esp"));		# +=tp[0]
	&lea	($num,&DWP(-1,$j));
	&adc	("edx",0);
	&mov	($j,1);
	&mov	("eax",&DWP(4,$inp));			# np[1]

	&jmp	(&label("3rdmadd"));
\f
&set_label("x86done",4);
	&mov	($np,$_np);	# make adjustments for tail processing
}

&set_label("common_tail",16);
	&mov	("esi",&DWP($frame+4,"esp",$num,4));# load upmost overflow bit
	&mov	($rp,$_rp);			# load result pointer
						# [$ap and $bp are zapped]
	&xor	($i,$i);			# i=0
	&mov	($j,$num);			# j=num-1
	&cmp	("esi",0);			# clears CF unconditionally
	&jnz	(&label("sub"));
	&mov	("eax",&DWP($frame,"esp",$j,4));
	&cmp	("eax",&DWP(0,$np,$j,4));	# tp[num-1]-np[num-1]?
	&jae	(&label("sub"));		# if taken CF is cleared
&set_label("copy",16);
	&mov	("eax",&DWP($frame,"esp",$j,4));
	&mov	(&DWP(0,$rp,$j,4),"eax");	# rp[i]=tp[i]
	&mov	(&DWP($frame,"esp",$j,4),$j);	# zap temporary vector
	&dec	($j);
	&jge	(&label("copy"));
	&jmp	(&label("exit"));

&set_label("sub",16);
	&mov	("eax",&DWP($frame,"esp",$i,4));
	&sbb	("eax",&DWP(0,$np,$i,4));
	&mov	(&DWP(0,$rp,$i,4),"eax");	# rp[i]=tp[i]-np[i]
	&lea	($i,&DWP(1,$i));		# i++
	&dec	($j);				# doesn't affect CF!
	&jge	(&label("sub"));
	&mov	($j,$num);			# j=num-1
	&sbb	("esi",0);			# esi holds upmost overflow bit
	&jc	(&label("copy"));
&set_label("zap",16);
	&mov	(&DWP($frame,"esp",$j,4),$i);	# zap temporary vector
	&dec	($j);
	&jge	(&label("zap"));

&set_label("exit",4);
	&mov	("esp",$_sp);		# pull saved stack pointer
	&mov	("eax",1);
&set_label("just_leave");
&function_end("bn_mul_mont");

&asciz("Montgomery Multiplication for x86, CRYPTOGAMS by <appro\@openssl.org>");

&asm_finish();
Commit	Line	Data
54f3d200 AP	1	#!/usr/bin/env perl
	2
	3	# ====================================================================
	4	# Written by Andy Polyakov <appro@fy.chalmers.se> for the OpenSSL
48d2335d AP	5	# project. The module is, however, dual licensed under OpenSSL and
	6	# CRYPTOGAMS licenses depending on where you obtain it. For further
	7	# details see http://www.openssl.org/~appro/cryptogams/.
54f3d200 AP	8	# ====================================================================
54f3d200 AP	9
35593b33 AP	10	# October 2005
35593b33 AP	11	#
54f3d200 AP	12	# This is a "teaser" code, as it can be improved in several ways...
	13	# First of all non-SSE2 path should be implemented (yes, for now it
	14	# performs Montgomery multiplication/convolution only on SSE2-capable
	15	# CPUs such as P4, others fall down to original code). Then inner loop
	16	# can be unrolled and modulo-scheduled to improve ILP and possibly
	17	# moved to 128-bit XMM register bank (though it would require input
	18	# rearrangement and/or increase bus bandwidth utilization). Dedicated
	19	# squaring procedure should give further performance improvement...
	20	# Yet, for being draft, the code improves rsa512 sign benchmark by
	21	# 110%(!), rsa1024 one - by 70% and rsa4096 - by 20%:-)
	22
1702c8c4 AP	23	# December 2006
	24	#
	25	# Modulo-scheduling SSE2 loops results in further 15-20% improvement.
	26	# Integer-only code [being equipped with dedicated squaring procedure]
	27	# gives >=30% on rsa512 sign benchmark...
	28
	29	$0 =~ m/(.*[\/\\])[^\/\\]+$/; $dir=$1;
	30	push(@INC,"${dir}","${dir}../../perlasm");
54f3d200 AP	31	require "x86asm.pl";
	32
	33	&asm_init($ARGV[0],$0);
	34
	35	$sse2=0;
	36	for (@ARGV) { $sse2=1 if (/-DOPENSSL_IA32_SSE2/); }
	37
	38	&external_label("OPENSSL_ia32cap_P") if ($sse2);
	39
1702c8c4	40	&function_begin("bn_mul_mont");
54f3d200	41
48d2335d	42	$i="edx";
54f3d200 AP	43	$j="ecx";
	44	$ap="esi";
	45	$rp="edi"; $bp="edi"; # overlapping variables!!!
48d2335d AP	46	$np="ebp";
48d2335d AP	47	$num="ebx";
54f3d200	48
34736de4 AP	49	$_rp=&DWP(4*0,"esp"); # stack top layout
	50	$_ap=&DWP(4*1,"esp");
	51	$_bp=&DWP(4*2,"esp");
	52	$_np=&DWP(4*3,"esp");
	53	$_n0=&DWP(4*4,"esp");
	54	$_num=&DWP(4*5,"esp");
	55	$_sp=&DWP(4*6,"esp");
48d2335d	56	$_bpend=&DWP(4*7,"esp");
34736de4	57	$frame=32; # size of above frame rounded up to 16n
54f3d200	58
48d2335d AP	59	&xor ("eax","eax");
48d2335d AP	60	&mov ("edi",&wparam(5)); # int num
1702c8c4 AP	61	&cmp ("edi",4);
1702c8c4 AP	62	&jl (&label("just_leave"));
54f3d200 AP	63
	64	################################# load argument block...
	65	&mov ("eax",&wparam(0)); # BN_ULONG *rp
	66	&mov ("ebx",&wparam(1)); # const BN_ULONG *ap
	67	&mov ("ecx",&wparam(2)); # const BN_ULONG *bp
	68	&mov ("edx",&wparam(3)); # const BN_ULONG *np
4d524040	69	&mov ("esi",&wparam(4)); # const BN_ULONG *n0
48d2335d	70	#&mov ("edi",&wparam(5)); # int num
54f3d200	71
48d2335d AP	72	&mov ("ebp","esp"); # saved stack pointer!
	73	&add ("edi",2); # extra two words on top of tp
	74	&neg ("edi");
	75	&lea ("esp",&DWP(-$frame,"esp","edi",4)); # alloca($frame+4*(num+2))
	76	&neg ("edi");
	77	&and ("esp",-4096); # minimize TLB utilization
54f3d200	78
4d524040	79	&mov ("esi",&DWP(0,"esi")); # pull n0[0]
54f3d200 AP	80	&mov ($_rp,"eax"); # ... save a copy of argument block
	81	&mov ($_ap,"ebx");
	82	&mov ($_bp,"ecx");
	83	&mov ($_np,"edx");
	84	&mov ($_n0,"esi");
1702c8c4	85	&lea ($num,&DWP(-3,"edi")); # num=num-1 to assist modulo-scheduling
48d2335d AP	86	#&mov ($_num,$num); # redundant as $num is not reused
48d2335d AP	87	&mov ($_sp,"ebp"); # saved stack pointer!
1702c8c4	88	\f
48d2335d AP	89	if($sse2) {
	90	$acc0="mm0"; # mmx register bank layout
	91	$acc1="mm1";
	92	$car0="mm2";
	93	$car1="mm3";
	94	$mul0="mm4";
	95	$mul1="mm5";
	96	$temp="mm6";
	97	$mask="mm7";
	98
	99	&picmeup("eax","OPENSSL_ia32cap_P");
	100	&bt (&DWP(0,"eax"),26);
	101	&jnc (&label("non_sse2"));
54f3d200 AP	102
	103	&mov ("eax",-1);
	104	&movd ($mask,"eax"); # mask 32 lower bits
	105
	106	&mov ($ap,$_ap); # load input pointers
	107	&mov ($bp,$_bp);
	108	&mov ($np,$_np);
	109
	110	&xor ($i,$i); # i=0
	111	&xor ($j,$j); # j=0
	112
	113	&movd ($mul0,&DWP(0,$bp)); # bp[0]
	114	&movd ($mul1,&DWP(0,$ap)); # ap[0]
	115	&movd ($car1,&DWP(0,$np)); # np[0]
	116
	117	&pmuludq($mul1,$mul0); # ap[0]*bp[0]
	118	&movq ($car0,$mul1);
	119	&movq ($acc0,$mul1); # I wish movd worked for
	120	&pand ($acc0,$mask); # inter-register transfers
	121
	122	&pmuludq($mul1,$_n0); # *=n0
	123
	124	&pmuludq($car1,$mul1); # "t[0]"np[0]n0
	125	&paddq ($car1,$acc0);
	126
1702c8c4 AP	127	&movd ($acc1,&DWP(4,$np)); # np[1]
	128	&movd ($acc0,&DWP(4,$ap)); # ap[1]
	129
54f3d200 AP	130	&psrlq ($car0,32);
	131	&psrlq ($car1,32);
	132
	133	&inc ($j); # j++
	134	&set_label("1st");
54f3d200 AP	135	&pmuludq($acc0,$mul0); # ap[j]*bp[0]
54f3d200 AP	136	&pmuludq($acc1,$mul1); # np[j]*m1
54f3d200	137	&paddq ($car0,$acc0); # +=c0
1702c8c4 AP	138	&paddq ($car1,$acc1); # +=c1
1702c8c4 AP	139
54f3d200 AP	140	&movq ($acc0,$car0);
54f3d200 AP	141	&pand ($acc0,$mask);
1702c8c4	142	&movd ($acc1,&DWP(4,$np,$j,4)); # np[j+1]
54f3d200	143	&paddq ($car1,$acc0); # +=ap[j]*bp[0];
1702c8c4	144	&movd ($acc0,&DWP(4,$ap,$j,4)); # ap[j+1]
54f3d200	145	&psrlq ($car0,32);
1702c8c4	146	&movd (&DWP($frame-4,"esp",$j,4),$car1); # tp[j-1]=
54f3d200 AP	147	&psrlq ($car1,32);
	148
	149	&lea ($j,&DWP(1,$j));
	150	&cmp ($j,$num);
	151	&jl (&label("1st"));
	152
1702c8c4 AP	153	&pmuludq($acc0,$mul0); # ap[num-1]*bp[0]
	154	&pmuludq($acc1,$mul1); # np[num-1]*m1
	155	&paddq ($car0,$acc0); # +=c0
	156	&paddq ($car1,$acc1); # +=c1
54f3d200	157
1702c8c4 AP	158	&movq ($acc0,$car0);
	159	&pand ($acc0,$mask);
	160	&paddq ($car1,$acc0); # +=ap[num-1]*bp[0];
	161	&movd (&DWP($frame-4,"esp",$j,4),$car1); # tp[num-2]=
	162
	163	&psrlq ($car0,32);
	164	&psrlq ($car1,32);
	165
	166	&paddq ($car1,$car0);
	167	&movq (&DWP($frame,"esp",$num,4),$car1); # tp[num].tp[num-1]
	168	\f
54f3d200 AP	169	&inc ($i); # i++
	170	&set_label("outer");
	171	&xor ($j,$j); # j=0
	172
	173	&movd ($mul0,&DWP(0,$bp,$i,4)); # bp[i]
	174	&movd ($mul1,&DWP(0,$ap)); # ap[0]
34736de4 AP	175	&movd ($temp,&DWP($frame,"esp")); # tp[0]
34736de4 AP	176	&movd ($car1,&DWP(0,$np)); # np[0]
54f3d200 AP	177	&pmuludq($mul1,$mul0); # ap[0]*bp[i]
	178
	179	&paddq ($mul1,$temp); # +=tp[0]
	180	&movq ($acc0,$mul1);
	181	&movq ($car0,$mul1);
	182	&pand ($acc0,$mask);
	183
	184	&pmuludq($mul1,$_n0); # *=n0
	185
	186	&pmuludq($car1,$mul1);
	187	&paddq ($car1,$acc0);
	188
1702c8c4 AP	189	&movd ($temp,&DWP($frame+4,"esp")); # tp[1]
	190	&movd ($acc1,&DWP(4,$np)); # np[1]
	191	&movd ($acc0,&DWP(4,$ap)); # ap[1]
	192
54f3d200 AP	193	&psrlq ($car0,32);
54f3d200 AP	194	&psrlq ($car1,32);
1702c8c4	195	&paddq ($car0,$temp); # +=tp[1]
54f3d200 AP	196
54f3d200 AP	197	&inc ($j); # j++
1702c8c4	198	&dec ($num);
54f3d200	199	&set_label("inner");
54f3d200 AP	200	&pmuludq($acc0,$mul0); # ap[j]*bp[i]
54f3d200 AP	201	&pmuludq($acc1,$mul1); # np[j]*m1
54f3d200	202	&paddq ($car0,$acc0); # +=c0
1702c8c4 AP	203	&paddq ($car1,$acc1); # +=c1
1702c8c4 AP	204
54f3d200	205	&movq ($acc0,$car0);
1702c8c4	206	&movd ($temp,&DWP($frame+4,"esp",$j,4));# tp[j+1]
54f3d200	207	&pand ($acc0,$mask);
1702c8c4	208	&movd ($acc1,&DWP(4,$np,$j,4)); # np[j+1]
54f3d200	209	&paddq ($car1,$acc0); # +=ap[j]*bp[i]+tp[j]
1702c8c4	210	&movd ($acc0,&DWP(4,$ap,$j,4)); # ap[j+1]
54f3d200	211	&psrlq ($car0,32);
1702c8c4	212	&movd (&DWP($frame-4,"esp",$j,4),$car1);# tp[j-1]=
54f3d200	213	&psrlq ($car1,32);
1702c8c4	214	&paddq ($car0,$temp); # +=tp[j+1]
54f3d200	215
1702c8c4	216	&dec ($num);
54f3d200	217	&lea ($j,&DWP(1,$j)); # j++
1702c8c4 AP	218	&jnz (&label("inner"));
	219
	220	&mov ($num,$j);
	221	&pmuludq($acc0,$mul0); # ap[num-1]*bp[i]
	222	&pmuludq($acc1,$mul1); # np[num-1]*m1
	223	&paddq ($car0,$acc0); # +=c0
	224	&paddq ($car1,$acc1); # +=c1
	225
	226	&movq ($acc0,$car0);
	227	&pand ($acc0,$mask);
	228	&paddq ($car1,$acc0); # +=ap[num-1]*bp[i]+tp[num-1]
	229	&movd (&DWP($frame-4,"esp",$j,4),$car1); # tp[num-2]=
	230	&psrlq ($car0,32);
	231	&psrlq ($car1,32);
54f3d200	232
1702c8c4	233	&movd ($temp,&DWP($frame+4,"esp",$num,4)); # += tp[num]
54f3d200 AP	234	&paddq ($car1,$car0);
54f3d200 AP	235	&paddq ($car1,$temp);
1702c8c4	236	&movq (&DWP($frame,"esp",$num,4),$car1); # tp[num].tp[num-1]
54f3d200 AP	237
	238	&lea ($i,&DWP(1,$i)); # i++
	239	&cmp ($i,$num);
1702c8c4	240	&jle (&label("outer"));
54f3d200 AP	241
54f3d200 AP	242	&emms (); # done with mmx bank
48d2335d AP	243	&jmp (&label("common_tail"));
	244
	245	&set_label("non_sse2",16);
	246	}
1702c8c4 AP	247	\f
1702c8c4 AP	248	if (0) {
48d2335d AP	249	&mov ("esp",$_sp);
	250	&xor ("eax","eax"); # signal "not fast enough [yet]"
	251	&jmp (&label("just_leave"));
1702c8c4 AP	252	# While the below code provides competitive performance for
	253	# all key lengthes on modern cores, it's still a tad slower
	254	# for >=2048-bits keys on elder CPUs:-( "Competitive" means
	255	# compared to the original integer-only assembler. 512-bit
	256	# RSA sign is better by >=30%, but that's about all one can
	257	# say about all CPUs...
48d2335d AP	258	} else {
	259	$inp="esi"; # integer path uses these registers differently
	260	$word="edi";
	261	$carry="ebp";
	262
48d2335d	263	&mov ($inp,$_ap);
1702c8c4	264	&lea ($carry,&DWP(1,$num));
48d2335d	265	&mov ($word,$_bp);
1702c8c4 AP	266	&xor ($j,$j); # j=0
	267	&mov ("edx",$inp);
	268	&and ($carry,1); # see if num is even
	269	&sub ("edx",$word); # see if ap==bp
48d2335d	270	&lea ("eax",&DWP(4,$word,$num,4)); # &bp[num]
1702c8c4	271	&or ($carry,"edx");
48d2335d	272	&mov ($word,&DWP(0,$word)); # bp[0]
1702c8c4	273	&jz (&label("bn_sqr_mont"));
48d2335d	274	&mov ($_bpend,"eax");
1702c8c4	275	&mov ("eax",&DWP(0,$inp));
48d2335d AP	276	&xor ("edx","edx");
	277
	278	&set_label("mull",16);
48d2335d AP	279	&mov ($carry,"edx");
48d2335d AP	280	&mul ($word); # ap[j]*bp[0]
1702c8c4	281	&add ($carry,"eax");
48d2335d	282	&lea ($j,&DWP(1,$j));
48d2335d	283	&adc ("edx",0);
1702c8c4	284	&mov ("eax",&DWP(0,$inp,$j,4)); # ap[j+1]
48d2335d	285	&cmp ($j,$num);
1702c8c4 AP	286	&mov (&DWP($frame-4,"esp",$j,4),$carry); # tp[j]=
1702c8c4 AP	287	&jl (&label("mull"));
48d2335d	288
48d2335d AP	289	&mov ($carry,"edx");
48d2335d AP	290	&mul ($word); # ap[num-1]*bp[0]
1702c8c4	291	&mov ($word,$_n0);
48d2335d	292	&add ("eax",$carry);
1702c8c4	293	&mov ($inp,$_np);
48d2335d	294	&adc ("edx",0);
1702c8c4	295	&imul ($word,&DWP($frame,"esp")); # n0*tp[0]
48d2335d AP	296
	297	&mov (&DWP($frame,"esp",$num,4),"eax"); # tp[num-1]=
	298	&xor ($j,$j);
	299	&mov (&DWP($frame+4,"esp",$num,4),"edx"); # tp[num]=
	300	&mov (&DWP($frame+8,"esp",$num,4),$j); # tp[num+1]=
	301
	302	&mov ("eax",&DWP(0,$inp)); # np[0]
	303	&mul ($word); # np[0]*m
	304	&add ("eax",&DWP($frame,"esp")); # +=tp[0]
1702c8c4	305	&mov ("eax",&DWP(4,$inp)); # np[1]
48d2335d	306	&adc ("edx",0);
1702c8c4	307	&inc ($j);
48d2335d AP	308
48d2335d AP	309	&jmp (&label("2ndmadd"));
1702c8c4	310	\f\f
48d2335d	311	&set_label("1stmadd",16);
48d2335d AP	312	&mov ($carry,"edx");
48d2335d AP	313	&mul ($word); # ap[j]*bp[i]
1702c8c4	314	&add ($carry,&DWP($frame,"esp",$j,4)); # +=tp[j]
48d2335d	315	&lea ($j,&DWP(1,$j));
48d2335d	316	&adc ("edx",0);
1702c8c4 AP	317	&add ($carry,"eax");
1702c8c4 AP	318	&mov ("eax",&DWP(0,$inp,$j,4)); # ap[j+1]
48d2335d	319	&adc ("edx",0);
48d2335d	320	&cmp ($j,$num);
1702c8c4 AP	321	&mov (&DWP($frame-4,"esp",$j,4),$carry); # tp[j]=
1702c8c4 AP	322	&jl (&label("1stmadd"));
48d2335d	323
48d2335d AP	324	&mov ($carry,"edx");
	325	&mul ($word); # ap[num-1]*bp[i]
	326	&add ("eax",&DWP($frame,"esp",$num,4)); # +=tp[num-1]
1702c8c4	327	&mov ($word,$_n0);
48d2335d	328	&adc ("edx",0);
1702c8c4 AP	329	&mov ($inp,$_np);
1702c8c4 AP	330	&add ($carry,"eax");
48d2335d	331	&adc ("edx",0);
1702c8c4	332	&imul ($word,&DWP($frame,"esp")); # n0*tp[0]
48d2335d AP	333
	334	&xor ($j,$j);
	335	&add ("edx",&DWP($frame+4,"esp",$num,4)); # carry+=tp[num]
1702c8c4	336	&mov (&DWP($frame,"esp",$num,4),$carry); # tp[num-1]=
48d2335d	337	&adc ($j,0);
1702c8c4	338	&mov ("eax",&DWP(0,$inp)); # np[0]
48d2335d AP	339	&mov (&DWP($frame+4,"esp",$num,4),"edx"); # tp[num]=
	340	&mov (&DWP($frame+8,"esp",$num,4),$j); # tp[num+1]=
	341
48d2335d AP	342	&mul ($word); # np[0]*m
48d2335d AP	343	&add ("eax",&DWP($frame,"esp")); # +=tp[0]
1702c8c4	344	&mov ("eax",&DWP(4,$inp)); # np[1]
48d2335d AP	345	&adc ("edx",0);
48d2335d AP	346	&mov ($j,1);
1702c8c4	347	\f
48d2335d	348	&set_label("2ndmadd",16);
48d2335d AP	349	&mov ($carry,"edx");
48d2335d AP	350	&mul ($word); # np[j]*m
1702c8c4	351	&add ($carry,&DWP($frame,"esp",$j,4)); # +=tp[j]
48d2335d	352	&lea ($j,&DWP(1,$j));
48d2335d	353	&adc ("edx",0);
1702c8c4 AP	354	&add ($carry,"eax");
1702c8c4 AP	355	&mov ("eax",&DWP(0,$inp,$j,4)); # np[j+1]
48d2335d	356	&adc ("edx",0);
48d2335d	357	&cmp ($j,$num);
1702c8c4 AP	358	&mov (&DWP($frame-8,"esp",$j,4),$carry); # tp[j-1]=
1702c8c4 AP	359	&jl (&label("2ndmadd"));
48d2335d	360
48d2335d	361	&mov ($carry,"edx");
1702c8c4 AP	362	&mul ($word); # np[j]*m
1702c8c4 AP	363	&add ($carry,&DWP($frame,"esp",$j,4)); # +=tp[j]
48d2335d	364	&adc ("edx",0);
1702c8c4	365	&add ($carry,"eax");
48d2335d	366	&adc ("edx",0);
1702c8c4	367	&mov (&DWP($frame-4,"esp",$num,4),$carry); # tp[num-2]=
48d2335d AP	368
48d2335d AP	369	&xor ("eax","eax");
1702c8c4	370	&mov ($j,$_bp); # &bp[i]
48d2335d AP	371	&add ("edx",&DWP($frame+4,"esp",$num,4)); # carry+=tp[num]
48d2335d AP	372	&adc ("eax",&DWP($frame+8,"esp",$num,4)); # +=tp[num+1]
1702c8c4	373	&lea ($j,&DWP(4,$j));
48d2335d	374	&mov (&DWP($frame,"esp",$num,4),"edx"); # tp[num-1]=
1702c8c4	375	&cmp ($j,$_bpend);
48d2335d	376	&mov (&DWP($frame+4,"esp",$num,4),"eax"); # tp[num]=
48d2335d	377	&je (&label("x86done"));
1702c8c4 AP	378
1702c8c4 AP	379	&mov ($word,&DWP(0,$j)); # bp[i]
48d2335d	380	&mov ($inp,$_ap);
1702c8c4	381	&mov ($_bp,$j); # &bp[++i]
48d2335d AP	382	&xor ($j,$j);
48d2335d AP	383	&xor ("edx","edx");
1702c8c4	384	&mov ("eax",&DWP(0,$inp));
48d2335d	385	&jmp (&label("1stmadd"));
1702c8c4 AP	386	\f
	387	&set_label("bn_sqr_mont",16);
	388	$sbit=$num;
	389	&mov ($_num,$num);
	390	&mov ($_bp,$j); # i=0
	391
	392	&mov ("eax",$word); # ap[0]
	393	&mul ($word); # ap[0]*ap[0]
	394	&mov (&DWP($frame,"esp"),"eax"); # tp[0]=
	395	&mov ($sbit,"edx");
	396	&shr ("edx",1);
	397	&and ($sbit,1);
	398	&inc ($j);
	399	&set_label("sqr",16);
	400	&mov ("eax",&DWP(0,$inp,$j,4)); # ap[j]
	401	&mov ($carry,"edx");
	402	&mul ($word); # ap[j]*ap[0]
	403	&add ("eax",$carry);
	404	&lea ($j,&DWP(1,$j));
	405	&adc ("edx",0);
	406	&lea ($carry,&DWP(0,$sbit,"eax",2));
	407	&shr ("eax",31);
	408	&cmp ($j,$_num);
	409	&mov ($sbit,"eax");
	410	&mov (&DWP($frame-4,"esp",$j,4),$carry); # tp[j]=
	411	&jl (&label("sqr"));
	412
	413	&mov ("eax",&DWP(0,$inp,$j,4)); # ap[num-1]
	414	&mov ($carry,"edx");
	415	&mul ($word); # ap[num-1]*ap[0]
	416	&add ("eax",$carry);
	417	&mov ($word,$_n0);
	418	&adc ("edx",0);
	419	&mov ($inp,$_np);
	420	&lea ($carry,&DWP(0,$sbit,"eax",2));
	421	&imul ($word,&DWP($frame,"esp")); # n0*tp[0]
	422	&shr ("eax",31);
	423	&mov (&DWP($frame,"esp",$j,4),$carry); # tp[num-1]=
	424
	425	&lea ($carry,&DWP(0,"eax","edx",2));
	426	&mov ("eax",&DWP(0,$inp)); # np[0]
	427	&shr ("edx",31);
	428	&mov (&DWP($frame+4,"esp",$j,4),$carry); # tp[num]=
	429	&mov (&DWP($frame+8,"esp",$j,4),"edx"); # tp[num+1]=
	430
	431	&mul ($word); # np[0]*m
	432	&add ("eax",&DWP($frame,"esp")); # +=tp[0]
	433	&mov ($num,$j);
	434	&adc ("edx",0);
	435	&mov ("eax",&DWP(4,$inp)); # np[1]
	436	&mov ($j,1);
	437	\f\f
	438	&set_label("3rdmadd",16);
	439	&mov ($carry,"edx");
	440	&mul ($word); # np[j]*m
	441	&add ($carry,&DWP($frame,"esp",$j,4)); # +=tp[j]
	442	&adc ("edx",0);
	443	&add ($carry,"eax");
	444	&mov ("eax",&DWP(4,$inp,$j,4)); # np[j+1]
	445	&adc ("edx",0);
	446	&mov (&DWP($frame-4,"esp",$j,4),$carry); # tp[j-1]=
	447
	448	&mov ($carry,"edx");
	449	&mul ($word); # np[j+1]*m
450	&add ($carry,&DWP($frame+4,"esp",$j,4)); # +=tp[j+1]
451	&lea ($j,&DWP(2,$j));
452	&adc ("edx",0);
453	&add ($carry,"eax");
454	&mov ("eax",&DWP(0,$inp,$j,4)); # np[j+2]
455	&adc ("edx",0);
456	&cmp ($j,$num);
457	&mov (&DWP($frame-8,"esp",$j,4),$carry); # tp[j]=
458	&jl (&label("3rdmadd"));
459
460	&mov ($carry,"edx");
461	&mul ($word); # np[j]*m
462	&add ($carry,&DWP($frame,"esp",$num,4)); # +=tp[num-1]
463	&adc ("edx",0);
464	&add ($carry,"eax");
465	&adc ("edx",0);
466	&mov (&DWP($frame-4,"esp",$num,4),$carry); # tp[num-2]=
467
468	&mov ($j,$_bp); # i
469	&xor ("eax","eax");
470	&mov ($inp,$_ap);
471	&add ("edx",&DWP($frame+4,"esp",$num,4)); # carry+=tp[num]
472	&adc ("eax",&DWP($frame+8,"esp",$num,4)); # +=tp[num+1]
473	&mov (&DWP($frame,"esp",$num,4),"edx"); # tp[num-1]=
474	&cmp ($j,$num);
475	&mov (&DWP($frame+4,"esp",$num,4),"eax"); # tp[num]=
476	&je (&label("x86done"));
477	\f
478	&mov ($word,&DWP(4,$inp,$j,4)); # ap[i]
479	&lea ($j,&DWP(1,$j));
480	&mov ("eax",$word);
481	&mov ($_bp,$j); # ++i
482	&mul ($word); # ap[i]*ap[i]
483	&add ("eax",&DWP($frame,"esp",$j,4)); # +=tp[i]
484	&adc ("edx",0);
485	&mov (&DWP($frame,"esp",$j,4),"eax"); # tp[i]=
486	&xor ($carry,$carry);
487	&cmp ($j,$num);
488	&lea ($j,&DWP(1,$j));
489	&je (&label("sqrlast"));
48d2335d	490
1702c8c4 AP	491	&mov ($sbit,"edx"); # zaps $num
	492	&shr ("edx",1);
	493	&and ($sbit,1);
	494	&set_label("sqradd",16);
	495	&mov ("eax",&DWP(0,$inp,$j,4)); # ap[j]
	496	&mov ($carry,"edx");
	497	&mul ($word); # ap[j]*ap[i]
	498	&add ("eax",$carry);
	499	&lea ($j,&DWP(1,$j));
	500	&adc ("edx",0);
	501	&lea ($carry,&DWP(0,$sbit,"eax",2));
	502	&shr ("eax",31);
	503	&add ($carry,&DWP($frame-4,"esp",$j,4)); # +=tp[j]
	504	&adc ("eax",0);
	505	&cmp ($j,$_num);
	506	&mov (&DWP($frame-4,"esp",$j,4),$carry); # tp[j]=
	507	&mov ($sbit,"eax");
	508	&jle (&label("sqradd"));
	509
	510	&mov ($carry,"edx");
	511	&lea ("edx",&DWP(0,$sbit,"edx",2));
	512	&shr ($carry,31);
	513	&set_label("sqrlast");
	514	&mov ($word,$_n0);
	515	&mov ($inp,$_np);
	516	&imul ($word,&DWP($frame,"esp")); # n0*tp[0]
	517
	518	&add ("edx",&DWP($frame,"esp",$j,4)); # +=tp[num]
	519	&mov ("eax",&DWP(0,$inp)); # np[0]
	520	&adc ($carry,0);
	521	&mov (&DWP($frame,"esp",$j,4),"edx"); # tp[num]=
	522	&mov (&DWP($frame+4,"esp",$j,4),$carry); # tp[num+1]=
	523
	524	&mul ($word); # np[0]*m
	525	&add ("eax",&DWP($frame,"esp")); # +=tp[0]
	526	&lea ($num,&DWP(-1,$j));
	527	&adc ("edx",0);
	528	&mov ($j,1);
	529	&mov ("eax",&DWP(4,$inp)); # np[1]
	530
	531	&jmp (&label("3rdmadd"));
	532	\f
	533	&set_label("x86done",4);
48d2335d	534	&mov ($np,$_np); # make adjustments for tail processing
48d2335d AP	535	}
	536
	537	&set_label("common_tail",16);
1702c8c4	538	&mov ("esi",&DWP($frame+4,"esp",$num,4));# load upmost overflow bit
54f3d200 AP	539	&mov ($rp,$_rp); # load result pointer
	540	# [$ap and $bp are zapped]
	541	&xor ($i,$i); # i=0
1702c8c4	542	&mov ($j,$num); # j=num-1
54f3d200 AP	543	&cmp ("esi",0); # clears CF unconditionally
54f3d200 AP	544	&jnz (&label("sub"));
34736de4	545	&mov ("eax",&DWP($frame,"esp",$j,4));
54f3d200 AP	546	&cmp ("eax",&DWP(0,$np,$j,4)); # tp[num-1]-np[num-1]?
54f3d200 AP	547	&jae (&label("sub")); # if taken CF is cleared
48d2335d	548	&set_label("copy",16);
34736de4	549	&mov ("eax",&DWP($frame,"esp",$j,4));
54f3d200	550	&mov (&DWP(0,$rp,$j,4),"eax"); # rp[i]=tp[i]
34736de4	551	&mov (&DWP($frame,"esp",$j,4),$j); # zap temporary vector
54f3d200 AP	552	&dec ($j);
54f3d200 AP	553	&jge (&label("copy"));
48d2335d	554	&jmp (&label("exit"));
54f3d200	555
48d2335d	556	&set_label("sub",16);
34736de4	557	&mov ("eax",&DWP($frame,"esp",$i,4));
54f3d200 AP	558	&sbb ("eax",&DWP(0,$np,$i,4));
	559	&mov (&DWP(0,$rp,$i,4),"eax"); # rp[i]=tp[i]-np[i]
	560	&lea ($i,&DWP(1,$i)); # i++
	561	&dec ($j); # doesn't affect CF!
	562	&jge (&label("sub"));
1702c8c4	563	&mov ($j,$num); # j=num-1
54f3d200 AP	564	&sbb ("esi",0); # esi holds upmost overflow bit
54f3d200 AP	565	&jc (&label("copy"));
48d2335d	566	&set_label("zap",16);
34736de4	567	&mov (&DWP($frame,"esp",$j,4),$i); # zap temporary vector
54f3d200 AP	568	&dec ($j);
	569	&jge (&label("zap"));
	570
48d2335d	571	&set_label("exit",4);
54f3d200 AP	572	&mov ("esp",$_sp); # pull saved stack pointer
54f3d200 AP	573	&mov ("eax",1);
48d2335d	574	&set_label("just_leave");
54f3d200 AP	575	&function_end("bn_mul_mont");
54f3d200 AP	576
1702c8c4 AP	577	&asciz("Montgomery Multiplication for x86, CRYPTOGAMS by <appro\@openssl.org>");
1702c8c4 AP	578
54f3d200	579	&asm_finish();