libtommath.h - libzahl - big integer library
(HTM) git clone git://git.suckless.org/libzahl
(DIR) Log
(DIR) Files
(DIR) Refs
(DIR) README
(DIR) LICENSE
---
libtommath.h (6423B)
---
1 #include <tommath.h>
2
3 #include <setjmp.h>
4 #include <stddef.h>
5 #include <stdint.h>
6 #include <stdio.h>
7
8 #define BIGINT_LIBRARY "libtommath"
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 mp_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 zsetup(jmp_buf env)
35 {
36 *jbuf = *env;
37 try(mp_init_set_int(_0, 0));
38 try(mp_init_set_int(_1, 1));
39 try(mp_init(_a));
40 try(mp_init(_b));
41 }
42
43 static inline void
44 zunsetup(void)
45 {
46 mp_clear(_0);
47 mp_clear(_1);
48 mp_clear(_a);
49 mp_clear(_b);
50 }
51
52 static inline void
53 zperror(const char *str)
54 {
55 if (str && *str)
56 fprintf(stderr, "%s: %s\n", str, mp_error_to_string(error));
57 else
58 fprintf(stderr, "%s\n", mp_error_to_string(error));
59 }
60
61 static inline void
62 zinit(z_t a)
63 {
64 try(mp_init(a));
65 }
66
67 static inline void
68 zfree(z_t a)
69 {
70 mp_clear(a);
71 }
72
73 static inline void
74 zset(z_t r, z_t a)
75 {
76 try(mp_copy(a, r));
77 }
78
79 static inline void
80 zneg(z_t r, z_t a)
81 {
82 try(mp_neg(a, r));
83 }
84
85 static inline void
86 zabs(z_t r, z_t a)
87 {
88 try(mp_abs(a, r));
89 }
90
91 static inline void
92 zadd(z_t r, z_t a, z_t b)
93 {
94 try(mp_add(a, b, r));
95 }
96
97 static inline void
98 zsub(z_t r, z_t a, z_t b)
99 {
100 try(mp_sub(a, b, r));
101 }
102
103 static inline void
104 zadd_unsigned(z_t r, z_t a, z_t b)
105 {
106 zabs(_a, a);
107 zabs(_b, b);
108 zadd(r, _a, _b);
109 }
110
111 static inline void
112 zsub_unsigned(z_t r, z_t a, z_t b)
113 {
114 zabs(_a, a);
115 zabs(_b, b);
116 zsub(r, _a, _b);
117 }
118
119 static inline size_t
120 zbits(z_t a)
121 {
122 return mp_count_bits(a);
123 }
124
125 static inline size_t
126 zlsb(z_t a)
127 {
128 return mp_cnt_lsb(a);
129 }
130
131 static inline int
132 zeven(z_t a)
133 {
134 return mp_iseven(a);
135 }
136
137 static inline int
138 zodd(z_t a)
139 {
140 return mp_isodd(a);
141 }
142
143 static inline int
144 zeven_nonzero(z_t a)
145 {
146 return zeven(a);
147 }
148
149 static inline int
150 zodd_nonzero(z_t a)
151 {
152 return zodd(a);
153 }
154
155 static inline int
156 zzero(z_t a)
157 {
158 return mp_iszero(a);
159 }
160
161 static inline void
162 zand(z_t r, z_t a, z_t b)
163 {
164 try(mp_and(a, b, r));
165 }
166
167 static inline void
168 zor(z_t r, z_t a, z_t b)
169 {
170 try(mp_or(a, b, r));
171 }
172
173 static inline void
174 zxor(z_t r, z_t a, z_t b)
175 {
176 try(mp_xor(a, b, r));
177 }
178
179 static inline void
180 znot(z_t r, z_t a)
181 {
182 try(mp_2expt(_a, (int)zbits(a)));
183 try(mp_sub_d(_a, 1, _a));
184 zand(r, a, _a);
185 zneg(r, r);
186 }
187
188 static inline int
189 zbtest(z_t a, size_t bit)
190 {
191 try(mp_2expt(_b, (int)bit));
192 zand(_b, a, _b);
193 return !zzero(_b);
194 }
195
196 static inline void
197 zbset(z_t r, z_t a, size_t bit, int mode)
198 {
199 if (mode > 0) {
200 try(mp_2expt(_b, (int)bit));
201 zor(r, a, _b);
202 } else if (mode < 0 || zbtest(a, bit)) {
203 try(mp_2expt(_b, (int)bit));
204 zxor(r, a, _b);
205 }
206 }
207
208 static inline void
209 zswap(z_t a, z_t b)
210 {
211 mp_exch(a, b);
212 }
213
214 static inline void
215 zlsh(z_t r, z_t a, size_t b)
216 {
217 try(mp_mul_2d(a, (int)b, r));
218 }
219
220 static inline void
221 zrsh(z_t r, z_t a, size_t b)
222 {
223 try(mp_div_2d(a, (int)b, r, 0));
224 }
225
226 static inline void
227 ztrunc(z_t r, z_t a, size_t b)
228 {
229 try(mp_mod_2d(a, (int)b, r));
230 }
231
232 static inline void
233 zsplit(z_t high, z_t low, z_t a, size_t brk)
234 {
235 if (low == a) {
236 zrsh(high, a, brk);
237 ztrunc(low, a, brk);
238 } else {
239 ztrunc(low, a, brk);
240 zrsh(high, a, brk);
241 }
242 }
243
244 static inline void
245 zsetu(z_t r, unsigned long long int val)
246 {
247 try(mp_set_long_long(r, val));
248 }
249
250 static inline void
251 zseti(z_t r, long long int val)
252 {
253 if (val >= 0) {
254 zsetu(r, (unsigned long long int)val);
255 } else {
256 zsetu(r, (unsigned long long int)-val);
257 zneg(r, r);
258 }
259 }
260
261 static inline int
262 zcmpmag(z_t a, z_t b)
263 {
264 return mp_cmp_mag(a, b);
265 }
266
267 static inline int
268 zcmp(z_t a, z_t b)
269 {
270 return mp_cmp(a, b);
271 }
272
273 static inline int
274 zcmpi(z_t a, long long int b)
275 {
276 zseti(_b, b);
277 return zcmp(a, _b);
278 }
279
280 static inline int
281 zcmpu(z_t a, unsigned long long int b)
282 {
283 zsetu(_b, b);
284 return zcmp(a, _b);
285 }
286
287 static inline int
288 zsignum(z_t a)
289 {
290 return zcmp(a, _0);
291 }
292
293 static inline void
294 zgcd(z_t r, z_t a, z_t b)
295 {
296 try(mp_gcd(a, b, r));
297 }
298
299 static inline void
300 zmul(z_t r, z_t a, z_t b)
301 {
302 try(mp_mul(a, b, r));
303 }
304
305 static inline void
306 zsqr(z_t r, z_t a)
307 {
308 try(mp_sqr(a, r));
309 }
310
311 static inline void
312 zmodmul(z_t r, z_t a, z_t b, z_t m)
313 {
314 try(mp_mulmod(a, b, m, r));
315 }
316
317 static inline void
318 zmodsqr(z_t r, z_t a, z_t m)
319 {
320 try(mp_sqrmod(a, m, r));
321 }
322
323 static inline void
324 zpow(z_t r, z_t a, z_t b)
325 {
326 try(mp_expt_d(a, (mp_digit)mp_get_int(b), r));
327 }
328
329 static inline void
330 zpowu(z_t r, z_t a, unsigned long long int b)
331 {
332 try(mp_expt_d(a, (mp_digit)b, r));
333 }
334
335 static inline void
336 zmodpow(z_t r, z_t a, z_t b, z_t m)
337 {
338 try(mp_exptmod(a, b, m, r));
339 }
340
341 static inline void
342 zmodpowu(z_t r, z_t a, unsigned long long int b, z_t m)
343 {
344 try(mp_set_int(_b, b));
345 try(mp_exptmod(a, _b, m, r));
346 }
347
348 static inline void
349 zsets(z_t a, const char *s)
350 {
351 try(mp_read_radix(a, s, 10));
352 }
353
354 static inline size_t
355 zstr_length(z_t a, size_t b)
356 {
357 try(mp_radix_size(a, b, &_tmp));
358 return _tmp;
359 }
360
361 static inline char *
362 zstr(z_t a, char *s, size_t n)
363 {
364 try(mp_toradix(a, s, 10));
365 return s;
366 (void) n;
367 }
368
369 static inline int
370 zptest(z_t w, z_t a, int t)
371 {
372 try(mp_prime_is_prime(a, t, &_tmp));
373 return _tmp;
374 (void) w; /* Note, the witness is not returned. */
375 }
376
377 static inline size_t
378 zsave(z_t a, char *b)
379 {
380 _tmp = !b ? mp_signed_bin_size(a) : mp_to_signed_bin(a, (unsigned char *)b);
381 return _tmp;
382 }
383
384 static inline size_t
385 zload(z_t a, const char *b) /* Note, requires that zsave was called directly prior. */
386 {
387 return mp_read_signed_bin(a, (const unsigned char *)b, _tmp);
388 }
389
390 static inline void
391 zdiv(z_t r, z_t a, z_t b)
392 {
393 try(mp_div(a, b, r, 0));
394 }
395
396 static inline void
397 zmod(z_t r, z_t a, z_t b)
398 {
399 try(mp_mod(a, b, r));
400 }
401
402 static inline void
403 zdivmod(z_t q, z_t r, z_t a, z_t b)
404 {
405 try(mp_div(a, b, q, r));
406 }
407
408 static inline void
409 zrand(z_t r, int dev, int dist, z_t n)
410 {
411 static int gave_up = 0;
412 int bits;
413 (void) dev;
414
415 if (zzero(n)) {
416 mp_zero(r);
417 return;
418 }
419 if (zsignum(n) < 0) {
420 return;
421 }
422
423 bits = zbits(n);
424
425 switch (dist) {
426 case QUASIUNIFORM:
427 try(mp_rand(r, bits));
428 zadd(r, r, _1);
429 zmul(r, r, n);
430 zrsh(r, r, bits);
431 break;
432
433 case UNIFORM:
434 if (!gave_up) {
435 gave_up = 1;
436 printf("I'm sorry, this is too difficult, I give up.\n");
437 }
438 break;
439
440 case MODUNIFORM:
441 try(mp_rand(r, bits));
442 if (zcmp(r, n) > 0)
443 zsub(r, r, n);
444 break;
445
446 default:
447 abort();
448 }
449 }