contrib/bc/include/num.h

   1 /*
   2  * *****************************************************************************
   3  *
   4  * SPDX-License-Identifier: BSD-2-Clause
   5  *
   6  * Copyright (c) 2018-2020 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 #define BC_BASE (10)
  55
  56 typedef unsigned long ulong;
  57
  58 typedef BclBigDig BcBigDig;
  59
  60 #if BC_LONG_BIT >= 64
  61
  62 #define BC_NUM_BIGDIG_MAX ((BcBigDig) UINT64_MAX)
  63
  64 #define BC_BASE_DIGS (9)
  65 #define BC_BASE_POW (1000000000)
  66
  67 #define BC_NUM_BIGDIG_C UINT64_C
  68
  69 typedef int_least32_t BcDig;
  70
  71 #elif BC_LONG_BIT >= 32
  72
  73 #define BC_NUM_BIGDIG_MAX ((BcBigDig) UINT32_MAX)
  74
  75 #define BC_BASE_DIGS (4)
  76 #define BC_BASE_POW (10000)
  77
  78 #define BC_NUM_BIGDIG_C UINT32_C
  79
  80 typedef int_least16_t BcDig;
  81
  82 #else
  83
  84 #error BC_LONG_BIT must be at least 32
  85
  86 #endif // BC_LONG_BIT >= 64
  87
  88 #define BC_NUM_DEF_SIZE (8)
  89
  90 typedef struct BcNum {
  91         BcDig *restrict num;
  92         size_t rdx;
  93         size_t scale;
  94         size_t len;
  95         size_t cap;
  96 } BcNum;
  97
  98 #if BC_ENABLE_EXTRA_MATH
  99
 100 #ifndef BC_ENABLE_RAND
 101 #define BC_ENABLE_RAND (1)
 102 #endif // BC_ENABLE_RAND
 103
 104 #if BC_ENABLE_RAND
 105 // Forward declaration
 106 struct BcRNG;
 107 #endif // BC_ENABLE_RAND
 108
 109 #endif // BC_ENABLE_EXTRA_MATH
 110
 111 #define BC_NUM_MIN_BASE (BC_NUM_BIGDIG_C(2))
 112 #define BC_NUM_MAX_POSIX_IBASE (BC_NUM_BIGDIG_C(16))
 113 #define BC_NUM_MAX_IBASE (BC_NUM_BIGDIG_C(36))
 114 // This is the max base allowed by bc_num_parseChar().
 115 #define BC_NUM_MAX_LBASE (BC_NUM_BIGDIG_C('Z' + BC_BASE + 1))
 116 #define BC_NUM_PRINT_WIDTH (BC_NUM_BIGDIG_C(69))
 117
 118 #ifndef BC_NUM_KARATSUBA_LEN
 119 #define BC_NUM_KARATSUBA_LEN (BC_NUM_BIGDIG_C(32))
 120 #elif BC_NUM_KARATSUBA_LEN < 16
 121 #error BC_NUM_KARATSUBA_LEN must be at least 16.
 122 #endif // BC_NUM_KARATSUBA_LEN
 123
 124 // A crude, but always big enough, calculation of
 125 // the size required for ibase and obase BcNum's.
 126 #define BC_NUM_BIGDIG_LOG10 (BC_NUM_DEF_SIZE)
 127
 128 #define BC_NUM_NONZERO(n) ((n)->len)
 129 #define BC_NUM_ZERO(n) (!BC_NUM_NONZERO(n))
 130 #define BC_NUM_ONE(n) ((n)->len == 1 && (n)->rdx == 0 && (n)->num[0] == 1)
 131
 132 #define BC_NUM_NUM_LETTER(c) ((c) - 'A' + BC_BASE)
 133
 134 #define BC_NUM_KARATSUBA_ALLOCS (6)
 135
 136 #define BC_NUM_ROUND_POW(s) (bc_vm_growSize((s), BC_BASE_DIGS - 1))
 137 #define BC_NUM_RDX(s) (BC_NUM_ROUND_POW(s) / BC_BASE_DIGS)
 138
 139 #define BC_NUM_RDX_VAL(n) ((n)->rdx >> 1)
 140 #define BC_NUM_RDX_VAL_NP(n) ((n).rdx >> 1)
 141 #define BC_NUM_RDX_SET(n, v) \
 142         ((n)->rdx = (((v) << 1) | ((n)->rdx & (BcBigDig) 1)))
 143 #define BC_NUM_RDX_SET_NP(n, v) \
 144         ((n).rdx = (((v) << 1) | ((n).rdx & (BcBigDig) 1)))
 145 #define BC_NUM_RDX_SET_NEG(n, v, neg) \
 146         ((n)->rdx = (((v) << 1) | (neg)))
 147
 148 #define BC_NUM_RDX_VALID(n) \
 149         (BC_NUM_ZERO(n) || BC_NUM_RDX_VAL(n) * BC_BASE_DIGS >= (n)->scale)
 150 #define BC_NUM_RDX_VALID_NP(n) \
 151         ((!(n).len) || BC_NUM_RDX_VAL_NP(n) * BC_BASE_DIGS >= (n).scale)
 152
 153 #define BC_NUM_NEG(n) ((n)->rdx & ((BcBigDig) 1))
 154 #define BC_NUM_NEG_NP(n) ((n).rdx & ((BcBigDig) 1))
 155 #define BC_NUM_NEG_CLR(n) ((n)->rdx &= ~((BcBigDig) 1))
 156 #define BC_NUM_NEG_CLR_NP(n) ((n).rdx &= ~((BcBigDig) 1))
 157 #define BC_NUM_NEG_SET(n) ((n)->rdx |= ((BcBigDig) 1))
 158 #define BC_NUM_NEG_TGL(n) ((n)->rdx ^= ((BcBigDig) 1))
 159 #define BC_NUM_NEG_TGL_NP(n) ((n).rdx ^= ((BcBigDig) 1))
 160 #define BC_NUM_NEG_VAL(n, v) (((n)->rdx & ~((BcBigDig) 1)) | (v))
 161 #define BC_NUM_NEG_VAL_NP(n, v) (((n).rdx & ~((BcBigDig) 1)) | (v))
 162
 163 #define BC_NUM_SIZE(n) ((n) * sizeof(BcDig))
 164
 165 #if BC_DEBUG_CODE
 166 #define BC_NUM_PRINT(x) fprintf(stderr, "%s = %lu\n", #x, (unsigned long)(x))
 167 #define DUMP_NUM bc_num_dump
 168 #else // BC_DEBUG_CODE
 169 #undef DUMP_NUM
 170 #define DUMP_NUM(x,y)
 171 #define BC_NUM_PRINT(x)
 172 #endif // BC_DEBUG_CODE
 173
 174 typedef void (*BcNumBinaryOp)(BcNum*, BcNum*, BcNum*, size_t);
 175 typedef size_t (*BcNumBinaryOpReq)(const BcNum*, const BcNum*, size_t);
 176 typedef void (*BcNumDigitOp)(size_t, size_t, bool);
 177 typedef void (*BcNumShiftAddOp)(BcDig*, const BcDig*, size_t);
 178
 179 void bc_num_init(BcNum *restrict n, size_t req);
 180 void bc_num_setup(BcNum *restrict n, BcDig *restrict num, size_t cap);
 181 void bc_num_copy(BcNum *d, const BcNum *s);
 182 void bc_num_createCopy(BcNum *d, const BcNum *s);
 183 void bc_num_createFromBigdig(BcNum *n, BcBigDig val);
 184 void bc_num_clear(BcNum *restrict n);
 185 void bc_num_free(void *num);
 186
 187 size_t bc_num_scale(const BcNum *restrict n);
 188 size_t bc_num_len(const BcNum *restrict n);
 189
 190 void bc_num_bigdig(const BcNum *restrict n, BcBigDig *result);
 191 void bc_num_bigdig2(const BcNum *restrict n, BcBigDig *result);
 192 void bc_num_bigdig2num(BcNum *restrict n, BcBigDig val);
 193
 194 #if BC_ENABLE_EXTRA_MATH && BC_ENABLE_RAND
 195 void bc_num_irand(const BcNum *restrict a, BcNum *restrict b,
 196                   struct BcRNG *restrict rng);
 197 void bc_num_rng(const BcNum *restrict n, struct BcRNG *rng);
 198 void bc_num_createFromRNG(BcNum *restrict n, struct BcRNG *rng);
 199 #endif // BC_ENABLE_EXTRA_MATH && BC_ENABLE_RAND
 200
 201 void bc_num_add(BcNum *a, BcNum *b, BcNum *c, size_t scale);
 202 void bc_num_sub(BcNum *a, BcNum *b, BcNum *c, size_t scale);
 203 void bc_num_mul(BcNum *a, BcNum *b, BcNum *c, size_t scale);
 204 void bc_num_div(BcNum *a, BcNum *b, BcNum *c, size_t scale);
 205 void bc_num_mod(BcNum *a, BcNum *b, BcNum *c, size_t scale);
 206 void bc_num_pow(BcNum *a, BcNum *b, BcNum *c, size_t scale);
 207 #if BC_ENABLE_EXTRA_MATH
 208 void bc_num_places(BcNum *a, BcNum *b, BcNum *c, size_t scale);
 209 void bc_num_lshift(BcNum *a, BcNum *b, BcNum *c, size_t scale);
 210 void bc_num_rshift(BcNum *a, BcNum *b, BcNum *c, size_t scale);
 211 #endif // BC_ENABLE_EXTRA_MATH
 212 void bc_num_sqrt(BcNum *restrict a, BcNum *restrict b, size_t scale);
 213 void bc_num_sr(BcNum *restrict a, BcNum *restrict b, size_t scale);
 214 void bc_num_divmod(BcNum *a, BcNum *b, BcNum *c, BcNum *d, size_t scale);
 215
 216 size_t bc_num_addReq(const BcNum* a, const BcNum* b, size_t scale);
 217
 218 size_t bc_num_mulReq(const BcNum *a, const BcNum *b, size_t scale);
 219 size_t bc_num_divReq(const BcNum *a, const BcNum *b, size_t scale);
 220 size_t bc_num_powReq(const BcNum *a, const BcNum *b, size_t scale);
 221 #if BC_ENABLE_EXTRA_MATH
 222 size_t bc_num_placesReq(const BcNum *a, const BcNum *b, size_t scale);
 223 #endif // BC_ENABLE_EXTRA_MATH
 224
 225 void bc_num_truncate(BcNum *restrict n, size_t places);
 226 void bc_num_extend(BcNum *restrict n, size_t places);
 227 void bc_num_shiftRight(BcNum *restrict n, size_t places);
 228
 229 ssize_t bc_num_cmp(const BcNum *a, const BcNum *b);
 230
 231 #if DC_ENABLED
 232 void bc_num_modexp(BcNum *a, BcNum *b, BcNum *c, BcNum *restrict d);
 233 #endif // DC_ENABLED
 234
 235 void bc_num_zero(BcNum *restrict n);
 236 void bc_num_one(BcNum *restrict n);
 237 ssize_t bc_num_cmpZero(const BcNum *n);
 238
 239 bool bc_num_strValid(const char *restrict val);
 240 void bc_num_parse(BcNum *restrict n, const char *restrict val, BcBigDig base);
 241 void bc_num_print(BcNum *restrict n, BcBigDig base, bool newline);
 242 #if DC_ENABLED
 243 void bc_num_stream(BcNum *restrict n, BcBigDig base);
 244 #endif // DC_ENABLED
 245
 246 #if BC_DEBUG_CODE
 247 void bc_num_printDebug(const BcNum *n, const char *name, bool emptyline);
 248 void bc_num_printDigs(const BcDig* n, size_t len, bool emptyline);
 249 void bc_num_printWithDigs(const BcNum *n, const char *name, bool emptyline);
 250 void bc_num_dump(const char *varname, const BcNum *n);
 251 #endif // BC_DEBUG_CODE
 252
 253 extern const char bc_num_hex_digits[];
 254 extern const BcBigDig bc_num_pow10[BC_BASE_DIGS + 1];
 255
 256 extern const BcDig bc_num_bigdigMax[];
 257 extern const BcDig bc_num_bigdigMax2[];
 258 extern const size_t bc_num_bigdigMax_size;
 259 extern const size_t bc_num_bigdigMax2_size;
 260
 261 #endif // BC_NUM_H