/*--- ZBIGINT.H: Header file for basic bignum operations */
/* Most of these symbols were invented by Arjen Lenstra.
* I have attempted to elucidate them here. /mrr
*
* MYINT is a symbol which should be "long int" or "int",
* depending on what's more efficient on your machine.
* When in doubt, stick to "long int".
*
* Many of the other symbols depend upon how big MYINTs are
* your machine. Just define the symbol MYINT_BITS as 16, 32, or 64.
*
* Note: The first three are the most likely to have to be
* changed to meet your needs. They affect the magnitude of
* the largest BIGINT.
*
* ZMAX_BITS The maximum number of bits that will ever need to
* fit in a BIGINT. Make sure it's big enough to
* handle intermediate results. (Make it twice as big
* as your biggest modulus.)
* ZSIZEP The number of long ints taken up by a BIGINT.
* Note: The largest BIGINT is 2^((ZSIZEP-1)*NBITS)-1.
* A ZSIZEP of 15 means that you can represent
* up to 2^(14*30)-1 = 2^520 - 1. But note that you
* will probably want ZSIZEP to be big enough to
* accomodate numbers larger than you are using as
* input, to allow for intermediate results.
* ZZSIZEP The number of long ints required to represent the biggest
* BIGINT if you use only NBITSH bits of each BIGINT.
* ZZSIZEP = ZSIZEP*2 - 1 (the one for the first long int
* used to hold the length).
* ZDECSIZE Number of characters needed to represent the largest
* BIGINT in decimal ASCII form.
* NBITS Number of bits used in a long int. Must be even and must
* be less than the size of a long int to avoid overflow
* to sign bit.
* NBITSH Half of NBITS (used in division, amoung others)
* RADIX 2^NBITS
* RADIXM RADIX-1; in other words, a bit mask that covers all
* the bits of a long int that we use.
* RADIXROOT sqrt(RADIX)
* RADIXROOTM RADIXROOT-1; in other words, a bit mask that covers
* the bottom half of the bits used in a long int.
* ZSINT I can't tell the difference in meaning between this
* and RADIXROOT. Used to avoid overflow in divisions (?).
* PRIMBND Used in prime number generation.
* INDBND Used in prime number generation.
* MRANDBITS The number of bits returned by zrandombits. Should
* always be = NBITS with current implementation.
* TWO_TO_THE_MRANDBITS 2^MRANDBITS, which should be a long int.
* BITS_PER_BYTE You can guess this one.
*/
/* 32 bits seems to be fastest even for PCs, although they are
* emulating 32-bit arithmetic with 16-bit instructions.
*/
#define MYINT long int
#define MYINT_BITS 32
/* Very important: Make sure that ZMAX_BITS is set big enough. */
#define ZMAX_BITS 2000
#if MYINT_BITS == 32
#define NBITS 30
#define NBITSH 15
#define RADIX 1073741824
#define RADIXM 1073741823
#define RADIXROOT 32768
#define RADIXROOTM 32767
#define ZSINT 32768
#define MRANDBITS 30
#define TWO_TO_THE_MRANDBITS 1073741824
#endif
/* Some lousy C compilers don't recognize #elif. */
#if MYINT_BITS == 16
#define NBITS 14
#define NBITSH 7
#define RADIX 16384
#define RADIXM 16383
#define RADIXROOT 128
#define RADIXROOTM 127
#define ZSINT 128
#define MRANDBITS 14
#define TWO_TO_THE_MRANDBITS 16384
#endif
#if MYINT_BITS == 64
#define NBITS 62
#define NBITSH 31
#define RADIX 0x4000000000000000
#define RADIXM 0x3fffffffffffffff
#define RADIXROOT 0x80000000
#define RADIXROOTM 0x7fffffff
#define ZSINT 0x80000000
#define MRANDBITS 62
#define TWO_TO_THE_MRANDBITS 0x400000000000000
#endif
#define ZSIZEP ((ZMAX_BITS/NBITS)+1)
#define ZZSIZEP (2*ZSIZEP-1)
#define ZDECSIZE ((ZMAX_BITS)/3)
#define PRIMBND 5000
#define INDBND 48
#define BITS_PER_BYTE 8
typedef struct { MYINT len; MYINT val[ZSIZEP-1]; } BIGINT;
#ifdef Z_DEFINE
#define DEF
#else
#define DEF extern
#endif
DEF BIGINT z_one;
/* The macros below mimic another multiple-precision package.
* They are included here to ease porting of code and to allow
* the programmer to maintain the coding discipline needed
* in an environment in which the BIGINTs are dynamically allocated,
* in case a dynamic version of this package is released.
*/
#define MINIT(x) zset((MYINT)0,x)
#define MSET(c,x) zset((MYINT)c,x)
#define MCOPY(x,y) zcopy(x,y)
#define MMOVE(x,y) MCOPY(x,y)
#define MFREE(x)
#define MMOVEFREE(x,y) MCOPY(x,y)
/*--- End of ZBIGINT.H ---------------------------------------- */