bug#32463: 27.0.50; (logior -1) => 4611686018427387903

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Katsumi Yamaoka]

Hi,

What do I have to do to get -1 by `(logior -1)' ?  Otherwise,
is it just a bug?  Setting `binary-as-unsigned' has no effect.

I'm using an old input method sj3-egg[1] but it got not to work.
The following Lisp snippet shows what it does first when opening
the connection to the sj3 server:

(with-temp-buffer
  (set-buffer-multibyte nil)
  (let ((pt (point-min)))
    (insert "\377\377\377\376")
    (logior
     (lsh (- (logxor (char-after pt) 128) 128) 24)
     (lsh (char-after (+ pt 1)) 16)
     (lsh (char-after (+ pt 2)) 8)
     (lsh (char-after (+ pt 3)) 0))))

It should return -2, but 4611686018427387902 now.
(Oh, it's doubled most-positive-fixnum!)

Thanks.

[1] http://www.jpl.org/ftp/pub/elisp/sj3-egg-0.8.5.tar.gz

In GNU Emacs 27.0.50 (build 1, x86_64-unknown-cygwin, GTK+ Version 3.22.28)
 of 2018-08-17 built on localhost
Windowing system distributor 'The Cygwin/X Project', version 11.0.12000000

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Pip Cet]

[-- Attachment #1: Type: text/plain, Size: 2482 bytes --]

Can you try the attached patch? It fixes a few things that I reported
to Tom yesterday:

---


None of these are necessarily bugs, but:

* I find the behavior of `lsh', `logand', `logior', and `logxor', when
given negative arguments, surprising. I think it would make most sense
to treat negative numbers as the infinite bitstream consisting of all
ones to the left of the specified value:

(logand -1 -1) would be interpreted as ...1111111 & ...1111111 =
...1111111, so it would be -1 (rather than 2 * most-positive-fixnum +
1).
(lsh (- (lsh -1 64) 1) -1) would be ...1110111...1111 shifted to the
right by one digit, an odd number, rather than the even number
currently produced. (I believe lsh and ash should behave identically.)

* the documentation of `random' still refers to representable integers
* I think we should rename `random' to `random-fixnum' and add a Lisp
function `random' which accepts positive fixnum, bignum, and float
arguments, doing the right thing for each. `cl-random' similarly needs
updating, or documentation of its current 32-bit nature.
* there appears to be a most-positive-bignum; on x86-64, it consists
of 0x7fffffff 8-byte words of one bits, 16 GiB. Operating on integers
larger than that will currently abort emacs with an error message:
"gmp: overflow in mpz type".
* long-running bignum operations appear not to be interruptible.

Please consider something like the attached patch?

Thanks!
On Fri, Aug 17, 2018 at 3:31 AM Katsumi Yamaoka <yamaoka@jpl.org> wrote:
>
> Hi,
>
> What do I have to do to get -1 by `(logior -1)' ?  Otherwise,
> is it just a bug?  Setting `binary-as-unsigned' has no effect.
>
> I'm using an old input method sj3-egg[1] but it got not to work.
> The following Lisp snippet shows what it does first when opening
> the connection to the sj3 server:
>
> (with-temp-buffer
>   (set-buffer-multibyte nil)
>   (let ((pt (point-min)))
>     (insert "\377\377\377\376")
>     (logior
>      (lsh (- (logxor (char-after pt) 128) 128) 24)
>      (lsh (char-after (+ pt 1)) 16)
>      (lsh (char-after (+ pt 2)) 8)
>      (lsh (char-after (+ pt 3)) 0))))
>
> It should return -2, but 4611686018427387902 now.
> (Oh, it's doubled most-positive-fixnum!)
>
> Thanks.
>
> [1] http://www.jpl.org/ftp/pub/elisp/sj3-egg-0.8.5.tar.gz
>
> In GNU Emacs 27.0.50 (build 1, x86_64-unknown-cygwin, GTK+ Version 3.22.28)
>  of 2018-08-17 built on localhost
> Windowing system distributor 'The Cygwin/X Project', version 11.0.12000000
>
>
>

[-- Attachment #2: Minor-bignum-tweaks.patch --]
[-- Type: text/x-patch, Size: 3209 bytes --]

diff --git a/src/data.c b/src/data.c
index a1215b9d6bf..eb15bc5bdda 100644
--- a/src/data.c
+++ b/src/data.c
@@ -3006,7 +3006,7 @@ arith_driver (enum arithop code, ptrdiff_t nargs, Lisp_Object *args)
 	    {
 	      mpz_t tem;
 	      mpz_init (tem);
-	      mpz_set_uintmax (tem, XUFIXNUM (val));
+	      mpz_set_intmax (tem, XFIXNUM (val));
 	      mpz_and (accum, accum, tem);
 	      mpz_clear (tem);
 	    }
@@ -3018,7 +3018,7 @@ arith_driver (enum arithop code, ptrdiff_t nargs, Lisp_Object *args)
 	    {
 	      mpz_t tem;
 	      mpz_init (tem);
-	      mpz_set_uintmax (tem, XUFIXNUM (val));
+	      mpz_set_intmax (tem, XFIXNUM (val));
 	      mpz_ior (accum, accum, tem);
 	      mpz_clear (tem);
 	    }
@@ -3030,7 +3030,7 @@ arith_driver (enum arithop code, ptrdiff_t nargs, Lisp_Object *args)
 	    {
 	      mpz_t tem;
 	      mpz_init (tem);
-	      mpz_set_uintmax (tem, XUFIXNUM (val));
+	      mpz_set_intmax (tem, XFIXNUM (val));
 	      mpz_xor (accum, accum, tem);
 	      mpz_clear (tem);
 	    }
@@ -3383,8 +3383,6 @@ ash_lsh_impl (Lisp_Object value, Lisp_Object count, bool lsh)
       mpz_init (result);
       if (XFIXNUM (count) >= 0)
 	mpz_mul_2exp (result, XBIGNUM (value)->value, XFIXNUM (count));
-      else if (lsh)
-	mpz_tdiv_q_2exp (result, XBIGNUM (value)->value, - XFIXNUM (count));
       else
 	mpz_fdiv_q_2exp (result, XBIGNUM (value)->value, - XFIXNUM (count));
       val = make_number (result);
@@ -3401,14 +3399,7 @@ ash_lsh_impl (Lisp_Object value, Lisp_Object count, bool lsh)
 
       if (XFIXNUM (count) >= 0)
 	mpz_mul_2exp (result, result, XFIXNUM (count));
-      else if (lsh)
-	{
-	  if (mpz_sgn (result) > 0)
-	    mpz_fdiv_q_2exp (result, result, - XFIXNUM (count));
-	  else
-	    mpz_fdiv_q_2exp (result, result, - XFIXNUM (count));
-	}
-      else /* ash */
+      else
 	mpz_fdiv_q_2exp (result, result, - XFIXNUM (count));
 
       val = make_number (result);
diff --git a/src/fns.c b/src/fns.c
index f6e68036413..5f4b455b503 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -56,15 +56,15 @@ DEFUN ("identity", Fidentity, Sidentity, 1, 1, 0,
 }
 
 DEFUN ("random", Frandom, Srandom, 0, 1, 0,
-       doc: /* Return a pseudo-random number.
-All integers representable in Lisp, i.e. between `most-negative-fixnum'
+       doc: /* Return a pseudo-random fixnum.
+All integers representable as fixnums, i.e. between `most-negative-fixnum'
 and `most-positive-fixnum', inclusive, are equally likely.
 
-With positive integer LIMIT, return random number 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.
-Other values of LIMIT are ignored.
+With positive fixnum integer LIMIT, return random number 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.  Other values of LIMIT are ignored.
 
 See Info node `(elisp)Random Numbers' for more details.  */)
   (Lisp_Object limit)

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Katsumi Yamaoka]

On Fri, 17 Aug 2018 05:59:14 +0000, Pip Cet wrote:
> Can you try the attached patch? It fixes a few things that I reported
> to Tom yesterday:

Oh, the patch solves my problem.  sj3-egg now works as before.
Thank you!

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Andy Moreton]

On Fri 17 Aug 2018, Pip Cet wrote:

> Can you try the attached patch? It fixes a few things that I reported
> to Tom yesterday:
>
> ---
>
>
> None of these are necessarily bugs, but:
>
> * I find the behavior of `lsh', `logand', `logior', and `logxor', when
> given negative arguments, surprising. I think it would make most sense
> to treat negative numbers as the infinite bitstream consisting of all
> ones to the left of the specified value:
>
> (logand -1 -1) would be interpreted as ...1111111 & ...1111111 =
> ...1111111, so it would be -1 (rather than 2 * most-positive-fixnum +
> 1).
> (lsh (- (lsh -1 64) 1) -1) would be ...1110111...1111 shifted to the
> right by one digit, an odd number, rather than the even number
> currently produced. (I believe lsh and ash should behave identically.)

> @@ -3383,8 +3383,6 @@ ash_lsh_impl (Lisp_Object value, Lisp_Object count, bool lsh)
>        mpz_init (result);
>        if (XFIXNUM (count) >= 0)
>  	mpz_mul_2exp (result, XBIGNUM (value)->value, XFIXNUM (count));
> -      else if (lsh)
> -	mpz_tdiv_q_2exp (result, XBIGNUM (value)->value, - XFIXNUM (count));
>        else
>  	mpz_fdiv_q_2exp (result, XBIGNUM (value)->value, - XFIXNUM (count));
>        val = make_number (result);
> @@ -3401,14 +3399,7 @@ ash_lsh_impl (Lisp_Object value, Lisp_Object count, bool lsh)

Please add more test cases to test/src/data-tests.el to ensure that the
logical operations have the expected behaviour for positive and negative
arguments, and for both bignum and fixnum arguments. The tdiv/fdiv were
added to give expected results. Pay particular attention to values around
most-positive-fixnum and most-negative-fixnum.

>        if (XFIXNUM (count) >= 0)
>  	mpz_mul_2exp (result, result, XFIXNUM (count));
> -      else if (lsh)
> -	{
> -	  if (mpz_sgn (result) > 0)
> -	    mpz_fdiv_q_2exp (result, result, - XFIXNUM (count));
> -	  else
> -	    mpz_fdiv_q_2exp (result, result, - XFIXNUM (count));
> -	}
> -      else /* ash */
> +      else
>  	mpz_fdiv_q_2exp (result, result, - XFIXNUM (count));

This part is an obvious simplification and is fine (I should have
spotted it before sending my patch that Tom committed).

    AndyM

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Pip Cet]

On Fri, Aug 17, 2018 at 9:34 AM Andy Moreton <andrewjmoreton@gmail.com> wrote:
>
> On Fri 17 Aug 2018, Pip Cet wrote:
>
> > Can you try the attached patch? It fixes a few things that I reported
> > to Tom yesterday:
> >
> > ---
> >
> >
> > None of these are necessarily bugs, but:
> >
> > * I find the behavior of `lsh', `logand', `logior', and `logxor', when
> > given negative arguments, surprising. I think it would make most sense
> > to treat negative numbers as the infinite bitstream consisting of all
> > ones to the left of the specified value:
> >
> > (logand -1 -1) would be interpreted as ...1111111 & ...1111111 =
> > ...1111111, so it would be -1 (rather than 2 * most-positive-fixnum +
> > 1).
> > (lsh (- (lsh -1 64) 1) -1) would be ...1110111...1111 shifted to the
> > right by one digit, an odd number, rather than the even number
> > currently produced. (I believe lsh and ash should behave identically.)
>
> > @@ -3383,8 +3383,6 @@ ash_lsh_impl (Lisp_Object value, Lisp_Object count, bool lsh)
> >        mpz_init (result);
> >        if (XFIXNUM (count) >= 0)
> >       mpz_mul_2exp (result, XBIGNUM (value)->value, XFIXNUM (count));
> > -      else if (lsh)
> > -     mpz_tdiv_q_2exp (result, XBIGNUM (value)->value, - XFIXNUM (count));
> >        else
> >       mpz_fdiv_q_2exp (result, XBIGNUM (value)->value, - XFIXNUM (count));
> >        val = make_number (result);
> > @@ -3401,14 +3399,7 @@ ash_lsh_impl (Lisp_Object value, Lisp_Object count, bool lsh)
>
> Please add more test cases to test/src/data-tests.el to ensure that the
> logical operations have the expected behaviour for positive and negative
> arguments, and for both bignum and fixnum arguments.

Paul committed a patch in the meantime (independently, I think?) which
does add tests. I'll try to write some more.

> The tdiv/fdiv were
> added to give expected results. Pay particular attention to values around
> most-positive-fixnum and most-negative-fixnum.

I don't think they do give the expected results. We should discuss
that in more detail, but first, can we agree that lsh and ash behave
the same for bignums? If so, clearly one branch of the code you quoted
is incorrect, and I think it's the tdiv one.

I ran:

(require 'cl)

(let ((i 0))
  (while (< i 128)
    (message "%d %x" i (lsh (- (lsh -1 i) 1) -1))
    (incf i)))

and got this output:

[...]
57 -100000000000001
58 -200000000000001
59 -400000000000001
60 -800000000000001
61 -1000000000000000
62 -2000000000000000
63 -4000000000000000
64 -8000000000000000
[...]

Something is wrong there. The expression certainly shouldn't switch
from being odd to being even just because we're leaving the fixnum
range. If I do the calculation by hand on a piece of paper, I get the
results that correspond to the fixnum case, not the bignum case.

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Pip Cet]

[-- Attachment #1: Type: text/plain, Size: 293 bytes --]

On Fri, Aug 17, 2018 at 11:36 AM Pip Cet <pipcet@gmail.com> wrote:
> and got this output:

I forgot to mention this is on an x86-64 machine with a Linux kernel
and Debian GNU/Linux, and external libgmp.

I'm attaching the patch that I think should still be applied, which
includes some tests.

[-- Attachment #2: Minor-bignum-tweaks-002.patch --]
[-- Type: text/x-patch, Size: 3536 bytes --]

diff --git a/src/data.c b/src/data.c
index 5a355d9787c..077cc8283eb 100644
--- a/src/data.c
+++ b/src/data.c
@@ -3382,8 +3382,6 @@ ash_lsh_impl (Lisp_Object value, Lisp_Object count, bool lsh)
       mpz_init (result);
       if (XFIXNUM (count) >= 0)
 	mpz_mul_2exp (result, XBIGNUM (value)->value, XFIXNUM (count));
-      else if (lsh)
-	mpz_tdiv_q_2exp (result, XBIGNUM (value)->value, - XFIXNUM (count));
       else
 	mpz_fdiv_q_2exp (result, XBIGNUM (value)->value, - XFIXNUM (count));
       val = make_number (result);
@@ -3400,14 +3398,7 @@ ash_lsh_impl (Lisp_Object value, Lisp_Object count, bool lsh)
 
       if (XFIXNUM (count) >= 0)
 	mpz_mul_2exp (result, result, XFIXNUM (count));
-      else if (lsh)
-	{
-	  if (mpz_sgn (result) > 0)
-	    mpz_fdiv_q_2exp (result, result, - XFIXNUM (count));
-	  else
-	    mpz_fdiv_q_2exp (result, result, - XFIXNUM (count));
-	}
-      else /* ash */
+      else
 	mpz_fdiv_q_2exp (result, result, - XFIXNUM (count));
 
       val = make_number (result);
diff --git a/src/fns.c b/src/fns.c
index f6e68036413..5f4b455b503 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -56,15 +56,15 @@ DEFUN ("identity", Fidentity, Sidentity, 1, 1, 0,
 }
 
 DEFUN ("random", Frandom, Srandom, 0, 1, 0,
-       doc: /* Return a pseudo-random number.
-All integers representable in Lisp, i.e. between `most-negative-fixnum'
+       doc: /* Return a pseudo-random fixnum.
+All integers representable as fixnums, i.e. between `most-negative-fixnum'
 and `most-positive-fixnum', inclusive, are equally likely.
 
-With positive integer LIMIT, return random number 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.
-Other values of LIMIT are ignored.
+With positive fixnum integer LIMIT, return random number 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.  Other values of LIMIT are ignored.
 
 See Info node `(elisp)Random Numbers' for more details.  */)
   (Lisp_Object limit)
diff --git a/test/src/data-tests.el b/test/src/data-tests.el
index a4c6b0e4915..6a2578e19a0 100644
--- a/test/src/data-tests.el
+++ b/test/src/data-tests.el
@@ -614,6 +614,11 @@ binding-test-some-local
   (let ((n (1+ most-positive-fixnum)))
     (should (= (logxor -1 n) (lognot n)))))
 
+(ert-deftest data-tests-logand ()
+  (should (= -1 (logand) (logand -1) (logand -1 -1)))
+  (let ((n (1+ most-positive-fixnum)))
+    (should (= (logand -1 n) n))))
+
 (ert-deftest data-tests-minmax ()
   (let ((a (- most-negative-fixnum 1))
         (b (+ most-positive-fixnum 1))
@@ -642,6 +647,14 @@ data-tests-check-sign
   (should (= (ash most-negative-fixnum 1)
              (* most-negative-fixnum 2)))
   (should (= (lsh most-negative-fixnum 1)
-             (* most-negative-fixnum 2))))
+             (* most-negative-fixnum 2)))
+  (should (= (ash (* 2 most-negative-fixnum) -1)
+             most-negative-fixnum))
+  (should (= (lsh (* 2 most-negative-fixnum) -1)
+             most-negative-fixnum))
+  (should (= (lsh (- (lsh most-negative-fixnum 1) 1) -1)
+             (- most-negative-fixnum 1)))
+  (should (= (ash (- (lsh most-negative-fixnum 1) 1) -1)
+             (- most-negative-fixnum 1))))
 
 ;;; data-tests.el ends here

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Andy Moreton]

