www.pudn.com > CiperLib_release_by_csk.rar > CiperLib.h
/*
Big Integer Operation
HEADER FILE
BY CSK(³ÂÊ¿¿)
CSK@live.com
www.csksoft.net
*/
#pragma once
#ifndef CIPER_LIB_H
#define CIPER_LIB_H
class ZModn;
class IntHelper;
class Integer
{
/*
STATIC AREA
*/
friend class ZModn;
friend class IntHelper;
public:
//Please call this function before any operation first!
//otherwise this function will be automatically called with u_data_arr_num = 1024
//This func can called by ONLY ONCE!
static bool Init(unsigned int u_data_arr_num = 1024);
//intend_op = 0 : add , 1: sub
//this func judge whether to do adding or subing operation
static void add_sub_director(Integer &src, Integer &dest, unsigned int intend_op);
protected:
static unsigned int ms_u_ref_cnt;//the number of instances
static bool ms_b_inited; //indicate whether the func Init was called
static unsigned int ms_u_data_arr_num; //indicate the bits length of Integer, this value is set by Init
//create memory for holding num data, the length of the buffer is ms_u_data_arr_num/32
static void create_data_buf(Integer & i);
//release the memory allocated by create_data_buf
static void release_data_buf(Integer & i);
//src += dest, assume src.sign = dest.sign
static void raw_add(Integer &src, const Integer &dest);
//src -= dest, assume src.sign = dest.sign
static void raw_sub(Integer &src, const Integer &dest);
//dest = left * right + dest
static void raw_mul(const Integer &left, const Integer &right, Integer &dest);
//dest = left / right
//left = left mod right
//if &dest = &left, only quotient returns
//if &dest = &right, only reminder returns
//return 0 if success
//1: div by zero
static int raw_div(Integer &left, Integer &right, Integer &dest);
static void raw_mul_int(Integer &left, unsigned int n, Integer &dest);
static unsigned int raw_div_int(Integer &left, unsigned int n, Integer &dest);
static int norm_divisor(Integer &left, Integer &right);
/*
END OF STATIC AREA
*/
//pointer to the buffer created by create_data_buf
unsigned int *m_p_data_arr;
//indicate the sign of current integer, 0 for positive, 1 for negative
unsigned int m_dw_sign;
//current length of the integer, range for 1 to ms_u_data_arr_num
unsigned int m_acutual_len;
//indicate whether this number is overflowed
unsigned int m_dw_isOverflow;
//common init func
void inner_init();
public:
//------Init func
Integer();
Integer(const Integer &); //create a new copy of Integer
Integer(__int64); //create from a 64-bit integer
Integer(int); //create from a 32-bit integer
Integer(char *, unsigned int = 10); //create from string, the second argument indicate the base number
//release func
~Integer();
//------convert
//convert current integer value to string,
//max_buffer_size indicates the max buffer size of strNum,
//base indicate the base number, only 10 and 16 is valid
bool toString(char *strNum, unsigned int max_buffer_size, unsigned int base = 10) const;
//parse integer value from string, base indicate the base number, only 10 and 16 is valid
bool fromString(char *strNum, unsigned int base = 10);
//parse integer from 64-bit buildin type
void fromInt64(__int64);
//parse integer from 32-bit buildin type
void fromInt(int);
//------copy
//make a new copy without affect the previous one
Integer & copyFrom(const Integer &);
//------operation
//compare this and the argument
// if this > argument , return 1
// if this < argument , return -1
// if this == argument , return 0
int compare(const Integer &) const;
bool isZero() const;
// make this = 0
Integer& zero();
//this += argu
Integer& plus( Integer &);
//this -= argu
Integer& minus( Integer &);
//dest = this * right
Integer& mul(const Integer &right,Integer &dest);
// Integer& full_div(const Integer &right,Integer &dest);
//dest = this / right
Integer& div(const Integer &right);
//dest = this mod right
Integer& mod(const Integer &right);
//set x=x.(base^n)
Integer& shift(int n);
//------operator
Integer & operator= (const Integer &);
int operator>(const Integer &) const;
int operator<(const Integer &) const;
int operator==(const Integer &) const;
int operator!=(const Integer &) const;
int operator>=(const Integer &) const;
int operator<=(const Integer &) const;
Integer & operator+=(const Integer &);
Integer & operator+=(int);
Integer & operator-=(const Integer &);
Integer & operator-=(int);
Integer & operator*=(const Integer &);
Integer & operator*=(int);
Integer & operator/=(const Integer &);
Integer & operator/=(int);
Integer & operator%=(const Integer &);
Integer & operator%=(int);
Integer operator+(const Integer &);
Integer operator+(int);
Integer operator-(const Integer &);
Integer operator-(int);
Integer operator*(const Integer &);
Integer operator*(int);
Integer operator/(const Integer &);
Integer operator/(int);
Integer operator%(const Integer &);
Integer operator%(int);
};
class ZModn
{
protected:
Integer m_mod_value;
static unsigned int prime_array[];
static bool is_prime_arr_inited;
static void genPrimeArr();
public:
//set the mod value of Zm
//Call this func First!!!
bool setMod( Integer&);
//judge a prime using Rabin-Miller method
static bool isPrime( Integer&);
//generate a prime >= start_val
static bool genPrime(Integer & start_val,Integer & dest);
//quick judge a Integer whether it is a prime
//returns 0 means it is not a prime
// 1 means it must be a prime
// 2 means it may be a prime
static int quickPrimeDec( Integer&);
//A = A mod m_mod_value
Integer & toMod(Integer& A);
//B = A + B (mod m_mod_value)
Integer & mod_add(Integer& A, Integer& B);
//B = A * B (mod m_mod_value)
Integer & mod_mul(Integer&, Integer& );
//A = A^N (mod m_mod_value)
Integer & mod_pow(Integer& A, Integer& N);
Integer & Euc(Integer&, Integer&);
};
class IntHelper
{
private:
//used for Marsaglia & Zaman's algorithm
static unsigned int rnd_seeds[];
static unsigned int rnd_carry_flag;
static int rnd_pos;
public:
//returns number of bits
static int logb2(const Integer&);
//returns the sliding windows's value
static int sliding_window(const Integer& ,int ,int *,int * ,int );
//get the n-bits' value
static int testbit(const Integer& x,unsigned int n);
//using Marsaglia & Zaman's method to generation long period random number
static void MZ_seed(unsigned int seed);
static unsigned int MZ_rand();
};
#endif