llongint.cpp

应用编码与计算机密码学>程序 如果好的话请发言

		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
	}
	LLongInt rc(pQuotient, quotientLen, rSign);
	delete pQuotient;
	delete pDividendLLI;
	return rc;
}

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

LLongInt LLongInt::operator %(LLongInt &another)
{
	unsigned int *pQuotient;
	int quotientLen;
	if (Abs(*this) >= Abs(another))
	{
	   quotientLen = this->lliLength - another.lliLength + 1;
       pQuotient = new unsigned int[quotientLen];
	}
	else
		return *this;
	unsigned int *pQuotient2 = pQuotient + quotientLen - 1;
	unsigned int *pDivisorLLI = another.pLLI;
	unsigned int *pDivisorLLI2 = another.pLLI + another.lliLength - 1;
	unsigned int *pDividendLLI = new unsigned int[this->lliLength+2];
	unsigned int *pDividendLLI1 = pDividendLLI;
	unsigned int *pDividendLLI2;
	int divisorLZs /*, dividendLZs*/ ;
	int totalShiftBits, shiftedBits = 0;
	__asm
	{
		mov eax, another
		mov ebx, this
		//拷贝被除数
		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 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
	}
	LLongInt rc(pDividendLLI1, another.lliLength, this->sign);
	delete pQuotient;
	delete pDividendLLI;
	return rc;
}

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

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 ( lliLength==1 && another.lliLength==1 && pLLI[0]==0 && another.pLLI[0]==0)
		return 1;
	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 ( lliLength==1 && another.lliLength==1 && pLLI[0]==0 && another.pLLI[0]==0)
		return 0;
	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 ( lliLength==1 && another.lliLength==1 && pLLI[0]==0 && another.pLLI[0]==0)
		return 0;
	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