zmath.h

Calc Software Package for Number Calc

/*
 * zmath - declarations for extended precision integer arithmetic
 *
 * Copyright (C) 1999-2006  David I. Bell
 *
 * Calc is open software; you can redistribute it and/or modify it under
 * the terms of the version 2.1 of the GNU Lesser General Public License
 * as published by the Free Software Foundation.
 *
 * Calc is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE.	 See the GNU Lesser General
 * Public License for more details.
 *
 * A copy of version 2.1 of the GNU Lesser General Public License is
 * distributed with calc under the filename COPYING-LGPL.  You should have
 * received a copy with calc; if not, write to Free Software Foundation, Inc.
 * 59 Temple Place, Suite 330, Boston, MA  02111-1307, USA.
 *
 * @(#) $Revision: 29.18 $
 * @(#) $Id: zmath.h,v 29.18 2006/12/15 16:20:04 chongo Exp $
 * @(#) $Source: /usr/local/src/cmd/calc/RCS/zmath.h,v $
 *
 * Under source code control:	1993/07/30 19:42:48
 * File existed as early as:	1993
 *
 * Share and enjoy!  :-)	http://www.isthe.com/chongo/tech/comp/calc/
 */

/*
 * Data structure declarations for extended precision integer arithmetic.
 * The assumption made is that a long is 32 bits and shorts are 16 bits,
 * and longs must be addressible on word boundaries.
 */


#if !defined(__ZMATH_H__)
#define __ZMATH_H__


#if defined(CALC_SRC)	/* if we are building from the calc source tree */
# include "win32dll.h"
# include "alloc.h"
# include "endian_calc.h"
# include "longbits.h"
# include "byteswap.h"
# include "have_stdlib.h"
#else
# include <calc/win32dll.h>
# include <calc/alloc.h>
# include <calc/endian_calc.h>
# include <calc/longbits.h>
# include <calc/byteswap.h>
# include <calc/have_stdlib.h>
#endif
#ifdef HAVE_STDLIB_H
# include <stdlib.h>
#endif


#ifndef ALLOCTEST
# define freeh(p) { if (((void *)p != (void *)_zeroval_) &&		\
			 ((void *)p != (void *)_oneval_)) free((void *)p); }
#endif


#if !defined(TRUE)
#define TRUE	((BOOL) 1)			/* booleans */
#endif
#if !defined(FALSE)
#define FALSE	((BOOL) 0)
#endif


/*
 * NOTE: FULL must be twice the storage size of a HALF
 *	 HALF must be BASEB bits long
 */

#if defined(HAVE_B64)

#define BASEB	32			/* use base 2^32 */
typedef USB32 HALF;			/* unit of number storage */
typedef SB32 SHALF;			/* signed HALF */
typedef USB64 FULL;			/* double unit of number storage */
typedef SB64 SFULL;			/* signed FULL */

#define SWAP_HALF_IN_B64(dest, src)	SWAP_B32_IN_B64(dest, src)
#define SWAP_HALF_IN_B32(dest, src)	(*(dest) = *(src))
#define SWAP_HALF_IN_FULL(dest, src)	SWAP_B32_IN_B64(dest, src)
#define SWAP_HALF_IN_HASH(dest, src)	SWAP_B16_IN_HASH(dest, src)
#define SWAP_HALF_IN_FLAG(dest, src)	SWAP_B16_IN_FLAG(dest, src)
#define SWAP_HALF_IN_BOOL(dest, src)	SWAP_B16_IN_BOOL(dest, src)
#define SWAP_HALF_IN_LEN(dest, src)	SWAP_B16_IN_LEN(dest, src)
#define SWAP_B32_IN_FULL(dest, src)	SWAP_B32_IN_B64(dest, src)
#define SWAP_B16_IN_FULL(dest, src)	SWAP_B16_IN_B64(dest, src)
#define SWAP_B16_IN_HALF(dest, src)	SWAP_B16_IN_B32(dest, src)
#define SWAP_B8_IN_FULL(dest, src)	SWAP_B8_IN_B64(dest, src)
#define SWAP_B8_IN_HALF(dest, src)	SWAP_B8_IN_B32(dest, src)

