Subject: 27.0.60; cl--random-state uncontrolled growth due to bignums

From: Christopher Wellons <[email-masked]>
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))))