llongint.cpp

一个大整数运算类

		//求出除数的第一个双字的最高位的二进制0的个数
		mov ecx, 32
		mov edx, 0
		mov esi, 0x80000000
		mov edi, pDivisorLLI2
		mov edi, [edi]   ;//another.pLLI[another.lliLength-1];
CalcDivisorLZLoop:
		test esi, edi
		jnz CalcDivisorLZOver
		inc edx
		shr esi, 1
		loop CalcDivisorLZLoop
CalcDivisorLZOver:
		mov divisorLZs, edx

		//置商为0
		mov edi, pQuotient
		push eax
		xor eax, eax  ;//mov eax, 0
		mov ecx, quotientLen
		cld
		rep stosd
		pop eax

LLongIntDivideLoop:
		//求出被除数的第一个双字的最高位的二进制0的个数
		mov ecx, 32
		mov edx, 0
		mov esi, 0x80000000
		mov edi, pDividendLLI2
		mov edi, [edi]
CalcDividendLZLoop:
		test esi, edi
		jnz CalcDividendLZOver
		inc edx
		shr esi, 1
		loop CalcDividendLZLoop
CalcDividendLZOver:
;//		mov dividendLZs, edx

;//被除数左移max(1, dividendLZs-divisorLZs)位
		mov ecx, 1
		;//mov edx, dividendLZs
		sub edx, divisorLZs
		cmp edx, 1
		jle DividendShiftLeft
		cmp edx, 32
		jb LessThan32Bits
		mov edx, 31
LessThan32Bits:
		mov ecx, edx
DividendShiftLeft:
		add shiftedBits, ecx
		mov edx, shiftedBits
		cmp edx, totalShiftBits
		jbe ShiftBitsOK
		sub shiftedBits, ecx
		mov edx, totalShiftBits
		sub edx, shiftedBits
		mov ecx, edx
		mov edx, totalShiftBits
		mov shiftedBits, edx
ShiftBitsOK:
		mov esi, pDividendLLI2
;//		cmp esi, pDividendLLI
;//		jb DividendShiftLeftOver
DividendShiftLeftLoop:
		mov edx, [esi]
		shld [esi+4], edx, cl
		sub esi, 4
		cmp esi, pDividendLLI
		jae DividendShiftLeftLoop
;//DividendShiftLeftOver:
		add esi, 4
		shl dword ptr [esi], cl

;//商左移max(1, dividendLZs-divisorLZs)位
;//QuotientShiftLeft:
		mov esi, pQuotient2
		cmp esi, pQuotient
		jbe QuotientShiftLeftOver
QuotientShiftLeftLoop:
		mov edx, [esi-4]
		shld [esi], edx, cl
		sub esi, 4
		cmp esi, pQuotient
		ja QuotientShiftLeftLoop
QuotientShiftLeftOver:
		shl dword ptr [esi], cl
;//比较被除数和除数的...位
		mov esi, pDividendLLI2
;//		add esi, 4
		cmp dword ptr [esi+4], 0
		ja SetQuotientTo1
;//		sub esi, 4
		mov ecx, [eax][lliLength]
		mov edi, pDivisorLLI2
CmpDividendDivisor2:
		mov edx, [esi]
		cmp edx, [edi]
		jb SetQuotientTo0
		ja SetQuotientTo1
		sub esi, 4
		sub edi, 4
		loop CmpDividendDivisor2
SetQuotientTo1:
		mov esi, pQuotient
		or dword ptr [esi], 1

;//substraction
		mov esi, pDividendLLI1
		mov edi, pDivisorLLI
		mov ecx, [eax][lliLength]
		push eax
		xor eax, eax
		clc
SubDivisorFromDividend:
		mov edx, [edi][eax*4]
		sbb [esi][eax*4], edx
		inc eax
		loop SubDivisorFromDividend
		sbb [esi][eax*4], 0
		pop eax
