largeintegers.cpp

RSA大数运算库 RSA大数运算库

		pop ebx
		pop esi
		pop edi	
		ret //
	}	
}
//############################################################################################
__declspec(naked)int Lint::NormalizeLength(void)//cuts all the leading zero bytes
{	
	__asm
	{	//distinguishes all leading zeros
		push ebx

		mov eax,[ecx]Lint.Data//
lp30:	mov ebx,[ecx]Lint.IntLen// length 
		cmp dword ptr[eax+ebx*4-4],0//
		jne end30//need no normalizing
		cmp [ecx]Lint.IntLen,2//not normalize if first dword=0
		jnae end30//not normalize if first dword=0
		dec [ecx]Lint.IntLen//normalize length of this
		jmp lp30

end30:	mov eax,0//return 0;
		pop ebx
		ret //
	}	
}
//############################################################################################
__declspec(naked)int Lint::Mul1(Lint* A2,Lint* product)
{
	BU A2digit;//current digit for internal multiplication
	BU savecx;//save ecx
	BU saveesp;//for saving stack pointer esp	
	BU A1len;//length of A1
	PBU A2data;//pointer of A2->Data
	__asm
	{	
		push ebp
		mov ebp,esp
		sub esp,__LOCAL_SIZE//as  many bytes as local variables
		push edi//save registers
		push esi
		push ebx
		push ecx
		push edx	
		
		//////////// multiplication /////////	
		mov ebx,this
		mov edx,A2
		//if we have A2<=32bit we use Mul2 (faster)
		cmp [edx]Lint.IntLen,1
		jne mmul
		//multiply
		mov esi,product
		push esi
		mov edx,[edx]Lint.Data
		mov edx,[edx]//A2.Data[0]
		mov ecx,ebx//this
		call Mul2
		jmp end31

mmul:	mov saveesp,esp//save esp

		mov esp,product
		
		//product->ReallocDataZero(A2len+A1->IntLen)
		mov ecx,[edx]A2.IntLen
		add ecx,[ebx]Lint.IntLen//A1len+A2len
		mov [esp]product.IntLen,ecx
		mov edi,[esp]product.Data
        mov esi,edi
		mov eax,0
		cld//  cld is for inc and std is for dec
		rep stosd//fill product  data with zeros		
		mov edi,[ebx]Lint.Data
        mov eax,[ebx]Lint.IntLen
		mov A1len,eax
		mov eax,[edx]A2.Data
		mov A2data,eax
		mov eax,[eax]
		mov A2digit,eax		
		mov ecx,[edx]A2.IntLen
beg://mul/////////////////////mul	///////////////////////
		mov savecx,ecx//push ecx
		mov ecx,A1len
		mov	edx,0
		mov ebx,0//for index        
arx:	mov	eax,[edi+ebx*4]// mov eax, A1data
		mov	esp,edx// save temporarily edx
		mul	A2digit//multiply 
		add	eax,esp// from previous	mult
		adc	edx,0//and the carry to	edx		
		add [esi+ebx*4],eax//add the product to memory
		adc edx,0//and the carry to	edx
		inc ebx
		loop arx
		////////////////////////////////////////////////
		mov [esi+ebx*4],edx//write the remain msb to memory
		add esi,4
		add A2data,4
		mov eax,A2data
		mov eax,[eax]
		mov A2digit,eax//
		mov ecx,savecx//pop ecx
		loop beg

		mov esp,saveesp//restore esp

		//product->NormalizeLength();
		mov esi,product
		mov ebx,[esi]product.Data
nl1:	mov	ecx,[esi]product.IntLen//length	value	
		test dword ptr[ebx+ecx*4-4],4294967295
		jnz end31//need no normalizing		
		dec [esi]product.IntLen//normalize length of product
		test [esi]product.IntLen,4294967295//if curlen is above 0
		jnz nl1
		inc [esi]product.IntLen//if 0 then curlen=1
end31:
		// test sign
		mov ebx,this
		mov eax,0
		cmp eax,[ebx]Lint.sign// test sign
		rcl eax,1
		mov ebx,A2
		mov ecx,0
		cmp ecx,[ebx]Lint.sign// test sign
		rcl ecx,1		
		xor eax,ecx
//		cmp eax,ecx//theese all are the xor function (compatibility with 486)
//		jne xr1
//		mov eax,0
//		jmp xr2
//xr1:	mov eax,1/////////// minus if one is minus
//xr2:	mov [esi]product.sign,eax//set sign		
		mov [esi]product.sign,eax//set sign	

		//if product==0 then sign must be plus
		//zero must have allways positive sign
		mov	ecx,[esi]product.IntLen//length	value
		mov eax,[esi]product.Data
		mov eax,[eax] //
		add eax,[esi]product.IntLen//if len==1 and data[0]==0
		cmp eax,1
		jne end002
		mov dword ptr[esi]product.sign,0//set positive sign	
end002:	
		mov eax,0//return 0;
		pop edx//restore
		pop ecx
		pop ebx
		pop esi
		pop edi
		mov esp,ebp
		pop ebp
		ret //	
	}
}

