integer.cpp

关于大数运算的加 减 乘 除 模 等运算 运用了libtommath库的算法

/*
    Big Integer Operation
    SRC FILE
    BY CSK(陈士凯)
    [e-mail]
    www.csksoft.net
*/

#include "CiperLib.h"
#include "inner_support.h"

#include "string.h"
bool Integer::ms_b_inited =false;
unsigned int Integer::ms_u_data_arr_num = 0;
unsigned int Integer::ms_u_ref_cnt = 0;



void Integer::create_data_buf(Integer & i)
{
    if (i.m_p_data_arr != NULL) release_data_buf(i);
    i.m_p_data_arr = new unsigned int [ms_u_data_arr_num];
    i.m_acutual_len = 1;    //default is 1, not ZERO
    memset(i.m_p_data_arr, 0 , sizeof(unsigned int) * ms_u_data_arr_num);
}

void Integer::release_data_buf(Integer & i)
{
    if (i.m_p_data_arr) delete [] i.m_p_data_arr;
    i.m_p_data_arr = NULL;
}

bool Integer::Init(unsigned int u_data_arr_num)
{
    if (ms_b_inited) return false;
    unsigned int tmp;
    tmp = (u_data_arr_num + 31) & (~31);
    if (tmp ==0) return false;

    ms_u_data_arr_num = tmp / 32;
    ms_b_inited = true;

    unsigned int seed;

	_asm {
			RDTSC
            mov seed,eax
    }
    IntHelper::MZ_seed(seed);
    return true;
}

///////////////////////////////////////////////////////////////////////////////
void Integer::inner_init()
{
    m_p_data_arr = 0;
    m_dw_sign = 0;
    m_dw_isOverflow = 0;
    ms_u_ref_cnt ++;
    if (!ms_b_inited)
        Init(1024);
   
    create_data_buf(*this);
}


Integer::Integer()
{
    inner_init();
   
    create_data_buf(*this);

}

Integer::~Integer()
{
    ms_u_ref_cnt--;
    release_data_buf(*this);
}



Integer::Integer(const Integer & src)
{
    inner_init();
    copyFrom(src);
}

Integer::Integer(__int64 num)
{
    inner_init();
   
    create_data_buf(*this);
    fromInt64(num);
}


Integer::Integer(int num)
{
    inner_init();
   
    create_data_buf(*this);
    fromInt(num);
}


Integer::Integer(char *strNum, unsigned int  base)
{
    inner_init();
    if (!fromString(strNum)) fromInt(0);
}
/////////////////////////////////////////////////////////////////////////////////

bool Integer::fromString(char *strNum, unsigned int  base)
{
    this->zero();
    size_t arr_len = strlen(strNum);
    size_t i=0;
    if (strNum[0] == '-') 
    {

        i =1;
    }
    for(;i<arr_len;i++)
    {
        raw_mul_int(*this, base , *this);
        int current_val=strNum[i]-'0';
        plus(Integer(current_val));
    }
    if (strNum[0] == '-')
        this->m_dw_sign =1;
    return true;
}


/*
MAY CONTAIN BUGS!
*/
void Integer::fromInt64(__int64 num)
{
    zero();
    if (num ==0) return;

    int new_length;
   
    if (num < 0) { this->m_dw_sign = 1; num=-num; }
    new_length = 0;
    while(num > 0)
    {
        this->m_p_data_arr[new_length] = (unsigned int)(num & DWORD_BITMASK);
        num = num >> 32;
        new_length ++;
    }
    this->m_acutual_len = new_length;

}

void Integer::fromInt(int num)
{
    zero();
    if (num ==0) return;
    this->m_dw_sign = (num>=0)?0:1;
    this->m_p_data_arr[0] = (this->m_dw_sign==0)?num:-num;
    this->m_acutual_len = 1;
}

bool Integer::toString(char *strNum, unsigned int max_buffer_size, unsigned int  base) const
{

    bool isNotOverflow = false;
    char ch_tb[] = "0123456789ABCDEF";
    if (base>16) return false;

    unsigned int current_pos = 0;
    Integer tmp = *this;
    if (this->m_dw_sign)
        max_buffer_size --;
    while(!tmp.isZero())
    {
        if (current_pos >= max_buffer_size)
        {
            break;
        }
        strNum[current_pos + (this->m_dw_sign?1:0)] = ch_tb[Integer::raw_div_int(tmp,base,tmp)];
        current_pos++;
    }
    if (tmp.isZero())
    {
        isNotOverflow=true;
        if (current_pos ==0){
            strNum[ 0 ] = '0';
            strNum[ 1 ] = 0;
            return true;
        }
    }
    strNum[current_pos+ (this->m_dw_sign?1:0)] = 0;
    for (unsigned int pos =0; pos < current_pos/2 ; pos++)
    {
        char tmp = strNum[current_pos - pos - 1+ (this->m_dw_sign?1:0)];
        strNum[current_pos - pos - 1+ (this->m_dw_sign?1:0)] = strNum[pos+ (this->m_dw_sign?1:0)];
        strNum[pos+ (this->m_dw_sign?1:0)] = tmp;
    }

    
    if (this->m_dw_sign) strNum[0] = '-';
    return isNotOverflow;
}

