GNU bug report logs - #9118
23.3.50; Don't seed the RNG in message-unique-id

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 9118 in the body.
You can then email your comments to 9118 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Leo <sdl.web <at> gmail.com>
To: bug-gnu-emacs <at> gnu.org
Subject: 23.3.50; Don't seed the RNG in message-unique-id
Date: Tue, 19 Jul 2011 00:42:10 +0800

Function message-unique-id seeds the RNG every time it runs and relies
on its undocumented return value. Should something like this be applied?

--- a/message.el
+++ b/message.el
@@ -5484,7 +5484,8 @@
   ;; Don't use microseconds from (current-time), they may be unsupported.
   ;; Instead we use this randomly inited counter.
   (setq message-unique-id-char
-	(% (1+ (or message-unique-id-char (logand (random t) (1- (lsh 1 20)))))
+	(% (1+ (or message-unique-id-char
+		   (logand (random most-positive-fixnum) (1- (lsh 1 20)))))
 	   ;; (current-time) returns 16-bit ints,
 	   ;; and 2^16*25 just fits into 4 digits i base 36.
 	   (* 25 25)))

Diff finished.  Tue Jul 19 00:34:45 2011

Leo

Message #12 received at 9118 <at> debbugs.gnu.org (full text, mbox):

From: Lars Magne Ingebrigtsen <larsi <at> gnus.org>
To: Leo <sdl.web <at> gmail.com>
Cc: 9118 <at> debbugs.gnu.org
Subject: Re: bug#9118: 23.3.50; Don't seed the RNG in message-unique-id
Date: Tue, 19 Jul 2011 16:57:27 +0200

Leo <sdl.web <at> gmail.com> writes:

> Function message-unique-id seeds the RNG every time it runs and relies
> on its undocumented return value. Should something like this be applied?
>
> --- a/message.el
> +++ b/message.el
> @@ -5484,7 +5484,8 @@
>    ;; Don't use microseconds from (current-time), they may be unsupported.
>    ;; Instead we use this randomly inited counter.
>    (setq message-unique-id-char
> -	(% (1+ (or message-unique-id-char (logand (random t) (1- (lsh 1 20)))))
> +	(% (1+ (or message-unique-id-char
> +		   (logand (random most-positive-fixnum) (1- (lsh 1 20)))))

Unfortunately, Emacs doesn't seed itself on startup, so (random x) will
return the same thing every time you start Emacs.

So I don't think changing this is appropriate at this time.

-- 
(domestic pets only, the antidote for overdose, milk.)
  bloggy blog http://lars.ingebrigtsen.no/

Message #15 received at 9118 <at> debbugs.gnu.org (full text, mbox):

From: Leo <sdl.web <at> gmail.com>
To: Lars Magne Ingebrigtsen <larsi <at> gnus.org>
Cc: 9118 <at> debbugs.gnu.org
Subject: Re: bug#9118: 23.3.50; Don't seed the RNG in message-unique-id
Date: Tue, 19 Jul 2011 23:14:54 +0800

On 2011-07-19 22:57 +0800, Lars Magne Ingebrigtsen wrote:
> Unfortunately, Emacs doesn't seed itself on startup, so (random x) will
> return the same thing every time you start Emacs.
>
> So I don't think changing this is appropriate at this time.

But you can arrange to seed it once when that file is loaded. No need to
seed it every time. BTW, (random t) produces no random numbers.

(loop repeat 5 collect (random t))

=>

(2265815277832325116 2265815277832325116 2265815277832325116 2265815277832325116 2265815277832325116)

Leo

Message #18 received at 9118 <at> debbugs.gnu.org (full text, mbox):

From: Lars Magne Ingebrigtsen <larsi <at> gnus.org>
To: Leo <sdl.web <at> gmail.com>
Cc: 9118 <at> debbugs.gnu.org
Subject: Re: bug#9118: 23.3.50; Don't seed the RNG in message-unique-id
Date: Tue, 19 Jul 2011 17:24:36 +0200

Leo <sdl.web <at> gmail.com> writes:

> But you can arrange to seed it once when that file is loaded. No need to
> seed it every time.

Calling it once every time you send an email isn't really heavy usage of
the re-seeding.

> BTW, (random t) produces no random numbers.
>
> (loop repeat 5 collect (random t))
>
> =>
>
> (2265815277832325116 2265815277832325116 2265815277832325116
> 2265815277832325116 2265815277832325116)

Oops.  :-)  Fixed now.

-- 
(domestic pets only, the antidote for overdose, milk.)
  bloggy blog http://lars.ingebrigtsen.no/

Message #21 received at 9118 <at> debbugs.gnu.org (full text, mbox):

From: Leo <sdl.web <at> gmail.com>
To: Lars Magne Ingebrigtsen <larsi <at> gnus.org>
Cc: 9118 <at> debbugs.gnu.org
Subject: Re: bug#9118: 23.3.50; Don't seed the RNG in message-unique-id
Date: Tue, 19 Jul 2011 23:44:30 +0800

On 2011-07-19 23:24 +0800, Lars Magne Ingebrigtsen wrote:
>> But you can arrange to seed it once when that file is loaded. No need to
>> seed it every time.
>
> Calling it once every time you send an email isn't really heavy usage of
> the re-seeding.

But every seeding interrupts the internal random state (which is out of
our control at the moment) and break the users' train of random numbers.

Also if you grep (random t) in the lisp/, you can see there is some
effort in making a package only change the random state at most once.

Leo

Message #24 received at 9118 <at> debbugs.gnu.org (full text, mbox):

From: Lars Magne Ingebrigtsen <larsi <at> gnus.org>
To: Leo <sdl.web <at> gmail.com>
Cc: 9118 <at> debbugs.gnu.org
Subject: Re: bug#9118: 23.3.50; Don't seed the RNG in message-unique-id
Date: Tue, 19 Jul 2011 17:49:19 +0200

Leo <sdl.web <at> gmail.com> writes:

> But every seeding interrupts the internal random state (which is out of
> our control at the moment) and break the users' train of random numbers.
>
> Also if you grep (random t) in the lisp/, you can see there is some
> effort in making a package only change the random state at most once.

Once per package?  That means that it's called many times in a single
Emacs session, so I don't really see the problem.

This should really be fixed by Emacs calling `(random t)' at startup.

-- 
(domestic pets only, the antidote for overdose, milk.)
  bloggy blog http://lars.ingebrigtsen.no/

Message #27 received at 9118 <at> debbugs.gnu.org (full text, mbox):

From: Leo <sdl.web <at> gmail.com>
To: 9118 <at> debbugs.gnu.org
Cc: Lars Magne Ingebrigtsen <larsi <at> gnus.org>
Subject: Re: bug#9118: 23.3.50; Don't seed the RNG in message-unique-id
Date: Wed, 20 Jul 2011 10:12:12 +0800

On 2011-07-19 23:49 +0800, Lars Magne Ingebrigtsen wrote:
> Once per package?  That means that it's called many times in a single
> Emacs session, so I don't really see the problem.

Only at the time of loading a package and only a package or two in the
following do I use. After loading the packages, they won't change the
rng any more.

But calling (random t) every time a function is called just gets in the
way, that means I am no longer getting a uniform distribution from the
RNG. Also (random t) is much more predictable.

,----
| ChangeLog.6:6494:	(life): Do (random t) only once and only when `life' is called.
| allout-widgets.el:1351:;;                  (random t)
| calc/calc-comb.el:575:    (random t)
| gnus/message.el:4788:		  (format "%x%x%x" (random) (random t) (random))
| gnus/message.el:5494:	(% (1+ (or message-unique-id-char (logand (random t) (1- (lsh 1 20)))))
| net/sasl.el:186:	(% (1+ (or sasl-unique-id-char (logand (random t) (1- (lsh 1 20)))))
| org/org-id.el:322:			  (random t)
| play/5x5.el:957:(random t)
| play/animate.el:204:(random t)
| play/blackbox.el:260:  (random t)
| play/cookie1.el:57:(random t)
| Binary file play/cookie1.elc matches
| play/dissociate.el:97:(random t)
| play/doctor.el:1620:(random t)
| play/dunnet.el:3013:(random t)
| play/gomoku.el:1200:(random t)
| play/landmark.el:1686:(random t)
| play/life.el:125:      (random t))
| play/mpuz.el:38:(random t)				; randomize
| play/tetris.el:639:(random t)
| play/zone.el:683:(random t)
| server.el:97:           (when val (random t))
| type-break.el:584:        (random t)
`----

> This should really be fixed by Emacs calling `(random t)' at startup.

That should leave for the user to do. Common Lisp also does no seeding
at start up.

Leo

Message #30 received at 9118 <at> debbugs.gnu.org (full text, mbox):

From: Lars Magne Ingebrigtsen <larsi <at> gnus.org>
To: Leo <sdl.web <at> gmail.com>
Cc: 9118 <at> debbugs.gnu.org
Subject: Re: bug#9118: 23.3.50; Don't seed the RNG in message-unique-id
Date: Wed, 20 Jul 2011 22:28:02 +0200

Leo <sdl.web <at> gmail.com> writes:

> That should leave for the user to do. Common Lisp also does no seeding
> at start up.

LispWorks seeds at start-up.

-- 
(domestic pets only, the antidote for overdose, milk.)
  bloggy blog http://lars.ingebrigtsen.no/

Message #33 received at 9118 <at> debbugs.gnu.org (full text, mbox):

From: Leo <sdl.web <at> gmail.com>
To: Lars Magne Ingebrigtsen <larsi <at> gnus.org>
Cc: 9118 <at> debbugs.gnu.org
Subject: Re: bug#9118: 23.3.50; Don't seed the RNG in message-unique-id
Date: Thu, 21 Jul 2011 12:45:31 +0800

On 2011-07-21 04:28 +0800, Lars Magne Ingebrigtsen wrote:
>> That should leave for the user to do. Common Lisp also does no seeding
>> at start up.
>
> LispWorks seeds at start-up.

Indeed, some do some don't. I wonder if Emacs should? It will be just
one line change.

Leo

Message #36 received at 9118 <at> debbugs.gnu.org (full text, mbox):

From: Juanma Barranquero <lekktu <at> gmail.com>
To: Leo <sdl.web <at> gmail.com>
Cc: Lars Magne Ingebrigtsen <larsi <at> gnus.org>, 9118 <at> debbugs.gnu.org
Subject: Re: bug#9118: 23.3.50; Don't seed the RNG in message-unique-id
Date: Thu, 21 Jul 2011 13:57:51 +0200

On Thu, Jul 21, 2011 at 06:45, Leo <sdl.web <at> gmail.com> wrote:

> Indeed, some do some don't. I wonder if Emacs should?

Many systems (languages, etc.) have a facility to seed the RNG with a
specific seed (saved from a previous run, for example), so you can
have repeated runs with the exact same sequence of random numbers, if
needed. That can be useful for simulation, testing, etc.

AFAIK, the Emacs RNG does not allow that at the lisp level, so it
would be better to automatically seed it and remove the many (random
t) calls, which, as has been pointed out, can in fact be harmful for
the quality of the generated random number series, if called
repeatedly.

    Juanma

Message #39 received at 9118 <at> debbugs.gnu.org (full text, mbox):

From: Leo <sdl.web <at> gmail.com>
To: Juanma Barranquero <lekktu <at> gmail.com>
Cc: Lars Magne Ingebrigtsen <larsi <at> gnus.org>, 9118 <at> debbugs.gnu.org
Subject: Re: bug#9118: 23.3.50; Don't seed the RNG in message-unique-id
Date: Thu, 21 Jul 2011 23:58:46 +0800

On 2011-07-21 19:57 +0800, Juanma Barranquero wrote:
> Many systems (languages, etc.) have a facility to seed the RNG with a
> specific seed (saved from a previous run, for example), so you can
> have repeated runs with the exact same sequence of random numbers, if
> needed. That can be useful for simulation, testing, etc.
>
> AFAIK, the Emacs RNG does not allow that at the lisp level, so it
> would be better to automatically seed it and remove the many (random
> t) calls, which, as has been pointed out, can in fact be harmful for
> the quality of the generated random number series, if called
> repeatedly.

I agree completely.

How about something along these lines? (note: before this patch (random
1.0) is equivalent to (random most-positive-fixnum)).

=== modified file 'src/fns.c'
--- src/fns.c	2011-07-05 02:51:15 +0000
+++ src/fns.c	2011-07-21 15:47:30 +0000
@@ -69,15 +69,15 @@
 }
 
 DEFUN ("random", Frandom, Srandom, 0, 1, 0,
-       doc: /* Return a pseudo-random number.
+       doc: /* Return a non-negative pseudo-random number less than LIMIT.
 All integers representable in Lisp are equally likely.
   On most systems, this is 29 bits' worth.
-With positive integer LIMIT, return random number in interval [0,LIMIT).
-With argument t, set the random number seed from the current time and pid.
-Other values of LIMIT are ignored.  */)
+Optional argument LIMIT defaults to `most-positive-fixnum'.
+With argument t, set the random number seed from the current time
+  and pid and return nil.  */)
   (Lisp_Object limit)
 {
-  EMACS_INT val;
+  EMACS_INT val, denominator;
   Lisp_Object lispy_val;
 
   if (EQ (limit, Qt))
@@ -85,24 +85,28 @@
       EMACS_TIME t;
       EMACS_GET_TIME (t);
       seed_random (getpid () ^ EMACS_SECS (t) ^ EMACS_USECS (t));
+      return Qnil;
     }
 
-  if (NATNUMP (limit) && XFASTINT (limit) != 0)
-    {
-      /* Try to take our random number from the higher bits of VAL,
-	 not the lower, since (says Gentzel) the low bits of `random'
-	 are less random than the higher ones.  We do this by using the
-	 quotient rather than the remainder.  At the high end of the RNG
-	 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.  */
-      EMACS_INT denominator = (INTMASK + 1) / XFASTINT (limit);
-      do
-	val = get_random () / denominator;
-      while (val >= XFASTINT (limit));
-    }
-  else
-    val = get_random ();
+  if (NILP (limit))
+    XSETINT (limit, MOST_POSITIVE_FIXNUM);
+
+  CHECK_NATNUM (limit);
+
+  if (XFASTINT (limit) == 0)
+    xsignal1 (Qargs_out_of_range, limit);
+
+  /* Try to take our random number from the higher bits of VAL,
+     not the lower, since (says Gentzel) the low bits of `random'
+     are less random than the higher ones.  We do this by using the
+     quotient rather than the remainder.  At the high end of the RNG
+     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 = (INTMASK + 1) / XFASTINT (limit);
+  do
+    val = get_random () / denominator;
+  while (val >= XFASTINT (limit));
   XSETINT (lispy_val, val);
   return lispy_val;
 }
@@ -5009,4 +5013,5 @@
 void
 init_fns (void)
 {
+  Frandom (Qt);
 }

Message #42 received at 9118 <at> debbugs.gnu.org (full text, mbox):

From: Lars Magne Ingebrigtsen <larsi <at> gnus.org>
To: Leo <sdl.web <at> gmail.com>
Cc: Juanma Barranquero <lekktu <at> gmail.com>, 9118 <at> debbugs.gnu.org
Subject: Re: bug#9118: 23.3.50; Don't seed the RNG in message-unique-id
Date: Sun, 31 Jul 2011 17:39:22 +0200

Leo <sdl.web <at> gmail.com> writes:

> +With argument t, set the random number seed from the current time
> +  and pid and return nil.  */)

This would break old (buggy) usages, so it seems unnecessary.

-- 
(domestic pets only, the antidote for overdose, milk.)
  bloggy blog http://lars.ingebrigtsen.no/

Message #45 received at 9118 <at> debbugs.gnu.org (full text, mbox):

From: Leo <sdl.web <at> gmail.com>
To: Lars Magne Ingebrigtsen <larsi <at> gnus.org>
Cc: Juanma Barranquero <lekktu <at> gmail.com>, 9118 <at> debbugs.gnu.org
Subject: Re: bug#9118: 23.3.50; Don't seed the RNG in message-unique-id
Date: Mon, 01 Aug 2011 00:02:23 +0800

On 2011-07-31 23:39 +0800, Lars Magne Ingebrigtsen wrote:
> Leo <sdl.web <at> gmail.com> writes:
>
>> +With argument t, set the random number seed from the current time
>> +  and pid and return nil.  */)
>
> This would break old (buggy) usages, so it seems unnecessary.

The fix is straightforward. It is worth the small trouble. I can take
care of fixing all the handful of occurrences in Emacs source.

Leo

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.