c_cpp/etc/calc/zmath.h

   1 /*
   2  * zmath - declarations for extended precision integer arithmetic
   3  *
   4  * Copyright (C) 1999-2007  David I. Bell
   5  *
   6  * Calc is open software; you can redistribute it and/or modify it under
   7  * the terms of the version 2.1 of the GNU Lesser General Public License
   8  * as published by the Free Software Foundation.
   9  *
  10  * Calc is distributed in the hope that it will be useful, but WITHOUT
  11  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  12  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General
  13  * Public License for more details.
  14  *
  15  * A copy of version 2.1 of the GNU Lesser General Public License is
  16  * distributed with calc under the filename COPYING-LGPL.  You should have
  17  * received a copy with calc; if not, write to Free Software Foundation, Inc.
  18  * 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
  19  *
  20  * @(#) $Revision: 30.3 $
  21  * @(#) $Id: zmath.h,v 30.3 2013/08/11 08:41:38 chongo Exp $
  22  * @(#) $Source: /usr/local/src/bin/calc/RCS/zmath.h,v $
  23  *
  24  * Under source code control:   1993/07/30 19:42:48
  25  * File existed as early as:    1993
  26  *
  27  * Share and enjoy!  :-)        http://www.isthe.com/chongo/tech/comp/calc/
  28  */
  29
  30 /*
  31  * Data structure declarations for extended precision integer arithmetic.
  32  * The assumption made is that a long is 32 bits and shorts are 16 bits,
  33  * and longs must be addressible on word boundaries.
  34  */
  35
  36
  37 #if !defined(__ZMATH_H__)
  38 #define __ZMATH_H__
  39
  40
  41 #if defined(CALC_SRC)   /* if we are building from the calc source tree */
  42 # include "decl.h"
  43 # include "alloc.h"
  44 # include "endian_calc.h"
  45 # include "longbits.h"
  46 # include "byteswap.h"
  47 # include "have_stdlib.h"
  48 #else
  49 # include <calc/decl.h>
  50 # include <calc/alloc.h>
  51 # include <calc/endian_calc.h>
  52 # include <calc/longbits.h>
  53 # include <calc/byteswap.h>
  54 # include <calc/have_stdlib.h>
  55 #endif
  56 #ifdef HAVE_STDLIB_H
  57 # include <stdlib.h>
  58 #endif
  59
  60
  61 #ifndef ALLOCTEST
  62 # define freeh(p) { if (((void *)p != (void *)_zeroval_) &&             \
  63                          ((void *)p != (void *)_oneval_)) free((void *)p); }
  64 #endif
  65
  66
  67 #if !defined(TRUE)
  68 #define TRUE    ((BOOL) 1)                      /* booleans */
  69 #endif
  70 #if !defined(FALSE)
  71 #define FALSE   ((BOOL) 0)
  72 #endif
  73
  74
  75 /*
  76  * NOTE: FULL must be twice the storage size of a HALF
  77  *       HALF must be BASEB bits long
  78  */
  79
  80 #if defined(HAVE_B64)
  81
  82 #define BASEB   32                      /* use base 2^32 */
  83 typedef USB32 HALF;                     /* unit of number storage */
  84 typedef SB32 SHALF;                     /* signed HALF */
  85 typedef USB64 FULL;                     /* double unit of number storage */
  86 typedef SB64 SFULL;                     /* signed FULL */
  87
  88 #define SWAP_HALF_IN_B64(dest, src)     SWAP_B32_IN_B64(dest, src)
  89 #define SWAP_HALF_IN_B32(dest, src)     (*(dest) = *(src))
  90 #define SWAP_HALF_IN_FULL(dest, src)    SWAP_B32_IN_B64(dest, src)
  91 #define SWAP_HALF_IN_HASH(dest, src)    SWAP_B16_IN_HASH(dest, src)
  92 #define SWAP_HALF_IN_FLAG(dest, src)    SWAP_B16_IN_FLAG(dest, src)
  93 #define SWAP_HALF_IN_BOOL(dest, src)    SWAP_B16_IN_BOOL(dest, src)
  94 #define SWAP_HALF_IN_LEN(dest, src)     SWAP_B16_IN_LEN(dest, src)
  95 #define SWAP_B32_IN_FULL(dest, src)     SWAP_B32_IN_B64(dest, src)
  96 #define SWAP_B16_IN_FULL(dest, src)     SWAP_B16_IN_B64(dest, src)
  97 #define SWAP_B16_IN_HALF(dest, src)     SWAP_B16_IN_B32(dest, src)
  98 #define SWAP_B8_IN_FULL(dest, src)      SWAP_B8_IN_B64(dest, src)
  99 #define SWAP_B8_IN_HALF(dest, src)      SWAP_B8_IN_B32(dest, src)
 100
 101 #else
 102
 103 #define BASEB   16                      /* use base 2^16 */
 104 typedef USB16 HALF;                     /* unit of number storage */
 105 typedef SB16 SHALF;                     /* signed HALF */
 106 typedef USB32 FULL;                     /* double unit of number storage */
 107 typedef SB32 SFULL;                     /* signed FULL */
 108
 109 #define SWAP_HALF_IN_B64(dest, src)     SWAP_B16_IN_B64(dest, src)
 110 #define SWAP_HALF_IN_B32(dest, src)     SWAP_B16_IN_B32(dest, src)
 111 #define SWAP_HALF_IN_FULL(dest, src)    SWAP_B16_IN_B32(dest, src)
 112 #define SWAP_HALF_IN_HASH(dest, src)    SWAP_B16_IN_HASH(dest, src)
 113 #define SWAP_HALF_IN_FLAG(dest, src)    SWAP_B16_IN_FLAG(dest, src)
 114 #define SWAP_HALF_IN_BOOL(dest, src)    SWAP_B16_IN_BOOL(dest, src)
 115 #define SWAP_HALF_IN_LEN(dest, src)     SWAP_B16_IN_LEN(dest, src)
 116 #define SWAP_B32_IN_FULL(dest, src)     (*(dest) = *(src))
 117 #define SWAP_B16_IN_FULL(dest, src)     SWAP_B16_IN_B32(dest, src)
 118 #define SWAP_B16_IN_HALF(dest, src)     (*(dest) = *(src))
 119 #define SWAP_B8_IN_FULL(dest, src)      SWAP_B8_IN_B32(dest, src)
 120 #define SWAP_B8_IN_HALF(dest, src)      SWAP_B8_IN_B16(dest, src)
 121
 122 #endif
 123
 124 #define BASE    ((FULL)1<<BASEB)                /* base for calculations */
 125 #define BASE1   (BASE - (FULL)1)                /* one less than base */
 126 #define BASEDIG ((BASEB/16)*5)                  /* number of digits in base */
 127 #define FULL_BITS (2*BASEB)                     /* bits in a FULL */
 128
 129 #define TOPHALF ((FULL)1 << (BASEB-1))          /* highest bit in a HALF */
 130 #define MAXHALF (TOPHALF - (FULL)1)             /* largest SHALF value */
 131
 132 #define TOPFULL ((FULL)1 << (FULL_BITS-1))      /* highest bit in FULL */
 133 #define MAXFULL (TOPFULL - (FULL)1)             /* largest SFULL value */
 134 #define MINSFULL ((SFULL)(TOPFULL))             /* most negative SFULL value */
 135 #define MAXUFULL (MAXFULL | TOPFULL)            /* largest FULL value */
 136
 137 #define TOPLONG ((unsigned long)1 << (LONG_BITS-1))     /* top long bit */
 138 #define MAXLONG ((long) (TOPLONG - (unsigned long)1))   /* largest long val */
 139 #define MAXULONG (MAXLONG | TOPLONG)            /* largest unsigned long val */
 140
 141
 142 /*
 143  * other misc typedefs
 144  */
 145 typedef USB32 QCKHASH;                  /* 32 bit hash value */
 146 #if defined(HAVE_B64) && LONG_BITS == 32
 147 typedef HALF PRINT;                     /* cast for zio printing fucctions */
 148 #define SWAP_B16_IN_PRINT(dest, src)    SWAP_B16_IN_HALF(dest, src)
 149 #define SWAP_B8_IN_PRINT(dest, src)     SWAP_B8_IN_HALF(dest, src)
 150 #else
 151 typedef FULL PRINT;                     /* cast for zio printing fucctions */
 152 #define SWAP_B16_IN_PRINT(dest, src)    SWAP_B16_IN_FULL(dest, src)
 153 #define SWAP_B8_IN_PRINT(dest, src)     SWAP_B8_IN_FULL(dest, src)
 154 #endif
 155 typedef SB32 FLAG;                      /* small value (e.g. comparison) */
 156 typedef SB32 BOOL;                      /* TRUE or FALSE value */
 157 typedef SB32 LEN;                       /* unit of length storage */
 158
 159 #define SWAP_B32_IN_HASH(dest, src)     (*(dest) = *(src))
 160 #define SWAP_B16_IN_HASH(dest, src)     SWAP_B16_IN_B32(dest, src)
 161 #define SWAP_B8_IN_HASH(dest, src)      SWAP_B8_IN_B32(dest, src)
 162
 163 #define SWAP_B32_IN_FLAG(dest, src)     (*(dest) = *(src))
 164 #define SWAP_B16_IN_FLAG(dest, src)     SWAP_B16_IN_B32(dest, src)
 165 #define SWAP_B8_IN_FLAG(dest, src)      SWAP_B8_IN_B32(dest, src)
 166
 167 #define SWAP_B32_IN_BOOL(dest, src)     (*(dest) = *(src))
 168 #define SWAP_B16_IN_BOOL(dest, src)     SWAP_B16_IN_B32(dest, src)
 169 #define SWAP_B8_IN_BOOL(dest, src)      SWAP_B8_IN_B32(dest, src)
 170
 171 #define SWAP_B32_IN_LEN(dest, src)      (*(dest) = *(src))
 172 #define SWAP_B16_IN_LEN(dest, src)      SWAP_B16_IN_B32(dest, src)
 173 #define SWAP_B8_IN_LEN(dest, src)       SWAP_B8_IN_B32(dest, src)
 174
 175 #if LONG_BITS == 64
 176 #define SWAP_HALF_IN_LONG(dest, src)    SWAP_HALF_IN_B64(dest, src)
 177 #else /* LONG_BITS == 64 */
 178 #define SWAP_HALF_IN_LONG(dest, src)    SWAP_HALF_IN_B32(dest, src)
 179 #endif /* LONG_BITS == 64 */
 180
 181
 182 /*
 183  * FNV-1 basis
 184  *
 185  * We start the hash at a non-zero value at the beginning so that
 186  * hashing blocks of data with all 0 bits do not map onto the same
 187  * 0 hash value.  The virgin value that we use below is the hash value
 188  * that we would get from following 32 ASCII characters:
 189  *
 190  *              chongo <Landon Curt Noll> /\../\
 191  *
 192  * Note that the \'s above are not back-slashing escape characters.
 193  * They are literal ASCII  backslash 0x5c characters.
 194  *
 195  * The effect of this virgin initial value is the same as starting
 196  * with 0 and pre-pending those 32 characters onto the data being
 197  * hashed.
 198  *
 199  * Yes, even with this non-zero virgin value there is a set of data
 200  * that will result in a zero hash value.  Worse, appending any
 201  * about of zero bytes will continue to produce a zero hash value.
 202  * But that would happen with any initial value so long as the
 203  * hash of the initial was the `inverse' of the virgin prefix string.
 204  *
 205  * But then again for any hash function, there exists sets of data
 206  * which that the hash of every member is the same value.  That is
 207  * life with many to few mapping functions.  All we do here is to
 208  * prevent sets whose members consist of 0 or more bytes of 0's from
 209  * being such an awkward set.
 210  *
 211  * And yes, someone can figure out what the magic 'inverse' of the
 212  * 32 ASCII character are ... but this hash function is NOT intended
 213  * to be a cryptographic hash function, just a fast and reasonably
 214  * good hash function.
 215  */
 216 #define FNV1_32_BASIS ((QCKHASH)(0x811c9dc5))
 217
 218
 219 /*
 220  * The largest power of 10 we will compute for our decimal conversion
 221  * internal constants is: 10^(2^TEN_MAX).
 222  */
 223 #define TEN_MAX 31      /* 10^2^31 requires about 1.66 * 2^29 bytes */
 224
 225
 226 /*
 227  * LEN storage size must be <= FULL storage size
 228  */
 229 #define MAXLEN  ((LEN) 0x7fffffff >> 3) /* longest value allowed */
 230
 231
 232 #define MAXREDC 64                      /* number of entries in REDC cache */
 233 #define SQ_ALG2 3388                    /* size for alternative squaring */
 234 #define MUL_ALG2 1780                   /* size for alternative multiply */
 235 #define POW_ALG2 176                    /* size for using REDC for powers */
 236 /* old REDC_ALG2 was 5/4 of POW_ALG2, so we will keep the same ratio */
 237 #define REDC_ALG2 220                   /* size for using alternative REDC */
 238
 239
 240 typedef union {
 241         FULL    ivalue;
 242         struct {
 243                 HALF Svalue1;
 244                 HALF Svalue2;
 245         } sis;
 246 } SIUNION;
 247
 248
 249 #if !defined(LITTLE_ENDIAN)
 250 #define LITTLE_ENDIAN   1234    /* Least Significant Byte first */
 251 #endif
 252 #if !defined(BIG_ENDIAN)
 253 #define BIG_ENDIAN      4321    /* Most Significant Byte first */
 254 #endif
 255 /* PDP_ENDIAN - LSB in word, MSW in long is not supported */
 256
 257 #if CALC_BYTE_ORDER == LITTLE_ENDIAN
 258 # define silow  sis.Svalue1     /* low order half of full value */
 259 # define sihigh sis.Svalue2     /* high order half of full value */
 260 #else
 261 # if CALC_BYTE_ORDER == BIG_ENDIAN
 262 #  define silow sis.Svalue2     /* low order half of full value */
 263 #  define sihigh sis.Svalue1    /* high order half of full value */
 264 # else
 265    /\oo/\    CALC_BYTE_ORDER must be BIG_ENDIAN or LITTLE_ENDIAN    /\oo/\  !!!
 266 # endif
 267 #endif
 268
 269
 270 typedef struct {
 271         HALF    *v;             /* pointer to array of values */
 272         LEN     len;            /* number of values in array */
 273         BOOL    sign;           /* sign, nonzero is negative */
 274 } ZVALUE;
 275
 276
 277
 278 /*
 279  * Function prototypes for integer math routines.
 280  */
 281 E_FUNC HALF * alloc(LEN len);
 282 #ifdef  ALLOCTEST
 283 E_FUNC void freeh(HALF *);
 284 #endif
 285
 286
 287 /*
 288  * Input, output, and conversion routines.
 289  */
 290 E_FUNC void zcopy(ZVALUE z, ZVALUE *res);
 291 E_FUNC void itoz(long i, ZVALUE *res);
 292 E_FUNC void utoz(FULL i, ZVALUE *res);
 293 E_FUNC void stoz(SFULL i, ZVALUE *res);
 294 E_FUNC void str2z(char *s, ZVALUE *res);
 295 E_FUNC long ztoi(ZVALUE z);
 296 E_FUNC FULL ztou(ZVALUE z);
 297 E_FUNC SFULL ztos(ZVALUE z);
 298 E_FUNC void zprintval(ZVALUE z, long decimals, long width);
 299 E_FUNC void zprintx(ZVALUE z, long width);
 300 E_FUNC void zprintb(ZVALUE z, long width);
 301 E_FUNC void zprinto(ZVALUE z, long width);
 302 E_FUNC void fitzprint(ZVALUE, long, long);
 303
 304
 305 /*
 306  * Basic numeric routines.
 307  */
 308 E_FUNC void zmuli(ZVALUE z, long n, ZVALUE *res);
 309 E_FUNC long zdivi(ZVALUE z, long n, ZVALUE *res);
 310 E_FUNC long zmodi(ZVALUE z, long n);
 311 E_FUNC void zadd(ZVALUE z1, ZVALUE z2, ZVALUE *res);
 312 E_FUNC void zsub(ZVALUE z1, ZVALUE z2, ZVALUE *res);
 313 E_FUNC void zmul(ZVALUE z1, ZVALUE z2, ZVALUE *res);
 314 E_FUNC long zdiv(ZVALUE z1, ZVALUE z2, ZVALUE *res, ZVALUE *rem, long R);
 315 E_FUNC long zquo(ZVALUE z1, ZVALUE z2, ZVALUE *res, long R);
 316 E_FUNC long zmod(ZVALUE z1, ZVALUE z2, ZVALUE *rem, long R);
 317 E_FUNC void zequo(ZVALUE z1, ZVALUE z2, ZVALUE *res);
 318 E_FUNC BOOL zdivides(ZVALUE z1, ZVALUE z2);
 319 E_FUNC void zor(ZVALUE z1, ZVALUE z2, ZVALUE *res);
 320 E_FUNC void zand(ZVALUE z1, ZVALUE z2, ZVALUE *res);
 321 E_FUNC void zxor(ZVALUE z1, ZVALUE z2, ZVALUE *res);
 322 E_FUNC void zandnot(ZVALUE z1, ZVALUE z2, ZVALUE *res);
 323 E_FUNC long zpopcnt(ZVALUE z, int bitval);
 324 E_FUNC void zshift(ZVALUE z, long n, ZVALUE *res);
 325 E_FUNC void zsquare(ZVALUE z, ZVALUE *res);
 326 E_FUNC long zlowbit(ZVALUE z);
 327 E_FUNC LEN zhighbit(ZVALUE z);
 328 E_FUNC void zbitvalue(long n, ZVALUE *res);
 329 E_FUNC BOOL zisset(ZVALUE z, long n);
 330 E_FUNC BOOL zisonebit(ZVALUE z);
 331 E_FUNC BOOL zisallbits(ZVALUE z);
 332 E_FUNC FLAG ztest(ZVALUE z);
 333 E_FUNC FLAG zrel(ZVALUE z1, ZVALUE z2);
 334 E_FUNC FLAG zabsrel(ZVALUE z1, ZVALUE z2);
 335 E_FUNC BOOL zcmp(ZVALUE z1, ZVALUE z2);
 336
 337
 338 /*
 339  * More complicated numeric functions.
 340  */
 341 E_FUNC FULL uugcd(FULL i1, FULL i2);
 342 E_FUNC long iigcd(long i1, long i2);
 343 E_FUNC void zgcd(ZVALUE z1, ZVALUE z2, ZVALUE *res);
 344 E_FUNC void zlcm(ZVALUE z1, ZVALUE z2, ZVALUE *res);
 345 E_FUNC void zreduce(ZVALUE z1, ZVALUE z2, ZVALUE *z1res, ZVALUE *z2res);
 346 E_FUNC void zfact(ZVALUE z, ZVALUE *dest);
 347 E_FUNC void zperm(ZVALUE z1, ZVALUE z2, ZVALUE *res);
 348 E_FUNC int zcomb(ZVALUE z1, ZVALUE z2, ZVALUE *res);
 349 E_FUNC FLAG zjacobi(ZVALUE z1, ZVALUE z2);
 350 E_FUNC void zfib(ZVALUE z, ZVALUE *res);
 351 E_FUNC void zpowi(ZVALUE z1, ZVALUE z2, ZVALUE *res);
 352 E_FUNC void ztenpow(long power, ZVALUE *res);
 353 E_FUNC void zpowermod(ZVALUE z1, ZVALUE z2, ZVALUE z3, ZVALUE *res);
 354 E_FUNC BOOL zmodinv(ZVALUE z1, ZVALUE z2, ZVALUE *res);
 355 E_FUNC BOOL zrelprime(ZVALUE z1, ZVALUE z2);
 356 E_FUNC long zlog(ZVALUE z1, ZVALUE z2);
 357 E_FUNC long zlog10(ZVALUE z, BOOL *was_10_power);
 358 E_FUNC long zdivcount(ZVALUE z1, ZVALUE z2);
 359 E_FUNC long zfacrem(ZVALUE z1, ZVALUE z2, ZVALUE *rem);
 360 E_FUNC long zgcdrem(ZVALUE z1, ZVALUE z2, ZVALUE *res);
 361 E_FUNC long zdigits(ZVALUE z1);
 362 E_FUNC long zdigit(ZVALUE z1, long n);
 363 E_FUNC FLAG zsqrt(ZVALUE z1, ZVALUE *dest, long R);
 364 E_FUNC void zroot(ZVALUE z1, ZVALUE z2, ZVALUE *dest);
 365 E_FUNC BOOL zissquare(ZVALUE z);
 366 E_FUNC void zhnrmod(ZVALUE v, ZVALUE h, ZVALUE zn, ZVALUE zr, ZVALUE *res);
 367
 368
 369 /*
 370  * Prime related functions.
 371  */
 372 E_FUNC FLAG zisprime(ZVALUE z);
 373 E_FUNC FULL znprime(ZVALUE z);
 374 E_FUNC FULL next_prime(FULL v);
 375 E_FUNC FULL zpprime(ZVALUE z);
 376 E_FUNC void zpfact(ZVALUE z, ZVALUE *dest);
 377 E_FUNC BOOL zprimetest(ZVALUE z, long count, ZVALUE skip);
 378 E_FUNC BOOL zredcprimetest(ZVALUE z, long count, ZVALUE skip);
 379 E_FUNC BOOL znextcand(ZVALUE z1, long count, ZVALUE skip, ZVALUE res,
 380                       ZVALUE mod, ZVALUE *cand);
 381 E_FUNC BOOL zprevcand(ZVALUE z1, long count, ZVALUE skip, ZVALUE res,
 382                       ZVALUE mod, ZVALUE *cand);
 383 E_FUNC FULL zlowfactor(ZVALUE z, long count);
 384 E_FUNC FLAG zfactor(ZVALUE z1, ZVALUE z2, ZVALUE *res);
 385 E_FUNC long zpix(ZVALUE z1);
 386 E_FUNC void zlcmfact(ZVALUE z, ZVALUE *dest);
 387
 388
 389 /*
 390  * Misc misc functions. :-)
 391  */
 392 E_FUNC void zsquaremod(ZVALUE z1, ZVALUE z2, ZVALUE *res);
 393 E_FUNC void zminmod(ZVALUE z1, ZVALUE z2, ZVALUE *res);
 394 E_FUNC BOOL zcmpmod(ZVALUE z1, ZVALUE z2, ZVALUE z3);
 395 E_FUNC void zio_init(void);
 396
 397
 398 /*
 399  * These functions are for internal use only.
 400  */
 401 E_FUNC void ztrim(ZVALUE *z);
 402 E_FUNC void zshiftr(ZVALUE z, long n);
 403 E_FUNC void zshiftl(ZVALUE z, long n);
 404 E_FUNC HALF *zalloctemp(LEN len);
 405
 406
 407 /*
 408  * Modulo arithmetic definitions.
 409  * Structure holding state of REDC initialization.
 410  * Multiple instances of this structure can be used allowing
 411  * calculations with more than one modulus at the same time.
 412  * Len of zero means the structure is not initialized.
 413  */
 414 typedef struct {
 415         LEN len;                /* number of words in binary modulus */
 416         ZVALUE mod;             /* modulus REDC is computing with */
 417         ZVALUE inv;             /* inverse of modulus in binary modulus */
 418         ZVALUE one;             /* REDC format for the number 1 */
 419 } REDC;
 420
 421 E_FUNC REDC *zredcalloc(ZVALUE z1);
 422 E_FUNC void zredcfree(REDC *rp);
 423 E_FUNC void zredcencode(REDC *rp, ZVALUE z1, ZVALUE *res);
 424 E_FUNC void zredcdecode(REDC *rp, ZVALUE z1, ZVALUE *res);
 425 E_FUNC void zredcmul(REDC *rp, ZVALUE z1, ZVALUE z2, ZVALUE *res);
 426 E_FUNC void zredcsquare(REDC *rp, ZVALUE z1, ZVALUE *res);
 427 E_FUNC void zredcpower(REDC *rp, ZVALUE z1, ZVALUE z2, ZVALUE *res);
 428
 429
 430 /*
 431  * macro expansions to speed this thing up
 432  */
 433 #define ziseven(z)      (!(*(z).v & 0x1))
 434 #define zisodd(z)       (*(z).v & 0x1)
 435 #define ziszero(z)      ((*(z).v == 0) && ((z).len == 1))
 436 #define zisneg(z)       ((z).sign)
 437 #define zispos(z)       (((z).sign == 0) && (*(z).v || ((z).len > 1)))
 438 #define zisunit(z)      ((*(z).v == 1) && ((z).len == 1))
 439 #define zisone(z)       ((*(z).v == 1) && ((z).len == 1) && !(z).sign)
 440 #define zisnegone(z)    ((*(z).v == 1) && ((z).len == 1) && (z).sign)
 441 #define zltnegone(z)    (zisneg(z) && (((z).len > 1) || *(z).v > 1))
 442 #define zistwo(z)       ((*(z).v == 2) && ((z).len == 1) && !(z).sign)
 443 #define zisabstwo(z)    ((*(z).v == 2) && ((z).len == 1))
 444 #define zisabsleone(z)  ((*(z).v <= 1) && ((z).len == 1))
 445 #define zislezero(z)    (zisneg(z) || ziszero(z))
 446 #define zisleone(z)     (zisneg(z) || zisabsleone(z))
 447 #define zistiny(z)      ((z).len == 1)
 448
 449 /*
 450  * zgtmaxfull(z)        TRUE if abs(z) > MAXFULL
 451  */
 452 #define zgtmaxfull(z)   (((z).len > 2) || (((z).len == 2) && \
 453                          (((SHALF)(z).v[1]) < 0)))
 454
 455 /*
 456  * zgtmaxufull(z)       TRUE if abs(z) will not fit into a FULL (> MAXUFULL)
 457  */
 458 #define zgtmaxufull(z)  ((z).len > 2)
 459
 460 /*
 461  * zgtmaxulong(z)       TRUE if abs(z) > MAXULONG
 462  */
 463 #if BASEB >= LONG_BITS
 464 #define zgtmaxulong(z)  ((z).len > 1)
 465 #else
 466 #define zgtmaxulong(z)  zgtmaxufull(z)
 467 #endif
 468
 469 /*
 470  * zgtmaxlong(z)        TRUE if abs(z) > MAXLONG
 471  */
 472 #if BASEB >= LONG_BITS
 473 #define zgtmaxlong(z)   (((z).len > 1) || (((z).len == 1) && \
 474                          (((SHALF)(z).v[0]) < 0)))
 475 #else
 476 #define zgtmaxlong(z)   zgtmaxfull(z)
 477 #endif
 478
 479 /*
 480  * Some algorithms testing for values of a certain length.  Macros such as
 481  * zistiny() do this well.  In other cases algorthms require tests for values
 482  * in comparison to a given power of 2.  In the later case, zistiny() compares
 483  * against a different power of 2 on a 64 bit machine.  The macros below
 484  * provide a tests against powers of 2 that are independent of the work size.
 485  *
 486  *      zge16b(z)       TRUE if abs(z) >= 2^16
 487  *      zge24b(z)       TRUE if abs(z) >= 2^24
 488  *      zge31b(z)       TRUE if abs(z) >= 2^31
 489  *      zge32b(z)       TRUE if abs(z) >= 2^32
 490  *      zge64b(z)       TRUE if abs(z) >= 2^64
 491  *      zge128b(z)      TRUE if abs(z) >= 2^128
 492  *      zge256b(z)      TRUE if abs(z) >= 2^256
 493  *      zge512b(z)      TRUE if abs(z) >= 2^512
 494  *      zge1024b(z)     TRUE if abs(z) >= 2^1024
 495  *      zge2048b(z)     TRUE if abs(z) >= 2^2048
 496  *      zge4096b(z)     TRUE if abs(z) >= 2^4096
 497  *      zge8192b(z)     TRUE if abs(z) >= 2^8192
 498  */
 499 #if BASEB == 32
 500
 501 #define zge16b(z)       (!zistiny(z) || ((z).v[0] >= (HALF)0x10000))
 502 #define zge24b(z)       (!zistiny(z) || ((z).v[0] >= (HALF)0x1000000))
 503 #define zge31b(z)       (!zistiny(z) || (((SHALF)(z).v[0]) < 0))
 504 #define zge32b(z)       (!zistiny(z))
 505 #define zge64b(z)       ((z).len > 2)
 506 #define zge128b(z)      ((z).len > 4)
 507 #define zge256b(z)      ((z).len > 8)
 508 #define zge512b(z)      ((z).len > 16)
 509 #define zge1024b(z)     ((z).len > 32)
 510 #define zge2048b(z)     ((z).len > 64)
 511 #define zge4096b(z)     ((z).len > 128)
 512 #define zge8192b(z)     ((z).len > 256)
 513
 514 #else
 515
 516 #define zge16b(z)       (!zistiny(z))
 517 #define zge24b(z)       (((z).len > 2) || (((z).len == 2) && \
 518                          ((z).v[1] >= (HALF)0x100)))
 519 #define zge31b(z)       (((z).len > 2) || (((z).len == 2) && \
 520                          (((SHALF)(z).v[1]) < 0)))
 521 #define zge32b(z)       ((z).len > 2)
 522 #define zge64b(z)       ((z).len > 4)
 523 #define zge128b(z)      ((z).len > 8)
 524 #define zge256b(z)      ((z).len > 16)
 525 #define zge512b(z)      ((z).len > 32)
 526 #define zge1024b(z)     ((z).len > 64)
 527 #define zge2048b(z)     ((z).len > 128)
 528 #define zge4096b(z)     ((z).len > 256)
 529 #define zge8192b(z)     ((z).len > 512)
 530
 531 #endif
 532
 533
 534 /*
 535  * ztofull - convert an absolute value of a ZVALUE to a FULL if possible
 536  *
 537  * If the value is too large, only the low order bits that are able to
 538  * be converted into a FULL will be used.
 539  */
 540 #define ztofull(z)      (zistiny(z) ? ((FULL)((z).v[0])) :              \
 541                                       ((FULL)((z).v[0]) +               \
 542                                        ((FULL)((z).v[1]) << BASEB)))
 543
 544 #define z1tol(z)        ((long)((z).v[0]))
 545 #define z2tol(z)        ((long)(((z).v[0]) + \
 546                                 (((z).v[1] & MAXHALF) << BASEB)))
 547
 548 /*
 549  * ztoulong - convert an absolute value of a ZVALUE to an unsigned long
 550  *
 551  * If the value is too large, only the low order bits that are able to
 552  * be converted into a long will be used.
 553  */
 554 #if BASEB >= LONG_BITS
 555 # define ztoulong(z)    ((unsigned long)z1tol(z))
 556 #else
 557 # define ztoulong(z)    ((unsigned long)ztofull(z))
 558 #endif
 559
 560 /*
 561  * ztolong - convert an absolute value of a ZVALUE to a long
 562  *
 563  * If the value is too large, only the low order bits that are able to
 564  * be converted into a long will be used.
 565  */
 566 #define ztolong(z)      ((long)(ztoulong(z) & MAXLONG))
 567
 568 #define zclearval(z)    memset((z).v, 0, (z).len * sizeof(HALF))
 569 #define zcopyval(z1,z2) memcpy((z2).v, (z1).v, (z1).len * sizeof(HALF))
 570 #define zquicktrim(z)   {if (((z).len > 1) && ((z).v[(z).len-1] == 0)) \
 571                                 (z).len--;}
 572 #define zfree(z)        freeh((z).v)
 573
 574
 575 /*
 576  * Output modes for numeric displays.
 577  */
 578 #define MODE_DEFAULT    0
 579 #define MODE_FRAC       1
 580 #define MODE_INT        2
 581 #define MODE_REAL       3
 582 #define MODE_EXP        4
 583 #define MODE_HEX        5
 584 #define MODE_OCTAL      6
 585 #define MODE_BINARY     7
 586 #define MODE_MAX        7
 587 #define MODE2_OFF       (MODE_MAX+1)
 588
 589 #define MODE_INITIAL    MODE_REAL
 590 #define MODE2_INITIAL   MODE2_OFF
 591
 592
 593 /*
 594  * Output routines for either FILE handles or strings.
 595  */
 596 E_FUNC void math_chr(int ch);
 597 E_FUNC void math_str(char *str);
 598 E_FUNC void math_fill(char *str, long width);
 599 E_FUNC void math_flush(void);
 600 E_FUNC void math_divertio(void);
 601 E_FUNC void math_cleardiversions(void);
 602 E_FUNC char *math_getdivertedio(void);
 603 E_FUNC int math_setmode(int mode);
 604 E_FUNC int math_setmode2(int mode);
 605 E_FUNC LEN math_setdigits(LEN digits);
 606 E_FUNC void math_fmt(char *, ...) PRINTF_FORMAT(1, 2);
 607
 608
 609 /*
 610  * The error routine.
 611  */
 612 E_FUNC void math_error(char *, ...) PRINTF_FORMAT(1, 2);
 613
 614
 615 /*
 616  * external swap functions
 617  */
 618 E_FUNC HALF *swap_b8_in_HALFs(HALF *dest, HALF *src, LEN len);
 619 E_FUNC ZVALUE *swap_b8_in_ZVALUE(ZVALUE *dest, ZVALUE *src, BOOL all);
 620 E_FUNC HALF *swap_b16_in_HALFs(HALF *dest, HALF *src, LEN len);
 621 E_FUNC ZVALUE *swap_b16_in_ZVALUE(ZVALUE *dest, ZVALUE *src, BOOL all);
 622 E_FUNC ZVALUE *swap_HALF_in_ZVALUE(ZVALUE *dest, ZVALUE *src, BOOL all);
 623
 624
 625 /*
 626  * constants used often by the arithmetic routines
 627  */
 628 EXTERN HALF _zeroval_[], _oneval_[], _twoval_[], _threeval_[], _fourval_[];
 629 EXTERN HALF _fiveval_[], _sixval_[], _sevenval_[], _eightval_[], _nineval_[];
 630 EXTERN HALF _tenval_[], _elevenval_[], _twelveval_[], _thirteenval_[];
 631 EXTERN HALF _fourteenval_[], _fifteenval_[];
 632 EXTERN HALF _sqbaseval_[];
 633 EXTERN HALF _fourthbaseval_[];
 634
 635 EXTERN ZVALUE zconst[];         /* ZVALUE integers from 0 thru 15 */
 636
 637 EXTERN ZVALUE _zero_, _one_, _two_, _ten_, _neg_one_;
 638 EXTERN ZVALUE _sqbase_, _pow4base_, _pow8base_;
 639
 640 EXTERN ZVALUE _b32_, _b64_;
 641
 642 EXTERN BOOL _math_abort_;       /* nonzero to abort calculations */
 643 EXTERN ZVALUE _tenpowers_[];    /* table of 10^2^n */
 644
 645 /*
 646  * Bit fiddeling functions and types
 647  */
 648 EXTERN HALF bitmask[];          /* bit rotation, norm 0 */
 649 EXTERN HALF lowhalf[];          /* bit masks from low end of HALF */
 650 EXTERN HALF rlowhalf[];         /* reversed bit masks from low end of HALF */
 651 EXTERN HALF highhalf[];         /* bit masks from high end of HALF */
 652 EXTERN HALF rhighhalf[];        /* reversed bit masks from high end of HALF */
 653 #define HAVE_REVERSED_MASKS     /* allows old code to know libcalc.a has them */
 654
 655
 656 /*
 657  * BITSTR - string of bits within an array of HALFs
 658  *
 659  * This typedef records a location of a bit in an array of HALFs.
 660  * Bit 0 in a HALF is assumed to be the least significant bit in that HALF.
 661  *
 662  * The most significant bit is found at (loc,bit).  Bits of lesser
 663  * significance may be found in previous bits and HALFs.
 664  */
 665 typedef struct {
 666         HALF *loc;      /* half address of most significant bit */
 667         int bit;        /* bit position within half of most significant bit */
 668         int len;        /* length of string in bits */
 669 } BITSTR;
 670
 671
 672 #endif /* !__ZMATH_H__*/