On Fri 17 Aug 2018, Pip Cet wrote:

> On Fri, Aug 17, 2018 at 11:36 AM Pip Cet <pipcet@gmail.com> wrote:
>> and got this output:
>
> I forgot to mention this is on an x86-64 machine with a Linux kernel
> and Debian GNU/Linux, and external libgmp.
>
> I'm attaching the patch that I think should still be applied, which
> includes some tests.

I have tried this patch on a Windows MSYS2 mingw64 x86_64 build [1], and
the updated data-tests pass. Thanks for fixing the bugs I introduced.

    AndyM

[1] This needs a patched gmp.h to avoid a different problem with
incorrect DLL imports from libgmp-10.dll that break Flogcount.

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 257 bytes --]

Pip Cet wrote:
> I'm attaching the patch that I think should still be applied, which
> includes some tests.

Thanks. I think most of that patch was addressed by my previous patch, except 
for the doc changes for 'random' for which I installed the attached.

[-- Attachment #2: 0001-Document-that-random-is-limited-to-fixnums.txt --]
[-- Type: text/plain, Size: 2557 bytes --]

From 97d273033b523bc07911c848d4e8bf96cdce0c90 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Sat, 18 Aug 2018 15:39:05 -0700
Subject: [PATCH] =?UTF-8?q?Document=20that=20=E2=80=98random=E2=80=99=20is?=
 =?UTF-8?q?=20limited=20to=20fixnums?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

Problem reported by Pip Cet (Bug#32463#20).
* doc/lispref/numbers.texi (Random Numbers):
* src/fns.c (Frandom): Adjust doc.
---
 doc/lispref/numbers.texi | 7 +++----
 src/fns.c                | 9 +++------
 2 files changed, 6 insertions(+), 10 deletions(-)

diff --git a/doc/lispref/numbers.texi b/doc/lispref/numbers.texi
index ee6456b1be..74a313e2e1 100644
--- a/doc/lispref/numbers.texi
+++ b/doc/lispref/numbers.texi
@@ -1236,11 +1236,10 @@ Random Numbers
 This function returns a pseudo-random integer.  Repeated calls return a
 series of pseudo-random integers.
 
-If @var{limit} is a positive integer, the value is chosen to be
+If @var{limit} is a positive fixnum, the value is chosen to be
 nonnegative and less than @var{limit}.  Otherwise, the value might be
-any integer representable in Lisp, i.e., an integer between
-@code{most-negative-fixnum} and @code{most-positive-fixnum}
-(@pxref{Integer Basics}).
+any fixnum, i.e., any integer from @code{most-negative-fixnum} through
+@code{most-positive-fixnum} (@pxref{Integer Basics}).
 
 If @var{limit} is @code{t}, it means to choose a new seed as if Emacs
 were restarting, typically from the system entropy.  On systems
diff --git a/src/fns.c b/src/fns.c
index f6e6803641..a11de1b082 100644
--- a/src/fns.c
+++ b/src/fns.c
@@ -56,15 +56,12 @@ DEFUN ("identity", Fidentity, Sidentity, 1, 1, 0,
 }
 
 DEFUN ("random", Frandom, Srandom, 0, 1, 0,
-       doc: /* Return a pseudo-random number.
-All integers representable in Lisp, i.e. between `most-negative-fixnum'
-and `most-positive-fixnum', inclusive, are equally likely.
-
-With positive integer LIMIT, return random number in interval [0,LIMIT).
+       doc: /* Return a pseudo-random integer.
+By default, return a fixnum; all fixnums are equally likely.
+With positive fixnum 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.
-Other values of LIMIT are ignored.
 
 See Info node `(elisp)Random Numbers' for more details.  */)
   (Lisp_Object limit)
-- 
2.17.1

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Andy Moreton]

On Fri 17 Aug 2018, Pip Cet wrote:

> On Fri, Aug 17, 2018 at 9:34 AM Andy Moreton <andrewjmoreton@gmail.com> wrote:
> Paul committed a patch in the meantime (independently, I think?) which
> does add tests. I'll try to write some more.

Thanks. I should have done that with my patches to fix some bignum bugs.

>> The tdiv/fdiv were
>> added to give expected results. Pay particular attention to values around
>> most-positive-fixnum and most-negative-fixnum.
>
> I don't think they do give the expected results. We should discuss
> that in more detail, but first, can we agree that lsh and ash behave
> the same for bignums? If so, clearly one branch of the code you quoted
> is incorrect, and I think it's the tdiv one.

I agree that for bignums lsh and ash should behave the same way. I can
easily belive that there are bugs in this code, as I was fighting
problems with 64bit Windows having 32bit long at the same time.

> I ran:
>
> (require 'cl)
>
> (let ((i 0))
>   (while (< i 128)
>     (message "%d %x" i (lsh (- (lsh -1 i) 1) -1))
>     (incf i)))

Or equivalently:
  (dotimes (i 128) (message "%d %x" i (lsh (1- (lsh -1 i)) -1)))

> and got this output:
>
> [...]
> 57 -100000000000001
> 58 -200000000000001
> 59 -400000000000001
> 60 -800000000000001
> 61 -1000000000000000
> 62 -2000000000000000
> 63 -4000000000000000
> 64 -8000000000000000
> [...]
>
> Something is wrong there.

Yes, this is clearly not behaving correctly and needs to be fixed.
Thanks for investigating this.

    AndyM

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Paul Eggert]

Pip Cet wrote:

> Paul committed a patch in the meantime (independently, I think?) which
> does add tests. I'll try to write some more.

Yes, I noticed the logior etc. problem separately and fixed it in master without 
knowing about this bug report. There are some other bignum problems too that 
need fixing and are in my pipeline.

> can we agree that lsh and ash behave
> the same for bignums?

It would be weird for lsh to act one way for negative bignums, and a different 
and incompatible way for negative fixnums. Instead, I suggest that we deprecate 
lsh, as it doesn't make sense any more now that integers have unbounded size. 
While we're deprecating it, we can make (lsh A B) signal an error if A is a 
bignum and B is negative, since there's nothing we can do there that is 
reasonable and is compatible with the fixnum behavior.

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Eli Zaretskii]

> From: Paul Eggert <eggert@cs.ucla.edu>
> Date: Sat, 18 Aug 2018 11:48:11 -0700
> Cc: 32463@debbugs.gnu.org
> 
> It would be weird for lsh to act one way for negative bignums, and a different 
> and incompatible way for negative fixnums. Instead, I suggest that we deprecate 
> lsh, as it doesn't make sense any more now that integers have unbounded size. 

It is IMO absurd for us to deprecate a valid and useful operation just
because we added bignums.  If we cannot agree on its semantics for
bignums (which would surprise me), then it is better to make it not
work for bignums at all than deprecate it for fixnums.

> While we're deprecating it, we can make (lsh A B) signal an error if A is a 
> bignum and B is negative, since there's nothing we can do there that is 
> reasonable and is compatible with the fixnum behavior.

If that's the best we can do, fine.  But it doesn't require
deprecating lsh while we are at it.

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Pip Cet]

On Sat, Aug 18, 2018 at 7:00 PM Eli Zaretskii <eliz@gnu.org> wrote:
>
> > From: Paul Eggert <eggert@cs.ucla.edu>
> > Date: Sat, 18 Aug 2018 11:48:11 -0700
> > Cc: 32463@debbugs.gnu.org
> >
> > It would be weird for lsh to act one way for negative bignums, and a different
> > and incompatible way for negative fixnums. Instead, I suggest that we deprecate
> > lsh, as it doesn't make sense any more now that integers have unbounded size.
>
> It is IMO absurd for us to deprecate a valid and useful operation just
> because we added bignums.  If we cannot agree on its semantics for
> bignums (which would surprise me), then it is better to make it not
> work for bignums at all than deprecate it for fixnums.

The recent code changes made `lsh' behave the same as `ash' for
fixnums, if I understand correctly. Are you suggesting we revert to
the previous behavior, and try to come up with an interpretation for
bignums that somehow extends the previous behavior?

(In any case, the current code for bignums is inconsistent for the
low-order bits that should be unaffected by whatever convention we
choose).

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 591 bytes --]

Pip Cet wrote:
> Are you suggesting we revert to
> the previous behavior, and try to come up with an interpretation for
> bignums that somehow extends the previous behavior?

I think Eli was suggesting reverting lsh to the traditional behavior for 
fixnums, for backwards-compatibility reasons.

There doesn't seem to be a good way to extend this behavior for bignums, so I 
installed the attached patch that simply makes it an error to invoke (lsh A B) 
where A is a negative bignum and B is negative. This patch also adds some test 
cases inspired by one of your previous emails (thanks).

[-- Attachment #2: 0001-Restore-traditional-lsh-behavior-on-fixnums.txt --]
[-- Type: text/plain, Size: 10598 bytes --]

From 673b1785db4604efe81b8045a9d8ab68936af719 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Sat, 18 Aug 2018 15:20:46 -0700
Subject: [PATCH] Restore traditional lsh behavior on fixnums
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

* doc/lispref/numbers.texi (Bitwise Operations): Document that
the traditional (lsh A B) behavior is for fixnums, and that it
is an error if A and B are both negative and A is a bignum.
See Bug#32463.
* lisp/subr.el (lsh): New function, moved here from src/data.c.
* src/data.c (ash_lsh_impl): Remove, moving body into Fash
since it’s the only caller now.
(Fash): Check for out-of-range counts.  If COUNT is zero,
return first argument instead of going through libgmp.  Omit
lsh code since lsh is now done in Lisp.  Add code for shifting
fixnums right, to avoid a round trip through libgmp.
(Flsh): Remove; moved to lisp/subr.el.
* test/lisp/international/ccl-tests.el (shift):
Test for traditional lsh behavior, instead of assuming
lsh is like ash when bignums are present.
* test/src/data-tests.el (data-tests-logand)
(data-tests-logior, data-tests-logxor, data-tests-ash-lsh):
New tests.
---
 doc/lispref/numbers.texi             |  7 +++-
 lisp/subr.el                         | 12 ++++++
 src/data.c                           | 60 +++++++++++-----------------
 test/lisp/international/ccl-tests.el | 21 +++-------
 test/src/data-tests.el               | 16 ++++++--
 5 files changed, 59 insertions(+), 57 deletions(-)

diff --git a/doc/lispref/numbers.texi b/doc/lispref/numbers.texi
index 37d2c31649..ee6456b1be 100644
--- a/doc/lispref/numbers.texi
+++ b/doc/lispref/numbers.texi
@@ -844,7 +844,9 @@ Bitwise Operations
 if @var{count} is negative, bringing zeros into the vacated bits.  If
 @var{count} is negative, @code{lsh} shifts zeros into the leftmost
 (most-significant) bit, producing a nonnegative result even if
-@var{integer1} is negative.  Contrast this with @code{ash}, below.
+@var{integer1} is negative fixnum.  (If @var{integer1} is a negative
+bignum, @var{count} must be nonnegative.)  Contrast this with
+@code{ash}, below.
 
 Here are two examples of @code{lsh}, shifting a pattern of bits one
 place to the left.  We show only the low-order eight bits of the binary
@@ -913,7 +915,8 @@ Bitwise Operations
 @code{ash} gives the same results as @code{lsh} except when
 @var{integer1} and @var{count} are both negative.  In that case,
 @code{ash} puts ones in the empty bit positions on the left, while
-@code{lsh} puts zeros in those bit positions.
+@code{lsh} puts zeros in those bit positions and requires
+@var{integer1} to be a fixnum.
 
 Thus, with @code{ash}, shifting the pattern of bits one place to the right
 looks like this:
diff --git a/lisp/subr.el b/lisp/subr.el
index fbb3e49a35..cafa4835ea 100644
--- a/lisp/subr.el
+++ b/lisp/subr.el
@@ -366,6 +366,18 @@ zerop
   (declare (compiler-macro (lambda (_) `(= 0 ,number))))
   (= 0 number))
 
+(defun lsh (value count)
+  "Return VALUE with its bits shifted left by COUNT.
+If COUNT is negative, shifting is actually to the right.
+In this case, if VALUE is a negative fixnum treat it as unsigned,
+i.e., subtract 2 * most-negative-fixnum from VALUE before shifting it."
+  (when (and (< value 0) (< count 0))
+    (when (< value most-negative-fixnum)
+      (signal 'args-out-of-range (list value count)))
+    (setq value (logand (ash value -1) most-positive-fixnum))
+    (setq count (1+ count)))
+  (ash value count))
+
 \f
 ;;;; List functions.
 
diff --git a/src/data.c b/src/data.c
index 5a355d9787..a39978ab1d 100644
--- a/src/data.c
+++ b/src/data.c
@@ -3365,30 +3365,44 @@ representation.  */)
 		      : count_one_bits_ll (v));
 }
 
-static Lisp_Object
-ash_lsh_impl (Lisp_Object value, Lisp_Object count, bool lsh)
+DEFUN ("ash", Fash, Sash, 2, 2, 0,
+       doc: /* Return VALUE with its bits shifted left by COUNT.
+If COUNT is negative, shifting is actually to the right.
+In this case, the sign bit is duplicated.  */)
+  (Lisp_Object value, Lisp_Object count)
 {
-  /* This code assumes that signed right shifts are arithmetic.  */
-  verify ((EMACS_INT) -1 >> 1 == -1);
-
   Lisp_Object val;
 
+  /* The negative of the minimum value of COUNT that fits into a fixnum,
+     such that mpz_fdiv_q_exp supports -COUNT.  */
+  EMACS_INT minus_count_min = min (-MOST_NEGATIVE_FIXNUM,
+				   TYPE_MAXIMUM (mp_bitcnt_t));
   CHECK_INTEGER (value);
-  CHECK_FIXNUM (count);
+  CHECK_RANGED_INTEGER (count, - minus_count_min, TYPE_MAXIMUM (mp_bitcnt_t));
 
   if (BIGNUMP (value))
     {
+      if (XFIXNUM (count) == 0)
+	return value;
       mpz_t result;
       mpz_init (result);
-      if (XFIXNUM (count) >= 0)
+      if (XFIXNUM (count) > 0)
 	mpz_mul_2exp (result, XBIGNUM (value)->value, XFIXNUM (count));
-      else if (lsh)
-	mpz_tdiv_q_2exp (result, XBIGNUM (value)->value, - XFIXNUM (count));
       else
 	mpz_fdiv_q_2exp (result, XBIGNUM (value)->value, - XFIXNUM (count));
       val = make_number (result);
       mpz_clear (result);
     }
+  else if (XFIXNUM (count) <= 0)
+    {
+      /* This code assumes that signed right shifts are arithmetic.  */
+      verify ((EMACS_INT) -1 >> 1 == -1);
+
+      EMACS_INT shift = -XFIXNUM (count);
+      EMACS_INT result = (shift < EMACS_INT_WIDTH ? XFIXNUM (value) >> shift
+			  : XFIXNUM (value) < 0 ? -1 : 0);
+      val = make_fixnum (result);
+    }
   else
     {
       /* Just do the work as bignums to make the code simpler.  */
@@ -3400,14 +3414,7 @@ ash_lsh_impl (Lisp_Object value, Lisp_Object count, bool lsh)
 
       if (XFIXNUM (count) >= 0)
 	mpz_mul_2exp (result, result, XFIXNUM (count));
-      else if (lsh)
-	{
-	  if (mpz_sgn (result) > 0)
-	    mpz_fdiv_q_2exp (result, result, - XFIXNUM (count));
-	  else
-	    mpz_fdiv_q_2exp (result, result, - XFIXNUM (count));
-	}
-      else /* ash */
+      else
 	mpz_fdiv_q_2exp (result, result, - XFIXNUM (count));
 
       val = make_number (result);
@@ -3417,24 +3424,6 @@ ash_lsh_impl (Lisp_Object value, Lisp_Object count, bool lsh)
   return val;
 }
 
-DEFUN ("ash", Fash, Sash, 2, 2, 0,
-       doc: /* Return VALUE with its bits shifted left by COUNT.
-If COUNT is negative, shifting is actually to the right.
-In this case, the sign bit is duplicated.  */)
-  (register Lisp_Object value, Lisp_Object count)
-{
-  return ash_lsh_impl (value, count, false);
-}
-
-DEFUN ("lsh", Flsh, Slsh, 2, 2, 0,
-       doc: /* Return VALUE with its bits shifted left by COUNT.
-If COUNT is negative, shifting is actually to the right.
-In this case, zeros are shifted in on the left.  */)
-  (register Lisp_Object value, Lisp_Object count)
-{
-  return ash_lsh_impl (value, count, true);
-}
-
 DEFUN ("1+", Fadd1, Sadd1, 1, 1, 0,
        doc: /* Return NUMBER plus one.  NUMBER may be a number or a marker.
 Markers are converted to integers.  */)
@@ -4235,7 +4224,6 @@ syms_of_data (void)
   defsubr (&Slogior);
   defsubr (&Slogxor);
   defsubr (&Slogcount);
-  defsubr (&Slsh);
   defsubr (&Sash);
   defsubr (&Sadd1);
   defsubr (&Ssub1);
diff --git a/test/lisp/international/ccl-tests.el b/test/lisp/international/ccl-tests.el
index b41b8c1ff6..7dd7224726 100644
--- a/test/lisp/international/ccl-tests.el
+++ b/test/lisp/international/ccl-tests.el
@@ -37,18 +37,9 @@
 
   ;; shift right -ve                    -5628     #x3fffffffffffea04
   (should (= (ash -5628 -8)               -22)) ; #x3fffffffffffffea
-
-  ;; shift right                       -5628      #x3fffffffffffea04
-  (cond
-   ((fboundp 'bignump)
-    (should (= (lsh -5628 -8)            -22))) ; #x3fffffffffffffea  bignum
-   ((= (logb most-negative-fixnum) 61)
-    (should (= (lsh -5628 -8)
-               (string-to-number
-                "18014398509481962"))))         ; #x003fffffffffffea  master (64bit)
-   ((= (logb most-negative-fixnum) 29)
-    (should (= (lsh -5628 -8)        4194282))) ; #x003fffea          master (32bit)
-   ))
+  (should (= (lsh -5628 -8)
+             (ash (- -5628 (ash most-negative-fixnum 1)) -8)
+             (ash (logand (ash -5628 -1) most-positive-fixnum) -7))))
 
 ;; CCl program from `pgg-parse-crc24' in lisp/obsolete/pgg-parse.el
 (defconst prog-pgg-source
@@ -177,11 +168,11 @@ prog-midi-code
      82169 240 2555 18 128 81943 15 276 529 305 81 -17660 -17916 22])
 
 (defconst prog-midi-dump
-"Out-buffer must be 2 times bigger than in-buffer.
+(concat "Out-buffer must be 2 times bigger than in-buffer.
 Main-body:
     2:[read-jump-cond-expr-const] read r0, if !(r0 < 128), jump to 22(+20)
     5:[branch] jump to array[r3] of length 4
-	11 12 15 18 22 
+	11 12 15 18 22 ""
    11:[jump] jump to 2(-9)
    12:[set-register] r1 = r0
    13:[set-register] r0 = r4
@@ -227,7 +218,7 @@ prog-midi-dump
    71:[jump] jump to 2(-69)
 At EOF:
    72:[end] end
-")
+"))
 
 (ert-deftest ccl-compile-midi ()
   (should (equal (ccl-compile prog-midi-source) prog-midi-code)))
diff --git a/test/src/data-tests.el b/test/src/data-tests.el
index a4c6b0e491..85cbab2610 100644
--- a/test/src/data-tests.el
+++ b/test/src/data-tests.el
@@ -598,7 +598,9 @@ binding-test-some-local
   (should (fixnump (1- (1+ most-positive-fixnum)))))
 
 (ert-deftest data-tests-logand ()
-  (should (= -1 (logand -1)))
+  (should (= -1 (logand) (logand -1) (logand -1 -1)))
+  (let ((n (1+ most-positive-fixnum)))
+    (should (= (logand -1 n) n)))
   (let ((n (* 2 most-negative-fixnum)))
     (should (= (logand -1 n) n))))
 
@@ -606,11 +608,11 @@ binding-test-some-local
   (should (= (logcount (read "#xffffffffffffffffffffffffffffffff")) 128)))
 
 (ert-deftest data-tests-logior ()
-  (should (= -1 (logior -1)))
+  (should (= -1 (logior -1) (logior -1 -1)))
   (should (= -1 (logior most-positive-fixnum most-negative-fixnum))))
 
 (ert-deftest data-tests-logxor ()
-  (should (= -1 (logxor -1)))
+  (should (= -1 (logxor -1) (logxor -1 -1 -1)))
   (let ((n (1+ most-positive-fixnum)))
     (should (= (logxor -1 n) (lognot n)))))
 
@@ -642,6 +644,12 @@ data-tests-check-sign
   (should (= (ash most-negative-fixnum 1)
              (* most-negative-fixnum 2)))
   (should (= (lsh most-negative-fixnum 1)
-             (* most-negative-fixnum 2))))
+             (* most-negative-fixnum 2)))
+  (should (= (ash (* 2 most-negative-fixnum) -1)
+	     most-negative-fixnum))
+  (should (= (lsh most-positive-fixnum -1) (/ most-positive-fixnum 2)))
+  (should (= (lsh most-negative-fixnum -1) (lsh (- most-negative-fixnum) -1)))
+  (should (= (lsh -1 -1) most-positive-fixnum))
+  (should-error (lsh (1- most-negative-fixnum) -1)))
 
 ;;; data-tests.el ends here
