xref: /freebsd/contrib/bc/include/num.h (revision 9e5787d2284e187abb5b654d924394a65772e004)
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 
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 uint64_t BcBigDig;
75 
76 #define BC_NUM_BIGDIG_MAX ((BcBigDig) UINT64_MAX)
77 
78 #define BC_BASE_DIGS (9)
79 #define BC_BASE_POW (1000000000)
80 
81 #define BC_NUM_BIGDIG_C UINT64_C
82 
83 #elif BC_LONG_BIT >= 32
84 
85 typedef int_least16_t BcDig;
86 typedef uint32_t BcBigDig;
87 
88 #define BC_NUM_BIGDIG_MAX ((BcBigDig) UINT32_MAX)
89 
90 #define BC_BASE_DIGS (4)
91 #define BC_BASE_POW (10000)
92 
93 #define BC_NUM_BIGDIG_C UINT32_C
94 
95 #else
96 
97 #error BC_LONG_BIT must be at least 32
98 
99 #endif // BC_LONG_BIT >= 64
100 
101 #define BC_NUM_DEF_SIZE (8)
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 #if BC_ENABLE_EXTRA_MATH
113 
114 #ifndef BC_ENABLE_RAND
115 #define BC_ENABLE_RAND (1)
116 #endif // BC_ENABLE_RAND
117 
118 #if BC_ENABLE_RAND
119 // Forward declaration
120 struct BcRNG;
121 #endif // BC_ENABLE_RAND
122 
123 #endif // BC_ENABLE_EXTRA_MATH
124 
125 #define BC_NUM_MIN_BASE (BC_NUM_BIGDIG_C(2))
126 #define BC_NUM_MAX_POSIX_IBASE (BC_NUM_BIGDIG_C(16))
127 #define BC_NUM_MAX_IBASE (BC_NUM_BIGDIG_C(36))
128 // This is the max base allowed by bc_num_parseChar().
129 #define BC_NUM_MAX_LBASE (BC_NUM_BIGDIG_C('Z' + BC_BASE + 1))
130 #define BC_NUM_PRINT_WIDTH (BC_NUM_BIGDIG_C(69))
131 
132 #ifndef BC_NUM_KARATSUBA_LEN
133 #define BC_NUM_KARATSUBA_LEN (BC_NUM_BIGDIG_C(32))
134 #elif BC_NUM_KARATSUBA_LEN < 16
135 #error BC_NUM_KARATSUBA_LEN must be at least 16.
136 #endif // BC_NUM_KARATSUBA_LEN
137 
138 // A crude, but always big enough, calculation of
139 // the size required for ibase and obase BcNum's.
140 #define BC_NUM_BIGDIG_LOG10 (BC_NUM_DEF_SIZE)
141 
142 #define BC_NUM_NONZERO(n) ((n)->len)
143 #define BC_NUM_ZERO(n) (!BC_NUM_NONZERO(n))
144 #define BC_NUM_ONE(n) ((n)->len == 1 && (n)->rdx == 0 && (n)->num[0] == 1)
145 
146 #define BC_NUM_NUM_LETTER(c) ((c) - 'A' + BC_BASE)
147 
148 #define BC_NUM_KARATSUBA_ALLOCS (6)
149 
150 #define BC_NUM_ROUND_POW(s) (bc_vm_growSize((s), BC_BASE_DIGS - 1))
151 #define BC_NUM_RDX(s) (BC_NUM_ROUND_POW(s) / BC_BASE_DIGS)
152 
153 #define BC_NUM_SIZE(n) ((n) * sizeof(BcDig))
154 
155 #if BC_DEBUG_CODE
156 #define BC_NUM_PRINT(x) fprintf(stderr, "%s = %lu\n", #x, (unsigned long)(x))
157 #define DUMP_NUM bc_num_dump
158 #else // BC_DEBUG_CODE
159 #undef DUMP_NUM
160 #define DUMP_NUM(x,y)
161 #define BC_NUM_PRINT(x)
162 #endif // BC_DEBUG_CODE
163 
164 typedef void (*BcNumBinaryOp)(BcNum*, BcNum*, BcNum*, size_t);
165 typedef size_t (*BcNumBinaryOpReq)(const BcNum*, const BcNum*, size_t);
166 typedef void (*BcNumDigitOp)(size_t, size_t, bool);
167 typedef void (*BcNumShiftAddOp)(BcDig*, const BcDig*, size_t);
168 
169 void bc_num_init(BcNum *restrict n, size_t req);
170 void bc_num_setup(BcNum *restrict n, BcDig *restrict num, size_t cap);
171 void bc_num_copy(BcNum *d, const BcNum *s);
172 void bc_num_createCopy(BcNum *d, const BcNum *s);
173 void bc_num_createFromBigdig(BcNum *n, BcBigDig val);
174 void bc_num_clear(BcNum *restrict n);
175 void bc_num_free(void *num);
176 
177 size_t bc_num_scale(const BcNum *restrict n);
178 size_t bc_num_len(const BcNum *restrict n);
179 
180 void bc_num_bigdig(const BcNum *restrict n, BcBigDig *result);
181 void bc_num_bigdig2(const BcNum *restrict n, BcBigDig *result);
182 void bc_num_bigdig2num(BcNum *restrict n, BcBigDig val);
183 
184 #if BC_ENABLE_EXTRA_MATH && BC_ENABLE_RAND
185 void bc_num_irand(const BcNum *restrict a, BcNum *restrict b,
186                       struct BcRNG *restrict rng);
187 void bc_num_rng(const BcNum *restrict n, struct BcRNG *rng);
188 void bc_num_createFromRNG(BcNum *restrict n, struct BcRNG *rng);
189 #endif // BC_ENABLE_EXTRA_MATH && BC_ENABLE_RAND
190 
191 void bc_num_add(BcNum *a, BcNum *b, BcNum *c, size_t scale);
192 void bc_num_sub(BcNum *a, BcNum *b, BcNum *c, size_t scale);
193 void bc_num_mul(BcNum *a, BcNum *b, BcNum *c, size_t scale);
194 void bc_num_div(BcNum *a, BcNum *b, BcNum *c, size_t scale);
195 void bc_num_mod(BcNum *a, BcNum *b, BcNum *c, size_t scale);
196 void bc_num_pow(BcNum *a, BcNum *b, BcNum *c, size_t scale);
197 #if BC_ENABLE_EXTRA_MATH
198 void bc_num_places(BcNum *a, BcNum *b, BcNum *c, size_t scale);
199 void bc_num_lshift(BcNum *a, BcNum *b, BcNum *c, size_t scale);
200 void bc_num_rshift(BcNum *a, BcNum *b, BcNum *c, size_t scale);
201 #endif // BC_ENABLE_EXTRA_MATH
202 void bc_num_sqrt(BcNum *restrict a, BcNum *restrict b, size_t scale);
203 void bc_num_divmod(BcNum *a, BcNum *b, BcNum *c, BcNum *d, size_t scale);
204 
205 size_t bc_num_addReq(const BcNum* a, const BcNum* b, size_t scale);
206 
207 size_t bc_num_mulReq(const BcNum *a, const BcNum *b, size_t scale);
208 size_t bc_num_powReq(const BcNum *a, const BcNum *b, size_t scale);
209 #if BC_ENABLE_EXTRA_MATH
210 size_t bc_num_placesReq(const BcNum *a, const BcNum *b, size_t scale);
211 #endif // BC_ENABLE_EXTRA_MATH
212 
213 void bc_num_truncate(BcNum *restrict n, size_t places);
214 ssize_t bc_num_cmp(const BcNum *a, const BcNum *b);
215 
216 #if DC_ENABLED
217 void bc_num_modexp(BcNum *a, BcNum *b, BcNum *c, BcNum *restrict d);
218 #endif // DC_ENABLED
219 
220 void bc_num_one(BcNum *restrict n);
221 ssize_t bc_num_cmpZero(const BcNum *n);
222 
223 void bc_num_parse(BcNum *restrict n, const char *restrict val,
224                       BcBigDig base, bool letter);
225 void bc_num_print(BcNum *restrict n, BcBigDig base, bool newline);
226 #if DC_ENABLED
227 void bc_num_stream(BcNum *restrict n, BcBigDig base);
228 #endif // DC_ENABLED
229 
230 #if BC_DEBUG_CODE
231 void bc_num_printDebug(const BcNum *n, const char *name, bool emptyline);
232 void bc_num_printDigs(const BcDig* n, size_t len, bool emptyline);
233 void bc_num_printWithDigs(const BcNum *n, const char *name, bool emptyline);
234 void bc_num_dump(const char *varname, const BcNum *n);
235 #endif // BC_DEBUG_CODE
236 
237 extern const char bc_num_hex_digits[];
238 extern const BcBigDig bc_num_pow10[BC_BASE_DIGS + 1];
239 
240 extern const BcDig bc_num_bigdigMax[];
241 extern const size_t bc_num_bigdigMax_size;
242 
243 #endif // BC_NUM_H
244