Skip to content

Commit 81612e8

Browse files
mdickinsonmdickinson
committed
Merged revisions 77410,77421,77450-77451 via svnmerge from
svn+ssh://pythondev@svn.python.org/python/trunk ........ r77410 | mark.dickinson | 2010-01-10 13:06:31 +0000 (Sun, 10 Jan 2010) | 1 line Remove unused BCinfo fields and an unused macro. ........ r77421 | mark.dickinson | 2010-01-11 17:15:13 +0000 (Mon, 11 Jan 2010) | 1 line Change a variable type to avoid signed overflow; replace repeated '19999' constant by a define. ........ r77450 | mark.dickinson | 2010-01-12 22:23:56 +0000 (Tue, 12 Jan 2010) | 4 lines Issue python#7632: Fix a problem with _Py_dg_strtod that could lead to crashes in debug builds, for certain long numeric strings corresponding to subnormal values. ........ r77451 | mark.dickinson | 2010-01-12 22:55:51 +0000 (Tue, 12 Jan 2010) | 2 lines Issue python#7632: Fix a bug in dtoa.c that could lead to incorrectly-rounded results. ........
1 parent f845302 commit 81612e8

4 files changed

Lines changed: 167 additions & 36 deletions

File tree

‎Lib/test/floating_points.txt‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1019,3 +1019,10 @@
10191019
+43723334984997307E-26
10201020
+10182419849537963E-24
10211021
-93501703572661982E-26
1022+
1023+
# A value that caused a crash in debug builds for Python >= 2.7, 3.1
1024+
# See http://bugs.python.org/issue7632
1025+
2183167012312112312312.23538020374420446192e-370
1026+
1027+
# Another value designed to test a corner case of Python's strtod code.
1028+
0.99999999999999999999999999999999999999999e+23

‎Lib/test/test_float.py‎

Lines changed: 102 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,7 @@
77
from math import isinf, isnan, copysign, ldexp
88
import operator
99
import random, fractions
10+
import re
1011

1112
INF = float("inf")
1213
NAN = float("nan")
@@ -20,6 +21,74 @@
2021
test_dir = os.path.dirname(__file__) or os.curdir
2122
format_testfile = os.path.join(test_dir, 'formatfloat_testcases.txt')
2223

24+
finite_decimal_parser = re.compile(r""" # A numeric string consists of:
25+
(?P<sign>[-+])? # an optional sign, followed by
26+
(?=\d|\.\d) # a number with at least one digit
27+
(?P<int>\d*) # having a (possibly empty) integer part
28+
(?:\.(?P<frac>\d*))? # followed by an optional fractional part
29+
(?:E(?P<exp>[-+]?\d+))? # and an optional exponent
30+
\Z
31+
""", re.VERBOSE | re.IGNORECASE | re.UNICODE).match
32+
33+
# Pure Python version of correctly rounded string->float conversion.
34+
# Avoids any use of floating-point by returning the result as a hex string.
35+
def strtod(s, mant_dig=53, min_exp = -1021, max_exp = 1024):
36+
"""Convert a finite decimal string to a hex string representing an
37+
IEEE 754 binary64 float. Return 'inf' or '-inf' on overflow.
38+
This function makes no use of floating-point arithmetic at any
39+
stage."""
40+
41+
# parse string into a pair of integers 'a' and 'b' such that
42+
# abs(decimal value) = a/b, and a boolean 'negative'.
43+
m = finite_decimal_parser(s)
44+
if m is None:
45+
raise ValueError('invalid numeric string')
46+
fraction = m.group('frac') or ''
47+
intpart = int(m.group('int') + fraction)
48+
exp = int(m.group('exp') or '0') - len(fraction)
49+
negative = m.group('sign') == '-'
50+
a, b = intpart*10**max(exp, 0), 10**max(0, -exp)
51+
52+
# quick return for zeros
53+
if not a:
54+
return '-0x0.0p+0' if negative else '0x0.0p+0'
55+
56+
# compute exponent e for result; may be one too small in the case
57+
# that the rounded value of a/b lies in a different binade from a/b
58+
d = a.bit_length() - b.bit_length()
59+
d += (a >> d if d >= 0 else a << -d) >= b
60+
e = max(d, min_exp) - mant_dig
61+
62+
# approximate a/b by number of the form q * 2**e; adjust e if necessary
63+
a, b = a << max(-e, 0), b << max(e, 0)
64+
q, r = divmod(a, b)
65+
if 2*r > b or 2*r == b and q & 1:
66+
q += 1
67+
if q.bit_length() == mant_dig+1:
68+
q //= 2
69+
e += 1
70+
71+
# double check that (q, e) has the right form
72+
assert q.bit_length() <= mant_dig and e >= min_exp - mant_dig
73+
assert q.bit_length() == mant_dig or e == min_exp - mant_dig
74+
75+
# check for overflow and underflow
76+
if e + q.bit_length() > max_exp:
77+
return '-inf' if negative else 'inf'
78+
if not q:
79+
return '-0x0.0p+0' if negative else '0x0.0p+0'
80+
81+
# for hex representation, shift so # bits after point is a multiple of 4
82+
hexdigs = 1 + (mant_dig-2)//4
83+
shift = 3 - (mant_dig-2)%4
84+
q, e = q << shift, e - shift
85+
return '{}0x{:x}.{:0{}x}p{:+d}'.format(
86+
'-' if negative else '',
87+
q // 16**hexdigs,
88+
q % 16**hexdigs,
89+
hexdigs,
90+
e + 4*hexdigs)
91+
2392
class GeneralFloatCases(unittest.TestCase):
2493