-- 
2.17.1

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Eli Zaretskii]

> From: Pip Cet <pipcet@gmail.com>
> Date: Sat, 18 Aug 2018 19:58:40 +0000
> Cc: eggert@cs.ucla.edu, andrewjmoreton@gmail.com, 32463@debbugs.gnu.org
> 
> > It is IMO absurd for us to deprecate a valid and useful operation just
> > because we added bignums.  If we cannot agree on its semantics for
> > bignums (which would surprise me), then it is better to make it not
> > work for bignums at all than deprecate it for fixnums.
> 
> The recent code changes made `lsh' behave the same as `ash' for
> fixnums, if I understand correctly. Are you suggesting we revert to
> the previous behavior, and try to come up with an interpretation for
> bignums that somehow extends the previous behavior?

I indeed missed the change in the behavior of lsh, as it wasn't
accompanied by any documentation changes.  However, today's commits by
Paul already reverted lsh to its previous behavior, I believe.

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Paul Eggert]

Eli Zaretskii wrote:

>> we can make (lsh A B) signal an error if A is a
>> bignum and B is negative, since there's nothing we can do there that is
>> reasonable and is compatible with the fixnum behavior.

> If that's the best we can do, fine.
OK, let's go that route.

 > It is IMO absurd for us to deprecate a valid and useful operation just
 > because we added bignums.

It would indeed be absurd if lsh were still valid and useful. However, because 
lsh assumes fixed-width integers its overall utility is negative for new Elisp 
code because it mostly just introduces opportunities for confusion. This is why 
Common Lisp and Scheme don't have lsh. Backward compatibility is the only reason 
Emacs Lisp should have lsh. (Obviously we can't simply remove lsh.)

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Andy Moreton]

On Sat 18 Aug 2018, Paul Eggert wrote:

> Pip Cet wrote:
>
>> Paul committed a patch in the meantime (independently, I think?) which
>> does add tests. I'll try to write some more.
>
> Yes, I noticed the logior etc. problem separately and fixed it in master
> without knowing about this bug report. There are some other bignum problems
> too that need fixing and are in my pipeline.

I'm not sure what is on your list of remaining issues, but here is mine:

a) A bug in bignumcompare for 64bit Windows. Patch is here:
   http://lists.gnu.org/archive/html/emacs-devel/2018-08/msg00487.html

b) fmod_float has a bug:
   http://lists.gnu.org/archive/html/emacs-devel/2018-08/msg00442.html

c) Extend Fexpt to support bignums. Patch is here:
   http://lists.gnu.org/archive/html/emacs-devel/2018-08/msg00503.html

d) Extend Fceiling, Ffloor, Fround and Ftruncate to support bignums by
   updating rounding_driver.

Please describe any additional issues you have discovered.

    AndyM

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Live System User]

Andy Moreton <andrewjmoreton@gmail.com> writes:

> On Sat 18 Aug 2018, Paul Eggert wrote:
>
>> Pip Cet wrote:
>>
>>> Paul committed a patch in the meantime (independently, I think?) which
>>> does add tests. I'll try to write some more.
>>
>> Yes, I noticed the logior etc. problem separately and fixed it in master
>> without knowing about this bug report. There are some other bignum problems
>> too that need fixing and are in my pipeline.
>
> I'm not sure what is on your list of remaining issues, but here is mine:
>
> a) A bug in bignumcompare for 64bit Windows. Patch is here:
>    http://lists.gnu.org/archive/html/emacs-devel/2018-08/msg00487.html
>
> b) fmod_float has a bug:
>    http://lists.gnu.org/archive/html/emacs-devel/2018-08/msg00442.html
>
> c) Extend Fexpt to support bignums. Patch is here:
>    http://lists.gnu.org/archive/html/emacs-devel/2018-08/msg00503.html
>
> d) Extend Fceiling, Ffloor, Fround and Ftruncate to support bignums by
>    updating rounding_driver.
>
> Please describe any additional issues you have discovered.

  There also appears to be a bug dealing with date/time
  convesion (maybe a float issue?):

         M-: (date-to-time "Tue, 06 Mar 2018 11:17:02 -0500")
         Invalid date: Tue, 06 Mar 2018 11:17:02 -0500


  When the date/time is being parsed you eroneouse get:

        M-: (parse-time-string "Tue, 06 Mar 2018 11:17:02 -0500")
        (nil nil nil 6 3 2018 2 nil nil)


  With Emacs 26.1, you get:

         (2 17 11 6 3 2018 2 nil -18000)

  See bug#32443

  Thanks.


>
>     AndyM

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

What exactly is the problem with lsh and bignums?  Is it for negative
numbers because there is no specific width?

I think that limiting lsh to fixnums is better than altering its behavior
for fixnums.  But there are other solutions.

One possible solution is to give lsh an optional third argument to
specify the nominal width of the first argument.  The default could be
the width of a fixnum on your platform.

How does Scheme handle the issue?


