contrib/bc/include/num.h

   1 /*
   2  * *****************************************************************************
   3  *
   4  * SPDX-License-Identifier: BSD-2-Clause
   5  *
   6  * Copyright (c) 2018-2021 Gavin D. Howard and contributors.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions are met:
  10  *
  11  * * Redistributions of source code must retain the above copyright notice, this
  12  *   list of conditions and the following disclaimer.
  13  *
  14  * * Redistributions in binary form must reproduce the above copyright notice,
  15  *   this list of conditions and the following disclaimer in the documentation
  16  *   and/or other materials provided with the distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  19  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  20  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  21  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
  22  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  23  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  24  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  25  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  26  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  27  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  28  * POSSIBILITY OF SUCH DAMAGE.
  29  *
  30  * *****************************************************************************
  31  *
  32  * Definitions for the num type.
  33  *
  34  */
  35
  36 #ifndef BC_NUM_H
  37 #define BC_NUM_H
  38
  39 #include <limits.h>
  40 #include <stdbool.h>
  41 #include <stddef.h>
  42 #include <stdint.h>
  43
  44 #include <sys/types.h>
  45
  46 #include <status.h>
  47 #include <vector.h>
  48 #include <bcl.h>
  49
  50 #ifndef BC_ENABLE_EXTRA_MATH
  51 #define BC_ENABLE_EXTRA_MATH (1)
  52 #endif // BC_ENABLE_EXTRA_MATH
  53
  54 /// Everything in bc is base 10..
  55 #define BC_BASE (10)
  56
  57 /// Alias.
  58 typedef unsigned long ulong;
  59
  60 /// This is here because BcBigDig came first, but when I created bcl, it's
  61 /// definition has to be defined first.
  62 typedef BclBigDig BcBigDig;
  63
  64 #if BC_LONG_BIT >= 64
  65
  66 /// The biggest number held by a BcBigDig.
  67 #define BC_NUM_BIGDIG_MAX ((BcBigDig) UINT64_MAX)
  68
  69 /// The number of decimal digits in one limb.
  70 #define BC_BASE_DIGS (9)
  71
  72 /// The max number + 1 that one limb can hold.
  73 #define BC_BASE_POW (1000000000)
  74
  75 /// An alias for portability.
  76 #define BC_NUM_BIGDIG_C UINT64_C
  77
  78 /// The actual limb type.
  79 typedef int_least32_t BcDig;
  80
  81 #elif BC_LONG_BIT >= 32
  82
  83 /// The biggest number held by a BcBigDig.
  84 #define BC_NUM_BIGDIG_MAX ((BcBigDig) UINT32_MAX)
  85
  86 /// The number of decimal digits in one limb.
  87 #define BC_BASE_DIGS (4)
  88
  89 /// The max number + 1 that one limb can hold.
  90 #define BC_BASE_POW (10000)
  91
  92 /// An alias for portability.
  93 #define BC_NUM_BIGDIG_C UINT32_C
  94
  95 /// The actual limb type.
  96 typedef int_least16_t BcDig;
  97
  98 #else
  99
 100 /// LONG_BIT must be at least 32 on POSIX. We depend on that.
 101 #error BC_LONG_BIT must be at least 32
 102
 103 #endif // BC_LONG_BIT >= 64
 104
 105 /// The default (and minimum) number of limbs when allocating a number.
 106 #define BC_NUM_DEF_SIZE (8)
 107
 108 /// The actual number struct. This is where the magic happens.
 109 typedef struct BcNum {
 110
 111         /// The limb array. It is restrict because *no* other item should own the
 112         /// array. For more information, see the development manual
 113         /// (manuals/development.md#numbers).
 114         BcDig *restrict num;
 115
 116         /// The number of limbs before the decimal (radix) point. This also stores
 117         /// the negative bit in the least significant bit since it uses at least two
 118         /// bits less than scale. It is also used less than scale. See the
 119         /// development manual (manuals/development.md#numbers) for more info.
 120         size_t rdx;
 121
 122         /// The actual scale of the number. This is different from rdx because there
 123         /// are multiple digits in one limb, and in the last limb, only some of the
 124         /// digits may be part of the scale. However, scale must always match rdx
 125         /// (except when the number is 0), or there is a bug. For more information,
 126         /// see the development manual (manuals/development.md#numbers).
 127         size_t scale;
 128
 129         /// The number of valid limbs in the array. If this is 0, then the number is
 130         /// 0 as well.
 131         size_t len;
 132
 133         /// The capacity of the limbs array. This is how many limbs the number could
 134         /// expand to without reallocation.
 135         size_t cap;
 136
 137 } BcNum;
 138
 139 #if BC_ENABLE_EXTRA_MATH
 140
 141 // Forward declaration
 142 struct BcRNG;
 143
 144 #endif // BC_ENABLE_EXTRA_MATH
 145
 146 /// The minimum obase.
 147 #define BC_NUM_MIN_BASE (BC_NUM_BIGDIG_C(2))
 148
 149 /// The maximum ibase allowed by POSIX.
 150 #define BC_NUM_MAX_POSIX_IBASE (BC_NUM_BIGDIG_C(16))
 151
 152 /// The actual ibase supported by this implementation.
 153 #define BC_NUM_MAX_IBASE (BC_NUM_BIGDIG_C(36))
 154
 155 /// The max base allowed by bc_num_parseChar().
 156 #define BC_NUM_MAX_LBASE (BC_NUM_BIGDIG_C('Z' + BC_BASE + 1))
 157
 158 /// The default number of characters to print before a backslash newline.
 159 #define BC_NUM_PRINT_WIDTH (BC_NUM_BIGDIG_C(69))
 160
 161 /// The base for printing streams from numbers.
 162 #define BC_NUM_STREAM_BASE (256)
 163
 164 // This sets a default for the Karatsuba length.
 165 #ifndef BC_NUM_KARATSUBA_LEN
 166 #define BC_NUM_KARATSUBA_LEN (BC_NUM_BIGDIG_C(32))
 167 #elif BC_NUM_KARATSUBA_LEN < 16
 168 #error BC_NUM_KARATSUBA_LEN must be at least 16.
 169 #endif // BC_NUM_KARATSUBA_LEN
 170
 171 // A crude, but always big enough, calculation of
 172 // the size required for ibase and obase BcNum's.
 173 #define BC_NUM_BIGDIG_LOG10 (BC_NUM_DEF_SIZE)
 174
 175 /**
 176  * Returns non-zero if the BcNum @a n is non-zero.
 177  * @param n  The number to test.
 178  * @return   Non-zero if @a n is non-zero, zero otherwise.
 179  */
 180 #define BC_NUM_NONZERO(n) ((n)->len)
 181
 182 /**
 183  * Returns true if the BcNum @a n is zero.
 184  * @param n  The number to test.
 185  * @return   True if @a n is zero, false otherwise.
 186  */
 187 #define BC_NUM_ZERO(n) (!BC_NUM_NONZERO(n))
 188
 189 /**
 190  * Returns true if the BcNum @a n is one with no scale.
 191  * @param n  The number to test.
 192  * @return   True if @a n equals 1 with no scale, false otherwise.
 193  */
 194 #define BC_NUM_ONE(n) ((n)->len == 1 && (n)->rdx == 0 && (n)->num[0] == 1)
 195
 196 /**
 197  * Converts the letter @a c into a number.
 198  * @param c  The letter to convert.
 199  * @return   The number corresponding to the letter.
 200  */
 201 #define BC_NUM_NUM_LETTER(c) ((c) - 'A' + BC_BASE)
 202
 203 /// The number of allocations done by bc_num_k(). If you change the number of
 204 /// allocations, you must change this. This is done in order to allocate them
 205 /// all as one allocation and just give them all pointers to different parts.
 206 /// Works pretty well, but you have to be careful.
 207 #define BC_NUM_KARATSUBA_ALLOCS (6)
 208
 209 /**
 210  * Rounds @a s (scale) up to the next power of BC_BASE_DIGS. This also check for
 211  * overflow and gives a fatal error if that happens because we just can't go
 212  * over the limits we have imposed.
 213  * @param s  The scale to round up.
 214  * @return   @a s rounded up to the next power of BC_BASE_DIGS.
 215  */
 216 #define BC_NUM_ROUND_POW(s) (bc_vm_growSize((s), BC_BASE_DIGS - 1))
 217
 218 /**
 219  * Returns the equivalent rdx for the scale @a s.
 220  * @param s  The scale to convert.
 221  * @return   The rdx for @a s.
 222  */
 223 #define BC_NUM_RDX(s) (BC_NUM_ROUND_POW(s) / BC_BASE_DIGS)
 224
 225 /**
 226  * Returns the actual rdx of @a n. (It removes the negative bit.)
 227  * @param n  The number.
 228  * @return   The real rdx of @a n.
 229  */
 230 #define BC_NUM_RDX_VAL(n) ((n)->rdx >> 1)
 231
 232 /**
 233  * Returns the actual rdx of @a n, where @a n is not a pointer. (It removes the
 234  * negative bit.)
 235  * @param n  The number.
 236  * @return   The real rdx of @a n.
 237  */
 238 #define BC_NUM_RDX_VAL_NP(n) ((n).rdx >> 1)
 239
 240 /**
 241  * Sets the rdx of @a n to @a v.
 242  * @param n  The number.
 243  * @param v  The value to set the rdx to.
 244  */
 245 #define BC_NUM_RDX_SET(n, v) \
 246         ((n)->rdx = (((v) << 1) | ((n)->rdx & (BcBigDig) 1)))
 247
 248 /**
 249  * Sets the rdx of @a n to @a v, where @a n is not a pointer.
 250  * @param n  The number.
 251  * @param v  The value to set the rdx to.
 252  */
 253 #define BC_NUM_RDX_SET_NP(n, v) \
 254         ((n).rdx = (((v) << 1) | ((n).rdx & (BcBigDig) 1)))
 255
 256 /**
 257  * Sets the rdx of @a n to @a v and the negative bit to @a neg.
 258  * @param n    The number.
 259  * @param v    The value to set the rdx to.
 260  * @param neg  The value to set the negative bit to.
 261  */
 262 #define BC_NUM_RDX_SET_NEG(n, v, neg) \
 263         ((n)->rdx = (((v) << 1) | (neg)))
 264
 265 /**
 266  * Returns true if the rdx and scale for @a n match.
 267  * @param n  The number to test.
 268  * @return   True if the rdx and scale of @a n match, false otherwise.
 269  */
 270 #define BC_NUM_RDX_VALID(n) \
 271         (BC_NUM_ZERO(n) || BC_NUM_RDX_VAL(n) * BC_BASE_DIGS >= (n)->scale)
 272
 273 /**
 274  * Returns true if the rdx and scale for @a n match, where @a n is not a
 275  * pointer.
 276  * @param n  The number to test.
 277  * @return   True if the rdx and scale of @a n match, false otherwise.
 278  */
 279 #define BC_NUM_RDX_VALID_NP(n) \
 280         ((!(n).len) || BC_NUM_RDX_VAL_NP(n) * BC_BASE_DIGS >= (n).scale)
 281
 282 /**
 283  * Returns true if @a n is negative, false otherwise.
 284  * @param n  The number to test.
 285  * @return   True if @a n is negative, false otherwise.
 286  */
 287 #define BC_NUM_NEG(n) ((n)->rdx & ((BcBigDig) 1))
 288
 289 /**
 290  * Returns true if @a n is negative, false otherwise, where @a n is not a
 291  * pointer.
 292  * @param n  The number to test.
 293  * @return   True if @a n is negative, false otherwise.
 294  */
 295 #define BC_NUM_NEG_NP(n) ((n).rdx & ((BcBigDig) 1))
 296
 297 /**
 298  * Clears the negative bit on @a n.
 299  * @param n  The number.
 300  */
 301 #define BC_NUM_NEG_CLR(n) ((n)->rdx &= ~((BcBigDig) 1))
 302
 303 /**
 304  * Clears the negative bit on @a n, where @a n is not a pointer.
 305  * @param n  The number.
 306  */
 307 #define BC_NUM_NEG_CLR_NP(n) ((n).rdx &= ~((BcBigDig) 1))
 308
 309 /**
 310  * Sets the negative bit on @a n.
 311  * @param n  The number.
 312  */
 313 #define BC_NUM_NEG_SET(n) ((n)->rdx |= ((BcBigDig) 1))
 314
 315 /**
 316  * Toggles the negative bit on @a n.
 317  * @param n  The number.
 318  */
 319 #define BC_NUM_NEG_TGL(n) ((n)->rdx ^= ((BcBigDig) 1))
 320
 321 /**
 322  * Toggles the negative bit on @a n, where @a n is not a pointer.
 323  * @param n  The number.
 324  */
 325 #define BC_NUM_NEG_TGL_NP(n) ((n).rdx ^= ((BcBigDig) 1))
 326
 327 /**
 328  * Returns the rdx val for @a n if the negative bit is set to @a v.
 329  * @param n  The number.
 330  * @param v  The value for the negative bit.
 331  * @return   The value of the rdx of @a n if the negative bit were set to @a v.
 332  */
 333 #define BC_NUM_NEG_VAL(n, v) (((n)->rdx & ~((BcBigDig) 1)) | (v))
 334
 335 /**
 336  * Returns the rdx val for @a n if the negative bit is set to @a v, where @a n
 337  * is not a pointer.
 338  * @param n  The number.
 339  * @param v  The value for the negative bit.
 340  * @return   The value of the rdx of @a n if the negative bit were set to @a v.
 341  */
 342 #define BC_NUM_NEG_VAL_NP(n, v) (((n).rdx & ~((BcBigDig) 1)) | (v))
 343
 344 /**
 345  * Returns the size, in bytes, of limb array with @a n limbs.
 346  * @param n  The number.
 347  * @return   The size, in bytes, of a limb array with @a n limbs.
 348  */
 349 #define BC_NUM_SIZE(n) ((n) * sizeof(BcDig))
 350
 351 // These are for debugging only.
 352 #if BC_DEBUG_CODE
 353 #define BC_NUM_PRINT(x) fprintf(stderr, "%s = %lu\n", #x, (unsigned long)(x))
 354 #define DUMP_NUM bc_num_dump
 355 #else // BC_DEBUG_CODE
 356 #undef DUMP_NUM
 357 #define DUMP_NUM(x,y)
 358 #define BC_NUM_PRINT(x)
 359 #endif // BC_DEBUG_CODE
 360
 361 /**
 362  * A function type for binary operators.
 363  * @param a      The first parameter.
 364  * @param b      The second parameter.
 365  * @param c      The return value.
 366  * @param scale  The current scale.
 367  */
 368 typedef void (*BcNumBinaryOp)(BcNum* a, BcNum* b, BcNum* c, size_t scale);
 369
 370 /**
 371  * A function type for binary operators *after* @a c has been properly
 372  * allocated. At this point, *nothing* should be pointing to @a c (in any way
 373  * that matters, anyway).
 374  * @param a      The first operand.
 375  * @param b      The second operand.
 376  * @param c      The return parameter.
 377  * @param scale  The current scale.
 378  */
 379 typedef void (*BcNumBinOp)(BcNum* a, BcNum* b, BcNum* restrict c, size_t scale);
 380
 381 /**
 382  * A function type for getting the allocation size needed for a binary operator.
 383  * Any function used for this *must* return enough space for *all* possible
 384  * invocations of the operator.
 385  * @param a      The first parameter.
 386  * @param b      The second parameter.
 387  * @param scale  The current scale.
 388  * @return       The size of allocation needed for the result of the operator
 389  *               with @a a, @a b, and @a scale.
 390  */
 391 typedef size_t (*BcNumBinaryOpReq)(const BcNum* a, const BcNum* b,
 392                                    size_t scale);
 393
 394 /**
 395  * A function type for printing a "digit." Functions of this type will print one
 396  * digit in a number. Digits are printed differently based on the base, which is
 397  * why there is more than one implementation of this function type.
 398  * @param n       The "digit" to print.
 399  * @param len     The "length" of the digit, or number of characters that will
 400  *                need to be printed for the digit.
 401  * @param rdx     True if a decimal (radix) point should be printed.
 402  * @param bslash  True if a backslash+newline should be printed if the character
 403  *                limit for the line is reached, false otherwise.
 404  */
 405 typedef void (*BcNumDigitOp)(size_t n, size_t len, bool rdx, bool bslash);
 406
 407 /**
 408  * A function type to run an operator on @a a and @a b and store the result in
 409  * @a a. This is used in karatsuba for faster adds and subtracts at the end.
 410  * @param a    The first parameter and return value.
 411  * @param b    The second parameter.
 412  * @param len  The minimum length of both arrays.
 413  */
 414 typedef void (*BcNumShiftAddOp)(BcDig* restrict a, const BcDig* restrict b,
 415                                 size_t len);
 416
 417 /**
 418  * Initializes @a n with @a req limbs in its array.
 419  * @param n    The number to initialize.
 420  * @param req  The number of limbs @a n must have in its limb array.
 421  */
 422 void bc_num_init(BcNum *restrict n, size_t req);
 423
 424 /**
 425  * Initializes (sets up) @a n with the preallocated limb array @a num that has
 426  * size @a cap. This is called by @a bc_num_init(), but it is also used by parts
 427  * of bc that use statically allocated limb arrays.
 428  * @param n    The number to initialize.
 429  * @param num  The preallocated limb array.
 430  * @param cap  The capacity of @a num.
 431  */
 432 void bc_num_setup(BcNum *restrict n, BcDig *restrict num, size_t cap);
 433
 434 /**
 435  * Copies @a s into @a d. This does a deep copy and requires that @a d is
 436  * already a valid and allocated BcNum.
 437  * @param d  The destination BcNum.
 438  * @param s  The source BcNum.
 439  */
 440 void bc_num_copy(BcNum *d, const BcNum *s);
 441
 442 /**
 443  * Creates @a d and copies @a s into @a d. This does a deep copy and requires
 444  * that @a d is *not* a valid or allocated BcNum.
 445  * @param d  The destination BcNum.
 446  * @param s  The source BcNum.
 447  */
 448 void bc_num_createCopy(BcNum *d, const BcNum *s);
 449
 450 /**
 451  * Creates (initializes) @a n and sets its value to the equivalent of @a val.
 452  * @a n must *not* be a valid or preallocated BcNum.
 453  * @param n    The number to initialize and set.
 454  * @param val  The value to set @a n's value to.
 455  */
 456 void bc_num_createFromBigdig(BcNum *restrict n, BcBigDig val);
 457
 458 /**
 459  * Makes @a n valid for holding strings. @a n must *not* be allocated; this
 460  * simply clears some fields, including setting the num field to NULL.
 461  * @param n  The number to clear.
 462  */
 463 void bc_num_clear(BcNum *restrict n);
 464
 465 /**
 466  * Frees @a num, which is a BcNum as a void pointer. This is a destructor.
 467  * @param num  The BcNum to free as a void pointer.
 468  */
 469 void bc_num_free(void *num);
 470
 471 /**
 472  * Returns the scale of @a n.
 473  * @param n  The number.
 474  * @return   The scale of @a n.
 475  */
 476 size_t bc_num_scale(const BcNum *restrict n);
 477
 478 /**
 479  * Returns the length (in decimal digits) of @a n. This is complicated. First,
 480  * if the number is zero, we always return at least one, but we also return the
 481  * scale if it exists. Then, If it is not zero, it opens a whole other can of
 482  * worms. Read the comments in the definition.
 483  * @param n  The number.
 484  * @return   The length of @a n.
 485  */
 486 size_t bc_num_len(const BcNum *restrict n);
 487
 488 /**
 489  * Convert a number to a BcBigDig (hardware integer). This version does error
 490  * checking, and if it finds an error, throws it. Otherwise, it calls
 491  * bc_num_bigdig2().
 492  * @param n  The number to convert.
 493  * @return   The number as a hardware integer.
 494  */
 495 BcBigDig bc_num_bigdig(const BcNum *restrict n);
 496
 497 /**
 498  * Convert a number to a BcBigDig (hardware integer). This version does no error
 499  * checking.
 500  * @param n  The number to convert.
 501  * @return   The number as a hardware integer.
 502  */
 503 BcBigDig bc_num_bigdig2(const BcNum *restrict n);
 504
 505 /**
 506  * Sets @a n to the value of @a val. @a n is expected to be a valid and
 507  * allocated BcNum.
 508  * @param n    The number to set.
 509  * @param val  The value to set the number to.
 510  */
 511 void bc_num_bigdig2num(BcNum *restrict n, BcBigDig val);
 512
 513 #if BC_ENABLE_EXTRA_MATH
 514
 515 /**
 516  * Generates a random arbitrary-size integer less than or equal to @a a and
 517  * returns it in @a b. This implements irand().
 518  * @param a    The limit for the integer to generate.
 519  * @param b    The return value.
 520  * @param rng  The pseudo-random number generator.
 521  */
 522 void bc_num_irand(BcNum *restrict a, BcNum *restrict b,
 523                   struct BcRNG *restrict rng);
 524
 525 /**
 526  * Sets the seed for the PRNG @a rng from @a n.
 527  * @param n    The new seed for the PRNG.
 528  * @param rng  The PRNG to set the seed for.
 529  */
 530 void bc_num_rng(const BcNum *restrict n, struct BcRNG *rng);
 531
 532 /**
 533  * Sets @a n to the value produced by the PRNG. This implements rand().
 534  * @param n    The number to set.
 535  * @param rng  The pseudo-random number generator.
 536  */
 537 void bc_num_createFromRNG(BcNum *restrict n, struct BcRNG *rng);
 538
 539 #endif // BC_ENABLE_EXTRA_MATH
 540
 541 /**
 542  * The add function. This is a BcNumBinaryOp function.
 543  * @param a      The first parameter.
 544  * @param b      The second parameter.
 545  * @param c      The return value.
 546  * @param scale  The current scale.
 547  */
 548 void bc_num_add(BcNum *a, BcNum *b, BcNum *c, size_t scale);
 549
 550 /**
 551  * The subtract function. This is a BcNumBinaryOp function.
 552  * @param a      The first parameter.
 553  * @param b      The second parameter.
 554  * @param c      The return value.
 555  * @param scale  The current scale.
 556  */
 557 void bc_num_sub(BcNum *a, BcNum *b, BcNum *c, size_t scale);
 558
 559 /**
 560  * The multiply function.
 561  * @param a      The first parameter. This is a BcNumBinaryOp function.
 562  * @param b      The second parameter.
 563  * @param c      The return value.
 564  * @param scale  The current scale.
 565  */
 566 void bc_num_mul(BcNum *a, BcNum *b, BcNum *c, size_t scale);
 567
 568 /**
 569  * The division function.
 570  * @param a      The first parameter. This is a BcNumBinaryOp function.
 571  * @param b      The second parameter.
 572  * @param c      The return value.
 573  * @param scale  The current scale.
 574  */
 575 void bc_num_div(BcNum *a, BcNum *b, BcNum *c, size_t scale);
 576
 577 /**
 578  * The modulus function.
 579  * @param a      The first parameter. This is a BcNumBinaryOp function.
 580  * @param b      The second parameter.
 581  * @param c      The return value.
 582  * @param scale  The current scale.
 583  */
 584 void bc_num_mod(BcNum *a, BcNum *b, BcNum *c, size_t scale);
 585
 586 /**
 587  * The power function.
 588  * @param a      The first parameter. This is a BcNumBinaryOp function.
 589  * @param b      The second parameter.
 590  * @param c      The return value.
 591  * @param scale  The current scale.
 592  */
 593 void bc_num_pow(BcNum *a, BcNum *b, BcNum *c, size_t scale);
 594 #if BC_ENABLE_EXTRA_MATH
 595
 596 /**
 597  * The places function (@ operator). This is a BcNumBinaryOp function.
 598  * @param a      The first parameter.
 599  * @param b      The second parameter.
 600  * @param c      The return value.
 601  * @param scale  The current scale.
 602  */
 603 void bc_num_places(BcNum *a, BcNum *b, BcNum *c, size_t scale);
 604
 605 /**
 606  * The left shift function (<< operator). This is a BcNumBinaryOp function.
 607  * @param a      The first parameter.
 608  * @param b      The second parameter.
 609  * @param c      The return value.
 610  * @param scale  The current scale.
 611  */
 612 void bc_num_lshift(BcNum *a, BcNum *b, BcNum *c, size_t scale);
 613
 614 /**
 615  * The right shift function (>> operator). This is a BcNumBinaryOp function.
 616  * @param a      The first parameter.
 617  * @param b      The second parameter.
 618  * @param c      The return value.
 619  * @param scale  The current scale.
 620  */
 621 void bc_num_rshift(BcNum *a, BcNum *b, BcNum *c, size_t scale);
 622
 623 #endif // BC_ENABLE_EXTRA_MATH
 624
 625 /**
 626  * Square root.
 627  * @param a      The first parameter.
 628  * @param b      The return value.
 629  * @param scale  The current scale.
 630  */
 631 void bc_num_sqrt(BcNum *restrict a, BcNum *restrict b, size_t scale);
 632
 633 /**
 634  * Divsion and modulus together. This is a dc extension.
 635  * @param a      The first parameter.
 636  * @param b      The second parameter.
 637  * @param c      The first return value (quotient).
 638  * @param d      The second return value (modulus).
 639  * @param scale  The current scale.
 640  */
 641 void bc_num_divmod(BcNum *a, BcNum *b, BcNum *c, BcNum *d, size_t scale);
 642
 643 /**
 644  * A function returning the required allocation size for an addition or a
 645  * subtraction. This is a BcNumBinaryOpReq function.
 646  * @param a      The first parameter.
 647  * @param b      The second parameter.
 648  * @param scale  The current scale.
 649  * @return       The size of allocation needed for the result of add or subtract
 650  *               with @a a, @a b, and @a scale.
 651  */
 652 size_t bc_num_addReq(const BcNum* a, const BcNum* b, size_t scale);
 653
 654 /**
 655  * A function returning the required allocation size for a multiplication. This
 656  * is a BcNumBinaryOpReq function.
 657  * @param a      The first parameter.
 658  * @param b      The second parameter.
 659  * @param scale  The current scale.
 660  * @return       The size of allocation needed for the result of multiplication
 661  *               with @a a, @a b, and @a scale.
 662  */
 663 size_t bc_num_mulReq(const BcNum *a, const BcNum *b, size_t scale);
 664
 665 /**
 666  * A function returning the required allocation size for a division or modulus.
 667  * This is a BcNumBinaryOpReq function.
 668  * @param a      The first parameter.
 669  * @param b      The second parameter.
 670  * @param scale  The current scale.
 671  * @return       The size of allocation needed for the result of division or
 672  *               modulus with @a a, @a b, and @a scale.
 673  */
 674 size_t bc_num_divReq(const BcNum *a, const BcNum *b, size_t scale);
 675
 676 /**
 677  * A function returning the required allocation size for an exponentiation. This
 678  * is a BcNumBinaryOpReq function.
 679  * @param a      The first parameter.
 680  * @param b      The second parameter.
 681  * @param scale  The current scale.
 682  * @return       The size of allocation needed for the result of exponentiation
 683  *               with @a a, @a b, and @a scale.
 684  */
 685 size_t bc_num_powReq(const BcNum *a, const BcNum *b, size_t scale);
 686
 687 #if BC_ENABLE_EXTRA_MATH
 688
 689 /**
 690  * A function returning the required allocation size for a places, left shift,
 691  * or right shift. This is a BcNumBinaryOpReq function.
 692  * @param a      The first parameter.
 693  * @param b      The second parameter.
 694  * @param scale  The current scale.
 695  * @return       The size of allocation needed for the result of places, left
 696  *               shift, or right shift with @a a, @a b, and @a scale.
 697  */
 698 size_t bc_num_placesReq(const BcNum *a, const BcNum *b, size_t scale);
 699
 700 #endif // BC_ENABLE_EXTRA_MATH
 701
 702 /**
 703  * Truncate @a n *by* @a places decimal places. This only extends places *after*
 704  * the decimal point.
 705  * @param n       The number to truncate.
 706  * @param places  The number of places to truncate @a n by.
 707  */
 708 void bc_num_truncate(BcNum *restrict n, size_t places);
 709
 710 /**
 711  * Extend @a n *by* @a places decimal places. This only extends places *after*
 712  * the decimal point.
 713  * @param n       The number to truncate.
 714  * @param places  The number of places to extend @a n by.
 715  */
 716 void bc_num_extend(BcNum *restrict n, size_t places);
 717
 718 /**
 719  * Shifts @a n right by @a places decimal places. This is the workhorse of the
 720  * right shift operator, and would be static to src/num.c, except that
 721  * src/library.c uses it for efficiency when executing its frand.
 722  * @param n       The number to shift right.
 723  * @param places  The number of decimal places to shift @a n right by.
 724  */
 725 void bc_num_shiftRight(BcNum *restrict n, size_t places);
 726
 727 /**
 728  * Compare a and b and return the result of their comparison as an ssize_t.
 729  * Returns >0 if @a a is greater than @a b, <0 if @a a is less than @a b, and =0
 730  * if a == b.
 731  * @param a  The first number.
 732  * @param b  The second number.
 733  * @return   The result of the comparison.
 734  */
 735 ssize_t bc_num_cmp(const BcNum *a, const BcNum *b);
 736
 737 /**
 738  * Modular exponentiation.
 739  * @param a      The first parameter.
 740  * @param b      The second parameter.
 741  * @param c      The third parameter.
 742  * @param d      The return value.
 743  */
 744 void bc_num_modexp(BcNum *a, BcNum *b, BcNum *c, BcNum *restrict d);
 745
 746 /**
 747  * Sets @a n to zero with a scale of zero.
 748  * @param n  The number to zero.
 749  */
 750 void bc_num_zero(BcNum *restrict n);
 751
 752 /**
 753  * Sets @a n to one with a scale of zero.
 754  * @param n  The number to set to one.
 755  */
 756 void bc_num_one(BcNum *restrict n);
 757
 758 /**
 759  * An efficient function to compare @a n to zero.
 760  * @param n  The number to compare to zero.
 761  * @return   The result of the comparison.
 762  */
 763 ssize_t bc_num_cmpZero(const BcNum *n);
 764
 765 #if !defined(NDEBUG) || BC_ENABLE_LIBRARY
 766
 767 /**
 768  * Check a number string for validity and return true if it is, false otherwise.
 769  * The library needs this to check user-supplied strings, but in bc and dc, this
 770  * is only used for debug asserts because the parsers should get the numbers
 771  * parsed right, which should ensure they are always valid.
 772  * @param val  The string to check.
 773  * @return     True if the string is a valid number, false otherwise.
 774  */
 775 bool bc_num_strValid(const char *restrict val);
 776
 777 #endif // !defined(NDEBUG) || BC_ENABLE_LIBRARY
 778
 779 /**
 780  * Parses a number string into the number @a n according to @a base.
 781  * @param n     The number to set to the parsed value.
 782  * @param val   The number string to parse.
 783  * @param base  The base to parse the number string by.
 784  */
 785 void bc_num_parse(BcNum *restrict n, const char *restrict val, BcBigDig base);
 786
 787 /**
 788  * Prints the number @a n according to @a base.
 789  * @param n        The number to print.
 790  * @param base     The base to print the number by.
 791  * @param newline  True if a newline should be inserted at the end, false
 792  *                 otherwise.
 793  */
 794 void bc_num_print(BcNum *restrict n, BcBigDig base, bool newline);
 795
 796 #if !BC_ENABLE_LIBRARY
 797
 798 /**
 799  * Prints a number as a character stream.
 800  * @param n     The number to print as a character stream.
 801  */
 802 void bc_num_stream(BcNum *restrict n);
 803
 804 #endif // !BC_ENABLE_LIBRARY
 805
 806 #if BC_DEBUG_CODE
 807
 808 /**
 809  * Print a number with a label. This is a debug-only function.
 810  * @param n          The number to print.
 811  * @param name       The label to print the number with.
 812  * @param emptyline  True if there should be an empty line after the number.
 813  */
 814 void bc_num_printDebug(const BcNum *n, const char *name, bool emptyline);
 815
 816 /**
 817  * Print the limbs of @a n. This is a debug-only function.
 818  * @param n          The number to print.
 819  * @param len        The length of the number.
 820  * @param emptyline  True if there should be an empty line after the number.
 821  */
 822 void bc_num_printDigs(const BcDig* n, size_t len, bool emptyline);
 823
 824 /**
 825  * Print debug info about @a n along with its limbs.
 826  * @param n          The number to print.
 827  * @param name       The label to print the number with.
 828  * @param emptyline  True if there should be an empty line after the number.
 829  */
 830 void bc_num_printWithDigs(const BcNum *n, const char *name, bool emptyline);
 831
 832 /**
 833  * Dump debug info about a BcNum variable.
 834  * @param varname  The variable name.
 835  * @param n        The number.
 836  */
 837 void bc_num_dump(const char *varname, const BcNum *n);
 838
 839 #endif // BC_DEBUG_CODE
 840
 841 /// A reference to an array of hex digits for easy conversion for printing.
 842 extern const char bc_num_hex_digits[];
 843
 844 /// An array of powers of 10 for easy conversion from number of digits to
 845 //powers.
 846 extern const BcBigDig bc_num_pow10[BC_BASE_DIGS + 1];
 847
 848 /// A reference to a constant array that is the max of a BigDig.
 849 extern const BcDig bc_num_bigdigMax[];
 850
 851 /// A reference to a constant size of the above array.
 852 extern const size_t bc_num_bigdigMax_size;
 853
 854 /// A reference to a constant array that is 2 times the max of a BigDig.
 855 extern const BcDig bc_num_bigdigMax2[];
 856
 857 /// A reference to a constant size of the above array.
 858 extern const size_t bc_num_bigdigMax2_size;
 859
 860 #endif // BC_NUM_H