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) |