-- 
Dr Richard Stallman
President, Free Software Foundation (https://gnu.org, https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Paul Eggert]

Richard Stallman wrote:
> What exactly is the problem with lsh and bignums?  Is it for negative
> numbers because there is no specific width?

Yes, that's it.

> One possible solution is to give lsh an optional third argument to
> specify the nominal width of the first argument.  The default could be
> the width of a fixnum on your platform.

Although we discussed something along those lines and could easily implement 
something, it's a bit trickier than it might sound at first, because of corner 
cases where the semantics are unclear. Here's one possible implementation (there 
are other approaches of course):

    (defun lsh (value count &optional width)
      (when (and (< value 0) (< count 0))
        (let ((lo (if width (ash 1 (1- width)) most-negative-fixnum)))
	 (when (< value lo)
	   (signal 'args-out-of-range (list value count width)))
	 (setq value (logand (ash value -1) (- -1 lo)))
	 (setq count (1+ count))))
      (ash value count))

I am skeptical whether the complexity of this extension is worth the effort to 
maintain and document. In a language with bignums, if you need a mask of bits 
you simply use a nonnegative integer, which means you can use ash without 
worrying about the corner cases that invariably afflict lsh.

> How does Scheme handle the issue?

Scheme does not have logical shifts, only arithmetic shifts. Logical shifts 
don't make that much sense once you have bignums.

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Richard Stallman]

[[[ To any NSA and FBI agents reading my email: please consider    ]]]
[[[ whether defending the US Constitution against all enemies,     ]]]
[[[ foreign or domestic, requires you to follow Snowden's example. ]]]

Maybe you are right about lsh and bignums, but we must keep lsh for
fixnums compatibility.  It could give an error if the first argument
is a negative bignum.  Or it could give an error for any bignum.

-- 
Dr Richard Stallman
President, Free Software Foundation (https://gnu.org, https://fsf.org)
Internet Hall-of-Famer (https://internethalloffame.org)

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Paul Eggert]

> I'm not sure what is on your list of remaining issues, but here is mine:
> 
> a) A bug in bignumcompare for 64bit Windows. Patch is here:
>    http://lists.gnu.org/archive/html/emacs-devel/2018-08/msg00487.html

That patch doesn't go far enough, I'm afraid, as there are other bugs in bignum 
comparison. For example, NaNs vs bignums don't always work. And while we're in 
the neighborhood one can more cheaply compare a fixnum to a bignum by simply 
looking at the bignum's sign, as the numeric values don't matter in that case. 
This item is first on my list of things to fix partly because it's relatively easy.

> b) fmod_float has a bug:
>    http://lists.gnu.org/archive/html/emacs-devel/2018-08/msg00442.html
> 
> c) Extend Fexpt to support bignums. Patch is here:
>    http://lists.gnu.org/archive/html/emacs-devel/2018-08/msg00503.html
> 
> d) Extend Fceiling, Ffloor, Fround and Ftruncate to support bignums by
>    updating rounding_driver.

These are all news to me; thanks for the list.

There are some relatively minor things involving removal of assumption that 
there are no padding bits (OK, so Emacs is not likely to run on Crays any time 
soon, but it's easy to port).

My bigger concern is memory management, along with integer overflow in size or 
bitcount calculation. Copies are made of bignums when not needed, behavior is 
dicey if memory is exhausted during bignum computation, and I'm afraid C-g will 
have problems when bignums get large. I don't have a good handle on this stuff 
yet. I have put in some sanity checks (e.g., see check_bignum_size in emacs.c) 
but I suspect more are needed. In particular, Fexpt will need to be careful as 
it is a good way to explode a bignum's size.

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 161 bytes --]

Paul Eggert wrote:
> This item is first on my list of things to fix partly because it's relatively easy.

No time like the present, so I installed the attached.

[-- Attachment #2: 0001-Improve-bignum-comparison-Bug-32463-50.fix --]
[-- Type: text/plain, Size: 7356 bytes --]

From 1d2df2fd03f35ca8d8dfc8b999d8bba3c7c13157 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Sat, 18 Aug 2018 16:13:04 -0700
Subject: [PATCH] Improve bignum comparison (Bug#32463#50)
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

* src/data.c (isnan): Remove, as we can assume C99.
(bignumcompare): Remove, folding its functionality
into arithcompare.
(arithcompare): Compare bignums directly here.
Fix bugs when comparing NaNs to bignums.
When comparing a bignum to a fixnum, just look at the
bignum’s sign, as that’s all that is needed.
Decrease scope of locals when this is easy.
* test/src/data-tests.el (data-tests-bignum): Test bignum vs NaN.
---
 src/data.c             | 168 +++++++++++------------------------------
 test/src/data-tests.el |   5 +-
 2 files changed, 47 insertions(+), 126 deletions(-)

diff --git a/src/data.c b/src/data.c
index a39978ab1d..0754d4c176 100644
--- a/src/data.c
+++ b/src/data.c
@@ -2386,140 +2386,37 @@ bool-vector.  IDX starts at 0.  */)
 \f
 /* Arithmetic functions */
 
-#ifndef isnan
-# define isnan(x) ((x) != (x))
-#endif
-
-static Lisp_Object
-bignumcompare (Lisp_Object num1, Lisp_Object num2,
-	       enum Arith_Comparison comparison)
-{
-  int cmp;
-  bool test;
-
-  if (BIGNUMP (num1))
-    {
-      if (FLOATP (num2))
-	{
-	  /* Note that GMP doesn't define comparisons against NaN, so
-	     we need to handle them specially.  */
-	  if (isnan (XFLOAT_DATA (num2)))
-	    return Qnil;
-	  cmp = mpz_cmp_d (XBIGNUM (num1)->value, XFLOAT_DATA (num2));
-	}
-      else if (FIXNUMP (num2))
-        {
-          if (sizeof (EMACS_INT) > sizeof (long) && XFIXNUM (num2) > LONG_MAX)
-            {
-              mpz_t tem;
-              mpz_init (tem);
-              mpz_set_intmax (tem, XFIXNUM (num2));
-              cmp = mpz_cmp (XBIGNUM (num1)->value, tem);
-              mpz_clear (tem);
-            }
-          else
-            cmp = mpz_cmp_si (XBIGNUM (num1)->value, XFIXNUM (num2));
-        }
-      else
-	{
-	  eassume (BIGNUMP (num2));
-	  cmp = mpz_cmp (XBIGNUM (num1)->value, XBIGNUM (num2)->value);
-	}
-    }
-  else
-    {
-      eassume (BIGNUMP (num2));
-      if (FLOATP (num1))
-	{
-	  /* Note that GMP doesn't define comparisons against NaN, so
-	     we need to handle them specially.  */
-	  if (isnan (XFLOAT_DATA (num1)))
-	    return Qnil;
-	  cmp = - mpz_cmp_d (XBIGNUM (num2)->value, XFLOAT_DATA (num1));
-	}
-      else
-        {
-	  eassume (FIXNUMP (num1));
-          if (sizeof (EMACS_INT) > sizeof (long) && XFIXNUM (num1) > LONG_MAX)
-            {
-              mpz_t tem;
-              mpz_init (tem);
-              mpz_set_intmax (tem, XFIXNUM (num1));
-              cmp = - mpz_cmp (XBIGNUM (num2)->value, tem);
-              mpz_clear (tem);
-            }
-          else
-            cmp = - mpz_cmp_si (XBIGNUM (num2)->value, XFIXNUM (num1));
-        }
-    }
-
-  switch (comparison)
-    {
-    case ARITH_EQUAL:
-      test = cmp == 0;
-      break;
-
-    case ARITH_NOTEQUAL:
-      test = cmp != 0;
-      break;
-
-    case ARITH_LESS:
-      test = cmp < 0;
-      break;
-
-    case ARITH_LESS_OR_EQUAL:
-      test = cmp <= 0;
-      break;
-
-    case ARITH_GRTR:
-      test = cmp > 0;
-      break;
-
-    case ARITH_GRTR_OR_EQUAL:
-      test = cmp >= 0;
-      break;
-
-    default:
-      eassume (false);
-    }
-
-  return test ? Qt : Qnil;
-}
-
 Lisp_Object
 arithcompare (Lisp_Object num1, Lisp_Object num2,
 	      enum Arith_Comparison comparison)
 {
-  double f1, f2;
-  EMACS_INT i1, i2;
-  bool lt, eq, gt;
+  EMACS_INT i1 = 0, i2 = 0;
+  bool lt, eq = true, gt;
   bool test;
 
   CHECK_NUMBER_COERCE_MARKER (num1);
   CHECK_NUMBER_COERCE_MARKER (num2);
 
-  if (BIGNUMP (num1) || BIGNUMP (num2))
-    return bignumcompare (num1, num2, comparison);
-
-  /* If either arg is floating point, set F1 and F2 to the 'double'
-     approximations of the two arguments, and set LT, EQ, and GT to
-     the <, ==, > floating-point comparisons of F1 and F2
+  /* If the comparison is mostly done by comparing two doubles,
+     set LT, EQ, and GT to the <, ==, > results of that comparison,
      respectively, taking care to avoid problems if either is a NaN,
      and trying to avoid problems on platforms where variables (in
      violation of the C standard) can contain excess precision.
      Regardless, set I1 and I2 to integers that break ties if the
-     floating-point comparison is either not done or reports
+     two-double comparison is either not done or reports
      equality.  */
 
   if (FLOATP (num1))
     {
-      f1 = XFLOAT_DATA (num1);
+      double f1 = XFLOAT_DATA (num1);
       if (FLOATP (num2))
 	{
-	  i1 = i2 = 0;
-	  f2 = XFLOAT_DATA (num2);
+	  double f2 = XFLOAT_DATA (num2);
+	  lt = f1 < f2;
+	  eq = f1 == f2;
+	  gt = f1 > f2;
 	}
-      else
+      else if (FIXNUMP (num2))
 	{
 	  /* Compare a float NUM1 to an integer NUM2 by converting the
 	     integer I2 (i.e., NUM2) to the double F2 (a conversion that
@@ -2529,35 +2426,56 @@ arithcompare (Lisp_Object num1, Lisp_Object num2,
 	     floating-point comparison reports a tie, NUM1 = F1 = F2 = I1
 	     (exactly) so I1 - I2 = NUM1 - NUM2 (exactly), so comparing I1
 	     to I2 will break the tie correctly.  */
-	  i1 = f2 = i2 = XFIXNUM (num2);
+	  double f2 = XFIXNUM (num2);
+	  lt = f1 < f2;
+	  eq = f1 == f2;
+	  gt = f1 > f2;
+	  i1 = f2;
+	  i2 = XFIXNUM (num2);
 	}
-      lt = f1 < f2;
-      eq = f1 == f2;
-      gt = f1 > f2;
+      else if (isnan (f1))
+	lt = eq = gt = false;
+      else
+	i2 = mpz_cmp_d (XBIGNUM (num2)->value, f1);
     }
-  else
+  else if (FIXNUMP (num1))
     {
-      i1 = XFIXNUM (num1);
       if (FLOATP (num2))
 	{
 	  /* Compare an integer NUM1 to a float NUM2.  This is the
 	     converse of comparing float to integer (see above).  */
-	  i2 = f1 = i1;
-	  f2 = XFLOAT_DATA (num2);
+	  double f1 = XFIXNUM (num1), f2 = XFLOAT_DATA (num2);
 	  lt = f1 < f2;
 	  eq = f1 == f2;
 	  gt = f1 > f2;
+	  i1 = XFIXNUM (num1);
+	  i2 = f1;
 	}
-      else
+      else if (FIXNUMP (num2))
 	{
+	  i1 = XFIXNUM (num1);
 	  i2 = XFIXNUM (num2);
-	  eq = true;
 	}
+      else
+	i2 = mpz_sgn (XBIGNUM (num2)->value);
     }
+  else if (FLOATP (num2))
+    {
+      double f2 = XFLOAT_DATA (num2);
+      if (isnan (f2))
+	lt = eq = gt = false;
+      else
+	i1 = mpz_cmp_d (XBIGNUM (num1)->value, f2);
+    }
+  else if (FIXNUMP (num2))
+    i1 = mpz_sgn (XBIGNUM (num1)->value);
+  else
+    i1 = mpz_cmp (XBIGNUM (num1)->value, XBIGNUM (num2)->value);
 
   if (eq)
     {
-      /* Break a floating-point tie by comparing the integers.  */
+      /* The two-double comparison either reported equality, or was not done.
+	 Break the tie by comparing the integers.  */
       lt = i1 < i2;
       eq = i1 == i2;
       gt = i1 > i2;
diff --git a/test/src/data-tests.el b/test/src/data-tests.el
index 85cbab2610..688c32d6ee 100644
--- a/test/src/data-tests.el
+++ b/test/src/data-tests.el
@@ -551,7 +551,10 @@ binding-test-some-local
     (should (= b0 b0))
 
     (should (/= b0 f-1))
-    (should (/= b0 b-1))))
+    (should (/= b0 b-1))
+
+    (should (/= b0 0.0e+NaN))
+    (should (/= b-1 0.0e+NaN))))
 
 (ert-deftest data-tests-+ ()
   (should-not (fixnump (+ most-positive-fixnum most-positive-fixnum)))
-- 
2.17.1

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Andy Moreton]

On Sat 18 Aug 2018, Paul Eggert wrote:

> My bigger concern is memory management, along with integer overflow in size or
> bitcount calculation. Copies are made of bignums when not needed, behavior is
> dicey if memory is exhausted during bignum computation, and I'm afraid C-g
> will have problems when bignums get large. I don't have a good handle on this
> stuff yet. I have put in some sanity checks (e.g., see check_bignum_size in
> emacs.c) but I suspect more are needed. In particular, Fexpt will need to be
> careful as it is a good way to explode a bignum's size.

Indeed. There are many places that create a temporary bignum, and thus
call mpz_init/mpz_clear frequently. I haven't profiled this, but it may
be an opportunuty for some optimization.

Fixing C-g will require awkward changes to either GMP and/or emacs.

    AndyM

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Pip Cet]

On Sat, Aug 18, 2018 at 10:58 PM Paul Eggert <eggert@cs.ucla.edu> wrote:
 My bigger concern is memory management, along with integer overflow in size or
> bitcount calculation. Copies are made of bignums when not needed, behavior is
> dicey if memory is exhausted during bignum computation, and I'm afraid C-g will
> have problems when bignums get large.

Even if memory isn't exhausted, creating a bignum larger than 16 GB
(our most-positive-bignum) results in an immediate crash with external
libgmp (Linux, x86_64), and that appears not to be easy to fix without
modifying gmp.

> I don't have a good handle on this stuff
> yet. I have put in some sanity checks (e.g., see check_bignum_size in emacs.c)
> but I suspect more are needed. In particular, Fexpt will need to be careful as
> it is a good way to explode a bignum's size.

That and left shifts are probably the ones to worry about for now.
Creating a large bignum by repeated multiplication will require at
least some intermediate bignums, which need to be allocated and copied
and thus probably alert the user to something going on.

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Paul Eggert]

Pip Cet wrote:

> Even if memory isn't exhausted, creating a bignum larger than 16 GB
> (our most-positive-bignum) results in an immediate crash with external
> libgmp (Linux, x86_64), and that appears not to be easy to fix without
> modifying gmp.

Is there a libgmp bug report for this? or is there a reasonable way to 
characterize this arbitrary limitation in libgmp, so that Emacs does not go over 
the limit and crash? I've already put in one limit, and we can tighten that 
limit (or add more checks) if we know what libgmp's limits are.

> That and left shifts are probably the ones to worry about for now.
> Creating a large bignum by repeated multiplication will require at
> least some intermediate bignums, which need to be allocated and copied
> and thus probably alert the user to something going on.

expt does bignums now too, so that's one more point of failure in this area.

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Pip Cet]

On Sun, Aug 19, 2018 at 10:59 AM Paul Eggert <eggert@cs.ucla.edu> wrote:
> Pip Cet wrote:
> > Even if memory isn't exhausted, creating a bignum larger than 16 GB
> > (our most-positive-bignum) results in an immediate crash with external
> > libgmp (Linux, x86_64), and that appears not to be easy to fix without
> > modifying gmp.
>
> Is there a libgmp bug report for this? or is there a reasonable way to
> characterize this arbitrary limitation in libgmp, so that Emacs does not go over
> the limit and crash? I've already put in one limit, and we can tighten that
> limit (or add more checks) if we know what libgmp's limits are.

libgmp stores mpzs as an int (this is a known bug, and plans to work
around it are on the GMP site) giving their current size in words (8
bytes each on x86_64). So the maximum bignum is 0x7fffffff * 64 one
bits. When that limit is reached, _mpz_realloc calls abort rather than
the user-provided reallocation function.

Of course, on POSIX systems, we can catch SIGABRT, but then we'd need
a flag to mark whether we're in a GMP function and another flag to
mark that we're calling abort from a signal handler which might have
interrupted the GMP function, and a third flag to mark that stack
overflow occurred in a signal handler which interrupted a GMP function
so we longjmp()ed out of GMP. On most ELF systems, we can probably
preload a library redirecting abort() for GMP. These are all ugly
solutions to what is ultimately a GMP limitation that should probably
be fixed, making GMP interruptible and abort-safe, which essentially
all interactive applications of it require.

I think we can be clever and wrap calls to mpz_mul_2exp (which can
create arbitrary bignums) and whatever Fexpt uses and make our
allocation function signal for bignums >= sqrt(most-positive-bignum)
(such numbers cannot produce the overflow condition if combined with
multiplication, addition, or subtraction). In fact, I'd suggest a much
lower limit until/unless the C-g issue is fixed, perhaps overridable
by a user preference if people really want to use big bignums.

(I've looked at implementing big rational numbers as an Emacs type
using GMP, too, and I think performance issues are more pronounced for
those, since even (absolutely) small numbers can have a huge
representation.)

> > That and left shifts are probably the ones to worry about for now.
> > Creating a large bignum by repeated multiplication will require at
> > least some intermediate bignums, which need to be allocated and copied
> > and thus probably alert the user to something going on.
>
> expt does bignums now too, so that's one more point of failure in this area.

Yes, that's what "that" referred to. Are there other operations that
create large bignums that I've missed?

I'm not sure what a reasonable limit would be, but I think a global
limit of bignum size to something that allows for "immediate"
computations would be best.

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 953 bytes --]

Pip Cet wrote:

> I think we can be clever and wrap calls to mpz_mul_2exp (which can
> create arbitrary bignums) and whatever Fexpt uses....  I'd suggest a much
> lower limit until/unless the C-g issue is fixed, perhaps overridable
> by a user preference if people really want to use big bignums.

Yes, this sounds good. After stressing Emacs with bignums for a bit, I found 
that it was too easy to get Emacs to abort or hang by creating large bignums.

> I'm not sure what a reasonable limit would be, but I think a global
> limit of bignum size to something that allows for "immediate"
> computations would be best.

I installed the attached patch to do that. It tentatively defaults to a limit of 
2↑↑5 (i.e., 2**65536) for bignums, overrideable by setting a new variable 
'integer-width' that defaults to 65536. This default should be big enough for 
almost all Emacs applications and should avoid issues of aborts and hangs.

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-Avoid-libgmp-aborts-by-imposing-limits.patch --]
[-- Type: text/x-patch; name="0001-Avoid-libgmp-aborts-by-imposing-limits.patch", Size: 32306 bytes --]

From d6a497dd887cdbb35c5b4e2929e83962ba708159 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Tue, 21 Aug 2018 02:16:50 -0700
Subject: [PATCH] Avoid libgmp aborts by imposing limits
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

