1 /* 2 * ***************************************************************************** 3 * 4 * Copyright (c) 2018-2019 Gavin D. Howard and contributors. 5 * 6 * All rights reserved. 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 #include <stdio.h> 44 45 #include <sys/types.h> 46 47 #include <status.h> 48 49 #ifndef BC_ENABLE_EXTRA_MATH 50 #define BC_ENABLE_EXTRA_MATH (1) 51 #endif // BC_ENABLE_EXTRA_MATH 52 53 #define BC_BASE (10) 54 55 typedef unsigned long ulong; 56 57 // For some reason, LONG_BIT is not defined in some versions of gcc. 58 // I define it here to the minimum accepted value in the POSIX standard. 59 #ifndef LONG_BIT 60 #define LONG_BIT (32) 61 #endif // LONG_BIT 62 63 #ifndef BC_LONG_BIT 64 #define BC_LONG_BIT LONG_BIT 65 #endif // BC_LONG_BIT 66 67 #if BC_LONG_BIT > LONG_BIT 68 #error BC_LONG_BIT cannot be greater than LONG_BIT 69 #endif // BC_LONG_BIT > LONG_BIT 70 71 #if BC_LONG_BIT >= 64 72 73 typedef int_least32_t BcDig; 74 typedef uint_fast64_t BcBigDig; 75 76 #define BC_NUM_BIGDIG_MAX (UINT_FAST64_MAX) 77 78 #define BC_BASE_DIGS (9) 79 #define BC_BASE_POW (1000000000) 80 #define BC_NUM_DEF_SIZE (2) 81 82 #define BC_NUM_BIGDIG_C UINT64_C 83 84 #elif BC_LONG_BIT >= 32 85 86 typedef int_least16_t BcDig; 87 typedef uint_fast32_t BcBigDig; 88 89 #define BC_NUM_BIGDIG_MAX (UINT_FAST32_MAX) 90 91 #define BC_BASE_DIGS (4) 92 #define BC_BASE_POW (10000) 93 #define BC_NUM_DEF_SIZE (4) 94 95 #define BC_NUM_BIGDIG_C UINT32_C 96 97 #else 98 99 #error BC_LONG_BIT must be at least 32 100 101 #endif // BC_LONG_BIT >= 64 102 103 typedef struct BcNum { 104 BcDig *restrict num; 105 size_t rdx; 106 size_t scale; 107 size_t len; 108 size_t cap; 109 bool neg; 110 } BcNum; 111 112 #define BC_NUM_MIN_BASE (BC_NUM_BIGDIG_C(2)) 113 #define BC_NUM_MAX_POSIX_IBASE (BC_NUM_BIGDIG_C(16)) 114 #define BC_NUM_MAX_IBASE (BC_NUM_BIGDIG_C(36)) 115 // This is the max base allowed by bc_num_parseChar(). 116 #define BC_NUM_MAX_LBASE (BC_NUM_BIGDIG_C('Z' + BC_BASE + 1)) 117 #define BC_NUM_PRINT_WIDTH (BC_NUM_BIGDIG_C(69)) 118 119 #ifndef BC_NUM_KARATSUBA_LEN 120 #define BC_NUM_KARATSUBA_LEN (BC_NUM_BIGDIG_C(64)) 121 #elif BC_NUM_KARATSUBA_LEN < 16 122 #error BC_NUM_KARATSUBA_LEN must be at least 16. 123 #endif // BC_NUM_KARATSUBA_LEN 124 125 // A crude, but always big enough, calculation of 126 // the size required for ibase and obase BcNum's. 127 #define BC_NUM_BIGDIG_LOG10 ((CHAR_BIT * sizeof(BcBigDig) + 1) / 2 + 1) 128 129 #define BC_NUM_NONZERO(n) ((n)->len) 130 #define BC_NUM_ZERO(n) (!BC_NUM_NONZERO(n)) 131 #define BC_NUM_ONE(n) ((n)->len == 1 && (n)->rdx == 0 && (n)->num[0] == 1) 132 133 #define BC_NUM_NUM_LETTER(c) ((c) - 'A' + BC_BASE) 134 135 #define BC_NUM_KARATSUBA_ALLOCS (6) 136 137 #define BC_NUM_CMP_SIGNAL_VAL (~((ssize_t) ((size_t) SSIZE_MAX))) 138 #define BC_NUM_CMP_SIGNAL(cmp) (cmp == BC_NUM_CMP_SIGNAL_VAL) 139 140 #define BC_NUM_ROUND_POW(s) (bc_vm_growSize((s), BC_BASE_DIGS - 1)) 141 #define BC_NUM_RDX(s) (BC_NUM_ROUND_POW(s) / BC_BASE_DIGS) 142 143 #define BC_NUM_SIZE(n) ((n) * sizeof(BcDig)) 144 145 #if BC_DEBUG_CODE 146 #define BC_NUM_PRINT(x) fprintf(stderr, "%s = %lu\n", #x, (unsigned long)(x)) 147 #define DUMP_NUM bc_num_dump 148 #else // BC_DEBUG_CODE 149 #undef DUMP_NUM 150 #define DUMP_NUM(x,y) 151 #define BC_NUM_PRINT(x) 152 #endif // BC_DEBUG_CODE 153 154 typedef BcStatus (*BcNumBinaryOp)(BcNum*, BcNum*, BcNum*, size_t); 155 typedef size_t (*BcNumBinaryOpReq)(const BcNum*, const BcNum*, size_t); 156 typedef void (*BcNumDigitOp)(size_t, size_t, bool); 157 typedef BcStatus (*BcNumShiftAddOp)(BcDig*, const BcDig*, size_t); 158 159 void bc_num_init(BcNum *restrict n, size_t req); 160 void bc_num_setup(BcNum *restrict n, BcDig *restrict num, size_t cap); 161 void bc_num_copy(BcNum *d, const BcNum *s); 162 void bc_num_createCopy(BcNum *d, const BcNum *s); 163 void bc_num_createFromBigdig(BcNum *n, BcBigDig val); 164 void bc_num_free(void *num); 165 166 size_t bc_num_scale(const BcNum *restrict n); 167 size_t bc_num_len(const BcNum *restrict n); 168 169 BcStatus bc_num_bigdig(const BcNum *restrict n, BcBigDig *result); 170 void bc_num_bigdig2num(BcNum *restrict n, BcBigDig val); 171 172 BcStatus bc_num_add(BcNum *a, BcNum *b, BcNum *c, size_t scale); 173 BcStatus bc_num_sub(BcNum *a, BcNum *b, BcNum *c, size_t scale); 174 BcStatus bc_num_mul(BcNum *a, BcNum *b, BcNum *c, size_t scale); 175 BcStatus bc_num_div(BcNum *a, BcNum *b, BcNum *c, size_t scale); 176 BcStatus bc_num_mod(BcNum *a, BcNum *b, BcNum *c, size_t scale); 177 BcStatus bc_num_pow(BcNum *a, BcNum *b, BcNum *c, size_t scale); 178 #if BC_ENABLE_EXTRA_MATH 179 BcStatus bc_num_places(BcNum *a, BcNum *b, BcNum *c, size_t scale); 180 BcStatus bc_num_lshift(BcNum *a, BcNum *b, BcNum *c, size_t scale); 181 BcStatus bc_num_rshift(BcNum *a, BcNum *b, BcNum *c, size_t scale); 182 #endif // BC_ENABLE_EXTRA_MATH 183 BcStatus bc_num_sqrt(BcNum *restrict a, BcNum *restrict b, size_t scale); 184 BcStatus bc_num_divmod(BcNum *a, BcNum *b, BcNum *c, BcNum *d, size_t scale); 185 186 size_t bc_num_addReq(const BcNum* a, const BcNum* b, size_t scale); 187 188 size_t bc_num_mulReq(const BcNum *a, const BcNum *b, size_t scale); 189 size_t bc_num_powReq(const BcNum *a, const BcNum *b, size_t scale); 190 #if BC_ENABLE_EXTRA_MATH 191 size_t bc_num_placesReq(const BcNum *a, const BcNum *b, size_t scale); 192 #endif // BC_ENABLE_EXTRA_MATH 193 194 void bc_num_truncate(BcNum *restrict n, size_t places); 195 ssize_t bc_num_cmp(const BcNum *a, const BcNum *b); 196 197 #if DC_ENABLED 198 BcStatus bc_num_modexp(BcNum *a, BcNum *b, BcNum *c, BcNum *restrict d); 199 #endif // DC_ENABLED 200 201 void bc_num_one(BcNum *restrict n); 202 ssize_t bc_num_cmpZero(const BcNum *n); 203 204 BcStatus bc_num_parse(BcNum *restrict n, const char *restrict val, 205 BcBigDig base, bool letter); 206 BcStatus bc_num_print(BcNum *restrict n, BcBigDig base, bool newline); 207 #if DC_ENABLED 208 BcStatus bc_num_stream(BcNum *restrict n, BcBigDig base); 209 #endif // DC_ENABLED 210 211 #if BC_DEBUG_CODE 212 void bc_num_printDebug(const BcNum *n, const char *name, bool emptyline); 213 void bc_num_printDigs(const BcDig* n, size_t len, bool emptyline); 214 void bc_num_printWithDigs(const BcNum *n, const char *name, bool emptyline); 215 void bc_num_dump(const char *varname, const BcNum *n); 216 #endif // BC_DEBUG_CODE 217 218 extern const char bc_num_hex_digits[]; 219 extern const BcBigDig bc_num_pow10[BC_BASE_DIGS + 1]; 220 221 #endif // BC_NUM_H 222