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