Integer & Integer::copyFrom(const Integer & src)
{
    this->m_dw_sign = src.m_dw_sign;
    this->m_acutual_len = src.m_acutual_len;
    memcpy(this->m_p_data_arr,src.m_p_data_arr,sizeof(unsigned int) * MAX(src.m_acutual_len,m_acutual_len));
    return *this;
}




////////////////////////////////////////////////////////////////////////////////////////////////////////
//  OPERATION
int Integer::compare(const Integer & right) const
{
    if (&right == this) return 0; //the same object
    int sig;
    
    if (this->m_dw_sign != right.m_dw_sign) return (right.m_dw_sign <<1) -1;    //diferent sig
    

    sig= (this->m_dw_sign == 0)?1:-1;
    //same sig
    if (this->m_acutual_len > right.m_acutual_len){ return sig;}  // A.length > B.length
    else
    {
        if (this->m_acutual_len < right.m_acutual_len) return -sig;   //A.length < B.length
        for(int i=this->m_acutual_len-1;i>=0;i--)
        {
            if(this->m_p_data_arr[i]>right.m_p_data_arr[i])return sig;
            if(this->m_p_data_arr[i]<right.m_p_data_arr[i])return -sig;
        }
    }

    return 0;
}

bool Integer::isZero() const
{
    return (this->m_acutual_len == 1 && this->m_p_data_arr[0] ==0);
}

Integer& Integer::zero()
{
    memset(this->m_p_data_arr,0,ms_u_data_arr_num);
    this->m_acutual_len=1;
    this->m_dw_sign = 0;
    return *this;
}




////////////////////////////////////////////////////////////////////////////////////////////////////////
//  OPERATOR

Integer & Integer::operator= (const Integer &src)
{
    return copyFrom(src);
}

int Integer::operator>(const Integer &right) const
{
    return (compare(right)==1)?1:0;
}

int Integer::operator<(const Integer &right) const
{
    return (compare(right)==-1)?1:0;
}

int Integer::operator==(const Integer &right) const
{
    return (compare(right)==0)?1:0;
}

int Integer::operator!=(const Integer &right) const
{
    return (compare(right)==0)?0:1;
}


int Integer::operator>=(const Integer &right) const
{
    return (compare(right)>=0)?1:0;
}

int Integer::operator<=(const Integer &right) const
{
    return (compare(right)<=0)?1:0;
}


Integer & Integer::operator+=(const Integer &right)
{
    return this->plus(const_cast<Integer &>(right));
}
Integer & Integer::operator+=(int right)
{
    return this->plus(Integer(right));
}

Integer & Integer::operator-=(const Integer &right)
{
    return this->minus(const_cast<Integer &>(right));
}
Integer & Integer::operator-=(int right)
{
    return this->minus(Integer(right));
}

Integer & Integer::operator*=(const Integer &right)
{
    return this->mul(right,*this);
}
Integer & Integer::operator*=(int right)
{
    this->raw_mul_int(*this,right,*this);
    return *this;
}

Integer & Integer::operator/=(const Integer &right)
{   
    return this->div(right);
}
Integer & Integer::operator/=(int right)
{
    this->raw_div_int(*this,right,*this);
    return *this;
}

Integer & Integer::operator%=(const Integer &right)
{
    return this->mod(right);
}
Integer & Integer::operator%=(int right)
{
    unsigned int tmp_ans = this->raw_div_int(*this,right,*this);
    this->fromInt64((__int64)tmp_ans);
    return *this;
}


Integer Integer::operator+(const Integer &right)
{
    Integer ans =*this;
    add_sub_director(ans,const_cast<Integer &>(right),0);
    return Integer(ans);
}
Integer  Integer::operator+(int right)
{
    Integer ans =*this;
    add_sub_director(ans,Integer(right),0);
    return Integer(ans);
}

Integer  Integer::operator-(const Integer &right)
{
    Integer ans =*this;
    add_sub_director(ans,const_cast<Integer &>(right),1);
    return Integer(ans);
}
Integer  Integer::operator-(int right)
{
    Integer ans =*this;
    add_sub_director(ans,Integer(right),1);
    return Integer(ans);
}

Integer  Integer::operator*(const Integer &right)
{
    Integer ans;
    raw_mul(*this,right,ans);
    return Integer(ans);
}
Integer  Integer::operator*(int right)
{

    Integer ans;
    raw_mul_int(*this,right,ans);
    return Integer(ans);
}

Integer  Integer::operator/(const Integer &right)
{
    Integer ans = *this;
    ans.div(right);
    return Integer(ans);
}
Integer  Integer::operator/(int right)
{
    Integer ans ;
    raw_div_int(*this,right,ans);
    return Integer(ans);
}

Integer  Integer::operator%(const Integer &right)
{
    Integer ans = *this;
    ans.mod(right);
    return Integer(ans);
}
Integer  Integer::operator%(int right)
{
    Integer tmp;
    unsigned int tmp_ans = this->raw_div_int(*this,right,tmp);
    
    return Integer((__int64)right);
}