libgo: Update to weekly.2012-01-15.

From-SVN: r183539

6 files changed, 289 insertions, 31 deletions

diff --git a/libgo/go/strconv/extfloat.go b/libgo/go/strconv/extfloat.go
index 980052a7..64ab84f 100644
--- a/libgo/go/strconv/extfloat.go
+++ b/libgo/go/strconv/extfloat.go
@@ -191,6 +191,36 @@ func (f *extFloat) Assign(x float64) {
 	f.exp -= 64
 }
 
+// AssignComputeBounds sets f to the value of x and returns
+// lower, upper such that any number in the closed interval
+// [lower, upper] is converted back to x.
+func (f *extFloat) AssignComputeBounds(x float64) (lower, upper extFloat) {
+	// Special cases.
+	bits := math.Float64bits(x)
+	flt := &float64info
+	neg := bits>>(flt.expbits+flt.mantbits) != 0
+	expBiased := int(bits>>flt.mantbits) & (1<<flt.expbits - 1)
+	mant := bits & (uint64(1)<<flt.mantbits - 1)
+
+	if expBiased == 0 {
+		// denormalized.
+		f.mant = mant
+		f.exp = 1 + flt.bias - int(flt.mantbits)
+	} else {
+		f.mant = mant | 1<<flt.mantbits
+		f.exp = expBiased + flt.bias - int(flt.mantbits)
+	}
+	f.neg = neg
+
+	upper = extFloat{mant: 2*f.mant + 1, exp: f.exp - 1, neg: f.neg}
+	if mant != 0 || expBiased == 1 {
+		lower = extFloat{mant: 2*f.mant - 1, exp: f.exp - 1, neg: f.neg}
+	} else {
+		lower = extFloat{mant: 4*f.mant - 1, exp: f.exp - 2, neg: f.neg}
+	}
+	return
+}
+
 // Normalize normalizes f so that the highest bit of the mantissa is
 // set, and returns the number by which the mantissa was left-shifted.
 func (f *extFloat) Normalize() uint {
@@ -309,3 +339,163 @@ func (f *extFloat) AssignDecimal(d *decimal) (ok bool) {
 	}
 	return true
 }
