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.

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  <eggert@cs.ucla.edu>
+
+        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  <monnier@iro.umontreal.ca>
 
         * 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