largeintegers.cpp

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

	{
		push ebp//save registers
		push edi
		push esi
		push ebx
		push ecx
		push edx
	
		mov ebp,ecx
		mov edi,edx

		mov ebx,[edi]Lint.sign
		mov ecx,[ebp]Lint.sign
		jecxz cnt03//if this>0 jump
		mov ecx,ebx
		jecxz cnt04
		//both negatives
		mov [ebp]Lint.sign,0//make positive temporarily
		mov [edi]Lint.sign,0//make positive temporarily
		mov ecx,ebp
		call Add2
		mov [edi]Lint.sign,1//restore
		mov [ebp]Lint.sign,1//make it negative
		jmp end39

cnt04:	//this negative and A2 positive
		mov [ebp]Lint.sign,0//make positive temporarily
		mov ecx,ebp
		call Sub2
		not [ebp]Lint.sign //reverse the sign
		and [ebp]Lint.sign,1
		jmp end39

cnt03:	mov ecx,ebx
		jecxz cnt05
		//this positive and A2 negative
		mov [edi]Lint.sign,0//make positive temporarily
		mov ecx,ebp
		call Sub2
		mov [edi]Lint.sign,1//restore
		jmp end39
cnt05:	//both positives
	

		//set the len difference and realloc data
		mov ecx,[edi]Lint.IntLen
		mov edx,[ebp]Lint.IntLen
		sub edx,[edi]Lint.IntLen//save to edx the diference
		jnc cnt06//if this len<A2len patch this with zeroes
		mov ecx,ebp
		mov edx,[edi]Lint.IntLen
		call ReallocData
		mov ecx,edx
		mov edx,0
		
cnt06:	//reallocate one dword more (addition)
		mov eax,[ebp]Lint.Data
		mov ebx,[ebp]Lint.IntLen
		mov dword ptr[eax+ebx*4],0//zeroize dword
		inc [ebp]Lint.IntLen//new IntLen
	
		//here begins the addition
		mov	esi,[ebp]Lint.Data
		mov	edi,[edi]Lint.Data
		mov ebx,0//for index purpose
		clc//clear carry
		////////////add	min	integer	first///////////////////////
arx:	mov	eax,[edi+ebx*4]//mov eax,A2data
		adc	[esi+ebx*4],eax//add
		inc ebx//increase index
		loop arx
		///////////////proccess	the	rest bytes////////////////////
		mov ecx,edx
		jecxz lastact//if minlen==maxlen jump to lastact		
		//propagate the carry to the next dwords
rest:	adc	dword ptr[esi+ebx*4],0//add
		jnc lastact//if we have not a carry we dont need to continue the execution
		inc ebx//increase index
		loop rest
//////////////////////////////////////////////////////////////////
lastact://add carry(if exists) to sum
		adc	[esi+ebx*4],0//add only carry
		// here ends the addition

		//this->NormalizeLength();
		mov edx,[ebp]Lint.Data//
nrml1:	mov ecx,[ebp]Lint.IntLen
		test dword ptr[edx+ecx*4-4],4294967295//
		jnz end39//need no normalizing
		cmp dword ptr[ebp]Lint.IntLen,2//not normalize if first dword=0
		jnae end39//not normalize if first dword=0
		dec dword ptr[ebp]Lint.IntLen//normalize length of this
		jmp nrml1
end39:
		mov eax,0
		pop edx//restore
		pop ecx
		pop ebx
		pop esi
		pop edi	
		pop ebp
		ret //
	}
}
//############################################################################################
__declspec(naked)int Lint::Sub1(Lint* A1, Lint* A2, Lint*  result)
{
	BU eql;
	BU minlen;
	BU maxlen;

	__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

	}
	
	if (A1->sign==0)
	{
		if (A2->sign>0)
		{
			A2->sign=0;
			Add1(A1,A2,result);
			result->sign=0;//positive
			A2->sign=1;//restore
			goto endsub;
		}
	}
	else//A1.sign>0
	{
		if (A2->sign==0)
		{
			A1->sign=0;
			Add1(A1,A2,result);
			result->sign=1;//negative
			A1->sign=1;//restore
			goto endsub;
		}
		else 
		{
			A2->sign=0;
			A1->sign=0;
			Sub1(A2,A1,result);
			A2->sign=1;//restore
			A1->sign=1;//restore			
			goto endsub;
		}
	}

	eql=A1->CompareU(A2);//absolute values comparison
	if (eql==2)//|A2>A1|
	{
		Sub1(A2,A1,result);//we want a2 biger than a1
		if(result->sign==0) result->sign=1;else result->sign=0;
		goto endsub;
	}
	if (eql==0)//|A2=A1|
		(*result)=0;
	__asm
	{		
		mov esi,A1
		mov edi,A2
		mov eax,[edi]A2.IntLen
		mov minlen,eax//minlen=A2->IntLen;//minimum	length
		mov ecx,[esi]A1.IntLen
		mov maxlen,ecx//maxlen=A1->IntLen;//maximum	length		
		//result->ReallocDataZero(maxlen)			
		mov ebx,result
		lea edx,[ebx]result.IntLen
		mov edi,[ebx]result.Data
		mov [edx],ecx//
		mov eax,0// fill memory and return 0;
		cld
		rep stosd
		
		mov	ecx, minlen	
		clc//clear carry
		mov edi,0//index
		mov ebx,A2		
		mov	ebx,[ebx]A2.Data//mov	ebx,mindata
		mov esi,A1		
		mov	esi,[esi]A1.Data//mov	esi,maxdata
		mov edx,result		
		mov	edx,[edx]result.Data
		////////////subb	min	integer	first///////////////////////
arx:	mov eax,[esi+edi*4]//mov eax,maxdata
		sbb	eax,[ebx+edi*4]//sub
		mov	[edx+edi*4],eax//mov sum,eax
		inc edi
		loop arx
		///////////////proccess	the	rest bytes////////////////////
		mov	ecx,maxlen
		pushf//save	carry etc
		sub	ecx, minlen			
		popf//load carry
		jecxz lastact

		jnc restwoc	// if not carry just copy the rest bytes(for fastener code)
				
rest:	mov	eax,[esi+edi*4]//mov ebx,maxdata
		sbb	eax,0//sub
		mov	[edx+edi*4],eax//mov sum,eax
		inc edi
		loop rest
		jmp lastact
/////////////////////////////////////////////////////////////
restwoc:	
		mov	eax,[esi+edi*4]//mov ebx,maxdata
		mov [edx+edi*4],eax
		inc edi
		loop restwoc
		clc
/////////////////////////////////////////////////////////////////
lastact://last action  add carry(if exists) to sum
		mov edi,result
		lea ebx,[edi]result.sign
		setc [ebx]//set or not cf
		//result->NormalizeLength();
		mov esi,[edi]result.Data//
nrml1:	mov ecx,[edi]result.IntLen
		test dword ptr[esi+ecx*4-4],4294967295//
		jnz end39//need no normalizing
		cmp dword ptr[edi]result.IntLen,2//not normalize if first dword=0
		jnae end39//not normalize if first dword=0
		dec dword ptr[edi]result.IntLen//normalize length of this
		jmp nrml1
end39:	
	}	


