llongint.cpp

应用编码与计算机密码学program 《应用编码与计算机密码学》程序 RSA算法源代码

#include <stdlib.h>
#include <string.h>
#include "LLongInt.h"
//---------------------------------------------------------------------------------------------------
//---------------------------------------------------------------------------------------------------
int LLongInt::Trim( )
{
	int oldLen = lliLength;
	while ( pLLI[lliLength-1] == 0 && lliLength > 1)
		lliLength--;
	return (lliLength == oldLen );
}

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

LLongInt::LLongInt()
{
	sign = 0;
	lliLength = 1;
	pLLI = new unsigned int[1];
	*pLLI = 0;
}

LLongInt::LLongInt(__int64 i64)
{
	pLLI = new unsigned int[2];
	lliLength = 2;
	if ( i64 < 0 )
	{
		sign = 1;
		i64 = -i64;
	}
	else
		sign = 0;
	memcpy(pLLI, &i64, 8);
	Trim( );
}

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

LLongInt::LLongInt(char *strDec)
{
	if ( strDec[0] == '-' ) 
		sign = 1;
	else
		sign = 0;
	int strLen = strlen(strDec);
	if ( strLen % 4 == 0 )
		lliLength = strLen / 4;
	else
		lliLength = strLen / 4 + 1;
	pLLI = new unsigned int[lliLength];
	unsigned int *pTmp = new unsigned int[lliLength];
	memset(pLLI, 0, lliLength*4);
	memset(pTmp, 0, lliLength*4);
	unsigned int *pLLI = this->pLLI;
	int a, intCount;
	__asm
	{
		pusha
		mov ebx, this
		mov eax, [ebx][sign]
		mov dword ptr a, eax
WhileA1:
		mov edx, a
		mov intCount, edx
		shr dword ptr intCount, 2
		inc intCount
		cmp edx, strLen
		jb LLIDec2Hex
		jmp LLIDec2HexOver
LLIDec2Hex:

		mov esi, 0
		mov ecx, intCount
CopyToTmp:
		mov eax, pLLI
		mov ebx, [eax][esi*4]
		mov eax, pTmp
		mov [eax][esi*4], ebx
		inc esi
		loop CopyToTmp

		mov eax, pLLI
		mov esi, intCount
		dec esi
EightTimes:
		cmp esi, 0
		jnz EightTimesLoop
		jmp EightTimesOver
EightTimesLoop:
		mov ebx, [eax][esi*4-4]
		shld [eax][esi*4], ebx, 3
		dec esi
		jmp EightTimes
EightTimesOver:
		shl dword ptr [eax][esi], 3

		mov eax, pTmp
		mov esi, intCount
		dec esi
TwoTimesTmp:
		cmp esi, 0
		jnz TwoTimesLoop
		jmp TwoTimesOver
TwoTimesLoop:
		mov ebx, [eax][esi*4-4]
		shld [eax][esi*4], ebx, 1
		dec esi
		jmp TwoTimesTmp
TwoTimesOver:
		shl dword ptr [eax][esi], 1

		mov ecx, intCount
		xor esi, esi
		clc
TenTimes:
		mov eax, pTmp
		mov ebx, [eax][esi*4]
		mov eax, pLLI
		adc [eax][esi*4], ebx
		inc esi
		loop TenTimes
		
		mov ecx, intCount
		mov esi, a
		xor eax, eax
		mov ebx, strDec
		mov al, byte ptr [ebx][esi];
		sub al, '0'
		xor esi, esi
		mov ebx, pLLI
		add [ebx][esi*4], eax
		inc esi
		dec ecx
		jnz AddDecBit
		jmp AddDecBitOver
AddDecBit:
		mov eax, pLLI
		adc dword ptr [eax][esi*4], 0
		inc esi
		loop AddDecBit
AddDecBitOver:
		inc a
		jmp WhileA1
LLIDec2HexOver:
		popa
	}
	Trim( );
	delete pTmp;
}

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

LLongInt LLongInt::operator -( )
{
	__asm     //	sign = sign ^ 1;
	{
		mov eax, this
		xor dword ptr [eax][sign], 1
	}
	return *this;
}

LLongInt LLongInt::Abs(LLongInt &lli)
{
	return LLongInt(lli.pLLI, lli.lliLength, 0);
}

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

LLongInt::LLongInt(unsigned int *strHex, int intCount, int sign)
{
	this->sign = sign;
	lliLength = intCount;
	pLLI = new unsigned int[intCount];
	memcpy(pLLI, strHex, intCount*4);
	Trim( );
}

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

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

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

LLongInt::~LLongInt( )
{
	if ( pLLI != NULL )
		delete pLLI;
}

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

