?? 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 ÷nd, 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;
*/
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -