diff options
Diffstat (limited to 'lib/libc/stdlib/random.c')
| -rw-r--r-- | lib/libc/stdlib/random.c | 106 |
1 files changed, 100 insertions, 6 deletions
diff --git a/lib/libc/stdlib/random.c b/lib/libc/stdlib/random.c index 7c76158d9b97..4737e40814f2 100644 --- a/lib/libc/stdlib/random.c +++ b/lib/libc/stdlib/random.c @@ -29,14 +29,20 @@ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. + * + * $Id: random.c,v 1.9 1997/06/14 00:13:56 ache Exp $ + * */ #if defined(LIBC_SCCS) && !defined(lint) static char sccsid[] = "@(#)random.c 8.2 (Berkeley) 5/19/95"; #endif /* LIBC_SCCS and not lint */ +#include <sys/time.h> /* for srandomdev() */ +#include <fcntl.h> /* for srandomdev() */ #include <stdio.h> #include <stdlib.h> +#include <unistd.h> /* for srandomdev() */ /* * random.c: @@ -61,7 +67,7 @@ static char sccsid[] = "@(#)random.c 8.2 (Berkeley) 5/19/95"; * state information, which will allow a degree seven polynomial. (Note: * the zeroeth word of state information also has some other information * stored in it -- see setstate() for details). - * + * * The random number generation technique is a linear feedback shift register * approach, employing trinomials (since there are fewer terms to sum up that * way). In this approach, the least significant bit of all the numbers in @@ -141,7 +147,7 @@ static long seps [MAX_TYPES] = { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 }; /* * Initially, everything is set up as if from: * - * initstate(1, &randtbl, 128); + * initstate(1, randtbl, 128); * * Note that this initialization takes advantage of the fact that srandom() * advances the front and rear pointers 10*rand_deg times, and hence the @@ -154,12 +160,23 @@ static long seps [MAX_TYPES] = { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 }; static long randtbl[DEG_3 + 1] = { TYPE_3, +#ifdef USE_WEAK_SEEDING +/* Historic implementation compatibility */ +/* The random sequences do not vary much with the seed */ 0x9a319039, 0x32d9c024, 0x9b663182, 0x5da1f342, 0xde3b81e0, 0xdf0a6fb5, 0xf103bc02, 0x48f340fb, 0x7449e56b, 0xbeb1dbb0, 0xab5c5918, 0x946554fd, 0x8c2e680f, 0xeb3d799f, 0xb11ee0b7, 0x2d436b86, 0xda672e2a, 0x1588ca88, 0xe369735d, 0x904f35f7, 0xd7158fd6, 0x6fa6f051, 0x616e6b96, 0xac94efdc, 0x36413f93, 0xc622c298, 0xf5a42ab8, 0x8a88d77b, 0xf5ad9d0e, 0x8999220b, 0x27fb47b9, +#else /* !USE_WEAK_SEEDING */ + 0x991539b1, 0x16a5bce3, 0x6774a4cd, 0x3e01511e, 0x4e508aaa, 0x61048c05, + 0xf5500617, 0x846b7115, 0x6a19892c, 0x896a97af, 0xdb48f936, 0x14898454, + 0x37ffd106, 0xb58bff9c, 0x59e17104, 0xcf918a49, 0x09378c83, 0x52c7a471, + 0x8d293ea9, 0x1f4fc301, 0xc3db71be, 0x39b44e1c, 0xf8a44ef9, 0x4c8b80b1, + 0x19edc328, 0x87bf4bdd, 0xc9b240e5, 0xe9ee4b1b, 0x4382aee7, 0x535b6b41, + 0xf3bec5da +#endif /* !USE_WEAK_SEEDING */ }; /* @@ -195,6 +212,38 @@ static long rand_deg = DEG_3; static long rand_sep = SEP_3; static long *end_ptr = &randtbl[DEG_3 + 1]; +static inline long good_rand __P((long)); + +static inline long good_rand (x) + register long x; +{ +#ifdef USE_WEAK_SEEDING +/* + * Historic implementation compatibility. + * The random sequences do not vary much with the seed, + * even with overflowing. + */ + return (1103515245 * x + 12345); +#else /* !USE_WEAK_SEEDING */ +/* + * Compute x = (7^5 * x) mod (2^31 - 1) + * wihout overflowing 31 bits: + * (2^31 - 1) = 127773 * (7^5) + 2836 + * From "Random number generators: good ones are hard to find", + * Park and Miller, Communications of the ACM, vol. 31, no. 10, + * October 1988, p. 1195. + */ + register long hi, lo; + + hi = x / 127773; + lo = x % 127773; + x = 16807 * lo - 2836 * hi; + if (x <= 0) + x += 0x7fffffff; + return (x); +#endif /* !USE_WEAK_SEEDING */ +} + /* * srandom: * @@ -218,7 +267,7 @@ srandom(x) else { state[0] = x; for (i = 1; i < rand_deg; i++) - state[i] = 1103515245 * state[i - 1] + 12345; + state[i] = good_rand(state[i - 1]); fptr = &state[rand_sep]; rptr = &state[0]; for (i = 0; i < 10 * rand_deg; i++) @@ -227,6 +276,51 @@ srandom(x) } /* + * srandomdev: + * + * Many programs choose the seed value in a totally predictable manner. + * This often causes problems. We seed the generator using the much more + * secure urandom(4) interface. Note that this particular seeding + * procedure can generate states which are impossible to reproduce by + * calling srandom() with any value, since the succeeding terms in the + * state buffer are no longer derived from the LC algorithm applied to + * a fixed seed. + */ +void +srandomdev() +{ + int fd, done; + size_t len; + + if (rand_type == TYPE_0) + len = sizeof state[0]; + else + len = rand_deg * sizeof state[0]; + + done = 0; + fd = open("/dev/urandom", O_RDONLY, 0); + if (fd >= 0) { + if (read(fd, (void *) state, len) == (ssize_t) len) + done = 1; + close(fd); + } + + if (!done) { + struct timeval tv; + unsigned long junk; + + gettimeofday(&tv, NULL); + srandom(getpid() ^ tv.tv_sec ^ tv.tv_usec ^ junk); + return; + } + + if (rand_type != TYPE_0) { + fptr = &state[rand_sep]; + rptr = &state[0]; + } +} + +/* * initstate: * * Initialize the state information in the given array of n bytes for future @@ -234,12 +328,12 @@ srandom(x) * the break values for the different R.N.G.'s, we choose the best (largest) * one we can and set things up for it. srandom() is then called to * initialize the state information. - * + * * Note that on return from srandom(), we set state[-1] to be the type * multiplexed with the current value of the rear pointer; this is so * successive calls to initstate() won't lose this information and will be * able to restart with setstate(). - * + * * Note: the first thing we do is save the current state, if any, just like * setstate() so that it doesn't matter when initstate is called. * @@ -378,7 +472,7 @@ random() if (rand_type == TYPE_0) { i = state[0]; - state[0] = i = (i * 1103515245 + 12345) & 0x7fffffff; + state[0] = i = (good_rand(i)) & 0x7fffffff; } else { /* * Use local variables rather than static variables for speed. |