2594
def test_float(self):
@@ -1263,6 +1332,38 @@ def roundtrip(x):
12631332
else:
12641333
self.identical(x, fromHex(toHex(x)))
12651334

1335+
class StrtodTestCase(unittest.TestCase):
1336+
def check_string(self, s):
1337+
expected = strtod(s)
1338+
try:
1339+
fs = float(s)
1340+
except OverflowError:
1341+
got = '-inf' if s[0] == '-' else 'inf'
1342+
else:
1343+
got = fs.hex()
1344+
self.assertEqual(expected, got,
1345+
"Incorrectly rounded str->float conversion for "
1346+
"{}: expected {}, got {}".format(s, expected, got))
1347+
1348+
@unittest.skipUnless(getattr(sys, 'float_repr_style', '') == 'short',
1349+
"applies only when using short float repr style")
1350+
def test_bug7632(self):
1351+
# check a few particular values that gave incorrectly rounded
1352+
# results with previous versions of dtoa.c
1353+
test_strings = [
1354+
'94393431193180696942841837085033647913224148539854e-358',
1355+
'12579816049008305546974391768996369464963024663104e-357',
1356+
'17489628565202117263145367596028389348922981857013e-357',
1357+
'18487398785991994634182916638542680759613590482273e-357',
1358+
'32002864200581033134358724675198044527469366773928e-358',
1359+
'73608278998966969345824653500136787876436005957953e-358',
1360+
'64774478836417299491718435234611299336288082136054e-358',
1361+
'13704940134126574534878641876947980878824688451169e-357',
1362+
'46697445774047060960624497964425416610480524760471e-358',
1363+
]
1364+
for s in test_strings:
1365+
self.check_string(s)
1366+
12661367

12671368
def test_main():
12681369
support.run_unittest(
@@ -1275,6 +1376,7 @@ def test_main():
12751376
RoundTestCase,
12761377
InfNanTest,
12771378
HexFloatTestCase,
1379+
StrtodTestCase,
12781380
)
12791381

12801382
if __name__ == '__main__':

‎Misc/NEWS‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,11 @@ What's New in Python 3.2 Alpha 1?
1212
Core and Builtins
1313
-----------------
1414

15+
- Issue #7632: Fix a crash in dtoa.c that occurred in debug builds
16+
when parsing certain long numeric strings corresponding to subnormal
17+
values. Also fix a number of bugs in dtoa.c that could lead to
18+
incorrectly rounded results when converting strings to floats.
19+
1520
- The __complex__ method is now looked up on the class of instances to make it
1621
consistent with other special methods.
1722

‎Python/dtoa.c‎