#else

#define BASEB	16			/* use base 2^16 */
typedef USB16 HALF;			/* unit of number storage */
typedef SB16 SHALF;			/* signed HALF */
typedef USB32 FULL;			/* double unit of number storage */
typedef SB32 SFULL;			/* signed FULL */

#define SWAP_HALF_IN_B64(dest, src)	SWAP_B16_IN_B64(dest, src)
#define SWAP_HALF_IN_B32(dest, src)	SWAP_B16_IN_B32(dest, src)
#define SWAP_HALF_IN_FULL(dest, src)	SWAP_B16_IN_B32(dest, src)
#define SWAP_HALF_IN_HASH(dest, src)	SWAP_B16_IN_HASH(dest, src)
#define SWAP_HALF_IN_FLAG(dest, src)	SWAP_B16_IN_FLAG(dest, src)
#define SWAP_HALF_IN_BOOL(dest, src)	SWAP_B16_IN_BOOL(dest, src)
#define SWAP_HALF_IN_LEN(dest, src)	SWAP_B16_IN_LEN(dest, src)
#define SWAP_B32_IN_FULL(dest, src)	(*(dest) = *(src))
#define SWAP_B16_IN_FULL(dest, src)	SWAP_B16_IN_B32(dest, src)
#define SWAP_B16_IN_HALF(dest, src)	(*(dest) = *(src))
#define SWAP_B8_IN_FULL(dest, src)	SWAP_B8_IN_B32(dest, src)
#define SWAP_B8_IN_HALF(dest, src)	SWAP_B8_IN_B16(dest, src)

#endif

#define BASE	((FULL)1<<BASEB)		/* base for calculations */
#define BASE1	(BASE - (FULL)1)		/* one less than base */
#define BASEDIG ((BASEB/16)*5)			/* number of digits in base */
#define FULL_BITS (2*BASEB)			/* bits in a FULL */

#define TOPHALF ((FULL)1 << (BASEB-1))		/* highest bit in a HALF */
#define MAXHALF (TOPHALF - (FULL)1)		/* largest SHALF value */

#define TOPFULL ((FULL)1 << (FULL_BITS-1))	/* highest bit in FULL */
#define MAXFULL (TOPFULL - (FULL)1)		/* largest SFULL value */
#define MINSFULL ((SFULL)(TOPFULL))		/* most negative SFULL value */
#define MAXUFULL (MAXFULL | TOPFULL)		/* largest FULL value */

#define TOPLONG ((unsigned long)1 << (LONG_BITS-1))	/* top long bit */
#define MAXLONG ((long) (TOPLONG - (unsigned long)1))	/* largest long val */
#define MAXULONG (MAXLONG | TOPLONG)		/* largest unsigned long val */


/*
 * other misc typedefs
 */
typedef USB32 QCKHASH;			/* 32 bit hash value */
#if defined(HAVE_B64) && LONG_BITS == 32
typedef HALF PRINT;			/* cast for zio printing fucctions */
#define SWAP_B16_IN_PRINT(dest, src)	SWAP_B16_IN_HALF(dest, src)
#define SWAP_B8_IN_PRINT(dest, src)	SWAP_B8_IN_HALF(dest, src)
#else
typedef FULL PRINT;			/* cast for zio printing fucctions */
#define SWAP_B16_IN_PRINT(dest, src)	SWAP_B16_IN_FULL(dest, src)
#define SWAP_B8_IN_PRINT(dest, src)	SWAP_B8_IN_FULL(dest, src)
#endif
typedef SB32 FLAG;			/* small value (e.g. comparison) */
typedef SB32 BOOL;			/* TRUE or FALSE value */
typedef SB32 LEN;			/* unit of length storage */

#define SWAP_B32_IN_HASH(dest, src)	(*(dest) = *(src))
#define SWAP_B16_IN_HASH(dest, src)	SWAP_B16_IN_B32(dest, src)
#define SWAP_B8_IN_HASH(dest, src)	SWAP_B8_IN_B32(dest, src)