libgmp calls ‘abort’ when given numbers too big for its
internal data structures.  The numeric limit is large and
platform-dependent; with 64-bit GMP 6.1.2 it is around
2**2**37.  Work around the problem by refusing to call libgmp
functions with arguments that would cause an abort.  With luck
libgmp will have a better way to do this in the future.
Also, introduce a variable integer-width that lets the user
control how large bignums can be.  This currently defaults
to 2**16, i.e., it allows bignums up to 2**2**16.  This
should be enough for ordinary computation, and should
help Emacs to avoid thrashing or hanging.
Problem noted by Pip Cet (Bug#32463#71).
* doc/lispref/numbers.texi, etc/NEWS:
Document recent bignum changes, including this one.
Improve documentation for bitwise operations, in the light
of bignums.
* src/alloc.c (make_number): Enforce integer-width.
(integer_overflow): New function.
(xrealloc_for_gmp, xfree_for_gmp):
Move here from emacs.c, as it's memory allocation.
(init_alloc): Initialize GMP here, rather than in emacs.c.
(integer_width): New var.
* src/data.c (GMP_NLIMBS_MAX, NLIMBS_LIMIT): New constants.
(emacs_mpz_size, emacs_mpz_mul)
(emacs_mpz_mul_2exp, emacs_mpz_pow_ui): New functions.
(arith_driver, Fash, expt_integer): Use them.
(expt_integer): New function, containing integer code
that was out of place in floatfns.c.
(check_bignum_size, xmalloc_for_gmp): Remove.
* src/emacs.c (main): Do not initialize GMP here.
* src/floatfns.c (Fexpt): Use expt_integer, which
now contains integer code moved from here.
* src/lisp.h (GMP_NUMB_BITS): Define if gmp.h doesn’t.
---
 doc/lispref/numbers.texi | 314 ++++++++++++++++++---------------------
 etc/NEWS                 |   6 +
 src/alloc.c              |  73 ++++++---
 src/data.c               | 109 +++++++++++++-
 src/emacs.c              |  34 -----
 src/floatfns.c           |  24 +--
 src/lisp.h               |  11 +-
 7 files changed, 321 insertions(+), 250 deletions(-)

diff --git a/doc/lispref/numbers.texi b/doc/lispref/numbers.texi
index 209e9f139a..9c16b1a64c 100644
--- a/doc/lispref/numbers.texi
+++ b/doc/lispref/numbers.texi
@@ -34,13 +34,21 @@ Numbers
 @node Integer Basics
 @section Integer Basics
 
-  Integers in Emacs Lisp can have arbitrary precision.
+  Integers in Emacs Lisp are not limited to the machine word size.
 
   Under the hood, though, there are two kinds of integers: smaller
 ones, called @dfn{fixnums}, and larger ones, called @dfn{bignums}.
-Some functions in Emacs only accept fixnums.  Also, while fixnums can
-always be compared for equality with @code{eq}, bignums require the
-use of @code{eql}.
+Some functions in Emacs accept only fixnums.  Also, while fixnums can
+always be compared for numeric equality with @code{eq}, bignums
+require more-heavyweight equality predicates like @code{eql}.
+
+  The range of values for bignums is limited by the amount of main
+memory, by machine characteristics such as the size of the word used
+to represent a bignum's exponent, and by the @code{integer-width}
+variable.  These limits are typically much more generous than the
+limits for fixnums.  A bignum is never numerically equal to a fixnum;
+if Emacs computes an integer in fixnum range, it represents the
+integer as a fixnum, not a bignum.
 
   The range of values for a fixnum depends on the machine.  The
 minimum range is @minus{}536,870,912 to 536,870,911 (30 bits; i.e.,
@@ -97,33 +105,30 @@ Integer Basics
 #24r1k @result{} 44
 @end example
 
-  An integer is read as a fixnum if it is in the correct range.
-Otherwise, it will be read as a bignum.
-
   To understand how various functions work on integers, especially the
 bitwise operators (@pxref{Bitwise Operations}), it is often helpful to
 view the numbers in their binary form.
 
-  In 30-bit binary, the decimal integer 5 looks like this:
+  In binary, the decimal integer 5 looks like this:
 
 @example
-0000...000101 (30 bits total)
+...000101
 @end example
 
 @noindent
-(The @samp{...} stands for enough bits to fill out a 30-bit word; in
-this case, @samp{...} stands for twenty 0 bits.  Later examples also
-use the @samp{...} notation to make binary integers easier to read.)
+(The @samp{...} stands for a conceptually infinite number of bits that
+match the leading bit; here, an infinite number of 0 bits.  Later
+examples also use this @samp{...} notation.)
 
   The integer @minus{}1 looks like this:
 
 @example
-1111...111111 (30 bits total)
+...111111
 @end example
 
 @noindent
 @cindex two's complement
-@minus{}1 is represented as 30 ones.  (This is called @dfn{two's
+@minus{}1 is represented as all ones.  (This is called @dfn{two's
 complement} notation.)
 
   Subtracting 4 from @minus{}1 returns the negative integer @minus{}5.
@@ -131,14 +136,7 @@ Integer Basics
 @minus{}5 looks like this:
 
 @example
-1111...111011 (30 bits total)
-@end example
-
-  In this implementation, the largest 30-bit binary integer is
-536,870,911 in decimal.  In binary, it looks like this:
-
-@example
-0111...111111 (30 bits total)
+...111011
 @end example
 
   Many of the functions described in this chapter accept markers for
@@ -147,10 +145,10 @@ Integer Basics
 give these arguments the name @var{number-or-marker}.  When the argument
 value is a marker, its position value is used and its buffer is ignored.
 
-@cindex largest Lisp integer
-@cindex maximum Lisp integer
+@cindex largest fixnum
+@cindex maximum fixnum
 @defvar most-positive-fixnum
-The value of this variable is the largest ``small'' integer that Emacs
+The value of this variable is the greatest ``small'' integer that Emacs
 Lisp can handle.  Typical values are
 @ifnottex
 2**29 @minus{} 1
@@ -168,11 +166,11 @@ Integer Basics
 on 64-bit platforms.
 @end defvar
 
-@cindex smallest Lisp integer
-@cindex minimum Lisp integer
+@cindex smallest fixnum
+@cindex minimum fixnum
 @defvar most-negative-fixnum
-The value of this variable is the smallest small integer that Emacs
-Lisp can handle.  It is negative.  Typical values are
+The value of this variable is the numerically least ``small'' integer
+that Emacs Lisp can handle.  It is negative.  Typical values are
 @ifnottex
 @minus{}2**29
 @end ifnottex
@@ -187,6 +185,19 @@ Integer Basics
 @math{-2^{61}}
 @end tex
 on 64-bit platforms.
+@end defvar
+
+@cindex bignum range
+@cindex integer range
+@defvar integer-width
+The value of this variable is a nonnegative integer that is an upper
+bound on the number of bits in a bignum.  Integers outside the fixnum
+range are limited to absolute values less than 2@sup{@var{n}}, where
+@var{n} is this variable's value.  Attempts to create bignums outside
+this range result in integer overflow.  Setting this variable to zero
+disables creation of bignums; setting it to a large number can cause
+Emacs to consume large quantities of memory if a computation creates
+huge integers.
 @end defvar
 
   In Emacs Lisp, text characters are represented by integers.  Any
@@ -378,17 +389,17 @@ Comparison of Numbers
 comparison would return @code{nil} and vice versa.  @xref{Float
 Basics}.
 
-  In Emacs Lisp, each small integer is a unique Lisp object.
-Therefore, @code{eq} is equivalent to @code{=} where small integers are
-concerned.  It is sometimes convenient to use @code{eq} for comparing
-an unknown value with an integer, because @code{eq} does not report an
+  In Emacs Lisp, if two fixnums are numerically equal, they are the
+same Lisp object.  That is, @code{eq} is equivalent to @code{=} on
+fixnums.  It is sometimes convenient to use @code{eq} for comparing
+an unknown value with a fixnum, because @code{eq} does not report an
 error if the unknown value is not a number---it accepts arguments of
 any type.  By contrast, @code{=} signals an error if the arguments are
 not numbers or markers.  However, it is better programming practice to
 use @code{=} if you can, even for comparing integers.
 
-  Sometimes it is useful to compare numbers with @code{equal}, which
-treats two numbers as equal if they have the same data type (both
+  Sometimes it is useful to compare numbers with @code{eql} or @code{equal},
+which treat two numbers as equal if they have the same data type (both
 integers, or both floating point) and the same value.  By contrast,
 @code{=} can treat an integer and a floating-point number as equal.
 @xref{Equality Predicates}.
@@ -830,142 +841,113 @@ Bitwise Operations
 @cindex logical arithmetic
 
   In a computer, an integer is represented as a binary number, a
-sequence of @dfn{bits} (digits which are either zero or one).  A bitwise
+sequence of @dfn{bits} (digits which are either zero or one).
+Conceptually the bit sequence is infinite on the left, with the
+most-significant bits being all zeros or all ones.  A bitwise
 operation acts on the individual bits of such a sequence.  For example,
 @dfn{shifting} moves the whole sequence left or right one or more places,
 reproducing the same pattern moved over.
 
   The bitwise operations in Emacs Lisp apply only to integers.
 
-@defun lsh integer1 count
-@cindex logical shift
-@code{lsh}, which is an abbreviation for @dfn{logical shift}, shifts the
-bits in @var{integer1} to the left @var{count} places, or to the right
-if @var{count} is negative, bringing zeros into the vacated bits.  If
-@var{count} is negative, @code{lsh} shifts zeros into the leftmost
-(most-significant) bit, producing a nonnegative result even if
-@var{integer1} is negative fixnum.  (If @var{integer1} is a negative
-bignum, @var{count} must be nonnegative.)  Contrast this with
-@code{ash}, below.
-
-Here are two examples of @code{lsh}, shifting a pattern of bits one
-place to the left.  We show only the low-order eight bits of the binary
-pattern; the rest are all zero.
+@defun ash integer1 count
+@cindex arithmetic shift
+@code{ash} (@dfn{arithmetic shift}) shifts the bits in @var{integer1}
+to the left @var{count} places, or to the right if @var{count} is
+negative.  Left shifts introduce zero bits on the right; right shifts
+discard the rightmost bits.  Considered as an integer operation,
+@code{ash} multiplies @var{integer1} by 2@sup{@var{count}} and then
+converts the result to an integer by rounding downward, toward
+minus infinity.
+
+Here are examples of @code{ash}, shifting a pattern of bits one place
+to the left and to the right.  These examples show only the low-order
+bits of the binary pattern; leading bits all agree with the
+highest-order bit shown.  As you can see, shifting left by one is
+equivalent to multiplying by two, whereas shifting right by one is
+equivalent to dividing by two and then rounding toward minus infinity.
 
 @example
 @group
-(lsh 5 1)
-     @result{} 10
-;; @r{Decimal 5 becomes decimal 10.}
-00000101 @result{} 00001010
-
-(lsh 7 1)
-     @result{} 14
+(ash 7 1) @result{} 14
 ;; @r{Decimal 7 becomes decimal 14.}
-00000111 @result{} 00001110
-@end group
-@end example
-
-@noindent
-As the examples illustrate, shifting the pattern of bits one place to
-the left produces a number that is twice the value of the previous
-number.
-
-Shifting a pattern of bits two places to the left produces results
-like this (with 8-bit binary numbers):
-
-@example
-@group
-(lsh 3 2)
-     @result{} 12
-;; @r{Decimal 3 becomes decimal 12.}
-00000011 @result{} 00001100
+...000111
+     @result{}
+...001110
 @end group
-@end example
-
-On the other hand, shifting one place to the right looks like this:
 
-@example
 @group
-(lsh 6 -1)
-     @result{} 3
-;; @r{Decimal 6 becomes decimal 3.}
-00000110 @result{} 00000011
+(ash 7 -1) @result{} 3
+...000111
+     @result{}
+...000011
 @end group
 
 @group
-(lsh 5 -1)
-     @result{} 2
-;; @r{Decimal 5 becomes decimal 2.}
-00000101 @result{} 00000010
+(ash -7 1) @result{} -14
+...111001
+     @result{}
+...110010
 @end group
-@end example
-
-@noindent
-As the example illustrates, shifting one place to the right divides the
-value of a positive integer by two, rounding downward.
-@end defun
-
-@defun ash integer1 count
-@cindex arithmetic shift
-@code{ash} (@dfn{arithmetic shift}) shifts the bits in @var{integer1}
-to the left @var{count} places, or to the right if @var{count}
-is negative.
-
-@code{ash} gives the same results as @code{lsh} except when
-@var{integer1} and @var{count} are both negative.  In that case,
-@code{ash} puts ones in the empty bit positions on the left, while
-@code{lsh} puts zeros in those bit positions and requires
-@var{integer1} to be a fixnum.
 
-Thus, with @code{ash}, shifting the pattern of bits one place to the right
-looks like this:
-
-@example
 @group
-(ash -6 -1) @result{} -3
-;; @r{Decimal @minus{}6 becomes decimal @minus{}3.}
-1111...111010 (30 bits total)
+(ash -7 -1) @result{} -4
+...111001
      @result{}
-1111...111101 (30 bits total)
+...111100
 @end group
 @end example
 
-Here are other examples:
+Here are examples of shifting left or right by two bits:
 
-@c !!! Check if lined up in smallbook format!  XDVI shows problem
-@c     with smallbook but not with regular book! --rjc 16mar92
 @smallexample
 @group
-                   ;  @r{       30-bit binary values}
-
-(lsh 5 2)          ;   5  =  @r{0000...000101}
-     @result{} 20         ;      =  @r{0000...010100}
-@end group
-@group
-(ash 5 2)
-     @result{} 20
-(lsh -5 2)         ;  -5  =  @r{1111...111011}
-     @result{} -20        ;      =  @r{1111...101100}
-(ash -5 2)
-     @result{} -20
+                  ;  @r{       binary values}
+(ash 5 2)         ;   5  =  @r{...000101}
+     @result{} 20         ;      =  @r{...010100}
+(ash -5 2)        ;  -5  =  @r{...111011}
+     @result{} -20        ;      =  @r{...101100}
 @end group
 @group
-(lsh 5 -2)         ;   5  =  @r{0000...000101}
-     @result{} 1          ;      =  @r{0000...000001}
+(ash 5 -2)
+     @result{} 1          ;      =  @r{...000001}
 @end group
 @group
-(ash 5 -2)
-     @result{} 1
+(ash -5 -2)
+     @result{} -2         ;      =  @r{...111110}
 @end group
+@end smallexample
+@end defun
+
+@defun lsh integer1 count
+@cindex logical shift
+@code{lsh}, which is an abbreviation for @dfn{logical shift}, shifts the
+bits in @var{integer1} to the left @var{count} places, or to the right
+if @var{count} is negative, bringing zeros into the vacated bits.  If
+@var{count} is negative, then @var{integer1} must be either a fixnum
+or a positive bignum, and @code{lsh} treats a negative fixnum as if it
+were unsigned by subtracting twice @code{most-negative-fixnum} before
+shifting, producing a nonnegative result.  This quirky behavior dates
+back to when Emacs supported only fixnums; nowadays @code{ash} is a
+better choice.
+
+As @code{lsh} behaves like @code{ash} except when @var{integer1} and
+@var{count1} are both negative, the following examples focus on these
+exceptional cases.  These examples assume 30-bit fixnums.
+
+@smallexample
 @group
-(lsh -5 -2)        ;  -5  =  @r{1111...111011}
-     @result{} 268435454
-                   ;      =  @r{0011...111110}
+                 ; @r{     binary values}
+(ash -7 -1)      ; -7 = @r{...111111111111111111111111111001}
+     @result{} -4        ;    = @r{...111111111111111111111111111100}
+(lsh -7 -1)
+     @result{} 536870908 ;    = @r{...011111111111111111111111111100}
 @end group
 @group
-(ash -5 -2)        ;  -5  =  @r{1111...111011}
-     @result{} -2         ;      =  @r{1111...111110}
+(ash -5 -2)      ; -5 = @r{...111111111111111111111111111011}
+     @result{} -2        ;    = @r{...111111111111111111111111111110}
+(lsh -5 -2)
+     @result{} 268435454 ;    = @r{...001111111111111111111111111110}
 @end group
 @end smallexample
 @end defun
@@ -999,23 +981,23 @@ Bitwise Operations
 
 @smallexample
 @group
-                   ; @r{       30-bit binary values}
+                   ; @r{       binary values}
 
-(logand 14 13)     ; 14  =  @r{0000...001110}
-                   ; 13  =  @r{0000...001101}
-     @result{} 12         ; 12  =  @r{0000...001100}
+(logand 14 13)     ; 14  =  @r{...001110}
+                   ; 13  =  @r{...001101}
+     @result{} 12         ; 12  =  @r{...001100}
 @end group
 
 @group
-(logand 14 13 4)   ; 14  =  @r{0000...001110}
-                   ; 13  =  @r{0000...001101}
-                   ;  4  =  @r{0000...000100}
-     @result{} 4          ;  4  =  @r{0000...000100}
+(logand 14 13 4)   ; 14  =  @r{...001110}
+                   ; 13  =  @r{...001101}
+                   ;  4  =  @r{...000100}
+     @result{} 4          ;  4  =  @r{...000100}
 @end group
 
 @group
 (logand)
-     @result{} -1         ; -1  =  @r{1111...111111}
+     @result{} -1         ; -1  =  @r{...111111}
 @end group
 @end smallexample
 @end defun
@@ -1029,18 +1011,18 @@ Bitwise Operations
 
 @smallexample
 @group
-                   ; @r{       30-bit binary values}
+                   ; @r{       binary values}
 
-(logior 12 5)      ; 12  =  @r{0000...001100}
-                   ;  5  =  @r{0000...000101}
-     @result{} 13         ; 13  =  @r{0000...001101}
+(logior 12 5)      ; 12  =  @r{...001100}
+                   ;  5  =  @r{...000101}
+     @result{} 13         ; 13  =  @r{...001101}
 @end group
 
 @group
-(logior 12 5 7)    ; 12  =  @r{0000...001100}
-                   ;  5  =  @r{0000...000101}
-                   ;  7  =  @r{0000...000111}
-     @result{} 15         ; 15  =  @r{0000...001111}
+(logior 12 5 7)    ; 12  =  @r{...001100}
+                   ;  5  =  @r{...000101}
+                   ;  7  =  @r{...000111}
+     @result{} 15         ; 15  =  @r{...001111}
 @end group
 @end smallexample
 @end defun
@@ -1054,18 +1036,18 @@ Bitwise Operations
 
 @smallexample
 @group
-                   ; @r{       30-bit binary values}
+                   ; @r{       binary values}
 
-(logxor 12 5)      ; 12  =  @r{0000...001100}
-                   ;  5  =  @r{0000...000101}
-     @result{} 9          ;  9  =  @r{0000...001001}
+(logxor 12 5)      ; 12  =  @r{...001100}
+                   ;  5  =  @r{...000101}
+     @result{} 9          ;  9  =  @r{...001001}
 @end group
 
 @group
-(logxor 12 5 7)    ; 12  =  @r{0000...001100}
-                   ;  5  =  @r{0000...000101}
-                   ;  7  =  @r{0000...000111}
-     @result{} 14         ; 14  =  @r{0000...001110}
+(logxor 12 5 7)    ; 12  =  @r{...001100}
+                   ;  5  =  @r{...000101}
+                   ;  7  =  @r{...000111}
+     @result{} 14         ; 14  =  @r{...001110}
 @end group
 @end smallexample
 @end defun
@@ -1078,9 +1060,9 @@ Bitwise Operations
 @example
 (lognot 5)
      @result{} -6
-;;  5  =  @r{0000...000101} (30 bits total)
+;;  5  =  @r{...000101}
 ;; @r{becomes}
-;; -6  =  @r{1111...111010} (30 bits total)
+;; -6  =  @r{...111010}
 @end example
 @end defun
 
@@ -1095,9 +1077,9 @@ Bitwise Operations
 nonnegative.
 
 @example
-(logcount 43)     ; 43 = #b101011
+(logcount 43)     ;  43 = @r{...000101011}
      @result{} 4
-(logcount -43)    ; -43 = #b111...1010101
+(logcount -43)    ; -43 = @r{...111010101}
      @result{} 3
 @end example
 @end defun
diff --git a/etc/NEWS b/etc/NEWS
index a9f8ed2ef8..9a74164421 100644
--- a/etc/NEWS
+++ b/etc/NEWS
@@ -871,6 +871,12 @@ bignums.  However, note that unlike fixnums, bignums will not compare
 equal with 'eq', you must use 'eql' instead.  (Numerical comparison
 with '=' works on both, of course.)
 
++++
+** New variable 'integer-width'.
+It is a nonnegative integer specifying the maximum number of bits
+allowed in a bignum.  Integer overflow occurs if this limit is
+exceeded.
+
 ** define-minor-mode automatically documents the meaning of ARG
 
 +++
diff --git a/src/alloc.c b/src/alloc.c
index ddc0696ba9..24a24aab96 100644
--- a/src/alloc.c
+++ b/src/alloc.c
@@ -3746,33 +3746,33 @@ make_bignum_str (const char *num, int base)
 Lisp_Object
 make_number (mpz_t value)
 {
-  if (mpz_fits_slong_p (value))
-    {
-      long l = mpz_get_si (value);
-      if (!FIXNUM_OVERFLOW_P (l))
-	return make_fixnum (l);
-    }
-  else if (LONG_WIDTH < FIXNUM_BITS)
+  size_t bits = mpz_sizeinbase (value, 2);
+
+  if (bits <= FIXNUM_BITS)
     {
-      size_t bits = mpz_sizeinbase (value, 2);
+      EMACS_INT v = 0;
+      int i = 0, shift = 0;
 
-      if (bits <= FIXNUM_BITS)
-        {
-          EMACS_INT v = 0;
-	  int i = 0;
-	  for (int shift = 0; shift < bits; shift += mp_bits_per_limb)
-            {
-	      EMACS_INT limb = mpz_getlimbn (value, i++);
-	      v += limb << shift;
-            }
-	  if (mpz_sgn (value) < 0)
-            v = -v;
+      do
+	{
+	  EMACS_INT limb = mpz_getlimbn (value, i++);
+	  v += limb << shift;
+	  shift += GMP_NUMB_BITS;
+	}
+      while (shift < bits);
 
-          if (!FIXNUM_OVERFLOW_P (v))
-	    return make_fixnum (v);
-        }
+      if (mpz_sgn (value) < 0)
+	v = -v;
+
+      if (!FIXNUM_OVERFLOW_P (v))
+	return make_fixnum (v);
     }
 
+  /* The documentation says integer-width should be nonnegative, so
+     a single comparison suffices even though 'bits' is unsigned.  */
+  if (integer_width < bits)
+    integer_overflow ();
+
   struct Lisp_Bignum *b = ALLOCATE_PSEUDOVECTOR (struct Lisp_Bignum, value,
 						 PVEC_BIGNUM);
   /* We could mpz_init + mpz_swap here, to avoid a copy, but the
@@ -7200,6 +7200,26 @@ verify_alloca (void)
 
 #endif /* ENABLE_CHECKING && USE_STACK_LISP_OBJECTS */
 
+/* Memory allocation for GMP.  */
+
+void
+integer_overflow (void)
+{
+  error ("Integer too large to be represented");
+}
+
+static void *
+xrealloc_for_gmp (void *ptr, size_t ignore, size_t size)
+{
+  return xrealloc (ptr, size);
+}
+
+static void
+xfree_for_gmp (void *ptr, size_t ignore)
+{
+  xfree (ptr);
+}
+
 /* Initialization.  */
 
 void
@@ -7233,6 +7253,10 @@ init_alloc_once (void)
 void
 init_alloc (void)
 {
+  eassert (mp_bits_per_limb == GMP_NUMB_BITS);
+  integer_width = 1 << 16;
+  mp_set_memory_functions (xmalloc, xrealloc_for_gmp, xfree_for_gmp);
+
   Vgc_elapsed = make_float (0.0);
   gcs_done = 0;
 
@@ -7335,6 +7359,11 @@ The time is in seconds as a floating point value.  */);
   DEFVAR_INT ("gcs-done", gcs_done,
               doc: /* Accumulated number of garbage collections done.  */);
 
+  DEFVAR_INT ("integer-width", integer_width,
+	      doc: /* Maximum number of bits in bignums.
+Integers outside the fixnum range are limited to absolute values less
+than 2**N, where N is this variable's value.  N should be nonnegative.  */);
+
   defsubr (&Scons);
   defsubr (&Slist);
   defsubr (&Svector);
diff --git a/src/data.c b/src/data.c
index 8a6975da3a..4c6d33f294 100644
--- a/src/data.c
+++ b/src/data.c
@@ -2384,6 +2384,80 @@ bool-vector.  IDX starts at 0.  */)
   return newelt;
 }
 \f
+/* GMP tests for this value and aborts (!) if it is exceeded.
+   This is as of GMP 6.1.2 (2016); perhaps future versions will differ.  */
+enum { GMP_NLIMBS_MAX = min (INT_MAX, ULONG_MAX / GMP_NUMB_BITS) };
+
+/* An upper bound on limb counts, needed to prevent libgmp and/or
+   Emacs from aborting or otherwise misbehaving.  This bound applies
+   to estimates of mpz_t sizes before the mpz_t objects are created,
+   as opposed to integer-width which operates on mpz_t values after
+   creation and before conversion to Lisp bignums.  */
+enum
+  {
+   NLIMBS_LIMIT = min (min (/* libgmp needs to store limb counts.  */
+			    GMP_NLIMBS_MAX,
+
+			    /* Size calculations need to work.  */
+			    min (PTRDIFF_MAX, SIZE_MAX) / sizeof (mp_limb_t)),
+
+		       /* Emacs puts bit counts into fixnums.  */
+		       MOST_POSITIVE_FIXNUM / GMP_NUMB_BITS)
+  };
+
+/* Like mpz_size, but tell the compiler the result is a nonnegative int.  */
+
+static int
+emacs_mpz_size (mpz_t const op)
+{
+  mp_size_t size = mpz_size (op);
+  eassume (0 <= size && size <= INT_MAX);
+  return size;
+}
+
+/* Wrappers to work around GMP limitations.  As of GMP 6.1.2 (2016),
+   the library code aborts when a number is too large.  These wrappers
+   avoid the problem for functions that can return numbers much larger
+   than their arguments.  For slowly-growing numbers, the integer
+   width check in make_number should suffice.  */
+
+static void
+emacs_mpz_mul (mpz_t rop, mpz_t const op1, mpz_t const op2)
+{
+  if (NLIMBS_LIMIT - emacs_mpz_size (op1) < emacs_mpz_size (op2))
+    integer_overflow ();
+  mpz_mul (rop, op1, op2);
+}
+
+static void
+emacs_mpz_mul_2exp (mpz_t rop, mpz_t const op1, mp_bitcnt_t op2)
+{
+  /* Fudge factor derived from GMP 6.1.2, to avoid an abort in
+     mpz_mul_2exp (look for the '+ 1' in its source code).  */
+  enum { mul_2exp_extra_limbs = 1 };
+  enum { lim = min (NLIMBS_LIMIT, GMP_NLIMBS_MAX - mul_2exp_extra_limbs) };
+
+  mp_bitcnt_t op2limbs = op2 / GMP_NUMB_BITS;
+  if (lim - emacs_mpz_size (op1) < op2limbs)
+    integer_overflow ();
+  mpz_mul_2exp (rop, op1, op2);
+}
+
+static void
+emacs_mpz_pow_ui (mpz_t rop, mpz_t const base, unsigned long exp)
+{
+  /* This fudge factor is derived from GMP 6.1.2, to avoid an abort in
+     mpz_n_pow_ui (look for the '5' in its source code).  */
+  enum { pow_ui_extra_limbs = 5 };
+  enum { lim = min (NLIMBS_LIMIT, GMP_NLIMBS_MAX - pow_ui_extra_limbs) };
+
+  int nbase = emacs_mpz_size (base), n;
+  if (INT_MULTIPLY_WRAPV (nbase, exp, &n) || lim < n)
+    integer_overflow ();
+  mpz_pow_ui (rop, base, exp);
+}
+
+\f
 /* Arithmetic functions */
 
 Lisp_Object
@@ -2872,13 +2946,13 @@ arith_driver (enum arithop code, ptrdiff_t nargs, Lisp_Object *args)
 	  break;
 	case Amult:
 	  if (BIGNUMP (val))
-	    mpz_mul (accum, accum, XBIGNUM (val)->value);
+	    emacs_mpz_mul (accum, accum, XBIGNUM (val)->value);
 	  else if (! FIXNUMS_FIT_IN_LONG)
             {
 	      mpz_t tem;
 	      mpz_init (tem);
 	      mpz_set_intmax (tem, XFIXNUM (val));
-	      mpz_mul (accum, accum, tem);
+	      emacs_mpz_mul (accum, accum, tem);
 	      mpz_clear (tem);
             }
 	  else
@@ -3293,7 +3367,7 @@ In this case, the sign bit is duplicated.  */)
       mpz_t result;
       mpz_init (result);
       if (XFIXNUM (count) > 0)
-	mpz_mul_2exp (result, XBIGNUM (value)->value, XFIXNUM (count));
+	emacs_mpz_mul_2exp (result, XBIGNUM (value)->value, XFIXNUM (count));
       else
 	mpz_fdiv_q_2exp (result, XBIGNUM (value)->value, - XFIXNUM (count));
       val = make_number (result);
@@ -3319,7 +3393,7 @@ In this case, the sign bit is duplicated.  */)
       mpz_set_intmax (result, XFIXNUM (value));
 
       if (XFIXNUM (count) >= 0)
-	mpz_mul_2exp (result, result, XFIXNUM (count));
+	emacs_mpz_mul_2exp (result, result, XFIXNUM (count));
       else
 	mpz_fdiv_q_2exp (result, result, - XFIXNUM (count));
 
@@ -3330,6 +3404,33 @@ In this case, the sign bit is duplicated.  */)
   return val;
 }
 
