From: Pip Cet <pipcet@gmail.com>
To: Eli Zaretskii <eliz@gnu.org>
Cc: Stefan Monnier <monnier@iro.umontreal.ca>, emacs-devel@gnu.org
Subject: Re: master d582356: * src/fns.c (Frandom): Handle bignum `limit`s
Date: Sat, 6 Mar 2021 13:22:10 +0000 [thread overview]
Message-ID: <CAOqdjBcntGEzfmu0Ag080z_nAnQbs-Du3MNu2ovW=CKU4Rg_uQ@mail.gmail.com> (raw)
In-Reply-To: <83k0qkwnwt.fsf@gnu.org>
[-- Attachment #1: Type: text/plain, Size: 1831 bytes --]
On Sat, Mar 6, 2021 at 10:57 AM Eli Zaretskii <eliz@gnu.org> wrote:
> > From: Pip Cet <pipcet@gmail.com>
> > Date: Sat, 6 Mar 2021 09:44:18 +0000
> > Cc: Stefan Monnier <monnier@iro.umontreal.ca>, emacs-devel@gnu.org
> >
> > I thought this code in code_conversion_save was safe:
> >
> > Lisp_Object name
> > = Fgenerate_new_buffer_name (Vcode_conversion_workbuf_name, Qnil);
> > workbuf = Fget_buffer_create (name, Qt);
> >
> > but I had misread the second argument to Fget_buffer_create: it's
> > inhibit-hooks, not run-hooks.
> >
> > So I'm not sure whether code_conversion_save is allowed to call Lisp.
> I'd rather it didn't, for more than one reason. But we can side-step
> this by making Fgenerate_new_buffer_name use random-fixnum, which is
> still a pure-C implementation.
Here's a patch which makes it use get_random() directly.
> > It would really help to document the "doesn't call Lisp" and "doesn't
> > quit" restrictions somewhere (but I'm not volunteering...)
>
> I agree, on both counts.
Actually, I think it would be best to have these restrictions
represented in the code. I see two ways of doing that:
1. Have FUNCTION_MAY_GC etc. translate into a GCC attribute in debug
builds so we can statically check that a function that says it never
calls GC doesn't call a function that says it may call GC.
2. Have a statement at the beginning of non-GCing functions which sets
a flag that is then checked by garbage-collecting functions, so that
we may dynamically check this.
(1) seems easy to implement, but has a high rate of false negatives as
many functions are safe to call from non-GCing functions as long as
the arguments are correct.
(2) is difficult to implement, and would only trigger at runtime.
So I say we should do (1) in preference to (2), but maybe we should do both.
Pip
[-- Attachment #2: 0001-Implement-random-in-Lisp-exposing-only-random-fixnum.patch --]
[-- Type: text/x-patch, Size: 7507 bytes --]
From 755d9fe9a256a72f8cac9e6a006151bd6cc4c46e Mon Sep 17 00:00:00 2001
From: Pip Cet <pipcet@gmail.com>
Date: Sat, 6 Mar 2021 07:37:22 +0000
Subject: [PATCH] Implement random in Lisp, exposing only random-fixnum from C
* src/buffer.c (Fgenerate_new_buffer_name): Call get_random().
* src/fns.c (Frandom): Rename to Frandom_fixnum and simplify.
(ccall2): Remove function.
(random_bignum): Remove function.
(syms_of_fns): Register random-fixnum, not random.
* lisp/subr.el (random): New function.
---
lisp/subr.el | 43 ++++++++++++++++++++++++++++
src/buffer.c | 15 ++++++++--
src/fns.c | 80 +++++-----------------------------------------------
3 files changed, 62 insertions(+), 76 deletions(-)
diff --git a/lisp/subr.el b/lisp/subr.el
index 0b5634739993f..fd7bc0283875b 100644
--- a/lisp/subr.el
+++ b/lisp/subr.el
@@ -6238,4 +6238,47 @@ internal--format-docstring-line
This is intended for internal use only."
(internal--fill-string-single-line (apply #'format string objects)))
+(defun random (&optional limit)
+ "Return a pseudo-random integer.
+By default, return a fixnum; all fixnums are equally likely.
+With positive integer LIMIT, return random integer in interval [0,LIMIT).
+With float argument LIMIT, return a float between 0 and LIMIT.
+With argument t, set the random number seed from the system's entropy
+pool if available, otherwise from less-random volatile data such as the time.
+With a string argument, set the seed based on the string's contents.
+
+See Info node `(elisp)Random Numbers' for more details."
+ (cond
+ ((null limit)
+ (random-fixnum))
+ ((natnump limit)
+ (if (<= limit 0)
+ (error "Non-positive argument"))
+ (let (okay remainder)
+ (while (not okay)
+ (let ((val 0)
+ (lim limit)
+ (bits 0)
+ (bits-per-iteration (1-
+ (truncate
+ (log (1+ most-positive-fixnum) 2)))))
+ (while (not (zerop lim))
+ (let ((rand (logand (1- (lsh 1 bits-per-iteration))
+ (random-fixnum))))
+ (setq bits (+ bits bits-per-iteration))
+ (setq val (logior (lsh val bits-per-iteration)
+ rand))
+ (setq lim (lsh lim (- bits-per-iteration)))))
+ (setq remainder (% val limit))
+ (setq okay (<= (- val remainder)
+ (- (lsh 1 bits) limit)))))
+ remainder))
+ ((floatp limit)
+ (* (random-integer (lsh 1 64))
+ (/ 1.0 (float (lsh 1 64)))
+ limit))
+ ((eq limit t) (random-fixnum limit))
+ ((stringp limit) (random-fixnum limit))
+ ((error "invalid limit %S" limit))))
+
;;; subr.el ends here
diff --git a/src/buffer.c b/src/buffer.c
index 03c10cc7ae5ba..6bdc857bff0b0 100644
--- a/src/buffer.c
+++ b/src/buffer.c
@@ -1149,10 +1149,19 @@ DEFUN ("generate-new-buffer-name", Fgenerate_new_buffer_name,
char number[sizeof "-999999"];
/* Use XFIXNUM instead of XFIXNAT to work around GCC bug 80776. */
- int i = XFIXNUM (Frandom (make_fixnum (1000000)));
- eassume (0 <= i && i < 1000000);
+ EMACS_INT random_fixnum;
+ int random;
+ do
+ {
+ random_fixnum = get_random ();
+ random = random_fixnum % 1000000;
+ }
+ while (random_fixnum - random >= INTMASK + 1 - 1000000);
+ /* GCC sometimes doesn't grok this if written as a single eassume. */
+ eassume (0 <= random);
+ eassume (random < 1000000);
- AUTO_STRING_WITH_LEN (lnumber, number, sprintf (number, "-%d", i));
+ AUTO_STRING_WITH_LEN (lnumber, number, sprintf (number, "-%d", random));
genbase = concat2 (name, lnumber);
if (NILP (Fget_buffer (genbase)))
return genbase;
diff --git a/src/fns.c b/src/fns.c
index b193ad648a96c..a65a5d88d4e4a 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -54,88 +54,22 @@ DEFUN ("identity", Fidentity, Sidentity, 1, 1, 0,
return argument;
}
-static Lisp_Object
-ccall2 (Lisp_Object (f) (ptrdiff_t nargs, Lisp_Object *args),
- Lisp_Object arg1, Lisp_Object arg2)
-{
- Lisp_Object args[2] = {arg1, arg2};
- return f (2, args);
-}
-
-static Lisp_Object
-get_random_bignum (Lisp_Object limit)
-{
- /* This is a naive transcription into bignums of the fixnum algorithm.
- I'd be quite surprised if that's anywhere near the best algorithm
- for it. */
- while (true)
- {
- Lisp_Object val = make_fixnum (0);
- Lisp_Object lim = limit;
- int bits = 0;
- int bitsperiteration = FIXNUM_BITS - 1;
- do
- {
- /* Shift by one so it is a valid positive fixnum. */
- EMACS_INT rand = get_random () >> 1;
- Lisp_Object lrand = make_fixnum (rand);
- bits += bitsperiteration;
- val = ccall2 (Flogior,
- Fash (val, make_fixnum (bitsperiteration)),
- lrand);
- lim = Fash (lim, make_fixnum (- bitsperiteration));
- }
- while (!EQ (lim, make_fixnum (0)));
- /* Return the remainder, except reject the rare case where
- get_random returns a number so close to INTMASK that the
- remainder isn't random. */
- Lisp_Object remainder = Frem (val, limit);
- if (!NILP (ccall2 (Fleq,
- ccall2 (Fminus, val, remainder),
- ccall2 (Fminus,
- Fash (make_fixnum (1), make_fixnum (bits)),
- limit))))
- return remainder;
- }
-}
-
-DEFUN ("random", Frandom, Srandom, 0, 1, 0,
+DEFUN ("random-fixnum", Frandom_fixnum, Srandom_fixnum, 0, 1, 0,
doc: /* Return a pseudo-random integer.
-By default, return a fixnum; all fixnums are equally likely.
-With positive integer LIMIT, return random integer in interval [0,LIMIT).
-With argument t, set the random number seed from the system's entropy
-pool if available, otherwise from less-random volatile data such as the time.
-With a string argument, set the seed based on the string's contents.
+Return a fixnum; all fixnums are equally likely. With argument t, also set
+the random number seed from the system's entropy pool if available, otherwise
+from less-random volatile data such as the time.
+With a string argument, also set the seed based on the string's contents.
See Info node `(elisp)Random Numbers' for more details. */)
(Lisp_Object limit)
{
- EMACS_INT val;
-
if (EQ (limit, Qt))
init_random ();
else if (STRINGP (limit))
seed_random (SSDATA (limit), SBYTES (limit));
- if (BIGNUMP (limit))
- {
- if (0 > mpz_sgn (*xbignum_val (limit)))
- xsignal2 (Qwrong_type_argument, Qnatnump, limit);
- return get_random_bignum (limit);
- }
- val = get_random ();
- if (FIXNUMP (limit) && 0 < XFIXNUM (limit))
- while (true)
- {
- /* Return the remainder, except reject the rare case where
- get_random returns a number so close to INTMASK that the
- remainder isn't random. */
- EMACS_INT remainder = val % XFIXNUM (limit);
- if (val - remainder <= INTMASK - XFIXNUM (limit) + 1)
- return make_fixnum (remainder);
- val = get_random ();
- }
- return make_ufixnum (val);
+ return make_ufixnum (get_random ());
}
\f
/* Random data-structure functions. */
@@ -5968,7 +5902,7 @@ syms_of_fns (void)
use_short_answers = false;
defsubr (&Sidentity);
- defsubr (&Srandom);
+ defsubr (&Srandom_fixnum);
defsubr (&Slength);
defsubr (&Ssafe_length);
defsubr (&Slength_less);
--
2.30.1
next prev parent reply other threads:[~2021-03-06 13:22 UTC|newest]
Thread overview: 19+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <20210305170955.27732.27579@vcs0.savannah.gnu.org>
[not found] ` <20210305170957.AF99920E1B@vcs0.savannah.gnu.org>
2021-03-05 19:42 ` master d582356: * src/fns.c (Frandom): Handle bignum `limit`s Pip Cet
2021-03-05 19:56 ` Stefan Monnier
2021-03-05 20:13 ` Pip Cet
2021-03-05 20:34 ` Stefan Monnier
2021-03-06 7:42 ` Pip Cet
2021-03-06 8:44 ` Eli Zaretskii
2021-03-06 9:44 ` Pip Cet
2021-03-06 10:56 ` Eli Zaretskii
2021-03-06 13:22 ` Pip Cet [this message]
2021-03-06 14:45 ` Eli Zaretskii
2021-03-07 13:27 ` Pip Cet
2021-03-07 14:04 ` Eli Zaretskii
2021-03-07 14:21 ` Pip Cet
2021-03-07 15:22 ` Eli Zaretskii
2021-03-07 17:23 ` Pip Cet
2021-03-07 17:47 ` Eli Zaretskii
2021-03-07 18:37 ` Stefan Monnier
2021-03-07 19:54 ` Andrea Corallo via Emacs development discussions.
2021-03-07 19:55 ` Pip Cet
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAOqdjBcntGEzfmu0Ag080z_nAnQbs-Du3MNu2ovW=CKU4Rg_uQ@mail.gmail.com' \
--to=pipcet@gmail.com \
--cc=eliz@gnu.org \
--cc=emacs-devel@gnu.org \
--cc=monnier@iro.umontreal.ca \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.