📄 largeint.cpp
字号:
// LargeInt.cpp
// 作者 pAnic 2005年9月22日。
// CLargeInt 类的实现。
//////////////////////////////////////////////////////////////////////
#include "LargeInt.h"
#include <memory.h>
#include <algorithm>
namespace panic
{
std::vector<T_DWORD> CLargeInt::_smallPrimes;
void CLargeInt::InitSmallPrimes(T_DWORD count)
{
if( !_smallPrimes.size() ) //尚未初始化
{
_smallPrimes.reserve(count);
_smallPrimes.push_back(3);
_smallPrimes.push_back(5);
_smallPrimes.push_back(7);
_smallPrimes.push_back(11);
_smallPrimes.push_back(13);
T_DWORD i = 0;
for( i = 17; _smallPrimes.size() < count; i+= 2)
{
bool bePrime = true;
for( T_DWORD j = 0; j < _smallPrimes.size(); j++ )
{
if( ( _smallPrimes[j] * _smallPrimes[j] ) > i ) //已经不可能了。
break;
if( (i % _smallPrimes[j]) == 0) //可以整除
bePrime = false;
}
if( bePrime ) //是素数
{
_smallPrimes.push_back(i);
}
}
}
}
bool CLargeInt::SmallPrimeTest(const CLargeInt& n)
{
if( n._data[0] == 2 && n._len == 1) return true; //2是质数。
if( n._len == 1 && n._data[0] <= _smallPrimes.back() ) //整数比表中的数据小。
{
if( std::binary_search(_smallPrimes.begin(),_smallPrimes.end(),n._data[0]) ) //找到，n存在于质数表中。
{
return true; //通过测试，数n是质数。
}
return false; //没有通过，n是合数。
}
else
{
CLargeInt temp;
T_DWORD r;
for( T_DWORD i = 0; i < _smallPrimes.size(); i++)
{
Div(n,_smallPrimes[i],temp,r); //依次检查是否能整除。
if( r == 0) return false; //能整除，说明 n 有小于它的质因子。n 是合数。
}
return true; // n 没有表中已有的质因子，n有可能是质数。
}
}
bool CLargeInt::IsPrime(const CLargeInt &n)
{
InitSmallPrimes();
if( n._data[0]&1 ) //奇数
{
if( n._len == 1 && n._data[0] <= _smallPrimes.back() )
{
return SmallPrimeTest(n); //是小质数表中的一个质数。
}
else
{
if( SmallPrimeTest(n) ) //通过小质数测试
{
for( int i = 0; i < 5; i++)
{
CLargeInt a(_smallPrimes[ _smallPrimes.size() - i]);
if( !RabinMillerTest(n,a) ) return false;
}
return true; //99.9%的可能是质数。
}
else return false;
}
}
return false;
}
void CLargeInt::CreatePrime(CLargeInt &n)
{
n._data[0] |= 0x01;
while( !IsPrime(n) )
{
Add(n,2,n); //步进2，寻找最接近的下一个质数。这个算法并不是寻找质数最好的算法，但是它可以保证寻找到相邻的质数。
}
}
CLargeInt::CLargeInt(T_DWORD value) : _len(1)
{
_data[0] = value;
}
CLargeInt::CLargeInt(const CLargeInt& other)
{
Copy(other,*this);
}
CLargeInt::CLargeInt(const char * str): _len(1)
{
_data[0] = 0;
if(str && strlen(str) > 2 && ( strncmp(str,"0x",2) == 0 || strncmp(str,"0X",2) == 0 ) )
{
CLargeInt temp;
const char * p = str + 2;
while( *p )
{
char ch = *p;
T_DWORD n = 0;
switch(ch)
{
case '0':case '1':case '2': case '3':case '4':case '5':case '6':case '7':case '8':case '9':
n = (ch - '0');
break;
case 'A':case 'B':case 'C':case 'D':case 'E':case 'F':
n = (ch - 'A' + 10);
break;
case 'a':case 'b':case 'c':case 'd':case 'e':case 'f':
n = (ch - 'a' + 10);
break;
}
p++;
Mul(*this,16,temp);
Add(temp,n,*this);
}
}
else
{//这里应该用来处理除了0x开头的16进制字符串的情况。
__asm int 3;
}
}
CLargeInt::~CLargeInt()
{
}
void CLargeInt::Copy(const CLargeInt& source,CLargeInt& target)
{
if( &source != &target ) //避免自身拷贝。
{
target._len = source._len;
//相信库函数能提供最高效的实现。
memcpy(target._data,source._data,source._len*4);
}
}
bool CLargeInt::Equal(const CLargeInt& source,const CLargeInt& target)
{
if( source._len == target._len )
{
//相信库函数能提供最高效的实现。
return !(memcmp(source._data,target._data,source._len*4));
}
else return false;
}
bool CLargeInt::LargerEqual(const CLargeInt& source,const CLargeInt& target,T_DWORD offset )
{
if( source._len > (target._len + offset) ) return true;
else if( source._len < (target._len + offset) ) return false;
else
{
int end = offset;
for( int i = source._len - 1; i >= end ; i--)
{
T_DWORD ii = i - offset;
if( source._data[i] > target._data[ii] ) return true; //大于
else if( source._data[i] < target._data[ii] ) return false;
}
return true; //相等。
}
}
void CLargeInt::Add(const CLargeInt &augend, const CLargeInt &addend, CLargeInt &sum,T_DWORD offset)
{
T_DWORD len,len1,len2; //len绝对不能<1，否则会出错。
T_DWORD *p1 = 0;
T_DWORD *p2 = 0;
T_DWORD *p3 = 0;
if( augend._len >= (addend._len+offset) )
{
len = augend._len - offset;
len1 = addend._len;
len2 = len - len1;
p1 = augend._data+offset;
p2 = addend._data;
p3 = sum._data+offset;
}
else
{
len = addend._len;
if( augend._len <= offset )
{
augend._data[offset] = 0;
len1 = 1;
len2 = addend._len - len1;
}
else
{
len1 = augend._len - offset;
len2 = addend._len - len1;
}
p1 = addend._data;
p2 = augend._data + offset;
p3 = sum._data + offset;
}
__asm
{
pushad;
//载入计算地址
mov esi,p1;
mov ebx,p2;
mov edi,p3;
mov eax,len1;
sal eax,2;
//计算末地址
add esi,eax;
add ebx,eax;
add edi,eax;
mov ecx,eax;
add ecx,4*7;
and ecx,0xFFFFFFE0; //ecx - ecx%32,这里的ecx就变成了偏移址，同时也是累加器。
neg ecx; //取负，用作累加。
sar eax,2; //回复到原来的长度
neg eax; //取负
and eax,dword ptr 7;
jz labeladd0; //如果低位是0，说明长度至少有8(因为长度为0是非法的)
mov edx,dword ptr 0xC;
mul edx; //eax变为相对偏移址。
lea edx,labeladd1; //载入起始地址
sub edx,dword ptr 0xC;
add eax,edx; //计算出跳转地址
clc; //清除标志位。
jmp eax; //跳转
labeladdloop:
popf;
labeladd0:
mov eax,[esi+ecx+0*4];
adc eax,[ebx+ecx+0*4];
mov [edi+ecx+0*4],eax;
labeladd1:
mov eax,[esi+ecx+1*4];
adc eax,[ebx+ecx+1*4];
mov [edi+ecx+1*4],eax;
//labeladd2:
mov eax,[esi+ecx+2*4];
adc eax,[ebx+ecx+2*4];
mov [edi+ecx+2*4],eax;
//labeladd3:
mov eax,[esi+ecx+3*4];
adc eax,[ebx+ecx+3*4];
mov [edi+ecx+3*4],eax;
//labeladd4:
mov eax,[esi+ecx+4*4];
adc eax,[ebx+ecx+4*4];
mov [edi+ecx+4*4],eax;
//labeladd5:
mov eax,[esi+ecx+5*4];
adc eax,[ebx+ecx+5*4];
mov [edi+ecx+5*4],eax;
//labeladd6:
mov eax,[esi+ecx+6*4];
adc eax,[ebx+ecx+6*4];
mov [edi+ecx+6*4],eax;
//labeladd7:
mov eax,[esi+ecx+7*4];
adc eax,[ebx+ecx+7*4];
mov [edi+ecx+7*4],eax;
//labeladd8:
pushf;
add ecx,32;
jnz labeladdloop;
//运行到这里了，说明两数重合部分已经处理完了。开始处理两数相差的部分。
mov ecx,len2; //载入长度
xor ebx,ebx; //因为ebx指向的缓冲区废弃不用了，所以使用已经空闲的ebx寄存器。
cmp ebx,ecx; //判断ecx是否等于ebx(0)
jz labelcarry; //如果相等，说明已经处理完了，跳转到处理最后一次进位的地方。
labelfix:
popf; //弹出上次的标志位。
mov eax,[esi+ebx*4];
adc eax,0;
mov [edi+ebx*4],eax;
//如果这里没有进位，剩下的部分可以直接拷贝。拷贝的长度就是ecx-1
jnc labelcopy;
pushf; //保存标志位。
inc ebx; //步进
dec ecx;
jnz labelfix; //循环。
labelcarry:
popf; //弹出标志位
jnc labelend; //没有进位就直接结束
//没有跳转说明有进位：
mov dword ptr [edi+ebx*4],dword ptr 0x00000001; //直接置1
lea eax,len;
inc [eax]; //总长度+1
inc ecx; //补一次。
labelcopy:
dec ecx;
sal ecx,2;
cmp edi,esi; //比较源地址和目标地址，如果相同就跳过。
jz labelend;
sal ebx,2;
add ebx,4;
add edi,ebx;
add esi,ebx;
rep movs dword ptr [edi],dword ptr [esi];
labelend:
popad;
}
sum._len = len + offset;
}
void CLargeInt::Sub(const CLargeInt& minuend,const CLargeInt& subtrahend,CLargeInt& difference,T_DWORD offset)
{
T_DWORD len,len1,len2; //len绝对不能<1，否则会出错。
T_DWORD *p1 = 0;
T_DWORD *p2 = 0;
T_DWORD *p3 = 0;
if( minuend._len >= (subtrahend._len+offset) )
{
len = minuend._len- offset;
len1 = subtrahend._len;
len2 = len - len1;
p1 = minuend._data + offset;
p2 = subtrahend._data;
p3 = difference._data + offset;
}
else
{
__asm int 3; //出错。
}
__asm
{
pushad;
//载入计算地址
mov esi,p1;
mov ebx,p2;
mov edi,p3;
mov eax,len1;
sal eax,2;
//计算末地址
add esi,eax;
add ebx,eax;
add edi,eax;
mov ecx,eax;
add ecx,4*7;
and ecx,0xFFFFFFE0; //ecx - ecx%32,这里的ecx就变成了偏移址，同时也是累加器。
neg ecx; //取负，用作累加。
sar eax,2; //回复到原来的长度
neg eax; //取负
and eax,dword ptr 7;
jz labeladd0; //如果低位是0，说明长度至少有8(因为长度为0是非法的)
mov edx,dword ptr 0xC;
mul edx; //eax变为相对偏移址。
lea edx,labeladd1; //载入起始地址
sub edx,dword ptr 0xC;
add eax,edx; //计算出跳转地址
clc; //清除标志位。
jmp eax; //跳转
labeladdloop:
popf;
labeladd0:
mov eax,[esi+ecx+0*4];
sbb eax,[ebx+ecx+0*4];
mov [edi+ecx+0*4],eax;
labeladd1:
mov eax,[esi+ecx+1*4];
sbb eax,[ebx+ecx+1*4];
mov [edi+ecx+1*4],eax;
//labeladd2:
mov eax,[esi+ecx+2*4];
sbb eax,[ebx+ecx+2*4];
mov [edi+ecx+2*4],eax;
//labeladd3:
mov eax,[esi+ecx+3*4];
sbb eax,[ebx+ecx+3*4];
mov [edi+ecx+3*4],eax;
//labeladd4:
mov eax,[esi+ecx+4*4];
sbb eax,[ebx+ecx+4*4];
mov [edi+ecx+4*4],eax;
//labeladd5:
mov eax,[esi+ecx+5*4];
sbb eax,[ebx+ecx+5*4];
mov [edi+ecx+5*4],eax;
//labeladd6:
mov eax,[esi+ecx+6*4];
sbb eax,[ebx+ecx+6*4];
mov [edi+ecx+6*4],eax;
//labeladd7:
mov eax,[esi+ecx+7*4];
sbb eax,[ebx+ecx+7*4];
mov [edi+ecx+7*4],eax;
//labeladd8:
pushf;
add ecx,32;
jnz labeladdloop;
//运行到这里了，说明两数重合部分已经处理完了。开始处理两数相差的部分。
mov ecx,len2; //载入长度,
//只处理p1的buf
xor ebx,ebx; //因为ebx指向的缓冲区废弃不用了，所以使用已经空闲的ebx寄存器。
cmp ebx,ecx; //判断ecx是否等于ebx
jz labelcarry; //如果相等，说明已经处理完了，跳转到处理最后一次进位的地方。
labelfix:
popf; //弹出上次的标志位。
mov eax,[esi+ebx*4];
sbb eax,0;
mov [edi+ebx*4],eax;
//如果这里没有进位，剩下的部分可以直接拷贝。拷贝的长度就是ecx-1
jnc labelcopy;
pushf; //保存标志位。
inc ebx; //步进
dec ecx;
jnz labelfix; //循环。
labelcarry:
popf; //弹出标志位
jnc labelend; //没有进位就直接结束
//没有跳转说明有进位：
int 3; //说明减数不够，结果为负
mov dword ptr [edi+ebx*4],dword ptr 0x00000001; //直接置1
lea eax,len;
dec [eax]; //总长度-1
inc ecx; //补一次。
labelcopy:
dec ecx;
sal ecx,2;
cmp edi,esi; //比较源地址和目标地址，如果相同就跳过。
jz labelend;
sal ebx,2;
add ebx,4;
add edi,ebx;
add esi,ebx;
rep movs dword ptr [edi],dword ptr [esi];
labelend:
popad;
}
difference._len = len+offset;
for( T_DWORD i = difference._len-1; i > 0; i--)
{
if( difference._data[i] == 0 ) //末尾是0
{
difference._len--;
}
else break;
}
}
void CLargeInt::Mul(const CLargeInt& faciend,T_DWORD multiplier,CLargeInt& product)
{
T_DWORD len; //len绝对不能<1，否则会出错。
T_DWORD *p1 = 0;
T_DWORD *p2 = 0;
T_DWORD *p3 = 0;
len = faciend._len;
p1 = faciend._data;
p2 = 0;
p3 = product._data;
memset(p3,0,(len+1)*4);
__asm
{
pushad;
//载入计算地址
mov esi,p1;
mov edi,p3;
mov ebx,multiplier
mov eax,len;
sal eax,2;
//计算末地址
add esi,eax;
add edi,eax;
mov ecx,eax;
add ecx,4*7;
and ecx,0xFFFFFFE0; //ecx - ecx%32,这里的ecx就变成了偏移址，同时也是累加器。
neg ecx; //取负，用作累加。
sar eax,2; //回复到原来的长度
neg eax; //取负
and eax,dword ptr 7;
jz labeladd0; //如果低位是0，说明长度至少有8(因为长度为0是非法的)
mov edx,dword ptr 0xe; //0xe是跳转地址的系数。
mul edx; //eax变为相对偏移址。
lea edx,labeladd1; //载入起始地址
sub edx,dword ptr 0xe;
add eax,edx; //计算出跳转地址
clc; //清除标志位。
jmp eax; //跳转
labeladdloop:
labeladd0:
mov eax,[esi+ecx+0*4];
mul ebx;
add [edi+ecx+0*4],eax;
adc [edi+ecx+1*4],edx;
labeladd1:
mov eax,[esi+ecx+1*4];
mul ebx;
add [edi+ecx+1*4],eax;
adc [edi+ecx+2*4],edx;
//labeladd2:
mov eax,[esi+ecx+2*4];
mul ebx;
add [edi+ecx+2*4],eax;
adc [edi+ecx+3*4],edx;
//labeladd3:
mov eax,[esi+ecx+3*4];
mul ebx;
add [edi+ecx+3*4],eax;
adc [edi+ecx+4*4],edx;
//labeladd4:
mov eax,[esi+ecx+4*4];
mul ebx;
add [edi+ecx+4*4],eax;
adc [edi+ecx+5*4],edx;
//labeladd5:
mov eax,[esi+ecx+5*4];
mul ebx;
add [edi+ecx+5*4],eax;
adc [edi+ecx+6*4],edx;
//labeladd6:
mov eax,[esi+ecx+6*4];
mul ebx;
add [edi+ecx+6*4],eax;
adc [edi+ecx+7*4],edx;
//labeladd7:
mov eax,[esi+ecx+7*4];
mul ebx;
add [edi+ecx+7*4],eax;
adc [edi+ecx+8*4],edx;
//labeladd8:
add ecx,32;
jnz labeladdloop;
//labelend:
popad;
}
product._len = len+1;
for( T_DWORD i = product._len-1; i > 0; i--)
{
if( product._data[i] == 0 ) //末尾是0
{
product._len--;
}
else break;
}
}
void CLargeInt::RCR(CLargeInt& n)
{
T_DWORD len; //len绝对不能<1，否则会出错。
T_DWORD *p1 = 0;
len = n._len;
p1 = n._data;
__asm
{
pushad;
//载入计算地址
mov esi,p1;
mov eax,len;
mov ecx,eax;
add ecx,dword ptr 15;
and ecx,dword ptr 0xFFFFFFF0;
mov eax,ecx;
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -