* bug#8611: fixnum arithmetic should not wrap around
@ 2011-05-03 18:27 Paul Eggert
2011-05-04 0:31 ` Stefan Monnier
` (2 more replies)
0 siblings, 3 replies; 10+ messages in thread
From: Paul Eggert @ 2011-05-03 18:27 UTC (permalink / raw
To: 8611
Currently, on a 32-bit host, Emacs is not consistent in its treatment
of integers that are out of range. The top-level Lisp reader treats
536870912 as if it were 536870912.0; but as of Emacs 23.3 it also
evaluates (1+ 536870911) to -536870912; in Emacs 23.1 the same
expression evaluated to 0, which was no better.
If Emacs Lisp treats too-large integers as floating point when
reading, then its arithmetic should be consistent with this. In the
long run perhaps it'd be better for Emacs Lisp to use bignums, but
until then, consistent use of floating point is a better substitute
than wraparound.
Here's a proposed patch to do that. It affects only the arithmetic
operations, not shifting, though shifting could easily be added to the
list of operations that switch to floating point on overflow.
=== modified file 'doc/lispref/ChangeLog'
--- doc/lispref/ChangeLog 2011-05-03 07:41:32 +0000
+++ doc/lispref/ChangeLog 2011-05-03 16:33:36 +0000
@@ -1,6 +1,9 @@
2011-05-03 Paul Eggert <eggert@cs.ucla.edu>
* numbers.texi (Integer Basics): Large integers are treated as floats.
+ (Arithmetic Operations, Math Functions): Large integers go to
+ floats instead of wrapping around.
+ * objects.texi (Integer Type): Likewise.
2011-04-30 Lars Magne Ingebrigtsen <larsi@gnus.org>
=== modified file 'doc/lispref/numbers.texi'
--- doc/lispref/numbers.texi 2011-05-03 07:41:32 +0000
+++ doc/lispref/numbers.texi 2011-05-03 16:33:36 +0000
@@ -507,9 +507,9 @@
All of these functions except @code{%} return a floating point value
if any argument is floating.
- It is important to note that in Emacs Lisp, arithmetic functions
-do not check for overflow. Thus @code{(1+ 268435455)} may evaluate to
-@minus{}268435456, depending on your hardware.
+ If integer arithmetic overflows, the resulting value is converted
+to floating point. Thus @code{(1+ 536870911)} may evaluate to
+536870912.0, depending on your hardware.
@defun 1+ number-or-marker
This function returns @var{number-or-marker} plus 1.
@@ -826,7 +826,7 @@
As the example illustrates, shifting one place to the right divides the
value of a positive integer by two, rounding downward.
-The function @code{lsh}, like all Emacs Lisp arithmetic functions, does
+The function @code{lsh} does
not check for overflow, so shifting left can discard significant bits
and change the sign of the number. For example, left shifting
536,870,911 produces @minus{}2 on a 30-bit machine:
@@ -1169,8 +1169,8 @@
@defun expt x y
This function returns @var{x} raised to power @var{y}. If both
-arguments are integers and @var{y} is positive, the result is an
-integer; in this case, overflow causes truncation, so watch out.
+arguments are integers and @var{y} is nonnegative, the result is an
+integer if it is in Emacs integer range.
@end defun
@defun sqrt arg
=== modified file 'doc/lispref/objects.texi'
--- doc/lispref/objects.texi 2011-02-25 03:27:45 +0000
+++ doc/lispref/objects.texi 2011-05-03 16:33:36 +0000
@@ -179,10 +179,10 @@
@tex
@math{2^{29}-1})
@end tex
-on most machines. (Some machines may provide a wider range.) It is
-important to note that the Emacs Lisp arithmetic functions do not check
-for overflow. Thus @code{(1+ 536870911)} is @minus{}536870912 on most
-machines.
+on most machines. (Some machines may provide a wider range.)
+If integer arithmetic overflows, the resulting value is converted
++to floating point. Thus @code{(1+ 536870911)} may evaluate to
++536870912.0, depending on your hardware.
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
@@ -195,7 +195,8 @@
1 ; @r{The integer 1.}
1. ; @r{Also the integer 1.}
+1 ; @r{Also the integer 1.}
-1073741825 ; @r{Also the integer 1 on a 30-bit implementation.}
+1073741825 ; @r{The floating point number 1073741825.0,}
+ ; @r{on a 30-bit implementation.}
@end group
@end example
=== modified file 'etc/ChangeLog'
--- etc/ChangeLog 2011-05-03 03:34:26 +0000
+++ etc/ChangeLog 2011-05-03 16:33:36 +0000
@@ -1,3 +1,8 @@
+2011-05-03 Paul Eggert <eggert@cs.ucla.edu>
+
+ * NEWS: Integer overflow now yields floating-point instead of
+ wrapping around.
+
2011-05-03 Leo Liu <sdl.web@gmail.com>
* NEWS: Mention the new command isearch-yank-pop.
=== modified file 'etc/NEWS'
--- etc/NEWS 2011-05-03 03:34:26 +0000
+++ etc/NEWS 2011-05-03 16:33:36 +0000
@@ -728,6 +728,12 @@
\f
* Incompatible Lisp Changes in Emacs 24.1
++++
+** Integer arithmetic overflow now yields the nearest floating-piont
+value rather than wrapping around. For example, on a 32-bit machine,
+(1+ 536870911) yields 536870912.0, instead of the -536870912 it
+yielded in Emacs 23.3, or the 0 it yielded in Emacs 23.1.
+
---
** `char-direction-table' and the associated function `char-direction'
were deleted. They were buggy and inferior to the new support of
=== modified file 'src/ChangeLog'
--- src/ChangeLog 2011-05-03 06:26:40 +0000
+++ src/ChangeLog 2011-05-03 08:52:13 +0000
@@ -1,5 +1,14 @@
2011-05-03 Paul Eggert <eggert@cs.ucla.edu>
+ Arithmetic overflows now return float rather than wrapping around.
+ * data.c: Include <intprops.h>.
+ (arith_driver): Use floating point if the accumulator would otherwise
+ go out of EMACS_INT range.
+ (arith_driver, Fadd1, Fsub1): Use floating point if the result is
+ out of Emacs fixnum range.
+ * bytecode.c (exec_byte_code): Likewise, for Bsub1, Badd1, Bnegate.
+ * floatfns.c (Fexpt): Likewise.
+
* callproc.c (Fcall_process): Use 'volatile' to avoid vfork clobbering.
* process.c (Fformat_network_address): Fix typo: args2 -> *args2.
=== modified file 'src/bytecode.c'
--- src/bytecode.c 2011-04-25 21:34:39 +0000
+++ src/bytecode.c 2011-05-03 07:51:38 +0000
@@ -1186,7 +1186,7 @@
{
Lisp_Object v1;
v1 = TOP;
- if (INTEGERP (v1))
+ if (INTEGERP (v1) && MOST_NEGATIVE_FIXNUM < XINT (v1))
{
XSETINT (v1, XINT (v1) - 1);
TOP = v1;
@@ -1204,7 +1204,7 @@
{
Lisp_Object v1;
v1 = TOP;
- if (INTEGERP (v1))
+ if (INTEGERP (v1) && XINT (v1) < MOST_POSITIVE_FIXNUM)
{
XSETINT (v1, XINT (v1) + 1);
TOP = v1;
@@ -1290,7 +1290,7 @@
{
Lisp_Object v1;
v1 = TOP;
- if (INTEGERP (v1))
+ if (INTEGERP (v1) && - MOST_POSITIVE_FIXNUM <= XINT (v1))
{
XSETINT (v1, - XINT (v1));
TOP = v1;
=== modified file 'src/data.c'
--- src/data.c 2011-04-25 21:34:39 +0000
+++ src/data.c 2011-05-03 07:51:38 +0000
@@ -22,6 +22,9 @@
#include <signal.h>
#include <stdio.h>
#include <setjmp.h>
+
+#include <intprops.h>
+
#include "lisp.h"
#include "puresize.h"
#include "character.h"
@@ -2426,10 +2429,8 @@
static Lisp_Object
arith_driver (enum arithop code, size_t nargs, register Lisp_Object *args)
{
- register Lisp_Object val;
register size_t argnum;
register EMACS_INT accum = 0;
- register EMACS_INT next;
switch (SWITCH_ENUM_CAST (code))
{
@@ -2451,58 +2452,89 @@
for (argnum = 0; argnum < nargs; argnum++)
{
+ EMACS_INT a = accum;
+ int use_float = 0;
+
/* Using args[argnum] as argument to CHECK_NUMBER_... */
- val = args[argnum];
+ Lisp_Object val = args[argnum];
CHECK_NUMBER_OR_FLOAT_COERCE_MARKER (val);
-
- if (FLOATP (val))
- return float_arith_driver ((double) accum, argnum, code,
- nargs, args);
args[argnum] = val;
- next = XINT (args[argnum]);
- switch (SWITCH_ENUM_CAST (code))
+
+ if (FLOATP (val))
+ use_float = 1;
+ else
{
- case Aadd:
- accum += next;
- break;
- case Asub:
- accum = argnum ? accum - next : nargs == 1 ? - next : next;
- break;
- case Amult:
- accum *= next;
- break;
- case Adiv:
- if (!argnum)
- accum = next;
- else
+ EMACS_INT next = XINT (val);
+ switch (SWITCH_ENUM_CAST (code))
{
- if (next == 0)
- xsignal0 (Qarith_error);
- accum /= next;
+ case Aadd:
+ if (next < 0
+ ? a < TYPE_MINIMUM (EMACS_INT) - next
+ : TYPE_MAXIMUM (EMACS_INT) - next < a)
+ use_float = 1;
+ else
+ a += next;
+ break;
+ case Asub:
+ if (argnum == 0 && nargs != 1)
+ a = next;
+ else if (next < 0
+ ? TYPE_MAXIMUM (EMACS_INT) + next < a
+ : a < TYPE_MINIMUM (EMACS_INT) + next)
+ use_float = 1;
+ else
+ a -= next;
+ break;
+ case Amult:
+ if (next < 0
+ ? (a < 0
+ ? a < TYPE_MAXIMUM (EMACS_INT) / next
+ : next != -1 && TYPE_MINIMUM (EMACS_INT) / next < a)
+ : (next != 0
+ && (a < 0
+ ? a < TYPE_MINIMUM (EMACS_INT) / next
+ : TYPE_MAXIMUM (EMACS_INT) / next < a)))
+ use_float = 1;
+ else
+ a *= next;
+ break;
+ case Adiv:
+ if (!argnum)
+ a = next;
+ else
+ {
+ if (next == 0)
+ xsignal0 (Qarith_error);
+ a /= next;
+ }
+ break;
+ case Alogand:
+ a &= next;
+ break;
+ case Alogior:
+ a |= next;
+ break;
+ case Alogxor:
+ a ^= next;
+ break;
+ case Amax:
+ if (!argnum || a < next)
+ a = next;
+ break;
+ case Amin:
+ if (!argnum || next < a)
+ a = next;
+ break;
}
- break;
- case Alogand:
- accum &= next;
- break;
- case Alogior:
- accum |= next;
- break;
- case Alogxor:
- accum ^= next;
- break;
- case Amax:
- if (!argnum || next > accum)
- accum = next;
- break;
- case Amin:
- if (!argnum || next < accum)
- accum = next;
- break;
}
+
+ if (use_float)
+ return float_arith_driver (accum, argnum, code, nargs, args);
+
+ accum = a;
}
- XSETINT (val, accum);
- return val;
+ return make_fixnum_or_float (accum);
}
#undef isnan
@@ -2777,7 +2809,8 @@
if (FLOATP (number))
return (make_float (1.0 + XFLOAT_DATA (number)));
-
+ if (XINT (number) + 1 == MOST_POSITIVE_FIXNUM + 1)
+ return make_float (XINT (number) + 1);
XSETINT (number, XINT (number) + 1);
return number;
}
@@ -2791,7 +2824,8 @@
if (FLOATP (number))
return (make_float (-1.0 + XFLOAT_DATA (number)));
-
+ if (XINT (number) - 1 == MOST_NEGATIVE_FIXNUM - 1)
+ return make_float (XINT (number) - 1);
XSETINT (number, XINT (number) - 1);
return number;
}
=== modified file 'src/floatfns.c'
--- src/floatfns.c 2011-04-14 05:04:02 +0000
+++ src/floatfns.c 2011-05-03 08:52:13 +0000
@@ -491,27 +491,39 @@
y = XINT (arg2);
acc = 1;
- if (y < 0)
- {
- if (x == 1)
- acc = 1;
- else if (x == -1)
- acc = (y & 1) ? -1 : 1;
- else
- acc = 0;
- }
- else
- {
- while (y > 0)
- {
- if (y & 1)
- acc *= x;
- x *= x;
- y = (unsigned)y >> 1;
- }
- }
- XSETINT (val, acc);
- return val;
+ if ((x == 0 && y != 0) || x == 1 || (x == -1 && (y & 1)))
+ return arg1;
+ if (x == -1)
+ y = 0;
+
+ while (1)
+ {
+ if (y & 1)
+ {
+ if (x < 0
+ ? (acc < 0
+ ? acc < MOST_POSITIVE_FIXNUM / x
+ : MOST_NEGATIVE_FIXNUM / x < acc)
+ : (acc < 0
+ ? acc < MOST_NEGATIVE_FIXNUM / x
+ : MOST_POSITIVE_FIXNUM / x < acc))
+ break;
+ acc *= x;
+ }
+
+ y >>= 1;
+ if (y == 0)
+ {
+ XSETINT (val, acc);
+ return val;
+ }
+
+ if (x < 0
+ ? x < MOST_POSITIVE_FIXNUM / x
+ : MOST_POSITIVE_FIXNUM / x < x)
+ break;
+ x *= x;
+ }
}
f1 = FLOATP (arg1) ? XFLOAT_DATA (arg1) : XINT (arg1);
f2 = FLOATP (arg2) ? XFLOAT_DATA (arg2) : XINT (arg2);
^ permalink raw reply [flat|nested] 10+ messages in thread
* bug#8611: fixnum arithmetic should not wrap around
2011-05-03 18:27 bug#8611: fixnum arithmetic should not wrap around Paul Eggert
@ 2011-05-04 0:31 ` Stefan Monnier
2011-05-04 1:19 ` Paul Eggert
2016-06-11 0:00 ` Noam Postavsky
2018-08-22 17:02 ` bug#8611: close Tom Tromey
2 siblings, 1 reply; 10+ messages in thread
From: Stefan Monnier @ 2011-05-04 0:31 UTC (permalink / raw
To: Paul Eggert; +Cc: 8611
> If Emacs Lisp treats too-large integers as floating point when
> reading, then its arithmetic should be consistent with this. In the
> long run perhaps it'd be better for Emacs Lisp to use bignums, but
> until then, consistent use of floating point is a better substitute
> than wraparound.
I'm not convinced that auto-switching to floats is a good idea.
Using floats has only been introduced in order to handle things like
file sizes larger than 4GB, i.e. the int-to-float conversion currently
only ever happens for values that come from some C function.
Until now the current inconsistency hasn't seemed to be a source of real
problems, so I'd rather leave it as is. If/when we bump into a real
problem due to it, we'll then see what needs to be done.
Stefan
^ permalink raw reply [flat|nested] 10+ messages in thread
* bug#8611: fixnum arithmetic should not wrap around
2011-05-04 0:31 ` Stefan Monnier
@ 2011-05-04 1:19 ` Paul Eggert
2011-05-04 1:29 ` Stefan Monnier
0 siblings, 1 reply; 10+ messages in thread
From: Paul Eggert @ 2011-05-04 1:19 UTC (permalink / raw
To: Stefan Monnier; +Cc: 8611
On 05/03/11 17:31, Stefan Monnier wrote:
> Using floats has only been introduced in order to handle things like
> file sizes larger than 4GB, i.e. the int-to-float conversion currently
> only ever happens for values that come from some C function.
Sorry, I don't follow. The Lisp reader currently sees "536870912"
and generates a float. How is that "some C function"?
The Lisp reader's behavior has nothing to do with the stat function
or with file sizes or with anything other than how Emacs itself
is implemented.
I'm just trying to understand the general design principle here.
On further thought:
Would it be better to change Emacs to use bignums if available?
I could do that, using GMP, I suppose. But surely it should return
bignums consistently everywhere: the Lisp reader, string-to-number,
arithmetic operations, etc.
If bignums aren't feasible for some reason, and floats are our best
approximation, shouldn't floats be used consistently whereever
bignums would otherwise be used?
^ permalink raw reply [flat|nested] 10+ messages in thread
* bug#8611: fixnum arithmetic should not wrap around
2011-05-04 1:19 ` Paul Eggert
@ 2011-05-04 1:29 ` Stefan Monnier
2011-05-04 4:10 ` Paul Eggert
0 siblings, 1 reply; 10+ messages in thread
From: Stefan Monnier @ 2011-05-04 1:29 UTC (permalink / raw
To: Paul Eggert; +Cc: 8611
>> Using floats has only been introduced in order to handle things like
>> file sizes larger than 4GB, i.e. the int-to-float conversion currently
>> only ever happens for values that come from some C function.
> Sorry, I don't follow. The Lisp reader currently sees "536870912"
> and generates a float. How is that "some C function"?
I guess "from outside of Elisp" is a better description than "from some
C function". The Lisp reader brings values from outside Elisp
into Elisp.
> Would it be better to change Emacs to use bignums if available?
Maybe. Other than Calc (and only if someone goes thorugh the trouble to
port it to the new bignum primitives), I can't think of too many
packages that would benefit, so it would seem to bring in a lot of extra
code and complexity for little pay off.
I guess Stephen could tell us if that is indeed (or not) what happen(s|ed)
with XEmacs's bignums.
Stefan
^ permalink raw reply [flat|nested] 10+ messages in thread
* bug#8611: fixnum arithmetic should not wrap around
2011-05-04 1:29 ` Stefan Monnier
@ 2011-05-04 4:10 ` Paul Eggert
2011-05-04 12:57 ` Stefan Monnier
0 siblings, 1 reply; 10+ messages in thread
From: Paul Eggert @ 2011-05-04 4:10 UTC (permalink / raw
To: Stefan Monnier; +Cc: 8611
On 05/03/11 18:29, Stefan Monnier wrote:
>> Would it be better to change Emacs to use bignums if available?
> ... Other than Calc (and only if someone goes thorugh the trouble to
> port it to the new bignum primitives), I can't think of too many
> packages that would benefit,
I can. The calendrical and time zone stuff would benefit.
That's the only elisp code that I've had much to do with, but
a quick scan of the Elisp source code suggests several other
modules would benefit as well: arc-mode.el, byte-opt.el, Gnus,
imenu.el, imap.el, lazy-lock.el, and there's more but I got
tired of looking.
> I guess "from outside of Elisp" is a better description than "from some
> C function". The Lisp reader brings values from outside Elisp
> into Elisp.
I'm still not understanding the principle. For example,
(string-to-number "536870912") operates entirely within Elisp,
but it returns a float when the integer is out of range.
Perhaps the principle is supposed to be "arithmetic operations
involving only integers always return integers"? But that's
not right either, since (expt 2 -1) returns 0.5.
In contrast, the principle "operations that would return
an integer out of range, return a nearby float instead"
is simple and easy to explain.
^ permalink raw reply [flat|nested] 10+ messages in thread
* bug#8611: fixnum arithmetic should not wrap around
2011-05-04 4:10 ` Paul Eggert
@ 2011-05-04 12:57 ` Stefan Monnier
2011-05-04 15:06 ` Paul Eggert
0 siblings, 1 reply; 10+ messages in thread
From: Stefan Monnier @ 2011-05-04 12:57 UTC (permalink / raw
To: Paul Eggert; +Cc: 8611
> I'm still not understanding the principle. For example,
> (string-to-number "536870912") operates entirely within Elisp,
> but it returns a float when the integer is out of range.
No: the content of a string is "external data", so string-to-number,
just like `read', brings external data into the Elisp world.
> In contrast, the principle "operations that would return
> an integer out of range, return a nearby float instead"
> is simple and easy to explain.
Conversion to float is in general not a good idea, as I'm sure you're
aware, since the semantics of floating point numbers is very different
from the semantics of integers. So I'd rather not do it more than we
currently do.
Also, I'd rather not fix something that's not broken, and AFAIK the
current inconsistent behavior has not caused any real problem.
Stefan
^ permalink raw reply [flat|nested] 10+ messages in thread
* bug#8611: fixnum arithmetic should not wrap around
2011-05-04 12:57 ` Stefan Monnier
@ 2011-05-04 15:06 ` Paul Eggert
2011-05-04 18:41 ` Stefan Monnier
0 siblings, 1 reply; 10+ messages in thread
From: Paul Eggert @ 2011-05-04 15:06 UTC (permalink / raw
To: Stefan Monnier; +Cc: 8611
On 05/04/11 05:57, Stefan Monnier wrote:
> Conversion to float is in general not a good idea
OK, how about using bignum instead? That would be quite a bit of
work, and I wouldn't want to embark on it if the answer is going
to be "don't fix something that isn't broken". Clearly the
current behavior is broken at some level, since we have mathematical
nonsense like adding two positive numbers gives you a negative number,
and this results in much real Emacs Lisp code going into contortions;
but if the overall idea is that this is good enough, then I should
not bother.
Perhaps I should raise this on the emacs-devel list? It seems to be
a more general point, one that surely has come up before.
^ permalink raw reply [flat|nested] 10+ messages in thread
* bug#8611: fixnum arithmetic should not wrap around
2011-05-04 15:06 ` Paul Eggert
@ 2011-05-04 18:41 ` Stefan Monnier
0 siblings, 0 replies; 10+ messages in thread
From: Stefan Monnier @ 2011-05-04 18:41 UTC (permalink / raw
To: Paul Eggert; +Cc: 8611
>> Conversion to float is in general not a good idea
> OK, how about using bignum instead?
That would be cleaner, semantics-wise. But we already have a recent
thread about it.
Stefan
^ permalink raw reply [flat|nested] 10+ messages in thread
* bug#8611: fixnum arithmetic should not wrap around
2011-05-03 18:27 bug#8611: fixnum arithmetic should not wrap around Paul Eggert
2011-05-04 0:31 ` Stefan Monnier
@ 2016-06-11 0:00 ` Noam Postavsky
2018-08-22 17:02 ` bug#8611: close Tom Tromey
2 siblings, 0 replies; 10+ messages in thread
From: Noam Postavsky @ 2016-06-11 0:00 UTC (permalink / raw
To: 8611
tag 8611 + wontfix
quit
Seems like the conclusion here is wontfix.
^ permalink raw reply [flat|nested] 10+ messages in thread
* bug#8611: close
2011-05-03 18:27 bug#8611: fixnum arithmetic should not wrap around Paul Eggert
2011-05-04 0:31 ` Stefan Monnier
2016-06-11 0:00 ` Noam Postavsky
@ 2018-08-22 17:02 ` Tom Tromey
2 siblings, 0 replies; 10+ messages in thread
From: Tom Tromey @ 2018-08-22 17:02 UTC (permalink / raw
To: 8611-done
Bignums went in, so this can be closed.
Tom
^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2018-08-22 17:02 UTC | newest]
Thread overview: 10+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2011-05-03 18:27 bug#8611: fixnum arithmetic should not wrap around Paul Eggert
2011-05-04 0:31 ` Stefan Monnier
2011-05-04 1:19 ` Paul Eggert
2011-05-04 1:29 ` Stefan Monnier
2011-05-04 4:10 ` Paul Eggert
2011-05-04 12:57 ` Stefan Monnier
2011-05-04 15:06 ` Paul Eggert
2011-05-04 18:41 ` Stefan Monnier
2016-06-11 0:00 ` Noam Postavsky
2018-08-22 17:02 ` bug#8611: close Tom Tromey
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.