+/* Return X ** Y as an integer.  X and Y must be integers, and Y must
+   be nonnegative.  */
+
+Lisp_Object
+expt_integer (Lisp_Object x, Lisp_Object y)
+{
+  unsigned long exp;
+  if (TYPE_RANGED_FIXNUMP (unsigned long, y))
+    exp = XFIXNUM (y);
+  else if (MOST_POSITIVE_FIXNUM < ULONG_MAX && BIGNUMP (y)
+	   && mpz_fits_ulong_p (XBIGNUM (y)->value))
+    exp = mpz_get_ui (XBIGNUM (y)->value);
+  else
+    integer_overflow ();
+
+  mpz_t val;
+  mpz_init (val);
+  emacs_mpz_pow_ui (val,
+		    (FIXNUMP (x)
+		     ? (mpz_set_intmax (val, XFIXNUM (x)), val)
+		     : XBIGNUM (x)->value),
+		    exp);
+  Lisp_Object res = make_number (val);
+  mpz_clear (val);
+  return res;
+}
+
 DEFUN ("1+", Fadd1, Sadd1, 1, 1, 0,
        doc: /* Return NUMBER plus one.  NUMBER may be a number or a marker.
 Markers are converted to integers.  */)
diff --git a/src/emacs.c b/src/emacs.c
index 11ee0b8118..7d07ec8502 100644
--- a/src/emacs.c
+++ b/src/emacs.c
@@ -673,38 +673,6 @@ close_output_streams (void)
     _exit (EXIT_FAILURE);
 }
 
-/* Memory allocation functions for GMP.  */
-
-static void
-check_bignum_size (size_t size)
-{
-  /* Do not create a bignum whose log base 2 could exceed fixnum range.
-     This way, functions like mpz_popcount return values in fixnum range.
-     It may also help to avoid other problems with outlandish bignums.  */
-  if (MOST_POSITIVE_FIXNUM / CHAR_BIT < size)
-    error ("Integer too large to be represented");
-}
-
-static void * ATTRIBUTE_MALLOC
-xmalloc_for_gmp (size_t size)
-{
-  check_bignum_size (size);
-  return xmalloc (size);
-}
-
-static void *
-xrealloc_for_gmp (void *ptr, size_t ignore, size_t size)
-{
-  check_bignum_size (size);
-  return xrealloc (ptr, size);
-}
-
-static void
-xfree_for_gmp (void *ptr, size_t ignore)
-{
-  xfree (ptr);
-}
-
 /* ARGSUSED */
 int
 main (int argc, char **argv)
@@ -803,8 +771,6 @@ main (int argc, char **argv)
   init_standard_fds ();
   atexit (close_output_streams);
 
-  mp_set_memory_functions (xmalloc_for_gmp, xrealloc_for_gmp, xfree_for_gmp);
-
   sort_args (argc, argv);
   argc = 0;
   while (argv[argc]) argc++;
diff --git a/src/floatfns.c b/src/floatfns.c
index 7c52a0a9a2..ea9000b90a 100644
--- a/src/floatfns.c
+++ b/src/floatfns.c
@@ -210,29 +210,7 @@ DEFUN ("expt", Fexpt, Sexpt, 2, 2, 0,
   /* Common Lisp spec: don't promote if both are integers, and if the
      result is not fractional.  */
   if (INTEGERP (arg1) && NATNUMP (arg2))
-    {
-      unsigned long exp;
-      if (TYPE_RANGED_FIXNUMP (unsigned long, arg2))
-	exp = XFIXNUM (arg2);
-      else if (MOST_POSITIVE_FIXNUM < ULONG_MAX && BIGNUMP (arg2)
-	       && mpz_fits_ulong_p (XBIGNUM (arg2)->value))
-	exp = mpz_get_ui (XBIGNUM (arg2)->value);
-      else
-	xsignal3 (Qrange_error, build_string ("expt"), arg1, arg2);
-
-      mpz_t val;
-      mpz_init (val);
-      if (FIXNUMP (arg1))
-	{
-	  mpz_set_intmax (val, XFIXNUM (arg1));
-	  mpz_pow_ui (val, val, exp);
-	}
-      else
-	mpz_pow_ui (val, XBIGNUM (arg1)->value, exp);
-      Lisp_Object res = make_number (val);
-      mpz_clear (val);
-      return res;
-    }
+    return expt_integer (arg1, arg2);
 
   return make_float (pow (XFLOATINT (arg1), XFLOATINT (arg2)));
 }
diff --git a/src/lisp.h b/src/lisp.h
index fe384d1844..8f48a33484 100644
--- a/src/lisp.h
+++ b/src/lisp.h
@@ -996,6 +996,14 @@ enum More_Lisp_Bits
 #define MOST_POSITIVE_FIXNUM (EMACS_INT_MAX >> INTTYPEBITS)
 #define MOST_NEGATIVE_FIXNUM (-1 - MOST_POSITIVE_FIXNUM)
 
+
+/* GMP-related limits.  */
+
+/* Number of data bits in a limb.  */
+#ifndef GMP_NUMB_BITS
+enum { GMP_NUMB_BITS = TYPE_WIDTH (mp_limb_t) };
+#endif
+
 #if USE_LSB_TAG
 
 INLINE Lisp_Object
@@ -3338,7 +3346,7 @@ extern void set_internal (Lisp_Object, Lisp_Object, Lisp_Object,
                           enum Set_Internal_Bind);
 extern void set_default_internal (Lisp_Object, Lisp_Object,
                                   enum Set_Internal_Bind bindflag);
-
+extern Lisp_Object expt_integer (Lisp_Object, Lisp_Object);
 extern void syms_of_data (void);
 extern void swap_in_global_binding (struct Lisp_Symbol *);
 
@@ -3700,6 +3708,7 @@ extern void display_malloc_warning (void);
 extern ptrdiff_t inhibit_garbage_collection (void);
 extern Lisp_Object build_overlay (Lisp_Object, Lisp_Object, Lisp_Object);
 extern void free_cons (struct Lisp_Cons *);
+extern _Noreturn void integer_overflow (void);
 extern void init_alloc_once (void);
 extern void init_alloc (void);
 extern void syms_of_alloc (void);
-- 
2.17.1

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Andy Moreton]

On Tue 21 Aug 2018, Paul Eggert wrote:

> Pip Cet wrote:
>> I'm not sure what a reasonable limit would be, but I think a global
>> limit of bignum size to something that allows for "immediate"
>> computations would be best.
>
> I installed the attached patch to do that. It tentatively defaults to a limit
> of 2↑↑5 (i.e., 2**65536) for bignums, overrideable by setting a new variable
> 'integer-width' that defaults to 65536. This default should be big enough for
> almost all Emacs applications and should avoid issues of aborts and hangs.

Have you checked a mini-gmp build to ensure that this patch works if
the GMP library is not installed ?

It might be slightly faster to use mpz_limbs_read in make_number instead
of mpz_getlimbn.

    AndyM

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Eli Zaretskii]

