diff options
author | Gavin Howard <gavin@yzena.com> | 2021-07-11 00:20:25 -0600 |
---|---|---|
committer | Gavin Howard <gavin@yzena.com> | 2021-07-11 00:20:25 -0600 |
commit | 70ae81a06c32c7b525d26e4cfc4d21a4f5052a63 (patch) | |
tree | 663e947edeb03152a19586f87358e8876dead94f /include | |
parent | 701068c5a5ae6dc91cf3fc4b4c34223649674798 (diff) | |
download | platform_external_bc-70ae81a06c32c7b525d26e4cfc4d21a4f5052a63.tar.gz platform_external_bc-70ae81a06c32c7b525d26e4cfc4d21a4f5052a63.tar.bz2 platform_external_bc-70ae81a06c32c7b525d26e4cfc4d21a4f5052a63.zip |
Do a lot of documentation work
Signed-off-by: Gavin Howard <gavin@yzena.com>
Diffstat (limited to 'include')
-rw-r--r-- | include/num.h | 621 | ||||
-rw-r--r-- | include/opt.h | 57 | ||||
-rw-r--r-- | include/parse.h | 72 | ||||
-rw-r--r-- | include/program.h | 249 | ||||
-rw-r--r-- | include/rand.h | 310 | ||||
-rw-r--r-- | include/read.h | 6 | ||||
-rw-r--r-- | include/version.h | 2 |
7 files changed, 1278 insertions, 39 deletions
diff --git a/include/num.h b/include/num.h index b532639b..eb9f73d2 100644 --- a/include/num.h +++ b/include/num.h @@ -51,48 +51,89 @@ #define BC_ENABLE_EXTRA_MATH (1) #endif // BC_ENABLE_EXTRA_MATH +/// Everything in bc is base 10.. #define BC_BASE (10) +/// Alias. typedef unsigned long ulong; +/// This is here because BcBigDig came first, but when I created bcl, it's +/// definition has to be defined first. typedef BclBigDig BcBigDig; #if BC_LONG_BIT >= 64 +/// The biggest number held by a BcBigDig. #define BC_NUM_BIGDIG_MAX ((BcBigDig) UINT64_MAX) +/// The number of decimal digits in one limb. #define BC_BASE_DIGS (9) + +/// The max number + 1 that one limb can hold. #define BC_BASE_POW (1000000000) +/// An alias for portability. #define BC_NUM_BIGDIG_C UINT64_C +/// The actual limb type. typedef int_least32_t BcDig; #elif BC_LONG_BIT >= 32 +/// The biggest number held by a BcBigDig. #define BC_NUM_BIGDIG_MAX ((BcBigDig) UINT32_MAX) +/// The number of decimal digits in one limb. #define BC_BASE_DIGS (4) + +/// The max number + 1 that one limb can hold. #define BC_BASE_POW (10000) +/// An alias for portability. #define BC_NUM_BIGDIG_C UINT32_C +/// The actual limb type. typedef int_least16_t BcDig; #else +/// LONG_BIT must be at least 32 on POSIX. We depend on that. #error BC_LONG_BIT must be at least 32 #endif // BC_LONG_BIT >= 64 +/// The default (and minimum) number of limbs when allocating a number. #define BC_NUM_DEF_SIZE (8) +/// The actual number struct. This is where the magic happens. typedef struct BcNum { + + /// The limb array. It is restrict because *no* other item should own the + /// array. For more information, see the development manual + /// (manuals/development.md#numbers). BcDig *restrict num; + + /// The number of limbs before the decimal (radix) point. This also stores + /// the negative bit in the least significant bit since it uses at least two + /// bits less than scale. It is also used less than scale. See the + /// development manual (manuals/development.md#numbers) for more info. size_t rdx; + + /// The actual scale of the number. This is different from rdx because there + /// are multiple digits in one limb, and in the last limb, only some of the + /// digits may be part of the scale. However, scale must always match rdx + /// (except when the number is 0), or there is a bug. For more information, + /// see the development manual (manuals/development.md#numbers). size_t scale; + + /// The number of valid limbs in the array. If this is 0, then the number is + /// 0 as well. size_t len; + + /// The capacity of the limbs array. This is how many limbs the number could + /// expand to without reallocation. size_t cap; + } BcNum; #if BC_ENABLE_EXTRA_MATH @@ -108,13 +149,25 @@ struct BcRNG; #endif // BC_ENABLE_EXTRA_MATH +/// The minimum obase. #define BC_NUM_MIN_BASE (BC_NUM_BIGDIG_C(2)) + +/// The maximum ibase allowed by POSIX. #define BC_NUM_MAX_POSIX_IBASE (BC_NUM_BIGDIG_C(16)) + +/// The actual ibase supported by this implementation. #define BC_NUM_MAX_IBASE (BC_NUM_BIGDIG_C(36)) -// This is the max base allowed by bc_num_parseChar(). + +/// The max base allowed by bc_num_parseChar(). #define BC_NUM_MAX_LBASE (BC_NUM_BIGDIG_C('Z' + BC_BASE + 1)) + +/// The default number of characters to print before a backslash newline. #define BC_NUM_PRINT_WIDTH (BC_NUM_BIGDIG_C(69)) +/// The base for printing streams from numbers. +#define BC_NUM_STREAM_BASE (256) + +// This sets a default for the Karatsuba length. #ifndef BC_NUM_KARATSUBA_LEN #define BC_NUM_KARATSUBA_LEN (BC_NUM_BIGDIG_C(32)) #elif BC_NUM_KARATSUBA_LEN < 16 @@ -125,43 +178,183 @@ struct BcRNG; // the size required for ibase and obase BcNum's. #define BC_NUM_BIGDIG_LOG10 (BC_NUM_DEF_SIZE) +/** + * Returns non-zero if the BcNum @a n is non-zero. + * @param n The number to test. + * @return Non-zero if @a n is non-zero, zero otherwise. + */ #define BC_NUM_NONZERO(n) ((n)->len) + +/** + * Returns true if the BcNum @a n is zero. + * @param n The number to test. + * @return True if @a n is zero, false otherwise. + */ #define BC_NUM_ZERO(n) (!BC_NUM_NONZERO(n)) + +/** + * Returns true if the BcNum @a n is one with no scale. + * @param n The number to test. + * @return True if @a n equals 1 with no scale, false otherwise. + */ #define BC_NUM_ONE(n) ((n)->len == 1 && (n)->rdx == 0 && (n)->num[0] == 1) +/** + * Converts the letter @a c into a number. + * @param c The letter to convert. + * @return The number corresponding to the letter. + */ #define BC_NUM_NUM_LETTER(c) ((c) - 'A' + BC_BASE) +/// The number of allocations done by bc_num_k(). If you change the number of +/// allocations, you must change this. This is done in order to allocate them +/// all as one allocation and just give them all pointers to different parts. +/// Works pretty well, but you have to be careful. #define BC_NUM_KARATSUBA_ALLOCS (6) +/** + * Rounds @a s (scale) up to the next power of BC_BASE_DIGS. This also check for + * overflow and gives a fatal error if that happens because we just can't go + * over the limits we have imposed. + * @param s The scale to round up. + * @return @a s rounded up to the next power of BC_BASE_DIGS. + */ #define BC_NUM_ROUND_POW(s) (bc_vm_growSize((s), BC_BASE_DIGS - 1)) + +/** + * Returns the equivalent rdx for the scale @a s. + * @param s The scale to convert. + * @return The rdx for @a s. + */ #define BC_NUM_RDX(s) (BC_NUM_ROUND_POW(s) / BC_BASE_DIGS) +/** + * Returns the actual rdx of @a n. (It removes the negative bit.) + * @param n The number. + * @return The real rdx of @a n. + */ #define BC_NUM_RDX_VAL(n) ((n)->rdx >> 1) + +/** + * Returns the actual rdx of @a n, where @a n is not a pointer. (It removes the + * negative bit.) + * @param n The number. + * @return The real rdx of @a n. + */ #define BC_NUM_RDX_VAL_NP(n) ((n).rdx >> 1) + +/** + * Sets the rdx of @a n to @a v. + * @param n The number. + * @param v The value to set the rdx to. + */ #define BC_NUM_RDX_SET(n, v) \ ((n)->rdx = (((v) << 1) | ((n)->rdx & (BcBigDig) 1))) + +/** + * Sets the rdx of @a n to @a v, where @a n is not a pointer. + * @param n The number. + * @param v The value to set the rdx to. + */ #define BC_NUM_RDX_SET_NP(n, v) \ ((n).rdx = (((v) << 1) | ((n).rdx & (BcBigDig) 1))) + +/** + * Sets the rdx of @a n to @a v and the negative bit to @a neg. + * @param n The number. + * @param v The value to set the rdx to. + * @param neg The value to set the negative bit to. + */ #define BC_NUM_RDX_SET_NEG(n, v, neg) \ ((n)->rdx = (((v) << 1) | (neg))) +/** + * Returns true if the rdx and scale for @a n match. + * @param n The number to test. + * @return True if the rdx and scale of @a n match, false otherwise. + */ #define BC_NUM_RDX_VALID(n) \ (BC_NUM_ZERO(n) || BC_NUM_RDX_VAL(n) * BC_BASE_DIGS >= (n)->scale) + +/** + * Returns true if the rdx and scale for @a n match, where @a n is not a + * pointer. + * @param n The number to test. + * @return True if the rdx and scale of @a n match, false otherwise. + */ #define BC_NUM_RDX_VALID_NP(n) \ ((!(n).len) || BC_NUM_RDX_VAL_NP(n) * BC_BASE_DIGS >= (n).scale) +/** + * Returns true if @a n is negative, false otherwise. + * @param n The number to test. + * @return True if @a n is negative, false otherwise. + */ #define BC_NUM_NEG(n) ((n)->rdx & ((BcBigDig) 1)) + +/** + * Returns true if @a n is negative, false otherwise, where @a n is not a + * pointer. + * @param n The number to test. + * @return True if @a n is negative, false otherwise. + */ #define BC_NUM_NEG_NP(n) ((n).rdx & ((BcBigDig) 1)) + +/** + * Clears the negative bit on @a n. + * @param n The number. + */ #define BC_NUM_NEG_CLR(n) ((n)->rdx &= ~((BcBigDig) 1)) + +/** + * Clears the negative bit on @a n, where @a n is not a pointer. + * @param n The number. + */ #define BC_NUM_NEG_CLR_NP(n) ((n).rdx &= ~((BcBigDig) 1)) + +/** + * Sets the negative bit on @a n. + * @param n The number. + */ #define BC_NUM_NEG_SET(n) ((n)->rdx |= ((BcBigDig) 1)) + +/** + * Toggles the negative bit on @a n. + * @param n The number. + */ #define BC_NUM_NEG_TGL(n) ((n)->rdx ^= ((BcBigDig) 1)) + +/** + * Toggles the negative bit on @a n, where @a n is not a pointer. + * @param n The number. + */ #define BC_NUM_NEG_TGL_NP(n) ((n).rdx ^= ((BcBigDig) 1)) + +/** + * Returns the rdx val for @a n if the negative bit is set to @a v. + * @param n The number. + * @param v The value for the negative bit. + * @return The value of the rdx of @a n if the negative bit were set to @a v. + */ #define BC_NUM_NEG_VAL(n, v) (((n)->rdx & ~((BcBigDig) 1)) | (v)) + +/** + * Returns the rdx val for @a n if the negative bit is set to @a v, where @a n + * is not a pointer. + * @param n The number. + * @param v The value for the negative bit. + * @return The value of the rdx of @a n if the negative bit were set to @a v. + */ #define BC_NUM_NEG_VAL_NP(n, v) (((n).rdx & ~((BcBigDig) 1)) | (v)) +/** + * Returns the size, in bytes, of limb array with @a n limbs. + * @param n The number. + * @return The size, in bytes, of a limb array with @a n limbs. + */ #define BC_NUM_SIZE(n) ((n) * sizeof(BcDig)) +// These are for debugging only. #if BC_DEBUG_CODE #define BC_NUM_PRINT(x) fprintf(stderr, "%s = %lu\n", #x, (unsigned long)(x)) #define DUMP_NUM bc_num_dump @@ -171,95 +364,505 @@ struct BcRNG; #define BC_NUM_PRINT(x) #endif // BC_DEBUG_CODE -typedef void (*BcNumBinaryOp)(BcNum*, BcNum*, BcNum*, size_t); -typedef void (*BcNumBinOp)(BcNum*, BcNum*, BcNum* restrict, size_t); -typedef size_t (*BcNumBinaryOpReq)(const BcNum*, const BcNum*, size_t); -typedef void (*BcNumDigitOp)(size_t, size_t, bool, bool); -typedef void (*BcNumShiftAddOp)(BcDig* restrict, const BcDig* restrict, size_t); +/** + * A function type for binary operators. + * @param a The first parameter. + * @param b The second parameter. + * @param c The return value. + * @param scale The current scale. + */ +typedef void (*BcNumBinaryOp)(BcNum* a, BcNum* b, BcNum* c, size_t scale); + +/** + * A function type for binary operators *after* @a c has been properly + * allocated. At this point, *nothing* should be pointing to @a c (in any way + * that matters, anyway). + * @param a The first parameter. + * @param b The second parameter. + * @param c The return value. + * @param scale The current scale. + */ +typedef void (*BcNumBinOp)(BcNum* a, BcNum* b, BcNum* restrict c, size_t scale); + +/** + * A function type for getting the allocation size needed for a binary operator. + * Any function used for this *must* return enough space for *all* possible + * invocations of the operator. + * @param a The first parameter. + * @param b The second parameter. + * @param scale The current scale. + * @return The size of allocation needed for the result of the operator + * with @a a, @a b, and @a scale. + */ +typedef size_t (*BcNumBinaryOpReq)(const BcNum* a, const BcNum* b, + size_t scale); + +/** + * A function type for printing a "digit." Functions of this type will print one + * digit in a number. Digits are printed differently based on the base, which is + * why there is more than one implementation of this function type. + * @param n The "digit" to print. + * @param len The "length" of the digit, or number of characters that will + * need to be printed for the digit. + * @param rdx True if a decimal (radix) point should be printed. + * @param bslash True if a backslash+newline should be printed if the character + * limit for the line is reached, false otherwise. + */ +typedef void (*BcNumDigitOp)(size_t n, size_t len, bool rdx, bool bslash); + +/** + * A function type to run an operator on @a a and @a b and store the result in + * @a a. This is used in karatsuba for faster adds and subtracts at the end. + * @param a The first parameter and return value. + * @param b The second parameter. + * @param len The minimum length of both arrays. + */ +typedef void (*BcNumShiftAddOp)(BcDig* restrict a, const BcDig* restrict b, + size_t len); +/** + * Initializes @a n with @a req limbs in its array. + * @param n The number to initialize. + * @param req The number of limbs @a n must have in its limb array. + */ void bc_num_init(BcNum *restrict n, size_t req); + +/** + * Initializes (sets up) @a n with the preallocated limb array @a num that has + * size @a cap. This is called by @a bc_num_init(), but it is also used by parts + * of bc that use statically allocated limb arrays. + * @param n The number to initialize. + * @param num The preallocated limb array. + * @param cap The capacity of @a num. + */ void bc_num_setup(BcNum *restrict n, BcDig *restrict num, size_t cap); + +/** + * Copies @a s into @a d. This does a deep copy and requires that @a d is + * already a valid and allocated BcNum. + * @param d The destination BcNum. + * @param s The source BcNum. + */ void bc_num_copy(BcNum *d, const BcNum *s); + +/** + * Creates @a d and copies @a s into @a d. This does a deep copy and requires + * that @a d is *not* a valid or allocated BcNum. + * @param d The destination BcNum. + * @param s The source BcNum. + */ void bc_num_createCopy(BcNum *d, const BcNum *s); -void bc_num_createFromBigdig(BcNum *n, BcBigDig val); + +/** + * Creates (initializes) @a n and sets its value to the equivalent of @a val. + * @a n must *not* be a valid or preallocated BcNum. + * @param n The number to initialize and set. + * @param val The value to set @a n's value to. + */ +void bc_num_createFromBigdig(BcNum *restrict n, BcBigDig val); + +/** + * Makes @a n valid for holding strings. @a n must *not* be allocated; this + * simply clears some fields, including setting the num field to NULL. + * @param n The number to clear. + */ void bc_num_clear(BcNum *restrict n); + +/** + * Frees @a num, which is a BcNum as a void pointer. This is a destructor. + * @param num The BcNum to free as a void pointer. + */ void bc_num_free(void *num); +/** + * Returns the scale of @a n. + * @param n The number. + * @return The scale of @a n. + */ size_t bc_num_scale(const BcNum *restrict n); + +/** + * Returns the length (in decimal digits) of @a n. This is complicated. First, + * if the number is zero, we always return at least one, but we also return the + * scale if it exists. Then, If it is not zero, it opens a whole other can of + * worms. Read the comments in the definition. + * @param n The number. + * @return The length of @a n. + */ size_t bc_num_len(const BcNum *restrict n); +/** + * Convert a number to a BcBigDig (hardware integer). This version does error + * checking, and if it finds an error, throws it. Otherwise, it calls + * bc_num_bigdig2(). + * @param n The number to convert. + * @return The number as a hardware integer. + */ BcBigDig bc_num_bigdig(const BcNum *restrict n); + +/** + * Convert a number to a BcBigDig (hardware integer). This version does no error + * checking. + * @param n The number to convert. + * @return The number as a hardware integer. + */ BcBigDig bc_num_bigdig2(const BcNum *restrict n); + +/** + * Sets @a n to the value of @a val. @a n is expected to be a valid and + * allocated BcNum. + * @param n The number to set. + * @param val The value to set the number to. + */ void bc_num_bigdig2num(BcNum *restrict n, BcBigDig val); #if BC_ENABLE_EXTRA_MATH && BC_ENABLE_RAND + +/** + * Generates a random arbitrary-size integer less than or equal to @a a and + * returns it in @a b. This implements irand(). + * @param a The limit for the integer to generate. + * @param b The return value. + * @param rng The pseudo-random number generator. + */ void bc_num_irand(BcNum *restrict a, BcNum *restrict b, struct BcRNG *restrict rng); + +/** + * Sets the seed for the PRNG @a rng from @a n. + * @param n The new seed for the PRNG. + * @param rng The PRNG to set the seed for. + */ void bc_num_rng(const BcNum *restrict n, struct BcRNG *rng); + +/** + * Sets @a n to the value produced by the PRNG. This implements rand(). + * @param n The number to set. + * @param rng The pseudo-random number generator. + */ void bc_num_createFromRNG(BcNum *restrict n, struct BcRNG *rng); + #endif // BC_ENABLE_EXTRA_MATH && BC_ENABLE_RAND +/** + * The add function. This is a BcNumBinaryOp function. + * @param a The first parameter. + * @param b The second parameter. + * @param c The return value. + * @param scale The current scale. + */ void bc_num_add(BcNum *a, BcNum *b, BcNum *c, size_t scale); + +/** + * The subtract function. This is a BcNumBinaryOp function. + * @param a The first parameter. + * @param b The second parameter. + * @param c The return value. + * @param scale The current scale. + */ void bc_num_sub(BcNum *a, BcNum *b, BcNum *c, size_t scale); + +/** + * The multiply function. + * @param a The first parameter. This is a BcNumBinaryOp function. + * @param b The second parameter. + * @param c The return value. + * @param scale The current scale. + */ void bc_num_mul(BcNum *a, BcNum *b, BcNum *c, size_t scale); + +/** + * The division function. + * @param a The first parameter. This is a BcNumBinaryOp function. + * @param b The second parameter. + * @param c The return value. + * @param scale The current scale. + */ void bc_num_div(BcNum *a, BcNum *b, BcNum *c, size_t scale); + +/** + * The modulus function. + * @param a The first parameter. This is a BcNumBinaryOp function. + * @param b The second parameter. + * @param c The return value. + * @param scale The current scale. + */ void bc_num_mod(BcNum *a, BcNum *b, BcNum *c, size_t scale); + +/** + * The power function. + * @param a The first parameter. This is a BcNumBinaryOp function. + * @param b The second parameter. + * @param c The return value. + * @param scale The current scale. + */ void bc_num_pow(BcNum *a, BcNum *b, BcNum *c, size_t scale); #if BC_ENABLE_EXTRA_MATH + +/** + * The places function (@ operator). This is a BcNumBinaryOp function. + * @param a The first parameter. + * @param b The second parameter. + * @param c The return value. + * @param scale The current scale. + */ void bc_num_places(BcNum *a, BcNum *b, BcNum *c, size_t scale); + +/** + * The left shift function (<< operator). This is a BcNumBinaryOp function. + * @param a The first parameter. + * @param b The second parameter. + * @param c The return value. + * @param scale The current scale. + */ void bc_num_lshift(BcNum *a, BcNum *b, BcNum *c, size_t scale); + +/** + * The right shift function (>> operator). This is a BcNumBinaryOp function. + * @param a The first parameter. + * @param b The second parameter. + * @param c The return value. + * @param scale The current scale. + */ void bc_num_rshift(BcNum *a, BcNum *b, BcNum *c, size_t scale); + #endif // BC_ENABLE_EXTRA_MATH + +/** + * Square root. + * @param a The first parameter. + * @param b The return value. + * @param scale The current scale. + */ void bc_num_sqrt(BcNum *restrict a, BcNum *restrict b, size_t scale); -void bc_num_sr(BcNum *restrict a, BcNum *restrict b, size_t scale); + +/** + * Divsion and modulus together. This is a dc extension. + * @param a The first parameter. + * @param b The second parameter. + * @param c The first return value (quotient). + * @param d The second return value (modulus). + * @param scale The current scale. + */ void bc_num_divmod(BcNum *a, BcNum *b, BcNum *c, BcNum *d, size_t scale); +/** + * A function returning the required allocation size for an addition or a + * subtraction. This is a BcNumBinaryOpReq function. + * @param a The first parameter. + * @param b The second parameter. + * @param scale The current scale. + * @return The size of allocation needed for the result of add or subtract + * with @a a, @a b, and @a scale. + */ size_t bc_num_addReq(const BcNum* a, const BcNum* b, size_t scale); +/** + * A function returning the required allocation size for a multiplication. This + * is a BcNumBinaryOpReq function. + * @param a The first parameter. + * @param b The second parameter. + * @param scale The current scale. + * @return The size of allocation needed for the result of multiplication + * with @a a, @a b, and @a scale. + */ size_t bc_num_mulReq(const BcNum *a, const BcNum *b, size_t scale); + +/** + * A function returning the required allocation size for a division or modulus. + * This is a BcNumBinaryOpReq function. + * @param a The first parameter. + * @param b The second parameter. + * @param scale The current scale. + * @return The size of allocation needed for the result of division or + * modulus with @a a, @a b, and @a scale. + */ size_t bc_num_divReq(const BcNum *a, const BcNum *b, size_t scale); + +/** + * A function returning the required allocation size for an exponentiation. This + * is a BcNumBinaryOpReq function. + * @param a The first parameter. + * @param b The second parameter. + * @param scale The current scale. + * @return The size of allocation needed for the result of exponentiation + * with @a a, @a b, and @a scale. + */ size_t bc_num_powReq(const BcNum *a, const BcNum *b, size_t scale); + #if BC_ENABLE_EXTRA_MATH + +/** + * A function returning the required allocation size for a places, left shift, + * or right shift. This is a BcNumBinaryOpReq function. + * @param a The first parameter. + * @param b The second parameter. + * @param scale The current scale. + * @return The size of allocation needed for the result of places, left + * shift, or right shift with @a a, @a b, and @a scale. + */ size_t bc_num_placesReq(const BcNum *a, const BcNum *b, size_t scale); + #endif // BC_ENABLE_EXTRA_MATH +/** + * Truncate @a n *by* @a places decimal places. + * @param n The number to truncate. + * @param places The number of places to truncate @a n by. + */ void bc_num_truncate(BcNum *restrict n, size_t places); + +/** + * Extend @a n *by* @a places decimal places. + * @param n The number to truncate. + * @param places The number of places to extend @a n by. + */ void bc_num_extend(BcNum *restrict n, size_t places); + +/** + * Shifts @a n right by @a places decimal places. This is a helper for + * bc_num_rshift(), and would be static to src/num.c, except that src/library.c + * uses it for efficiency when executing its frand. + * @param n The number to shift right. + * @param places The number of decimal places to shift @a n right by. + */ void bc_num_shiftRight(BcNum *restrict n, size_t places); +/** + * Compare a and b and return the result of their comparison as an ssize_t. + * Returns >0 if @a a is greater than @a b, <0 if @a a is less than @a b, and =0 + * if a == b. + * @param a The first number. + * @param b The second number. + * @return The result of the comparison. + */ ssize_t bc_num_cmp(const BcNum *a, const BcNum *b); #if DC_ENABLED + +/** + * Modular exponentiation. + * @param a The first parameter. + * @param b The second parameter. + * @param c The third parameter. + * @param d The return value. + */ void bc_num_modexp(BcNum *a, BcNum *b, BcNum *c, BcNum *restrict d); + #endif // DC_ENABLED +/** + * Sets @a n to zero with a scale of zero. + * @param n The number to zero. + */ void bc_num_zero(BcNum *restrict n); + +/** + * Sets @a n to one with a scale of zero. + * @param n The number to set to one. + */ void bc_num_one(BcNum *restrict n); + +/** + * An efficient function to compare @a n to zero. + * @param n The number to compare to zero. + * @return The result of the comparison. + */ ssize_t bc_num_cmpZero(const BcNum *n); #if !defined(NDEBUG) || BC_ENABLE_LIBRARY + +/** + * Check a number string for validity and return true if it is, false otherwise. + * The library needs this to check user-supplied strings, but in bc and dc, this + * is only used for debug asserts because the parsers should get the numbers + * parsed right, which should ensure they are always valid. + * @param val The string to check. + * @return True if the string is a valid number, false otherwise. + */ bool bc_num_strValid(const char *restrict val); + #endif // !defined(NDEBUG) || BC_ENABLE_LIBRARY + +/** + * Parses a number string into the number @a n according to @a base. + * @param n The number to set to the parsed value. + * @param val The number string to parse. + * @param base The base to parse the number string by. + */ void bc_num_parse(BcNum *restrict n, const char *restrict val, BcBigDig base); + +/** + * Prints the number @a n according to @a base. + * @param n The number to print. + * @param base The base to print the number by. + * @param newline True if a newline should be inserted at the end, false + * otherwise. + */ void bc_num_print(BcNum *restrict n, BcBigDig base, bool newline); + #if DC_ENABLED -void bc_num_stream(BcNum *restrict n, BcBigDig base); + +/** + * Prints a number as a character stream. + * @param n The number to print as a character stream. + */ +void bc_num_stream(BcNum *restrict n); + #endif // DC_ENABLED #if BC_DEBUG_CODE + +/** + * Print a number with a label. This is a debug-only function. + * @param n The number to print. + * @param name The label to print the number with. + * @param emptyline True if there should be an empty line after the number. + */ void bc_num_printDebug(const BcNum *n, const char *name, bool emptyline); + +/** + * Print the limbs of @a n. This is a debug-only function. + * @param n The number to print. + * @param len The length of the number. + * @param emptyline True if there should be an empty line after the number. + */ void bc_num_printDigs(const BcDig* n, size_t len, bool emptyline); + +/** + * Print debug info about @a n along with its limbs. + * @param n The number to print. + * @param name The label to print the number with. + * @param emptyline True if there should be an empty line after the number. + */ void bc_num_printWithDigs(const BcNum *n, const char *name, bool emptyline); + +/** + * Dump debug info about a BcNum variable. + * @param varname The variable name. + * @param n The number. + */ void bc_num_dump(const char *varname, const BcNum *n); + #endif // BC_DEBUG_CODE +/// A reference to an array of hex digits for easy conversion for printing. extern const char bc_num_hex_digits[]; + +/// An array of powers of 10 for easy conversion from number of digits to +//powers. extern const BcBigDig bc_num_pow10[BC_BASE_DIGS + 1]; +/// A reference to a constant array that is the max of a BigDig. extern const BcDig bc_num_bigdigMax[]; + +/// A reference to a constant size of the above array. extern const size_t bc_num_bigdigMax_size; +/// A reference to a constant array that is 2 times the max of a BigDig. extern const BcDig bc_num_bigdigMax2[]; + +/// A reference to a constant size of the above array. extern const size_t bc_num_bigdigMax2_size; #endif // BC_NUM_H diff --git a/include/opt.h b/include/opt.h index e14b8431..d9d46eba 100644 --- a/include/opt.h +++ b/include/opt.h @@ -43,37 +43,94 @@ #include <stdbool.h> #include <stdlib.h> +/// The data required to parse command-line arguments. typedef struct BcOpt { + + /// The array of arguments. char **argv; + + /// The index of the current argument. size_t optind; + + /// The actual parse option character. int optopt; + + /// Where in the option we are for multi-character single-character options. int subopt; + + /// The option argument. char *optarg; + } BcOpt; +/// The types of arguments. This is specially adapted for bc. typedef enum BcOptType { + + /// No argument required. BC_OPT_NONE, + + /// An argument required. BC_OPT_REQUIRED, + + /// An option that is bc-only. BC_OPT_BC_ONLY, + + /// An option that is dc-only. BC_OPT_DC_ONLY, + } BcOptType; +/// A struct to hold const data for long options. typedef struct BcOptLong { + + /// The name of the option. const char *name; + + /// The type of the option. BcOptType type; + + /// The character to return if the long option was parsed. int val; + } BcOptLong; +/** + * Initialize data for parsing options. + * @param o The option data to initialize. + * @param argv The array of arguments. + */ void bc_opt_init(BcOpt *o, char **argv); +/** + * Parse an option. This returns a value the same way getopt() and getopt_long() + * do, so it returns a character for the parsed option or -1 if done. + * @param o The option data. + * @param longopts The long options. + * @return A character for the parsed option, or -1 if done. + */ int bc_opt_parse(BcOpt *o, const BcOptLong *longopts); +/** + * Returns true if the option is `--` and not a long option. + * @param a The argument to parse. + * @return True if @a a is the `--` option, false otherwise. + */ #define BC_OPT_ISDASHDASH(a) \ ((a) != NULL && (a)[0] == '-' && (a)[1] == '-' && (a)[2] == '\0') +/** + * Returns true if the option is a short option. + * @param a The argument to parse. + * @return True if @a a is a short option, false otherwise. + */ #define BC_OPT_ISSHORTOPT(a) \ ((a) != NULL && (a)[0] == '-' && (a)[1] != '-' && (a)[1] != '\0') +/** + * Returns true if the option has `--` at the beginning, i.e., is a long option. + * @param a The argument to parse. + * @return True if @a a is a long option, false otherwise. + */ #define BC_OPT_ISLONGOPT(a) \ ((a) != NULL && (a)[0] == '-' && (a)[1] == '-' && (a)[2] != '\0') diff --git a/include/parse.h b/include/parse.h index 2d4173fc..e1492c19 100644 --- a/include/parse.h +++ b/include/parse.h @@ -45,55 +45,89 @@ #include <lex.h> #include <lang.h> -// the following are flags that can be passed to @a BcParseExpr functions. They +// The following are flags that can be passed to @a BcParseExpr functions. They // define the requirements that the parsed expression must meet to not have an // error thrown. -// A flag that requires that the expression is valid for conditionals in for -// loops, while loops, and if statements. This is because POSIX requires that -// certain operators are *only* used in those cases. It's whacked, but that's -// how it is. +/// A flag that requires that the expression is valid for conditionals in for +/// loops, while loops, and if statements. This is because POSIX requires that +/// certain operators are *only* used in those cases. It's whacked, but that's +/// how it is. #define BC_PARSE_REL (UINTMAX_C(1)<<0) -// A flag that requires that the expression is valid for a print statement. +/// A flag that requires that the expression is valid for a print statement. #define BC_PARSE_PRINT (UINTMAX_C(1)<<1) -// A flag that requires that the expression does *not* have any function call. +/// A flag that requires that the expression does *not* have any function call. #define BC_PARSE_NOCALL (UINTMAX_C(1)<<2) -// A flag that requires that the expression does *not* have a read() expression. +/// A flag that requires that the expression does *not* have a read() expression. #define BC_PARSE_NOREAD (UINTMAX_C(1)<<3) -// A flag that *allows* (rather than requires) that an array appear in the -// expression. This is mostly used as parameters in bc. +/// A flag that *allows* (rather than requires) that an array appear in the +/// expression. This is mostly used as parameters in bc. #define BC_PARSE_ARRAY (UINTMAX_C(1)<<4) -// A flag that requires that the expression is not empty and returns a value. +/// A flag that requires that the expression is not empty and returns a value. #define BC_PARSE_NEEDVAL (UINTMAX_C(1)<<5) -// Returns true if the current parser state allows parsing, false otherwise. #if BC_ENABLED + +/** + * Returns true if the current parser state allows parsing, false otherwise. + * @param p The parser. + * @return True if parsing can proceed, false otherwise. + */ #define BC_PARSE_CAN_PARSE(p) \ ((p).l.t != BC_LEX_EOF && (p).l.t != BC_LEX_KW_DEFINE) + #else // BC_ENABLED + +/** + * Returns true if the current parser state allows parsing, false otherwise. + * @param p The parser. + * @return True if parsing can proceed, false otherwise. + */ #define BC_PARSE_CAN_PARSE(p) ((p).l.t != BC_LEX_EOF) + #endif // BC_ENABLED -// Pushes the instruction @a i onto the bytecode vector for the current -// function. +/** + * Pushes the instruction @a i onto the bytecode vector for the current + * function. + * @param p The parser. + * @param i The instruction to push onto the bytecode vector. + */ #define bc_parse_push(p, i) (bc_vec_pushByte(&(p)->func->code, (uchar) (i))) -// Pushes an index onto the bytecode vector. For more information, see -// @a bc_vec_pushIndex() in src/vector.c and @a bc_program_index() in -// src/program.c. +/** + * Pushes an index onto the bytecode vector. For more information, see + * @a bc_vec_pushIndex() in src/vector.c and @a bc_program_index() in + * src/program.c. + * @param p The parser. + * @param idx The index to push onto the bytecode vector. + */ #define bc_parse_pushIndex(p, idx) (bc_vec_pushIndex(&(p)->func->code, (idx))) -// Two convencience macros for throwing errors in parse code. They take care of -// plumbing like passing in the current line the lexer is on. +/** + * A convenience macro for throwing errors in parse code. They take care of + * plumbing like passing in the current line the lexer is on. + * @param p The parser. + * @param e The error. + */ #define bc_parse_err(p, e) (bc_vm_handleError((e), (p)->l.line)) + +/** + * A convenience macro for throwing errors in parse code. They take care of + * plumbing like passing in the current line the lexer is on. + * @param p The parser. + * @param e The error. + * @param ... The varags that are needed. + */ #define bc_parse_verr(p, e, ...) \ (bc_vm_handleError((e), (p)->l.line, __VA_ARGS__)) +// Forward declarations. struct BcParse; struct BcProgram; diff --git a/include/program.h b/include/program.h index ec31f348..52353e26 100644 --- a/include/program.h +++ b/include/program.h @@ -44,144 +44,379 @@ #include <num.h> #include <rand.h> +/// The index of ibase in the globals array. #define BC_PROG_GLOBALS_IBASE (0) + +/// The index of obase in the globals array. #define BC_PROG_GLOBALS_OBASE (1) + +/// The index of scale in the globals array. #define BC_PROG_GLOBALS_SCALE (2) #if BC_ENABLE_EXTRA_MATH + +/// The index of the rand max in the maxes array. #define BC_PROG_MAX_RAND (3) + #endif // BC_ENABLE_EXTRA_MATH +/// The length of the globals array. #define BC_PROG_GLOBALS_LEN (3 + BC_ENABLE_EXTRA_MATH) +/// The capacity of the one BcNum, which is a constant. #define BC_PROG_ONE_CAP (1) typedef struct BcProgram { + /// The array of globals values. BcBigDig globals[BC_PROG_GLOBALS_LEN]; + + /// The array of globals stacks. BcVec globals_v[BC_PROG_GLOBALS_LEN]; #if BC_ENABLE_EXTRA_MATH && BC_ENABLE_RAND + + /// The pseudo-random number generator. BcRNG rng; + #endif // BC_ENABLE_EXTRA_MATH && BC_ENABLE_RAND + /// The results stack. BcVec results; + + /// The execution stack. BcVec stack; + /// A pointer to the current function's constants. BcVec *consts; + + /// A pointer to the current function's strings. BcVec *strs; + /// The array of functions. BcVec fns; + + /// The map of functions to go with fns. BcVec fn_map; + /// The array of variables. BcVec vars; + + /// The map of variables to go with vars. BcVec var_map; + /// The array of arrays. BcVec arrs; + + /// The map of arrays to go with arrs. BcVec arr_map; #if DC_ENABLED + + /// An array of strings. This is for dc only because dc does not store + /// strings in functions. BcVec strs_v; + /// A vector of tail calls. These are just integers, which are the number of + /// tail calls that have been executed for each function (string) on the + /// stack for dc. This is to prevent dc from constantly growing memory use + /// because of pushing more and more string executions on the stack. BcVec tail_calls; - BcBigDig strm; + /// A BcNum that has the proper base for asciify for dc. BcNum strmb; + #endif // DC_ENABLED + /// A BcNum set to constant 0. BcNum zero; + + /// A BcNum set to constant 1. BcNum one; #if BC_ENABLED + + /// The last printed value for bc. BcNum last; + #endif // BC_ENABLED #if DC_ENABLED - // This uses BC_NUM_LONG_LOG10 because it is used in bc_num_ulong2num(), - // which attempts to realloc, unless it is big enough. This is big enough. + + // The BcDig array for strmb. This uses BC_NUM_LONG_LOG10 because it is used + // in bc_num_ulong2num(), which attempts to realloc, unless it is big + // enough. This is big enough. BcDig strmb_num[BC_NUM_BIGDIG_LOG10]; + #endif // DC_ENABLED + // The BcDig array for the zero BcNum. BcDig zero_num[BC_PROG_ONE_CAP]; + + // The BcDig array for the one BcNum. BcDig one_num[BC_PROG_ONE_CAP]; } BcProgram; +/** + * Returns true if the stack @a s has at least @a n items, false otherwise. + * @param s The stack to check. + * @param n The number of items the stack must have. + * @return True if @a s has at least @a n items, false otherwise. + */ #define BC_PROG_STACK(s, n) ((s)->len >= ((size_t) (n))) +/** + * Get a pointer to the top value in a global value stack. + * @param v The global value stack. + * @return A pointer to the top value in @a v. + */ #define BC_PROG_GLOBAL_PTR(v) (bc_vec_top(v)) + +/** + * Get the top value in a global value stack. + * @param v The global value stack. + * @return The top value in @a v. + */ #define BC_PROG_GLOBAL(v) (*((BcBigDig*) BC_PROG_GLOBAL_PTR(v))) +/** + * Returns the current value of ibase. + * @param p The program. + * @return The current ibase. + */ #define BC_PROG_IBASE(p) ((p)->globals[BC_PROG_GLOBALS_IBASE]) + +/** + * Returns the current value of obase. + * @param p The program. + * @return The current obase. + */ #define BC_PROG_OBASE(p) ((p)->globals[BC_PROG_GLOBALS_OBASE]) + +/** + * Returns the current value of scale. + * @param p The program. + * @return The current scale. + */ #define BC_PROG_SCALE(p) ((p)->globals[BC_PROG_GLOBALS_SCALE]) +/// The index for the main function in the functions array.// #define BC_PROG_MAIN (0) + +/// The index for the read function in the functions array. #define BC_PROG_READ (1) +/** + * Retires (completes the execution of) an instruction. Some instructions + * require special retirement, but most can use this. + * @param p The program. + * @param nres The number of results returned by the instruction. + * @param nops The number of operands used by the instruction. + */ #define bc_program_retire(p, nres, nops) \ (bc_vec_npopAt(&(p)->results, (nops), (p)->results.len - (nres + nops))) #if DC_ENABLED + +/// A constant that tells how many functions are required in dc. #define BC_PROG_REQ_FUNCS (2) + #if !BC_ENABLED -// For dc only, last is always true. + +/// This define disappears the parameter last because for dc only, last is +/// always true. #define bc_program_copyToVar(p, name, t, last) \ bc_program_copyToVar(p, name, t) + #endif // !BC_ENABLED + #else // DC_ENABLED -// For bc, 'pop' and 'copy' are always false. + +/// This define disappears pop and copy because for bc, 'pop' and 'copy' are +/// always false. #define bc_program_pushVar(p, code, bgn, pop, copy) \ bc_program_pushVar(p, code, bgn) + +// In debug mode, we want bc to check the stack, but otherwise, we don't because +// the bc language implicitly mandates that the stack should always have enough +// items. #ifdef NDEBUG #define BC_PROG_NO_STACK_CHECK #endif // NDEBUG + #endif // DC_ENABLED +/** + * Returns true if the BcNum @a n is acting as a string. + * @param n The BcNum to test. + * @return True if @a n is acting as a string, false otherwise. + */ #define BC_PROG_STR(n) ((n)->num == NULL && !(n)->cap) + #if BC_ENABLED + +/** + * Returns true if the result @a r and @a n is a number. + * @param r The result. + * @param n The number corresponding to the result. + * @return True if the result holds a number, false otherwise. + */ #define BC_PROG_NUM(r, n) \ ((r)->t != BC_RESULT_ARRAY && (r)->t != BC_RESULT_STR && !BC_PROG_STR(n)) + #else // BC_ENABLED + +/** + * Returns true if the result @a r and @a n is a number. + * @param r The result. + * @param n The number corresponding to the result. + * @return True if the result holds a number, false otherwise. + */ #define BC_PROG_NUM(r, n) ((r)->t != BC_RESULT_STR && !BC_PROG_STR(n)) -// For dc, inst is always BC_INST_ARRAY_ELEM. + +/// This define removes the inst parameter because for dc, inst is always +/// BC_INST_ARRAY_ELEM. #define bc_program_pushArray(p, code, bgn, inst) \ bc_program_pushArray(p, code, bgn) + #endif // BC_ENABLED -typedef void (*BcProgramUnary)(BcResult*, BcNum*); +/** + * This is a function type for unary operations. Currently, these include + * boolean not, negation, and truncation with extra math. + * @param r The BcResult to store the result into. + * @param n The parameter to the unary operation. + */ +typedef void (*BcProgramUnary)(BcResult *r, BcNum *n); +/** + * Initializes the BcProgram. + * @param p The program to initialize. + */ void bc_program_init(BcProgram *p); + +#ifndef NDEBUG + +/** + * Frees a BcProgram. This is only used in debug builds because a BcProgram is + * only freed on program exit, and we don't care about freeing resources on + * exit. + * @param p The program to initialize. + */ void bc_program_free(BcProgram *p); +#endif // NDEBUG + #if BC_DEBUG_CODE #if BC_ENABLED && DC_ENABLED + +/** + * Prints the bytecode in a function. This is a debug-only function. + * @param p The program. + */ void bc_program_code(const BcProgram *p); + +/** + * Prints an instruction. This is a debug-only function. + * @param p The program. + * @param code The bytecode array. + * @param bgn A pointer to the current index. It is also updated to the next + * index. + */ void bc_program_printInst(const BcProgram *p, const char *code, size_t *restrict bgn); + +/** + * Prints the stack. This is a debug-only function. + * @param p The program. + */ void bc_program_printStackDebug(BcProgram* p); + #endif // BC_ENABLED && DC_ENABLED #endif // BC_DEBUG_CODE +/** + * Returns the index of the variable or array in their respective arrays. + * @param p The program. + * @param id The BcId of the variable or array. + * @param var True if the search should be for a variable, false for an array. + * @return The index of the variable or array in the correct array. + */ size_t bc_program_search(BcProgram *p, const char* id, bool var); + +/** + * Inserts a function into the program and returns the index of the function in + * the fns array. + * @param p The program. + * @param name The name of the function. + * @return The index of the function after insertion. + */ size_t bc_program_insertFunc(BcProgram *p, const char *name); + +/** + * Resets a program, usually because of resetting after an error. + * @param p The program to reset. + */ void bc_program_reset(BcProgram *p); + +/** + * Executes bc or dc code in the BcProgram. + * @param p The program. + */ void bc_program_exec(BcProgram *p); +/** + * Negates a copy of a BcNum. This is a BcProgramUnary function. + * @param r The BcResult to store the result into. + * @param n The parameter to the unary operation. + */ void bc_program_negate(BcResult *r, BcNum *n); + +/** + * Returns a boolean not of a BcNum. This is a BcProgramUnary function. + * @param r The BcResult to store the result into. + * @param n The parameter to the unary operation. + */ void bc_program_not(BcResult *r, BcNum *n); + #if BC_ENABLE_EXTRA_MATH + +/** + * Truncates a copy of a BcNum. This is a BcProgramUnary function. + * @param r The BcResult to store the result into. + * @param n The parameter to the unary operation. + */ void bc_program_trunc(BcResult *r, BcNum *n); + #endif // BC_ENABLE_EXTRA_MATH +/// A reference to an array of binary operator functions. extern const BcNumBinaryOp bc_program_ops[]; + +/// A reference to an array of binary operator allocation request functions. extern const BcNumBinaryOpReq bc_program_opReqs[]; + +/// A reference to an array of unary operator functions. extern const BcProgramUnary bc_program_unarys[]; + +/// A reference to a filename for command-line expressions. extern const char bc_program_exprs_name[]; + +/// A reference to a filename for stdin. extern const char bc_program_stdin_name[]; + +/// A reference to the ready message printed on SIGINT. extern const char bc_program_ready_msg[]; + +/// A reference to the length of the ready message. extern const size_t bc_program_ready_msg_len; + +/// A reference to an array of escape characters for the print statement. extern const char bc_program_esc_chars[]; + +/// A reference to an array of the characters corresponding to the escape +/// characters in bc_program_esc_chars. extern const char bc_program_esc_seqs[]; #endif // BC_PROGRAM_H diff --git a/include/rand.h b/include/rand.h index 77663d9e..62c4f0ed 100644 --- a/include/rand.h +++ b/include/rand.h @@ -52,10 +52,17 @@ #if BC_ENABLE_RAND -typedef ulong (*BcRandUlong)(void*); +/** + * A function to return a random unsigned long. + * @param ptr A void ptr to some data that will help generate the random ulong. + * @return The random ulong. + */ +typedef ulong (*BcRandUlong)(void *ptr); #if BC_LONG_BIT >= 64 +// If longs are 64 bits, we have the option of 128-bit integers on some +// compilers. These two sections test that. #ifdef BC_RAND_BUILTIN #if BC_RAND_BUILTIN #ifndef __SIZEOF_INT128__ @@ -73,131 +80,430 @@ typedef ulong (*BcRandUlong)(void*); #endif // __SIZEOF_INT128__ #endif // BC_RAND_BUILTIN +/// The type for random integers. typedef uint64_t BcRand; +/// A constant defined by PCG. #define BC_RAND_ROTC (63) #if BC_RAND_BUILTIN +/// A typedef for the PCG state. typedef __uint128_t BcRandState; +/** + * Multiply two integers, worrying about overflow. + * @param a The first integer. + * @param b The second integer. + * @return The product of the PCG states. + */ #define bc_rand_mul(a, b) (((BcRandState) (a)) * ((BcRandState) (b))) + +/** + * Add two integers, worrying about overflow. + * @param a The first integer. + * @param b The second integer. + * @return The sum of the PCG states. + */ #define bc_rand_add(a, b) (((BcRandState) (a)) + ((BcRandState) (b))) +/** + * Multiply two PCG states. + * @param a The first PCG state. + * @param b The second PCG state. + * @return The product of the PCG states. + */ #define bc_rand_mul2(a, b) (((BcRandState) (a)) * ((BcRandState) (b))) + +/** + * Add two PCG states. + * @param a The first PCG state. + * @param b The second PCG state. + * @return The sum of the PCG states. + */ #define bc_rand_add2(a, b) (((BcRandState) (a)) + ((BcRandState) (b))) +/** + * Figure out if the PRNG has been modified. Since the increment of the PRNG has + * to be odd, we use the extra bit to store whether it has been modified or not. + * @param r The PRNG. + * @return True if the PRNG has *not* been modified, false otherwise. + */ #define BC_RAND_NOTMODIFIED(r) (((r)->inc & 1UL) == 0) + +/** + * Return true if the PRNG has not been seeded yet. + * @param r The PRNG. + * @return True if the PRNG has not been seeded yet, false otherwise. + */ #define BC_RAND_ZERO(r) (!(r)->state) +/** + * Returns a constant built from @a h and @a l. + * @param h The high 64 bits. + * @param l The low 64 bits. + * @return The constant built from @a h and @a l. + */ #define BC_RAND_CONSTANT(h, l) ((((BcRandState) (h)) << 64) + (BcRandState) (l)) +/** + * Truncates a PCG state to the number of bits in a random integer. + * @param s The state to truncate. + * @return The truncated state. + */ #define BC_RAND_TRUNC(s) ((uint64_t) (s)) + +/** + * Chops a PCG state in half and returns the top bits. + * @param s The state to chop. + * @return The chopped state's top bits. + */ #define BC_RAND_CHOP(s) ((uint64_t) ((s) >> 64UL)) + +/** + * Rotates a PCG state. + * @param s The state to rotate. + * @return The rotated state. + */ #define BC_RAND_ROTAMT(s) ((unsigned int) ((s) >> 122UL)) #else // BC_RAND_BUILTIN +/// A typedef for the PCG state. typedef struct BcRandState { + /// The low bits. uint_fast64_t lo; + + /// The high bits. uint_fast64_t hi; } BcRandState; +/** + * Multiply two integers, worrying about overflow. + * @param a The first integer. + * @param b The second integer. + * @return The product of the PCG states. + */ #define bc_rand_mul(a, b) (bc_rand_multiply((a), (b))) + +/** + * Add two integers, worrying about overflow. + * @param a The first integer. + * @param b The second integer. + * @return The sum of the PCG states. + */ #define bc_rand_add(a, b) (bc_rand_addition((a), (b))) +/** + * Multiply two PCG states. + * @param a The first PCG state. + * @param b The second PCG state. + * @return The product of the PCG states. + */ #define bc_rand_mul2(a, b) (bc_rand_multiply2((a), (b))) + +/** + * Add two PCG states. + * @param a The first PCG state. + * @param b The second PCG state. + * @return The sum of the PCG states. + */ #define bc_rand_add2(a, b) (bc_rand_addition2((a), (b))) +/** + * Figure out if the PRNG has been modified. Since the increment of the PRNG has + * to be odd, we use the extra bit to store whether it has been modified or not. + * @param r The PRNG. + * @return True if the PRNG has *not* been modified, false otherwise. + */ #define BC_RAND_NOTMODIFIED(r) (((r)->inc.lo & 1) == 0) + +/** + * Return true if the PRNG has not been seeded yet. + * @param r The PRNG. + * @return True if the PRNG has not been seeded yet, false otherwise. + */ #define BC_RAND_ZERO(r) (!(r)->state.lo && !(r)->state.hi) +/** + * Returns a constant built from @a h and @a l. + * @param h The high 64 bits. + * @param l The low 64 bits. + * @return The constant built from @a h and @a l. + */ #define BC_RAND_CONSTANT(h, l) { .lo = (l), .hi = (h) } +/** + * Truncates a PCG state to the number of bits in a random integer. + * @param s The state to truncate. + * @return The truncated state. + */ #define BC_RAND_TRUNC(s) ((s).lo) + +/** + * Chops a PCG state in half and returns the top bits. + * @param s The state to chop. + * @return The chopped state's top bits. + */ #define BC_RAND_CHOP(s) ((s).hi) + +/** + * Returns the rotate amount for a PCG state. + * @param s The state to rotate. + * @return The semi-rotated state. + */ #define BC_RAND_ROTAMT(s) ((unsigned int) ((s).hi >> 58UL)) +/// A 64-bit integer with the bottom 32 bits set. #define BC_RAND_BOTTOM32 (((uint_fast64_t) 0xffffffffULL)) + +/** + * Returns the 32-bit truncated value of @a n. + * @param n The integer to truncate. + * @return The bottom 32 bits of @a n. + */ #define BC_RAND_TRUNC32(n) ((n) & BC_RAND_BOTTOM32) + +/** + * Returns the second 32 bits of @a n. + * @param n The integer to truncate. + * @return The second 32 bits of @a n. + */ #define BC_RAND_CHOP32(n) ((n) >> 32) #endif // BC_RAND_BUILTIN +/// A constant defined by PCG. #define BC_RAND_MULTIPLIER \ BC_RAND_CONSTANT(2549297995355413924ULL, 4865540595714422341ULL) +/** + * Returns the result of a PCG fold. + * @param s The state to fold. + * @return The folded state. + */ #define BC_RAND_FOLD(s) ((BcRand) (BC_RAND_CHOP(s) ^ BC_RAND_TRUNC(s))) #else // BC_LONG_BIT >= 64 +// If we are using 32-bit longs, we need to set these so. #undef BC_RAND_BUILTIN #define BC_RAND_BUILTIN (1) +/// The type for random integers. typedef uint32_t BcRand; +/// A constant defined by PCG. #define BC_RAND_ROTC (31) +/// A typedef for the PCG state. typedef uint_fast64_t BcRandState; +/** + * Multiply two integers, worrying about overflow. + * @param a The first integer. + * @param b The second integer. + * @return The product of the PCG states. + */ #define bc_rand_mul(a, b) (((BcRandState) (a)) * ((BcRandState) (b))) + +/** + * Add two integers, worrying about overflow. + * @param a The first integer. + * @param b The second integer. + * @return The sum of the PCG states. + */ #define bc_rand_add(a, b) (((BcRandState) (a)) + ((BcRandState) (b))) +/** + * Multiply two PCG states. + * @param a The first PCG state. + * @param b The second PCG state. + * @return The product of the PCG states. + */ #define bc_rand_mul2(a, b) (((BcRandState) (a)) * ((BcRandState) (b))) + +/** + * Add two PCG states. + * @param a The first PCG state. + * @param b The second PCG state. + * @return The sum of the PCG states. + */ #define bc_rand_add2(a, b) (((BcRandState) (a)) + ((BcRandState) (b))) +/** + * Figure out if the PRNG has been modified. Since the increment of the PRNG has + * to be odd, we use the extra bit to store whether it has been modified or not. + * @param r The PRNG. + * @return True if the PRNG has *not* been modified, false otherwise. + */ #define BC_RAND_NOTMODIFIED(r) (((r)->inc & 1UL) == 0) + +/** + * Return true if the PRNG has not been seeded yet. + * @param r The PRNG. + * @return True if the PRNG has not been seeded yet, false otherwise. + */ #define BC_RAND_ZERO(r) (!(r)->state) -#define BC_RAND_CONSTANT UINT64_C +/** + * Returns a constant built from a number. + * @param n The number. + * @return The constant built from @a n. + */ +#define BC_RAND_CONSTANT(n) UINT64_C(n) + +/// A constant defined by PCG. #define BC_RAND_MULTIPLIER BC_RAND_CONSTANT(6364136223846793005) +/** + * Truncates a PCG state to the number of bits in a random integer. + * @param s The state to truncate. + * @return The truncated state. + */ #define BC_RAND_TRUNC(s) ((uint32_t) (s)) + +/** + * Chops a PCG state in half and returns the top bits. + * @param s The state to chop. + * @return The chopped state's top bits. + */ #define BC_RAND_CHOP(s) ((uint32_t) ((s) >> 32UL)) + +/** + * Returns the rotate amount for a PCG state. + * @param s The state to rotate. + * @return The semi-rotated state. + */ #define BC_RAND_ROTAMT(s) ((unsigned int) ((s) >> 59UL)) +/** + * Returns the result of a PCG fold. + * @param s The state to fold. + * @return The folded state. + */ #define BC_RAND_FOLD(s) ((BcRand) ((((s) >> 18U) ^ (s)) >> 27U)) #endif // BC_LONG_BIT >= 64 +/** + * Rotates @a v by @a r bits. + * @param v The value to rotate. + * @param r The amount to rotate by. + * @return The rotated value. + */ #define BC_RAND_ROT(v, r) \ ((BcRand) (((v) >> (r)) | ((v) << ((0 - (r)) & BC_RAND_ROTC)))) +/// The number of bits in a random integer. #define BC_RAND_BITS (sizeof(BcRand) * CHAR_BIT) + +/// The number of bits in a PCG state. #define BC_RAND_STATE_BITS (sizeof(BcRandState) * CHAR_BIT) +/// The size of a BcNum with the max random integer. This isn't exact; it's +/// actually rather crude. But it's always enough. #define BC_RAND_NUM_SIZE (BC_NUM_BIGDIG_LOG10 * 2 + 2) +/// The mask for how many bits bc_rand_srand() can set per iteration. #define BC_RAND_SRAND_BITS ((1 << CHAR_BIT) - 1) +/// The actual RNG data. These are the actual PRNG's. typedef struct BcRNGData { + /// The state. BcRandState state; + + /// The increment and the modified bit. BcRandState inc; } BcRNGData; +/// The public PRNG. This is just a stack of PRNG's to maintain the globals +/// stack illusion. typedef struct BcRNG { + /// The stack of PRNG's. BcVec v; } BcRNG; +/** + * Initializes a BcRNG. + * @param r The BcRNG to initialize. + */ void bc_rand_init(BcRNG *r); + #ifndef NDEBUG + +/** + * Frees a BcRNG. This is only in debug builds because it would only be freed on + * exit. + * @param r The BcRNG to free. + */ void bc_rand_free(BcRNG *r); + #endif // NDEBUG +/** + * Returns a random integer from the PRNG. + * @param r The PRNG. + * @return A random integer. + */ BcRand bc_rand_int(BcRNG *r); + +/** + * Returns a random integer from the PRNG bounded by @a bound. Bias is + * eliminated. + * @param r The PRNG. + * @param bound The bound for the random integer. + * @return A bounded random integer. + */ BcRand bc_rand_bounded(BcRNG *r, BcRand bound); + +/** + * Seed the PRNG with the state in two parts and the increment in two parts. + * @param r The PRNG. + * @param state1 The first part of the state. + * @param state2 The second part of the state. + * @param inc1 The first part of the increment. + * @param inc2 The second part of the increment. + */ void bc_rand_seed(BcRNG *r, ulong state1, ulong state2, ulong inc1, ulong inc2); + +/** + * Pushes a new PRNG onto the PRNG stack. + * @param r The PRNG. + */ void bc_rand_push(BcRNG *r); + +/** + * Pops one or all but one items off of the PRNG stack. + * @param r The PRNG. + * @param reset True if all but one PRNG should be popped off the stack, false + * if only one should be popped. + */ void bc_rand_pop(BcRNG *r, bool reset); + +/** + * Returns, via pointers, the state of the PRNG in pieces. + * @param r The PRNG. + * @param s1 The return value for the first part of the state. + * @param s2 The return value for the second part of the state. + * @param i1 The return value for the first part of the increment. + * @param i2 The return value for the second part of the increment. + */ void bc_rand_getRands(BcRNG *r, BcRand *s1, BcRand *s2, BcRand *i1, BcRand *i2); + +/** + * Seed the PRNG with random data. + * @param rng The PRNG. + */ void bc_rand_srand(BcRNGData *rng); +/// A reference to a constant multiplier. extern const BcRandState bc_rand_multiplier; #endif // BC_ENABLE_RAND diff --git a/include/read.h b/include/read.h index 007dcaef..0a685657 100644 --- a/include/read.h +++ b/include/read.h @@ -41,7 +41,11 @@ #include <status.h> #include <vector.h> -/// Returns true if c is a non-ASCII char. +/** + * Returns true if @a c is a non-ASCII (invalid) char. + * @param c The character to test. + * @return True if @a c is an invalid char. + */ #define BC_READ_BIN_CHAR(c) (((c) < ' ' && !isspace((c))) || ((uchar) c) > '~') /** diff --git a/include/version.h b/include/version.h index e29bbf69..5127c28e 100644 --- a/include/version.h +++ b/include/version.h @@ -36,7 +36,7 @@ #ifndef BC_VERSION_H #define BC_VERSION_H -// The current version. +/// The current version. #define VERSION 5.0.0 #endif // BC_VERSION_H |