inthelper.cpp

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

/*
    Helper func for Integer Class
    BY CSK(陈士凯)
    [e-mail]
    www.csksoft.net
*/

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



//random seeds number
#define R_M_RND_SEEDS_NUM 37
#define R_M_RND_SEEDS_F 14

unsigned int IntHelper::rnd_seeds[R_M_RND_SEEDS_NUM];
unsigned int IntHelper::rnd_carry_flag = 0;
int IntHelper::rnd_pos = 0;

int IntHelper::logb2(const Integer& src)
{
    int ans;
    unsigned int top;
    
    if (src.isZero()) return 0;
    
    ans=32*(src.m_acutual_len-1);
    top=src.m_p_data_arr[src.m_acutual_len-1];
    while (top>=1)
    {
        ans++;
        top = top >> 1;
    }
    return ans;
}


int IntHelper::testbit(const Integer& x,unsigned int n)
{

    if ((x.m_p_data_arr[n>>5] & ((unsigned int)1<<(n%32)))) return 1;

    return 0;
}

int IntHelper::sliding_window(const Integer& x,int i,int *nbs,int * nzs,int window_size )
{
    int j,r,w;
    w=window_size;
/* check for leading 0 bit */

    *nbs=1;
    *nzs=0;
    if (!testbit(x,(unsigned int)i)) return 0;

/* adjust window size if not enough bits left */
   
    if (i-w+1<0) w=i+1;

    r=1;
    for (j=i-1;j>i-w;j--)
    { /* accumulate bits. Abort if two 0's in a row */
        (*nbs)++;
        r*=2;
        if (testbit( x,(unsigned int)j)) r+=1;
        if (r%4==0)
        { /* oops - too many zeros - shorten window */
            r/=4;
            *nbs-=2;
            *nzs=2;
            break;
        }
    }
    if (r%2==0)
    { /* remove trailing 0 */
        r/=2;
        *nzs=1;
        (*nbs)--;
    }
    return r;

}
void IntHelper::MZ_seed(unsigned int seed)
{
    int i,in;
    unsigned int t,m=1L;
    rnd_carry_flag=0;
    rnd_pos=0;
    rnd_seeds[0]^=seed;

    for (i=1;i<R_M_RND_SEEDS_NUM;i++)
    { 
        in=(R_M_RND_SEEDS_F*i)%R_M_RND_SEEDS_NUM;
        rnd_seeds[in]=m; 
        t=m;
        m=seed-m;
        seed=t;
    }
    for (i=0;i<1000;i++) MZ_rand(); //init
}

unsigned int IntHelper::MZ_rand()
{
    int i,k;
    unsigned int pdiff,t;
   

    
    rnd_pos++;
    if (rnd_pos<R_M_RND_SEEDS_NUM) return rnd_seeds[rnd_pos];
    
    rnd_pos=0;

    for (i=0,k=R_M_RND_SEEDS_NUM-R_M_RND_SEEDS_F;i<R_M_RND_SEEDS_NUM;i++,k++)
    { /* calculate next NK values */
        if (k==R_M_RND_SEEDS_NUM) k=0;
        t=rnd_seeds[k];
        pdiff=t - rnd_seeds[i] - rnd_carry_flag;
        if (pdiff<t) rnd_carry_flag=0;
        if (pdiff>t) rnd_carry_flag=1;
        rnd_seeds[i]=pdiff; 
    }
    return rnd_seeds[0];


}