//############################################################################################
__declspec(naked)int Lint::Mul2(BU A2,Lint* product)
{
	__asm
	{	
//////////// before modify anything look at warnings ///////////////////////////////////
		push ebp
		push edi//save registers
		push esi
		push ebx
		push ecx
		push edx

		mov ebp,edx
		mov esi,[ecx]Lint.Data
		mov edi,[esp+28]////product  warning -------warning---------warning -------warning
		mov eax,[ecx]Lint.sign
		mov [edi]product.sign,eax//copy sign to product
		mov dword ptr[edi]product.IntLen,1
		mov	ecx, [ecx]Lint.IntLen
		add [edi]product.IntLen,ecx//prod.curlen= a1.curlen+1 
		mov edi,[edi]product.Data
		mov edx,0
		////////////mul ///////////////////////
arx:	mov eax,[esi]		
		mov ebx,edx// save temporarily edx
		mul	ebp//multiply 
		add eax,ebx// from previous mult
		adc edx,0//and the carry to edx
		mov [edi],eax//save the result 		
		add esi,4//increase pointers
		add edi,4
		loop arx
		mov [edi],edx
//////////// before modify anything look at warnings ///////////////////////////////////
		//prod->NormalizeLength();
		mov edi,[esp+28]////product  warning -------warning---------warning -------warning
		mov esi,[edi]product.Data//data	pointer
lpn1:	mov	ecx,[edi]product.IntLen//length	value	
		test dword ptr[esi+ecx*4-4],4294967295
		jnz end18//need no normalizing		
		dec [edi]product.IntLen//normalize length of prod
		test [edi]product.IntLen,4294967295//if curlen is above 0
		jnz lpn1
		inc [edi]product.IntLen//if 0 then curlen=1
end18:
		//zero product must have pos sign
		mov ecx,edi
		call ZeroSign//product		

		mov eax,0//return 0;
		pop edx//restore
		pop ecx
		pop ebx
		pop esi
		pop edi
		pop ebp
		ret 4//pop the last 4 bytes (1 argument)
	}

}

