internals.h - libzahl - big integer library
(HTM) git clone git://git.suckless.org/libzahl
(DIR) Log
(DIR) Files
(DIR) Refs
(DIR) README
(DIR) LICENSE
---
internals.h (11600B)
---
1 /* See LICENSE file for copyright and license details. */
2 #include "../zahl.h"
3
4 #include <errno.h>
5 #include <stdlib.h>
6 #include <string.h>
7
8 /* clang pretends to be GCC... */
9 #if defined(__GNUC__) && defined(__clang__)
10 # undef __GNUC__
11 #endif
12
13 #define BITS_PER_CHAR ZAHL_BITS_PER_CHAR
14 #define LB_BITS_PER_CHAR ZAHL_LB_BITS_PER_CHAR
15
16 #define FLOOR_BITS_TO_CHARS(bits) ZAHL_FLOOR_BITS_TO_CHARS(bits)
17 #define CEILING_BITS_TO_CHARS(bits) ZAHL_CEILING_BITS_TO_CHARS(bits)
18 #define BITS_IN_LAST_CHAR(bits) ZAHL_BITS_IN_LAST_CHAR(bits)
19 #define TRUNCATE_TO_CHAR(bits) ZAHL_TRUNCATE_TO_CHAR(bits)
20
21 #define O0 ZAHL_O0
22 #define O1 ZAHL_O1
23 #define O2 ZAHL_O2
24 #define O3 ZAHL_O3
25 #define Ofast ZAHL_Ofast
26 #define Os ZAHL_Os
27 #define Oz ZAHL_Oz
28
29 #define LIST_TEMPS_HERE\
30 X(libzahl_tmp_str_num, 0)\
31 X(libzahl_tmp_str_mag, 0)\
32 X(libzahl_tmp_str_div, 0)\
33 X(libzahl_tmp_str_rem, 0)\
34 X(libzahl_tmp_gcd_u, 0)\
35 X(libzahl_tmp_gcd_v, 0)\
36 X(libzahl_tmp_sub, 0)\
37 X(libzahl_tmp_modmul, 0)\
38 X(libzahl_tmp_pow_b, 0)\
39 X(libzahl_tmp_pow_c, 0)\
40 X(libzahl_tmp_pow_d, 0)\
41 X(libzahl_tmp_modsqr, 0)\
42 X(libzahl_tmp_divmod_a, 0)\
43 X(libzahl_tmp_divmod_b, 0)\
44 X(libzahl_tmp_divmod_d, 0)\
45 X(libzahl_tmp_ptest_x, 0)\
46 X(libzahl_tmp_ptest_a, 0)\
47 X(libzahl_tmp_ptest_d, 0)\
48 X(libzahl_tmp_ptest_n1, 0)\
49 X(libzahl_tmp_ptest_n4, 0)
50
51 #define LIST_TEMPS\
52 X(libzahl_tmp_div, 0)\
53 X(libzahl_tmp_mod, 0)\
54 LIST_TEMPS_HERE
55
56 #define LIST_CONSTS\
57 X(0, libzahl_const_1e19, zsetu, 10000000000000000000ULL) /* The largest power of 10 < 2⁶⁴. */\
58 X(1, libzahl_const_1, zsetu, 1)\
59 X(2, libzahl_const_2, zsetu, 2)\
60 X(3, libzahl_const_4, zsetu, 4)
61
62 #define X(x, s) extern z_t x;
63 LIST_TEMPS_HERE
64 #undef X
65 #define X(i, x, f, v) extern z_t x;
66 LIST_CONSTS
67 #undef X
68
69 extern z_t libzahl_tmp_divmod_ds[BITS_PER_CHAR];
70 extern jmp_buf libzahl_jmp_buf;
71 extern int libzahl_set_up;
72 extern int libzahl_error;
73 extern zahl_char_t **libzahl_pool[sizeof(size_t) * 8];
74 extern size_t libzahl_pool_n[sizeof(size_t) * 8];
75 extern size_t libzahl_pool_alloc[sizeof(size_t) * 8];
76 extern struct zahl **libzahl_temp_stack;
77 extern struct zahl **libzahl_temp_stack_head;
78 extern struct zahl **libzahl_temp_stack_end;
79 extern void *libzahl_temp_allocation;
80
81 #define likely(expr) ZAHL_LIKELY(expr)
82 #define unlikely(expr) ZAHL_UNLIKELY(expr)
83
84 #if defined(ZAHL_UNSAFE)
85 # define check(expr) 0
86 #else
87 # define check(expr) unlikely(expr)
88 #endif
89
90 #define SET_SIGNUM(a, signum) ZAHL_SET_SIGNUM(a, signum)
91 #define SET(a, b) ZAHL_SET(a, b)
92 #define ENSURE_SIZE(a, n) ZAHL_ENSURE_SIZE(a, n)
93 #define TRIM(a) ZAHL_TRIM(a)
94 #define TRIM_NONZERO(a) ZAHL_TRIM_NONZERO(a)
95 #define TRIM_AND_ZERO(a) ZAHL_TRIM_AND_ZERO(a)
96 #define TRIM_AND_SIGN(a, s) ZAHL_TRIM_AND_SIGN(a, s)
97 #define SWAP(a, b, t, m) ((t)->m = (a)->m, (a)->m = (b)->m, (b)->m = (t)->m)
98 #define MIN(a, b) ((a) < (b) ? (a) : (b))
99 #define MAX(a, b) ((a) > (b) ? (a) : (b))
100 #define MIN_MAX_1(min, max, a, b) ((min) = MIN(a, b), (max) = MAX(a, b))
101 #define MIN_MAX_2(min, max, a, b) ((min) = (a) + (b) - ((max) = MAX(a, b)))
102 #define znegative(a) (zsignum(a) < 0)
103 #define znegative1(a, b) ((zsignum(a) | zsignum(b)) < 0)
104 #define znegative2(a, b) ((zsignum(a) & zsignum(b)) < 0)
105 #define zpositive(a) (zsignum(a) > 0)
106 #define zpositive1(a, b) (zpositive(a) + zpositive(b) > 0)
107 #define zpositive2(a, b) (zsignum(a) + zsignum(b) == 2)
108 #define zzero2(a, b) (!(zsignum(a) | zsignum(b)))
109 #define zmemcpy(d, s, n) libzahl_memcpy(d, s, n)
110 #define zmemmove(d, s, n) libzahl_memmove(d, s, n)
111 #define zmemmovef(d, s, n) libzahl_memmovef(d, s, n)
112 #define zmemmoveb(d, s, n) libzahl_memmoveb(d, s, n)
113 #define zmemset(a, v, n) libzahl_memset(a, v, n)
114 #define zmemset_precise(a, v, n) libzahl_memset_precise(a, v, n)
115
116 static inline int
117 zzero1(z_t a, z_t b)
118 {
119 return zzero(a) || zzero(b);
120 }
121
122 static inline void
123 zmemcpy_range(register zahl_char_t *restrict d, register const zahl_char_t *restrict s, size_t i, size_t n)
124 {
125 d += i;
126 s += i;
127 n -= i;
128 zmemcpy(d, s, n);
129 }
130
131 static void
132 libzahl_failure(int error)
133 {
134 libzahl_error = (error);
135 if (libzahl_temp_stack)
136 while (libzahl_temp_stack_head != libzahl_temp_stack)
137 zfree(*--libzahl_temp_stack_head);
138 free(libzahl_temp_allocation);
139 libzahl_temp_allocation = 0;
140 longjmp(libzahl_jmp_buf, 1);
141 }
142
143 static inline void
144 libzahl_memfailure(void)
145 {
146 if (!errno) /* sigh... */
147 errno = ENOENT;
148 libzahl_failure(errno);
149 }
150
151 /*
152 * libzahl_msb_nz_zu
153 * ^^^ ^^ ^^
154 * | | |
155 * | | \- size_t parameter
156 * | \- non-zero input
157 * \- most significant bit
158 */
159
160 #if SIZE_MAX == ULONG_MAX
161 # define libzahl_msb_nz_zu(x) libzahl_msb_nz_lu(x)
162 #else
163 # define libzahl_msb_nz_zu(x) libzahl_msb_nz_llu(x)
164 #endif
165
166 #if defined(__GNUC__) || defined(__clang__)
167 # define libzahl_msb_nz_lu(x) (8 * sizeof(unsigned long int) - 1 - (size_t)__builtin_clzl(x))
168 # define libzahl_msb_nz_llu(x) (8 * sizeof(unsigned long long int) - 1 - (size_t)__builtin_clzll(x))
169 #else
170 static inline size_t
171 libzahl_msb_nz_lu(unsigned long int x)
172 {
173 size_t r = 0;
174 for (; x; x >>= 1, r++);
175 return r - 1;
176 }
177
178 static inline size_t
179 libzahl_msb_nz_llu(unsigned long long int x)
180 {
181 size_t r = 0;
182 for (; x; x >>= 1, r++);
183 return r - 1;
184 }
185 #endif
186
187 #if defined(__GNUC__) || defined(__clang__)
188 # if INT64_MAX == LONG_MAX
189 # define libzahl_add_overflow(rp, a, b) __builtin_uaddl_overflow(a, b, rp)
190 # else
191 # define libzahl_add_overflow(rp, a, b) __builtin_uaddll_overflow(a, b, rp)
192 # endif
193 #else
194 static inline int
195 libzahl_add_overflow(zahl_char_t *rp, zahl_char_t a, zahl_char_t b)
196 {
197 int carry = ZAHL_CHAR_MAX - a < b;
198 *rp = a + b;
199 return carry;
200 }
201 #endif
202
203 static inline void
204 zsplit_pz(z_t high, z_t low, z_t a, size_t delim)
205 {
206 if (unlikely(zzero(a))) {
207 SET_SIGNUM(high, 0);
208 SET_SIGNUM(low, 0);
209 } else {
210 zsplit(high, low, a, delim);
211 }
212 }
213
214 static inline void
215 zrsh_taint(z_t a, size_t bits)
216 {
217 size_t i, chars, cbits;
218
219 if (unlikely(!bits))
220 return;
221 if (unlikely(zzero(a)))
222 return;
223
224 chars = FLOOR_BITS_TO_CHARS(bits);
225
226 if (unlikely(chars >= a->used || zbits(a) <= bits)) {
227 SET_SIGNUM(a, 0);
228 return;
229 }
230
231 bits = BITS_IN_LAST_CHAR(bits);
232 cbits = BITS_PER_CHAR - bits;
233
234 if (likely(chars)) {
235 a->used -= chars;
236 a->chars += chars;
237 }
238
239 if (unlikely(bits)) { /* This if statement is very important in C. */
240 a->chars[0] >>= bits;
241 for (i = 1; i < a->used; i++) {
242 a->chars[i - 1] |= a->chars[i] << cbits;
243 a->chars[i] >>= bits;
244 }
245 TRIM_NONZERO(a);
246 }
247 }
248
249 static inline void
250 zswap_tainted_unsigned(z_t a, z_t b)
251 {
252 z_t t;
253 SWAP(a, b, t, used);
254 SWAP(b, a, t, chars);
255 }
256
257 static inline void
258 zsplit_unsigned_fast_large_taint(z_t high, z_t low, z_t a, size_t n)
259 {
260 n >>= LB_BITS_PER_CHAR;
261 high->sign = 1;
262 high->used = a->used - n;
263 high->chars = a->chars + n;
264 #if 0
265 TRIM_AND_ZERO(high);
266 #endif
267 low->sign = 1;
268 low->used = n;
269 low->chars = a->chars;
270 TRIM_AND_ZERO(low);
271 }
272
273 static inline void
274 zsplit_unsigned_fast_small_auto(z_t high, z_t low, z_t a, size_t n)
275 {
276 zahl_char_t mask = 1;
277 mask = (mask << n) - 1;
278
279 high->sign = 1;
280 high->used = 1;
281 high->chars[0] = a->chars[0] >> n;
282 if (a->used == 2) {
283 high->chars[1] = a->chars[1] >> n;
284 high->used += !!high->chars[1];
285 n = BITS_PER_CHAR - n;
286 high->chars[0] |= (a->chars[1] & mask) << n;
287 }
288 #if 0
289 if (unlikely(!high->chars[high->used - 1]))
290 high->sign = 0;
291 #endif
292
293 low->sign = 1;
294 low->used = 1;
295 low->chars[0] = a->chars[0] & mask;
296 if (unlikely(!low->chars[0]))
297 low->sign = 0;
298 }
299
300 /* Calls to these functions must be called in stack-order
301 * For example,
302 *
303 * zinit_temp(a);
304 * zinit_temp(b);
305 * zfree_temp(b);
306 * zinit_temp(c);
307 * zfree_temp(c);
308 * zfree_temp(a);
309 *
310 * And not (swap the two last lines)
311 *
312 * zinit_temp(a);
313 * zinit_temp(b);
314 * zfree_temp(b);
315 * zinit_temp(c);
316 * zfree_temp(a);
317 * zfree_temp(c);
318 *
319 * { */
320
321 static inline void
322 zinit_temp(z_t a)
323 {
324 zinit(a);
325 if (unlikely(libzahl_temp_stack_head == libzahl_temp_stack_end)) {
326 size_t n = (size_t)(libzahl_temp_stack_end - libzahl_temp_stack);
327 void* old = libzahl_temp_stack;
328 libzahl_temp_stack = realloc(old, 2 * n * sizeof(*libzahl_temp_stack));
329 if (check(!libzahl_temp_stack)) {
330 libzahl_temp_stack = old;
331 libzahl_memfailure();
332 }
333 libzahl_temp_stack_head = libzahl_temp_stack + n;
334 libzahl_temp_stack_end = libzahl_temp_stack_head + n;
335 }
336 *libzahl_temp_stack_head++ = a;
337 }
338
339 static inline void
340 zfree_temp(z_t a)
341 {
342 zfree(a);
343 libzahl_temp_stack_head--;
344 }
345
346 /* } */
347
348 #define ZMEM_2OP_PRECISE(a, b, c, n, OP) \
349 do { \
350 zahl_char_t *a__ = (a); \
351 const zahl_char_t *b__ = (b); \
352 const zahl_char_t *c__ = (c); \
353 size_t i__, n__ = (n); \
354 if (n__ <= 4) { \
355 if (n__ >= 1) \
356 a__[0] = b__[0] OP c__[0]; \
357 if (n__ >= 2) \
358 a__[1] = b__[1] OP c__[1]; \
359 if (n__ >= 3) \
360 a__[2] = b__[2] OP c__[2]; \
361 if (n__ >= 4) \
362 a__[3] = b__[3] OP c__[3]; \
363 } else { \
364 for (i__ = 0; (i__ += 4) < n__;) { \
365 a__[i__ - 1] = b__[i__ - 1] OP c__[i__ - 1]; \
366 a__[i__ - 2] = b__[i__ - 2] OP c__[i__ - 2]; \
367 a__[i__ - 3] = b__[i__ - 3] OP c__[i__ - 3]; \
368 a__[i__ - 4] = b__[i__ - 4] OP c__[i__ - 4]; \
369 } \
370 if (i__ > n__) \
371 for (i__ -= 4; i__ < n__; i__++) \
372 a__[i__] = b__[i__] OP c__[i__]; \
373 } \
374 } while (0)
375
376 #define ZMEM_2OP(a, b, c, n, OP) \
377 do { \
378 zahl_char_t *a__ = (a); \
379 const zahl_char_t *b__ = (b); \
380 const zahl_char_t *c__ = (c); \
381 size_t i__, n__ = (n); \
382 for (i__ = 0; i__ < n__; i__ += 4) { \
383 a__[i__ + 0] = b__[i__ + 0] OP c__[i__ + 0]; \
384 a__[i__ + 1] = b__[i__ + 1] OP c__[i__ + 1]; \
385 a__[i__ + 2] = b__[i__ + 2] OP c__[i__ + 2]; \
386 a__[i__ + 3] = b__[i__ + 3] OP c__[i__ + 3]; \
387 } \
388 } while (0)
389
390 #define ZMEM_1OP(a, b, n, OP) \
391 do { \
392 zahl_char_t *a__ = (a); \
393 const zahl_char_t *b__ = (b); \
394 size_t i__, n__ = (n); \
395 for (i__ = 0; i__ < n__; i__ += 4) { \
396 a__[i__ + 0] = OP(b__[i__ + 0]); \
397 a__[i__ + 1] = OP(b__[i__ + 1]); \
398 a__[i__ + 2] = OP(b__[i__ + 2]); \
399 a__[i__ + 3] = OP(b__[i__ + 3]); \
400 } \
401 } while (0)