From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Paul Eggert Newsgroups: gmane.emacs.bugs Subject: bug#8611: fixnum arithmetic should not wrap around Date: Tue, 03 May 2011 11:27:41 -0700 Organization: UCLA Computer Science Department Message-ID: <4DC0491D.7090404@cs.ucla.edu> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit X-Trace: dough.gmane.org 1304447876 23329 80.91.229.12 (3 May 2011 18:37:56 GMT) X-Complaints-To: usenet@dough.gmane.org NNTP-Posting-Date: Tue, 3 May 2011 18:37:56 +0000 (UTC) To: 8611@debbugs.gnu.org Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Tue May 03 20:37:52 2011 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([140.186.70.17]) by lo.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1QHKTm-0006cx-W1 for geb-bug-gnu-emacs@m.gmane.org; Tue, 03 May 2011 20:37:51 +0200 Original-Received: from localhost ([::1]:45588 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QHKTm-0006ym-5K for geb-bug-gnu-emacs@m.gmane.org; Tue, 03 May 2011 14:37:50 -0400 Original-Received: from eggs.gnu.org ([140.186.70.92]:40809) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QHKT2-0005iq-I6 for bug-gnu-emacs@gnu.org; Tue, 03 May 2011 14:37:05 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1QHKSy-0001im-Sk for bug-gnu-emacs@gnu.org; Tue, 03 May 2011 14:37:04 -0400 Original-Received: from debbugs.gnu.org ([140.186.70.43]:57963) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QHKSy-0001ic-QE for bug-gnu-emacs@gnu.org; Tue, 03 May 2011 14:37:00 -0400 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.69) (envelope-from ) id 1QHKLG-00022G-Hp; Tue, 03 May 2011 14:29:02 -0400 X-Loop: help-debbugs@gnu.org Resent-From: Paul Eggert Original-Sender: debbugs-submit-bounces@debbugs.gnu.org Resent-To: owner@debbugs.gnu.org Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Tue, 03 May 2011 18:29:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 8611 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: X-Debbugs-Original-To: bug-gnu-emacs@gnu.org Original-Received: via spool by submit@debbugs.gnu.org id=B.13044472877755 (code B ref -1); Tue, 03 May 2011 18:29:02 +0000 Original-Received: (at submit) by debbugs.gnu.org; 3 May 2011 18:28:07 +0000 Original-Received: from localhost ([127.0.0.1] helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1QHKKM-000211-Er for submit@debbugs.gnu.org; Tue, 03 May 2011 14:28:06 -0400 Original-Received: from eggs.gnu.org ([140.186.70.92]) by debbugs.gnu.org with esmtp (Exim 4.69) (envelope-from ) id 1QHKKK-00020Y-78 for submit@debbugs.gnu.org; Tue, 03 May 2011 14:28:05 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1QHKKD-0000Ef-Gk for submit@debbugs.gnu.org; Tue, 03 May 2011 14:27:59 -0400 Original-Received: from lists.gnu.org ([140.186.70.17]:50853) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QHKKD-0000Eb-FE for submit@debbugs.gnu.org; Tue, 03 May 2011 14:27:57 -0400 Original-Received: from eggs.gnu.org ([140.186.70.92]:57692) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QHKKA-0003Z5-CO for bug-gnu-emacs@gnu.org; Tue, 03 May 2011 14:27:57 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1QHKK5-0000DB-VK for bug-gnu-emacs@gnu.org; Tue, 03 May 2011 14:27:54 -0400 Original-Received: from smtp.cs.ucla.edu ([131.179.128.62]:41269) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1QHKK5-0000D2-Ed for bug-gnu-emacs@gnu.org; Tue, 03 May 2011 14:27:49 -0400 Original-Received: from localhost (localhost.localdomain [127.0.0.1]) by smtp.cs.ucla.edu (Postfix) with ESMTP id 6292639E80F2 for ; Tue, 3 May 2011 11:27:47 -0700 (PDT) X-Virus-Scanned: amavisd-new at smtp.cs.ucla.edu Original-Received: from smtp.cs.ucla.edu ([127.0.0.1]) by localhost (smtp.cs.ucla.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id dsQD+BvJAFh2 for ; Tue, 3 May 2011 11:27:42 -0700 (PDT) Original-Received: from [131.179.64.200] (Penguin.CS.UCLA.EDU [131.179.64.200]) by smtp.cs.ucla.edu (Postfix) with ESMTPSA id 0641A39E8083 for ; Tue, 3 May 2011 11:27:42 -0700 (PDT) User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.15) Gecko/20110421 Fedora/3.1.9-2.fc14 Thunderbird/3.1.9 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.11 Precedence: list Resent-Date: Tue, 03 May 2011 14:29:02 -0400 X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 3) X-Received-From: 140.186.70.43 X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.bugs:46168 Archived-At: 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 * 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 === 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 + + * NEWS: Integer overflow now yields floating-point instead of + wrapping around. + 2011-05-03 Leo Liu * 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 @@ * 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 + Arithmetic overflows now return float rather than wrapping around. + * data.c: Include . + (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 #include #include + +#include + #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);