//############################################################################################
__declspec(naked)int Lint::Mul3(Lint* A2,Lint* product,BU digits)
{
	BU A2digit;//current digit for internal multiplication
	BU savecx;//save ecx
	BU saveesp;//for saving stack pointer esp	
	BU A1len;//length of A1
	PBU A2data;//pointer of A2->Data
	PBU digaddress;//for partial multiplication (product address )
	__asm
	{	
		push ebp
		mov ebp,esp
		sub esp,__LOCAL_SIZE//as  many bytes as local variables
		push edi//save registers
		push esi
		push ebx
		push ecx
		push edx	
		mov saveesp,esp//save esp

		//////////// multiplication /////////	
		mov ebx,this
		mov edx,A2
		mov esp,product		
		//product->ReallocDataZero(A2len+A1->IntLen)
		mov ecx,[edx]A2.IntLen
		add ecx,[ebx]Lint.IntLen//A1len+A2len
		//for partial mult
		cmp ecx,digits//for partial mult
		jc nxt02
		mov ecx,digits
nxt02:	mov [esp]product.IntLen,ecx
		mov edi,[esp]product.Data
        mov esi,edi
		mov eax,0
		cld//  cld is for inc and std is for dec
		rep stosd//fill product  data with zeros		
		mov edi,[ebx]Lint.Data
        //mov A1data,edi		
		mov eax,[ebx]Lint.IntLen
		mov A1len,eax
		mov eax,[edx]A2.Data
		mov A2data,eax
		mov eax,[eax]
		mov A2digit,eax		
		mov ecx,[edx]A2.IntLen
		//for patrial multiplication
		mov eax,digits
		dec eax//points to the first digit for value 1
		lea eax,[esi+eax*4]
		mov digaddress,eax
beg://mul/////////////////////mul	///////////////////////
		mov savecx,ecx//push ecx
		mov ecx,A1len
		mov	edx,0
		mov ebx,0//for index        
arx:	mov	eax,[edi+ebx*4]// mov eax, A1data
		mov	esp,edx// save temporarily edx
		mul	A2digit//multiply 
		add	eax,esp// from previous	mult
		adc	edx,0//and the carry to	edx		
		add [esi+ebx*4],eax//add the product to memory
		adc edx,0//and the carry to	edx
		inc ebx
		//for patrial multiplication
		lea eax,[esi+ebx*4-4]
		cmp eax,digaddress//for patrial multiplication(its not implemented right, but it is more fast)
		loopnz arx
		////////////////////////////////////////////////
		mov [esi+ebx*4],edx//write the remain msb to memory
		add esi,4
		add A2data,4
		mov eax,A2data
		mov eax,[eax]
		mov A2digit,eax//
		mov ecx,savecx//pop ecx
		//for patrial multiplication
		lea eax,[esi-4]
		cmp eax,digaddress
		loopnz beg

		//product->NormalizeLength();
		mov esi,product
		mov ebx,[esi]product.Data
nl1:	mov	ecx,[esi]product.IntLen//length	value	
		test dword ptr[ebx+ecx*4-4],4294967295
		jnz end31//need no normalizing		
		dec [esi]product.IntLen//normalize length of product
		test [esi]product.IntLen,4294967295//if curlen is above 0
		jnz nl1
		inc [esi]product.IntLen//if 0 then curlen=1
end31:
		// test sign
		mov ebx,this
		mov eax,0
		cmp eax,[ebx]Lint.sign// test sign
		rcl eax,1
		mov ebx,A2
		mov ecx,0
		cmp ecx,[ebx]Lint.sign// test sign
		rcl ecx,1		
		xor eax,ecx
//		cmp eax,ecx//theese all are the xor function (compatibility with 486)
//		jne xr1
//		mov eax,0
//		jmp xr2
//xr1:	mov eax,1/////////// minus if one is minus
//xr2:	mov [esi]product.sign,eax//set sign		
		mov [esi]product.sign,eax//set sign	

		//if product==0 then sign must be plus
		//zero must have allways positive sign
		mov	ecx,[esi]product.IntLen//length	value
		mov eax,[esi]product.Data
		mov eax,[eax] //
		add eax,[esi]product.IntLen//if len==1 and data[0]==0
		cmp eax,1
		jne end002
		mov dword ptr[esi]product.sign,0//set positive sign	
end002:	mov esp,saveesp//restore esp
		mov eax,0//return 0;
		pop edx//restore
		pop ecx
		pop ebx
		pop esi
		pop edi
		mov esp,ebp
		pop ebp
		ret //	
	}
}