;//		jmp SetQuotientOver
SetQuotientTo0:
;//SetQuotientOver:
		mov ecx, shiftedBits
		cmp ecx, totalShiftBits
		jb LLongIntDivideLoop
	}
	return LLongInt(pDividendLLI1, another.lliLength, this->sign);
}

//---------------------------------------------------------------------------------------------------

void LLongInt::operator =(LLongInt &another)
{
	if ( &another == this )
		return;
	if ( pLLI != NULL )
		delete pLLI;
	sign = another.sign;
	lliLength = another.lliLength;
	pLLI = new unsigned int[lliLength];
	memcpy(pLLI, another.pLLI, lliLength*4);
	Trim( );
	return;
}

//---------------------------------------------------------------------------------------------------

int LLongInt::operator ==(LLongInt &another)
{
	if ( sign != another.sign || lliLength != another.lliLength )
		return 0;
	int rc = memcmp(pLLI, another.pLLI, lliLength*4);
	return ( rc == 0 );
}

//---------------------------------------------------------------------------------------------------

int LLongInt::operator >(LLongInt &another)
{
	//符号不等
	if ( sign == 1 && another.sign == 0 )
		return 0;
	if ( sign == 0 && another.sign == 1)
		return 1;
	//符号相等
	if ( sign == 0 && another.sign == 0 ) //都为正数
	{
		//长度不等
		if ( lliLength > another.lliLength )
			return 1;
		if ( lliLength < another.lliLength )
			return 0;
		//长度相等
		int a;
		for ( a=lliLength-1; a>=0; a-- )
		{
			if ( pLLI[a] == another.pLLI[a] )
				continue;
			return (pLLI[a] > another.pLLI[a]);
		}
	}
	else //都为负数
	{
		//长度不等
		if ( lliLength > another.lliLength )
			return 0;
		if ( lliLength < another.lliLength )
			return 1;
		//长度相等
		int a;
		for ( a=lliLength-1; a>=0; a-- )
		{
			if ( pLLI[a] == another.pLLI[a] )
				continue;
			return (pLLI[a] < another.pLLI[a]);
		}
	}
	//相等
	return 0;
}

//---------------------------------------------------------------------------------------------------

int LLongInt::operator <(LLongInt &another)
{
	//符号不等
	if ( sign == 1 && another.sign == 0 )
		return 1;
	if ( sign == 0 && another.sign == 1)
		return 0;
	//符号相等
	if ( sign == 0 && another.sign == 0 ) //都为正数
	{
		//长度不等
		if ( lliLength > another.lliLength )
			return 0;
		if ( lliLength < another.lliLength )
			return 1;
		//长度相等
		int a;
		for ( a=lliLength-1; a>=0; a-- )
		{
			if ( pLLI[a] == another.pLLI[a] )
				continue;
			return (pLLI[a] < another.pLLI[a]);
		}
	}
	else //都为负数
	{
		//长度不等
		if ( lliLength > another.lliLength )
			return 1;
		if ( lliLength < another.lliLength )
			return 0;
		//长度相等
		int a;
		for ( a=lliLength-1; a>=0; a-- )
		{
			if ( pLLI[a] == another.pLLI[a] )
				continue;
			return (pLLI[a] > another.pLLI[a]);
		}
	}
	//相等
	return 0;

}

//---------------------------------------------------------------------------------------------------

int LLongInt::operator >=(LLongInt &another)
{
	return !(*this<another);
}

//---------------------------------------------------------------------------------------------------

int LLongInt::operator <=(LLongInt &another)
{
	return !(*this>another);
}

//---------------------------------------------------------------------------------------------------

int LLongInt::operator !=(LLongInt &another)
{
	return !(*this==another);
}


