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