+
+// Frexp10 is an analogue of math.Frexp for decimal powers. It scales
+// f by an approximate power of ten 10^-exp, and returns exp10, so
+// that f*10^exp10 has the same value as the old f, up to an ulp,
+// as well as the index of 10^-exp in the powersOfTen table.
+// The arguments expMin and expMax constrain the final value of the
+// binary exponent of f.
+func (f *extFloat) frexp10(expMin, expMax int) (exp10, index int) {
+	// it is illegal to call this function with a too restrictive exponent range.
+	if expMax-expMin <= 25 {
+		panic("strconv: invalid exponent range")
+	}
+	// Find power of ten such that x * 10^n has a binary exponent
+	// between expMin and expMax
+	approxExp10 := -(f.exp + 100) * 28 / 93 // log(10)/log(2) is close to 93/28.
+	i := (approxExp10 - firstPowerOfTen) / stepPowerOfTen
+Loop:
+	for {
+		exp := f.exp + powersOfTen[i].exp + 64
+		switch {
+		case exp < expMin:
+			i++
+		case exp > expMax:
+			i--
+		default:
+			break Loop
+		}
+	}
+	// Apply the desired decimal shift on f. It will have exponent
+	// in the desired range. This is multiplication by 10^-exp10.
+	f.Multiply(powersOfTen[i])
+
+	return -(firstPowerOfTen + i*stepPowerOfTen), i
+}
+
+// frexp10Many applies a common shift by a power of ten to a, b, c.
+func frexp10Many(expMin, expMax int, a, b, c *extFloat) (exp10 int) {
+	exp10, i := c.frexp10(expMin, expMax)
+	a.Multiply(powersOfTen[i])
+	b.Multiply(powersOfTen[i])
+	return
+}
+
+// ShortestDecimal stores in d the shortest decimal representation of f
+// which belongs to the open interval (lower, upper), where f is supposed
+// to lie. It returns false whenever the result is unsure. The implementation
+// uses the Grisu3 algorithm.
+func (f *extFloat) ShortestDecimal(d *decimal, lower, upper *extFloat) bool {
+	if f.mant == 0 {
+		d.d[0] = '0'
+		d.nd = 1
+		d.dp = 0
+		d.neg = f.neg
+	}
+	const minExp = -60
+	const maxExp = -32
+	upper.Normalize()
+	// Uniformize exponents.
+	if f.exp > upper.exp {
+		f.mant <<= uint(f.exp - upper.exp)
+		f.exp = upper.exp
+	}
+	if lower.exp > upper.exp {
+		lower.mant <<= uint(lower.exp - upper.exp)
+		lower.exp = upper.exp
+	}
+
+	exp10 := frexp10Many(minExp, maxExp, lower, f, upper)
+	// Take a safety margin due to rounding in frexp10Many, but we lose precision.
+	upper.mant++
+	lower.mant--
+
+	// The shortest representation of f is either rounded up or down, but
+	// in any case, it is a truncation of upper.
+	shift := uint(-upper.exp)
+	integer := uint32(upper.mant >> shift)
+	fraction := upper.mant - (uint64(integer) << shift)
+
+	// How far we can go down from upper until the result is wrong.
+	allowance := upper.mant - lower.mant
+	// How far we should go to get a very precise result.
+	targetDiff := upper.mant - f.mant
+
+	// Count integral digits: there are at most 10.
+	var integerDigits int
+	for i, pow := range uint64pow10 {
+		if uint64(integer) >= pow {
+			integerDigits = i + 1
+		}
+	}
+	for i := 0; i < integerDigits; i++ {
+		pow := uint64pow10[integerDigits-i-1]
+		digit := integer / uint32(pow)
+		d.d[i] = byte(digit + '0')
+		integer -= digit * uint32(pow)
+		// evaluate whether we should stop.
+		if currentDiff := uint64(integer)<<shift + fraction; currentDiff < allowance {
+			d.nd = i + 1
+			d.dp = integerDigits + exp10
+			d.neg = f.neg
+			// Sometimes allowance is so large the last digit might need to be
+			// decremented to get closer to f.
+			return adjustLastDigit(d, currentDiff, targetDiff, allowance, pow<<shift, 2)
+		}
+	}
+	d.nd = integerDigits
+	d.dp = d.nd + exp10
+	d.neg = f.neg
+
+	// Compute digits of the fractional part. At each step fraction does not
+	// overflow. The choice of minExp implies that fraction is less than 2^60.
+	var digit int
+	multiplier := uint64(1)
+	for {
+		fraction *= 10
+		multiplier *= 10
+		digit = int(fraction >> shift)
+		d.d[d.nd] = byte(digit + '0')
+		d.nd++
+		fraction -= uint64(digit) << shift
+		if fraction < allowance*multiplier {
+			// We are in the admissible range. Note that if allowance is about to
+			// overflow, that is, allowance > 2^64/10, the condition is automatically
+			// true due to the limited range of fraction.
+			return adjustLastDigit(d,
+				fraction, targetDiff*multiplier, allowance*multiplier,
+				1<<shift, multiplier*2)
+		}
+	}
+	return false
+}
+
+// adjustLastDigit modifies d = x-currentDiff*ε, to get closest to 
+// d = x-targetDiff*ε, without becoming smaller than x-maxDiff*ε.
+// It assumes that a decimal digit is worth ulpDecimal*ε, and that
+// all data is known with a error estimate of ulpBinary*ε.
+func adjustLastDigit(d *decimal, currentDiff, targetDiff, maxDiff, ulpDecimal, ulpBinary uint64) bool {
+	if ulpDecimal < 2*ulpBinary {
+		// Appromixation is too wide.
+		return false
+	}
+	for currentDiff+ulpDecimal/2+ulpBinary < targetDiff {
+		d.d[d.nd-1]--
+		currentDiff += ulpDecimal
+	}
+	if currentDiff+ulpDecimal <= targetDiff+ulpDecimal/2+ulpBinary {
+		// we have two choices, and don't know what to do.
+		return false
+	}
+	if currentDiff < ulpBinary || currentDiff > maxDiff-ulpBinary {
+		// we went too far
+		return false
+	}
+	if d.nd == 1 && d.d[0] == '0' {
+		// the number has actually reached zero.
+		d.nd = 0
+		d.dp = 0
+	}
+	return true
+}
diff --git a/libgo/go/strconv/fp_test.go b/libgo/go/strconv/fp_test.go
index 47877e3..171defa 100644
--- a/libgo/go/strconv/fp_test.go
+++ b/libgo/go/strconv/fp_test.go
@@ -26,8 +26,8 @@ func pow2(i int) float64 {
 	return pow2(i/2) * pow2(i-i/2)
 }
 