LLongInt LLongInt::operator +(LLongInt &another)
{
	if ( sign != another.sign)
	{
		if ( sign == 0)
			return (*this-(-another));
		else
			return (another - (-*this));
	}
	int a, b, len;
	unsigned int *pSrcLLI;
	unsigned int *pResult;
	unsigned int *pAddLLI;
	if ( lliLength <= another.lliLength )
	{
		pResult = new unsigned int[another.lliLength+1];
		a = lliLength;
		b = another.lliLength + 1 - a;
		pSrcLLI = pLLI;
		pAddLLI = another.pLLI;
		len = another.lliLength;
	}
	else
	{
		pResult = new unsigned int[lliLength+1];
		a = another.lliLength;
		b = lliLength + 1 - a;
		pSrcLLI = another.pLLI;
		pAddLLI = pLLI;
		len = lliLength;
	}

	__asm
	{
		mov eax, pResult
		mov ebx, pSrcLLI
		xor esi, esi
		mov ecx, a
CopyToResult1:
		mov edx, [ebx][esi*4]
		mov [eax][esi*4], edx
		inc esi
		loop CopyToResult1

		mov ecx, b
ZeroResult1:
		mov dword ptr [eax][esi*4], 0
		inc esi
		loop ZeroResult1

		xor esi, esi
		mov ebx, pAddLLI
		mov ecx, len
		clc
AddLoop:
		mov edx, [ebx][esi*4]
		adc [eax][esi*4], edx
		inc esi
		loop AddLoop
		adc [eax][esi*4], 0
	}
	LLongInt rcLLI(pResult, len+1, sign);
	delete pResult;
	return rcLLI;
}

LLongInt LLongInt::operator -(LLongInt &another)
{
	if ( sign != another.sign )
		return (*this + (-another));
	if ( sign == 0 )
	{
		if ( *this < another )
			return -(another-*this);
	}
	else
	{
		if ( *this > another )
			return -(another-*this);
	}

	int a, b ;
	unsigned int *pSrcLLI;
	unsigned int *pResult;
	unsigned int *pSubLLI;

	pResult = new unsigned int[lliLength];
	a = another.lliLength;
	b = lliLength-another.lliLength;
	pSrcLLI = pLLI;
	pSubLLI = another.pLLI;

	__asm
	{
		mov eax, this
		mov ecx, [eax][lliLength]
		mov eax, pResult
		mov ebx, pSrcLLI
		xor esi, esi
CopyToResult1:
		mov edx, [ebx][esi*4]
		mov [eax][esi*4], edx
		inc esi
		loop CopyToResult1

		xor esi, esi
		mov ebx, pSubLLI
		mov ecx, a
		clc
SubLoop1:
		mov edx, [ebx][esi*4]
		sbb [eax][esi*4], edx
		inc esi
		loop SubLoop1

		mov ecx, b
		cmp ecx, 0
		jz SubOver
SubLoop2:
		sbb dword ptr [eax][esi*4], 0
		inc esi
		loop SubLoop2
SubOver:
	}
	LLongInt rcLLI(pResult, lliLength, sign);
	delete pResult;
	return rcLLI;
}

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

LLongInt LLongInt::operator *(LLongInt &another)
{
	int rSign, tmpLen;
	unsigned int *rpLLI;
	unsigned int *pM1 = pLLI;
	unsigned int *pM2 = another.pLLI;
	int m1Len = lliLength;
	int m2Len = another.lliLength;
	__asm
	{
		;//求出rSign
		mov eax, this
		mov ecx, [eax][sign]
		mov ebx, another
		xor ecx, [ebx][sign]
		mov rSign, ecx
		;//
		mov ecx, [eax][lliLength]
		add ecx, [ebx][lliLength]
		mov tmpLen, ecx
	}
	rpLLI = new unsigned int[tmpLen];
	__asm
	{
		;//填充0
		mov eax, 0h
		mov edi, [rpLLI]
		mov ecx, tmpLen
		cld
		rep stosd

		mov esi, 0
while1:
		mov edi, 0
		cmp esi, m2Len
		jb while1Inner
		jmp while1Over
while1Inner:
while2:
		cmp edi, m1Len
		jb while2Inner
		jmp while2Over
while2Inner:
		mov eax, pM2
		mov ebx, [eax][esi*4]
		mov ecx, pM1
		mov eax, [ecx][edi*4]
		mul ebx
		mov ecx, esi
		add ecx, edi
		mov ebx, rpLLI
		add [ebx][ecx*4], eax
		inc ecx
		adc [ebx][ecx*4], edx
addForward:
		jnc addForwardOver
		inc ecx
		adc dword ptr [ebx][ecx*4], 0h
		jmp addForward
addForwardOver:
		inc edi
		jmp while2
while2Over:
		inc esi
		jmp while1
while1Over:
	}
	LLongInt rc(rpLLI, tmpLen, rSign);
	delete rpLLI;
	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 LLongInt((__int64)0);
	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*/ ,rSign;
	int totalShiftBits, shiftedBits = 0;
	__asm
	{
		//求出rSign
		mov eax, another
		mov ebx, this
		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
		//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