#define SWAP_B32_IN_FLAG(dest, src)	(*(dest) = *(src))
#define SWAP_B16_IN_FLAG(dest, src)	SWAP_B16_IN_B32(dest, src)
#define SWAP_B8_IN_FLAG(dest, src)	SWAP_B8_IN_B32(dest, src)

#define SWAP_B32_IN_BOOL(dest, src)	(*(dest) = *(src))
#define SWAP_B16_IN_BOOL(dest, src)	SWAP_B16_IN_B32(dest, src)
#define SWAP_B8_IN_BOOL(dest, src)	SWAP_B8_IN_B32(dest, src)

#define SWAP_B32_IN_LEN(dest, src)	(*(dest) = *(src))
#define SWAP_B16_IN_LEN(dest, src)	SWAP_B16_IN_B32(dest, src)
#define SWAP_B8_IN_LEN(dest, src)	SWAP_B8_IN_B32(dest, src)

#if LONG_BITS == 64
#define SWAP_HALF_IN_LONG(dest, src)	SWAP_HALF_IN_B64(dest, src)
#else /* LONG_BITS == 64 */
#define SWAP_HALF_IN_LONG(dest, src)	SWAP_HALF_IN_B32(dest, src)
#endif /* LONG_BITS == 64 */


/*
 * FNV-1 basis
 *
 * We start the hash at a non-zero value at the beginning so that
 * hashing blocks of data with all 0 bits do not map onto the same
 * 0 hash value.  The virgin value that we use below is the hash value
 * that we would get from following 32 ASCII characters:
 *
 *		chongo <Landon Curt Noll> /\../\
 *
 * Note that the \'s above are not back-slashing escape characters.
 * They are literal ASCII  backslash 0x5c characters.
 *
 * The effect of this virgin initial value is the same as starting
 * with 0 and pre-pending those 32 characters onto the data being
 * hashed.
 *
 * Yes, even with this non-zero virgin value there is a set of data
 * that will result in a zero hash value.  Worse, appending any
 * about of zero bytes will continue to produce a zero hash value.
 * But that would happen with any initial value so long as the
 * hash of the initial was the `inverse' of the virgin prefix string.
 *
 * But then again for any hash function, there exists sets of data
 * which that the hash of every member is the same value.  That is
 * life with many to few mapping functions.  All we do here is to
 * prevent sets whose members consist of 0 or more bytes of 0's from
 * being such an awkward set.
 *
 * And yes, someone can figure out what the magic 'inverse' of the
 * 32 ASCII character are ... but this hash function is NOT intended
 * to be a cryptographic hash function, just a fast and reasonably
 * good hash function.
 */
#define FNV1_32_BASIS ((QCKHASH)(0x811c9dc5))


/*
 * The largest power of 10 we will compute for our decimal conversion
 * internal constants is: 10^(2^TEN_MAX).
 */
#define TEN_MAX 31	/* 10^2^31 requires about 1.66 * 2^29 bytes */


/*
 * LEN storage size must be <= FULL storage size
 */
#define MAXLEN	((LEN) 0x7fffffff >> 3) /* longest value allowed */


#define MAXREDC 64			/* number of entries in REDC cache */
#define SQ_ALG2 3388			/* size for alternative squaring */
#define MUL_ALG2 1780			/* size for alternative multiply */
#define POW_ALG2 176			/* size for using REDC for powers */
/* old REDC_ALG2 was 5/4 of POW_ALG2, so we will keep the same ratio */
#define REDC_ALG2 220			/* size for using alternative REDC */


typedef union {
	FULL	ivalue;
	struct {
		HALF Svalue1;
		HALF Svalue2;
	} sis;
} SIUNION;


#if !defined(LITTLE_ENDIAN)
#define LITTLE_ENDIAN	1234	/* Least Significant Byte first */
#endif
#if !defined(BIG_ENDIAN)
#define BIG_ENDIAN	4321	/* Most Significant Byte first */
#endif
/* PDP_ENDIAN - LSB in word, MSW in long is not supported */

