largeintegers.cpp

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

	return cres;
}
//############################################################################################
Lint& Lint::operator - (int ss)
{
	gen=ss;
	Sub1(this,&gen,&restmp);
	cres=restmp;
	return cres;
}
//############################################################################################
Lint& Lint::operator * (int mm)
{
	gen=mm;
	Mul1(&gen,&restmp);
	cres=restmp;
	return cres;
}
//############################################################################################
Lint& Lint::operator / (int dd)
{
	LITmp=dd;
	Div1(&LITmp,&restmp,&gen);
	cres=restmp;
	return cres;
}
//############################################################################################
Lint& Lint::operator % (int mm)
{
	gen=mm;
	Div1(&gen,&gen,&restmp);
	cres=restmp;
	return cres;
}
//############################################################################################
__declspec(naked)void Lint::operator = (int it)//signed
{
	__asm
	{
		mov eax,edx
		and eax,80000000h//we want only the sign
		jz nxt39
		neg edx
nxt39:	shr eax,31//put it to lsb
		mov [ecx]Lint.sign,eax//copy sign
		mov [ecx]Lint.IntLen,1//copy curlen
		mov eax,[ecx]Lint.DataBase
		mov [ecx]Lint.Data,eax
		mov [eax],edx//*this=it;
		ret //
	}
}
//############################################################################################
__declspec(naked)void Lint::operator = (BU v)
{	
	__asm	
	{//*this=v;
		mov [ecx]this.IntLen,1//copy curlen
		mov [ecx]this.sign,0//copy sign
		mov eax,[ecx]this.DataBase
		mov [ecx]this.Data,eax
		mov [eax],edx//*this=v;
		ret //
	}
}
//############################################################################################
__declspec(naked)void Lint::operator = (Lint& source)
{
	__asm	
	{//*this=source;
		push ebx
		push esi
		push edi
		
		mov ebx,[edx]source.IntLen
		mov [ecx]Lint.IntLen,ebx//copy curlen
		mov eax,[edx]source.sign
		mov [ecx]Lint.sign,eax//copy sign
		mov eax,[edx]source.Data
		sub eax,[edx]source.DataBase
		add ebx,eax
		add eax,[ecx]Lint.DataBase
		mov [ecx]Lint.Data,eax//copy DataIndex
		mov esi,[edx]source.DataBase
		mov edi,[ecx]Lint.DataBase
		mov ecx,ebx
		cld//  cld is for inc and std is for dec
		rep movsd//*this=source;

		pop edi
		pop esi
		pop ebx
		ret //
	}	
}
//############################################################################################
void Lint::operator ++ (){restmp=1;Add2(&restmp);}
//############################################################################################
void Lint::operator -- (){restmp=1;Sub2(&restmp);}
//############################################################################################
void Lint::operator ++ (int){restmp=1;Add2(&restmp);}
//############################################################################################
void Lint::operator -- (int){restmp=1;Sub2(&restmp);}
//############################################################################################
void Lint::operator += (Lint& pp){Add2(&pp);}
//############################################################################################
void Lint::operator -= (Lint& ss){Sub2(&ss);}
//############################################################################################
void Lint::operator *= (Lint& mm)
{
	Mul1(&mm,&cres1);
	*this=cres1;
}
//############################################################################################
void Lint::operator /= (Lint& dd)
{
	Div1(&dd,&cres1,&gen);
	*this=cres1;
}
//############################################################################################
void Lint::operator %= (Lint& mm)
{
	Div1(&mm,&gen,&cres1);
	*this=cres1;
}
//############################################################################################
void Lint::operator += (BU pp){restmp=pp;Add2(&restmp);}
//############################################################################################
void Lint::operator -= (BU ss){restmp=ss;Sub2(&restmp);}
//############################################################################################
void Lint::operator *= (BU mm)
{
	Mul2(mm,&cres1);
	*this=cres1;
}
//############################################################################################
void Lint::operator /= (BU dd)
{
	Div2(dd,&cres1,&gen);
	*this=cres1;
}
//############################################################################################
void Lint::operator %= (BU mm)
{
	Div2(mm,&gen,&cres1);
	*this=cres1;
}
//############################################################################################
void Lint::operator += (int pp){restmp=pp;Add2(&restmp);}
//############################################################################################
void Lint::operator -= (int ss){restmp=ss;Sub2(&restmp);}
//############################################################################################
void Lint::operator *= (int mm)
{
	restmp=mm;
	Mul1(&restmp,&cres1);//warning signed unsigned
	*this=cres1;
}
//############################################################################################
void Lint::operator /= (int dd)
{
	restmp=dd;
	Div1(&restmp,&cres1,&gen);
	*this=cres1;
}
//############################################################################################
void Lint::operator %= (int mm)
{
	restmp=mm;
	Div1(&restmp,&gen,&cres1);
	*this=cres1;
}
//############################################################################################
int Lint::Exp(BU A1,BU exp,Lint* res)//Left-to-right binary exponentiation
{
	if(exp==0){*res=1;return 0;}
	if(A1==0){*res=1;return 0;}
	if(A1==1){*res=1;return 0;}
	//if(fact<0){res=1;return 0;}if below zero
	char bitt;// for testing bit
	*res=1;	
	for(int i=31;i>=0;--i)
	{
		res->Sqr1();		
		__asm
		{			
			mov	eax,i	
			bt exp,eax
			setc bitt
		}
		if(bitt)*res*=A1;
	}
	return 0;
}
//############################################################################################
__declspec(naked)int Lint::ToStr(char *s)//converts to string.
{
	__asm
	{	push ebp	
		push edi//save all registers
		push esi
		push ebx
		push edx
		push ecx
		
		////if this is zero s[0]='0';s[1]=0;return 0;
		mov esi,[ecx]Lint.Data//this
		mov esi,[esi]
		add esi,[ecx]Lint.IntLen
		cmp esi,1
		jne bgn
		mov [edx],48// '0'
		mov [edx+1],0// null
		jmp endff

bgn:	//div=this		
		cld//  cld is for inc and std is for dec
		mov esi,[ecx]Lint.Data//this
		mov edi,LITmp.Data//dvd
		mov ecx,[ecx]Lint.IntLen
		mov LITmp.IntLen,ecx			
		rep movsd//*this=source;			
		//quo=1;
		mov LITmp1.IntLen,1//set intlen
		mov LITmp1.sign,0//set sign
		mov eax,LITmp1.Data
		mov [eax],1//=1;
		//initialize pointers
		lea ecx,LITmp //div
		lea edi,LITmp1//quo
		lea esi,LITmp2//rem
		mov ebx,edx//s
		mov ebp,LITmp2.Data
		mov edx,radix
		
		//////////////// begin of loop //////////////////////////	
arxd1:	//while(quot>0>)
		mov eax,[edi]Lint.Data
		mov eax,[eax]
		add eax,[edi]Lint.IntLen
		cmp eax,2
		jc endts
		//Div2(dvd,radix,quo,rem)
		push esi//rem
		push edi//quo
		call Div2
		//str[strindex] = (char)rem.Data[0] + '0';
		mov al,byte ptr[ebp]//first byte of rem
		cmp al,10
		jc nxt1
		add al,7
nxt1:	add al,48//add the '0'
		mov byte ptr [ebx],al
		// div=quo
		xchg ecx,edi
		//++index;
		inc ebx
		jmp arxd1
endts:	////////////////end of loop //////////////////////////	
		dec ebx//not leading zero		

		//if this.sign>0 s[ebx] = '-';++strindex;
		mov ecx,[esp+0]//this
		mov ecx,[ecx]Lint.sign//this.sign
		jecxz nxt6
		mov byte ptr [ebx],'-'
		inc ebx//inc strindex
nxt6:	mov byte ptr [ebx],0//terminate with null
		push [esp+4] 
		call _strrev//I use this func because is very fast(difference in speed with a substitute, is negligible)
		add esp,4

endff:	mov eax,0//return 0;
		pop ecx
		pop edx//restore
		pop ebx
		pop esi
		pop edi
		pop ebp
		ret //		

		}
}
//############################################################################################
__declspec(naked)unsigned int Lint::GetLength(void){__asm mov eax,[ecx]Lint.IntLen	__asm ret}
//############################################################################################
__declspec(naked)unsigned int Lint::GetDigit(BU pos)
{	
	__asm	mov eax,[ecx]Lint.Data
	__asm	mov eax,[eax+edx*4]
	__asm	ret
}
//############################################################################################
__declspec(naked)void Lint::WipeOut(void)
{
	__asm
	{
		push ecx
		push edi
		mov edi,[ecx]Lint.DataBase
		mov [ecx]Lint.Data,edi
		mov [ecx]Lint.IntLen,0
		mov ecx,MAXLEN
		mov eax,0h
		rep stosd
		pop edi
		pop ecx
		ret
	}
}
//############################################################################################
void Lint::WipeOutAllGlobals(void)
{
	LITmp1.WipeOut();
	LITmp.WipeOut();
	LITmp2.WipeOut();
	gcd.WipeOut();
	gcd1.WipeOut();
	divy.WipeOut();
	divtmp.WipeOut();
	ybnt.WipeOut();
	gen.WipeOut();
	cres.WipeOut();
	cres1.WipeOut();
	restmp.WipeOut();
	r2.WipeOut();
	q3.WipeOut();
	b2km.WipeOut();
	mdxp.WipeOut();
	mdxp1.WipeOut();
	sqr.WipeOut();
	y.WipeOut();
	r.WipeOut();
}
//############################################################################################
__declspec(naked)bool Lint::IsOdd(void)
{
	__asm
	{
		mov eax,[ecx]Lint.Data
		bt dword ptr[eax],0
		mov eax,0
		rcl eax,1
		ret
	}
}
//############################################################################################
__declspec(naked)bool Lint::IsNeg(void){__asm mov eax,[ecx]Lint.sign __asm ret}
//############################################################################################
__declspec(naked)void Lint::MakeNeg(void)
{
	__asm mov [ecx]Lint.sign,1
	__asm ret
}
//############################################################################################
__declspec(naked)void Lint::MakePos(void)
{
	__asm mov [ecx]Lint.sign,0
	__asm ret
}
//############################################################################################
__declspec(naked)unsigned int Lint::CompareS(Lint* A1)
{	
	__asm
	{
		call CompareU
		cmp eax,1
		jne cmp2
		cmp dword ptr[ecx]this.sign,0
		je cmp20
		mov eax,2//this<A1
		ret
cmp20:	mov eax,1//this>A1
		ret

cmp2:	cmp eax,2
		jne cmp0
		cmp dword ptr[edx]A1.sign,0
		je cmp21
		mov eax,1//this>A1
		ret
cmp21:	mov eax,2//this<A1
		ret

cmp0:	//absolute values are equal 
		cmp dword ptr[ecx]this.sign,0
		jne cmpn1
		cmp dword ptr[edx]A1.sign,0
		jne cmpn1
		mov eax,0//both are positive and equal
		ret
cmpn1://one, or both are negatives
		cmp dword ptr[ecx]this.sign,0
		jne cmpn2
		mov eax,1// A1<this
		ret
cmpn2:	//'this' is negative
		cmp dword ptr[edx]A1.sign,0
		je cmpend
		mov eax,0//both are negative and equals
		ret
cmpend: //A1 is positive and 'this' is negative
		mov eax,2//this>A1
		ret
	}
}
//############################################################################################
__declspec(naked)unsigned int Lint::CompareU(Lint* A1)
{
	__asm
	{
		push edi//save registers
		push esi
		push ecx
		pushf
		
		mov esi,ecx//passed from caller
		// and edx passed from caller
		mov ecx,[edx]A1.IntLen
		cmp [esi]this.IntLen,ecx
		je nxtc//if are equals in size go to next comparison
		jnc an1//A1>A2
an2:	mov eax,2//A2 is greater
		jmp endcmp
an0:	mov	eax,0//equals
		jmp endcmp
an1:	mov eax,1//A1 is greater
		jmp endcmp
nxtc:	mov eax,[esi]this.Data
		lea esi,[eax+ecx*4-4]
		mov eax,[edx]A1.Data
		lea edi,[eax+ecx*4-4]
		std//set dir flag for decrement. std is for dec
		repe cmpsd//if equals continue loop//comparison dword by dword
		je an0//if are equals
		jnc an1//A1>A2
		jmp	an2//A1<A2
endcmp:	
		popf//restore dir flag because some stupid compilers think this is allways cld
		pop ecx//restore
		pop esi
		pop edi	
		ret //
	}
}
//############################################################################################
__declspec(naked)int Lint::ReallocData(BU newsize)
{
	__asm	
	{
		push edi//save registers
		push esi
		push ebx
		push ecx
		push edx	
		
		mov esi,edx//newsize
		mov ebx,ecx//passed from caller
		lea edx,[ebx]this.IntLen//curlen 
		mov ebx,[ebx]this.Data//data		
		cmp [edx],esi//curlen-newsize
		je fend//if (newsize==IntLen)return 0;
		jae eql// if newsize < curlen jump		
		mov ecx,esi
		sub ecx,[edx]//set counter to newsize-curlen
		mov edi,[edx]//index to curlen (next dword for allocation)
		mov eax,0		
mlp:	mov dword ptr[ebx+edi*4+0],eax//zeroize all the rest dwords
		inc edi
		loop mlp		
		mov [edx],esi//set the new curlen
		jmp fend
eql:	mov [edx],esi//set new size
fend:
		mov eax,0//return 0;
		pop edx//restore
		pop ecx