Line | Count | Source (jump to first uncovered line) |
1 | | /* mpz_urandomm (rop, state, n) -- Generate a uniform pseudorandom |
2 | | integer in the range 0 to N-1, using STATE as the random state |
3 | | previously initialized by a call to gmp_randinit(). |
4 | | |
5 | | Copyright 2000, 2002, 2012, 2015 Free Software Foundation, Inc. |
6 | | |
7 | | This file is part of the GNU MP Library. |
8 | | |
9 | | The GNU MP Library is free software; you can redistribute it and/or modify |
10 | | it under the terms of either: |
11 | | |
12 | | * the GNU Lesser General Public License as published by the Free |
13 | | Software Foundation; either version 3 of the License, or (at your |
14 | | option) any later version. |
15 | | |
16 | | or |
17 | | |
18 | | * the GNU General Public License as published by the Free Software |
19 | | Foundation; either version 2 of the License, or (at your option) any |
20 | | later version. |
21 | | |
22 | | or both in parallel, as here. |
23 | | |
24 | | The GNU MP Library is distributed in the hope that it will be useful, but |
25 | | WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY |
26 | | or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
27 | | for more details. |
28 | | |
29 | | You should have received copies of the GNU General Public License and the |
30 | | GNU Lesser General Public License along with the GNU MP Library. If not, |
31 | | see https://www.gnu.org/licenses/. */ |
32 | | |
33 | | #include "gmp-impl.h" |
34 | | #include "longlong.h" /* for count_leading_zeros */ |
35 | | |
36 | | |
37 | 0 | #define MAX_URANDOMM_ITER 80 |
38 | | |
39 | | void |
40 | | mpz_urandomm (mpz_ptr rop, gmp_randstate_ptr rstate, mpz_srcptr n) |
41 | 0 | { |
42 | 0 | mp_ptr rp, np; |
43 | 0 | mp_size_t nbits, size; |
44 | 0 | mp_limb_t nh; |
45 | 0 | int count; |
46 | 0 | int pow2; |
47 | 0 | int cmp; |
48 | 0 | TMP_DECL; |
49 | |
|
50 | 0 | size = ABSIZ (n); |
51 | 0 | if (UNLIKELY (size == 0)) |
52 | 0 | DIVIDE_BY_ZERO; |
53 | | |
54 | 0 | np = PTR (n); |
55 | 0 | nh = np[size - 1]; |
56 | | |
57 | | /* Detect whether n is a power of 2. */ |
58 | 0 | pow2 = POW2_P (nh) && (size == 1 || mpn_zero_p (np, size - 1)); |
59 | |
|
60 | 0 | count_leading_zeros (count, nh); |
61 | 0 | nbits = size * GMP_NUMB_BITS - (count - GMP_NAIL_BITS) - pow2; |
62 | 0 | if (nbits == 0) /* nbits == 0 means that n was == 1. */ |
63 | 0 | { |
64 | 0 | SIZ (rop) = 0; |
65 | 0 | return; |
66 | 0 | } |
67 | | |
68 | 0 | TMP_MARK; |
69 | 0 | if (rop == n) |
70 | 0 | { |
71 | 0 | mp_ptr tp; |
72 | 0 | tp = TMP_ALLOC_LIMBS (size); |
73 | 0 | MPN_COPY (tp, np, size); |
74 | 0 | np = tp; |
75 | 0 | } |
76 | | |
77 | | /* Here the allocated size can be one too much if n is a power of |
78 | | (2^GMP_NUMB_BITS) but it's convenient for using mpn_cmp below. */ |
79 | 0 | rp = MPZ_NEWALLOC (rop, size); |
80 | | /* Clear last limb to prevent the case in which size is one too much. */ |
81 | 0 | rp[size - 1] = 0; |
82 | |
|
83 | 0 | count = MAX_URANDOMM_ITER; /* Set iteration count limit. */ |
84 | 0 | do |
85 | 0 | { |
86 | 0 | _gmp_rand (rp, rstate, nbits); |
87 | 0 | MPN_CMP (cmp, rp, np, size); |
88 | 0 | } |
89 | 0 | while (cmp >= 0 && --count != 0); |
90 | |
|
91 | 0 | if (count == 0) |
92 | | /* Too many iterations; return result mod n == result - n */ |
93 | 0 | mpn_sub_n (rp, rp, np, size); |
94 | |
|
95 | 0 | MPN_NORMALIZE (rp, size); |
96 | 0 | SIZ (rop) = size; |
97 | 0 | TMP_FREE; |
98 | 0 | } |