> From: Paul Eggert <eggert@cs.ucla.edu>
> Date: Tue, 21 Aug 2018 02:40:34 -0700
> Cc: andrewjmoreton@gmail.com, 32463@debbugs.gnu.org
> 
> I installed the attached patch to do that. It tentatively defaults to a limit of 
> 2↑↑5 (i.e., 2**65536) for bignums, overrideable by setting a new variable 
> 'integer-width' that defaults to 65536. This default should be big enough for 
> almost all Emacs applications and should avoid issues of aborts and hangs.

Should the default value be different on 32-bit platforms?

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Andy Moreton]

On Tue 21 Aug 2018, Eli Zaretskii wrote:

>> From: Paul Eggert <eggert@cs.ucla.edu>
>> Date: Tue, 21 Aug 2018 02:40:34 -0700
>> Cc: andrewjmoreton@gmail.com, 32463@debbugs.gnu.org
>> 
>> I installed the attached patch to do that. It tentatively defaults to a limit of 
>> 2↑↑5 (i.e., 2**65536) for bignums, overrideable by setting a new variable 
>> 'integer-width' that defaults to 65536. This default should be big enough for 
>> almost all Emacs applications and should avoid issues of aborts and hangs.
>
> Should the default value be different on 32-bit platforms?

For a 32bit platform using 32bit mp_limb_t, this is only 2048 limbs, so
well within range of mpz_t::_mp_size. Having the same limit on all
platforms should be fine.

Does this limit apply to bignum values in lisp objects, or to
intermediate values inside libgmp, which may require extra space ?
The documentation for `integer-width' should make this clear.

    AndyM

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Paul Eggert]

Eli Zaretskii wrote:
> Should the default value [of integer-width] be different on 32-bit platforms?

My guess is not. The current default of 2**16 means that individual bignums are 
limited to around 8 KiB, and even 32-bit platforms can handle that. Of course as 
we gain experience we may want to change the default.

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 689 bytes --]

>> a) A bug in bignumcompare for 64bit Windows. Patch is here:
>> http://lists.gnu.org/archive/html/emacs-devel/2018-08/msg00487.html
>> ...
>> b) fmod_float has a bug:
>> http://lists.gnu.org/archive/html/emacs-devel/2018-08/msg00442.html
>>
>> c) Extend Fexpt to support bignums. Patch is here:
>> http://lists.gnu.org/archive/html/emacs-devel/2018-08/msg00503.html
>>
>> d) Extend Fceiling, Ffloor, Fround and Ftruncate to support bignums by
>>    updating rounding_driver.

I worked on these and installed patches to master that should do (a), (b), and 
(c). For (d) I wrote the attached patch, and plan to test it a bit more before 
installing, as it's the hairiest.

[-- Attachment #2: rounding.diff --]
[-- Type: text/x-patch, Size: 4936 bytes --]

diff --git a/src/floatfns.c b/src/floatfns.c
index 54d068c29e..e06657219d 100644
--- a/src/floatfns.c
+++ b/src/floatfns.c
@@ -379,10 +379,10 @@ This is the same as the exponent of a float.  */)
 static Lisp_Object
 rounding_driver (Lisp_Object arg, Lisp_Object divisor,
 		 double (*double_round) (double),
-		 EMACS_INT (*int_round2) (EMACS_INT, EMACS_INT),
+		 void (*int_divide) (mpz_t, mpz_t const, mpz_t const),
 		 const char *name)
 {
-  CHECK_FIXNUM_OR_FLOAT (arg);
+  CHECK_NUMBER (arg);
 
   double d;
   if (NILP (divisor))
@@ -393,12 +393,25 @@ rounding_driver (Lisp_Object arg, Lisp_Object divisor,
     }
   else
     {
-      CHECK_FIXNUM_OR_FLOAT (divisor);
+      CHECK_NUMBER (divisor);
       if (!FLOATP (arg) && !FLOATP (divisor))
 	{
-	  if (XFIXNUM (divisor) == 0)
+	  if (EQ (divisor, make_fixnum (0)))
 	    xsignal0 (Qarith_error);
-	  return make_fixnum (int_round2 (XFIXNUM (arg), XFIXNUM (divisor)));
+	  mpz_t d, q;
+	  mpz_init (d);
+	  mpz_init (q);
+	  int_divide (q,
+		      (FIXNUMP (arg)
+		       ? (mpz_set_intmax (q, XFIXNUM (arg)), q)
+		       : XBIGNUM (arg)->value),
+		      (FIXNUMP (divisor)
+		       ? (mpz_set_intmax (d, XFIXNUM (divisor)), d)
+		       : XBIGNUM (arg)->value));
+	  Lisp_Object result = make_number (q);
+	  mpz_clear (d);
+	  mpz_clear (q);
+	  return result;
 	}
 
       double f1 = FLOATP (arg) ? XFLOAT_DATA (arg) : XFIXNUM (arg);
@@ -422,37 +435,39 @@ rounding_driver (Lisp_Object arg, Lisp_Object divisor,
   xsignal2 (Qrange_error, build_string (name), arg);
 }
 
-static EMACS_INT
-ceiling2 (EMACS_INT i1, EMACS_INT i2)
-{
-  return i1 / i2 + ((i1 % i2 != 0) & ((i1 < 0) == (i2 < 0)));
-}
-
-static EMACS_INT
-floor2 (EMACS_INT i1, EMACS_INT i2)
-{
-  return i1 / i2 - ((i1 % i2 != 0) & ((i1 < 0) != (i2 < 0)));
-}
-
-static EMACS_INT
-truncate2 (EMACS_INT i1, EMACS_INT i2)
-{
-  return i1 / i2;
-}
-
-static EMACS_INT
-round2 (EMACS_INT i1, EMACS_INT i2)
-{
-  /* The C language's division operator gives us one remainder R, but
-     we want the remainder R1 on the other side of 0 if R1 is closer
-     to 0 than R is; because we want to round to even, we also want R1
-     if R and R1 are the same distance from 0 and if C's quotient is
-     odd.  */
-  EMACS_INT q = i1 / i2;
-  EMACS_INT r = i1 % i2;
-  EMACS_INT abs_r = eabs (r);
-  EMACS_INT abs_r1 = eabs (i2) - abs_r;
-  return q + (abs_r + (q & 1) <= abs_r1 ? 0 : (i2 ^ r) < 0 ? -1 : 1);
+static void
+rounddiv_q (mpz_t q, mpz_t const n, mpz_t const d)
+{
+  /* mpz_tdiv_qr gives us one remainder R, but we want the remainder
+     R1 on the other side of 0 if R1 is closer to 0 than R is; because
+     we want to round to even, we also want R1 if R and R1 are the
+     same distance from 0 and if the quotient is odd.
+
+     If we were using EMACS_INT arithmetic instead of bignums,
+     the following code could look something like this:
+
+     q = n / d;
+     r = n % d;
+     neg_d = d < 0;
+     neg_r = r < 0;
+     r = eabs (r);
+     abs_r1 = eabs (d) - r;
+     if (abs_r1 < r + (q & 1))
+       q += neg_d == neg_r ? 1 : -1;  */
+
+  mpz_t r, abs_r1;
+  mpz_init (r);
+  mpz_init (abs_r1);
+  mpz_tdiv_qr (q, r, n, d);
+  bool neg_d = mpz_sgn (d) < 0;
+  bool neg_r = mpz_sgn (r) < 0;
+  mpz_abs (r, r);
+  mpz_abs (abs_r1, d);
+  mpz_sub (abs_r1, abs_r1, r);
+  if (mpz_cmp (abs_r1, r) < (mpz_odd_p (q) != 0))
+    (neg_d == neg_r ? mpz_add_ui : mpz_sub_ui) (q, q, 1);
+  mpz_clear (r);
+  mpz_clear (abs_r1);
 }
 
 /* The code uses emacs_rint, so that it works to undefine HAVE_RINT
@@ -483,7 +498,7 @@ This rounds the value towards +inf.
 With optional DIVISOR, return the smallest integer no less than ARG/DIVISOR.  */)
   (Lisp_Object arg, Lisp_Object divisor)
 {
-  return rounding_driver (arg, divisor, ceil, ceiling2, "ceiling");
+  return rounding_driver (arg, divisor, ceil, mpz_cdiv_q, "ceiling");
 }
 
 DEFUN ("floor", Ffloor, Sfloor, 1, 2, 0,
@@ -492,7 +507,7 @@ This rounds the value towards -inf.
 With optional DIVISOR, return the largest integer no greater than ARG/DIVISOR.  */)
   (Lisp_Object arg, Lisp_Object divisor)
 {
-  return rounding_driver (arg, divisor, floor, floor2, "floor");
+  return rounding_driver (arg, divisor, floor, mpz_fdiv_q, "floor");
 }
 
 DEFUN ("round", Fround, Sround, 1, 2, 0,
@@ -505,7 +520,7 @@ your machine.  For example, (round 2.5) can return 3 on some
 systems, but 2 on others.  */)
   (Lisp_Object arg, Lisp_Object divisor)
 {
-  return rounding_driver (arg, divisor, emacs_rint, round2, "round");
+  return rounding_driver (arg, divisor, emacs_rint, rounddiv_q, "round");
 }
 
 DEFUN ("truncate", Ftruncate, Struncate, 1, 2, 0,
@@ -514,7 +529,7 @@ Rounds ARG toward zero.
 With optional DIVISOR, truncate ARG/DIVISOR.  */)
   (Lisp_Object arg, Lisp_Object divisor)
 {
-  return rounding_driver (arg, divisor, trunc, truncate2, "truncate");
+  return rounding_driver (arg, divisor, trunc, mpz_tdiv_q, "truncate");
 }
 
 

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Paul Eggert]

[-- Attachment #1: Type: text/plain, Size: 775 bytes --]

>>> d) Extend Fceiling, Ffloor, Fround and Ftruncate to support bignums by
>>>    updating rounding_driver.
> 
> I worked on these and installed patches to master that should do (a), (b), and 
> (c). For (d) I wrote the attached patch, and plan to test it a bit more before 
> installing, as it's the hairiest.

It took me longer to write the test cases than the code, but the tests did find 
bugs so it was worth it. I installed the attached.

While we're on the subject I moved the definition of 'bignump' and 'fixnump' 
from C to Lisp, since they are easily implementable in Lisp and don't seem to be 
performance relevant. Hope you don't mind too much that I would rather minimize 
the low-level details that the C code exports.

Both patches attached.

[-- Attachment #2: 0001-Move-bignump-fixnump-from-C-to-Lisp.patch --]
[-- Type: text/x-patch, Size: 3638 bytes --]

From c79444c5b7b8ead1ea98ed5603bf2a49c13dbf16 Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Tue, 21 Aug 2018 16:06:58 -0700
Subject: [PATCH 1/2] Move bignump, fixnump from C to Lisp

* doc/lispref/objects.texi (Integer Type): Mention
most-negative-fixnum and most-positive-fixnum as alternatives
to fixnump and bignump.
* lisp/subr.el (fixnump, bignump): Now written in Lisp.
* src/data.c (Ffixnump, Fbignump): No longer written in C,
as these new functions are not crucial for performance.
---
 doc/lispref/objects.texi |  7 ++++---
 lisp/subr.el             |  9 +++++++++
 src/data.c               | 21 ---------------------
 3 files changed, 13 insertions(+), 24 deletions(-)

diff --git a/doc/lispref/objects.texi b/doc/lispref/objects.texi
index 8c92de123c..a0940032ee 100644
--- a/doc/lispref/objects.texi
+++ b/doc/lispref/objects.texi
@@ -190,9 +190,10 @@ Integer Type
 fixnum will return a bignum instead.
 
   Fixnums can be compared with @code{eq}, but bignums require
-@code{eql} or @code{=}.  The @code{fixnump} predicate can be used to
-detect such small integers, and @code{bignump} can be used to detect
-large integers.
+@code{eql} or @code{=}.  To test whether an integer is a fixnum or a
+bignum, you can compare it to @code{most-negative-fixnum} and
+@code{most-positive-fixnum}, or you can use the convenience predicates
+@code{fixnump} and @code{bignump} on any object.
 
   The read syntax for integers is a sequence of (base ten) digits with an
 optional sign at the beginning and an optional period at the end.  The
diff --git a/lisp/subr.el b/lisp/subr.el
index cafa4835ea..9e880bc880 100644
--- a/lisp/subr.el
+++ b/lisp/subr.el
@@ -366,6 +366,15 @@ zerop
   (declare (compiler-macro (lambda (_) `(= 0 ,number))))
   (= 0 number))
 
