GNU bug report logs - #38753
27.0.60; cl--random-state uncontrolled growth due to bignums

Previous Next

Full log

View this message in rfc822 format

From: help-debbugs <at> gnu.org (GNU bug Tracking System)
To: Mattias Engdegård <mattiase <at> acm.org>
Cc: tracker <at> debbugs.gnu.org
Subject: bug#38753: closed (27.0.60; cl--random-state uncontrolled growth
 due to bignums)
Date: Sun, 29 Dec 2019 13:00:02 +0000

[Message part 1 (text/plain, inline)]

Your message dated Sun, 29 Dec 2019 13:59:31 +0100
with message-id <1A4F12F2-5DE3-4F42-8956-BD2DD27C4D47 <at> acm.org>
and subject line bug#38753: 27.0.60; cl--random-state uncontrolled growth due to bignums
has caused the debbugs.gnu.org bug report #38753,
regarding 27.0.60; cl--random-state uncontrolled growth due to bignums
to be marked as done.

(If you believe you have received this mail in error, please contact
help-debbugs <at> gnu.org.)


-- 
38753: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=38753
GNU Bug Tracking System
Contact help-debbugs <at> gnu.org with problems

[Message part 2 (message/rfc822, inline)]

From: Christopher Wellons <wellons <at> nullprogram.com>
To: bug-gnu-emacs <at> gnu.org
Subject: 27.0.60; cl--random-state uncontrolled growth due to bignums
Date: Thu, 26 Dec 2019 12:12:07 -0500

The cl-random generator was not written for bignums, so it misbehaves in
Emacs 27. After generating a few million numbers from any particular
state, it will only signal "Arithmetic overflow error". The generator
relies on fixnums wrapping via two's complement. In Emacs 27, fixnums
turn into bignums rather than wrap, so the state grows until reaching
the bignum limit, then breaks.

The cl-random function is a lagged Fibonacci generator. The output is
the difference of two integers at special "taps" in the state vector,
and one tap is replaced with the output. The output is properly
truncated using logand, but state update is not, and it soon fills with
growing bignums.

The fix is trivial: Move the logand truncation so that it applies to
both the output and the state update. The truncated bits are never used
so the output of the generator remains unchanged.

diff --git a/lisp/emacs-lisp/cl-extra.el b/lisp/emacs-lisp/cl-extra.el
index 7e9d8fe870..2e0b37c14d 100644
--- a/lisp/emacs-lisp/cl-extra.el
+++ b/lisp/emacs-lisp/cl-extra.el
@@ -469,7 +469,7 @@ cl-random
	  (while (< (setq i (1+ i)) 200) (cl-random 2 state))))
    (let* ((i (cl-callf (lambda (x) (% (1+ x) 55)) (cl--random-state-i state)))
	   (j (cl-callf (lambda (x) (% (1+ x) 55)) (cl--random-state-j state)))
-	   (n (logand 8388607 (aset vec i (- (aref vec i) (aref vec j))))))
+	   (n (aset vec i (logand 8388607 (- (aref vec i) (aref vec j))))))
      (if (integerp lim)
	  (if (<= lim 512) (% n lim)
	    (if (> lim 8388607) (setq n (+ (ash n 9) (cl-random 512 state))))

[Message part 3 (message/rfc822, inline)]

From: Mattias Engdegård <mattiase <at> acm.org>
To: 38753-done <at> debbugs.gnu.org
Subject: bug#38753: 27.0.60; cl--random-state uncontrolled growth due to
 bignums
Date: Sun, 29 Dec 2019 13:59:31 +0100

Thank you! The proposed fix indeed looks correct; applied to emacs-27.

Previous Next

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