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