endsub:
	__asm
	{
		mov eax,0
		pop edx//restore
		pop ecx
		pop ebx
		pop esi
		pop edi	
		mov esp,ebp
		pop ebp
		ret //
	}
}
//############################################################################################
__declspec(naked)int Lint::Sub2(Lint* A2)
{

	
	__asm
	{
		push ebp
		push edi//save registers
		push esi
		push ebx
		push ecx
		push edx

	
		mov ebp,ecx
		mov edi,edx

		mov ebx,[edi]Lint.sign
		mov ecx,[ebp]Lint.sign
		jecxz cnt03//if this>0 jump
		mov ecx,ebx
		jecxz cnt04
		//both negatives
		mov [ebp]Lint.sign,0//make positive temporarily
		mov [edi]Lint.sign,0//make positive temporarily
		mov ecx,ebp
		call Sub2
		mov [edi]Lint.sign,1//make it negative
		not [ebp]Lint.sign //reverse the sign
		and [ebp]Lint.sign,1
		jmp end39

cnt04:	//this negative and A2 positive
		mov [ebp]Lint.sign,0//make positive temporarily
		//mov edx,edi
		mov ecx,ebp
		call Add2
		mov [ebp]Lint.sign,1//make it negative
		jmp end39

cnt03:	mov ecx,ebx
		jecxz cnt05
		//this positive and A2 negative
		mov [edi]Lint.sign,0//make positive temporarily
		mov ecx,ebp
		call Add2
		mov [edi]Lint.sign,1//make it negative
		jmp end39
cnt05:	//both positives

		mov ecx,[edi]Lint.IntLen
		mov edx,[ebp]Lint.IntLen
		sub edx,[edi]Lint.IntLen//save to edx the diference
		jnc cnt//if this len<A2len patch this with zeroes
		mov ecx,ebp
		mov edx,[edi]Lint.IntLen
		call ReallocData
		mov ecx,edx
		mov edx,0

cnt:	mov	edi,[edi]A2.Data//mov	ebx,mindata
		mov	esi,[ebp]Lint.Data//mov	esi,maxdata
		mov ebx,0//index
		clc//clear carry
		////////////subb	min	integer	first///////////////////////
arx:	mov eax,[edi+ebx*4]//mov eax,mindata
		sbb	[esi+ebx*4],eax//sub
		inc ebx
		loop arx
		///////////////proccess	the	rest bytes////////////////////
		mov ecx,edx
		jecxz lastact//if difference=0 goto lastact				
rest:	sbb	dword ptr[esi+ebx*4],0//sub
		jnc lastact//if we have not a carry we dont need to continue the execution
		inc ebx
		loop rest		
/////////////////////////////////////////////////////////////////
lastact://last action  add carry(if exists) to sum
		mov [ebp]Lint.sign,0
		jnc cnt1

		//negate the integer (two's complement)
		mov [ebp]Lint.sign,1//set sign
		mov ecx,[ebp]Lint.IntLen
		mov edx,[ebp]Lint.Data
		not dword ptr[edx+0]//negate first byte
		add dword ptr[edx+0],1
		mov ebx,1
		dec ecx
		jecxz cnt1//if len=1 then we do not need to negate
acmp1:	not dword ptr[edx+ebx*4]//
		adc dword ptr[edx+ebx*4],0//propagate the carry
		inc ebx
		loop acmp1

cnt1:	//this->NormalizeLength();
		mov edx,[ebp]Lint.Data//
nrml1:	mov ecx,[ebp]Lint.IntLen
		test dword ptr[edx+ecx*4-4],4294967295//
		jnz end39//need no normalizing
		cmp dword ptr[ebp]Lint.IntLen,2//not normalize if first dword=0
		jnae end39//not normalize if first dword=0
		dec dword ptr[ebp]Lint.IntLen//normalize length of this
		jmp nrml1
end39:	
	
		mov eax,0
		pop edx//restore
		pop ecx
		pop ebx
		pop esi
		pop edi	
		//mov esp,ebp
		pop ebp
		ret //
	}
}
//############################################################################################
__declspec(naked)int Lint::Sr(BU t)//shift right 
{
	__asm
	{
		push edi//save registers
		push esi
		push ecx

		cmp edx,1
		jne zzz//if shift more than one bit

		mov eax,ecx
		mov edi,[eax]this.Data
		mov ecx,[eax]this.IntLen
		lea esi,[edi+ecx*4-4]//store for later use
		clc//clear carry flag
sr1:	rcr dword ptr[edi+ecx*4-4],1//rotate through cary
		loop sr1
		//normalize length(if we have leading zero)
		mov ecx,[esi]
		cmp ecx,0
		jne srend
		dec dword ptr[eax]this.IntLen//normalize
		jnz srend
		inc dword ptr[eax]this.IntLen//min curlen is 1
		jmp srend



//shift >1 bit right. slower than one bit shift		
zzz:	cmp edx,0
		je srend//if 0 times shift then return
		push edx
		xchg edx,ecx//both passed from caller		
		mov edi,[edx]Lint.Data
		mov eax,[edx]Lint.IntLen
		mov dword ptr[edi+eax*4],0
		mov esi,1
sr2:	mov eax,[edi+esi*4]
		shrd [edi+esi*4-4],eax,cl
		inc esi
		cmp [edx]Lint.IntLen,esi
		jnc sr2		
		//if msb is zero
		test dword ptr[edi+esi*4-8],4294967295
		jnz es3		
		dec [edx]this.IntLen//nomalize
		test [edx]this.IntLen,4294967295
		jnz es3
		inc [edx]this.IntLen
es3:	pop edx

srend:	
		mov eax,0
		pop ecx//restore
		pop esi
		pop edi	
		ret //
	}
}
//############################################################################################
__declspec(naked)int Lint::Sl(BU t)//shift left t bits //x=x*2
{
	__asm
	{
		push edi//save registers
		push esi
		push ecx

		cmp edx,1
		jne zzz//if shift more than one bits

		//shift one bit left. much faster than more bits shift		
		mov eax,ecx//passed from caller
		mov edi,[eax]this.Data
		mov ecx,[eax]this.IntLen
		clc//clear carry flag
		mov esi,0
sl1:	rcl dword ptr[edi+esi*4],1//rotate through cary
		inc esi
		loop sl1
		jnc endsl
		mov dword ptr[edi+esi*4],1//if we have cary
		inc [eax]this.IntLen
endsl:	jmp es1

		//shift >1 bit left. slower than one bit shift		
zzz:	cmp edx,0
		je es1//if 0 times shift then return
		push edx
		xchg edx,ecx//both passed from caller		
		mov edi,[edx]this.Data
		mov esi,[edx]this.IntLen
		mov dword ptr[edi+esi*4],0
sl2:	mov eax,[edi+esi*4-4]
		shld [edi+esi*4],eax,cl
		sub esi,1
		jnz sl2
		mov eax,0//shift the last dword
		shld [edi+esi*4],eax,cl
		//if msb is zero
		mov esi,[edx]this.IntLen
		mov eax,[edi+esi*4]
		cmp eax,0