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