Introduction
Introduction Statistics Contact Development Disclaimer Help
internals.h - libzahl - big integer library
git clone git://git.suckless.org/libzahl
Log
Files
Refs
README
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 …
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, …
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, …
101 #define MIN_MAX_2(min, max, a, b) ((min) = (a) + (b) - ((max) = MAX(a…
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…
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 …
168 # define libzahl_msb_nz_llu(x) (8 * sizeof(unsigned long long int)…
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,…
190 # else
191 # define libzahl_add_overflow(rp, a, b) __builtin_uaddll_overflow(a, b…
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 …
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_tem…
327 void* old = libzahl_temp_stack;
328 libzahl_temp_stack = realloc(old, 2 * n * sizeof(*libzah…
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__ -…
366 a__[i__ - 2] = b__[i__ - 2] OP c__[i__ -…
367 a__[i__ - 3] = b__[i__ - 3] OP c__[i__ -…
368 a__[i__ - 4] = b__[i__ - 4] OP c__[i__ -…
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)
You are viewing proxied material from suckless.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.