LLongInt LLongInt::Divide(LLongInt &divisor, LLongInt &dividend, LLongInt &remainder)
{
	unsigned int *pQuotient;
	int quotientLen;
	if (Abs(dividend) >= Abs(divisor))
	{
	   quotientLen = dividend.lliLength - divisor.lliLength + 1;
       pQuotient = new unsigned int[quotientLen];
	}
	else
	{
		remainder = dividend;
		return LLongInt((__int64)0);
	}
	unsigned int *pQuotient2 = pQuotient + quotientLen - 1;
	unsigned int *pDivisorLLI = divisor.pLLI;
	unsigned int *pDivisorLLI2 = divisor.pLLI + divisor.lliLength - 1;
	unsigned int *pDividendLLI = new unsigned int[dividend.lliLength+2];
	unsigned int *pDividendLLI1 = pDividendLLI;
	unsigned int *pDividendLLI2;
	int divisorLZs/*, dividendLZs*/ , rSign;
	int totalShiftBits, shiftedBits = 0;
	__asm
	{
		//求出rSign
		mov eax, divisor
		mov ebx, dividend
		mov ecx, [eax][sign]
		xor ecx, [ebx][sign]
		mov rSign, ecx
		//拷贝被除数
		mov edi, pDividendLLI
		mov ecx, [ebx][lliLength]
		mov dword ptr [edi][ecx*4], 0				;//最高两个双字置0
		mov dword ptr [edi][ecx*4+4], 0
		mov esi, [ebx][pLLI]
CopyDividend:
		mov edx, [esi][ecx*4-4]
		mov [edi][ecx*4-4], edx
		loop CopyDividend
		//
		mov ecx, [eax][lliLength]
		mov esi, [ebx][lliLength]
		dec esi
		shl esi, 2
		add esi, [ebx][pLLI]
		mov edi, pDivisorLLI2
CmpDividendDivisor1:
		mov edx, [esi]    ;//this->pLLI[esi]
		cmp edx, [edi]
		jb Fill32Zeros
		ja Fill64Zeros
		sub esi, 4
		sub edi, 4
		loop CmpDividendDivisor1
		;//jmp Fill64Zeros                 ;//==
Fill64Zeros:
		add pDividendLLI1, 4
Fill32Zeros:
		mov ecx, [ebx][lliLength]
		sub ecx, [eax][lliLength]
		shl ecx, 2
		add pDividendLLI1, ecx
		//
		mov ecx, pDividendLLI1
		mov edx, [eax][lliLength]
		dec edx
		shl edx, 2
		add ecx, edx
		mov pDividendLLI2, ecx
		mov ecx, pDividendLLI1
		sub ecx, pDividendLLI
		shl ecx, 3
		mov totalShiftBits, ecx  //得出要移位的总位数

		//求出除数的第一个双字的最高位的二进制0的个数
		mov ecx, 32
		mov edx, 0
		mov esi, 0x80000000
		mov edi, pDivisorLLI2
		mov edi, [edi]   ;//another.pLLI[another.lliLength-1];
CalcDivisorLZLoop:
		test esi, edi
		jnz CalcDivisorLZOver
		inc edx
		shr esi, 1
		loop CalcDivisorLZLoop
CalcDivisorLZOver:
		mov divisorLZs, edx

;/*
;//求出被除数的第一个双字的最高位的二进制0的个数
;		mov ecx, 32
;		mov edx, 0
;		mov esi, 0x80000000
;		mov edi, [ebx][lliLength]
;		mov edi, [ebx][pLLI-4][edi*4]   ;//this->pLLI[this->lliLength-1];
;CalcDividendLZLoop0:
;		test esi, edi
;		jnz CalcDividendLZOver
;		inc edx
;		shr esi, 1
;		loop CalcDividendLZLoop
;CalcDividendLZOver0:
;		mov dividendLZs, edx
;*/

		//置商为0
		mov edi, pQuotient
		push eax
		xor eax, eax  ;//mov eax, 0
		mov ecx, quotientLen
		cld
		rep stosd
		pop eax

LLongIntDivideLoop:
		//求出被除数的第一个双字的最高位的二进制0的个数
		mov ecx, 32
		mov edx, 0
		mov esi, 0x80000000
		mov edi, pDividendLLI2
		mov edi, [edi]
CalcDividendLZLoop:
		test esi, edi
		jnz CalcDividendLZOver
		inc edx
		shr esi, 1
		loop CalcDividendLZLoop
CalcDividendLZOver:
;//		mov dividendLZs, edx

;//被除数左移max(1, dividendLZs-divisorLZs)位
		mov ecx, 1
		;//mov edx, dividendLZs
		sub edx, divisorLZs
		cmp edx, 1
		jle DividendShiftLeft
		cmp edx, 32
		jb LessThan32Bits
		mov edx, 31
LessThan32Bits:
		mov ecx, edx
DividendShiftLeft:
		add shiftedBits, ecx
		mov edx, shiftedBits
		cmp edx, totalShiftBits
		jbe ShiftBitsOK
		sub shiftedBits, ecx
		mov edx, totalShiftBits
		sub edx, shiftedBits
		mov ecx, edx
		mov edx, totalShiftBits
		mov shiftedBits, edx
ShiftBitsOK:
		mov esi, pDividendLLI2
;//		cmp esi, pDividendLLI
;//		jb DividendShiftLeftOver
DividendShiftLeftLoop:
		mov edx, [esi]
		shld [esi+4], edx, cl
		sub esi, 4
		cmp esi, pDividendLLI
		jae DividendShiftLeftLoop
;//DividendShiftLeftOver:
		add esi, 4
		shl dword ptr [esi], cl

;//商左移max(1, dividendLZs-divisorLZs)位
;//QuotientShiftLeft:
		mov esi, pQuotient2
		cmp esi, pQuotient
		jbe QuotientShiftLeftOver
QuotientShiftLeftLoop:
		mov edx, [esi-4]
		shld [esi], edx, cl
		sub esi, 4
		cmp esi, pQuotient
		ja QuotientShiftLeftLoop
QuotientShiftLeftOver:
		shl dword ptr [esi], cl
;//比较被除数和除数的...位
		mov esi, pDividendLLI2
;//		add esi, 4
		cmp dword ptr [esi+4], 0
		ja SetQuotientTo1
;//		sub esi, 4
		mov ecx, [eax][lliLength]
		mov edi, pDivisorLLI2
CmpDividendDivisor2:
		mov edx, [esi]
		cmp edx, [edi]
		jb SetQuotientTo0
		ja SetQuotientTo1
		sub esi, 4
		sub edi, 4
		loop CmpDividendDivisor2
SetQuotientTo1:
		mov esi, pQuotient
		or dword ptr [esi], 1

;//substraction
		mov esi, pDividendLLI1
		mov edi, pDivisorLLI
		mov ecx, [eax][lliLength]
		push eax
		xor eax, eax
		clc
SubDivisorFromDividend:
		mov edx, [edi][eax*4]
		sbb [esi][eax*4], edx
		inc eax
		loop SubDivisorFromDividend
		sbb [esi][eax*4], 0
		pop eax
;//		jmp SetQuotientOver
SetQuotientTo0:
;//SetQuotientOver:
		mov ecx, shiftedBits
		cmp ecx, totalShiftBits
		jb LLongIntDivideLoop
	}
	remainder = LLongInt(pDividendLLI1, divisor.lliLength, dividend.sign);
	return LLongInt(pQuotient, quotientLen, rSign);
}
//---------------------------------------------------------------------------------------------------
char* LLongInt::LLongInt2A(char *buff, int radix, char *radixSymbols)
{
	static char strRadixSymbols[16] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 
		'a', 'b', 'c', 'd', 'e', 'f'};
	if (radix <= 1)
		return NULL;
	if (radix > 16 && radixSymbols==NULL)
		return NULL;
	if (radix <=16 && radixSymbols==NULL)
		radixSymbols = strRadixSymbols;
	LLongInt zero((__int64)0);
	LLongInt divisor((__int64)radix);
	LLongInt quotient = *this;
	LLongInt remainder((__int64)0);
	int symbols = 0;
	char *pBuff;
	if (this->sign == 0)
		pBuff = buff;
	else
	{
		pBuff = buff + 1;
		buff[0] = '-';
	}
	if (quotient == zero)
	{
		pBuff[0] = radixSymbols[0];
		pBuff[1] = 0;
		return buff;
	}

	while (quotient != zero)
	{
		quotient = Divide(divisor, quotient, remainder);
		pBuff[symbols] = radixSymbols[remainder.pLLI[0]];
		symbols++;
	}
	pBuff[symbols] = 0;
	symbols--;
	int index = 0;
	char temp;
	while (index < symbols)
	{
		temp = pBuff[index];
		pBuff[index] = pBuff[symbols];
		pBuff[symbols] = temp;
		index++;
		symbols--;
	}
	return buff;
}

