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