1*86d7f5d3SJohn Marino /* mpn_random2 -- Generate random numbers with relatively long strings
2*86d7f5d3SJohn Marino of ones and zeroes. Suitable for border testing.
3*86d7f5d3SJohn Marino
4*86d7f5d3SJohn Marino Copyright 1992, 1993, 1994, 1996, 2000, 2001, 2002, 2004 Free Software
5*86d7f5d3SJohn Marino Foundation, Inc.
6*86d7f5d3SJohn Marino
7*86d7f5d3SJohn Marino This file is part of the GNU MP Library.
8*86d7f5d3SJohn Marino
9*86d7f5d3SJohn Marino The GNU MP Library is free software; you can redistribute it and/or modify
10*86d7f5d3SJohn Marino it under the terms of the GNU Lesser General Public License as published by
11*86d7f5d3SJohn Marino the Free Software Foundation; either version 3 of the License, or (at your
12*86d7f5d3SJohn Marino option) any later version.
13*86d7f5d3SJohn Marino
14*86d7f5d3SJohn Marino The GNU MP Library is distributed in the hope that it will be useful, but
15*86d7f5d3SJohn Marino WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
16*86d7f5d3SJohn Marino or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
17*86d7f5d3SJohn Marino License for more details.
18*86d7f5d3SJohn Marino
19*86d7f5d3SJohn Marino You should have received a copy of the GNU Lesser General Public License
20*86d7f5d3SJohn Marino along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
21*86d7f5d3SJohn Marino
22*86d7f5d3SJohn Marino #include "gmp.h"
23*86d7f5d3SJohn Marino #include "gmp-impl.h"
24*86d7f5d3SJohn Marino
25*86d7f5d3SJohn Marino static void gmp_rrandomb __GMP_PROTO ((mp_ptr, gmp_randstate_t, mp_bitcnt_t));
26*86d7f5d3SJohn Marino
27*86d7f5d3SJohn Marino /* Ask _gmp_rand for 32 bits per call unless that's more than a limb can hold.
28*86d7f5d3SJohn Marino Thus, we get the same random number sequence in the common cases.
29*86d7f5d3SJohn Marino FIXME: We should always generate the same random number sequence! */
30*86d7f5d3SJohn Marino #if GMP_NUMB_BITS < 32
31*86d7f5d3SJohn Marino #define BITS_PER_RANDCALL GMP_NUMB_BITS
32*86d7f5d3SJohn Marino #else
33*86d7f5d3SJohn Marino #define BITS_PER_RANDCALL 32
34*86d7f5d3SJohn Marino #endif
35*86d7f5d3SJohn Marino
36*86d7f5d3SJohn Marino void
mpn_random2(mp_ptr rp,mp_size_t n)37*86d7f5d3SJohn Marino mpn_random2 (mp_ptr rp, mp_size_t n)
38*86d7f5d3SJohn Marino {
39*86d7f5d3SJohn Marino gmp_randstate_ptr rstate = RANDS;
40*86d7f5d3SJohn Marino int bit_pos; /* bit number of least significant bit where
41*86d7f5d3SJohn Marino next bit field to be inserted */
42*86d7f5d3SJohn Marino mp_limb_t ran, ranm; /* buffer for random bits */
43*86d7f5d3SJohn Marino
44*86d7f5d3SJohn Marino /* FIXME: Is n==0 supposed to be allowed? */
45*86d7f5d3SJohn Marino ASSERT (n >= 0);
46*86d7f5d3SJohn Marino
47*86d7f5d3SJohn Marino _gmp_rand (&ranm, rstate, BITS_PER_RANDCALL);
48*86d7f5d3SJohn Marino ran = ranm;
49*86d7f5d3SJohn Marino
50*86d7f5d3SJohn Marino /* Start off at a random bit position in the most significant limb. */
51*86d7f5d3SJohn Marino bit_pos = ran % GMP_NUMB_BITS;
52*86d7f5d3SJohn Marino
53*86d7f5d3SJohn Marino gmp_rrandomb (rp, rstate, n * GMP_NUMB_BITS - bit_pos);
54*86d7f5d3SJohn Marino }
55*86d7f5d3SJohn Marino
56*86d7f5d3SJohn Marino static void
gmp_rrandomb(mp_ptr rp,gmp_randstate_t rstate,mp_bitcnt_t nbits)57*86d7f5d3SJohn Marino gmp_rrandomb (mp_ptr rp, gmp_randstate_t rstate, mp_bitcnt_t nbits)
58*86d7f5d3SJohn Marino {
59*86d7f5d3SJohn Marino mp_bitcnt_t bi;
60*86d7f5d3SJohn Marino mp_limb_t ranm; /* buffer for random bits */
61*86d7f5d3SJohn Marino unsigned cap_chunksize, chunksize;
62*86d7f5d3SJohn Marino mp_size_t i;
63*86d7f5d3SJohn Marino
64*86d7f5d3SJohn Marino /* Set entire result to 111..1 */
65*86d7f5d3SJohn Marino i = (nbits + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS - 1;
66*86d7f5d3SJohn Marino rp[i] = GMP_NUMB_MAX >> (GMP_NUMB_BITS - (nbits % GMP_NUMB_BITS)) % GMP_NUMB_BITS;
67*86d7f5d3SJohn Marino for (i = i - 1; i >= 0; i--)
68*86d7f5d3SJohn Marino rp[i] = GMP_NUMB_MAX;
69*86d7f5d3SJohn Marino
70*86d7f5d3SJohn Marino _gmp_rand (&ranm, rstate, BITS_PER_RANDCALL);
71*86d7f5d3SJohn Marino cap_chunksize = nbits / (ranm % 4 + 1);
72*86d7f5d3SJohn Marino cap_chunksize += cap_chunksize == 0; /* make it at least 1 */
73*86d7f5d3SJohn Marino
74*86d7f5d3SJohn Marino bi = nbits;
75*86d7f5d3SJohn Marino
76*86d7f5d3SJohn Marino for (;;)
77*86d7f5d3SJohn Marino {
78*86d7f5d3SJohn Marino _gmp_rand (&ranm, rstate, BITS_PER_RANDCALL);
79*86d7f5d3SJohn Marino chunksize = 1 + ranm % cap_chunksize;
80*86d7f5d3SJohn Marino bi = (bi < chunksize) ? 0 : bi - chunksize;
81*86d7f5d3SJohn Marino
82*86d7f5d3SJohn Marino if (bi == 0)
83*86d7f5d3SJohn Marino break; /* low chunk is ...1 */
84*86d7f5d3SJohn Marino
85*86d7f5d3SJohn Marino rp[bi / GMP_NUMB_BITS] ^= CNST_LIMB (1) << bi % GMP_NUMB_BITS;
86*86d7f5d3SJohn Marino
87*86d7f5d3SJohn Marino _gmp_rand (&ranm, rstate, BITS_PER_RANDCALL);
88*86d7f5d3SJohn Marino chunksize = 1 + ranm % cap_chunksize;
89*86d7f5d3SJohn Marino bi = (bi < chunksize) ? 0 : bi - chunksize;
90*86d7f5d3SJohn Marino
91*86d7f5d3SJohn Marino mpn_incr_u (rp + bi / GMP_NUMB_BITS, CNST_LIMB (1) << bi % GMP_NUMB_BITS);
92*86d7f5d3SJohn Marino
93*86d7f5d3SJohn Marino if (bi == 0)
94*86d7f5d3SJohn Marino break; /* low chunk is ...0 */
95*86d7f5d3SJohn Marino }
96*86d7f5d3SJohn Marino }
97