Lines changed: 53 additions & 36 deletions
Original file line numberDiff line numberDiff line change
@@ -200,10 +200,11 @@ typedef union { double d; ULong L[2]; } U;
200200
#define STRTOD_DIGLIM 40
201201
#endif
202202

203-
#ifdef DIGLIM_DEBUG
204-
extern int strtod_diglim;
205-
#else
206-
#define strtod_diglim STRTOD_DIGLIM
203+
/* maximum permitted exponent value for strtod; exponents larger than
204+
MAX_ABS_EXP in absolute value get truncated to +-MAX_ABS_EXP. MAX_ABS_EXP
205+
should fit into an int. */
206+
#ifndef MAX_ABS_EXP
207+
#define MAX_ABS_EXP 19999U
207208
#endif
208209

209210
/* The following definition of Storeinc is appropriate for MIPS processors.
@@ -269,8 +270,7 @@ extern int strtod_diglim;
269270
typedef struct BCinfo BCinfo;
270271
struct
271272
BCinfo {
272-
int dp0, dp1, dplen, dsign, e0, inexact;
273-
int nd, nd0, rounding, scale, uflchk;
273+
int dp0, dp1, dplen, dsign, e0, nd, nd0, scale;
274274
};
275275

276276
#define FFFFFFFF 0xffffffffUL
@@ -1130,6 +1130,26 @@ quorem(Bigint *b, Bigint *S)
11301130
return q;
11311131
}
11321132

1133+
/* version of ulp(x) that takes bc.scale into account.
1134+
1135+
Assuming that x is finite and nonzero, and x / 2^bc.scale is exactly
1136+
representable as a double, sulp(x) is equivalent to 2^bc.scale * ulp(x /
1137+
2^bc.scale). */
1138+
1139+
static double
1140+
sulp(U *x, BCinfo *bc)
1141+
{
1142+
U u;
1143+
1144+
if (bc->scale && 2*P + 1 - ((word0(x) & Exp_mask) >> Exp_shift) > 0) {
1145+
/* rv/2^bc->scale is subnormal */
1146+
word0(&u) = (P+2)*Exp_msk1;
1147+
word1(&u) = 0;
1148+
return u.d;
1149+
}
1150+
else
1151+
return ulp(x);
1152+
}
11331153

11341154
/* return 0 on success, -1 on failure */
11351155

@@ -1142,7 +1162,7 @@ bigcomp(U *rv, const char *s0, BCinfo *bc)
11421162
dsign = bc->dsign;
11431163
nd = bc->nd;
11441164
nd0 = bc->nd0;
1145-
p5 = nd + bc->e0 - 1;
1165+
p5 = nd + bc->e0;
11461166
speccase = 0;
11471167
if (rv->d == 0.) { /* special case: value near underflow-to-zero */
11481168
/* threshold was rounded to zero */
@@ -1227,17 +1247,21 @@ bigcomp(U *rv, const char *s0, BCinfo *bc)
12271247
}
12281248
}
12291249

