From ed628ca79beefd78bb901b7ab3712391927c6f3b Mon Sep 17 00:00:00 2001
From: Russ Cox <rsc@golang.org>
Date: Mon, 17 Nov 2008 17:22:51 -0800
Subject: [PATCH] * 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
---
 src/lib/strconv/atof.go     | 162 +++++++++++++++++++++++++++++++++---
 src/lib/strconv/testatof.go |  66 ++++++++++++++-
 2 files changed, 214 insertions(+), 14 deletions(-)

diff --git a/src/lib/strconv/atof.go b/src/lib/strconv/atof.go
index 2a34e8d079..c0bb1a61c9 100644
--- a/src/lib/strconv/atof.go
+++ b/src/lib/strconv/atof.go
@@ -12,7 +12,7 @@ package strconv
 
 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 @@ func StringToDecimal(s string) (neg bool, d *Decimal, trunc bool, ok bool) {
 		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 @@ func StringToDecimal(s string) (neg bool, d *Decimal, trunc bool, ok bool) {
 		}
 		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 @@ func DecimalToFloatBits(neg bool, d *Decimal, trunc bool, flt *FloatInfo) (b uin
 		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 @@ func DecimalToFloatBits(neg bool, d *Decimal, trunc bool, flt *FloatInfo) (b uin
 		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 @@ func DecimalToFloatBits(neg bool, d *Decimal, trunc bool, flt *FloatInfo) (b uin
 			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 df3396b8d5..f17e6307d5 100644
--- a/src/lib/strconv/testatof.go
+++ b/src/lib/strconv/testatof.go
@@ -24,6 +24,61 @@ var tests = []Test {
 	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 @@ func main() {
 	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 {
-- 
2.50.0