Introduction
Introduction Statistics Contact Development Disclaimer Help
libtfm.h - libzahl - big integer library
git clone git://git.suckless.org/libzahl
Log
Files
Refs
README
LICENSE
---
libtfm.h (7384B)
---
1 #include <tfm.h>
2
3 #include <setjmp.h>
4 #include <stddef.h>
5 #include <stdint.h>
6 #include <stdio.h>
7
8 #define BIGINT_LIBRARY "TomsFastMath"
9
10 #define FAST_RANDOM 0
11 #define SECURE_RANDOM 0
12 #define DEFAULT_RANDOM 0
13 #define FASTEST_RANDOM 0
14 #define LIBC_RAND_RANDOM 0
15 #define LIBC_RANDOM_RANDOM 0
16 #define LIBC_RAND48_RANDOM 0
17 #define QUASIUNIFORM 0
18 #define UNIFORM 1
19 #define MODUNIFORM 2
20
21 typedef fp_int z_t[1];
22
23 static z_t _0, _1, _a, _b;
24 static int _tmp, error;
25 static jmp_buf jbuf;
26
27 #ifdef ZAHL_UNSAFE
28 # define try(expr) (expr)
29 #else
30 # define try(expr) do if ((error = (expr))) longjmp(jbuf, 1); while (0)
31 #endif
32
33 static inline void
34 fp_set_int(z_t a, uint32_t d)
35 {
36 a->dp[0] = d;
37 a->used = !!d;
38 a->sign = 0;
39 }
40
41 static inline void
42 zsetup(jmp_buf env)
43 {
44 *jbuf = *env;
45 fp_init(_0);
46 fp_init(_1);
47 fp_init(_a);
48 fp_init(_b);
49 fp_set_int(_0, 0);
50 fp_set_int(_1, 1);
51 }
52
53 static inline void
54 zunsetup(void)
55 {
56 /* Do nothing */
57 }
58
59 static inline void
60 zperror(const char *str)
61 {
62 const char *serr;
63 switch (error) {
64 case FP_VAL: serr = "FP_VAL"; break;
65 case FP_MEM: serr = "FP_MEM"; break;
66 default: serr = "unknown error"; break;
67 }
68 if (str && *str)
69 fprintf(stderr, "%s: %s\n", str, serr);
70 else
71 fprintf(stderr, "%s\n", serr);
72 }
73
74 static inline void
75 zinit(z_t a)
76 {
77 fp_init(a);
78 }
79
80 static inline void
81 zfree(z_t a)
82 {
83 (void) a;
84 }
85
86 static inline void
87 zadd(z_t r, z_t a, z_t b)
88 {
89 fp_add(a, b, r);
90 }
91
92 static inline void
93 zsub(z_t r, z_t a, z_t b)
94 {
95 fp_sub(a, b, r);
96 }
97
98 static inline void
99 zset(z_t r, z_t a)
100 {
101 fp_copy(a, r);
102 }
103
104 static inline int
105 zeven(z_t a)
106 {
107 return fp_iseven(a);
108 }
109
110 static inline int
111 zodd(z_t a)
112 {
113 return fp_isodd(a);
114 }
115
116 static inline int
117 zeven_nonzero(z_t a)
118 {
119 return fp_iseven(a);
120 }
121
122 static inline int
123 zodd_nonzero(z_t a)
124 {
125 return fp_isodd(a);
126 }
127
128 static inline int
129 zzero(z_t a)
130 {
131 return fp_iszero(a);
132 }
133
134 static inline int
135 zsignum(z_t a)
136 {
137 return fp_cmp(a, _0);
138 }
139
140 static inline size_t
141 zbits(z_t a)
142 {
143 return fp_count_bits(a);
144 }
145
146 static inline size_t
147 zlsb(z_t a)
148 {
149 return fp_cnt_lsb(a);
150 }
151
152 static inline void
153 zlsh(z_t r, z_t a, size_t b)
154 {
155 fp_mul_2d(a, b, r);
156 }
157
158 static inline void
159 zrsh(z_t r, z_t a, size_t b)
160 {
161 fp_div_2d(a, b, r, 0);
162 }
163
164 static inline void
165 ztrunc(z_t r, z_t a, size_t b)
166 {
167 fp_mod_2d(a, b, r);
168 }
169
170 static inline void
171 zgcd(z_t r, z_t a, z_t b)
172 {
173 fp_gcd(a, b, r);
174 }
175
176 static inline void
177 zmul(z_t r, z_t a, z_t b)
178 {
179 fp_mul(a, b, r);
180 }
181
182 static inline void
183 zsqr(z_t r, z_t a)
184 {
185 fp_sqr(a, r);
186 }
187
188 static inline void
189 zmodmul(z_t r, z_t a, z_t b, z_t m)
190 {
191 try(fp_mulmod(a, b, m, r));
192 }
193
194 static inline void
195 zmodsqr(z_t r, z_t a, z_t m)
196 {
197 try(fp_sqrmod(a, m, r));
198 }
199
200 static inline void
201 zsets(z_t a, char *s)
202 {
203 try(fp_read_radix(a, s, 10));
204 }
205
206 static inline size_t
207 zstr_length(z_t a, unsigned long long int b)
208 {
209 try(fp_radix_size(a, b, &_tmp));
210 return _tmp;
211 }
212
213 static inline char *
214 zstr(z_t a, char *s, size_t n)
215 {
216 try(fp_toradix(a, s, 10));
217 return s;
218 (void) n;
219 }
220
221 static inline int
222 zptest(z_t w, z_t a, int t)
223 {
224 return fp_isprime_ex(a, t);
225 (void) w; /* Note, the witness is not returned. */
226 }
227
228 static inline void
229 zdivmod(z_t q, z_t r, z_t a, z_t b)
230 {
231 try(fp_div(a, b, q, r));
232 }
233
234 static inline void
235 zdiv(z_t q, z_t a, z_t b)
236 {
237 zdivmod(q, 0, a, b);
238 }
239
240 static inline void
241 zmod(z_t r, z_t a, z_t b)
242 {
243 try(fp_mod(a, b, r));
244 }
245
246 static inline void
247 zneg(z_t r, z_t a)
248 {
249 fp_neg(a, r);
250 }
251
252 static inline void
253 zabs(z_t r, z_t a)
254 {
255 fp_abs(a, r);
256 }
257
258 static inline void
259 zadd_unsigned(z_t r, z_t a, z_t b)
260 {
261 zabs(_a, a);
262 zabs(_b, b);
263 zadd(r, _a, _b);
264 }
265
266 static inline void
267 zsub_unsigned(z_t r, z_t a, z_t b)
268 {
269 zabs(_a, a);
270 zabs(_b, b);
271 zsub(r, _a, _b);
272 }
273
274 static inline void
275 zswap(z_t a, z_t b)
276 {
277 z_t t;
278 zset(t, a);
279 zset(a, b);
280 zset(b, t);
281 }
282
283 static inline void
284 zand(z_t r, z_t a, z_t b)
285 {
286 int i;
287 for (i = 0; i < a->used && i < b->used; i++)
288 r->dp[i] = a->dp[i] & b->dp[i];
289 r->used = i;
290 while (r->used && !r->dp[r->used])
291 r->used--;
292 r->sign = a->sign & b->sign;
293 }
294
295 static inline void
296 zor(z_t r, z_t a, z_t b)
297 {
298 int i;
299 for (i = 0; i < a->used && i < b->used; i++)
300 r->dp[i] = a->dp[i] | b->dp[i];
301 for (; i < a->used; i++)
302 r->dp[i] = a->dp[i];
303 for (; i < b->used; i++)
304 r->dp[i] = b->dp[i];
305 r->used = i;
306 r->sign = a->sign | b->sign;
307 }
308
309 static inline void
310 zxor(z_t r, z_t a, z_t b)
311 {
312 int i;
313 for (i = 0; i < a->used && i < b->used; i++)
314 r->dp[i] = a->dp[i] ^ b->dp[i];
315 for (; i < a->used; i++)
316 r->dp[i] = a->dp[i];
317 for (; i < b->used; i++)
318 r->dp[i] = b->dp[i];
319 r->used = i;
320 while (r->used && !r->dp[r->used])
321 r->used--;
322 r->sign = a->sign ^ b->sign;
323 }
324
325 static inline size_t
326 zsave(z_t a, char *s)
327 {
328 _tmp = !s ? fp_signed_bin_size(a) : (fp_to_signed_bin(a, (unsign…
329 return _tmp;
330 }
331
332 static inline size_t
333 zload(z_t a, const char *s)
334 {
335 fp_read_signed_bin(a, (unsigned char *)s, _tmp);
336 return _tmp;
337 }
338
339 static inline void
340 zsetu(z_t r, unsigned long long int val)
341 {
342 uint32_t high = (uint32_t)(val >> 32);
343 uint32_t low = (uint32_t)val;
344
345 if (high) {
346 fp_set_int(r, high);
347 fp_set_int(_a, low);
348 fp_lshd(r, 32);
349 zadd(r, r, _a);
350 } else {
351 fp_set_int(r, low);
352 }
353
354 }
355
356 static inline void
357 zseti(z_t r, long long int val)
358 {
359 if (val >= 0) {
360 zsetu(r, (unsigned long long int)val);
361 } else {
362 zsetu(r, (unsigned long long int)-val);
363 zneg(r, r);
364 }
365 }
366
367 static inline int
368 zcmpmag(z_t a, z_t b)
369 {
370 return fp_cmp_mag(a, b);
371 }
372
373 static inline int
374 zcmp(z_t a, z_t b)
375 {
376 return fp_cmp(a, b);
377 }
378
379 static inline int
380 zcmpi(z_t a, long long int b)
381 {
382 zseti(_b, b);
383 return zcmp(a, _b);
384 }
385
386 static inline int
387 zcmpu(z_t a, unsigned long long int b)
388 {
389 zsetu(_b, b);
390 return zcmp(a, _b);
391 }
392
393 static inline void
394 zsplit(z_t high, z_t low, z_t a, size_t brk)
395 {
396 if (low == a) {
397 zrsh(high, a, brk);
398 ztrunc(low, a, brk);
399 } else {
400 ztrunc(low, a, brk);
401 zrsh(high, a, brk);
402 }
403 }
404
405 static inline void
406 znot(z_t r, z_t a)
407 {
408 fp_2expt(_a, zbits(a));
409 fp_sub_d(_a, 1, _a);
410 zand(r, a, _a);
411 zneg(r, r);
412 }
413
414 static inline int
415 zbtest(z_t a, size_t bit)
416 {
417 fp_2expt(_b, bit);
418 zand(_b, a, _b);
419 return !zzero(_b);
420 }
421
422 static inline void
423 zbset(z_t r, z_t a, size_t bit, int mode)
424 {
425 if (mode > 0) {
426 fp_2expt(_b, bit);
427 zor(r, a, _b);
428 } else if (mode < 0 || zbtest(a, bit)) {
429 fp_2expt(_b, bit);
430 zxor(r, a, _b);
431 }
432 }
433
434 static inline void
435 zrand(z_t r, int dev, int dist, z_t n)
436 {
437 static int gave_up = 0;
438 int bits;
439 (void) dev;
440
441 if (zzero(n)) {
442 fp_zero(r);
443 return;
444 }
445 if (zsignum(n) < 0) {
446 return;
447 }
448
449 bits = zbits(n);
450
451 switch (dist) {
452 case QUASIUNIFORM:
453 fp_rand(r, bits);
454 zadd(r, r, _1);
455 zmul(r, r, n);
456 zrsh(r, r, bits);
457 break;
458
459 case UNIFORM:
460 if (!gave_up) {
461 gave_up = 1;
462 printf("I'm sorry, this is too difficult, I give…
463 }
464 break;
465
466 case MODUNIFORM:
467 fp_rand(r, bits);
468 if (zcmp(r, n) > 0)
469 zsub(r, r, n);
470 break;
471
472 default:
473 abort();
474 }
475 }
476
477 static inline void
478 zpowu(z_t r, z_t a, unsigned long long int b)
479 {
480 if (!b) {
481 if (zzero(a)) {
482 error = FP_VAL;
483 longjmp(jbuf, 1);
484 }
485 zsetu(r, 1);
486 return;
487 }
488 zset(_a, a);
489 zsetu(r, 1);
490 for (; b; b >>= 1) {
491 if (b & 1)
492 zmul(r, r, _a);
493 zsqr(_a, _a);
494 }
495 }
496
497 static inline void
498 zpow(z_t r, z_t a, z_t b)
499 {
500 zpowu(r, a, b->used ? b->dp[0] : 0);
501 }
502
503 static inline void
504 zmodpow(z_t r, z_t a, z_t b, z_t m)
505 {
506 try(fp_exptmod(a, b, m, r));
507 }
508
509 static inline void
510 zmodpowu(z_t r, z_t a, unsigned long long int b, z_t m)
511 {
512 fp_set_int(_b, b);
513 zmodpow(r, a, _b, m);
514 }
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.