* faster atof for common cases
(gets 3x speedup in go; got 40x in c)
* handle and test overflow
R=r
DELTA=217 (200 added, 0 deleted, 17 changed)
OCL=19399
CL=19422
diff --git a/src/lib/strconv/atof.go b/src/lib/strconv/atof.go
index 2a34e8d..c0bb1a6 100644
--- a/src/lib/strconv/atof.go
+++ b/src/lib/strconv/atof.go
@@ -12,7 +12,7 @@
import "strconv"
-// TODO(rsc): Better truncation handling, check for overflow in exponent.
+// TODO(rsc): Better truncation handling.
func StringToDecimal(s string) (neg bool, d *Decimal, trunc bool, ok bool) {
i := 0;
@@ -61,7 +61,11 @@
b.dp = b.nd;
}
- // optional exponent moves decimal point
+ // optional exponent moves decimal point.
+ // if we read a very large, very long number,
+ // just be sure to move the decimal point by
+ // a lot (say, 100000). it doesn't matter if it's
+ // not the exact number.
if i < len(s) && s[i] == 'e' {
i++;
if i >= len(s) {
@@ -79,7 +83,9 @@
}
e := 0;
for ; i < len(s) && '0' <= s[i] && s[i] <= '9'; i++ {
- e = e*10 + int(s[i]) - '0';
+ if e < 10000 {
+ e = e*10 + int(s[i]) - '0';
+ }
}
b.dp += e*esign;
}
@@ -104,10 +110,24 @@
return 0, false
}
- // TODO: check for obvious overflow
+ var exp int;
+ var mant uint64;
+
+ // Obvious overflow/underflow.
+ // These bounds are for 64-bit floats.
+ // Will have to change if we want to support 80-bit floats in the future.
+ if d.dp > 310 {
+ goto overflow;
+ }
+ if d.dp < -330 {
+ // zero
+ mant = 0;
+ exp = flt.bias;
+ goto out;
+ }
// Scale by powers of two until in range [0.5, 1.0)
- exp := 0;
+ exp = 0;
for d.dp > 0 {
var n int;
if d.dp >= len(powtab) {
@@ -141,10 +161,21 @@
exp += n;
}
- // TODO: overflow/underflow
+ if exp-flt.bias >= 1<<flt.expbits - 1 {
+ goto overflow;
+ }
// Extract 1+flt.mantbits bits.
- mant := d.Shift(int(1+flt.mantbits)).RoundedInteger();
+ mant = d.Shift(int(1+flt.mantbits)).RoundedInteger();
+
+ // Rounding might have added a bit; shift down.
+ if mant == 2<<flt.mantbits {
+ mant >>= 1;
+ exp++;
+ if exp-flt.bias >= 1<<flt.expbits - 1 {
+ goto overflow;
+ }
+ }
// Denormalized?
if mant&(1<<flt.mantbits) == 0 {
@@ -159,30 +190,135 @@
panicln("DecimalToFloatBits1", exp, flt.bias);
}
}
+ goto out;
+overflow:
+ // ±Inf
+ mant = 0;
+ exp = 1<<flt.expbits - 1 + flt.bias;
+ overflow = true;
+
+out:
// Assemble bits.
bits := mant & (uint64(1)<<flt.mantbits - 1);
bits |= uint64((exp-flt.bias)&(1<<flt.expbits - 1)) << flt.mantbits;
if neg {
bits |= 1<<flt.mantbits<<flt.expbits;
}
- return bits, false;
+ return bits, overflow;
+}
+
+// Compute exact floating-point integer from d's digits.
+// Caller is responsible for avoiding overflow.
+func DecimalToFloat64Int(neg bool, d *Decimal) float64 {
+ f := float64(0);
+ for i := 0; i < d.nd; i++ {
+ f = f*10 + float64(d.d[i] - '0');
+ }
+ if neg {
+ f = -f;
+ }
+ return f;
+}
+func DecimalToFloat32Int(neg bool, d *Decimal) float32 {
+ f := float32(0);
+ for i := 0; i < d.nd; i++ {
+ f = f*10 + float32(d.d[i] - '0');
+ }
+ if neg {
+ f = -f;
+ }
+ return f;
+}
+
+// Exact powers of 10.
+var float64pow10 = []float64 {
+ 1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9,
+ 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19,
+ 1e20, 1e21, 1e22
+}
+var float32pow10 = []float32 {
+ 1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10
}
// If possible to convert decimal d to 64-bit float f exactly,
-// entirely in floating-point math, do so, avoiding the machinery above.
+// entirely in floating-point math, do so, avoiding the expense of DecimalToFloatBits.
+// Three common cases:
+// value is exact integer
+// value is exact integer * exact power of ten
+// value is exact integer / exact power of ten
+// These all produce potentially inexact but correctly rounded answers.
func DecimalToFloat64(neg bool, d *Decimal, trunc bool) (f float64, ok bool) {
- // TODO: Fill in.
- return 0, false;
+ // Exact integers are <= 10^15.
+ // Exact powers of ten are <= 10^22.
+ if d.nd > 15 {
+ return;
+ }
+ switch {
+ case d.dp == d.nd: // int
+ f := DecimalToFloat64Int(neg, d);
+ return f, true;
+
+ case d.dp > d.nd && d.dp <= 15+22: // int * 10^k
+ f := DecimalToFloat64Int(neg, d);
+ k := d.dp - d.nd;
+ // If exponent is big but number of digits is not,
+ // can move a few zeros into the integer part.
+ if k > 22 {
+ f *= float64pow10[k-22];
+ k = 22;
+ }
+ return f*float64pow10[k], true;
+
+ case d.dp < d.nd && d.nd - d.dp <= 22: // int / 10^k
+ f := DecimalToFloat64Int(neg, d);
+ return f/float64pow10[d.nd - d.dp], true;
+ }
+ return;
}
// If possible to convert decimal d to 32-bit float f exactly,
// entirely in floating-point math, do so, avoiding the machinery above.
func DecimalToFloat32(neg bool, d *Decimal, trunc bool) (f float32, ok bool) {
- // TODO: Fill in.
- return 0, false;
+ // Exact integers are <= 10^7.
+ // Exact powers of ten are <= 10^10.
+ if d.nd > 7 {
+ return;
+ }
+ switch {
+ case d.dp == d.nd: // int
+ f := DecimalToFloat32Int(neg, d);
+ return f, true;
+
+ case d.dp > d.nd && d.dp <= 7+10: // int * 10^k
+ f := DecimalToFloat32Int(neg, d);
+ k := d.dp - d.nd;
+ // If exponent is big but number of digits is not,
+ // can move a few zeros into the integer part.
+ if k > 10 {
+ f *= float32pow10[k-10];
+ k = 10;
+ }
+ return f*float32pow10[k], true;
+
+ case d.dp < d.nd && d.nd - d.dp <= 10: // int / 10^k
+ f := DecimalToFloat32Int(neg, d);
+ return f/float32pow10[d.nd - d.dp], true;
+ }
+ return;
}
+// Convert string s to floating-point number.
+//
+// If s is well-formed and near a valid floating point number,
+// returns f, false, true, where f is the nearest floating point
+// number rounded using IEEE754 unbiased rounding.
+//
+// If s is not syntactically well-formed, returns ok == false.
+//
+// If s is syntactically well-formed but is more than 1/2 ULP
+// away from the largest floating point number of the given size,
+// returns f = ±Inf, overflow = true, ok = true.
export func atof64(s string) (f float64, overflow bool, ok bool) {
neg, d, trunc, ok1 := StringToDecimal(s);
if !ok1 {
diff --git a/src/lib/strconv/testatof.go b/src/lib/strconv/testatof.go
index df3396b..f17e630 100644
--- a/src/lib/strconv/testatof.go
+++ b/src/lib/strconv/testatof.go
@@ -24,6 +24,61 @@
Test{ "100000000000000016777216", "1.0000000000000003e+23" },
Test{ "-1", "-1" },
Test{ "-0", "0" },
+ Test{ "1e-20", "1e-20" },
+
+ // largest float64
+ Test{ "1.7976931348623157e308", "1.7976931348623157e+308" },
+ Test{ "-1.7976931348623157e308", "-1.7976931348623157e+308" },
+ // next float64 - too large
+ Test{ "1.7976931348623159e308", "+Inf" },
+ Test{ "-1.7976931348623159e308", "-Inf" },
+ // the border is ...158079
+ // borderline - okay
+ Test{ "1.7976931348623158e308", "1.7976931348623157e+308" },
+ Test{ "-1.7976931348623158e308", "-1.7976931348623157e+308" },
+ // borderline - too large
+ Test{ "1.797693134862315808e308", "+Inf" },
+ Test{ "-1.797693134862315808e308", "-Inf" },
+
+ // a little too large
+ Test{ "1e308", "1e+308" },
+ Test{ "2e308", "+Inf" },
+ Test{ "1e309", "+Inf" },
+
+ // way too large
+ Test{ "1e310", "+Inf" },
+ Test{ "-1e310", "-Inf" },
+ Test{ "1e400", "+Inf" },
+ Test{ "-1e400", "-Inf" },
+ Test{ "1e400000", "+Inf" },
+ Test{ "-1e400000", "-Inf" },
+
+ // denormalized
+ Test{ "1e-305", "1e-305" },
+ Test{ "1e-306", "1e-306" },
+ Test{ "1e-307", "1e-307" },
+ Test{ "1e-308", "1e-308" },
+ Test{ "1e-309", "1e-309" },
+ Test{ "1e-310", "1e-310" },
+ Test{ "1e-322", "1e-322" },
+ // smallest denormal
+ Test{ "5e-324", "5e-324" },
+ // too small
+ Test{ "4e-324", "0" },
+ // way too small
+ Test{ "1e-350", "0" },
+ Test{ "1e-400000", "0" },
+
+ // try to overflow exponent
+ Test{ "1e-4294967296", "0" },
+ Test{ "1e+4294967296", "+Inf" },
+ Test{ "1e-18446744073709551616", "0" },
+ Test{ "1e+18446744073709551616", "+Inf" },
+
+ // Parse errors
+ Test{ "1e", "error" },
+ Test{ "1e-", "error" },
+ Test{ ".e-1", "error" },
}
func main() {
@@ -31,8 +86,17 @@
for i := 0; i < len(tests); i++ {
t := &tests[i];
f, overflow, ok := strconv.atof64(t.in);
+ if !ok && t.out == "error" {
+ continue;
+ }
if !ok {
- panicln("test", t.in);
+ panicln("test:", t.in, "failed to parse");
+ }
+ if overflow && !sys.isInf(f, 0) {
+ panicln("overflow but not inf:", t.in, f);
+ }
+ if sys.isInf(f, 0) && !overflow {
+ panicln("inf but not overflow:", t.in, f);
}
s := strconv.ftoa64(f, 'g', -1);
if s != t.out {