-// Wrapper around strconv.Atof64.  Handles dddddp+ddd (binary exponent)
-// itself, passes the rest on to strconv.Atof64.
+// Wrapper around strconv.ParseFloat(x, 64).  Handles dddddp+ddd (binary exponent)
+// itself, passes the rest on to strconv.ParseFloat.
 func myatof64(s string) (f float64, ok bool) {
 	a := strings.SplitN(s, "p", 2)
 	if len(a) == 2 {
@@ -70,8 +70,8 @@ func myatof64(s string) (f float64, ok bool) {
 	return f1, true
 }
 
-// Wrapper around strconv.Atof32.  Handles dddddp+ddd (binary exponent)
-// itself, passes the rest on to strconv.Atof32.
+// Wrapper around strconv.ParseFloat(x, 32).  Handles dddddp+ddd (binary exponent)
+// itself, passes the rest on to strconv.ParseFloat.
 func myatof32(s string) (f float32, ok bool) {
 	a := strings.SplitN(s, "p", 2)
 	if len(a) == 2 {
diff --git a/libgo/go/strconv/ftoa.go b/libgo/go/strconv/ftoa.go
index f4434fd..8eefbee 100644
--- a/libgo/go/strconv/ftoa.go
+++ b/libgo/go/strconv/ftoa.go
@@ -98,29 +98,43 @@ func genericFtoa(dst []byte, val float64, fmt byte, prec, bitSize int) []byte {
 		return fmtB(dst, neg, mant, exp, flt)
 	}
 
-	// Create exact decimal representation.
-	// The shift is exp - flt.mantbits because mant is a 1-bit integer
-	// followed by a flt.mantbits fraction, and we are treating it as
-	// a 1+flt.mantbits-bit integer.
-	d := new(decimal)
-	d.Assign(mant)
-	d.Shift(exp - int(flt.mantbits))
-
-	// Round appropriately.
 	// Negative precision means "only as much as needed to be exact."
-	shortest := false
-	if prec < 0 {
-		shortest = true
-		roundShortest(d, mant, exp, flt)
-		switch fmt {
-		case 'e', 'E':
-			prec = d.nd - 1
-		case 'f':
-			prec = max(d.nd-d.dp, 0)
-		case 'g', 'G':
-			prec = d.nd
+	shortest := prec < 0
+
+	d := new(decimal)
+	if shortest {
+		ok := false
+		if optimize && bitSize == 64 {
+			// Try Grisu3 algorithm.
+			f := new(extFloat)
+			lower, upper := f.AssignComputeBounds(val)
+			ok = f.ShortestDecimal(d, &lower, &upper)
+		}
+		if !ok {
+			// Create exact decimal representation.
+			// The shift is exp - flt.mantbits because mant is a 1-bit integer
+			// followed by a flt.mantbits fraction, and we are treating it as
+			// a 1+flt.mantbits-bit integer.
+			d.Assign(mant)
+			d.Shift(exp - int(flt.mantbits))
+			roundShortest(d, mant, exp, flt)
+		}
+		// Precision for shortest representation mode.
+		if prec < 0 {
+			switch fmt {
+			case 'e', 'E':
+				prec = d.nd - 1
+			case 'f':
+				prec = max(d.nd-d.dp, 0)
+			case 'g', 'G':
+				prec = d.nd
+			}
 		}
 	} else {
+		// Create exact decimal representation.
+		d.Assign(mant)
+		d.Shift(exp - int(flt.mantbits))
+		// Round appropriately.
 		switch fmt {
 		case 'e', 'E':
 			d.Round(prec + 1)
@@ -178,15 +192,26 @@ func roundShortest(d *decimal, mant uint64, exp int, flt *floatInfo) {
 		return
 	}
 
-	// TODO(rsc): Unless exp == minexp, if the number of digits in d
-	// is less than 17, it seems likely that it would be
-	// the shortest possible number already.  So maybe we can
-	// bail out without doing the extra multiprecision math here.
-
 	// Compute upper and lower such that any decimal number
 	// between upper and lower (possibly inclusive)
 	// will round to the original floating point number.
 
+	// We may see at once that the number is already shortest.
+	//
+	// Suppose d is not denormal, so that 2^exp <= d < 10^dp.
+	// The closest shorter number is at least 10^(dp-nd) away.
+	// The lower/upper bounds computed below are at distance
+	// at most 2^(exp-mantbits).
+	//
+	// So the number is already shortest if 10^(dp-nd) > 2^(exp-mantbits),
+	// or equivalently log2(10)*(dp-nd) > exp-mantbits.
+	// It is true if 332/100*(dp-nd) >= exp-mantbits (log2(10) > 3.32).
+	minexp := flt.bias + 1 // minimum possible exponent
+	if exp > minexp && 332*(d.dp-d.nd) >= 100*(exp-int(flt.mantbits)) {
+		// The number is already shortest.
+		return
+	}
+
 	// d = mant << (exp - mantbits)
 	// Next highest floating point number is mant+1 << exp-mantbits.
 	// Our upper bound is halfway inbetween, mant*2+1 << exp-mantbits-1.
@@ -200,7 +225,6 @@ func roundShortest(d *decimal, mant uint64, exp int, flt *floatInfo) {
 	// in which case the next lowest is mant*2-1 << exp-mantbits-1.
 	// Either way, call it mantlo << explo-mantbits.
 	// Our lower bound is halfway inbetween, mantlo*2+1 << explo-mantbits-1.
-	minexp := flt.bias + 1 // minimum possible exponent
 	var mantlo uint64
 	var explo int
 	if mant > 1<<flt.mantbits || exp == minexp {
@@ -241,7 +265,7 @@ func roundShortest(d *decimal, mant uint64, exp int, flt *floatInfo) {
 
 		// Okay to round up if upper has a different digit and
 		// either upper is inclusive or upper is bigger than the result of rounding up.
-		okup := m != u && (inclusive || i+1 < upper.nd)
+		okup := m != u && (inclusive || m+1 < u || i+1 < upper.nd)
 
 		// If it's okay to do either, then round to the nearest one.
 		// If it's okay to do only one, do it.
diff --git a/libgo/go/strconv/ftoa_test.go b/libgo/go/strconv/ftoa_test.go
index c69f8c2..ee7b7c4 100644
--- a/libgo/go/strconv/ftoa_test.go
+++ b/libgo/go/strconv/ftoa_test.go
@@ -6,6 +6,7 @@ package strconv_test
 
 import (
 	"math"
+	"math/rand"
 	. "strconv"
 	"testing"
 )
@@ -123,6 +124,10 @@ var ftoatests = []ftoaTest{
 	{2.2250738585072012e-308, 'g', -1, "2.2250738585072014e-308"},
 	// http://www.exploringbinary.com/php-hangs-on-numeric-value-2-2250738585072011e-308/
 	{2.2250738585072011e-308, 'g', -1, "2.225073858507201e-308"},
+
+	// Issue 2625.
+	{383260575764816448, 'f', 0, "383260575764816448"},
+	{383260575764816448, 'g', -1, "3.8326057576481645e+17"},
 }
 
 func TestFtoa(t *testing.T) {
@@ -149,6 +154,25 @@ func TestFtoa(t *testing.T) {
 	}
 }
 
+func TestFtoaRandom(t *testing.T) {
+	N := int(1e4)
+	if testing.Short() {
+		N = 100
+	}
+	t.Logf("testing %d random numbers with fast and slow FormatFloat", N)
+	for i := 0; i < N; i++ {
+		bits := uint64(rand.Uint32())<<32 | uint64(rand.Uint32())
+		x := math.Float64frombits(bits)
+		shortFast := FormatFloat(x, 'g', -1, 64)
+		SetOptimize(false)
+		shortSlow := FormatFloat(x, 'g', -1, 64)
+		SetOptimize(true)
+		if shortSlow != shortFast {
+			t.Errorf("%b printed as %s, want %s", x, shortFast, shortSlow)
+		}
+	}
+}
+
 /* This test relies on escape analysis which gccgo does not yet do.
 
 func TestAppendFloatDoesntAllocate(t *testing.T) {
@@ -188,6 +212,12 @@ func BenchmarkFormatFloatExp(b *testing.B) {
 	}
 }
 
+func BenchmarkFormatFloatNegExp(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		FormatFloat(-5.11e-95, 'g', -1, 64)
+	}
+}
+
 func BenchmarkFormatFloatBig(b *testing.B) {
 	for i := 0; i < b.N; i++ {
 		FormatFloat(123456789123456789123456789, 'g', -1, 64)
@@ -215,6 +245,13 @@ func BenchmarkAppendFloatExp(b *testing.B) {
 	}
 }
 
+func BenchmarkAppendFloatNegExp(b *testing.B) {
+	dst := make([]byte, 0, 30)
+	for i := 0; i < b.N; i++ {
+		AppendFloat(dst, -5.11e-95, 'g', -1, 64)
+	}
+}
+
 func BenchmarkAppendFloatBig(b *testing.B) {
 	dst := make([]byte, 0, 30)
 	for i := 0; i < b.N; i++ {
diff --git a/libgo/go/strconv/quote.go b/libgo/go/strconv/quote.go
index edba629..61dbcae 100644
--- a/libgo/go/strconv/quote.go
+++ b/libgo/go/strconv/quote.go
@@ -260,6 +260,7 @@ func UnquoteChar(s string, quote byte) (value rune, multibyte bool, tail string,
 		for j := 0; j < 2; j++ { // one digit already; two more
 			x := rune(s[j]) - '0'
 			if x < 0 || x > 7 {
+				err = ErrSyntax
 				return
 			}
 			v = (v << 3) | x
diff --git a/libgo/go/strconv/quote_test.go b/libgo/go/strconv/quote_test.go
index 419943d..3f544c4 100644
--- a/libgo/go/strconv/quote_test.go
+++ b/libgo/go/strconv/quote_test.go
@@ -191,7 +191,13 @@ var misquoted = []string{
 	`"'`,
 	`b"`,
 	`"\"`,
+	`"\9"`,
+	`"\19"`,
+	`"\129"`,
 	`'\'`,
+	`'\9'`,
+	`'\19'`,
+	`'\129'`,
 	`'ab'`,
 	`"\x1!"`,
 	`"\U12345678"`,