+(defun fixnump (object)
+  "Return t if OBJECT is a fixnum."
+  (and (integerp object)
+       (<= most-negative-fixnum object most-positive-fixnum)))
+
+(defun bignump (object)
+  "Return t if OBJECT is a bignum."
+  (and (integerp object) (not (fixnump object))))
+
 (defun lsh (value count)
   "Return VALUE with its bits shifted left by COUNT.
 If COUNT is negative, shifting is actually to the right.
diff --git a/src/data.c b/src/data.c
index 4c6d33f294..08c7271dd7 100644
--- a/src/data.c
+++ b/src/data.c
@@ -511,16 +511,6 @@ DEFUN ("integerp", Fintegerp, Sintegerp, 1, 1, 0,
   return Qnil;
 }
 
-DEFUN ("fixnump", Ffixnump, Sfixnump, 1, 1, 0,
-       doc: /* Return t if OBJECT is an fixnum.  */
-       attributes: const)
-  (Lisp_Object object)
-{
-  if (FIXNUMP (object))
-    return Qt;
-  return Qnil;
-}
-
 DEFUN ("integer-or-marker-p", Finteger_or_marker_p, Sinteger_or_marker_p, 1, 1, 0,
        doc: /* Return t if OBJECT is an integer or a marker (editor pointer).  */)
   (register Lisp_Object object)
@@ -598,15 +588,6 @@ DEFUN ("condition-variable-p", Fcondition_variable_p, Scondition_variable_p,
     return Qt;
   return Qnil;
 }
-
-DEFUN ("bignump", Fbignump, Sbignump, 1, 1, 0,
-       doc: /* Return t if OBJECT is a bignum.  */)
-  (Lisp_Object object)
-{
-  if (BIGNUMP (object))
-    return Qt;
-  return Qnil;
-}
 \f
 /* Extract and set components of lists.  */
 
@@ -4153,7 +4134,6 @@ syms_of_data (void)
   defsubr (&Sconsp);
   defsubr (&Satom);
   defsubr (&Sintegerp);
-  defsubr (&Sfixnump);
   defsubr (&Sinteger_or_marker_p);
   defsubr (&Snumberp);
   defsubr (&Snumber_or_marker_p);
@@ -4179,7 +4159,6 @@ syms_of_data (void)
   defsubr (&Sthreadp);
   defsubr (&Smutexp);
   defsubr (&Scondition_variable_p);
-  defsubr (&Sbignump);
   defsubr (&Scar);
   defsubr (&Scdr);
   defsubr (&Scar_safe);
-- 
2.17.1


[-- Attachment #3: 0002-Add-bignum-support-to-floor-ceiling-etc.patch --]
[-- Type: text/x-patch, Size: 7285 bytes --]

From 30efb8ed6c0968ca486081112f8d4dc147af9e6c Mon Sep 17 00:00:00 2001
From: Paul Eggert <eggert@cs.ucla.edu>
Date: Tue, 21 Aug 2018 19:23:45 -0700
Subject: [PATCH 2/2] Add bignum support to floor, ceiling, etc.

Problem reported by Andy Moreton (Bug#32463#35 (d)).
* src/floatfns.c (rounding_driver): Change the signature
of the integer rounder to use mpz_t rather than EMACS_INT.
All uses changed.  Support bignums.
(ceiling2, floor2, truncate2, round2): Remove.
All uses changed to rounddiv_q or to a GMP library function.
(rounddiv_q): New function.
* test/src/floatfns-tests.el (bignum-round): New test.
---
 src/floatfns.c             | 95 ++++++++++++++++++++++----------------
 test/src/floatfns-tests.el | 27 +++++++++++
 2 files changed, 82 insertions(+), 40 deletions(-)

diff --git a/src/floatfns.c b/src/floatfns.c
index ea9000b90a..c09fe9d6a5 100644
--- a/src/floatfns.c
+++ b/src/floatfns.c
@@ -357,10 +357,10 @@ This is the same as the exponent of a float.  */)
 static Lisp_Object
 rounding_driver (Lisp_Object arg, Lisp_Object divisor,
 		 double (*double_round) (double),
-		 EMACS_INT (*int_round2) (EMACS_INT, EMACS_INT),
+		 void (*int_divide) (mpz_t, mpz_t const, mpz_t const),
 		 const char *name)
 {
-  CHECK_FIXNUM_OR_FLOAT (arg);
+  CHECK_NUMBER (arg);
 
   double d;
   if (NILP (divisor))
@@ -371,12 +371,25 @@ rounding_driver (Lisp_Object arg, Lisp_Object divisor,
     }
   else
     {
-      CHECK_FIXNUM_OR_FLOAT (divisor);
+      CHECK_NUMBER (divisor);
       if (!FLOATP (arg) && !FLOATP (divisor))
 	{
-	  if (XFIXNUM (divisor) == 0)
+	  if (EQ (divisor, make_fixnum (0)))
 	    xsignal0 (Qarith_error);
-	  return make_fixnum (int_round2 (XFIXNUM (arg), XFIXNUM (divisor)));
+	  mpz_t d, q;
+	  mpz_init (d);
+	  mpz_init (q);
+	  int_divide (q,
+		      (FIXNUMP (arg)
+		       ? (mpz_set_intmax (q, XFIXNUM (arg)), q)
+		       : XBIGNUM (arg)->value),
+		      (FIXNUMP (divisor)
+		       ? (mpz_set_intmax (d, XFIXNUM (divisor)), d)
+		       : XBIGNUM (divisor)->value));
+	  Lisp_Object result = make_number (q);
+	  mpz_clear (d);
+	  mpz_clear (q);
+	  return result;
 	}
 
       double f1 = FLOATP (arg) ? XFLOAT_DATA (arg) : XFIXNUM (arg);
@@ -400,37 +413,39 @@ rounding_driver (Lisp_Object arg, Lisp_Object divisor,
   xsignal2 (Qrange_error, build_string (name), arg);
 }
 
-static EMACS_INT
-ceiling2 (EMACS_INT i1, EMACS_INT i2)
-{
-  return i1 / i2 + ((i1 % i2 != 0) & ((i1 < 0) == (i2 < 0)));
-}
-
-static EMACS_INT
-floor2 (EMACS_INT i1, EMACS_INT i2)
-{
-  return i1 / i2 - ((i1 % i2 != 0) & ((i1 < 0) != (i2 < 0)));
-}
-
-static EMACS_INT
-truncate2 (EMACS_INT i1, EMACS_INT i2)
-{
-  return i1 / i2;
-}
-
-static EMACS_INT
-round2 (EMACS_INT i1, EMACS_INT i2)
-{
-  /* The C language's division operator gives us one remainder R, but
-     we want the remainder R1 on the other side of 0 if R1 is closer
-     to 0 than R is; because we want to round to even, we also want R1
-     if R and R1 are the same distance from 0 and if C's quotient is
-     odd.  */
-  EMACS_INT q = i1 / i2;
-  EMACS_INT r = i1 % i2;
-  EMACS_INT abs_r = eabs (r);
-  EMACS_INT abs_r1 = eabs (i2) - abs_r;
-  return q + (abs_r + (q & 1) <= abs_r1 ? 0 : (i2 ^ r) < 0 ? -1 : 1);
+static void
+rounddiv_q (mpz_t q, mpz_t const n, mpz_t const d)
+{
+  /* mpz_tdiv_qr gives us one remainder R, but we want the remainder
+     R1 on the other side of 0 if R1 is closer to 0 than R is; because
+     we want to round to even, we also want R1 if R and R1 are the
+     same distance from 0 and if the quotient is odd.
+
+     If we were using EMACS_INT arithmetic instead of bignums,
+     the following code could look something like this:
+
+     q = n / d;
+     r = n % d;
+     neg_d = d < 0;
+     neg_r = r < 0;
+     r = eabs (r);
+     abs_r1 = eabs (d) - r;
+     if (abs_r1 < r + (q & 1))
+       q += neg_d == neg_r ? 1 : -1;  */
+
+  mpz_t r, abs_r1;
+  mpz_init (r);
+  mpz_init (abs_r1);
+  mpz_tdiv_qr (q, r, n, d);
+  bool neg_d = mpz_sgn (d) < 0;
+  bool neg_r = mpz_sgn (r) < 0;
+  mpz_abs (r, r);
+  mpz_abs (abs_r1, d);
+  mpz_sub (abs_r1, abs_r1, r);
+  if (mpz_cmp (abs_r1, r) < (mpz_odd_p (q) != 0))
+    (neg_d == neg_r ? mpz_add_ui : mpz_sub_ui) (q, q, 1);
+  mpz_clear (r);
+  mpz_clear (abs_r1);
 }
 
 /* The code uses emacs_rint, so that it works to undefine HAVE_RINT
@@ -461,7 +476,7 @@ This rounds the value towards +inf.
 With optional DIVISOR, return the smallest integer no less than ARG/DIVISOR.  */)
   (Lisp_Object arg, Lisp_Object divisor)
 {
-  return rounding_driver (arg, divisor, ceil, ceiling2, "ceiling");
+  return rounding_driver (arg, divisor, ceil, mpz_cdiv_q, "ceiling");
 }
 
 DEFUN ("floor", Ffloor, Sfloor, 1, 2, 0,
@@ -470,7 +485,7 @@ This rounds the value towards -inf.
 With optional DIVISOR, return the largest integer no greater than ARG/DIVISOR.  */)
   (Lisp_Object arg, Lisp_Object divisor)
 {
-  return rounding_driver (arg, divisor, floor, floor2, "floor");
+  return rounding_driver (arg, divisor, floor, mpz_fdiv_q, "floor");
 }
 
 DEFUN ("round", Fround, Sround, 1, 2, 0,
@@ -483,7 +498,7 @@ your machine.  For example, (round 2.5) can return 3 on some
 systems, but 2 on others.  */)
   (Lisp_Object arg, Lisp_Object divisor)
 {
-  return rounding_driver (arg, divisor, emacs_rint, round2, "round");
+  return rounding_driver (arg, divisor, emacs_rint, rounddiv_q, "round");
 }
 
 DEFUN ("truncate", Ftruncate, Struncate, 1, 2, 0,
@@ -492,7 +507,7 @@ Rounds ARG toward zero.
 With optional DIVISOR, truncate ARG/DIVISOR.  */)
   (Lisp_Object arg, Lisp_Object divisor)
 {
-  return rounding_driver (arg, divisor, trunc, truncate2, "truncate");
+  return rounding_driver (arg, divisor, trunc, mpz_tdiv_q, "truncate");
 }
 
 
diff --git a/test/src/floatfns-tests.el b/test/src/floatfns-tests.el
index e4caaa1e49..592efce359 100644
--- a/test/src/floatfns-tests.el
+++ b/test/src/floatfns-tests.el
@@ -58,4 +58,31 @@
 (ert-deftest bignum-mod ()
   (should (= 0 (mod (1+ most-positive-fixnum) 2.0))))
 
+(ert-deftest bignum-round ()
+  (let ((ns (list (* most-positive-fixnum most-negative-fixnum)
+                  (1- most-negative-fixnum) most-negative-fixnum
+                  (1+ most-negative-fixnum) -2 1 1 2
+                  (1- most-positive-fixnum) most-positive-fixnum
+                  (1+ most-positive-fixnum)
+                  (* most-positive-fixnum most-positive-fixnum))))
+    (dolist (n ns)
+      (dolist (d ns)
+        (let ((q (/ n d))
+              (r (% n d))
+              (same-sign (eq (< n 0) (< d 0))))
+          (should (= (ceiling n d)
+                     (+ q (if (and same-sign (not (zerop r))) 1 0))))
+          (should (= (floor n d)
+                     (- q (if (and (not same-sign) (not (zerop r))) 1 0))))
+          (should (= (truncate n d) q))
+          (let ((cdelta (abs (- n (* d (ceiling n d)))))
+                (fdelta (abs (- n (* d (floor n d)))))
+                (rdelta (abs (- n (* d (round n d))))))
+            (should (<= rdelta cdelta))
+            (should (<= rdelta fdelta))
+            (should (if (zerop r)
+                        (= 0 cdelta fdelta rdelta)
+                      (or (/= cdelta fdelta)
+                          (zerop (% (round n d) 2)))))))))))
+
 (provide 'floatfns-tests)
-- 
2.17.1

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Tom Tromey]

>>>>> "Paul" == Paul Eggert <eggert@cs.ucla.edu> writes:

Paul> My bigger concern is memory management, along with integer overflow in
Paul> size or bitcount calculation. Copies are made of bignums when not
Paul> needed

One idea is to change make_number to take ownership of the passed-in mpz_t.
I didn't do this because it makes the API confusing to use (I put in a
comment to this effect) but perhaps efficiency outweighs this; and
anyway the function could be renamed to make this more clear.

Tom

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Paul Eggert]

Tom Tromey wrote:
> One idea is to change make_number to take ownership of the passed-in mpz_t.
> I didn't do this because it makes the API confusing to use (I put in a
> comment to this effect) but perhaps efficiency outweighs this; and
> anyway the function could be renamed to make this more clear.

I plan to look into doing something along those lines. (Also, change its name to 
make_integer, since it doesn't make floats.)

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Eli Zaretskii]

> From: Paul Eggert <eggert@cs.ucla.edu>
> Date: Wed, 22 Aug 2018 10:52:53 -0700
> Cc: Andy Moreton <andrewjmoreton@gmail.com>, 32463@debbugs.gnu.org
> 
> Also, change its name to make_integer, since it doesn't make
> floats.

I'd rather we left the name alone.  It's a veteran name, burnt into
our muscle memory by many years of coding in Emacs.  Let's not change
it just because it isn't 100% accurate.

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Paul Eggert]

Eli Zaretskii wrote:
> I'd rather we left the name alone.  It's a veteran name, burnt into
> our muscle memory by many years of coding in Emacs.

But the name 'make_number' means something completely different now; it has a 
different signature, it is a lot more expensive than it used to be, and it 
cannot be used the way the old name could be used. So now is a good time to 
change the name anyway, regardless of whether the name choice was a good one 
originally.

We already changed the name XINT and friends, even though their semantics didn't 
change. It would be odd if we didn't fix make_number too, while we're in the 
neighborhood, since the case for changing it is even stronger than the case for 
XINT etc.

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Eli Zaretskii]

> Cc: tom@tromey.com, andrewjmoreton@gmail.com, 32463@debbugs.gnu.org
> From: Paul Eggert <eggert@cs.ucla.edu>
> Date: Wed, 22 Aug 2018 17:28:49 -0700
> 
> Eli Zaretskii wrote:
> > I'd rather we left the name alone.  It's a veteran name, burnt into
> > our muscle memory by many years of coding in Emacs.
> 
> But the name 'make_number' means something completely different now; it has a 
> different signature, it is a lot more expensive than it used to be, and it 
> cannot be used the way the old name could be used.

Then perhaps restore the old make_number and make a new function with
the extra functionality.

> We already changed the name XINT and friends, even though their semantics didn't 
> change.

And it's already a significant blow to coding habits.  I wonder when
this renaming spree will end, because it's beginning to look like a
whole new language to learn.

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Andy Moreton]

On Sun 19 Aug 2018, Paul Eggert wrote:

>>> a) A bug in bignumcompare for 64bit Windows. Patch is here:
>>> http://lists.gnu.org/archive/html/emacs-devel/2018-08/msg00487.html
>>> ...
>>> b) fmod_float has a bug:
>>> http://lists.gnu.org/archive/html/emacs-devel/2018-08/msg00442.html
>>>
>>> c) Extend Fexpt to support bignums. Patch is here:
>>> http://lists.gnu.org/archive/html/emacs-devel/2018-08/msg00503.html
>>>
>>> d) Extend Fceiling, Ffloor, Fround and Ftruncate to support bignums by
>>>    updating rounding_driver.
>
> I worked on these and installed patches to master that should do (a), (b), and
> (c). For (d) I wrote the attached patch, and plan to test it a bit more before
> installing, as it's the hairiest.

Thanks for fixing up all of these issues. Hopefully with some added test
cases the patch for (d) will also work too. Two more issues:

e) Grepping for FIXED_OR_FLOATP shows various places where code either
   assumes that all types are covered (no longer true now there are
   bignums), or uses incorrect accessors for the value in the object.
   For example, Fdefine_coding_system_internal has:

      else if (FIXED_OR_FLOATP (tmp))
        {
          dim2 = CHARSET_DIMENSION (CHARSET_FROM_ID (XFIXNAT (tmp)));

   Which should probably be:

      else if (NUMBERP (tmp))
        {
          dim2 = CHARSET_DIMENSION (CHARSET_FROM_ID (XFLOATINT (tmp)));

f) Users of CONS_TO_INTEGER and INTEGER_TO_CONS could be converted to
   use bignums.

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Paul Eggert]

> Does this limit apply to bignum values in lisp objects, or to
> intermediate values inside libgmp, which may require extra space ?
> The documentation for `integer-width' should make this clear.

integer-width applies only to Lisp objects. I'm not sure we should be exposing 
internal details of the interpreter to the Lisp user, which includes the sizes 
of its internal temporaries. If a need shows up for it we can do it, but I don't 
see the need.

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Andy Moreton]

On Tue 21 Aug 2018, Paul Eggert wrote:

>> Does this limit apply to bignum values in lisp objects, or to
>> intermediate values inside libgmp, which may require extra space ?
>> The documentation for `integer-width' should make this clear.
>
> integer-width applies only to Lisp objects. I'm not sure we should be exposing
> internal details of the interpreter to the Lisp user, which includes the sizes
> of its internal temporaries. If a need shows up for it we can do it, but I
> don't see the need.

The current documentation is uninformative:

  Maximum number of bits in bignums.
  Integers outside the fixnum range are limited to absolute values less
  than 2**N, where N is this variable’s value.  N should be nonnegative.

This says plenty abut fixnums, but does not mention that anything larger
than fixnum range is represented as a bignum. For users who are new to
all of this, it is important to state that.

I think it is worth mentioning that intermediate computations not visible
to lisp may use slightly larger bignums, and to make it clear that this
is a soft limit intended to prevent misbehaviour of the runtime.

    AndyM

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Eli Zaretskii]

> From: Andy Moreton <andrewjmoreton@gmail.com>
> Date: Thu, 23 Aug 2018 00:27:55 +0100
> 
> The current documentation is uninformative:
> 
>   Maximum number of bits in bignums.
>   Integers outside the fixnum range are limited to absolute values less
>   than 2**N, where N is this variable’s value.  N should be nonnegative.
> 
> This says plenty abut fixnums, but does not mention that anything larger
> than fixnum range is represented as a bignum. For users who are new to
> all of this, it is important to state that.
> 
> I think it is worth mentioning that intermediate computations not visible
> to lisp may use slightly larger bignums, and to make it clear that this
> is a soft limit intended to prevent misbehaviour of the runtime.

Feel free to propose a documentation patch, and let's take it from
there.

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Paul Eggert]

> Have you checked a mini-gmp build to ensure that this patch works if
> the GMP library is not installed ?

I have now. :-)  It works, in the sense that Emacs builds and fails only the 
tests that it was already failing.

> It might be slightly faster to use mpz_limbs_read in make_number instead
> of mpz_getlimbn.

On Fedora 28 x86-64, mpz_getlimbn is inline whereas mpz_limbs_read is a function 
call, so it's not clear which should be faster. Another item on the list of 
things to do....

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Andy Moreton]

On Tue 21 Aug 2018, Paul Eggert wrote:

>> Have you checked a mini-gmp build to ensure that this patch works if
>> the GMP library is not installed ?
>
> I have now. :-)  It works, in the sense that Emacs builds and fails only the
> tests that it was already failing.

Thanks. I mentioned this because GMP_NUMB_BITS etc are not defined in
mini-gmp.h (which your patches handle), but I wasn't sure if there were
other symbols that needed similar treatment.

As GMP_NUMB_BITS is always defined now, uses of mp_bits_per_limb could
be replaced with GMP_NUMB_BITS.

    AndyM

bug#32463: 27.0.50; (logior -1) => 4611686018427387903

[Andy Moreton]

On Tue 21 Aug 2018, Paul Eggert wrote:

>>>> d) Extend Fceiling, Ffloor, Fround and Ftruncate to support bignums by
>>>>    updating rounding_driver.
>>
>> I worked on these and installed patches to master that should do (a), (b),
>> and (c). For (d) I wrote the attached patch, and plan to test it a bit more
>> before installing, as it's the hairiest.
>
> It took me longer to write the test cases than the code, but the tests did
> find bugs so it was worth it. I installed the attached.

Thanks for all of your recent work on bignum issues, which has
siginificantly improved the bignum implementation.

> While we're on the subject I moved the definition of 'bignump' and 'fixnump'
> from C to Lisp, since they are easily implementable in Lisp and don't seem to
> be performance relevant. Hope you don't mind too much that I would rather
> minimize the low-level details that the C code exports.

I agree that performance is not an issue. However implementing these in lisp
assumes that bignums never represent values in fixnum range, rather than
checking that. We need some checks at the C level to ensure that this
property always holds.

    AndyM