www.pudn.com > CiperLib_release_by_csk.rar > int_op.cpp
/*
Big Integer Operation
ADD/SUB/MUL/DIV/MOD operation
SRC FILE
BY CSK(³ÂÊ¿¿)
CSK@live.com
www.csksoft.net
*/
#include "CiperLib.h"
#include "inner_support.h"
#pragma warning(disable:4731)
inline void Integer::raw_add(Integer &src, const Integer &dest)
{
unsigned int dest_length, src_length;
if (src.m_acutual_len >= dest.m_acutual_len)
{
dest_length = src.m_acutual_len;
src_length = dest.m_acutual_len;
}else
{
dest_length = dest.m_acutual_len;
src_length = src.m_acutual_len;
}
if (dest_length < Integer::ms_u_data_arr_num) dest_length++;
src.m_dw_isOverflow = 0; //clear overflow flag
unsigned int pos = 0;
//ADD CODE-- C-Style--slow..
#ifdef _NOTUSEASM
unsigned int carry_flag = 0;
// unsigned int result;
for(;pos < src_length; pos++) //add all columns of src and dest
{
unsigned int src_value;
src_value = src.m_p_data_arr[pos];
src.m_p_data_arr[pos] += dest.m_p_data_arr[pos] + carry_flag;
if (src.m_p_data_arr[pos] > src_value) { //is overflow?
carry_flag = 0;
}
else if (src.m_p_data_arr[pos] < dest.m_p_data_arr[pos]){
carry_flag = 1;
}
}
for(;pos < dest_length && carry_flag; pos++) //continue to add, caused by the sideeffect of carry_flag
{
unsigned int src_value;
src_value = src.m_p_data_arr[pos];
src.m_p_data_arr[pos] += carry_flag;
if (src.m_p_data_arr[pos] > src_value) { //is overflow?
carry_flag = 0;
}
else if (src.m_p_data_arr[pos] < src_value){
carry_flag = 1;
}
}
//ok, the algorithm should stop here, otherwise overflow happens..
if (carry_flag)//overflow
{
src.m_dw_isOverflow = 1;
}
#endif
#ifndef _NOTUSEASM
//ADD CODE-- ASM--hard to read, but faster
unsigned int * src_ptr,* dest_ptr, * is_overflow_ptr;
src_ptr = src.m_p_data_arr;
dest_ptr = const_cast(dest.m_p_data_arr);
is_overflow_ptr = &src.m_dw_isOverflow;
unsigned int remain_offset = dest_length - src_length;
__asm
{
// PUSHAD //save current register
mov edi, src_ptr
mov esi, dest_ptr //set base addr
xor ebx, ebx //set counter, and clear carry flag
mov ecx, src_length
firstl:
mov eax, [esi + ebx] //load dest data
adc [edi+ebx], eax //Add with carry flag
inc ebx
inc ebx
inc ebx
inc ebx //counter ++
dec ecx
jnz firstl //loop if counter1) dest_length--;
src.m_acutual_len = dest_length;
}
inline void Integer::raw_sub(Integer &src, const Integer &dest)
{
//assume src>dest and both are positive
unsigned int pos =0;
unsigned int dest_length = dest.m_acutual_len;
#ifdef _NOTUSEASM
unsigned int borrow_flag = 0;
for (; pos < dest_length || borrow_flag;pos++)
{
unsigned int src_value;
src_value = src.m_p_data_arr[pos];
src.m_p_data_arr[pos] -= dest.m_p_data_arr[pos] - borrow_flag;
if (src.m_p_data_arr[pos]src_value){
borrow_flag=1;
}
}
#endif
#ifndef _NOTUSEASM
unsigned int * src_ptr,* dest_ptr;
src_ptr = src.m_p_data_arr;
dest_ptr = const_cast(dest.m_p_data_arr);
__asm
{
// PUSHAD //save current register
mov edi, src_ptr
mov esi, dest_ptr //set base addr
xor ebx, ebx //set counter, and clear carry flag
mov ecx, dest_length
firstl:
mov eax, [esi + ebx] //load dest data
sbb [edi+ebx], eax //sub with carry flag
inc ebx
inc ebx
inc ebx
inc ebx //counter ++
dec ecx
jnz firstl //pos < dest_length
secondl:
jnc final //borrow_flag == 1?
mov eax, [esi + ebx] //load dest data
sbb [edi+ebx], eax //sub with carry flag
inc ebx
inc ebx
inc ebx
inc ebx //counter ++
jmp secondl
final:
// POPAD //recover current register
}
#endif
pos = src.m_acutual_len-1;
while (src.m_p_data_arr[pos]==0 && pos) pos--;
src.m_acutual_len = pos + 1;
src.m_dw_isOverflow = 0; //never overflows
}
inline void Integer::add_sub_director(Integer &src, Integer &dest, unsigned int intend_op)
{
/*
[0] [1] [intend_op]
-----------------------------------
+ + + sig = [0]
- - +
+ - -
- + - (old_sign_src ^ intend_op) ^ old_sign_dest = 0
-----------------------------------
+ + - sig = [0] * compare
+ - +
- - -
- + + (old_sign_src ^ intend_op) ^ old_sign_dest = 1
-----------------------------------
*/
unsigned int old_sign_src,old_sign_dest;
old_sign_src = src.m_dw_sign;
old_sign_dest = dest.m_dw_sign;
src.m_dw_sign = dest.m_dw_sign = 0; //get abs value
unsigned int selector = (old_sign_src ^ intend_op) ^ old_sign_dest;
if (selector)
{
int compare_val = src.compare(dest);
if (compare_val ==0) //must be zero
{
src.zero();
dest.m_dw_sign = old_sign_dest;
return;
}
if (compare_val == 1) //abs(src) > abs(dest)
{
raw_sub(src,dest);
src.m_dw_sign = old_sign_src;
}else
{
//tricks here, actually very bad coding style, but runs faster
Integer tmp(dest);
raw_sub(tmp,src);
release_data_buf(src);
src.m_acutual_len = tmp.m_acutual_len;
src.m_p_data_arr = tmp.m_p_data_arr;
tmp.m_p_data_arr = NULL;
src.m_dw_sign = 1- old_sign_src;
}
}
else
{
raw_add(src,dest);
src.m_dw_sign =old_sign_src;
}
dest.m_dw_sign = old_sign_dest;
}
void Integer::raw_mul(const Integer &left, const Integer &right, Integer &dest)
{
if (left.isZero() || right.isZero()) {
dest.zero();
return;
}
unsigned int dest_sign = left.m_dw_sign ^ right.m_dw_sign;
unsigned int ans_len = left.m_acutual_len + right.m_acutual_len;
unsigned int buffer_length = MAX(ans_len,ms_u_data_arr_num<<1);
static Integer tmpInt;
static bool fisrtcall = true;
//tricks
if (fisrtcall){
release_data_buf(tmpInt);
tmpInt.m_p_data_arr = new unsigned int [buffer_length];
fisrtcall = false;
}
unsigned int *ans_data = tmpInt.m_p_data_arr;
//
memset(ans_data,0,sizeof(unsigned int) * (buffer_length));
unsigned int *left_buffer = const_cast(left.m_p_data_arr);
unsigned int *right_buffer = const_cast(right.m_p_data_arr);
#ifdef _NOTUSEASM
__int64 tmp_ans;
unsigned int *dw_ans = (unsigned int *)&tmp_ans;
unsigned int i = 0 , j;
unsigned int carry_val;
for (;i edi
mov ebx,ans_data //ans_data -> edi
add ebx,esi //ans_data+=i
mov esi,right_buffer //right_buffer -> esi
sub ebx,esi
sub ebx,4 //right_buffer[]
push ebp
xor ebp,ebp
loop1:
mov eax,[esi] //right_buffer[j] -> eax
add esi,4 //j++
mul edi // right_buffer[j] * left_buffer[i] -> edx:eax
add eax,ebp // right_buffer[j] * left_buffer[i] mod base + carry -> cf
mov ebp,[esi+ebx] // ans_data[j+i] -> ebp
adc edx,0 // right_buffer[j] * left_buffer[i].high + cf
add ebp,eax // right_buffer[j] * left_buffer[i] mod base + ans_data[j+i] -> cf
adc edx,0 // right_buffer[j] * left_buffer[i].high + cf
mov [esi+ebx],ebp // (a.b + c) mod base -> ans_data[j+i]
dec ecx // src_len_right--
mov ebp,edx // carry = (a.b + c) / base
jnz loop1
mov [esi+ebx+4],ebp // ans_data[right.m_acutual_len+i]=carry_val;
pop ebp
}
}
#endif
//save ans to dest
memcpy(dest.m_p_data_arr,ans_data,sizeof(unsigned int) *ms_u_data_arr_num);
dest.m_dw_sign = dest_sign;
while(ans_data[ans_len-1] ==0 && ans_len>1) ans_len--;
//overflow checking and calc actual len
if (dest.m_dw_isOverflow = (ans_len>ms_u_data_arr_num)){
dest.m_acutual_len = ms_u_data_arr_num;
}
else
{
dest.m_acutual_len = ans_len;
}
///////////
}
//assume &left != &right
int Integer::raw_div(Integer &left, Integer &right, Integer &dest)
{
if (right.isZero()) return 1; //divided by zero
static Integer tmpAns;
unsigned int d_factor = 0;
unsigned int dw_reminder;
unsigned int *left_buf = left.m_p_data_arr;
unsigned int *right_buf = right.m_p_data_arr;
unsigned int *dest_buf = dest.m_p_data_arr;
unsigned int *tmp_buf = tmpAns.m_p_data_arr;
unsigned int right_buff_len = right.m_acutual_len;
unsigned int borrow_flag;
unsigned int old_sig_left,old_sig_right;
unsigned int attemp;
old_sig_left = left.m_dw_sign;
old_sig_right = right.m_dw_sign;
unsigned int dest_sign = old_sig_left ^ old_sig_right;
//calc with positive
left.m_dw_sign = right.m_dw_sign = 0;
tmpAns = left; //copy left to tmpAns
//some special conditions:
if (left.m_acutual_len == right.m_acutual_len)
{
if (left.m_acutual_len == 1) //A and B have only one "digit"
{
d_factor = tmp_buf[0] / right_buf[0];
tmp_buf[0] %= right_buf[0];
}
else if ((tmp_buf[tmpAns.m_acutual_len-1]/4)= right )
{
raw_sub(tmpAns,right);
d_factor ++;
}
}
}
if (tmpAns < right) //since tmpAns=right.m_acutual_len-1;k--)
{ /* long division */
#ifdef _NOTUSEASM
unsigned int carry_flg=0;
unsigned int tst,ra;
if (tmp_buf[k+1]==ldy) // guess next quotient 'digit'
{
attemp=DWORD_BITMASK;
ra=ldy+tmp_buf[k];
if (ra0)
{ /* do partial subtraction */
borrow_flag=0;
#ifdef _NOTUSEASM
unsigned int dig=0;
for (unsigned int i=0;iright_buf[i]) carry_flg=0;
if (psum1)dest.m_acutual_len--;
memset(dest_buf+dest.m_acutual_len,0,sizeof(unsigned int)*(ms_u_data_arr_num-dest.m_acutual_len));
if (left_buf!=dest_buf)
{
while(tmp_buf[tmpAns.m_acutual_len-1]==0 && tmpAns.m_acutual_len>1) tmpAns.m_acutual_len--;
if (d_factor!=1) raw_div_int( tmpAns,d_factor,left);
else left = tmpAns;
if (!left.isZero()) left.m_dw_sign = old_sig_left;
}
if (d_factor!=1) raw_div_int(right,d_factor,right);
right.m_dw_sign = old_sig_right;
return 0;
}
void Integer::raw_mul_int(Integer &left, unsigned int n, Integer &dest)
{
unsigned int carry_flg,pos;
unsigned int src_buf_len,dest_buf_len;
unsigned int * dest_buff = dest.m_p_data_arr;
unsigned int * src_buff = left.m_p_data_arr;
src_buf_len = left.m_acutual_len;
dest_buf_len= dest.m_acutual_len;
if (dest_buff != src_buff)
{
dest.zero();
}
if (n ==0 || left.isZero() )
{
dest.zero();
return;
}
carry_flg=0;
#ifndef _NOTUSEASM
__asm{
mov ecx,src_buf_len
or ecx,ecx
je finish //ecx > 0?
mov ebx,n
mov edi,dest_buff
mov esi,src_buff
push ebp
xor ebp,ebp
loop1:
mov eax,[esi]
add esi,4
mul ebx
add eax,ebp
adc edx,0
mov [edi],eax
add edi,4
mov ebp,edx
dec ecx
jnz loop1
mov eax,ebp
pop ebp
mov carry_flg,eax
finish:
}
#else
pos=0;
__int64 ans;
unsigned int *dw_ans = (unsigned int *)&ans;
for (;pos0)
{
pos=src_buf_len;
if (pos > ms_u_data_arr_num)
{
dest.m_dw_isOverflow = true;
return;
}
dest_buff[pos]=carry_flg;
dest.m_acutual_len = pos+1;
}
else dest.m_acutual_len =src_buf_len;
dest.m_dw_sign = left.m_dw_sign;
}
unsigned int Integer::raw_div_int(Integer &left, unsigned int n, Integer &dest)
{
unsigned int src_length;
unsigned int * src_buff = left.m_p_data_arr;
unsigned int * dest_buff = dest.m_p_data_arr;
unsigned int src_reminder = 0;
src_length = left.m_acutual_len;
if (src_buff!=dest_buff) dest.zero();
#ifndef _NOTUSEASM
__asm{
mov ecx,src_length
or ecx,ecx
je final
mov ebx,ecx
shl ebx,2
mov esi, src_buff
add esi,ebx
mov edi, dest_buff
add edi,ebx
mov ebx,n
push ebp
xor ebp,ebp
loop1:
sub esi,4
mov edx,ebp
mov eax,[esi]
div ebx
sub edi,4
mov ebp,edx
mov [edi],eax
dec ecx
jnz loop1
mov eax,ebp
pop ebp
mov src_reminder,eax
final:
}
#else
int pos;
__int64 tmp_ans;
unsigned int * dw_ans = (unsigned int *)&tmp_ans;
for (pos =(int)src_length-1;pos>=0;pos--)
{
dw_ans[0]=src_buff[pos];
dw_ans[1]=src_reminder;
dest_buff[pos]=(unsigned int)(tmp_ans/n);
src_reminder=(unsigned int)(tmp_ans-(__int64)dest_buff*n);
}
#endif
dest.m_acutual_len = src_length;
while(dest_buff[dest.m_acutual_len - 1] == 0 && dest.m_acutual_len>1) dest.m_acutual_len--;
return src_reminder;
}
int Integer::norm_divisor(Integer &left, Integer &right)
{
unsigned int norm,remainder;
int len;
if (left.m_p_data_arr!=right.m_p_data_arr) right = left;
len=right.m_acutual_len;
if ((remainder=right.m_p_data_arr[len-1]+1)==0) norm=1;
#ifdef _NOTUSEASM
else norm=(unsigned int)(((__int64)1 << 32)/remainder);
#else
else norm=muldvm((unsigned int)1,(unsigned int)0,remainder,( int *)&remainder);
#endif
if (norm!=1) raw_mul_int(right,norm,right);
return norm;
}
Integer& Integer::plus(Integer &dest)
{
add_sub_director(*this,dest,0);
return *this;
}
Integer& Integer::minus(Integer &dest)
{
add_sub_director(*this,dest,1);
return *this;
}
Integer& Integer::mul(const Integer &right,Integer &dest)
{
raw_mul(*this,right,dest);
return dest;
}
Integer& Integer::div(const Integer &right)
{
raw_div(*this,const_cast(right),*this);
return *this;
}
Integer& Integer::mod(const Integer &right)
{
raw_div(*this,const_cast(right),const_cast(right));
return *this;
}
Integer& Integer::shift(int n)
{
if (this->isZero() || n==0) return *this;
int dest_len = this->m_acutual_len + n;
int i;
if (dest_len<=0)
{
this->zero();
return *this;
}
if ((unsigned int)dest_len >ms_u_data_arr_num)
{
this->m_dw_isOverflow = true;
dest_len = ms_u_data_arr_num;
}
if (n>0)
{
for (i=dest_len-1;i>=n;i--)
this->m_p_data_arr[i]=this->m_p_data_arr[i-n];
for (i=0;im_p_data_arr[i]=0;
}
else
{
n=(-n);
for (i=0;im_p_data_arr[i]=this->m_p_data_arr[i+n];
for (i=0;im_p_data_arr[dest_len+i]=0;
}
this->m_acutual_len = dest_len;
return *this;
}