//############################################################################################
__declspec(naked)void Lint::ZeroSign(void)//makes the sign positive if integer is zero
{
	__asm
	{	//zero must have allways positive sign
		mov eax,[ecx]this.Data
		mov eax,[eax] //
		add eax,[ecx]this.IntLen//if len==1 and data[0]==0
		cmp eax,1
		jne end000
		mov dword ptr[ecx]this.sign,0//set positive sign	
end000:	ret //		
	}
}
//############################################################################################
__declspec(naked)int Lint::Div1(Lint* A2,Lint* quot,Lint* rem)
{
	BU thissign,A2sign;//for temp save signs
	BU saveesp;// for saving esp purpose
	BU i;
	BU mp;//for normalizing purpose
	BU n;
	BU t;
	BU yt;//for storage yt
	BU yt1;//for storage y(t-1)
	PBU qit1;//for storage q(i-t-1)
	BU xi;//for storage Xi
	BU xi1;//for storage Xi-1
	BU xi2;//for storage Xi-2

	__asm
       { 
		push ebp
		mov ebp,esp
		sub esp,__LOCAL_SIZE//as  many bytes as local variables
		push edi//save registers
		push esi
		push ebx
		pushf//2 bytes
		push edx//dont touch it
		push ecx//dont touch it
		
		
		cld//  cld is for inc and std is for dec		
		//look first if this<A2 or equals
		call CompareU
		cmp eax,2
		jne eol
		//A2>this  -> rem=this quot=0
		//rem=this
		mov ebx,rem
		mov edx,[ecx]Lint.sign
		mov [ebx]rem.sign,edx//copy sign
		mov esi,[ecx]Lint.Data
		mov edi,[ebx]rem.Data
		mov ecx,[ecx]Lint.IntLen
		mov [ebx]rem.IntLen,ecx//copy curlen first
		rep movsd//*this=source;		
		//qouot=0
		mov ebx,quot
		mov dword ptr[ebx]quot.IntLen,1//copy curlen first
		mov dword ptr[ebx]quot.sign,0//copy sign
		mov eax,[ebx]quot.Data
		mov dword ptr[eax],0
		jmp endz
eol:	
		//make the signs both positive
		mov ebx,[ecx]Lint.sign
		mov thissign,ebx//save sign
		mov ebx,[edx]Lint.sign
		mov A2sign,ebx//save sign
		mov [ecx]Lint.sign,0//make positive
		mov [edx]Lint.sign,0//make positive			
		
		//if this>A2 
		cmp eax,1
		je bac//if this>A2 goto main algorythm
		//else if |this=A2| quot=1 (check sign) and rem=0
		//quot=1 without sign. Must checked after this
		mov ebx,quot
		mov dword ptr[ebx]quot.IntLen,1//copy curlen first
		mov eax,[ebx]quot.Data
		mov dword ptr[eax],1
		//rem=0
		mov ebx,rem
		mov dword ptr[ebx]rem.IntLen,1//copy curlen first
		mov eax,[ebx]rem.Data
		mov dword ptr[eax],0
		jmp end17 //go for sign checking
	////////// end looking first if this<A2 or equals///////

		
bac:	mov ecx,[edx]Lint.IntLen//for later use A2
		//if len=1 call the div2 function and return
		cmp ecx,2
		jae nodiv2
		//call the div2 function and return	
		push rem//push args in reverse order
		push quot
		mov eax,[edx]Lint.Data
		mov edx,[eax]
		mov ecx,[esp+8]//this
		call Div2
		jmp end17//to fix the sign
		
		//divy=*A2;
nodiv2:	mov divy.IntLen,ecx//copy curlen first
		mov eax,[edx]Lint.sign
		mov divy.sign,eax
		mov esi,[edx]Lint.Data
		mov edi,divy.Data
		rep movsd//divy=*A2;
		
		//rem=*this;
		mov esi,[esp]//this, else ecx
		mov edi,rem
		mov ecx,[esi]Lint.sign
		mov [edi]Lint.sign,ecx//copy sign
		mov ecx,[esi]Lint.IntLen
		mov [edi]Lint.IntLen,ecx//copy curlen first
		mov esi,[esi]Lint.Data
		mov edi,[edi]Lint.Data
		rep movsd//rem=*this;