//模幂乘算法, 计算 *this ^ e mod n
LLongInt LLongInt::ExpMod(LLongInt e, LLongInt n)
{

	//汇编算法
	//m = *this		计算 m ^ e mod n
	int a, totalBits, nowBit, nowDW, testBits;
	LLongInt *pE = &e;
	LLongInt c(1);
	LLongInt m = *this;
	__asm
	{
	//计算e共有多少个二进制位
		mov eax, pE
		mov edx, [eax][lliLength]
		mov edi, edx
		shl edx, 5   ;//*32
		dec edi
		shl edi, 2   ;//*4

		mov ecx, 32
		mov esi, 0x80000000
		add edi, [eax][pLLI]
		mov edi, [edi]
CalcLZ:
		test esi, edi
		jnz CalcLZOver
		dec edx
		shr esi, 1
		loop CalcLZ
CalcLZOver:
		mov totalBits, edx
		mov dword ptr nowBit, 0
	}

	while (nowBit < totalBits)
	{
		__asm
		{
			mov esi, nowBit
			shr esi, 5    ;// /32
			shl esi, 2    ;// *4
			mov eax, pE
			add esi, [eax][pLLI]
			mov edx, [esi]
			mov nowDW, edx
			mov edx, totalBits
			sub edx, nowBit
			mov testBits, edx
			cmp edx, 32
			jbe TestHighestDWord
			;//mov testBits, 32
			jmp TestLowerDWords
		}
TestHighestDWord:
		for (a=0; a<testBits; a++)
		{
			__asm
			{
				test dword ptr nowDW, 1
				jz eDivide2
				;//and dword ptr nowDW, 0xfffffffe
			}
			c = ( m * c ) % n;
			__asm
			{
				mov edx, totalBits
				sub edx, nowBit
				cmp edx, 1
				jbe ExpModOver
			}
eDivide2:
			__asm	shr nowDW, 1
			m = (m * m) % n;
			__asm	inc nowBit
		}

TestLowerDWords:
		for (a=0; a<32; a++)
		{
			__asm
			{
				test dword ptr nowDW, 1
				jz eDivide2_2
				;//and dword ptr nowDW, 0xfffffffe
			}
			c = ( m * c ) % n;
eDivide2_2:
			__asm	shr nowDW, 1
			m = (m * m) % n;
			__asm	inc nowBit
		}
	}

ExpModOver:
	return c;


/*
	//C++算法
	LLongInt c(1);
	LLongInt m = *this;
	LLongInt zero((__int64)0);
	LLongInt one(1);
	LLongInt two(2);
	while ( e != zero)
	{
		if ( ( e % two ) == zero )
		{
			e = e / two;
			m = ( m * m ) % n;
		}
		else
		{
			e = e - one;
			c = ( m * c ) % n;
		}
	}
	return c;
*/

}