From d8ed26bd07abb23acc9c1879776f5afc44ed4874 Mon Sep 17 00:00:00 2001 From: Paul Eggert Date: Mon, 4 Jul 2011 19:51:15 -0700 Subject: [PATCH] Random fixes. E.g., (random) never returned negative values. * fns.c (Frandom): Use GET_EMACS_TIME for random seed, and add the subseconds part to the entropy, as that's a bit more random. Prefer signed to unsigned, since the signedness doesn't matter and in general we prefer signed. When given a limit, use a denominator equal to INTMASK + 1, not to VALMASK + 1, because the latter isn't right if USE_2_TAGS_FOR_INTS. * sysdep.c (get_random): Return a value in the range 0..INTMASK, not 0..VALMASK. Don't discard "excess" bits that random () returns. --- src/ChangeLog | 12 ++++++++++++ src/fns.c | 10 +++++++--- src/sysdep.c | 11 +++++++---- 3 files changed, 26 insertions(+), 7 deletions(-) diff --git a/src/ChangeLog b/src/ChangeLog index 17a6179f356..9ad7da46ecf 100644 --- a/src/ChangeLog +++ b/src/ChangeLog @@ -1,3 +1,15 @@ +2011-07-05 Paul Eggert + + Random fixes. E.g., (random) never returned negative values. + * fns.c (Frandom): Use GET_EMACS_TIME for random seed, and add the + subseconds part to the entropy, as that's a bit more random. + Prefer signed to unsigned, since the signedness doesn't matter and + in general we prefer signed. When given a limit, use a + denominator equal to INTMASK + 1, not to VALMASK + 1, because the + latter isn't right if USE_2_TAGS_FOR_INTS. + * sysdep.c (get_random): Return a value in the range 0..INTMASK, + not 0..VALMASK. Don't discard "excess" bits that random () returns. + 2011-07-04 Stefan Monnier * textprop.c (text_property_stickiness): diff --git a/src/fns.c b/src/fns.c index 5d2524d5cc2..0ca731ed331 100644 --- a/src/fns.c +++ b/src/fns.c @@ -79,10 +79,14 @@ Other values of LIMIT are ignored. */) { EMACS_INT val; Lisp_Object lispy_val; - EMACS_UINT denominator; if (EQ (limit, Qt)) - seed_random (getpid () + time (NULL)); + { + EMACS_TIME t; + EMACS_GET_TIME (t); + seed_random (getpid () ^ EMACS_SECS (t) ^ EMACS_USECS (t)); + } + if (NATNUMP (limit) && XFASTINT (limit) != 0) { /* Try to take our random number from the higher bits of VAL, @@ -92,7 +96,7 @@ Other values of LIMIT are ignored. */) it's possible to get a quotient larger than n; discarding these values eliminates the bias that would otherwise appear when using a large n. */ - denominator = ((EMACS_UINT) 1 << VALBITS) / XFASTINT (limit); + EMACS_INT denominator = (INTMASK + 1) / XFASTINT (limit); do val = get_random () / denominator; while (val >= XFASTINT (limit)); diff --git a/src/sysdep.c b/src/sysdep.c index 3a73b1a467b..8b6939b91fe 100644 --- a/src/sysdep.c +++ b/src/sysdep.c @@ -1783,7 +1783,8 @@ seed_random (long int arg) } /* - * Build a full Emacs-sized word out of whatever we've got. + * Return a nonnegative random integer out of whatever we've got. + * It contains enough bits to make a random (signed) Emacs fixnum. * This suffices even for a 64-bit architecture with a 15-bit rand. */ EMACS_INT @@ -1791,9 +1792,11 @@ get_random (void) { EMACS_UINT val = 0; int i; - for (i = 0; i < (VALBITS + RAND_BITS - 1) / RAND_BITS; i++) - val = (val << RAND_BITS) ^ random (); - return val & (((EMACS_INT) 1 << VALBITS) - 1); + for (i = 0; i < (FIXNUM_BITS + RAND_BITS - 1) / RAND_BITS; i++) + val = (random () ^ (val << RAND_BITS) + ^ (val >> (BITS_PER_EMACS_INT - RAND_BITS))); + val ^= val >> (BITS_PER_EMACS_INT - FIXNUM_BITS); + return val & INTMASK; } #ifndef HAVE_STRERROR -- 2.39.2