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) ((n)->rdx = (((v) << 1) | (neg))) 263 264 /** 265 * Returns true if the rdx and scale for @a n match. 266 * @param n The number to test. 267 * @return True if the rdx and scale of @a n match, false otherwise. 268 */ 269 #define BC_NUM_RDX_VALID(n) \ 270 (BC_NUM_ZERO(n) || BC_NUM_RDX_VAL(n) * BC_BASE_DIGS >= (n)->scale) 271 272 /** 273 * Returns true if the rdx and scale for @a n match, where @a n is not a 274 * pointer. 275 * @param n The number to test. 276 * @return True if the rdx and scale of @a n match, false otherwise. 277 */ 278 #define BC_NUM_RDX_VALID_NP(n) \ 279 ((!(n).len) || BC_NUM_RDX_VAL_NP(n) * BC_BASE_DIGS >= (n).scale) 280 281 /** 282 * Returns true if @a n is negative, false otherwise. 283 * @param n The number to test. 284 * @return True if @a n is negative, false otherwise. 285 */ 286 #define BC_NUM_NEG(n) ((n)->rdx & ((BcBigDig) 1)) 287 288 /** 289 * Returns true if @a n is negative, false otherwise, where @a n is not a 290 * pointer. 291 * @param n The number to test. 292 * @return True if @a n is negative, false otherwise. 293 */ 294 #define BC_NUM_NEG_NP(n) ((n).rdx & ((BcBigDig) 1)) 295 296 /** 297 * Clears the negative bit on @a n. 298 * @param n The number. 299 */ 300 #define BC_NUM_NEG_CLR(n) ((n)->rdx &= ~((BcBigDig) 1)) 301 302 /** 303 * Clears the negative bit on @a n, where @a n is not a pointer. 304 * @param n The number. 305 */ 306 #define BC_NUM_NEG_CLR_NP(n) ((n).rdx &= ~((BcBigDig) 1)) 307 308 /** 309 * Sets the negative bit on @a n. 310 * @param n The number. 311 */ 312 #define BC_NUM_NEG_SET(n) ((n)->rdx |= ((BcBigDig) 1)) 313 314 /** 315 * Toggles the negative bit on @a n. 316 * @param n The number. 317 */ 318 #define BC_NUM_NEG_TGL(n) ((n)->rdx ^= ((BcBigDig) 1)) 319 320 /** 321 * Toggles the negative bit on @a n, where @a n is not a pointer. 322 * @param n The number. 323 */ 324 #define BC_NUM_NEG_TGL_NP(n) ((n).rdx ^= ((BcBigDig) 1)) 325 326 /** 327 * Returns the rdx val for @a n if the negative bit is set to @a v. 328 * @param n The number. 329 * @param v The value for the negative bit. 330 * @return The value of the rdx of @a n if the negative bit were set to @a v. 331 */ 332 #define BC_NUM_NEG_VAL(n, v) (((n)->rdx & ~((BcBigDig) 1)) | (v)) 333 334 /** 335 * Returns the rdx val for @a n if the negative bit is set to @a v, where @a n 336 * is not a pointer. 337 * @param n The number. 338 * @param v The value for the negative bit. 339 * @return The value of the rdx of @a n if the negative bit were set to @a v. 340 */ 341 #define BC_NUM_NEG_VAL_NP(n, v) (((n).rdx & ~((BcBigDig) 1)) | (v)) 342 343 /** 344 * Returns the size, in bytes, of limb array with @a n limbs. 345 * @param n The number. 346 * @return The size, in bytes, of a limb array with @a n limbs. 347 */ 348 #define BC_NUM_SIZE(n) ((n) * sizeof(BcDig)) 349 350 // These are for debugging only. 351 #if BC_DEBUG_CODE 352 #define BC_NUM_PRINT(x) fprintf(stderr, "%s = %lu\n", #x, (unsigned long) (x)) 353 #define DUMP_NUM bc_num_dump 354 #else // BC_DEBUG_CODE 355 #undef DUMP_NUM 356 #define DUMP_NUM(x, y) 357 #define BC_NUM_PRINT(x) 358 #endif // BC_DEBUG_CODE 359 360 /** 361 * A function type for binary operators. 362 * @param a The first parameter. 363 * @param b The second parameter. 364 * @param c The return value. 365 * @param scale The current scale. 366 */ 367 typedef void (*BcNumBinaryOp)(BcNum* a, BcNum* b, BcNum* c, size_t scale); 368 369 /** 370 * A function type for binary operators *after* @a c has been properly 371 * allocated. At this point, *nothing* should be pointing to @a c (in any way 372 * that matters, anyway). 373 * @param a The first operand. 374 * @param b The second operand. 375 * @param c The return parameter. 376 * @param scale The current scale. 377 */ 378 typedef void (*BcNumBinOp)(BcNum* a, BcNum* b, BcNum* restrict c, size_t scale); 379 380 /** 381 * A function type for getting the allocation size needed for a binary operator. 382 * Any function used for this *must* return enough space for *all* possible 383 * invocations of the operator. 384 * @param a The first parameter. 385 * @param b The second parameter. 386 * @param scale The current scale. 387 * @return The size of allocation needed for the result of the operator 388 * with @a a, @a b, and @a scale. 389 */ 390 typedef size_t (*BcNumBinaryOpReq)(const BcNum* a, const BcNum* b, 391 size_t scale); 392 393 /** 394 * A function type for printing a "digit." Functions of this type will print one 395 * digit in a number. Digits are printed differently based on the base, which is 396 * why there is more than one implementation of this function type. 397 * @param n The "digit" to print. 398 * @param len The "length" of the digit, or number of characters that will 399 * need to be printed for the digit. 400 * @param rdx True if a decimal (radix) point should be printed. 401 * @param bslash True if a backslash+newline should be printed if the character 402 * limit for the line is reached, false otherwise. 403 */ 404 typedef void (*BcNumDigitOp)(size_t n, size_t len, bool rdx, bool bslash); 405 406 /** 407 * A function type to run an operator on @a a and @a b and store the result in 408 * @a a. This is used in karatsuba for faster adds and subtracts at the end. 409 * @param a The first parameter and return value. 410 * @param b The second parameter. 411 * @param len The minimum length of both arrays. 412 */ 413 typedef void (*BcNumShiftAddOp)(BcDig* restrict a, const BcDig* restrict b, 414 size_t len); 415 416 /** 417 * Initializes @a n with @a req limbs in its array. 418 * @param n The number to initialize. 419 * @param req The number of limbs @a n must have in its limb array. 420 */ 421 void 422 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 433 bc_num_setup(BcNum* restrict n, BcDig* restrict num, size_t cap); 434 435 /** 436 * Copies @a s into @a d. This does a deep copy and requires that @a d is 437 * already a valid and allocated BcNum. 438 * @param d The destination BcNum. 439 * @param s The source BcNum. 440 */ 441 void 442 bc_num_copy(BcNum* d, const BcNum* s); 443 444 /** 445 * Creates @a d and copies @a s into @a d. This does a deep copy and requires 446 * that @a d is *not* a valid or allocated BcNum. 447 * @param d The destination BcNum. 448 * @param s The source BcNum. 449 */ 450 void 451 bc_num_createCopy(BcNum* d, const BcNum* s); 452 453 /** 454 * Creates (initializes) @a n and sets its value to the equivalent of @a val. 455 * @a n must *not* be a valid or preallocated BcNum. 456 * @param n The number to initialize and set. 457 * @param val The value to set @a n's value to. 458 */ 459 void 460 bc_num_createFromBigdig(BcNum* restrict n, BcBigDig val); 461 462 /** 463 * Makes @a n valid for holding strings. @a n must *not* be allocated; this 464 * simply clears some fields, including setting the num field to NULL. 465 * @param n The number to clear. 466 */ 467 void 468 bc_num_clear(BcNum* restrict n); 469 470 /** 471 * Frees @a num, which is a BcNum as a void pointer. This is a destructor. 472 * @param num The BcNum to free as a void pointer. 473 */ 474 void 475 bc_num_free(void* num); 476 477 /** 478 * Returns the scale of @a n. 479 * @param n The number. 480 * @return The scale of @a n. 481 */ 482 size_t 483 bc_num_scale(const BcNum* restrict n); 484 485 /** 486 * Returns the length (in decimal digits) of @a n. This is complicated. First, 487 * if the number is zero, we always return at least one, but we also return the 488 * scale if it exists. Then, If it is not zero, it opens a whole other can of 489 * worms. Read the comments in the definition. 490 * @param n The number. 491 * @return The length of @a n. 492 */ 493 size_t 494 bc_num_len(const BcNum* restrict n); 495 496 /** 497 * Convert a number to a BcBigDig (hardware integer). This version does error 498 * checking, and if it finds an error, throws it. Otherwise, it calls 499 * bc_num_bigdig2(). 500 * @param n The number to convert. 501 * @return The number as a hardware integer. 502 */ 503 BcBigDig 504 bc_num_bigdig(const BcNum* restrict n); 505 506 /** 507 * Convert a number to a BcBigDig (hardware integer). This version does no error 508 * checking. 509 * @param n The number to convert. 510 * @return The number as a hardware integer. 511 */ 512 BcBigDig 513 bc_num_bigdig2(const BcNum* restrict n); 514 515 /** 516 * Sets @a n to the value of @a val. @a n is expected to be a valid and 517 * allocated BcNum. 518 * @param n The number to set. 519 * @param val The value to set the number to. 520 */ 521 void 522 bc_num_bigdig2num(BcNum* restrict n, BcBigDig val); 523 524 #if BC_ENABLE_EXTRA_MATH 525 526 /** 527 * Generates a random arbitrary-size integer less than or equal to @a a and 528 * returns it in @a b. This implements irand(). 529 * @param a The limit for the integer to generate. 530 * @param b The return value. 531 * @param rng The pseudo-random number generator. 532 */ 533 void 534 bc_num_irand(BcNum* restrict a, BcNum* restrict b, struct BcRNG* restrict rng); 535 536 /** 537 * Sets the seed for the PRNG @a rng from @a n. 538 * @param n The new seed for the PRNG. 539 * @param rng The PRNG to set the seed for. 540 */ 541 void 542 bc_num_rng(const BcNum* restrict n, struct BcRNG* rng); 543 544 /** 545 * Sets @a n to the value produced by the PRNG. This implements rand(). 546 * @param n The number to set. 547 * @param rng The pseudo-random number generator. 548 */ 549 void 550 bc_num_createFromRNG(BcNum* restrict n, struct BcRNG* rng); 551 552 #endif // BC_ENABLE_EXTRA_MATH 553 554 /** 555 * The add function. This is a BcNumBinaryOp function. 556 * @param a The first parameter. 557 * @param b The second parameter. 558 * @param c The return value. 559 * @param scale The current scale. 560 */ 561 void 562 bc_num_add(BcNum* a, BcNum* b, BcNum* c, size_t scale); 563 564 /** 565 * The subtract function. This is a BcNumBinaryOp function. 566 * @param a The first parameter. 567 * @param b The second parameter. 568 * @param c The return value. 569 * @param scale The current scale. 570 */ 571 void 572 bc_num_sub(BcNum* a, BcNum* b, BcNum* c, size_t scale); 573 574 /** 575 * The multiply function. 576 * @param a The first parameter. This is a BcNumBinaryOp function. 577 * @param b The second parameter. 578 * @param c The return value. 579 * @param scale The current scale. 580 */ 581 void 582 bc_num_mul(BcNum* a, BcNum* b, BcNum* c, size_t scale); 583 584 /** 585 * The division function. 586 * @param a The first parameter. This is a BcNumBinaryOp function. 587 * @param b The second parameter. 588 * @param c The return value. 589 * @param scale The current scale. 590 */ 591 void 592 bc_num_div(BcNum* a, BcNum* b, BcNum* c, size_t scale); 593 594 /** 595 * The modulus function. 596 * @param a The first parameter. This is a BcNumBinaryOp function. 597 * @param b The second parameter. 598 * @param c The return value. 599 * @param scale The current scale. 600 */ 601 void 602 bc_num_mod(BcNum* a, BcNum* b, BcNum* c, size_t scale); 603 604 /** 605 * The power function. 606 * @param a The first parameter. This is a BcNumBinaryOp function. 607 * @param b The second parameter. 608 * @param c The return value. 609 * @param scale The current scale. 610 */ 611 void 612 bc_num_pow(BcNum* a, BcNum* b, BcNum* c, size_t scale); 613 #if BC_ENABLE_EXTRA_MATH 614 615 /** 616 * The places function (@ operator). This is a BcNumBinaryOp function. 617 * @param a The first parameter. 618 * @param b The second parameter. 619 * @param c The return value. 620 * @param scale The current scale. 621 */ 622 void 623 bc_num_places(BcNum* a, BcNum* b, BcNum* c, size_t scale); 624 625 /** 626 * The left shift function (<< operator). This is a BcNumBinaryOp function. 627 * @param a The first parameter. 628 * @param b The second parameter. 629 * @param c The return value. 630 * @param scale The current scale. 631 */ 632 void 633 bc_num_lshift(BcNum* a, BcNum* b, BcNum* c, size_t scale); 634 635 /** 636 * The right shift function (>> operator). This is a BcNumBinaryOp function. 637 * @param a The first parameter. 638 * @param b The second parameter. 639 * @param c The return value. 640 * @param scale The current scale. 641 */ 642 void 643 bc_num_rshift(BcNum* a, BcNum* b, BcNum* c, size_t scale); 644 645 #endif // BC_ENABLE_EXTRA_MATH 646 647 /** 648 * Square root. 649 * @param a The first parameter. 650 * @param b The return value. 651 * @param scale The current scale. 652 */ 653 void 654 bc_num_sqrt(BcNum* restrict a, BcNum* restrict b, size_t scale); 655 656 /** 657 * Divsion and modulus together. This is a dc extension. 658 * @param a The first parameter. 659 * @param b The second parameter. 660 * @param c The first return value (quotient). 661 * @param d The second return value (modulus). 662 * @param scale The current scale. 663 */ 664 void 665 bc_num_divmod(BcNum* a, BcNum* b, BcNum* c, BcNum* d, size_t scale); 666 667 /** 668 * A function returning the required allocation size for an addition or a 669 * subtraction. This is a BcNumBinaryOpReq function. 670 * @param a The first parameter. 671 * @param b The second parameter. 672 * @param scale The current scale. 673 * @return The size of allocation needed for the result of add or subtract 674 * with @a a, @a b, and @a scale. 675 */ 676 size_t 677 bc_num_addReq(const BcNum* a, const BcNum* b, size_t scale); 678 679 /** 680 * A function returning the required allocation size for a multiplication. This 681 * is a BcNumBinaryOpReq function. 682 * @param a The first parameter. 683 * @param b The second parameter. 684 * @param scale The current scale. 685 * @return The size of allocation needed for the result of multiplication 686 * with @a a, @a b, and @a scale. 687 */ 688 size_t 689 bc_num_mulReq(const BcNum* a, const BcNum* b, size_t scale); 690 691 /** 692 * A function returning the required allocation size for a division or modulus. 693 * This is a BcNumBinaryOpReq function. 694 * @param a The first parameter. 695 * @param b The second parameter. 696 * @param scale The current scale. 697 * @return The size of allocation needed for the result of division or 698 * modulus with @a a, @a b, and @a scale. 699 */ 700 size_t 701 bc_num_divReq(const BcNum* a, const BcNum* b, size_t scale); 702 703 /** 704 * A function returning the required allocation size for an exponentiation. This 705 * is a BcNumBinaryOpReq function. 706 * @param a The first parameter. 707 * @param b The second parameter. 708 * @param scale The current scale. 709 * @return The size of allocation needed for the result of exponentiation 710 * with @a a, @a b, and @a scale. 711 */ 712 size_t 713 bc_num_powReq(const BcNum* a, const BcNum* b, size_t scale); 714 715 #if BC_ENABLE_EXTRA_MATH 716 717 /** 718 * A function returning the required allocation size for a places, left shift, 719 * or right shift. This is a BcNumBinaryOpReq function. 720 * @param a The first parameter. 721 * @param b The second parameter. 722 * @param scale The current scale. 723 * @return The size of allocation needed for the result of places, left 724 * shift, or right shift with @a a, @a b, and @a scale. 725 */ 726 size_t 727 bc_num_placesReq(const BcNum* a, const BcNum* b, size_t scale); 728 729 #endif // BC_ENABLE_EXTRA_MATH 730 731 /** 732 * Truncate @a n *by* @a places decimal places. This only extends places *after* 733 * the decimal point. 734 * @param n The number to truncate. 735 * @param places The number of places to truncate @a n by. 736 */ 737 void 738 bc_num_truncate(BcNum* restrict n, size_t places); 739 740 /** 741 * Extend @a n *by* @a places decimal places. This only extends places *after* 742 * the decimal point. 743 * @param n The number to truncate. 744 * @param places The number of places to extend @a n by. 745 */ 746 void 747 bc_num_extend(BcNum* restrict n, size_t places); 748 749 /** 750 * Shifts @a n right by @a places decimal places. This is the workhorse of the 751 * right shift operator, and would be static to src/num.c, except that 752 * src/library.c uses it for efficiency when executing its frand. 753 * @param n The number to shift right. 754 * @param places The number of decimal places to shift @a n right by. 755 */ 756 void 757 bc_num_shiftRight(BcNum* restrict n, size_t places); 758 759 /** 760 * Compare a and b and return the result of their comparison as an ssize_t. 761 * Returns >0 if @a a is greater than @a b, <0 if @a a is less than @a b, and =0 762 * if a == b. 763 * @param a The first number. 764 * @param b The second number. 765 * @return The result of the comparison. 766 */ 767 ssize_t 768 bc_num_cmp(const BcNum* a, const BcNum* b); 769 770 /** 771 * Modular exponentiation. 772 * @param a The first parameter. 773 * @param b The second parameter. 774 * @param c The third parameter. 775 * @param d The return value. 776 */ 777 void 778 bc_num_modexp(BcNum* a, BcNum* b, BcNum* c, BcNum* restrict d); 779 780 /** 781 * Sets @a n to zero with a scale of zero. 782 * @param n The number to zero. 783 */ 784 void 785 bc_num_zero(BcNum* restrict n); 786 787 /** 788 * Sets @a n to one with a scale of zero. 789 * @param n The number to set to one. 790 */ 791 void 792 bc_num_one(BcNum* restrict n); 793 794 /** 795 * An efficient function to compare @a n to zero. 796 * @param n The number to compare to zero. 797 * @return The result of the comparison. 798 */ 799 ssize_t 800 bc_num_cmpZero(const BcNum* n); 801 802 /** 803 * Check a number string for validity and return true if it is, false otherwise. 804 * The library needs this to check user-supplied strings, but in bc and dc, this 805 * is only used for debug asserts because the parsers should get the numbers 806 * parsed right, which should ensure they are always valid. 807 * @param val The string to check. 808 * @return True if the string is a valid number, false otherwise. 809 */ 810 bool 811 bc_num_strValid(const char* restrict val); 812 813 /** 814 * Parses a number string into the number @a n according to @a base. 815 * @param n The number to set to the parsed value. 816 * @param val The number string to parse. 817 * @param base The base to parse the number string by. 818 */ 819 void 820 bc_num_parse(BcNum* restrict n, const char* restrict val, BcBigDig base); 821 822 /** 823 * Prints the number @a n according to @a base. 824 * @param n The number to print. 825 * @param base The base to print the number by. 826 * @param newline True if a newline should be inserted at the end, false 827 * otherwise. 828 */ 829 void 830 bc_num_print(BcNum* restrict n, BcBigDig base, bool newline); 831 832 #if !BC_ENABLE_LIBRARY 833 834 /** 835 * Prints a number as a character stream. 836 * @param n The number to print as a character stream. 837 */ 838 void 839 bc_num_stream(BcNum* restrict n); 840 841 #endif // !BC_ENABLE_LIBRARY 842 843 #if BC_DEBUG_CODE 844 845 /** 846 * Print a number with a label. This is a debug-only function. 847 * @param n The number to print. 848 * @param name The label to print the number with. 849 * @param emptyline True if there should be an empty line after the number. 850 */ 851 void 852 bc_num_printDebug(const BcNum* n, const char* name, bool emptyline); 853 854 /** 855 * Print the limbs of @a n. This is a debug-only function. 856 * @param n The number to print. 857 * @param len The length of the number. 858 * @param emptyline True if there should be an empty line after the number. 859 */ 860 void 861 bc_num_printDigs(const BcDig* n, size_t len, bool emptyline); 862 863 /** 864 * Print debug info about @a n along with its limbs. 865 * @param n The number to print. 866 * @param name The label to print the number with. 867 * @param emptyline True if there should be an empty line after the number. 868 */ 869 void 870 bc_num_printWithDigs(const BcNum* n, const char* name, bool emptyline); 871 872 /** 873 * Dump debug info about a BcNum variable. 874 * @param varname The variable name. 875 * @param n The number. 876 */ 877 void 878 bc_num_dump(const char* varname, const BcNum* n); 879 880 #endif // BC_DEBUG_CODE 881 882 /// A reference to an array of hex digits for easy conversion for printing. 883 extern const char bc_num_hex_digits[]; 884 885 /// An array of powers of 10 for easy conversion from number of digits to 886 /// powers. 887 extern const BcBigDig bc_num_pow10[BC_BASE_DIGS + 1]; 888 889 /// A reference to a constant array that is the max of a BigDig. 890 extern const BcDig bc_num_bigdigMax[]; 891 892 /// A reference to a constant size of the above array. 893 extern const size_t bc_num_bigdigMax_size; 894 895 /// A reference to a constant array that is 2 times the max of a BigDig. 896 extern const BcDig bc_num_bigdigMax2[]; 897 898 /// A reference to a constant size of the above array. 899 extern const size_t bc_num_bigdigMax2_size; 900 901 #endif // BC_NUM_H 902