#if CALC_BYTE_ORDER == LITTLE_ENDIAN
# define silow	sis.Svalue1	/* low order half of full value */
# define sihigh sis.Svalue2	/* high order half of full value */
#else
# if CALC_BYTE_ORDER == BIG_ENDIAN
#  define silow sis.Svalue2	/* low order half of full value */
#  define sihigh sis.Svalue1	/* high order half of full value */
# else
   /\oo/\    CALC_BYTE_ORDER must be BIG_ENDIAN or LITTLE_ENDIAN    /\oo/\  !!!
# endif
#endif


typedef struct {
	HALF	*v;		/* pointer to array of values */
	LEN	len;		/* number of values in array */
	BOOL	sign;		/* sign, nonzero is negative */
} ZVALUE;



/*
 * Function prototypes for integer math routines.
 */
extern DLL HALF * alloc(LEN len);
#ifdef	ALLOCTEST
extern DLL void freeh(HALF *);
#endif


/*
 * Input, output, and conversion routines.
 */
extern DLL void zcopy(ZVALUE z, ZVALUE *res);
extern DLL void itoz(long i, ZVALUE *res);
extern DLL void utoz(FULL i, ZVALUE *res);
extern DLL void stoz(SFULL i, ZVALUE *res);
extern DLL void str2z(char *s, ZVALUE *res);
extern DLL long ztoi(ZVALUE z);
extern DLL FULL ztou(ZVALUE z);
extern DLL SFULL ztos(ZVALUE z);
extern DLL void zprintval(ZVALUE z, long decimals, long width);
extern DLL void zprintx(ZVALUE z, long width);
extern DLL void zprintb(ZVALUE z, long width);
extern DLL void zprinto(ZVALUE z, long width);
extern DLL void fitzprint(ZVALUE, long, long);


/*
 * Basic numeric routines.
 */
extern DLL void zmuli(ZVALUE z, long n, ZVALUE *res);
extern DLL long zdivi(ZVALUE z, long n, ZVALUE *res);
extern DLL long zmodi(ZVALUE z, long n);
extern DLL void zadd(ZVALUE z1, ZVALUE z2, ZVALUE *res);
extern DLL void zsub(ZVALUE z1, ZVALUE z2, ZVALUE *res);
extern DLL void zmul(ZVALUE z1, ZVALUE z2, ZVALUE *res);
extern DLL long zdiv(ZVALUE z1, ZVALUE z2, ZVALUE *res, ZVALUE *rem, long R);
extern DLL long zquo(ZVALUE z1, ZVALUE z2, ZVALUE *res, long R);
extern DLL long zmod(ZVALUE z1, ZVALUE z2, ZVALUE *rem, long R);
extern DLL void zequo(ZVALUE z1, ZVALUE z2, ZVALUE *res);
extern DLL BOOL zdivides(ZVALUE z1, ZVALUE z2);
extern DLL void zor(ZVALUE z1, ZVALUE z2, ZVALUE *res);
extern DLL void zand(ZVALUE z1, ZVALUE z2, ZVALUE *res);
extern DLL void zxor(ZVALUE z1, ZVALUE z2, ZVALUE *res);
extern DLL void zandnot(ZVALUE z1, ZVALUE z2, ZVALUE *res);
extern DLL long zpopcnt(ZVALUE z, int bitval);
extern DLL void zshift(ZVALUE z, long n, ZVALUE *res);
extern DLL void zsquare(ZVALUE z, ZVALUE *res);
extern DLL long zlowbit(ZVALUE z);
extern DLL LEN zhighbit(ZVALUE z);
extern DLL void zbitvalue(long n, ZVALUE *res);
extern DLL BOOL zisset(ZVALUE z, long n);
extern DLL BOOL zisonebit(ZVALUE z);
extern DLL BOOL zisallbits(ZVALUE z);
extern DLL FLAG ztest(ZVALUE z);
extern DLL FLAG zrel(ZVALUE z1, ZVALUE z2);
extern DLL FLAG zabsrel(ZVALUE z1, ZVALUE z2);