1 /*
2
3 Copyright 2011, 2016, 2018 Free Software Foundation, Inc.
4
5 This file is part of the GNU MP Library test suite.
6
7 The GNU MP Library test suite is free software; you can redistribute it
8 and/or modify it under the terms of the GNU General Public License as
9 published by the Free Software Foundation; either version 3 of the License,
10 or (at your option) any later version.
11
12 The GNU MP Library test suite is distributed in the hope that it will be
13 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
15 Public License for more details.
16
17 You should have received a copy of the GNU General Public License along with
18 the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */
19
20 #include <stdio.h>
21 #include <stdlib.h>
22
23 #include <time.h>
24
25 #ifdef __unix__
26 # include <unistd.h>
27 # include <sys/time.h>
28 #endif
29
30 #include "gmp.h"
31
32 #include "hex-random.h"
33
34 /* FIXME: gmp-impl.h included only for mpz_lucas_mod */
35 /* #include "gmp-impl.h" */
36 #if defined (__cplusplus)
37 extern "C" {
38 #endif
39
40 #define mpz_lucas_mod __gmpz_lucas_mod
41 __GMP_DECLSPEC int mpz_lucas_mod (mpz_ptr, mpz_ptr, long, mp_bitcnt_t, mpz_srcptr, mpz_ptr, mpz_ptr);
42
43 #if defined (__cplusplus)
44 }
45 #endif
46
47 static gmp_randstate_t state;
48
49 static void
50 mkseed (mpz_t seed)
51 {
52 FILE *f = fopen ("/dev/urandom", "rb");
53 if (f)
54 {
55 unsigned char buf[6];
56 size_t res;
57
58 setbuf (f, NULL);
59 res = fread (buf, sizeof(buf), 1, f);
60 fclose (f);
61
62 if (res == 1)
63 {
64 mpz_import (seed, sizeof(buf), 1, 1, 0, 0, buf);
65 return;
66 }
67 }
68
69 #ifdef __unix__
70 {
71 struct timeval tv;
72 mpz_t usec;
73 mpz_init (usec);
74
75 gettimeofday (&tv, NULL);
76 mpz_set_ui (seed, tv.tv_sec);
77 mpz_set_ui (usec, tv.tv_usec);
78 /* usec fits in 20 bits, shift left to make it 48 bits. */
79 mpz_mul_2exp (usec, usec, 28);
80 mpz_xor (seed, seed, usec);
81
82 mpz_clear (usec);
83 }
84 #else
85 mpz_set_ui (seed, time (NULL));
86 #endif
87 }
88
89 void
90 hex_random_init (void)
91 {
92 mpz_t seed;
93 char *env_seed;
94
95 mpz_init (seed);
96
97 env_seed = getenv ("GMP_CHECK_RANDOMIZE");
98 if (env_seed && env_seed[0])
99 {
100 mpz_set_str (seed, env_seed, 0);
101 if (mpz_cmp_ui (seed, 0) != 0)
102 gmp_printf ("Re-seeding with GMP_CHECK_RANDOMIZE=%Zd\n", seed);
103 else
104 {
105 mkseed (seed);
106 gmp_printf ("Seed GMP_CHECK_RANDOMIZE=%Zd (include this in bug reports)\n", seed);
107 }
108 fflush (stdout);
109 }
110 else
111 mpz_set_ui (seed, 4711);
112
113 gmp_randinit_default (state);
114 gmp_randseed (state, seed);
115
116 mpz_clear (seed);
117 }
118
119 char *
120 hex_urandomb (unsigned long bits)
121 {
122 char *res;
123 mpz_t x;
124
125 mpz_init (x);
126 mpz_urandomb (x, state, bits);
127 gmp_asprintf (&res, "%Zx", x);
128 mpz_clear (x);
129 return res;
130 }
131
132 char *
133 hex_rrandomb (unsigned long bits)
134 {
135 char *res;
136 mpz_t x;
137
138 mpz_init (x);
139 mpz_rrandomb (x, state, bits);
140 gmp_asprintf (&res, "%Zx", x);
141 mpz_clear (x);
142 return res;
143 }
144
145 char *
146 hex_rrandomb_export (void *dst, size_t *countp,
147 int order, size_t size, int endian, unsigned long bits)
148 {
149 char *res;
150 mpz_t x;
151 mpz_init (x);
152 mpz_rrandomb (x, state, bits);
153 gmp_asprintf (&res, "%Zx", x);
154 mpz_export (dst, countp, order, size, endian, 0, x);
155 mpz_clear (x);
156 return res;
157 }
158
159 void hex_random_op2 (enum hex_random_op op, unsigned long maxbits,
160 char **ap, char **rp)
161 {
162 mpz_t a, r;
163 unsigned long abits;
164 unsigned signs;
165
166 mpz_init (a);
167 mpz_init (r);
168
169 abits = gmp_urandomb_ui (state, 32) % maxbits;
170
171 mpz_rrandomb (a, state, abits);
172
173 signs = gmp_urandomb_ui (state, 1);
174 if (signs & 1)
175 mpz_neg (a, a);
176
177 switch (op)
178 {
179 default:
180 abort ();
181 case OP_SQR:
182 mpz_mul (r, a, a);
183 break;
184 }
185
186 gmp_asprintf (ap, "%Zx", a);
187 gmp_asprintf (rp, "%Zx", r);
188
189 mpz_clear (a);
190 mpz_clear (r);
191 }
192
193 void
194 hex_random_op3 (enum hex_random_op op, unsigned long maxbits,
195 char **ap, char **bp, char **rp)
196 {
197 mpz_t a, b, r;
198 unsigned long abits, bbits;
199 unsigned signs;
200
201 mpz_init (a);
202 mpz_init (b);
203 mpz_init (r);
204
205 abits = gmp_urandomb_ui (state, 32) % maxbits;
206 bbits = gmp_urandomb_ui (state, 32) % maxbits;
207
208 mpz_rrandomb (a, state, abits);
209 mpz_rrandomb (b, state, bbits);
210
211 signs = gmp_urandomb_ui (state, 3);
212 if (signs & 1)
213 mpz_neg (a, a);
214 if (signs & 2)
215 mpz_neg (b, b);
216
217 switch (op)
218 {
219 default:
220 abort ();
221 case OP_ADD:
222 mpz_add (r, a, b);
223 break;
224 case OP_SUB:
225 mpz_sub (r, a, b);
226 break;
227 case OP_MUL:
228 mpz_mul (r, a, b);
229 break;
230 case OP_GCD:
231 if (signs & 4)
232 {
233 /* Produce a large gcd */
234 unsigned long gbits = gmp_urandomb_ui (state, 32) % maxbits;
235 mpz_rrandomb (r, state, gbits);
236 mpz_mul (a, a, r);
237 mpz_mul (b, b, r);
238 }
239 mpz_gcd (r, a, b);
240 break;
241 case OP_LCM:
242 if (signs & 4)
243 {
244 /* Produce a large gcd */
245 unsigned long gbits = gmp_urandomb_ui (state, 32) % maxbits;
246 mpz_rrandomb (r, state, gbits);
247 mpz_mul (a, a, r);
248 mpz_mul (b, b, r);
249 }
250 mpz_lcm (r, a, b);
251 break;
252 case OP_AND:
253 mpz_and (r, a, b);
254 break;
255 case OP_IOR:
256 mpz_ior (r, a, b);
257 break;
258 case OP_XOR:
259 mpz_xor (r, a, b);
260 break;
261 }
262
263 gmp_asprintf (ap, "%Zx", a);
264 gmp_asprintf (bp, "%Zx", b);
265 gmp_asprintf (rp, "%Zx", r);
266
267 mpz_clear (a);
268 mpz_clear (b);
269 mpz_clear (r);
270 }
271
272 void
273 hex_random_op4 (enum hex_random_op op, unsigned long maxbits,
274 char **ap, char **bp, char **cp, char **dp)
275 {
276 mpz_t a, b, c, d;
277 unsigned long abits, bbits;
278 unsigned signs;
279
280 mpz_init (a);
281 mpz_init (b);
282 mpz_init (c);
283 mpz_init (d);
284
285 if (op == OP_POWM)
286 {
287 unsigned long cbits;
288 abits = gmp_urandomb_ui (state, 32) % maxbits;
289 bbits = 1 + gmp_urandomb_ui (state, 32) % maxbits;
290 cbits = 2 + gmp_urandomb_ui (state, 32) % maxbits;
291
292 mpz_rrandomb (a, state, abits);
293 mpz_rrandomb (b, state, bbits);
294 mpz_rrandomb (c, state, cbits);
295
296 signs = gmp_urandomb_ui (state, 3);
297 if (signs & 1)
298 mpz_neg (a, a);
299 if (signs & 2)
300 {
301 mpz_t g;
302
303 /* If we negate the exponent, must make sure that gcd(a, c) = 1 */
304 if (mpz_sgn (a) == 0)
305 mpz_set_ui (a, 1);
306 else
307 {
308 mpz_init (g);
309
310 for (;;)
311 {
312 mpz_gcd (g, a, c);
313 if (mpz_cmp_ui (g, 1) == 0)
314 break;
315 mpz_divexact (a, a, g);
316 }
317 mpz_clear (g);
318 }
319 mpz_neg (b, b);
320 }
321 if (signs & 4)
322 mpz_neg (c, c);
323
324 mpz_powm (d, a, b, c);
325 }
326 else
327 {
328 unsigned long qbits;
329 bbits = 1 + gmp_urandomb_ui (state, 32) % maxbits;
330 qbits = gmp_urandomb_ui (state, 32) % maxbits;
331 abits = bbits + qbits;
332 if (abits > 30)
333 abits -= 30;
334 else
335 abits = 0;
336
337 mpz_rrandomb (a, state, abits);
338 mpz_rrandomb (b, state, bbits);
339
340 signs = gmp_urandomb_ui (state, 2);
341 if (signs & 1)
342 mpz_neg (a, a);
343 if (signs & 2)
344 mpz_neg (b, b);
345
346 switch (op)
347 {
348 default:
349 abort ();
350 case OP_CDIV:
351 mpz_cdiv_qr (c, d, a, b);
352 break;
353 case OP_FDIV:
354 mpz_fdiv_qr (c, d, a, b);
355 break;
356 case OP_TDIV:
357 mpz_tdiv_qr (c, d, a, b);
358 break;
359 }
360 }
361 gmp_asprintf (ap, "%Zx", a);
362 gmp_asprintf (bp, "%Zx", b);
363 gmp_asprintf (cp, "%Zx", c);
364 gmp_asprintf (dp, "%Zx", d);
365
366 mpz_clear (a);
367 mpz_clear (b);
368 mpz_clear (c);
369 mpz_clear (d);
370 }
371
372 void
373 hex_random_bit_op (enum hex_random_op op, unsigned long maxbits,
374 char **ap, unsigned long *b, char **rp)
375 {
376 mpz_t a, r;
377 unsigned long abits, bbits;
378 unsigned signs;
379
380 mpz_init (a);
381 mpz_init (r);
382
383 abits = gmp_urandomb_ui (state, 32) % maxbits;
384 bbits = gmp_urandomb_ui (state, 32) % (maxbits + 100);
385
386 mpz_rrandomb (a, state, abits);
387
388 signs = gmp_urandomb_ui (state, 1);
389 if (signs & 1)
390 mpz_neg (a, a);
391
392 switch (op)
393 {
394 default:
395 abort ();
396
397 case OP_SETBIT:
398 mpz_set (r, a);
399 mpz_setbit (r, bbits);
400 break;
401 case OP_CLRBIT:
402 mpz_set (r, a);
403 mpz_clrbit (r, bbits);
404 break;
405 case OP_COMBIT:
406 mpz_set (r, a);
407 mpz_combit (r, bbits);
408 break;
409 case OP_CDIV_Q_2:
410 mpz_cdiv_q_2exp (r, a, bbits);
411 break;
412 case OP_CDIV_R_2:
413 mpz_cdiv_r_2exp (r, a, bbits);
414 break;
415 case OP_FDIV_Q_2:
416 mpz_fdiv_q_2exp (r, a, bbits);
417 break;
418 case OP_FDIV_R_2:
419 mpz_fdiv_r_2exp (r, a, bbits);
420 break;
421 case OP_TDIV_Q_2:
422 mpz_tdiv_q_2exp (r, a, bbits);
423 break;
424 case OP_TDIV_R_2:
425 mpz_tdiv_r_2exp (r, a, bbits);
426 break;
427 }
428
429 gmp_asprintf (ap, "%Zx", a);
430 *b = bbits;
431 gmp_asprintf (rp, "%Zx", r);
432
433 mpz_clear (a);
434 mpz_clear (r);
435 }
436
437 void
438 hex_random_scan_op (enum hex_random_op op, unsigned long maxbits,
439 char **ap, unsigned long *b, unsigned long *r)
440 {
441 mpz_t a;
442 unsigned long abits, bbits;
443 unsigned signs;
444
445 mpz_init (a);
446
447 abits = gmp_urandomb_ui (state, 32) % maxbits;
448 bbits = gmp_urandomb_ui (state, 32) % (maxbits + 100);
449
450 mpz_rrandomb (a, state, abits);
451
452 signs = gmp_urandomb_ui (state, 1);
453 if (signs & 1)
454 mpz_neg (a, a);
455
456 switch (op)
457 {
458 default:
459 abort ();
460
461 case OP_SCAN0:
462 *r = mpz_scan0 (a, bbits);
463 break;
464 case OP_SCAN1:
465 *r = mpz_scan1 (a, bbits);
466 break;
467 }
468 gmp_asprintf (ap, "%Zx", a);
469 *b = bbits;
470
471 mpz_clear (a);
472 }
473
474 void
475 hex_random_str_op (unsigned long maxbits,
476 int base, char **ap, char **rp)
477 {
478 mpz_t a;
479 unsigned long abits;
480 unsigned signs;
481
482 mpz_init (a);
483
484 abits = gmp_urandomb_ui (state, 32) % maxbits;
485
486 mpz_rrandomb (a, state, abits);
487
488 signs = gmp_urandomb_ui (state, 2);
489 if (signs & 1)
490 mpz_neg (a, a);
491
492 *ap = mpz_get_str (NULL, 16, a);
493 *rp = mpz_get_str (NULL, base, a);
494
495 mpz_clear (a);
496 }
497
498 void hex_random_lucm_op (unsigned long maxbits,
499 char **vp, char **qp, char **mp,
500 long *Q, unsigned long *b0, int *res)
501 {
502 mpz_t m, v, q, t1, t2;
503 unsigned long mbits;
504
505 mpz_init (m);
506 mpz_init (v);
507 mpz_init (q);
508 mpz_init (t1);
509 mpz_init (t2);
510
511 *Q = gmp_urandomb_ui (state, 14) + 1;
512
513 do
514 {
515 mbits = gmp_urandomb_ui (state, 32) % maxbits + 5;
516
517 mpz_rrandomb (m, state, mbits);
518 *b0 = gmp_urandomb_ui (state, 32) % (mbits - 3) + 2;
519 /* The GMP implementation uses the exponent (m >> b0) + 1. */
520 /* mini-gmp implementation uses the exponent (m >> b0) | 1. */
521 /* They are the same (and are used) only when (m >> b0) is even */
522 mpz_clrbit (m, *b0);
523 /* mini-gmp implementation only works if the modulus is odd. */
524 mpz_setbit (m, 0);
525 }
526 while (mpz_gcd_ui (NULL, m, *Q) != 1);
527
528 if (*Q == 1 || gmp_urandomb_ui (state, 1))
529 *Q = - *Q;
530
531 #if (__GNU_MP_VERSION == 6 && (__GNU_MP_VERSION_MINOR > 1 || __GNU_MP_VERSION_PATCHLEVEL > 9))
532 *res = mpz_lucas_mod (v, q, *Q, *b0, m, t1, t2);
533 #else
534 *b0 = 0;
535 #endif
536
537 gmp_asprintf (vp, "%Zx", v);
538 gmp_asprintf (qp, "%Zx", q);
539 gmp_asprintf (mp, "%Zx", m);
540
541 mpz_clear (m);
542 mpz_clear (v);
543 mpz_clear (q);
544 mpz_clear (t1);
545 mpz_clear (t2);
546 }
547
548 void
549 hex_mpq_random_str_op (unsigned long maxbits,
550 int base, char **ap, char **rp)
551 {
552 mpq_t a;
553 unsigned long abits;
554 unsigned signs;
555
556 mpq_init (a);
557
558 abits = gmp_urandomb_ui (state, 32) % maxbits;
559
560 mpz_rrandomb (mpq_numref (a), state, abits);
561 mpz_rrandomb (mpq_denref (a), state, abits);
562 mpz_add_ui (mpq_denref (a), mpq_denref (a), 1);
563
564 mpq_canonicalize (a);
565 signs = gmp_urandomb_ui (state, 2);
566 if (signs & 1)
567 mpq_neg (a, a);
568
569 *ap = mpq_get_str (NULL, 16, a);
570 *rp = mpq_get_str (NULL, base, a);
571
572 mpq_clear (a);
573 }