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