1230-
/* Now b/d = exactly half-way between the two floating-point values */
1231-
/* on either side of the input string. Compute first digit of b/d. */
1232-
1233-
if (!(dig = quorem(b,d))) {
1234-
b = multadd(b, 10, 0); /* very unlikely */
1235-
if (b == NULL) {
1236-
Bfree(d);
1237-
return -1;
1238-
}
1239-
dig = quorem(b,d);
1250+
/* Now 10*b/d = exactly half-way between the two floating-point values
1251+
on either side of the input string. If b >= d, round down. */
1252+
if (cmp(b, d) >= 0) {
1253+
dd = -1;
1254+
goto ret;
12401255
}
1256+
1257+
/* Compute first digit of 10*b/d. */
1258+
b = multadd(b, 10, 0);
1259+
if (b == NULL) {
1260+
Bfree(d);
1261+
return -1;
1262+
}
1263+
dig = quorem(b, d);
1264+
assert(dig < 10);
12411265

12421266
/* Compare b/d with s0 */
12431267

@@ -1285,12 +1309,12 @@ bigcomp(U *rv, const char *s0, BCinfo *bc)
12851309
else if (dd < 0) {
12861310
if (!dsign) /* does not happen for round-near */
12871311
retlow1:
1288-
dval(rv) -= ulp(rv);
1312+
dval(rv) -= sulp(rv, bc);
12891313
}
12901314
else if (dd > 0) {
12911315
if (dsign) {
12921316
rethi1:
1293-
dval(rv) += ulp(rv);
1317+
dval(rv) += sulp(rv, bc);
12941318
}
12951319
}
12961320
else {
@@ -1312,13 +1336,12 @@ _Py_dg_strtod(const char *s00, char **se)
13121336
int esign, i, j, k, nd, nd0, nf, nz, nz0, sign;
13131337
const char *s, *s0, *s1;
13141338
double aadj, aadj1;
1315-
Long L;
13161339
U aadj2, adj, rv, rv0;
1317-
ULong y, z;
1340+
ULong y, z, L;
13181341
BCinfo bc;
13191342
Bigint *bb, *bb1, *bd, *bd0, *bs, *delta;
13201343

1321-
sign = nz0 = nz = bc.dplen = bc.uflchk = 0;
1344+
sign = nz0 = nz = bc.dplen = 0;
13221345
dval(&rv) = 0.;
13231346
for(s = s00;;s++) switch(*s) {
13241347
case '-':
@@ -1413,11 +1436,11 @@ _Py_dg_strtod(const char *s00, char **se)
14131436
s1 = s;
14141437
while((c = *++s) >= '0' && c <= '9')
14151438
L = 10*L + c - '0';
1416-
if (s - s1 > 8 || L > 19999)
1439+
if (s - s1 > 8 || L > MAX_ABS_EXP)
14171440
/* Avoid confusion from exponents
14181441
* so large that e might overflow.
14191442
*/
1420-
e = 19999; /* safe for 16 bit ints */
1443+
e = (int)MAX_ABS_EXP; /* safe for 16 bit ints */
14211444
else
14221445
e = (int)L;
14231446
if (esign)
@@ -1555,11 +1578,11 @@ _Py_dg_strtod(const char *s00, char **se)
15551578
/* Put digits into bd: true value = bd * 10^e */
15561579

15571580
bc.nd = nd;
1558-
bc.nd0 = nd0; /* Only needed if nd > strtod_diglim, but done here */
1581+
bc.nd0 = nd0; /* Only needed if nd > STRTOD_DIGLIM, but done here */
15591582
/* to silence an erroneous warning about bc.nd0 */
15601583
/* possibly not being initialized. */
1561-
if (nd > strtod_diglim) {
1562-
/* ASSERT(strtod_diglim >= 18); 18 == one more than the */
1584+
if (nd > STRTOD_DIGLIM) {
1585+
/* ASSERT(STRTOD_DIGLIM >= 18); 18 == one more than the */
15631586
/* minimum number of decimal digits to distinguish double values */
15641587
/* in IEEE arithmetic. */
15651588
i = j = 18;
@@ -1767,10 +1790,8 @@ _Py_dg_strtod(const char *s00, char **se)
17671790
/* accept rv */
17681791
break;
17691792
/* rv = smallest denormal */
1770-
if (bc.nd >nd) {
1771-
bc.uflchk = 1;
1793+
if (bc.nd >nd)
17721794
break;
1773-
}
17741795
goto undfl;
17751796
}
17761797
}
@@ -1786,10 +1807,8 @@ _Py_dg_strtod(const char *s00, char **se)
17861807
else {
17871808
dval(&rv) -= ulp(&rv);
17881809
if (!dval(&rv)) {
1789-
if (bc.nd >nd) {
1790-
bc.uflchk = 1;
1810+
if (bc.nd >nd)
17911811
break;
1792-
}
17931812
goto undfl;
17941813
}
17951814
}
@@ -1801,10 +1820,8 @@ _Py_dg_strtod(const char *s00, char **se)
18011820
aadj = aadj1 = 1.;
18021821
else if (word1(&rv) || word0(&rv) & Bndry_mask) {
18031822
if (word1(&rv) == Tiny1 && !word0(&rv)) {
1804-
if (bc.nd >nd) {
1805-
bc.uflchk = 1;
1823+
if (bc.nd >nd)
18061824
break;
1807-
}
18081825
goto undfl;
18091826
}
18101827
aadj = 1.;

0 commit comments

Comments
 (0)