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#define BC_BASE (10) 55 56typedef unsigned long ulong; 57 58typedef 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 69typedef 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 80typedef 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 90typedef 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 106struct 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 174typedef void (*BcNumBinaryOp)(BcNum*, BcNum*, BcNum*, size_t); 175typedef void (*BcNumBinOp)(BcNum*, BcNum*, BcNum* restrict, size_t); 176typedef size_t (*BcNumBinaryOpReq)(const BcNum*, const BcNum*, size_t); 177typedef void (*BcNumDigitOp)(size_t, size_t, bool); 178typedef void (*BcNumShiftAddOp)(BcDig* restrict, const BcDig* restrict, size_t); 179 180void bc_num_init(BcNum *restrict n, size_t req); 181void bc_num_setup(BcNum *restrict n, BcDig *restrict num, size_t cap); 182void bc_num_copy(BcNum *d, const BcNum *s); 183void bc_num_createCopy(BcNum *d, const BcNum *s); 184void bc_num_createFromBigdig(BcNum *n, BcBigDig val); 185void bc_num_clear(BcNum *restrict n); 186void bc_num_free(void *num); 187 188size_t bc_num_scale(const BcNum *restrict n); 189size_t bc_num_len(const BcNum *restrict n); 190 191void bc_num_bigdig(const BcNum *restrict n, BcBigDig *result); 192void bc_num_bigdig2(const BcNum *restrict n, BcBigDig *result); 193void bc_num_bigdig2num(BcNum *restrict n, BcBigDig val); 194 195#if BC_ENABLE_EXTRA_MATH && BC_ENABLE_RAND 196void bc_num_irand(const BcNum *restrict a, BcNum *restrict b, 197 struct BcRNG *restrict rng); 198void bc_num_rng(const BcNum *restrict n, struct BcRNG *rng); 199void bc_num_createFromRNG(BcNum *restrict n, struct BcRNG *rng); 200#endif // BC_ENABLE_EXTRA_MATH && BC_ENABLE_RAND 201 202void bc_num_add(BcNum *a, BcNum *b, BcNum *c, size_t scale); 203void bc_num_sub(BcNum *a, BcNum *b, BcNum *c, size_t scale); 204void bc_num_mul(BcNum *a, BcNum *b, BcNum *c, size_t scale); 205void bc_num_div(BcNum *a, BcNum *b, BcNum *c, size_t scale); 206void bc_num_mod(BcNum *a, BcNum *b, BcNum *c, size_t scale); 207void bc_num_pow(BcNum *a, BcNum *b, BcNum *c, size_t scale); 208#if BC_ENABLE_EXTRA_MATH 209void bc_num_places(BcNum *a, BcNum *b, BcNum *c, size_t scale); 210void bc_num_lshift(BcNum *a, BcNum *b, BcNum *c, size_t scale); 211void bc_num_rshift(BcNum *a, BcNum *b, BcNum *c, size_t scale); 212#endif // BC_ENABLE_EXTRA_MATH 213void bc_num_sqrt(BcNum *restrict a, BcNum *restrict b, size_t scale); 214void bc_num_sr(BcNum *restrict a, BcNum *restrict b, size_t scale); 215void bc_num_divmod(BcNum *a, BcNum *b, BcNum *c, BcNum *d, size_t scale); 216 217size_t bc_num_addReq(const BcNum* a, const BcNum* b, size_t scale); 218 219size_t bc_num_mulReq(const BcNum *a, const BcNum *b, size_t scale); 220size_t bc_num_divReq(const BcNum *a, const BcNum *b, size_t scale); 221size_t bc_num_powReq(const BcNum *a, const BcNum *b, size_t scale); 222#if BC_ENABLE_EXTRA_MATH 223size_t bc_num_placesReq(const BcNum *a, const BcNum *b, size_t scale); 224#endif // BC_ENABLE_EXTRA_MATH 225 226void bc_num_truncate(BcNum *restrict n, size_t places); 227void bc_num_extend(BcNum *restrict n, size_t places); 228void bc_num_shiftRight(BcNum *restrict n, size_t places); 229 230ssize_t bc_num_cmp(const BcNum *a, const BcNum *b); 231 232#if DC_ENABLED 233void bc_num_modexp(BcNum *a, BcNum *b, BcNum *c, BcNum *restrict d); 234#endif // DC_ENABLED 235 236void bc_num_zero(BcNum *restrict n); 237void bc_num_one(BcNum *restrict n); 238ssize_t bc_num_cmpZero(const BcNum *n); 239 240#if !defined(NDEBUG) || BC_ENABLE_LIBRARY 241bool bc_num_strValid(const char *restrict val); 242#endif // !defined(NDEBUG) || BC_ENABLE_LIBRARY 243void bc_num_parse(BcNum *restrict n, const char *restrict val, BcBigDig base); 244void bc_num_print(BcNum *restrict n, BcBigDig base, bool newline); 245#if DC_ENABLED 246void bc_num_stream(BcNum *restrict n, BcBigDig base); 247#endif // DC_ENABLED 248 249#if BC_DEBUG_CODE 250void bc_num_printDebug(const BcNum *n, const char *name, bool emptyline); 251void bc_num_printDigs(const BcDig* n, size_t len, bool emptyline); 252void bc_num_printWithDigs(const BcNum *n, const char *name, bool emptyline); 253void bc_num_dump(const char *varname, const BcNum *n); 254#endif // BC_DEBUG_CODE 255 256extern const char bc_num_hex_digits[]; 257extern const BcBigDig bc_num_pow10[BC_BASE_DIGS + 1]; 258 259extern const BcDig bc_num_bigdigMax[]; 260extern const BcDig bc_num_bigdigMax2[]; 261extern const size_t bc_num_bigdigMax_size; 262extern const size_t bc_num_bigdigMax2_size; 263 264#endif // BC_NUM_H 265