diff options
author | Russ Cox <rsc@golang.org> | 2014-09-08 00:08:51 -0400 |
---|---|---|
committer | Russ Cox <rsc@golang.org> | 2014-09-08 00:08:51 -0400 |
commit | 8528da672cc093d4dd06732819abc1f7b6b5a46e (patch) | |
tree | 334be80d4a4c85b77db6f6fdb67cbf0528cba5f5 /src/strconv | |
parent | 73bcb69f272cbf34ddcc9daa56427a8683b5a95d (diff) | |
download | go-8528da672cc093d4dd06732819abc1f7b6b5a46e.tar.gz |
build: move package sources from src/pkg to src
Preparation was in CL 134570043.
This CL contains only the effect of 'hg mv src/pkg/* src'.
For more about the move, see golang.org/s/go14nopkg.
Diffstat (limited to 'src/strconv')
-rw-r--r-- | src/strconv/atob.go | 35 | ||||
-rw-r--r-- | src/strconv/atob_test.go | 91 | ||||
-rw-r--r-- | src/strconv/atof.go | 540 | ||||
-rw-r--r-- | src/strconv/atof_test.go | 430 | ||||
-rw-r--r-- | src/strconv/atoi.go | 198 | ||||
-rw-r--r-- | src/strconv/atoi_test.go | 326 | ||||
-rw-r--r-- | src/strconv/decimal.go | 378 | ||||
-rw-r--r-- | src/strconv/decimal_test.go | 127 | ||||
-rw-r--r-- | src/strconv/extfloat.go | 668 | ||||
-rw-r--r-- | src/strconv/fp_test.go | 144 | ||||
-rw-r--r-- | src/strconv/ftoa.go | 475 | ||||
-rw-r--r-- | src/strconv/ftoa_test.go | 240 | ||||
-rw-r--r-- | src/strconv/internal_test.go | 19 | ||||
-rw-r--r-- | src/strconv/isprint.go | 624 | ||||
-rw-r--r-- | src/strconv/itoa.go | 131 | ||||
-rw-r--r-- | src/strconv/itoa_test.go | 160 | ||||
-rw-r--r-- | src/strconv/makeisprint.go | 187 | ||||
-rw-r--r-- | src/strconv/quote.go | 455 | ||||
-rw-r--r-- | src/strconv/quote_example_test.go | 35 | ||||
-rw-r--r-- | src/strconv/quote_test.go | 266 | ||||
-rw-r--r-- | src/strconv/strconv_test.go | 57 | ||||
-rw-r--r-- | src/strconv/testdata/testfp.txt | 181 |
22 files changed, 5767 insertions, 0 deletions
diff --git a/src/strconv/atob.go b/src/strconv/atob.go new file mode 100644 index 000000000..d0cb09721 --- /dev/null +++ b/src/strconv/atob.go @@ -0,0 +1,35 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package strconv + +// ParseBool returns the boolean value represented by the string. +// It accepts 1, t, T, TRUE, true, True, 0, f, F, FALSE, false, False. +// Any other value returns an error. +func ParseBool(str string) (value bool, err error) { + switch str { + case "1", "t", "T", "true", "TRUE", "True": + return true, nil + case "0", "f", "F", "false", "FALSE", "False": + return false, nil + } + return false, syntaxError("ParseBool", str) +} + +// FormatBool returns "true" or "false" according to the value of b +func FormatBool(b bool) string { + if b { + return "true" + } + return "false" +} + +// AppendBool appends "true" or "false", according to the value of b, +// to dst and returns the extended buffer. +func AppendBool(dst []byte, b bool) []byte { + if b { + return append(dst, "true"...) + } + return append(dst, "false"...) +} diff --git a/src/strconv/atob_test.go b/src/strconv/atob_test.go new file mode 100644 index 000000000..28f469f58 --- /dev/null +++ b/src/strconv/atob_test.go @@ -0,0 +1,91 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package strconv_test + +import ( + "bytes" + . "strconv" + "testing" +) + +type atobTest struct { + in string + out bool + err error +} + +var atobtests = []atobTest{ + {"", false, ErrSyntax}, + {"asdf", false, ErrSyntax}, + {"0", false, nil}, + {"f", false, nil}, + {"F", false, nil}, + {"FALSE", false, nil}, + {"false", false, nil}, + {"False", false, nil}, + {"1", true, nil}, + {"t", true, nil}, + {"T", true, nil}, + {"TRUE", true, nil}, + {"true", true, nil}, + {"True", true, nil}, +} + +func TestParseBool(t *testing.T) { + for _, test := range atobtests { + b, e := ParseBool(test.in) + if test.err != nil { + // expect an error + if e == nil { + t.Errorf("%s: expected %s but got nil", test.in, test.err) + } else { + // NumError assertion must succeed; it's the only thing we return. + if test.err != e.(*NumError).Err { + t.Errorf("%s: expected %s but got %s", test.in, test.err, e) + } + } + } else { + if e != nil { + t.Errorf("%s: expected no error but got %s", test.in, e) + } + if b != test.out { + t.Errorf("%s: expected %t but got %t", test.in, test.out, b) + } + } + } +} + +var boolString = map[bool]string{ + true: "true", + false: "false", +} + +func TestFormatBool(t *testing.T) { + for b, s := range boolString { + if f := FormatBool(b); f != s { + t.Errorf(`FormatBool(%v): expected %q but got %q`, b, s, f) + } + } +} + +type appendBoolTest struct { + b bool + in []byte + out []byte +} + +var appendBoolTests = []appendBoolTest{ + {true, []byte("foo "), []byte("foo true")}, + {false, []byte("foo "), []byte("foo false")}, +} + +func TestAppendBool(t *testing.T) { + for _, test := range appendBoolTests { + b := AppendBool(test.in, test.b) + if !bytes.Equal(b, test.out) { + t.Errorf("AppendBool(%q, %v): expected %q but got %q", test.in, test.b, test.out, b) + } + } +} diff --git a/src/strconv/atof.go b/src/strconv/atof.go new file mode 100644 index 000000000..286206481 --- /dev/null +++ b/src/strconv/atof.go @@ -0,0 +1,540 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Package strconv implements conversions to and from string representations +// of basic data types. +package strconv + +// decimal to binary floating point conversion. +// Algorithm: +// 1) Store input in multiprecision decimal. +// 2) Multiply/divide decimal by powers of two until in range [0.5, 1) +// 3) Multiply by 2^precision and round to get mantissa. + +import "math" + +var optimize = true // can change for testing + +func equalIgnoreCase(s1, s2 string) bool { + if len(s1) != len(s2) { + return false + } + for i := 0; i < len(s1); i++ { + c1 := s1[i] + if 'A' <= c1 && c1 <= 'Z' { + c1 += 'a' - 'A' + } + c2 := s2[i] + if 'A' <= c2 && c2 <= 'Z' { + c2 += 'a' - 'A' + } + if c1 != c2 { + return false + } + } + return true +} + +func special(s string) (f float64, ok bool) { + if len(s) == 0 { + return + } + switch s[0] { + default: + return + case '+': + if equalIgnoreCase(s, "+inf") || equalIgnoreCase(s, "+infinity") { + return math.Inf(1), true + } + case '-': + if equalIgnoreCase(s, "-inf") || equalIgnoreCase(s, "-infinity") { + return math.Inf(-1), true + } + case 'n', 'N': + if equalIgnoreCase(s, "nan") { + return math.NaN(), true + } + case 'i', 'I': + if equalIgnoreCase(s, "inf") || equalIgnoreCase(s, "infinity") { + return math.Inf(1), true + } + } + return +} + +func (b *decimal) set(s string) (ok bool) { + i := 0 + b.neg = false + b.trunc = false + + // optional sign + if i >= len(s) { + return + } + switch { + case s[i] == '+': + i++ + case s[i] == '-': + b.neg = true + i++ + } + + // digits + sawdot := false + sawdigits := false + for ; i < len(s); i++ { + switch { + case s[i] == '.': + if sawdot { + return + } + sawdot = true + b.dp = b.nd + continue + + case '0' <= s[i] && s[i] <= '9': + sawdigits = true + if s[i] == '0' && b.nd == 0 { // ignore leading zeros + b.dp-- + continue + } + if b.nd < len(b.d) { + b.d[b.nd] = s[i] + b.nd++ + } else if s[i] != '0' { + b.trunc = true + } + continue + } + break + } + if !sawdigits { + return + } + if !sawdot { + b.dp = b.nd + } + + // 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' || s[i] == 'E') { + i++ + if i >= len(s) { + return + } + esign := 1 + if s[i] == '+' { + i++ + } else if s[i] == '-' { + i++ + esign = -1 + } + if i >= len(s) || s[i] < '0' || s[i] > '9' { + return + } + e := 0 + for ; i < len(s) && '0' <= s[i] && s[i] <= '9'; i++ { + if e < 10000 { + e = e*10 + int(s[i]) - '0' + } + } + b.dp += e * esign + } + + if i != len(s) { + return + } + + ok = true + return +} + +// readFloat reads a decimal mantissa and exponent from a float +// string representation. It sets ok to false if the number could +// not fit return types or is invalid. +func readFloat(s string) (mantissa uint64, exp int, neg, trunc, ok bool) { + const uint64digits = 19 + i := 0 + + // optional sign + if i >= len(s) { + return + } + switch { + case s[i] == '+': + i++ + case s[i] == '-': + neg = true + i++ + } + + // digits + sawdot := false + sawdigits := false + nd := 0 + ndMant := 0 + dp := 0 + for ; i < len(s); i++ { + switch c := s[i]; true { + case c == '.': + if sawdot { + return + } + sawdot = true + dp = nd + continue + + case '0' <= c && c <= '9': + sawdigits = true + if c == '0' && nd == 0 { // ignore leading zeros + dp-- + continue + } + nd++ + if ndMant < uint64digits { + mantissa *= 10 + mantissa += uint64(c - '0') + ndMant++ + } else if s[i] != '0' { + trunc = true + } + continue + } + break + } + if !sawdigits { + return + } + if !sawdot { + dp = nd + } + + // 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' || s[i] == 'E') { + i++ + if i >= len(s) { + return + } + esign := 1 + if s[i] == '+' { + i++ + } else if s[i] == '-' { + i++ + esign = -1 + } + if i >= len(s) || s[i] < '0' || s[i] > '9' { + return + } + e := 0 + for ; i < len(s) && '0' <= s[i] && s[i] <= '9'; i++ { + if e < 10000 { + e = e*10 + int(s[i]) - '0' + } + } + dp += e * esign + } + + if i != len(s) { + return + } + + exp = dp - ndMant + ok = true + return + +} + +// decimal power of ten to binary power of two. +var powtab = []int{1, 3, 6, 9, 13, 16, 19, 23, 26} + +func (d *decimal) floatBits(flt *floatInfo) (b uint64, overflow bool) { + var exp int + var mant uint64 + + // Zero is always a special case. + if d.nd == 0 { + mant = 0 + exp = flt.bias + goto out + } + + // 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 + for d.dp > 0 { + var n int + if d.dp >= len(powtab) { + n = 27 + } else { + n = powtab[d.dp] + } + d.Shift(-n) + exp += n + } + for d.dp < 0 || d.dp == 0 && d.d[0] < '5' { + var n int + if -d.dp >= len(powtab) { + n = 27 + } else { + n = powtab[-d.dp] + } + d.Shift(n) + exp -= n + } + + // Our range is [0.5,1) but floating point range is [1,2). + exp-- + + // Minimum representable exponent is flt.bias+1. + // If the exponent is smaller, move it up and + // adjust d accordingly. + if exp < flt.bias+1 { + n := flt.bias + 1 - exp + d.Shift(-n) + exp += n + } + + if exp-flt.bias >= 1<<flt.expbits-1 { + goto overflow + } + + // Extract 1+flt.mantbits bits. + d.Shift(int(1 + flt.mantbits)) + mant = d.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 { + 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 d.neg { + bits |= 1 << flt.mantbits << flt.expbits + } + return bits, overflow +} + +// 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 representation to 64-bit float f exactly, +// 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 atof64exact(mantissa uint64, exp int, neg bool) (f float64, ok bool) { + if mantissa>>float64info.mantbits != 0 { + return + } + f = float64(mantissa) + if neg { + f = -f + } + switch { + case exp == 0: + // an integer. + return f, true + // Exact integers are <= 10^15. + // Exact powers of ten are <= 10^22. + case exp > 0 && exp <= 15+22: // int * 10^k + // If exponent is big but number of digits is not, + // can move a few zeros into the integer part. + if exp > 22 { + f *= float64pow10[exp-22] + exp = 22 + } + if f > 1e15 || f < -1e15 { + // the exponent was really too large. + return + } + return f * float64pow10[exp], true + case exp < 0 && exp >= -22: // int / 10^k + return f / float64pow10[-exp], true + } + return +} + +// If possible to compute mantissa*10^exp to 32-bit float f exactly, +// entirely in floating-point math, do so, avoiding the machinery above. +func atof32exact(mantissa uint64, exp int, neg bool) (f float32, ok bool) { + if mantissa>>float32info.mantbits != 0 { + return + } + f = float32(mantissa) + if neg { + f = -f + } + switch { + case exp == 0: + return f, true + // Exact integers are <= 10^7. + // Exact powers of ten are <= 10^10. + case exp > 0 && exp <= 7+10: // int * 10^k + // If exponent is big but number of digits is not, + // can move a few zeros into the integer part. + if exp > 10 { + f *= float32pow10[exp-10] + exp = 10 + } + if f > 1e7 || f < -1e7 { + // the exponent was really too large. + return + } + return f * float32pow10[exp], true + case exp < 0 && exp >= -10: // int / 10^k + return f / float32pow10[-exp], true + } + return +} + +const fnParseFloat = "ParseFloat" + +func atof32(s string) (f float32, err error) { + if val, ok := special(s); ok { + return float32(val), nil + } + + if optimize { + // Parse mantissa and exponent. + mantissa, exp, neg, trunc, ok := readFloat(s) + if ok { + // Try pure floating-point arithmetic conversion. + if !trunc { + if f, ok := atof32exact(mantissa, exp, neg); ok { + return f, nil + } + } + // Try another fast path. + ext := new(extFloat) + if ok := ext.AssignDecimal(mantissa, exp, neg, trunc, &float32info); ok { + b, ovf := ext.floatBits(&float32info) + f = math.Float32frombits(uint32(b)) + if ovf { + err = rangeError(fnParseFloat, s) + } + return f, err + } + } + } + var d decimal + if !d.set(s) { + return 0, syntaxError(fnParseFloat, s) + } + b, ovf := d.floatBits(&float32info) + f = math.Float32frombits(uint32(b)) + if ovf { + err = rangeError(fnParseFloat, s) + } + return f, err +} + +func atof64(s string) (f float64, err error) { + if val, ok := special(s); ok { + return val, nil + } + + if optimize { + // Parse mantissa and exponent. + mantissa, exp, neg, trunc, ok := readFloat(s) + if ok { + // Try pure floating-point arithmetic conversion. + if !trunc { + if f, ok := atof64exact(mantissa, exp, neg); ok { + return f, nil + } + } + // Try another fast path. + ext := new(extFloat) + if ok := ext.AssignDecimal(mantissa, exp, neg, trunc, &float64info); ok { + b, ovf := ext.floatBits(&float64info) + f = math.Float64frombits(b) + if ovf { + err = rangeError(fnParseFloat, s) + } + return f, err + } + } + } + var d decimal + if !d.set(s) { + return 0, syntaxError(fnParseFloat, s) + } + b, ovf := d.floatBits(&float64info) + f = math.Float64frombits(b) + if ovf { + err = rangeError(fnParseFloat, s) + } + return f, err +} + +// ParseFloat converts the string s to a floating-point number +// with the precision specified by bitSize: 32 for float32, or 64 for float64. +// When bitSize=32, the result still has type float64, but it will be +// convertible to float32 without changing its value. +// +// If s is well-formed and near a valid floating point number, +// ParseFloat returns the nearest floating point number rounded +// using IEEE754 unbiased rounding. +// +// The errors that ParseFloat returns have concrete type *NumError +// and include err.Num = s. +// +// If s is not syntactically well-formed, ParseFloat returns err.Err = ErrSyntax. +// +// If s is syntactically well-formed but is more than 1/2 ULP +// away from the largest floating point number of the given size, +// ParseFloat returns f = ±Inf, err.Err = ErrRange. +func ParseFloat(s string, bitSize int) (f float64, err error) { + if bitSize == 32 { + f1, err1 := atof32(s) + return float64(f1), err1 + } + f1, err1 := atof64(s) + return f1, err1 +} diff --git a/src/strconv/atof_test.go b/src/strconv/atof_test.go new file mode 100644 index 000000000..ba4933218 --- /dev/null +++ b/src/strconv/atof_test.go @@ -0,0 +1,430 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package strconv_test + +import ( + "math" + "math/rand" + "reflect" + . "strconv" + "strings" + "testing" + "time" +) + +type atofTest struct { + in string + out string + err error +} + +var atoftests = []atofTest{ + {"", "0", ErrSyntax}, + {"1", "1", nil}, + {"+1", "1", nil}, + {"1x", "0", ErrSyntax}, + {"1.1.", "0", ErrSyntax}, + {"1e23", "1e+23", nil}, + {"1E23", "1e+23", nil}, + {"100000000000000000000000", "1e+23", nil}, + {"1e-100", "1e-100", nil}, + {"123456700", "1.234567e+08", nil}, + {"99999999999999974834176", "9.999999999999997e+22", nil}, + {"100000000000000000000001", "1.0000000000000001e+23", nil}, + {"100000000000000008388608", "1.0000000000000001e+23", nil}, + {"100000000000000016777215", "1.0000000000000001e+23", nil}, + {"100000000000000016777216", "1.0000000000000003e+23", nil}, + {"-1", "-1", nil}, + {"-0.1", "-0.1", nil}, + {"-0", "-0", nil}, + {"1e-20", "1e-20", nil}, + {"625e-3", "0.625", nil}, + + // NaNs + {"nan", "NaN", nil}, + {"NaN", "NaN", nil}, + {"NAN", "NaN", nil}, + + // Infs + {"inf", "+Inf", nil}, + {"-Inf", "-Inf", nil}, + {"+INF", "+Inf", nil}, + {"-Infinity", "-Inf", nil}, + {"+INFINITY", "+Inf", nil}, + {"Infinity", "+Inf", nil}, + + // largest float64 + {"1.7976931348623157e308", "1.7976931348623157e+308", nil}, + {"-1.7976931348623157e308", "-1.7976931348623157e+308", nil}, + // next float64 - too large + {"1.7976931348623159e308", "+Inf", ErrRange}, + {"-1.7976931348623159e308", "-Inf", ErrRange}, + // the border is ...158079 + // borderline - okay + {"1.7976931348623158e308", "1.7976931348623157e+308", nil}, + {"-1.7976931348623158e308", "-1.7976931348623157e+308", nil}, + // borderline - too large + {"1.797693134862315808e308", "+Inf", ErrRange}, + {"-1.797693134862315808e308", "-Inf", ErrRange}, + + // a little too large + {"1e308", "1e+308", nil}, + {"2e308", "+Inf", ErrRange}, + {"1e309", "+Inf", ErrRange}, + + // way too large + {"1e310", "+Inf", ErrRange}, + {"-1e310", "-Inf", ErrRange}, + {"1e400", "+Inf", ErrRange}, + {"-1e400", "-Inf", ErrRange}, + {"1e400000", "+Inf", ErrRange}, + {"-1e400000", "-Inf", ErrRange}, + + // denormalized + {"1e-305", "1e-305", nil}, + {"1e-306", "1e-306", nil}, + {"1e-307", "1e-307", nil}, + {"1e-308", "1e-308", nil}, + {"1e-309", "1e-309", nil}, + {"1e-310", "1e-310", nil}, + {"1e-322", "1e-322", nil}, + // smallest denormal + {"5e-324", "5e-324", nil}, + {"4e-324", "5e-324", nil}, + {"3e-324", "5e-324", nil}, + // too small + {"2e-324", "0", nil}, + // way too small + {"1e-350", "0", nil}, + {"1e-400000", "0", nil}, + + // try to overflow exponent + {"1e-4294967296", "0", nil}, + {"1e+4294967296", "+Inf", ErrRange}, + {"1e-18446744073709551616", "0", nil}, + {"1e+18446744073709551616", "+Inf", ErrRange}, + + // Parse errors + {"1e", "0", ErrSyntax}, + {"1e-", "0", ErrSyntax}, + {".e-1", "0", ErrSyntax}, + {"1\x00.2", "0", ErrSyntax}, + + // http://www.exploringbinary.com/java-hangs-when-converting-2-2250738585072012e-308/ + {"2.2250738585072012e-308", "2.2250738585072014e-308", nil}, + // http://www.exploringbinary.com/php-hangs-on-numeric-value-2-2250738585072011e-308/ + {"2.2250738585072011e-308", "2.225073858507201e-308", nil}, + + // A very large number (initially wrongly parsed by the fast algorithm). + {"4.630813248087435e+307", "4.630813248087435e+307", nil}, + + // A different kind of very large number. + {"22.222222222222222", "22.22222222222222", nil}, + {"2." + strings.Repeat("2", 4000) + "e+1", "22.22222222222222", nil}, + + // Exactly halfway between 1 and math.Nextafter(1, 2). + // Round to even (down). + {"1.00000000000000011102230246251565404236316680908203125", "1", nil}, + // Slightly lower; still round down. + {"1.00000000000000011102230246251565404236316680908203124", "1", nil}, + // Slightly higher; round up. + {"1.00000000000000011102230246251565404236316680908203126", "1.0000000000000002", nil}, + // Slightly higher, but you have to read all the way to the end. + {"1.00000000000000011102230246251565404236316680908203125" + strings.Repeat("0", 10000) + "1", "1.0000000000000002", nil}, +} + +var atof32tests = []atofTest{ + // Exactly halfway between 1 and the next float32. + // Round to even (down). + {"1.000000059604644775390625", "1", nil}, + // Slightly lower. + {"1.000000059604644775390624", "1", nil}, + // Slightly higher. + {"1.000000059604644775390626", "1.0000001", nil}, + // Slightly higher, but you have to read all the way to the end. + {"1.000000059604644775390625" + strings.Repeat("0", 10000) + "1", "1.0000001", nil}, + + // largest float32: (1<<128) * (1 - 2^-24) + {"340282346638528859811704183484516925440", "3.4028235e+38", nil}, + {"-340282346638528859811704183484516925440", "-3.4028235e+38", nil}, + // next float32 - too large + {"3.4028236e38", "+Inf", ErrRange}, + {"-3.4028236e38", "-Inf", ErrRange}, + // the border is 3.40282356779...e+38 + // borderline - okay + {"3.402823567e38", "3.4028235e+38", nil}, + {"-3.402823567e38", "-3.4028235e+38", nil}, + // borderline - too large + {"3.4028235678e38", "+Inf", ErrRange}, + {"-3.4028235678e38", "-Inf", ErrRange}, + + // Denormals: less than 2^-126 + {"1e-38", "1e-38", nil}, + {"1e-39", "1e-39", nil}, + {"1e-40", "1e-40", nil}, + {"1e-41", "1e-41", nil}, + {"1e-42", "1e-42", nil}, + {"1e-43", "1e-43", nil}, + {"1e-44", "1e-44", nil}, + {"6e-45", "6e-45", nil}, // 4p-149 = 5.6e-45 + {"5e-45", "6e-45", nil}, + // Smallest denormal + {"1e-45", "1e-45", nil}, // 1p-149 = 1.4e-45 + {"2e-45", "1e-45", nil}, + + // 2^92 = 8388608p+69 = 4951760157141521099596496896 (4.9517602e27) + // is an exact power of two that needs 8 decimal digits to be correctly + // parsed back. + // The float32 before is 16777215p+68 = 4.95175986e+27 + // The halfway is 4.951760009. A bad algorithm that thinks the previous + // float32 is 8388607p+69 will shorten incorrectly to 4.95176e+27. + {"4951760157141521099596496896", "4.9517602e+27", nil}, +} + +type atofSimpleTest struct { + x float64 + s string +} + +var ( + atofRandomTests []atofSimpleTest + benchmarksRandomBits [1024]string + benchmarksRandomNormal [1024]string +) + +func init() { + // The atof routines return NumErrors wrapping + // the error and the string. Convert the table above. + for i := range atoftests { + test := &atoftests[i] + if test.err != nil { + test.err = &NumError{"ParseFloat", test.in, test.err} + } + } + for i := range atof32tests { + test := &atof32tests[i] + if test.err != nil { + test.err = &NumError{"ParseFloat", test.in, test.err} + } + } + + // Generate random inputs for tests and benchmarks + rand.Seed(time.Now().UnixNano()) + if testing.Short() { + atofRandomTests = make([]atofSimpleTest, 100) + } else { + atofRandomTests = make([]atofSimpleTest, 10000) + } + for i := range atofRandomTests { + n := uint64(rand.Uint32())<<32 | uint64(rand.Uint32()) + x := math.Float64frombits(n) + s := FormatFloat(x, 'g', -1, 64) + atofRandomTests[i] = atofSimpleTest{x, s} + } + + for i := range benchmarksRandomBits { + bits := uint64(rand.Uint32())<<32 | uint64(rand.Uint32()) + x := math.Float64frombits(bits) + benchmarksRandomBits[i] = FormatFloat(x, 'g', -1, 64) + } + + for i := range benchmarksRandomNormal { + x := rand.NormFloat64() + benchmarksRandomNormal[i] = FormatFloat(x, 'g', -1, 64) + } +} + +func testAtof(t *testing.T, opt bool) { + oldopt := SetOptimize(opt) + for i := 0; i < len(atoftests); i++ { + test := &atoftests[i] + out, err := ParseFloat(test.in, 64) + outs := FormatFloat(out, 'g', -1, 64) + if outs != test.out || !reflect.DeepEqual(err, test.err) { + t.Errorf("ParseFloat(%v, 64) = %v, %v want %v, %v", + test.in, out, err, test.out, test.err) + } + + if float64(float32(out)) == out { + out, err := ParseFloat(test.in, 32) + out32 := float32(out) + if float64(out32) != out { + t.Errorf("ParseFloat(%v, 32) = %v, not a float32 (closest is %v)", test.in, out, float64(out32)) + continue + } + outs := FormatFloat(float64(out32), 'g', -1, 32) + if outs != test.out || !reflect.DeepEqual(err, test.err) { + t.Errorf("ParseFloat(%v, 32) = %v, %v want %v, %v # %v", + test.in, out32, err, test.out, test.err, out) + } + } + } + for _, test := range atof32tests { + out, err := ParseFloat(test.in, 32) + out32 := float32(out) + if float64(out32) != out { + t.Errorf("ParseFloat(%v, 32) = %v, not a float32 (closest is %v)", test.in, out, float64(out32)) + continue + } + outs := FormatFloat(float64(out32), 'g', -1, 32) + if outs != test.out || !reflect.DeepEqual(err, test.err) { + t.Errorf("ParseFloat(%v, 32) = %v, %v want %v, %v # %v", + test.in, out32, err, test.out, test.err, out) + } + } + SetOptimize(oldopt) +} + +func TestAtof(t *testing.T) { testAtof(t, true) } + +func TestAtofSlow(t *testing.T) { testAtof(t, false) } + +func TestAtofRandom(t *testing.T) { + for _, test := range atofRandomTests { + x, _ := ParseFloat(test.s, 64) + switch { + default: + t.Errorf("number %s badly parsed as %b (expected %b)", test.s, x, test.x) + case x == test.x: + case math.IsNaN(test.x) && math.IsNaN(x): + } + } + t.Logf("tested %d random numbers", len(atofRandomTests)) +} + +var roundTripCases = []struct { + f float64 + s string +}{ + // Issue 2917. + // This test will break the optimized conversion if the + // FPU is using 80-bit registers instead of 64-bit registers, + // usually because the operating system initialized the + // thread with 80-bit precision and the Go runtime didn't + // fix the FP control word. + {8865794286000691 << 39, "4.87402195346389e+27"}, + {8865794286000692 << 39, "4.8740219534638903e+27"}, +} + +func TestRoundTrip(t *testing.T) { + for _, tt := range roundTripCases { + old := SetOptimize(false) + s := FormatFloat(tt.f, 'g', -1, 64) + if s != tt.s { + t.Errorf("no-opt FormatFloat(%b) = %s, want %s", tt.f, s, tt.s) + } + f, err := ParseFloat(tt.s, 64) + if f != tt.f || err != nil { + t.Errorf("no-opt ParseFloat(%s) = %b, %v want %b, nil", tt.s, f, err, tt.f) + } + SetOptimize(true) + s = FormatFloat(tt.f, 'g', -1, 64) + if s != tt.s { + t.Errorf("opt FormatFloat(%b) = %s, want %s", tt.f, s, tt.s) + } + f, err = ParseFloat(tt.s, 64) + if f != tt.f || err != nil { + t.Errorf("opt ParseFloat(%s) = %b, %v want %b, nil", tt.s, f, err, tt.f) + } + SetOptimize(old) + } +} + +// TestRoundTrip32 tries a fraction of all finite positive float32 values. +func TestRoundTrip32(t *testing.T) { + step := uint32(997) + if testing.Short() { + step = 99991 + } + count := 0 + for i := uint32(0); i < 0xff<<23; i += step { + f := math.Float32frombits(i) + if i&1 == 1 { + f = -f // negative + } + s := FormatFloat(float64(f), 'g', -1, 32) + + parsed, err := ParseFloat(s, 32) + parsed32 := float32(parsed) + switch { + case err != nil: + t.Errorf("ParseFloat(%q, 32) gave error %s", s, err) + case float64(parsed32) != parsed: + t.Errorf("ParseFloat(%q, 32) = %v, not a float32 (nearest is %v)", s, parsed, parsed32) + case parsed32 != f: + t.Errorf("ParseFloat(%q, 32) = %b (expected %b)", s, parsed32, f) + } + count++ + } + t.Logf("tested %d float32's", count) +} + +func BenchmarkAtof64Decimal(b *testing.B) { + for i := 0; i < b.N; i++ { + ParseFloat("33909", 64) + } +} + +func BenchmarkAtof64Float(b *testing.B) { + for i := 0; i < b.N; i++ { + ParseFloat("339.7784", 64) + } +} + +func BenchmarkAtof64FloatExp(b *testing.B) { + for i := 0; i < b.N; i++ { + ParseFloat("-5.09e75", 64) + } +} + +func BenchmarkAtof64Big(b *testing.B) { + for i := 0; i < b.N; i++ { + ParseFloat("123456789123456789123456789", 64) + } +} + +func BenchmarkAtof64RandomBits(b *testing.B) { + for i := 0; i < b.N; i++ { + ParseFloat(benchmarksRandomBits[i%1024], 64) + } +} + +func BenchmarkAtof64RandomFloats(b *testing.B) { + for i := 0; i < b.N; i++ { + ParseFloat(benchmarksRandomNormal[i%1024], 64) + } +} + +func BenchmarkAtof32Decimal(b *testing.B) { + for i := 0; i < b.N; i++ { + ParseFloat("33909", 32) + } +} + +func BenchmarkAtof32Float(b *testing.B) { + for i := 0; i < b.N; i++ { + ParseFloat("339.778", 32) + } +} + +func BenchmarkAtof32FloatExp(b *testing.B) { + for i := 0; i < b.N; i++ { + ParseFloat("12.3456e32", 32) + } +} + +var float32strings [4096]string + +func BenchmarkAtof32Random(b *testing.B) { + n := uint32(997) + for i := range float32strings { + n = (99991*n + 42) % (0xff << 23) + float32strings[i] = FormatFloat(float64(math.Float32frombits(n)), 'g', -1, 32) + } + b.ResetTimer() + for i := 0; i < b.N; i++ { + ParseFloat(float32strings[i%4096], 32) + } +} diff --git a/src/strconv/atoi.go b/src/strconv/atoi.go new file mode 100644 index 000000000..9ecec5a58 --- /dev/null +++ b/src/strconv/atoi.go @@ -0,0 +1,198 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package strconv + +import "errors" + +// ErrRange indicates that a value is out of range for the target type. +var ErrRange = errors.New("value out of range") + +// ErrSyntax indicates that a value does not have the right syntax for the target type. +var ErrSyntax = errors.New("invalid syntax") + +// A NumError records a failed conversion. +type NumError struct { + Func string // the failing function (ParseBool, ParseInt, ParseUint, ParseFloat) + Num string // the input + Err error // the reason the conversion failed (ErrRange, ErrSyntax) +} + +func (e *NumError) Error() string { + return "strconv." + e.Func + ": " + "parsing " + Quote(e.Num) + ": " + e.Err.Error() +} + +func syntaxError(fn, str string) *NumError { + return &NumError{fn, str, ErrSyntax} +} + +func rangeError(fn, str string) *NumError { + return &NumError{fn, str, ErrRange} +} + +const intSize = 32 << (^uint(0) >> 63) + +// IntSize is the size in bits of an int or uint value. +const IntSize = intSize + +// Return the first number n such that n*base >= 1<<64. +func cutoff64(base int) uint64 { + if base < 2 { + return 0 + } + return (1<<64-1)/uint64(base) + 1 +} + +// ParseUint is like ParseInt but for unsigned numbers. +func ParseUint(s string, base int, bitSize int) (n uint64, err error) { + var cutoff, maxVal uint64 + + if bitSize == 0 { + bitSize = int(IntSize) + } + + s0 := s + switch { + case len(s) < 1: + err = ErrSyntax + goto Error + + case 2 <= base && base <= 36: + // valid base; nothing to do + + case base == 0: + // Look for octal, hex prefix. + switch { + case s[0] == '0' && len(s) > 1 && (s[1] == 'x' || s[1] == 'X'): + base = 16 + s = s[2:] + if len(s) < 1 { + err = ErrSyntax + goto Error + } + case s[0] == '0': + base = 8 + default: + base = 10 + } + + default: + err = errors.New("invalid base " + Itoa(base)) + goto Error + } + + n = 0 + cutoff = cutoff64(base) + maxVal = 1<<uint(bitSize) - 1 + + for i := 0; i < len(s); i++ { + var v byte + d := s[i] + switch { + case '0' <= d && d <= '9': + v = d - '0' + case 'a' <= d && d <= 'z': + v = d - 'a' + 10 + case 'A' <= d && d <= 'Z': + v = d - 'A' + 10 + default: + n = 0 + err = ErrSyntax + goto Error + } + if int(v) >= base { + n = 0 + err = ErrSyntax + goto Error + } + + if n >= cutoff { + // n*base overflows + n = 1<<64 - 1 + err = ErrRange + goto Error + } + n *= uint64(base) + + n1 := n + uint64(v) + if n1 < n || n1 > maxVal { + // n+v overflows + n = 1<<64 - 1 + err = ErrRange + goto Error + } + n = n1 + } + + return n, nil + +Error: + return n, &NumError{"ParseUint", s0, err} +} + +// ParseInt interprets a string s in the given base (2 to 36) and +// returns the corresponding value i. If base == 0, the base is +// implied by the string's prefix: base 16 for "0x", base 8 for +// "0", and base 10 otherwise. +// +// The bitSize argument specifies the integer type +// that the result must fit into. Bit sizes 0, 8, 16, 32, and 64 +// correspond to int, int8, int16, int32, and int64. +// +// The errors that ParseInt returns have concrete type *NumError +// and include err.Num = s. If s is empty or contains invalid +// digits, err.Err = ErrSyntax and the returned value is 0; +// if the value corresponding to s cannot be represented by a +// signed integer of the given size, err.Err = ErrRange and the +// returned value is the maximum magnitude integer of the +// appropriate bitSize and sign. +func ParseInt(s string, base int, bitSize int) (i int64, err error) { + const fnParseInt = "ParseInt" + + if bitSize == 0 { + bitSize = int(IntSize) + } + + // Empty string bad. + if len(s) == 0 { + return 0, syntaxError(fnParseInt, s) + } + + // Pick off leading sign. + s0 := s + neg := false + if s[0] == '+' { + s = s[1:] + } else if s[0] == '-' { + neg = true + s = s[1:] + } + + // Convert unsigned and check range. + var un uint64 + un, err = ParseUint(s, base, bitSize) + if err != nil && err.(*NumError).Err != ErrRange { + err.(*NumError).Func = fnParseInt + err.(*NumError).Num = s0 + return 0, err + } + cutoff := uint64(1 << uint(bitSize-1)) + if !neg && un >= cutoff { + return int64(cutoff - 1), rangeError(fnParseInt, s0) + } + if neg && un > cutoff { + return -int64(cutoff), rangeError(fnParseInt, s0) + } + n := int64(un) + if neg { + n = -n + } + return n, nil +} + +// Atoi is shorthand for ParseInt(s, 10, 0). +func Atoi(s string) (i int, err error) { + i64, err := ParseInt(s, 10, 0) + return int(i64), err +} diff --git a/src/strconv/atoi_test.go b/src/strconv/atoi_test.go new file mode 100644 index 000000000..940757307 --- /dev/null +++ b/src/strconv/atoi_test.go @@ -0,0 +1,326 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package strconv_test + +import ( + "errors" + "reflect" + . "strconv" + "testing" +) + +type atoui64Test struct { + in string + out uint64 + err error +} + +var atoui64tests = []atoui64Test{ + {"", 0, ErrSyntax}, + {"0", 0, nil}, + {"1", 1, nil}, + {"12345", 12345, nil}, + {"012345", 12345, nil}, + {"12345x", 0, ErrSyntax}, + {"98765432100", 98765432100, nil}, + {"18446744073709551615", 1<<64 - 1, nil}, + {"18446744073709551616", 1<<64 - 1, ErrRange}, + {"18446744073709551620", 1<<64 - 1, ErrRange}, +} + +var btoui64tests = []atoui64Test{ + {"", 0, ErrSyntax}, + {"0", 0, nil}, + {"1", 1, nil}, + {"12345", 12345, nil}, + {"012345", 012345, nil}, + {"0x12345", 0x12345, nil}, + {"0X12345", 0x12345, nil}, + {"12345x", 0, ErrSyntax}, + {"98765432100", 98765432100, nil}, + {"18446744073709551615", 1<<64 - 1, nil}, + {"18446744073709551616", 1<<64 - 1, ErrRange}, + {"18446744073709551620", 1<<64 - 1, ErrRange}, + {"0xFFFFFFFFFFFFFFFF", 1<<64 - 1, nil}, + {"0x10000000000000000", 1<<64 - 1, ErrRange}, + {"01777777777777777777777", 1<<64 - 1, nil}, + {"01777777777777777777778", 0, ErrSyntax}, + {"02000000000000000000000", 1<<64 - 1, ErrRange}, + {"0200000000000000000000", 1 << 61, nil}, +} + +type atoi64Test struct { + in string + out int64 + err error +} + +var atoi64tests = []atoi64Test{ + {"", 0, ErrSyntax}, + {"0", 0, nil}, + {"-0", 0, nil}, + {"1", 1, nil}, + {"-1", -1, nil}, + {"12345", 12345, nil}, + {"-12345", -12345, nil}, + {"012345", 12345, nil}, + {"-012345", -12345, nil}, + {"98765432100", 98765432100, nil}, + {"-98765432100", -98765432100, nil}, + {"9223372036854775807", 1<<63 - 1, nil}, + {"-9223372036854775807", -(1<<63 - 1), nil}, + {"9223372036854775808", 1<<63 - 1, ErrRange}, + {"-9223372036854775808", -1 << 63, nil}, + {"9223372036854775809", 1<<63 - 1, ErrRange}, + {"-9223372036854775809", -1 << 63, ErrRange}, +} + +var btoi64tests = []atoi64Test{ + {"", 0, ErrSyntax}, + {"0", 0, nil}, + {"-0", 0, nil}, + {"1", 1, nil}, + {"-1", -1, nil}, + {"12345", 12345, nil}, + {"-12345", -12345, nil}, + {"012345", 012345, nil}, + {"-012345", -012345, nil}, + {"0x12345", 0x12345, nil}, + {"-0X12345", -0x12345, nil}, + {"12345x", 0, ErrSyntax}, + {"-12345x", 0, ErrSyntax}, + {"98765432100", 98765432100, nil}, + {"-98765432100", -98765432100, nil}, + {"9223372036854775807", 1<<63 - 1, nil}, + {"-9223372036854775807", -(1<<63 - 1), nil}, + {"9223372036854775808", 1<<63 - 1, ErrRange}, + {"-9223372036854775808", -1 << 63, nil}, + {"9223372036854775809", 1<<63 - 1, ErrRange}, + {"-9223372036854775809", -1 << 63, ErrRange}, +} + +type atoui32Test struct { + in string + out uint32 + err error +} + +var atoui32tests = []atoui32Test{ + {"", 0, ErrSyntax}, + {"0", 0, nil}, + {"1", 1, nil}, + {"12345", 12345, nil}, + {"012345", 12345, nil}, + {"12345x", 0, ErrSyntax}, + {"987654321", 987654321, nil}, + {"4294967295", 1<<32 - 1, nil}, + {"4294967296", 1<<32 - 1, ErrRange}, +} + +type atoi32Test struct { + in string + out int32 + err error +} + +var atoi32tests = []atoi32Test{ + {"", 0, ErrSyntax}, + {"0", 0, nil}, + {"-0", 0, nil}, + {"1", 1, nil}, + {"-1", -1, nil}, + {"12345", 12345, nil}, + {"-12345", -12345, nil}, + {"012345", 12345, nil}, + {"-012345", -12345, nil}, + {"12345x", 0, ErrSyntax}, + {"-12345x", 0, ErrSyntax}, + {"987654321", 987654321, nil}, + {"-987654321", -987654321, nil}, + {"2147483647", 1<<31 - 1, nil}, + {"-2147483647", -(1<<31 - 1), nil}, + {"2147483648", 1<<31 - 1, ErrRange}, + {"-2147483648", -1 << 31, nil}, + {"2147483649", 1<<31 - 1, ErrRange}, + {"-2147483649", -1 << 31, ErrRange}, +} + +type numErrorTest struct { + num, want string +} + +var numErrorTests = []numErrorTest{ + {"0", `strconv.ParseFloat: parsing "0": failed`}, + {"`", "strconv.ParseFloat: parsing \"`\": failed"}, + {"1\x00.2", `strconv.ParseFloat: parsing "1\x00.2": failed`}, +} + +func init() { + // The atoi routines return NumErrors wrapping + // the error and the string. Convert the tables above. + for i := range atoui64tests { + test := &atoui64tests[i] + if test.err != nil { + test.err = &NumError{"ParseUint", test.in, test.err} + } + } + for i := range btoui64tests { + test := &btoui64tests[i] + if test.err != nil { + test.err = &NumError{"ParseUint", test.in, test.err} + } + } + for i := range atoi64tests { + test := &atoi64tests[i] + if test.err != nil { + test.err = &NumError{"ParseInt", test.in, test.err} + } + } + for i := range btoi64tests { + test := &btoi64tests[i] + if test.err != nil { + test.err = &NumError{"ParseInt", test.in, test.err} + } + } + for i := range atoui32tests { + test := &atoui32tests[i] + if test.err != nil { + test.err = &NumError{"ParseUint", test.in, test.err} + } + } + for i := range atoi32tests { + test := &atoi32tests[i] + if test.err != nil { + test.err = &NumError{"ParseInt", test.in, test.err} + } + } +} + +func TestParseUint64(t *testing.T) { + for i := range atoui64tests { + test := &atoui64tests[i] + out, err := ParseUint(test.in, 10, 64) + if test.out != out || !reflect.DeepEqual(test.err, err) { + t.Errorf("Atoui64(%q) = %v, %v want %v, %v", + test.in, out, err, test.out, test.err) + } + } +} + +func TestParseUint64Base(t *testing.T) { + for i := range btoui64tests { + test := &btoui64tests[i] + out, err := ParseUint(test.in, 0, 64) + if test.out != out || !reflect.DeepEqual(test.err, err) { + t.Errorf("ParseUint(%q) = %v, %v want %v, %v", + test.in, out, err, test.out, test.err) + } + } +} + +func TestParseInt64(t *testing.T) { + for i := range atoi64tests { + test := &atoi64tests[i] + out, err := ParseInt(test.in, 10, 64) + if test.out != out || !reflect.DeepEqual(test.err, err) { + t.Errorf("Atoi64(%q) = %v, %v want %v, %v", + test.in, out, err, test.out, test.err) + } + } +} + +func TestParseInt64Base(t *testing.T) { + for i := range btoi64tests { + test := &btoi64tests[i] + out, err := ParseInt(test.in, 0, 64) + if test.out != out || !reflect.DeepEqual(test.err, err) { + t.Errorf("ParseInt(%q) = %v, %v want %v, %v", + test.in, out, err, test.out, test.err) + } + } +} + +func TestParseUint(t *testing.T) { + switch IntSize { + case 32: + for i := range atoui32tests { + test := &atoui32tests[i] + out, err := ParseUint(test.in, 10, 0) + if test.out != uint32(out) || !reflect.DeepEqual(test.err, err) { + t.Errorf("Atoui(%q) = %v, %v want %v, %v", + test.in, out, err, test.out, test.err) + } + } + case 64: + for i := range atoui64tests { + test := &atoui64tests[i] + out, err := ParseUint(test.in, 10, 0) + if test.out != uint64(out) || !reflect.DeepEqual(test.err, err) { + t.Errorf("Atoui(%q) = %v, %v want %v, %v", + test.in, out, err, test.out, test.err) + } + } + } +} + +func TestParseInt(t *testing.T) { + switch IntSize { + case 32: + for i := range atoi32tests { + test := &atoi32tests[i] + out, err := ParseInt(test.in, 10, 0) + if test.out != int32(out) || !reflect.DeepEqual(test.err, err) { + t.Errorf("Atoi(%q) = %v, %v want %v, %v", + test.in, out, err, test.out, test.err) + } + } + case 64: + for i := range atoi64tests { + test := &atoi64tests[i] + out, err := ParseInt(test.in, 10, 0) + if test.out != int64(out) || !reflect.DeepEqual(test.err, err) { + t.Errorf("Atoi(%q) = %v, %v want %v, %v", + test.in, out, err, test.out, test.err) + } + } + } +} + +func TestNumError(t *testing.T) { + for _, test := range numErrorTests { + err := &NumError{ + Func: "ParseFloat", + Num: test.num, + Err: errors.New("failed"), + } + if got := err.Error(); got != test.want { + t.Errorf(`(&NumError{"ParseFloat", %q, "failed"}).Error() = %v, want %v`, test.num, got, test.want) + } + } +} + +func BenchmarkAtoi(b *testing.B) { + for i := 0; i < b.N; i++ { + ParseInt("12345678", 10, 0) + } +} + +func BenchmarkAtoiNeg(b *testing.B) { + for i := 0; i < b.N; i++ { + ParseInt("-12345678", 10, 0) + } +} + +func BenchmarkAtoi64(b *testing.B) { + for i := 0; i < b.N; i++ { + ParseInt("12345678901234", 10, 64) + } +} + +func BenchmarkAtoi64Neg(b *testing.B) { + for i := 0; i < b.N; i++ { + ParseInt("-12345678901234", 10, 64) + } +} diff --git a/src/strconv/decimal.go b/src/strconv/decimal.go new file mode 100644 index 000000000..42601283d --- /dev/null +++ b/src/strconv/decimal.go @@ -0,0 +1,378 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Multiprecision decimal numbers. +// For floating-point formatting only; not general purpose. +// Only operations are assign and (binary) left/right shift. +// Can do binary floating point in multiprecision decimal precisely +// because 2 divides 10; cannot do decimal floating point +// in multiprecision binary precisely. + +package strconv + +type decimal struct { + d [800]byte // digits + nd int // number of digits used + dp int // decimal point + neg bool + trunc bool // discarded nonzero digits beyond d[:nd] +} + +func (a *decimal) String() string { + n := 10 + a.nd + if a.dp > 0 { + n += a.dp + } + if a.dp < 0 { + n += -a.dp + } + + buf := make([]byte, n) + w := 0 + switch { + case a.nd == 0: + return "0" + + case a.dp <= 0: + // zeros fill space between decimal point and digits + buf[w] = '0' + w++ + buf[w] = '.' + w++ + w += digitZero(buf[w : w+-a.dp]) + w += copy(buf[w:], a.d[0:a.nd]) + + case a.dp < a.nd: + // decimal point in middle of digits + w += copy(buf[w:], a.d[0:a.dp]) + buf[w] = '.' + w++ + w += copy(buf[w:], a.d[a.dp:a.nd]) + + default: + // zeros fill space between digits and decimal point + w += copy(buf[w:], a.d[0:a.nd]) + w += digitZero(buf[w : w+a.dp-a.nd]) + } + return string(buf[0:w]) +} + +func digitZero(dst []byte) int { + for i := range dst { + dst[i] = '0' + } + return len(dst) +} + +// trim trailing zeros from number. +// (They are meaningless; the decimal point is tracked +// independent of the number of digits.) +func trim(a *decimal) { + for a.nd > 0 && a.d[a.nd-1] == '0' { + a.nd-- + } + if a.nd == 0 { + a.dp = 0 + } +} + +// Assign v to a. +func (a *decimal) Assign(v uint64) { + var buf [24]byte + + // Write reversed decimal in buf. + n := 0 + for v > 0 { + v1 := v / 10 + v -= 10 * v1 + buf[n] = byte(v + '0') + n++ + v = v1 + } + + // Reverse again to produce forward decimal in a.d. + a.nd = 0 + for n--; n >= 0; n-- { + a.d[a.nd] = buf[n] + a.nd++ + } + a.dp = a.nd + trim(a) +} + +// Maximum shift that we can do in one pass without overflow. +// Signed int has 31 bits, and we have to be able to accommodate 9<<k. +const maxShift = 27 + +// Binary shift right (* 2) by k bits. k <= maxShift to avoid overflow. +func rightShift(a *decimal, k uint) { + r := 0 // read pointer + w := 0 // write pointer + + // Pick up enough leading digits to cover first shift. + n := 0 + for ; n>>k == 0; r++ { + if r >= a.nd { + if n == 0 { + // a == 0; shouldn't get here, but handle anyway. + a.nd = 0 + return + } + for n>>k == 0 { + n = n * 10 + r++ + } + break + } + c := int(a.d[r]) + n = n*10 + c - '0' + } + a.dp -= r - 1 + + // Pick up a digit, put down a digit. + for ; r < a.nd; r++ { + c := int(a.d[r]) + dig := n >> k + n -= dig << k + a.d[w] = byte(dig + '0') + w++ + n = n*10 + c - '0' + } + + // Put down extra digits. + for n > 0 { + dig := n >> k + n -= dig << k + if w < len(a.d) { + a.d[w] = byte(dig + '0') + w++ + } else if dig > 0 { + a.trunc = true + } + n = n * 10 + } + + a.nd = w + trim(a) +} + +// Cheat sheet for left shift: table indexed by shift count giving +// number of new digits that will be introduced by that shift. +// +// For example, leftcheats[4] = {2, "625"}. That means that +// if we are shifting by 4 (multiplying by 16), it will add 2 digits +// when the string prefix is "625" through "999", and one fewer digit +// if the string prefix is "000" through "624". +// +// Credit for this trick goes to Ken. + +type leftCheat struct { + delta int // number of new digits + cutoff string // minus one digit if original < a. +} + +var leftcheats = []leftCheat{ + // Leading digits of 1/2^i = 5^i. + // 5^23 is not an exact 64-bit floating point number, + // so have to use bc for the math. + /* + seq 27 | sed 's/^/5^/' | bc | + awk 'BEGIN{ print "\tleftCheat{ 0, \"\" }," } + { + log2 = log(2)/log(10) + printf("\tleftCheat{ %d, \"%s\" },\t// * %d\n", + int(log2*NR+1), $0, 2**NR) + }' + */ + {0, ""}, + {1, "5"}, // * 2 + {1, "25"}, // * 4 + {1, "125"}, // * 8 + {2, "625"}, // * 16 + {2, "3125"}, // * 32 + {2, "15625"}, // * 64 + {3, "78125"}, // * 128 + {3, "390625"}, // * 256 + {3, "1953125"}, // * 512 + {4, "9765625"}, // * 1024 + {4, "48828125"}, // * 2048 + {4, "244140625"}, // * 4096 + {4, "1220703125"}, // * 8192 + {5, "6103515625"}, // * 16384 + {5, "30517578125"}, // * 32768 + {5, "152587890625"}, // * 65536 + {6, "762939453125"}, // * 131072 + {6, "3814697265625"}, // * 262144 + {6, "19073486328125"}, // * 524288 + {7, "95367431640625"}, // * 1048576 + {7, "476837158203125"}, // * 2097152 + {7, "2384185791015625"}, // * 4194304 + {7, "11920928955078125"}, // * 8388608 + {8, "59604644775390625"}, // * 16777216 + {8, "298023223876953125"}, // * 33554432 + {8, "1490116119384765625"}, // * 67108864 + {9, "7450580596923828125"}, // * 134217728 +} + +// Is the leading prefix of b lexicographically less than s? +func prefixIsLessThan(b []byte, s string) bool { + for i := 0; i < len(s); i++ { + if i >= len(b) { + return true + } + if b[i] != s[i] { + return b[i] < s[i] + } + } + return false +} + +// Binary shift left (/ 2) by k bits. k <= maxShift to avoid overflow. +func leftShift(a *decimal, k uint) { + delta := leftcheats[k].delta + if prefixIsLessThan(a.d[0:a.nd], leftcheats[k].cutoff) { + delta-- + } + + r := a.nd // read index + w := a.nd + delta // write index + n := 0 + + // Pick up a digit, put down a digit. + for r--; r >= 0; r-- { + n += (int(a.d[r]) - '0') << k + quo := n / 10 + rem := n - 10*quo + w-- + if w < len(a.d) { + a.d[w] = byte(rem + '0') + } else if rem != 0 { + a.trunc = true + } + n = quo + } + + // Put down extra digits. + for n > 0 { + quo := n / 10 + rem := n - 10*quo + w-- + if w < len(a.d) { + a.d[w] = byte(rem + '0') + } else if rem != 0 { + a.trunc = true + } + n = quo + } + + a.nd += delta + if a.nd >= len(a.d) { + a.nd = len(a.d) + } + a.dp += delta + trim(a) +} + +// Binary shift left (k > 0) or right (k < 0). +func (a *decimal) Shift(k int) { + switch { + case a.nd == 0: + // nothing to do: a == 0 + case k > 0: + for k > maxShift { + leftShift(a, maxShift) + k -= maxShift + } + leftShift(a, uint(k)) + case k < 0: + for k < -maxShift { + rightShift(a, maxShift) + k += maxShift + } + rightShift(a, uint(-k)) + } +} + +// If we chop a at nd digits, should we round up? +func shouldRoundUp(a *decimal, nd int) bool { + if nd < 0 || nd >= a.nd { + return false + } + if a.d[nd] == '5' && nd+1 == a.nd { // exactly halfway - round to even + // if we truncated, a little higher than what's recorded - always round up + if a.trunc { + return true + } + return nd > 0 && (a.d[nd-1]-'0')%2 != 0 + } + // not halfway - digit tells all + return a.d[nd] >= '5' +} + +// Round a to nd digits (or fewer). +// If nd is zero, it means we're rounding +// just to the left of the digits, as in +// 0.09 -> 0.1. +func (a *decimal) Round(nd int) { + if nd < 0 || nd >= a.nd { + return + } + if shouldRoundUp(a, nd) { + a.RoundUp(nd) + } else { + a.RoundDown(nd) + } +} + +// Round a down to nd digits (or fewer). +func (a *decimal) RoundDown(nd int) { + if nd < 0 || nd >= a.nd { + return + } + a.nd = nd + trim(a) +} + +// Round a up to nd digits (or fewer). +func (a *decimal) RoundUp(nd int) { + if nd < 0 || nd >= a.nd { + return + } + + // round up + for i := nd - 1; i >= 0; i-- { + c := a.d[i] + if c < '9' { // can stop after this digit + a.d[i]++ + a.nd = i + 1 + return + } + } + + // Number is all 9s. + // Change to single 1 with adjusted decimal point. + a.d[0] = '1' + a.nd = 1 + a.dp++ +} + +// Extract integer part, rounded appropriately. +// No guarantees about overflow. +func (a *decimal) RoundedInteger() uint64 { + if a.dp > 20 { + return 0xFFFFFFFFFFFFFFFF + } + var i int + n := uint64(0) + for i = 0; i < a.dp && i < a.nd; i++ { + n = n*10 + uint64(a.d[i]-'0') + } + for ; i < a.dp; i++ { + n *= 10 + } + if shouldRoundUp(a, a.dp) { + n++ + } + return n +} diff --git a/src/strconv/decimal_test.go b/src/strconv/decimal_test.go new file mode 100644 index 000000000..13a127f5b --- /dev/null +++ b/src/strconv/decimal_test.go @@ -0,0 +1,127 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package strconv_test + +import ( + . "strconv" + "testing" +) + +type shiftTest struct { + i uint64 + shift int + out string +} + +var shifttests = []shiftTest{ + {0, -100, "0"}, + {0, 100, "0"}, + {1, 100, "1267650600228229401496703205376"}, + {1, -100, + "0.00000000000000000000000000000078886090522101180541" + + "17285652827862296732064351090230047702789306640625", + }, + {12345678, 8, "3160493568"}, + {12345678, -8, "48225.3046875"}, + {195312, 9, "99999744"}, + {1953125, 9, "1000000000"}, +} + +func TestDecimalShift(t *testing.T) { + for i := 0; i < len(shifttests); i++ { + test := &shifttests[i] + d := NewDecimal(test.i) + d.Shift(test.shift) + s := d.String() + if s != test.out { + t.Errorf("Decimal %v << %v = %v, want %v", + test.i, test.shift, s, test.out) + } + } +} + +type roundTest struct { + i uint64 + nd int + down, round, up string + int uint64 +} + +var roundtests = []roundTest{ + {0, 4, "0", "0", "0", 0}, + {12344999, 4, "12340000", "12340000", "12350000", 12340000}, + {12345000, 4, "12340000", "12340000", "12350000", 12340000}, + {12345001, 4, "12340000", "12350000", "12350000", 12350000}, + {23454999, 4, "23450000", "23450000", "23460000", 23450000}, + {23455000, 4, "23450000", "23460000", "23460000", 23460000}, + {23455001, 4, "23450000", "23460000", "23460000", 23460000}, + + {99994999, 4, "99990000", "99990000", "100000000", 99990000}, + {99995000, 4, "99990000", "100000000", "100000000", 100000000}, + {99999999, 4, "99990000", "100000000", "100000000", 100000000}, + + {12994999, 4, "12990000", "12990000", "13000000", 12990000}, + {12995000, 4, "12990000", "13000000", "13000000", 13000000}, + {12999999, 4, "12990000", "13000000", "13000000", 13000000}, +} + +func TestDecimalRound(t *testing.T) { + for i := 0; i < len(roundtests); i++ { + test := &roundtests[i] + d := NewDecimal(test.i) + d.RoundDown(test.nd) + s := d.String() + if s != test.down { + t.Errorf("Decimal %v RoundDown %d = %v, want %v", + test.i, test.nd, s, test.down) + } + d = NewDecimal(test.i) + d.Round(test.nd) + s = d.String() + if s != test.round { + t.Errorf("Decimal %v Round %d = %v, want %v", + test.i, test.nd, s, test.down) + } + d = NewDecimal(test.i) + d.RoundUp(test.nd) + s = d.String() + if s != test.up { + t.Errorf("Decimal %v RoundUp %d = %v, want %v", + test.i, test.nd, s, test.up) + } + } +} + +type roundIntTest struct { + i uint64 + shift int + int uint64 +} + +var roundinttests = []roundIntTest{ + {0, 100, 0}, + {512, -8, 2}, + {513, -8, 2}, + {640, -8, 2}, + {641, -8, 3}, + {384, -8, 2}, + {385, -8, 2}, + {383, -8, 1}, + {1, 100, 1<<64 - 1}, + {1000, 0, 1000}, +} + +func TestDecimalRoundedInteger(t *testing.T) { + for i := 0; i < len(roundinttests); i++ { + test := roundinttests[i] + d := NewDecimal(test.i) + d.Shift(test.shift) + int := d.RoundedInteger() + if int != test.int { + t.Errorf("Decimal %v >> %v RoundedInteger = %v, want %v", + test.i, test.shift, int, test.int) + } + } +} diff --git a/src/strconv/extfloat.go b/src/strconv/extfloat.go new file mode 100644 index 000000000..bed8b16bd --- /dev/null +++ b/src/strconv/extfloat.go @@ -0,0 +1,668 @@ +// Copyright 2011 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package strconv + +// An extFloat represents an extended floating-point number, with more +// precision than a float64. It does not try to save bits: the +// number represented by the structure is mant*(2^exp), with a negative +// sign if neg is true. +type extFloat struct { + mant uint64 + exp int + neg bool +} + +// Powers of ten taken from double-conversion library. +// http://code.google.com/p/double-conversion/ +const ( + firstPowerOfTen = -348 + stepPowerOfTen = 8 +) + +var smallPowersOfTen = [...]extFloat{ + {1 << 63, -63, false}, // 1 + {0xa << 60, -60, false}, // 1e1 + {0x64 << 57, -57, false}, // 1e2 + {0x3e8 << 54, -54, false}, // 1e3 + {0x2710 << 50, -50, false}, // 1e4 + {0x186a0 << 47, -47, false}, // 1e5 + {0xf4240 << 44, -44, false}, // 1e6 + {0x989680 << 40, -40, false}, // 1e7 +} + +var powersOfTen = [...]extFloat{ + {0xfa8fd5a0081c0288, -1220, false}, // 10^-348 + {0xbaaee17fa23ebf76, -1193, false}, // 10^-340 + {0x8b16fb203055ac76, -1166, false}, // 10^-332 + {0xcf42894a5dce35ea, -1140, false}, // 10^-324 + {0x9a6bb0aa55653b2d, -1113, false}, // 10^-316 + {0xe61acf033d1a45df, -1087, false}, // 10^-308 + {0xab70fe17c79ac6ca, -1060, false}, // 10^-300 + {0xff77b1fcbebcdc4f, -1034, false}, // 10^-292 + {0xbe5691ef416bd60c, -1007, false}, // 10^-284 + {0x8dd01fad907ffc3c, -980, false}, // 10^-276 + {0xd3515c2831559a83, -954, false}, // 10^-268 + {0x9d71ac8fada6c9b5, -927, false}, // 10^-260 + {0xea9c227723ee8bcb, -901, false}, // 10^-252 + {0xaecc49914078536d, -874, false}, // 10^-244 + {0x823c12795db6ce57, -847, false}, // 10^-236 + {0xc21094364dfb5637, -821, false}, // 10^-228 + {0x9096ea6f3848984f, -794, false}, // 10^-220 + {0xd77485cb25823ac7, -768, false}, // 10^-212 + {0xa086cfcd97bf97f4, -741, false}, // 10^-204 + {0xef340a98172aace5, -715, false}, // 10^-196 + {0xb23867fb2a35b28e, -688, false}, // 10^-188 + {0x84c8d4dfd2c63f3b, -661, false}, // 10^-180 + {0xc5dd44271ad3cdba, -635, false}, // 10^-172 + {0x936b9fcebb25c996, -608, false}, // 10^-164 + {0xdbac6c247d62a584, -582, false}, // 10^-156 + {0xa3ab66580d5fdaf6, -555, false}, // 10^-148 + {0xf3e2f893dec3f126, -529, false}, // 10^-140 + {0xb5b5ada8aaff80b8, -502, false}, // 10^-132 + {0x87625f056c7c4a8b, -475, false}, // 10^-124 + {0xc9bcff6034c13053, -449, false}, // 10^-116 + {0x964e858c91ba2655, -422, false}, // 10^-108 + {0xdff9772470297ebd, -396, false}, // 10^-100 + {0xa6dfbd9fb8e5b88f, -369, false}, // 10^-92 + {0xf8a95fcf88747d94, -343, false}, // 10^-84 + {0xb94470938fa89bcf, -316, false}, // 10^-76 + {0x8a08f0f8bf0f156b, -289, false}, // 10^-68 + {0xcdb02555653131b6, -263, false}, // 10^-60 + {0x993fe2c6d07b7fac, -236, false}, // 10^-52 + {0xe45c10c42a2b3b06, -210, false}, // 10^-44 + {0xaa242499697392d3, -183, false}, // 10^-36 + {0xfd87b5f28300ca0e, -157, false}, // 10^-28 + {0xbce5086492111aeb, -130, false}, // 10^-20 + {0x8cbccc096f5088cc, -103, false}, // 10^-12 + {0xd1b71758e219652c, -77, false}, // 10^-4 + {0x9c40000000000000, -50, false}, // 10^4 + {0xe8d4a51000000000, -24, false}, // 10^12 + {0xad78ebc5ac620000, 3, false}, // 10^20 + {0x813f3978f8940984, 30, false}, // 10^28 + {0xc097ce7bc90715b3, 56, false}, // 10^36 + {0x8f7e32ce7bea5c70, 83, false}, // 10^44 + {0xd5d238a4abe98068, 109, false}, // 10^52 + {0x9f4f2726179a2245, 136, false}, // 10^60 + {0xed63a231d4c4fb27, 162, false}, // 10^68 + {0xb0de65388cc8ada8, 189, false}, // 10^76 + {0x83c7088e1aab65db, 216, false}, // 10^84 + {0xc45d1df942711d9a, 242, false}, // 10^92 + {0x924d692ca61be758, 269, false}, // 10^100 + {0xda01ee641a708dea, 295, false}, // 10^108 + {0xa26da3999aef774a, 322, false}, // 10^116 + {0xf209787bb47d6b85, 348, false}, // 10^124 + {0xb454e4a179dd1877, 375, false}, // 10^132 + {0x865b86925b9bc5c2, 402, false}, // 10^140 + {0xc83553c5c8965d3d, 428, false}, // 10^148 + {0x952ab45cfa97a0b3, 455, false}, // 10^156 + {0xde469fbd99a05fe3, 481, false}, // 10^164 + {0xa59bc234db398c25, 508, false}, // 10^172 + {0xf6c69a72a3989f5c, 534, false}, // 10^180 + {0xb7dcbf5354e9bece, 561, false}, // 10^188 + {0x88fcf317f22241e2, 588, false}, // 10^196 + {0xcc20ce9bd35c78a5, 614, false}, // 10^204 + {0x98165af37b2153df, 641, false}, // 10^212 + {0xe2a0b5dc971f303a, 667, false}, // 10^220 + {0xa8d9d1535ce3b396, 694, false}, // 10^228 + {0xfb9b7cd9a4a7443c, 720, false}, // 10^236 + {0xbb764c4ca7a44410, 747, false}, // 10^244 + {0x8bab8eefb6409c1a, 774, false}, // 10^252 + {0xd01fef10a657842c, 800, false}, // 10^260 + {0x9b10a4e5e9913129, 827, false}, // 10^268 + {0xe7109bfba19c0c9d, 853, false}, // 10^276 + {0xac2820d9623bf429, 880, false}, // 10^284 + {0x80444b5e7aa7cf85, 907, false}, // 10^292 + {0xbf21e44003acdd2d, 933, false}, // 10^300 + {0x8e679c2f5e44ff8f, 960, false}, // 10^308 + {0xd433179d9c8cb841, 986, false}, // 10^316 + {0x9e19db92b4e31ba9, 1013, false}, // 10^324 + {0xeb96bf6ebadf77d9, 1039, false}, // 10^332 + {0xaf87023b9bf0ee6b, 1066, false}, // 10^340 +} + +// floatBits returns the bits of the float64 that best approximates +// the extFloat passed as receiver. Overflow is set to true if +// the resulting float64 is ±Inf. +func (f *extFloat) floatBits(flt *floatInfo) (bits uint64, overflow bool) { + f.Normalize() + + exp := f.exp + 63 + + // Exponent too small. + if exp < flt.bias+1 { + n := flt.bias + 1 - exp + f.mant >>= uint(n) + exp += n + } + + // Extract 1+flt.mantbits bits from the 64-bit mantissa. + mant := f.mant >> (63 - flt.mantbits) + if f.mant&(1<<(62-flt.mantbits)) != 0 { + // Round up. + mant += 1 + } + + // Rounding might have added a bit; shift down. + if mant == 2<<flt.mantbits { + mant >>= 1 + exp++ + } + + // Infinities. + if exp-flt.bias >= 1<<flt.expbits-1 { + // ±Inf + mant = 0 + exp = 1<<flt.expbits - 1 + flt.bias + overflow = true + } else if mant&(1<<flt.mantbits) == 0 { + // Denormalized? + exp = flt.bias + } + // Assemble bits. + bits = mant & (uint64(1)<<flt.mantbits - 1) + bits |= uint64((exp-flt.bias)&(1<<flt.expbits-1)) << flt.mantbits + if f.neg { + bits |= 1 << (flt.mantbits + flt.expbits) + } + return +} + +// AssignComputeBounds sets f to the floating point value +// defined by mant, exp and precision given by flt. It returns +// lower, upper such that any number in the closed interval +// [lower, upper] is converted back to the same floating point number. +func (f *extFloat) AssignComputeBounds(mant uint64, exp int, neg bool, flt *floatInfo) (lower, upper extFloat) { + f.mant = mant + f.exp = exp - int(flt.mantbits) + f.neg = neg + if f.exp <= 0 && mant == (mant>>uint(-f.exp))<<uint(-f.exp) { + // An exact integer + f.mant >>= uint(-f.exp) + f.exp = 0 + return *f, *f + } + expBiased := exp - flt.bias + + upper = extFloat{mant: 2*f.mant + 1, exp: f.exp - 1, neg: f.neg} + if mant != 1<<flt.mantbits || 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() (shift uint) { + mant, exp := f.mant, f.exp + if mant == 0 { + return 0 + } + if mant>>(64-32) == 0 { + mant <<= 32 + exp -= 32 + } + if mant>>(64-16) == 0 { + mant <<= 16 + exp -= 16 + } + if mant>>(64-8) == 0 { + mant <<= 8 + exp -= 8 + } + if mant>>(64-4) == 0 { + mant <<= 4 + exp -= 4 + } + if mant>>(64-2) == 0 { + mant <<= 2 + exp -= 2 + } + if mant>>(64-1) == 0 { + mant <<= 1 + exp -= 1 + } + shift = uint(f.exp - exp) + f.mant, f.exp = mant, exp + return +} + +// Multiply sets f to the product f*g: the result is correctly rounded, +// but not normalized. +func (f *extFloat) Multiply(g extFloat) { + fhi, flo := f.mant>>32, uint64(uint32(f.mant)) + ghi, glo := g.mant>>32, uint64(uint32(g.mant)) + + // Cross products. + cross1 := fhi * glo + cross2 := flo * ghi + + // f.mant*g.mant is fhi*ghi << 64 + (cross1+cross2) << 32 + flo*glo + f.mant = fhi*ghi + (cross1 >> 32) + (cross2 >> 32) + rem := uint64(uint32(cross1)) + uint64(uint32(cross2)) + ((flo * glo) >> 32) + // Round up. + rem += (1 << 31) + + f.mant += (rem >> 32) + f.exp = f.exp + g.exp + 64 +} + +var uint64pow10 = [...]uint64{ + 1, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, + 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19, +} + +// AssignDecimal sets f to an approximate value mantissa*10^exp. It +// returns true if the value represented by f is guaranteed to be the +// best approximation of d after being rounded to a float64 or +// float32 depending on flt. +func (f *extFloat) AssignDecimal(mantissa uint64, exp10 int, neg bool, trunc bool, flt *floatInfo) (ok bool) { + const uint64digits = 19 + const errorscale = 8 + errors := 0 // An upper bound for error, computed in errorscale*ulp. + if trunc { + // the decimal number was truncated. + errors += errorscale / 2 + } + + f.mant = mantissa + f.exp = 0 + f.neg = neg + + // Multiply by powers of ten. + i := (exp10 - firstPowerOfTen) / stepPowerOfTen + if exp10 < firstPowerOfTen || i >= len(powersOfTen) { + return false + } + adjExp := (exp10 - firstPowerOfTen) % stepPowerOfTen + + // We multiply by exp%step + if adjExp < uint64digits && mantissa < uint64pow10[uint64digits-adjExp] { + // We can multiply the mantissa exactly. + f.mant *= uint64pow10[adjExp] + f.Normalize() + } else { + f.Normalize() + f.Multiply(smallPowersOfTen[adjExp]) + errors += errorscale / 2 + } + + // We multiply by 10 to the exp - exp%step. + f.Multiply(powersOfTen[i]) + if errors > 0 { + errors += 1 + } + errors += errorscale / 2 + + // Normalize + shift := f.Normalize() + errors <<= shift + + // Now f is a good approximation of the decimal. + // Check whether the error is too large: that is, if the mantissa + // is perturbated by the error, the resulting float64 will change. + // The 64 bits mantissa is 1 + 52 bits for float64 + 11 extra bits. + // + // In many cases the approximation will be good enough. + denormalExp := flt.bias - 63 + var extrabits uint + if f.exp <= denormalExp { + // f.mant * 2^f.exp is smaller than 2^(flt.bias+1). + extrabits = uint(63 - flt.mantbits + 1 + uint(denormalExp-f.exp)) + } else { + extrabits = uint(63 - flt.mantbits) + } + + halfway := uint64(1) << (extrabits - 1) + mant_extra := f.mant & (1<<extrabits - 1) + + // Do a signed comparison here! If the error estimate could make + // the mantissa round differently for the conversion to double, + // then we can't give a definite answer. + if int64(halfway)-int64(errors) < int64(mant_extra) && + int64(mant_extra) < int64(halfway)+int64(errors) { + return false + } + 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. +func (f *extFloat) frexp10() (exp10, index int) { + // The constants expMin and expMax constrain the final value of the + // binary exponent of f. We want a small integral part in the result + // because finding digits of an integer requires divisions, whereas + // digits of the fractional part can be found by repeatedly multiplying + // by 10. + const expMin = -60 + const expMax = -32 + // Find power of ten such that x * 10^n has a binary exponent + // between expMin and expMax. + approxExp10 := ((expMin+expMax)/2 - f.exp) * 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(a, b, c *extFloat) (exp10 int) { + exp10, i := c.frexp10() + a.Multiply(powersOfTen[i]) + b.Multiply(powersOfTen[i]) + return +} + +// FixedDecimal stores in d the first n significant digits +// of the decimal representation of f. It returns false +// if it cannot be sure of the answer. +func (f *extFloat) FixedDecimal(d *decimalSlice, n int) bool { + if f.mant == 0 { + d.nd = 0 + d.dp = 0 + d.neg = f.neg + return true + } + if n == 0 { + panic("strconv: internal error: extFloat.FixedDecimal called with n == 0") + } + // Multiply by an appropriate power of ten to have a reasonable + // number to process. + f.Normalize() + exp10, _ := f.frexp10() + + shift := uint(-f.exp) + integer := uint32(f.mant >> shift) + fraction := f.mant - (uint64(integer) << shift) + ε := uint64(1) // ε is the uncertainty we have on the mantissa of f. + + // Write exactly n digits to d. + needed := n // how many digits are left to write. + integerDigits := 0 // the number of decimal digits of integer. + pow10 := uint64(1) // the power of ten by which f was scaled. + for i, pow := 0, uint64(1); i < 20; i++ { + if pow > uint64(integer) { + integerDigits = i + break + } + pow *= 10 + } + rest := integer + if integerDigits > needed { + // the integral part is already large, trim the last digits. + pow10 = uint64pow10[integerDigits-needed] + integer /= uint32(pow10) + rest -= integer * uint32(pow10) + } else { + rest = 0 + } + + // Write the digits of integer: the digits of rest are omitted. + var buf [32]byte + pos := len(buf) + for v := integer; v > 0; { + v1 := v / 10 + v -= 10 * v1 + pos-- + buf[pos] = byte(v + '0') + v = v1 + } + for i := pos; i < len(buf); i++ { + d.d[i-pos] = buf[i] + } + nd := len(buf) - pos + d.nd = nd + d.dp = integerDigits + exp10 + needed -= nd + + if needed > 0 { + if rest != 0 || pow10 != 1 { + panic("strconv: internal error, rest != 0 but needed > 0") + } + // Emit digits for the fractional part. Each time, 10*fraction + // fits in a uint64 without overflow. + for needed > 0 { + fraction *= 10 + ε *= 10 // the uncertainty scales as we multiply by ten. + if 2*ε > 1<<shift { + // the error is so large it could modify which digit to write, abort. + return false + } + digit := fraction >> shift + d.d[nd] = byte(digit + '0') + fraction -= digit << shift + nd++ + needed-- + } + d.nd = nd + } + + // We have written a truncation of f (a numerator / 10^d.dp). The remaining part + // can be interpreted as a small number (< 1) to be added to the last digit of the + // numerator. + // + // If rest > 0, the amount is: + // (rest<<shift | fraction) / (pow10 << shift) + // fraction being known with a ±ε uncertainty. + // The fact that n > 0 guarantees that pow10 << shift does not overflow a uint64. + // + // If rest = 0, pow10 == 1 and the amount is + // fraction / (1 << shift) + // fraction being known with a ±ε uncertainty. + // + // We pass this information to the rounding routine for adjustment. + + ok := adjustLastDigitFixed(d, uint64(rest)<<shift|fraction, pow10, shift, ε) + if !ok { + return false + } + // Trim trailing zeros. + for i := d.nd - 1; i >= 0; i-- { + if d.d[i] != '0' { + d.nd = i + 1 + break + } + } + return true +} + +// adjustLastDigitFixed assumes d contains the representation of the integral part +// of some number, whose fractional part is num / (den << shift). The numerator +// num is only known up to an uncertainty of size ε, assumed to be less than +// (den << shift)/2. +// +// It will increase the last digit by one to account for correct rounding, typically +// when the fractional part is greater than 1/2, and will return false if ε is such +// that no correct answer can be given. +func adjustLastDigitFixed(d *decimalSlice, num, den uint64, shift uint, ε uint64) bool { + if num > den<<shift { + panic("strconv: num > den<<shift in adjustLastDigitFixed") + } + if 2*ε > den<<shift { + panic("strconv: ε > (den<<shift)/2") + } + if 2*(num+ε) < den<<shift { + return true + } + if 2*(num-ε) > den<<shift { + // increment d by 1. + i := d.nd - 1 + for ; i >= 0; i-- { + if d.d[i] == '9' { + d.nd-- + } else { + break + } + } + if i < 0 { + d.d[0] = '1' + d.nd = 1 + d.dp++ + } else { + d.d[i]++ + } + return true + } + return false +} + +// 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 *decimalSlice, lower, upper *extFloat) bool { + if f.mant == 0 { + d.nd = 0 + d.dp = 0 + d.neg = f.neg + return true + } + if f.exp == 0 && *lower == *f && *lower == *upper { + // an exact integer. + var buf [24]byte + n := len(buf) - 1 + for v := f.mant; v > 0; { + v1 := v / 10 + v -= 10 * v1 + buf[n] = byte(v + '0') + n-- + v = v1 + } + nd := len(buf) - n - 1 + for i := 0; i < nd; i++ { + d.d[i] = buf[n+1+i] + } + d.nd, d.dp = nd, nd + for d.nd > 0 && d.d[d.nd-1] == '0' { + d.nd-- + } + if d.nd == 0 { + d.dp = 0 + } + d.neg = f.neg + return true + } + 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(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 := 0, uint64(1); i < 20; i++ { + if pow > uint64(integer) { + integerDigits = i + break + } + pow *= 10 + } + 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) + } + } +} + +// 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 *decimalSlice, currentDiff, targetDiff, maxDiff, ulpDecimal, ulpBinary uint64) bool { + if ulpDecimal < 2*ulpBinary { + // Approximation 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/src/strconv/fp_test.go b/src/strconv/fp_test.go new file mode 100644 index 000000000..6de2f8bc6 --- /dev/null +++ b/src/strconv/fp_test.go @@ -0,0 +1,144 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package strconv_test + +import ( + "bufio" + "fmt" + "os" + "strconv" + "strings" + "testing" +) + +func pow2(i int) float64 { + switch { + case i < 0: + return 1 / pow2(-i) + case i == 0: + return 1 + case i == 1: + return 2 + } + return pow2(i/2) * pow2(i-i/2) +} + +// 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 { + n, err := strconv.ParseInt(a[0], 10, 64) + if err != nil { + return 0, false + } + e, err1 := strconv.Atoi(a[1]) + if err1 != nil { + println("bad e", a[1]) + return 0, false + } + v := float64(n) + // We expect that v*pow2(e) fits in a float64, + // but pow2(e) by itself may not. Be careful. + if e <= -1000 { + v *= pow2(-1000) + e += 1000 + for e < 0 { + v /= 2 + e++ + } + return v, true + } + if e >= 1000 { + v *= pow2(1000) + e -= 1000 + for e > 0 { + v *= 2 + e-- + } + return v, true + } + return v * pow2(e), true + } + f1, err := strconv.ParseFloat(s, 64) + if err != nil { + return 0, false + } + return f1, true +} + +// 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 { + n, err := strconv.Atoi(a[0]) + if err != nil { + println("bad n", a[0]) + return 0, false + } + e, err1 := strconv.Atoi(a[1]) + if err1 != nil { + println("bad p", a[1]) + return 0, false + } + return float32(float64(n) * pow2(e)), true + } + f64, err1 := strconv.ParseFloat(s, 32) + f1 := float32(f64) + if err1 != nil { + return 0, false + } + return f1, true +} + +func TestFp(t *testing.T) { + f, err := os.Open("testdata/testfp.txt") + if err != nil { + t.Fatal("testfp: open testdata/testfp.txt:", err) + } + defer f.Close() + + s := bufio.NewScanner(f) + + for lineno := 1; s.Scan(); lineno++ { + line := s.Text() + if len(line) == 0 || line[0] == '#' { + continue + } + a := strings.Split(line, " ") + if len(a) != 4 { + t.Error("testdata/testfp.txt:", lineno, ": wrong field count") + continue + } + var s string + var v float64 + switch a[0] { + case "float64": + var ok bool + v, ok = myatof64(a[2]) + if !ok { + t.Error("testdata/testfp.txt:", lineno, ": cannot atof64 ", a[2]) + continue + } + s = fmt.Sprintf(a[1], v) + case "float32": + v1, ok := myatof32(a[2]) + if !ok { + t.Error("testdata/testfp.txt:", lineno, ": cannot atof32 ", a[2]) + continue + } + s = fmt.Sprintf(a[1], v1) + v = float64(v1) + } + if s != a[3] { + t.Error("testdata/testfp.txt:", lineno, ": ", a[0], " ", a[1], " ", a[2], " (", v, ") ", + "want ", a[3], " got ", s) + } + } + if s.Err() != nil { + t.Fatal("testfp: read testdata/testfp.txt: ", s.Err()) + } +} diff --git a/src/strconv/ftoa.go b/src/strconv/ftoa.go new file mode 100644 index 000000000..1a9c41b85 --- /dev/null +++ b/src/strconv/ftoa.go @@ -0,0 +1,475 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Binary to decimal floating point conversion. +// Algorithm: +// 1) store mantissa in multiprecision decimal +// 2) shift decimal by exponent +// 3) read digits out & format + +package strconv + +import "math" + +// TODO: move elsewhere? +type floatInfo struct { + mantbits uint + expbits uint + bias int +} + +var float32info = floatInfo{23, 8, -127} +var float64info = floatInfo{52, 11, -1023} + +// FormatFloat converts the floating-point number f to a string, +// according to the format fmt and precision prec. It rounds the +// result assuming that the original was obtained from a floating-point +// value of bitSize bits (32 for float32, 64 for float64). +// +// The format fmt is one of +// 'b' (-ddddp±ddd, a binary exponent), +// 'e' (-d.dddde±dd, a decimal exponent), +// 'E' (-d.ddddE±dd, a decimal exponent), +// 'f' (-ddd.dddd, no exponent), +// 'g' ('e' for large exponents, 'f' otherwise), or +// 'G' ('E' for large exponents, 'f' otherwise). +// +// The precision prec controls the number of digits +// (excluding the exponent) printed by the 'e', 'E', 'f', 'g', and 'G' formats. +// For 'e', 'E', and 'f' it is the number of digits after the decimal point. +// For 'g' and 'G' it is the total number of digits. +// The special precision -1 uses the smallest number of digits +// necessary such that ParseFloat will return f exactly. +func FormatFloat(f float64, fmt byte, prec, bitSize int) string { + return string(genericFtoa(make([]byte, 0, max(prec+4, 24)), f, fmt, prec, bitSize)) +} + +// AppendFloat appends the string form of the floating-point number f, +// as generated by FormatFloat, to dst and returns the extended buffer. +func AppendFloat(dst []byte, f float64, fmt byte, prec int, bitSize int) []byte { + return genericFtoa(dst, f, fmt, prec, bitSize) +} + +func genericFtoa(dst []byte, val float64, fmt byte, prec, bitSize int) []byte { + var bits uint64 + var flt *floatInfo + switch bitSize { + case 32: + bits = uint64(math.Float32bits(float32(val))) + flt = &float32info + case 64: + bits = math.Float64bits(val) + flt = &float64info + default: + panic("strconv: illegal AppendFloat/FormatFloat bitSize") + } + + neg := bits>>(flt.expbits+flt.mantbits) != 0 + exp := int(bits>>flt.mantbits) & (1<<flt.expbits - 1) + mant := bits & (uint64(1)<<flt.mantbits - 1) + + switch exp { + case 1<<flt.expbits - 1: + // Inf, NaN + var s string + switch { + case mant != 0: + s = "NaN" + case neg: + s = "-Inf" + default: + s = "+Inf" + } + return append(dst, s...) + + case 0: + // denormalized + exp++ + + default: + // add implicit top bit + mant |= uint64(1) << flt.mantbits + } + exp += flt.bias + + // Pick off easy binary format. + if fmt == 'b' { + return fmtB(dst, neg, mant, exp, flt) + } + + if !optimize { + return bigFtoa(dst, prec, fmt, neg, mant, exp, flt) + } + + var digs decimalSlice + ok := false + // Negative precision means "only as much as needed to be exact." + shortest := prec < 0 + if shortest { + // Try Grisu3 algorithm. + f := new(extFloat) + lower, upper := f.AssignComputeBounds(mant, exp, neg, flt) + var buf [32]byte + digs.d = buf[:] + ok = f.ShortestDecimal(&digs, &lower, &upper) + if !ok { + return bigFtoa(dst, prec, fmt, neg, mant, exp, flt) + } + // Precision for shortest representation mode. + switch fmt { + case 'e', 'E': + prec = digs.nd - 1 + case 'f': + prec = max(digs.nd-digs.dp, 0) + case 'g', 'G': + prec = digs.nd + } + } else if fmt != 'f' { + // Fixed number of digits. + digits := prec + switch fmt { + case 'e', 'E': + digits++ + case 'g', 'G': + if prec == 0 { + prec = 1 + } + digits = prec + } + if digits <= 15 { + // try fast algorithm when the number of digits is reasonable. + var buf [24]byte + digs.d = buf[:] + f := extFloat{mant, exp - int(flt.mantbits), neg} + ok = f.FixedDecimal(&digs, digits) + } + } + if !ok { + return bigFtoa(dst, prec, fmt, neg, mant, exp, flt) + } + return formatDigits(dst, shortest, neg, digs, prec, fmt) +} + +// bigFtoa uses multiprecision computations to format a float. +func bigFtoa(dst []byte, prec int, fmt byte, neg bool, mant uint64, exp int, flt *floatInfo) []byte { + d := new(decimal) + d.Assign(mant) + d.Shift(exp - int(flt.mantbits)) + var digs decimalSlice + shortest := prec < 0 + if shortest { + roundShortest(d, mant, exp, flt) + digs = decimalSlice{d: d.d[:], nd: d.nd, dp: d.dp} + // Precision for shortest representation mode. + switch fmt { + case 'e', 'E': + prec = digs.nd - 1 + case 'f': + prec = max(digs.nd-digs.dp, 0) + case 'g', 'G': + prec = digs.nd + } + } else { + // Round appropriately. + switch fmt { + case 'e', 'E': + d.Round(prec + 1) + case 'f': + d.Round(d.dp + prec) + case 'g', 'G': + if prec == 0 { + prec = 1 + } + d.Round(prec) + } + digs = decimalSlice{d: d.d[:], nd: d.nd, dp: d.dp} + } + return formatDigits(dst, shortest, neg, digs, prec, fmt) +} + +func formatDigits(dst []byte, shortest bool, neg bool, digs decimalSlice, prec int, fmt byte) []byte { + switch fmt { + case 'e', 'E': + return fmtE(dst, neg, digs, prec, fmt) + case 'f': + return fmtF(dst, neg, digs, prec) + case 'g', 'G': + // trailing fractional zeros in 'e' form will be trimmed. + eprec := prec + if eprec > digs.nd && digs.nd >= digs.dp { + eprec = digs.nd + } + // %e is used if the exponent from the conversion + // is less than -4 or greater than or equal to the precision. + // if precision was the shortest possible, use precision 6 for this decision. + if shortest { + eprec = 6 + } + exp := digs.dp - 1 + if exp < -4 || exp >= eprec { + if prec > digs.nd { + prec = digs.nd + } + return fmtE(dst, neg, digs, prec-1, fmt+'e'-'g') + } + if prec > digs.dp { + prec = digs.nd + } + return fmtF(dst, neg, digs, max(prec-digs.dp, 0)) + } + + // unknown format + return append(dst, '%', fmt) +} + +// Round d (= mant * 2^exp) to the shortest number of digits +// that will let the original floating point value be precisely +// reconstructed. Size is original floating point size (64 or 32). +func roundShortest(d *decimal, mant uint64, exp int, flt *floatInfo) { + // If mantissa is zero, the number is zero; stop now. + if mant == 0 { + d.nd = 0 + return + } + + // 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 between, mant*2+1 << exp-mantbits-1. + upper := new(decimal) + upper.Assign(mant*2 + 1) + upper.Shift(exp - int(flt.mantbits) - 1) + + // d = mant << (exp - mantbits) + // Next lowest floating point number is mant-1 << exp-mantbits, + // unless mant-1 drops the significant bit and exp is not the minimum exp, + // 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 between, mantlo*2+1 << explo-mantbits-1. + var mantlo uint64 + var explo int + if mant > 1<<flt.mantbits || exp == minexp { + mantlo = mant - 1 + explo = exp + } else { + mantlo = mant*2 - 1 + explo = exp - 1 + } + lower := new(decimal) + lower.Assign(mantlo*2 + 1) + lower.Shift(explo - int(flt.mantbits) - 1) + + // The upper and lower bounds are possible outputs only if + // the original mantissa is even, so that IEEE round-to-even + // would round to the original mantissa and not the neighbors. + inclusive := mant%2 == 0 + + // Now we can figure out the minimum number of digits required. + // Walk along until d has distinguished itself from upper and lower. + for i := 0; i < d.nd; i++ { + var l, m, u byte // lower, middle, upper digits + if i < lower.nd { + l = lower.d[i] + } else { + l = '0' + } + m = d.d[i] + if i < upper.nd { + u = upper.d[i] + } else { + u = '0' + } + + // Okay to round down (truncate) if lower has a different digit + // or if lower is inclusive and is exactly the result of rounding down. + okdown := l != m || (inclusive && l == m && i+1 == lower.nd) + + // 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 || 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. + switch { + case okdown && okup: + d.Round(i + 1) + return + case okdown: + d.RoundDown(i + 1) + return + case okup: + d.RoundUp(i + 1) + return + } + } +} + +type decimalSlice struct { + d []byte + nd, dp int + neg bool +} + +// %e: -d.ddddde±dd +func fmtE(dst []byte, neg bool, d decimalSlice, prec int, fmt byte) []byte { + // sign + if neg { + dst = append(dst, '-') + } + + // first digit + ch := byte('0') + if d.nd != 0 { + ch = d.d[0] + } + dst = append(dst, ch) + + // .moredigits + if prec > 0 { + dst = append(dst, '.') + i := 1 + m := d.nd + prec + 1 - max(d.nd, prec+1) + for i < m { + dst = append(dst, d.d[i]) + i++ + } + for i <= prec { + dst = append(dst, '0') + i++ + } + } + + // e± + dst = append(dst, fmt) + exp := d.dp - 1 + if d.nd == 0 { // special case: 0 has exponent 0 + exp = 0 + } + if exp < 0 { + ch = '-' + exp = -exp + } else { + ch = '+' + } + dst = append(dst, ch) + + // dddd + var buf [3]byte + i := len(buf) + for exp >= 10 { + i-- + buf[i] = byte(exp%10 + '0') + exp /= 10 + } + // exp < 10 + i-- + buf[i] = byte(exp + '0') + + switch i { + case 0: + dst = append(dst, buf[0], buf[1], buf[2]) + case 1: + dst = append(dst, buf[1], buf[2]) + case 2: + // leading zeroes + dst = append(dst, '0', buf[2]) + } + return dst +} + +// %f: -ddddddd.ddddd +func fmtF(dst []byte, neg bool, d decimalSlice, prec int) []byte { + // sign + if neg { + dst = append(dst, '-') + } + + // integer, padded with zeros as needed. + if d.dp > 0 { + var i int + for i = 0; i < d.dp && i < d.nd; i++ { + dst = append(dst, d.d[i]) + } + for ; i < d.dp; i++ { + dst = append(dst, '0') + } + } else { + dst = append(dst, '0') + } + + // fraction + if prec > 0 { + dst = append(dst, '.') + for i := 0; i < prec; i++ { + ch := byte('0') + if j := d.dp + i; 0 <= j && j < d.nd { + ch = d.d[j] + } + dst = append(dst, ch) + } + } + + return dst +} + +// %b: -ddddddddp+ddd +func fmtB(dst []byte, neg bool, mant uint64, exp int, flt *floatInfo) []byte { + var buf [50]byte + w := len(buf) + exp -= int(flt.mantbits) + esign := byte('+') + if exp < 0 { + esign = '-' + exp = -exp + } + n := 0 + for exp > 0 || n < 1 { + n++ + w-- + buf[w] = byte(exp%10 + '0') + exp /= 10 + } + w-- + buf[w] = esign + w-- + buf[w] = 'p' + n = 0 + for mant > 0 || n < 1 { + n++ + w-- + buf[w] = byte(mant%10 + '0') + mant /= 10 + } + if neg { + w-- + buf[w] = '-' + } + return append(dst, buf[w:]...) +} + +func max(a, b int) int { + if a > b { + return a + } + return b +} diff --git a/src/strconv/ftoa_test.go b/src/strconv/ftoa_test.go new file mode 100644 index 000000000..39b861547 --- /dev/null +++ b/src/strconv/ftoa_test.go @@ -0,0 +1,240 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package strconv_test + +import ( + "math" + "math/rand" + . "strconv" + "testing" +) + +type ftoaTest struct { + f float64 + fmt byte + prec int + s string +} + +func fdiv(a, b float64) float64 { return a / b } // keep compiler in the dark + +const ( + below1e23 = 99999999999999974834176 + above1e23 = 100000000000000008388608 +) + +var ftoatests = []ftoaTest{ + {1, 'e', 5, "1.00000e+00"}, + {1, 'f', 5, "1.00000"}, + {1, 'g', 5, "1"}, + {1, 'g', -1, "1"}, + {20, 'g', -1, "20"}, + {1234567.8, 'g', -1, "1.2345678e+06"}, + {200000, 'g', -1, "200000"}, + {2000000, 'g', -1, "2e+06"}, + + // g conversion and zero suppression + {400, 'g', 2, "4e+02"}, + {40, 'g', 2, "40"}, + {4, 'g', 2, "4"}, + {.4, 'g', 2, "0.4"}, + {.04, 'g', 2, "0.04"}, + {.004, 'g', 2, "0.004"}, + {.0004, 'g', 2, "0.0004"}, + {.00004, 'g', 2, "4e-05"}, + {.000004, 'g', 2, "4e-06"}, + + {0, 'e', 5, "0.00000e+00"}, + {0, 'f', 5, "0.00000"}, + {0, 'g', 5, "0"}, + {0, 'g', -1, "0"}, + + {-1, 'e', 5, "-1.00000e+00"}, + {-1, 'f', 5, "-1.00000"}, + {-1, 'g', 5, "-1"}, + {-1, 'g', -1, "-1"}, + + {12, 'e', 5, "1.20000e+01"}, + {12, 'f', 5, "12.00000"}, + {12, 'g', 5, "12"}, + {12, 'g', -1, "12"}, + + {123456700, 'e', 5, "1.23457e+08"}, + {123456700, 'f', 5, "123456700.00000"}, + {123456700, 'g', 5, "1.2346e+08"}, + {123456700, 'g', -1, "1.234567e+08"}, + + {1.2345e6, 'e', 5, "1.23450e+06"}, + {1.2345e6, 'f', 5, "1234500.00000"}, + {1.2345e6, 'g', 5, "1.2345e+06"}, + + {1e23, 'e', 17, "9.99999999999999916e+22"}, + {1e23, 'f', 17, "99999999999999991611392.00000000000000000"}, + {1e23, 'g', 17, "9.9999999999999992e+22"}, + + {1e23, 'e', -1, "1e+23"}, + {1e23, 'f', -1, "100000000000000000000000"}, + {1e23, 'g', -1, "1e+23"}, + + {below1e23, 'e', 17, "9.99999999999999748e+22"}, + {below1e23, 'f', 17, "99999999999999974834176.00000000000000000"}, + {below1e23, 'g', 17, "9.9999999999999975e+22"}, + + {below1e23, 'e', -1, "9.999999999999997e+22"}, + {below1e23, 'f', -1, "99999999999999970000000"}, + {below1e23, 'g', -1, "9.999999999999997e+22"}, + + {above1e23, 'e', 17, "1.00000000000000008e+23"}, + {above1e23, 'f', 17, "100000000000000008388608.00000000000000000"}, + {above1e23, 'g', 17, "1.0000000000000001e+23"}, + + {above1e23, 'e', -1, "1.0000000000000001e+23"}, + {above1e23, 'f', -1, "100000000000000010000000"}, + {above1e23, 'g', -1, "1.0000000000000001e+23"}, + + {fdiv(5e-304, 1e20), 'g', -1, "5e-324"}, + {fdiv(-5e-304, 1e20), 'g', -1, "-5e-324"}, + + {32, 'g', -1, "32"}, + {32, 'g', 0, "3e+01"}, + + {100, 'x', -1, "%x"}, + + {math.NaN(), 'g', -1, "NaN"}, + {-math.NaN(), 'g', -1, "NaN"}, + {math.Inf(0), 'g', -1, "+Inf"}, + {math.Inf(-1), 'g', -1, "-Inf"}, + {-math.Inf(0), 'g', -1, "-Inf"}, + + {-1, 'b', -1, "-4503599627370496p-52"}, + + // fixed bugs + {0.9, 'f', 1, "0.9"}, + {0.09, 'f', 1, "0.1"}, + {0.0999, 'f', 1, "0.1"}, + {0.05, 'f', 1, "0.1"}, + {0.05, 'f', 0, "0"}, + {0.5, 'f', 1, "0.5"}, + {0.5, 'f', 0, "0"}, + {1.5, 'f', 0, "2"}, + + // http://www.exploringbinary.com/java-hangs-when-converting-2-2250738585072012e-308/ + {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) { + for i := 0; i < len(ftoatests); i++ { + test := &ftoatests[i] + s := FormatFloat(test.f, test.fmt, test.prec, 64) + if s != test.s { + t.Error("testN=64", test.f, string(test.fmt), test.prec, "want", test.s, "got", s) + } + x := AppendFloat([]byte("abc"), test.f, test.fmt, test.prec, 64) + if string(x) != "abc"+test.s { + t.Error("AppendFloat testN=64", test.f, string(test.fmt), test.prec, "want", "abc"+test.s, "got", string(x)) + } + if float64(float32(test.f)) == test.f && test.fmt != 'b' { + s := FormatFloat(test.f, test.fmt, test.prec, 32) + if s != test.s { + t.Error("testN=32", test.f, string(test.fmt), test.prec, "want", test.s, "got", s) + } + x := AppendFloat([]byte("abc"), test.f, test.fmt, test.prec, 32) + if string(x) != "abc"+test.s { + t.Error("AppendFloat testN=32", test.f, string(test.fmt), test.prec, "want", "abc"+test.s, "got", string(x)) + } + } + } +} + +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) + } + + prec := rand.Intn(12) + 5 + shortFast = FormatFloat(x, 'e', prec, 64) + SetOptimize(false) + shortSlow = FormatFloat(x, 'e', prec, 64) + SetOptimize(true) + if shortSlow != shortFast { + t.Errorf("%b printed as %s, want %s", x, shortFast, shortSlow) + } + } +} + +func BenchmarkFormatFloatDecimal(b *testing.B) { + for i := 0; i < b.N; i++ { + FormatFloat(33909, 'g', -1, 64) + } +} + +func BenchmarkFormatFloat(b *testing.B) { + for i := 0; i < b.N; i++ { + FormatFloat(339.7784, 'g', -1, 64) + } +} + +func BenchmarkFormatFloatExp(b *testing.B) { + for i := 0; i < b.N; i++ { + FormatFloat(-5.09e75, 'g', -1, 64) + } +} + +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) + } +} + +func benchmarkAppendFloat(b *testing.B, f float64, fmt byte, prec, bitSize int) { + dst := make([]byte, 30) + for i := 0; i < b.N; i++ { + AppendFloat(dst[:0], f, fmt, prec, bitSize) + } +} + +func BenchmarkAppendFloatDecimal(b *testing.B) { benchmarkAppendFloat(b, 33909, 'g', -1, 64) } +func BenchmarkAppendFloat(b *testing.B) { benchmarkAppendFloat(b, 339.7784, 'g', -1, 64) } +func BenchmarkAppendFloatExp(b *testing.B) { benchmarkAppendFloat(b, -5.09e75, 'g', -1, 64) } +func BenchmarkAppendFloatNegExp(b *testing.B) { benchmarkAppendFloat(b, -5.11e-95, 'g', -1, 64) } +func BenchmarkAppendFloatBig(b *testing.B) { + benchmarkAppendFloat(b, 123456789123456789123456789, 'g', -1, 64) +} + +func BenchmarkAppendFloat32Integer(b *testing.B) { benchmarkAppendFloat(b, 33909, 'g', -1, 32) } +func BenchmarkAppendFloat32ExactFraction(b *testing.B) { benchmarkAppendFloat(b, 3.375, 'g', -1, 32) } +func BenchmarkAppendFloat32Point(b *testing.B) { benchmarkAppendFloat(b, 339.7784, 'g', -1, 32) } +func BenchmarkAppendFloat32Exp(b *testing.B) { benchmarkAppendFloat(b, -5.09e25, 'g', -1, 32) } +func BenchmarkAppendFloat32NegExp(b *testing.B) { benchmarkAppendFloat(b, -5.11e-25, 'g', -1, 32) } + +func BenchmarkAppendFloat64Fixed1(b *testing.B) { benchmarkAppendFloat(b, 123456, 'e', 3, 64) } +func BenchmarkAppendFloat64Fixed2(b *testing.B) { benchmarkAppendFloat(b, 123.456, 'e', 3, 64) } +func BenchmarkAppendFloat64Fixed3(b *testing.B) { benchmarkAppendFloat(b, 1.23456e+78, 'e', 3, 64) } +func BenchmarkAppendFloat64Fixed4(b *testing.B) { benchmarkAppendFloat(b, 1.23456e-78, 'e', 3, 64) } diff --git a/src/strconv/internal_test.go b/src/strconv/internal_test.go new file mode 100644 index 000000000..d0fa80edf --- /dev/null +++ b/src/strconv/internal_test.go @@ -0,0 +1,19 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// export access to strconv internals for tests + +package strconv + +func NewDecimal(i uint64) *decimal { + d := new(decimal) + d.Assign(i) + return d +} + +func SetOptimize(b bool) bool { + old := optimize + optimize = b + return old +} diff --git a/src/strconv/isprint.go b/src/strconv/isprint.go new file mode 100644 index 000000000..80738ed71 --- /dev/null +++ b/src/strconv/isprint.go @@ -0,0 +1,624 @@ +// Copyright 2013 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// DO NOT EDIT. GENERATED BY +// go run makeisprint.go -output isprint.go + +package strconv + +// (468+138+67)*2 + (326)*4 = 2650 bytes + +var isPrint16 = []uint16{ + 0x0020, 0x007e, + 0x00a1, 0x0377, + 0x037a, 0x037f, + 0x0384, 0x0556, + 0x0559, 0x058a, + 0x058d, 0x05c7, + 0x05d0, 0x05ea, + 0x05f0, 0x05f4, + 0x0606, 0x061b, + 0x061e, 0x070d, + 0x0710, 0x074a, + 0x074d, 0x07b1, + 0x07c0, 0x07fa, + 0x0800, 0x082d, + 0x0830, 0x085b, + 0x085e, 0x085e, + 0x08a0, 0x08b2, + 0x08e4, 0x098c, + 0x098f, 0x0990, + 0x0993, 0x09b2, + 0x09b6, 0x09b9, + 0x09bc, 0x09c4, + 0x09c7, 0x09c8, + 0x09cb, 0x09ce, + 0x09d7, 0x09d7, + 0x09dc, 0x09e3, + 0x09e6, 0x09fb, + 0x0a01, 0x0a0a, + 0x0a0f, 0x0a10, + 0x0a13, 0x0a39, + 0x0a3c, 0x0a42, + 0x0a47, 0x0a48, + 0x0a4b, 0x0a4d, + 0x0a51, 0x0a51, + 0x0a59, 0x0a5e, + 0x0a66, 0x0a75, + 0x0a81, 0x0ab9, + 0x0abc, 0x0acd, + 0x0ad0, 0x0ad0, + 0x0ae0, 0x0ae3, + 0x0ae6, 0x0af1, + 0x0b01, 0x0b0c, + 0x0b0f, 0x0b10, + 0x0b13, 0x0b39, + 0x0b3c, 0x0b44, + 0x0b47, 0x0b48, + 0x0b4b, 0x0b4d, + 0x0b56, 0x0b57, + 0x0b5c, 0x0b63, + 0x0b66, 0x0b77, + 0x0b82, 0x0b8a, + 0x0b8e, 0x0b95, + 0x0b99, 0x0b9f, + 0x0ba3, 0x0ba4, + 0x0ba8, 0x0baa, + 0x0bae, 0x0bb9, + 0x0bbe, 0x0bc2, + 0x0bc6, 0x0bcd, + 0x0bd0, 0x0bd0, + 0x0bd7, 0x0bd7, + 0x0be6, 0x0bfa, + 0x0c00, 0x0c39, + 0x0c3d, 0x0c4d, + 0x0c55, 0x0c59, + 0x0c60, 0x0c63, + 0x0c66, 0x0c6f, + 0x0c78, 0x0cb9, + 0x0cbc, 0x0ccd, + 0x0cd5, 0x0cd6, + 0x0cde, 0x0ce3, + 0x0ce6, 0x0cf2, + 0x0d01, 0x0d3a, + 0x0d3d, 0x0d4e, + 0x0d57, 0x0d57, + 0x0d60, 0x0d63, + 0x0d66, 0x0d75, + 0x0d79, 0x0d7f, + 0x0d82, 0x0d96, + 0x0d9a, 0x0dbd, + 0x0dc0, 0x0dc6, + 0x0dca, 0x0dca, + 0x0dcf, 0x0ddf, + 0x0de6, 0x0def, + 0x0df2, 0x0df4, + 0x0e01, 0x0e3a, + 0x0e3f, 0x0e5b, + 0x0e81, 0x0e84, + 0x0e87, 0x0e8a, + 0x0e8d, 0x0e8d, + 0x0e94, 0x0ea7, + 0x0eaa, 0x0ebd, + 0x0ec0, 0x0ecd, + 0x0ed0, 0x0ed9, + 0x0edc, 0x0edf, + 0x0f00, 0x0f6c, + 0x0f71, 0x0fda, + 0x1000, 0x10c7, + 0x10cd, 0x10cd, + 0x10d0, 0x124d, + 0x1250, 0x125d, + 0x1260, 0x128d, + 0x1290, 0x12b5, + 0x12b8, 0x12c5, + 0x12c8, 0x1315, + 0x1318, 0x135a, + 0x135d, 0x137c, + 0x1380, 0x1399, + 0x13a0, 0x13f4, + 0x1400, 0x169c, + 0x16a0, 0x16f8, + 0x1700, 0x1714, + 0x1720, 0x1736, + 0x1740, 0x1753, + 0x1760, 0x1773, + 0x1780, 0x17dd, + 0x17e0, 0x17e9, + 0x17f0, 0x17f9, + 0x1800, 0x180d, + 0x1810, 0x1819, + 0x1820, 0x1877, + 0x1880, 0x18aa, + 0x18b0, 0x18f5, + 0x1900, 0x192b, + 0x1930, 0x193b, + 0x1940, 0x1940, + 0x1944, 0x196d, + 0x1970, 0x1974, + 0x1980, 0x19ab, + 0x19b0, 0x19c9, + 0x19d0, 0x19da, + 0x19de, 0x1a1b, + 0x1a1e, 0x1a7c, + 0x1a7f, 0x1a89, + 0x1a90, 0x1a99, + 0x1aa0, 0x1aad, + 0x1ab0, 0x1abe, + 0x1b00, 0x1b4b, + 0x1b50, 0x1b7c, + 0x1b80, 0x1bf3, + 0x1bfc, 0x1c37, + 0x1c3b, 0x1c49, + 0x1c4d, 0x1c7f, + 0x1cc0, 0x1cc7, + 0x1cd0, 0x1cf9, + 0x1d00, 0x1df5, + 0x1dfc, 0x1f15, + 0x1f18, 0x1f1d, + 0x1f20, 0x1f45, + 0x1f48, 0x1f4d, + 0x1f50, 0x1f7d, + 0x1f80, 0x1fd3, + 0x1fd6, 0x1fef, + 0x1ff2, 0x1ffe, + 0x2010, 0x2027, + 0x2030, 0x205e, + 0x2070, 0x2071, + 0x2074, 0x209c, + 0x20a0, 0x20bd, + 0x20d0, 0x20f0, + 0x2100, 0x2189, + 0x2190, 0x23fa, + 0x2400, 0x2426, + 0x2440, 0x244a, + 0x2460, 0x2b73, + 0x2b76, 0x2b95, + 0x2b98, 0x2bb9, + 0x2bbd, 0x2bd1, + 0x2c00, 0x2cf3, + 0x2cf9, 0x2d27, + 0x2d2d, 0x2d2d, + 0x2d30, 0x2d67, + 0x2d6f, 0x2d70, + 0x2d7f, 0x2d96, + 0x2da0, 0x2e42, + 0x2e80, 0x2ef3, + 0x2f00, 0x2fd5, + 0x2ff0, 0x2ffb, + 0x3001, 0x3096, + 0x3099, 0x30ff, + 0x3105, 0x312d, + 0x3131, 0x31ba, + 0x31c0, 0x31e3, + 0x31f0, 0x4db5, + 0x4dc0, 0x9fcc, + 0xa000, 0xa48c, + 0xa490, 0xa4c6, + 0xa4d0, 0xa62b, + 0xa640, 0xa6f7, + 0xa700, 0xa7ad, + 0xa7b0, 0xa7b1, + 0xa7f7, 0xa82b, + 0xa830, 0xa839, + 0xa840, 0xa877, + 0xa880, 0xa8c4, + 0xa8ce, 0xa8d9, + 0xa8e0, 0xa8fb, + 0xa900, 0xa953, + 0xa95f, 0xa97c, + 0xa980, 0xa9d9, + 0xa9de, 0xaa36, + 0xaa40, 0xaa4d, + 0xaa50, 0xaa59, + 0xaa5c, 0xaac2, + 0xaadb, 0xaaf6, + 0xab01, 0xab06, + 0xab09, 0xab0e, + 0xab11, 0xab16, + 0xab20, 0xab5f, + 0xab64, 0xab65, + 0xabc0, 0xabed, + 0xabf0, 0xabf9, + 0xac00, 0xd7a3, + 0xd7b0, 0xd7c6, + 0xd7cb, 0xd7fb, + 0xf900, 0xfa6d, + 0xfa70, 0xfad9, + 0xfb00, 0xfb06, + 0xfb13, 0xfb17, + 0xfb1d, 0xfbc1, + 0xfbd3, 0xfd3f, + 0xfd50, 0xfd8f, + 0xfd92, 0xfdc7, + 0xfdf0, 0xfdfd, + 0xfe00, 0xfe19, + 0xfe20, 0xfe2d, + 0xfe30, 0xfe6b, + 0xfe70, 0xfefc, + 0xff01, 0xffbe, + 0xffc2, 0xffc7, + 0xffca, 0xffcf, + 0xffd2, 0xffd7, + 0xffda, 0xffdc, + 0xffe0, 0xffee, + 0xfffc, 0xfffd, +} + +var isNotPrint16 = []uint16{ + 0x00ad, + 0x038b, + 0x038d, + 0x03a2, + 0x0530, + 0x0560, + 0x0588, + 0x0590, + 0x06dd, + 0x083f, + 0x0984, + 0x09a9, + 0x09b1, + 0x09de, + 0x0a04, + 0x0a29, + 0x0a31, + 0x0a34, + 0x0a37, + 0x0a3d, + 0x0a5d, + 0x0a84, + 0x0a8e, + 0x0a92, + 0x0aa9, + 0x0ab1, + 0x0ab4, + 0x0ac6, + 0x0aca, + 0x0b04, + 0x0b29, + 0x0b31, + 0x0b34, + 0x0b5e, + 0x0b84, + 0x0b91, + 0x0b9b, + 0x0b9d, + 0x0bc9, + 0x0c04, + 0x0c0d, + 0x0c11, + 0x0c29, + 0x0c45, + 0x0c49, + 0x0c57, + 0x0c80, + 0x0c84, + 0x0c8d, + 0x0c91, + 0x0ca9, + 0x0cb4, + 0x0cc5, + 0x0cc9, + 0x0cdf, + 0x0cf0, + 0x0d04, + 0x0d0d, + 0x0d11, + 0x0d45, + 0x0d49, + 0x0d84, + 0x0db2, + 0x0dbc, + 0x0dd5, + 0x0dd7, + 0x0e83, + 0x0e89, + 0x0e98, + 0x0ea0, + 0x0ea4, + 0x0ea6, + 0x0eac, + 0x0eba, + 0x0ec5, + 0x0ec7, + 0x0f48, + 0x0f98, + 0x0fbd, + 0x0fcd, + 0x10c6, + 0x1249, + 0x1257, + 0x1259, + 0x1289, + 0x12b1, + 0x12bf, + 0x12c1, + 0x12d7, + 0x1311, + 0x1680, + 0x170d, + 0x176d, + 0x1771, + 0x191f, + 0x1a5f, + 0x1cf7, + 0x1f58, + 0x1f5a, + 0x1f5c, + 0x1f5e, + 0x1fb5, + 0x1fc5, + 0x1fdc, + 0x1ff5, + 0x208f, + 0x2bc9, + 0x2c2f, + 0x2c5f, + 0x2d26, + 0x2da7, + 0x2daf, + 0x2db7, + 0x2dbf, + 0x2dc7, + 0x2dcf, + 0x2dd7, + 0x2ddf, + 0x2e9a, + 0x3040, + 0x318f, + 0x321f, + 0x32ff, + 0xa69e, + 0xa78f, + 0xa9ce, + 0xa9ff, + 0xab27, + 0xab2f, + 0xfb37, + 0xfb3d, + 0xfb3f, + 0xfb42, + 0xfb45, + 0xfe53, + 0xfe67, + 0xfe75, + 0xffe7, +} + +var isPrint32 = []uint32{ + 0x010000, 0x01004d, + 0x010050, 0x01005d, + 0x010080, 0x0100fa, + 0x010100, 0x010102, + 0x010107, 0x010133, + 0x010137, 0x01018c, + 0x010190, 0x01019b, + 0x0101a0, 0x0101a0, + 0x0101d0, 0x0101fd, + 0x010280, 0x01029c, + 0x0102a0, 0x0102d0, + 0x0102e0, 0x0102fb, + 0x010300, 0x010323, + 0x010330, 0x01034a, + 0x010350, 0x01037a, + 0x010380, 0x0103c3, + 0x0103c8, 0x0103d5, + 0x010400, 0x01049d, + 0x0104a0, 0x0104a9, + 0x010500, 0x010527, + 0x010530, 0x010563, + 0x01056f, 0x01056f, + 0x010600, 0x010736, + 0x010740, 0x010755, + 0x010760, 0x010767, + 0x010800, 0x010805, + 0x010808, 0x010838, + 0x01083c, 0x01083c, + 0x01083f, 0x01089e, + 0x0108a7, 0x0108af, + 0x010900, 0x01091b, + 0x01091f, 0x010939, + 0x01093f, 0x01093f, + 0x010980, 0x0109b7, + 0x0109be, 0x0109bf, + 0x010a00, 0x010a06, + 0x010a0c, 0x010a33, + 0x010a38, 0x010a3a, + 0x010a3f, 0x010a47, + 0x010a50, 0x010a58, + 0x010a60, 0x010a9f, + 0x010ac0, 0x010ae6, + 0x010aeb, 0x010af6, + 0x010b00, 0x010b35, + 0x010b39, 0x010b55, + 0x010b58, 0x010b72, + 0x010b78, 0x010b91, + 0x010b99, 0x010b9c, + 0x010ba9, 0x010baf, + 0x010c00, 0x010c48, + 0x010e60, 0x010e7e, + 0x011000, 0x01104d, + 0x011052, 0x01106f, + 0x01107f, 0x0110c1, + 0x0110d0, 0x0110e8, + 0x0110f0, 0x0110f9, + 0x011100, 0x011143, + 0x011150, 0x011176, + 0x011180, 0x0111c8, + 0x0111cd, 0x0111cd, + 0x0111d0, 0x0111da, + 0x0111e1, 0x0111f4, + 0x011200, 0x01123d, + 0x0112b0, 0x0112ea, + 0x0112f0, 0x0112f9, + 0x011301, 0x01130c, + 0x01130f, 0x011310, + 0x011313, 0x011339, + 0x01133c, 0x011344, + 0x011347, 0x011348, + 0x01134b, 0x01134d, + 0x011357, 0x011357, + 0x01135d, 0x011363, + 0x011366, 0x01136c, + 0x011370, 0x011374, + 0x011480, 0x0114c7, + 0x0114d0, 0x0114d9, + 0x011580, 0x0115b5, + 0x0115b8, 0x0115c9, + 0x011600, 0x011644, + 0x011650, 0x011659, + 0x011680, 0x0116b7, + 0x0116c0, 0x0116c9, + 0x0118a0, 0x0118f2, + 0x0118ff, 0x0118ff, + 0x011ac0, 0x011af8, + 0x012000, 0x012398, + 0x012400, 0x012474, + 0x013000, 0x01342e, + 0x016800, 0x016a38, + 0x016a40, 0x016a69, + 0x016a6e, 0x016a6f, + 0x016ad0, 0x016aed, + 0x016af0, 0x016af5, + 0x016b00, 0x016b45, + 0x016b50, 0x016b77, + 0x016b7d, 0x016b8f, + 0x016f00, 0x016f44, + 0x016f50, 0x016f7e, + 0x016f8f, 0x016f9f, + 0x01b000, 0x01b001, + 0x01bc00, 0x01bc6a, + 0x01bc70, 0x01bc7c, + 0x01bc80, 0x01bc88, + 0x01bc90, 0x01bc99, + 0x01bc9c, 0x01bc9f, + 0x01d000, 0x01d0f5, + 0x01d100, 0x01d126, + 0x01d129, 0x01d172, + 0x01d17b, 0x01d1dd, + 0x01d200, 0x01d245, + 0x01d300, 0x01d356, + 0x01d360, 0x01d371, + 0x01d400, 0x01d49f, + 0x01d4a2, 0x01d4a2, + 0x01d4a5, 0x01d4a6, + 0x01d4a9, 0x01d50a, + 0x01d50d, 0x01d546, + 0x01d54a, 0x01d6a5, + 0x01d6a8, 0x01d7cb, + 0x01d7ce, 0x01d7ff, + 0x01e800, 0x01e8c4, + 0x01e8c7, 0x01e8d6, + 0x01ee00, 0x01ee24, + 0x01ee27, 0x01ee3b, + 0x01ee42, 0x01ee42, + 0x01ee47, 0x01ee54, + 0x01ee57, 0x01ee64, + 0x01ee67, 0x01ee9b, + 0x01eea1, 0x01eebb, + 0x01eef0, 0x01eef1, + 0x01f000, 0x01f02b, + 0x01f030, 0x01f093, + 0x01f0a0, 0x01f0ae, + 0x01f0b1, 0x01f0f5, + 0x01f100, 0x01f10c, + 0x01f110, 0x01f16b, + 0x01f170, 0x01f19a, + 0x01f1e6, 0x01f202, + 0x01f210, 0x01f23a, + 0x01f240, 0x01f248, + 0x01f250, 0x01f251, + 0x01f300, 0x01f32c, + 0x01f330, 0x01f37d, + 0x01f380, 0x01f3ce, + 0x01f3d4, 0x01f3f7, + 0x01f400, 0x01f54a, + 0x01f550, 0x01f642, + 0x01f645, 0x01f6cf, + 0x01f6e0, 0x01f6ec, + 0x01f6f0, 0x01f6f3, + 0x01f700, 0x01f773, + 0x01f780, 0x01f7d4, + 0x01f800, 0x01f80b, + 0x01f810, 0x01f847, + 0x01f850, 0x01f859, + 0x01f860, 0x01f887, + 0x01f890, 0x01f8ad, + 0x020000, 0x02a6d6, + 0x02a700, 0x02b734, + 0x02b740, 0x02b81d, + 0x02f800, 0x02fa1d, + 0x0e0100, 0x0e01ef, +} + +var isNotPrint32 = []uint16{ // add 0x10000 to each entry + 0x000c, + 0x0027, + 0x003b, + 0x003e, + 0x039e, + 0x0809, + 0x0836, + 0x0856, + 0x0a04, + 0x0a14, + 0x0a18, + 0x10bd, + 0x1135, + 0x1212, + 0x1304, + 0x1329, + 0x1331, + 0x1334, + 0x246f, + 0x6a5f, + 0x6b5a, + 0x6b62, + 0xd455, + 0xd49d, + 0xd4ad, + 0xd4ba, + 0xd4bc, + 0xd4c4, + 0xd506, + 0xd515, + 0xd51d, + 0xd53a, + 0xd53f, + 0xd545, + 0xd551, + 0xee04, + 0xee20, + 0xee23, + 0xee28, + 0xee33, + 0xee38, + 0xee3a, + 0xee48, + 0xee4a, + 0xee4c, + 0xee50, + 0xee53, + 0xee58, + 0xee5a, + 0xee5c, + 0xee5e, + 0xee60, + 0xee63, + 0xee6b, + 0xee73, + 0xee78, + 0xee7d, + 0xee7f, + 0xee8a, + 0xeea4, + 0xeeaa, + 0xf0c0, + 0xf0d0, + 0xf12f, + 0xf4ff, + 0xf57a, + 0xf5a4, +} diff --git a/src/strconv/itoa.go b/src/strconv/itoa.go new file mode 100644 index 000000000..67f17d866 --- /dev/null +++ b/src/strconv/itoa.go @@ -0,0 +1,131 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package strconv + +// FormatUint returns the string representation of i in the given base, +// for 2 <= base <= 36. The result uses the lower-case letters 'a' to 'z' +// for digit values >= 10. +func FormatUint(i uint64, base int) string { + _, s := formatBits(nil, i, base, false, false) + return s +} + +// FormatInt returns the string representation of i in the given base, +// for 2 <= base <= 36. The result uses the lower-case letters 'a' to 'z' +// for digit values >= 10. +func FormatInt(i int64, base int) string { + _, s := formatBits(nil, uint64(i), base, i < 0, false) + return s +} + +// Itoa is shorthand for FormatInt(i, 10). +func Itoa(i int) string { + return FormatInt(int64(i), 10) +} + +// AppendInt appends the string form of the integer i, +// as generated by FormatInt, to dst and returns the extended buffer. +func AppendInt(dst []byte, i int64, base int) []byte { + dst, _ = formatBits(dst, uint64(i), base, i < 0, true) + return dst +} + +// AppendUint appends the string form of the unsigned integer i, +// as generated by FormatUint, to dst and returns the extended buffer. +func AppendUint(dst []byte, i uint64, base int) []byte { + dst, _ = formatBits(dst, i, base, false, true) + return dst +} + +const ( + digits = "0123456789abcdefghijklmnopqrstuvwxyz" + digits01 = "0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789" + digits10 = "0000000000111111111122222222223333333333444444444455555555556666666666777777777788888888889999999999" +) + +var shifts = [len(digits) + 1]uint{ + 1 << 1: 1, + 1 << 2: 2, + 1 << 3: 3, + 1 << 4: 4, + 1 << 5: 5, +} + +// formatBits computes the string representation of u in the given base. +// If neg is set, u is treated as negative int64 value. If append_ is +// set, the string is appended to dst and the resulting byte slice is +// returned as the first result value; otherwise the string is returned +// as the second result value. +// +func formatBits(dst []byte, u uint64, base int, neg, append_ bool) (d []byte, s string) { + if base < 2 || base > len(digits) { + panic("strconv: illegal AppendInt/FormatInt base") + } + // 2 <= base && base <= len(digits) + + var a [64 + 1]byte // +1 for sign of 64bit value in base 2 + i := len(a) + + if neg { + u = -u + } + + // convert bits + if base == 10 { + // common case: use constants for / and % because + // the compiler can optimize it into a multiply+shift, + // and unroll loop + for u >= 100 { + i -= 2 + q := u / 100 + j := uintptr(u - q*100) + a[i+1] = digits01[j] + a[i+0] = digits10[j] + u = q + } + if u >= 10 { + i-- + q := u / 10 + a[i] = digits[uintptr(u-q*10)] + u = q + } + + } else if s := shifts[base]; s > 0 { + // base is power of 2: use shifts and masks instead of / and % + b := uint64(base) + m := uintptr(b) - 1 // == 1<<s - 1 + for u >= b { + i-- + a[i] = digits[uintptr(u)&m] + u >>= s + } + + } else { + // general case + b := uint64(base) + for u >= b { + i-- + a[i] = digits[uintptr(u%b)] + u /= b + } + } + + // u < base + i-- + a[i] = digits[uintptr(u)] + + // add sign, if any + if neg { + i-- + a[i] = '-' + } + + if append_ { + d = append(dst, a[i:]...) + return + } + s = string(a[i:]) + return +} diff --git a/src/strconv/itoa_test.go b/src/strconv/itoa_test.go new file mode 100644 index 000000000..e0213ae9a --- /dev/null +++ b/src/strconv/itoa_test.go @@ -0,0 +1,160 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package strconv_test + +import ( + . "strconv" + "testing" +) + +type itob64Test struct { + in int64 + base int + out string +} + +var itob64tests = []itob64Test{ + {0, 10, "0"}, + {1, 10, "1"}, + {-1, 10, "-1"}, + {12345678, 10, "12345678"}, + {-987654321, 10, "-987654321"}, + {1<<31 - 1, 10, "2147483647"}, + {-1<<31 + 1, 10, "-2147483647"}, + {1 << 31, 10, "2147483648"}, + {-1 << 31, 10, "-2147483648"}, + {1<<31 + 1, 10, "2147483649"}, + {-1<<31 - 1, 10, "-2147483649"}, + {1<<32 - 1, 10, "4294967295"}, + {-1<<32 + 1, 10, "-4294967295"}, + {1 << 32, 10, "4294967296"}, + {-1 << 32, 10, "-4294967296"}, + {1<<32 + 1, 10, "4294967297"}, + {-1<<32 - 1, 10, "-4294967297"}, + {1 << 50, 10, "1125899906842624"}, + {1<<63 - 1, 10, "9223372036854775807"}, + {-1<<63 + 1, 10, "-9223372036854775807"}, + {-1 << 63, 10, "-9223372036854775808"}, + + {0, 2, "0"}, + {10, 2, "1010"}, + {-1, 2, "-1"}, + {1 << 15, 2, "1000000000000000"}, + + {-8, 8, "-10"}, + {057635436545, 8, "57635436545"}, + {1 << 24, 8, "100000000"}, + + {16, 16, "10"}, + {-0x123456789abcdef, 16, "-123456789abcdef"}, + {1<<63 - 1, 16, "7fffffffffffffff"}, + {1<<63 - 1, 2, "111111111111111111111111111111111111111111111111111111111111111"}, + + {16, 17, "g"}, + {25, 25, "10"}, + {(((((17*35+24)*35+21)*35+34)*35+12)*35+24)*35 + 32, 35, "holycow"}, + {(((((17*36+24)*36+21)*36+34)*36+12)*36+24)*36 + 32, 36, "holycow"}, +} + +func TestItoa(t *testing.T) { + for _, test := range itob64tests { + s := FormatInt(test.in, test.base) + if s != test.out { + t.Errorf("FormatInt(%v, %v) = %v want %v", + test.in, test.base, s, test.out) + } + x := AppendInt([]byte("abc"), test.in, test.base) + if string(x) != "abc"+test.out { + t.Errorf("AppendInt(%q, %v, %v) = %q want %v", + "abc", test.in, test.base, x, test.out) + } + + if test.in >= 0 { + s := FormatUint(uint64(test.in), test.base) + if s != test.out { + t.Errorf("FormatUint(%v, %v) = %v want %v", + test.in, test.base, s, test.out) + } + x := AppendUint(nil, uint64(test.in), test.base) + if string(x) != test.out { + t.Errorf("AppendUint(%q, %v, %v) = %q want %v", + "abc", uint64(test.in), test.base, x, test.out) + } + } + + if test.base == 10 && int64(int(test.in)) == test.in { + s := Itoa(int(test.in)) + if s != test.out { + t.Errorf("Itoa(%v) = %v want %v", + test.in, s, test.out) + } + } + } +} + +type uitob64Test struct { + in uint64 + base int + out string +} + +var uitob64tests = []uitob64Test{ + {1<<63 - 1, 10, "9223372036854775807"}, + {1 << 63, 10, "9223372036854775808"}, + {1<<63 + 1, 10, "9223372036854775809"}, + {1<<64 - 2, 10, "18446744073709551614"}, + {1<<64 - 1, 10, "18446744073709551615"}, + {1<<64 - 1, 2, "1111111111111111111111111111111111111111111111111111111111111111"}, +} + +func TestUitoa(t *testing.T) { + for _, test := range uitob64tests { + s := FormatUint(test.in, test.base) + if s != test.out { + t.Errorf("FormatUint(%v, %v) = %v want %v", + test.in, test.base, s, test.out) + } + x := AppendUint([]byte("abc"), test.in, test.base) + if string(x) != "abc"+test.out { + t.Errorf("AppendUint(%q, %v, %v) = %q want %v", + "abc", test.in, test.base, x, test.out) + } + + } +} + +func BenchmarkFormatInt(b *testing.B) { + for i := 0; i < b.N; i++ { + for _, test := range itob64tests { + FormatInt(test.in, test.base) + } + } +} + +func BenchmarkAppendInt(b *testing.B) { + dst := make([]byte, 0, 30) + for i := 0; i < b.N; i++ { + for _, test := range itob64tests { + AppendInt(dst, test.in, test.base) + } + } +} + +func BenchmarkFormatUint(b *testing.B) { + for i := 0; i < b.N; i++ { + for _, test := range uitob64tests { + FormatUint(test.in, test.base) + } + } +} + +func BenchmarkAppendUint(b *testing.B) { + dst := make([]byte, 0, 30) + for i := 0; i < b.N; i++ { + for _, test := range uitob64tests { + AppendUint(dst, test.in, test.base) + } + } +} diff --git a/src/strconv/makeisprint.go b/src/strconv/makeisprint.go new file mode 100644 index 000000000..588d0a00b --- /dev/null +++ b/src/strconv/makeisprint.go @@ -0,0 +1,187 @@ +// Copyright 2012 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// +build ignore + +// +// usage: +// +// go run makeisprint.go -output isprint.go +// + +package main + +import ( + "bytes" + "flag" + "fmt" + "go/format" + "io/ioutil" + "log" + "unicode" +) + +var filename = flag.String("output", "isprint.go", "output file name") + +var ( + range16 []uint16 + except16 []uint16 + range32 []uint32 + except32 []uint32 +) + +// bsearch16 returns the smallest i such that a[i] >= x. +// If there is no such i, bsearch16 returns len(a). +func bsearch16(a []uint16, x uint16) int { + i, j := 0, len(a) + for i < j { + h := i + (j-i)/2 + if a[h] < x { + i = h + 1 + } else { + j = h + } + } + return i +} + +// bsearch32 returns the smallest i such that a[i] >= x. +// If there is no such i, bsearch32 returns len(a). +func bsearch32(a []uint32, x uint32) int { + i, j := 0, len(a) + for i < j { + h := i + (j-i)/2 + if a[h] < x { + i = h + 1 + } else { + j = h + } + } + return i +} + +func isPrint(r rune) bool { + // Same algorithm, either on uint16 or uint32 value. + // First, find first i such that rang[i] >= x. + // This is the index of either the start or end of a pair that might span x. + // The start is even (rang[i&^1]) and the end is odd (rang[i|1]). + // If we find x in a range, make sure x is not in exception list. + + if 0 <= r && r < 1<<16 { + rr, rang, except := uint16(r), range16, except16 + i := bsearch16(rang, rr) + if i >= len(rang) || rr < rang[i&^1] || rang[i|1] < rr { + return false + } + j := bsearch16(except, rr) + return j >= len(except) || except[j] != rr + } + + rr, rang, except := uint32(r), range32, except32 + i := bsearch32(rang, rr) + if i >= len(rang) || rr < rang[i&^1] || rang[i|1] < rr { + return false + } + j := bsearch32(except, rr) + return j >= len(except) || except[j] != rr +} + +func scan(min, max rune) (rang, except []uint32) { + lo := rune(-1) + for i := min; ; i++ { + if (i > max || !unicode.IsPrint(i)) && lo >= 0 { + // End range, but avoid flip flop. + if i+1 <= max && unicode.IsPrint(i+1) { + except = append(except, uint32(i)) + continue + } + rang = append(rang, uint32(lo), uint32(i-1)) + lo = -1 + } + if i > max { + break + } + if lo < 0 && unicode.IsPrint(i) { + lo = i + } + } + return +} + +func to16(x []uint32) []uint16 { + var y []uint16 + for _, v := range x { + if uint32(uint16(v)) != v { + panic("bad 32->16 conversion") + } + y = append(y, uint16(v)) + } + return y +} + +func main() { + flag.Parse() + + rang, except := scan(0, 0xFFFF) + range16 = to16(rang) + except16 = to16(except) + range32, except32 = scan(0x10000, unicode.MaxRune) + + for i := rune(0); i <= unicode.MaxRune; i++ { + if isPrint(i) != unicode.IsPrint(i) { + log.Fatalf("%U: isPrint=%v, want %v\n", i, isPrint(i), unicode.IsPrint(i)) + } + } + + var buf bytes.Buffer + + fmt.Fprintf(&buf, `// Copyright 2013 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file.`+"\n\n") + fmt.Fprintf(&buf, "// DO NOT EDIT. GENERATED BY\n") + fmt.Fprintf(&buf, "// go run makeisprint.go -output isprint.go\n\n") + fmt.Fprintf(&buf, "package strconv\n\n") + + fmt.Fprintf(&buf, "// (%d+%d+%d)*2 + (%d)*4 = %d bytes\n\n", + len(range16), len(except16), len(except32), + len(range32), + (len(range16)+len(except16)+len(except32))*2+ + (len(range32))*4) + + fmt.Fprintf(&buf, "var isPrint16 = []uint16{\n") + for i := 0; i < len(range16); i += 2 { + fmt.Fprintf(&buf, "\t%#04x, %#04x,\n", range16[i], range16[i+1]) + } + fmt.Fprintf(&buf, "}\n\n") + + fmt.Fprintf(&buf, "var isNotPrint16 = []uint16{\n") + for _, r := range except16 { + fmt.Fprintf(&buf, "\t%#04x,\n", r) + } + fmt.Fprintf(&buf, "}\n\n") + + fmt.Fprintf(&buf, "var isPrint32 = []uint32{\n") + for i := 0; i < len(range32); i += 2 { + fmt.Fprintf(&buf, "\t%#06x, %#06x,\n", range32[i], range32[i+1]) + } + fmt.Fprintf(&buf, "}\n\n") + + fmt.Fprintf(&buf, "var isNotPrint32 = []uint16{ // add 0x10000 to each entry\n") + for _, r := range except32 { + if r >= 0x20000 { + log.Fatalf("%U too big for isNotPrint32\n", r) + } + fmt.Fprintf(&buf, "\t%#04x,\n", r-0x10000) + } + fmt.Fprintf(&buf, "}\n") + + data, err := format.Source(buf.Bytes()) + if err != nil { + log.Fatal(err) + } + err = ioutil.WriteFile(*filename, data, 0644) + if err != nil { + log.Fatal(err) + } +} diff --git a/src/strconv/quote.go b/src/strconv/quote.go new file mode 100644 index 000000000..4469c688b --- /dev/null +++ b/src/strconv/quote.go @@ -0,0 +1,455 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +//go:generate go run makeisprint.go -output isprint.go + +package strconv + +import ( + "unicode/utf8" +) + +const lowerhex = "0123456789abcdef" + +func quoteWith(s string, quote byte, ASCIIonly bool) string { + var runeTmp [utf8.UTFMax]byte + buf := make([]byte, 0, 3*len(s)/2) // Try to avoid more allocations. + buf = append(buf, quote) + for width := 0; len(s) > 0; s = s[width:] { + r := rune(s[0]) + width = 1 + if r >= utf8.RuneSelf { + r, width = utf8.DecodeRuneInString(s) + } + if width == 1 && r == utf8.RuneError { + buf = append(buf, `\x`...) + buf = append(buf, lowerhex[s[0]>>4]) + buf = append(buf, lowerhex[s[0]&0xF]) + continue + } + if r == rune(quote) || r == '\\' { // always backslashed + buf = append(buf, '\\') + buf = append(buf, byte(r)) + continue + } + if ASCIIonly { + if r < utf8.RuneSelf && IsPrint(r) { + buf = append(buf, byte(r)) + continue + } + } else if IsPrint(r) { + n := utf8.EncodeRune(runeTmp[:], r) + buf = append(buf, runeTmp[:n]...) + continue + } + switch r { + case '\a': + buf = append(buf, `\a`...) + case '\b': + buf = append(buf, `\b`...) + case '\f': + buf = append(buf, `\f`...) + case '\n': + buf = append(buf, `\n`...) + case '\r': + buf = append(buf, `\r`...) + case '\t': + buf = append(buf, `\t`...) + case '\v': + buf = append(buf, `\v`...) + default: + switch { + case r < ' ': + buf = append(buf, `\x`...) + buf = append(buf, lowerhex[s[0]>>4]) + buf = append(buf, lowerhex[s[0]&0xF]) + case r > utf8.MaxRune: + r = 0xFFFD + fallthrough + case r < 0x10000: + buf = append(buf, `\u`...) + for s := 12; s >= 0; s -= 4 { + buf = append(buf, lowerhex[r>>uint(s)&0xF]) + } + default: + buf = append(buf, `\U`...) + for s := 28; s >= 0; s -= 4 { + buf = append(buf, lowerhex[r>>uint(s)&0xF]) + } + } + } + } + buf = append(buf, quote) + return string(buf) + +} + +// Quote returns a double-quoted Go string literal representing s. The +// returned string uses Go escape sequences (\t, \n, \xFF, \u0100) for +// control characters and non-printable characters as defined by +// IsPrint. +func Quote(s string) string { + return quoteWith(s, '"', false) +} + +// AppendQuote appends a double-quoted Go string literal representing s, +// as generated by Quote, to dst and returns the extended buffer. +func AppendQuote(dst []byte, s string) []byte { + return append(dst, Quote(s)...) +} + +// QuoteToASCII returns a double-quoted Go string literal representing s. +// The returned string uses Go escape sequences (\t, \n, \xFF, \u0100) for +// non-ASCII characters and non-printable characters as defined by IsPrint. +func QuoteToASCII(s string) string { + return quoteWith(s, '"', true) +} + +// AppendQuoteToASCII appends a double-quoted Go string literal representing s, +// as generated by QuoteToASCII, to dst and returns the extended buffer. +func AppendQuoteToASCII(dst []byte, s string) []byte { + return append(dst, QuoteToASCII(s)...) +} + +// QuoteRune returns a single-quoted Go character literal representing the +// rune. The returned string uses Go escape sequences (\t, \n, \xFF, \u0100) +// for control characters and non-printable characters as defined by IsPrint. +func QuoteRune(r rune) string { + // TODO: avoid the allocation here. + return quoteWith(string(r), '\'', false) +} + +// AppendQuoteRune appends a single-quoted Go character literal representing the rune, +// as generated by QuoteRune, to dst and returns the extended buffer. +func AppendQuoteRune(dst []byte, r rune) []byte { + return append(dst, QuoteRune(r)...) +} + +// QuoteRuneToASCII returns a single-quoted Go character literal representing +// the rune. The returned string uses Go escape sequences (\t, \n, \xFF, +// \u0100) for non-ASCII characters and non-printable characters as defined +// by IsPrint. +func QuoteRuneToASCII(r rune) string { + // TODO: avoid the allocation here. + return quoteWith(string(r), '\'', true) +} + +// AppendQuoteRuneToASCII appends a single-quoted Go character literal representing the rune, +// as generated by QuoteRuneToASCII, to dst and returns the extended buffer. +func AppendQuoteRuneToASCII(dst []byte, r rune) []byte { + return append(dst, QuoteRuneToASCII(r)...) +} + +// CanBackquote reports whether the string s can be represented +// unchanged as a single-line backquoted string without control +// characters other than space and tab. +func CanBackquote(s string) bool { + for len(s) > 0 { + r, wid := utf8.DecodeRuneInString(s) + s = s[wid:] + if wid > 1 { + if r == '\ufeff' { + return false // BOMs are invisible and should not be quoted. + } + continue // All other multibyte runes are correctly encoded and assumed printable. + } + if r == utf8.RuneError { + return false + } + if (r < ' ' && r != '\t') || r == '`' || r == '\u007F' { + return false + } + } + return true +} + +func unhex(b byte) (v rune, ok bool) { + c := rune(b) + switch { + case '0' <= c && c <= '9': + return c - '0', true + case 'a' <= c && c <= 'f': + return c - 'a' + 10, true + case 'A' <= c && c <= 'F': + return c - 'A' + 10, true + } + return +} + +// UnquoteChar decodes the first character or byte in the escaped string +// or character literal represented by the string s. +// It returns four values: +// +// 1) value, the decoded Unicode code point or byte value; +// 2) multibyte, a boolean indicating whether the decoded character requires a multibyte UTF-8 representation; +// 3) tail, the remainder of the string after the character; and +// 4) an error that will be nil if the character is syntactically valid. +// +// The second argument, quote, specifies the type of literal being parsed +// and therefore which escaped quote character is permitted. +// If set to a single quote, it permits the sequence \' and disallows unescaped '. +// If set to a double quote, it permits \" and disallows unescaped ". +// If set to zero, it does not permit either escape and allows both quote characters to appear unescaped. +func UnquoteChar(s string, quote byte) (value rune, multibyte bool, tail string, err error) { + // easy cases + switch c := s[0]; { + case c == quote && (quote == '\'' || quote == '"'): + err = ErrSyntax + return + case c >= utf8.RuneSelf: + r, size := utf8.DecodeRuneInString(s) + return r, true, s[size:], nil + case c != '\\': + return rune(s[0]), false, s[1:], nil + } + + // hard case: c is backslash + if len(s) <= 1 { + err = ErrSyntax + return + } + c := s[1] + s = s[2:] + + switch c { + case 'a': + value = '\a' + case 'b': + value = '\b' + case 'f': + value = '\f' + case 'n': + value = '\n' + case 'r': + value = '\r' + case 't': + value = '\t' + case 'v': + value = '\v' + case 'x', 'u', 'U': + n := 0 + switch c { + case 'x': + n = 2 + case 'u': + n = 4 + case 'U': + n = 8 + } + var v rune + if len(s) < n { + err = ErrSyntax + return + } + for j := 0; j < n; j++ { + x, ok := unhex(s[j]) + if !ok { + err = ErrSyntax + return + } + v = v<<4 | x + } + s = s[n:] + if c == 'x' { + // single-byte string, possibly not UTF-8 + value = v + break + } + if v > utf8.MaxRune { + err = ErrSyntax + return + } + value = v + multibyte = true + case '0', '1', '2', '3', '4', '5', '6', '7': + v := rune(c) - '0' + if len(s) < 2 { + err = ErrSyntax + return + } + 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 + } + s = s[2:] + if v > 255 { + err = ErrSyntax + return + } + value = v + case '\\': + value = '\\' + case '\'', '"': + if c != quote { + err = ErrSyntax + return + } + value = rune(c) + default: + err = ErrSyntax + return + } + tail = s + return +} + +// Unquote interprets s as a single-quoted, double-quoted, +// or backquoted Go string literal, returning the string value +// that s quotes. (If s is single-quoted, it would be a Go +// character literal; Unquote returns the corresponding +// one-character string.) +func Unquote(s string) (t string, err error) { + n := len(s) + if n < 2 { + return "", ErrSyntax + } + quote := s[0] + if quote != s[n-1] { + return "", ErrSyntax + } + s = s[1 : n-1] + + if quote == '`' { + if contains(s, '`') { + return "", ErrSyntax + } + return s, nil + } + if quote != '"' && quote != '\'' { + return "", ErrSyntax + } + if contains(s, '\n') { + return "", ErrSyntax + } + + // Is it trivial? Avoid allocation. + if !contains(s, '\\') && !contains(s, quote) { + switch quote { + case '"': + return s, nil + case '\'': + r, size := utf8.DecodeRuneInString(s) + if size == len(s) && (r != utf8.RuneError || size != 1) { + return s, nil + } + } + } + + var runeTmp [utf8.UTFMax]byte + buf := make([]byte, 0, 3*len(s)/2) // Try to avoid more allocations. + for len(s) > 0 { + c, multibyte, ss, err := UnquoteChar(s, quote) + if err != nil { + return "", err + } + s = ss + if c < utf8.RuneSelf || !multibyte { + buf = append(buf, byte(c)) + } else { + n := utf8.EncodeRune(runeTmp[:], c) + buf = append(buf, runeTmp[:n]...) + } + if quote == '\'' && len(s) != 0 { + // single-quoted must be single character + return "", ErrSyntax + } + } + return string(buf), nil +} + +// contains reports whether the string contains the byte c. +func contains(s string, c byte) bool { + for i := 0; i < len(s); i++ { + if s[i] == c { + return true + } + } + return false +} + +// bsearch16 returns the smallest i such that a[i] >= x. +// If there is no such i, bsearch16 returns len(a). +func bsearch16(a []uint16, x uint16) int { + i, j := 0, len(a) + for i < j { + h := i + (j-i)/2 + if a[h] < x { + i = h + 1 + } else { + j = h + } + } + return i +} + +// bsearch32 returns the smallest i such that a[i] >= x. +// If there is no such i, bsearch32 returns len(a). +func bsearch32(a []uint32, x uint32) int { + i, j := 0, len(a) + for i < j { + h := i + (j-i)/2 + if a[h] < x { + i = h + 1 + } else { + j = h + } + } + return i +} + +// TODO: IsPrint is a local implementation of unicode.IsPrint, verified by the tests +// to give the same answer. It allows this package not to depend on unicode, +// and therefore not pull in all the Unicode tables. If the linker were better +// at tossing unused tables, we could get rid of this implementation. +// That would be nice. + +// IsPrint reports whether the rune is defined as printable by Go, with +// the same definition as unicode.IsPrint: letters, numbers, punctuation, +// symbols and ASCII space. +func IsPrint(r rune) bool { + // Fast check for Latin-1 + if r <= 0xFF { + if 0x20 <= r && r <= 0x7E { + // All the ASCII is printable from space through DEL-1. + return true + } + if 0xA1 <= r && r <= 0xFF { + // Similarly for ¡ through ÿ... + return r != 0xAD // ...except for the bizarre soft hyphen. + } + return false + } + + // Same algorithm, either on uint16 or uint32 value. + // First, find first i such that isPrint[i] >= x. + // This is the index of either the start or end of a pair that might span x. + // The start is even (isPrint[i&^1]) and the end is odd (isPrint[i|1]). + // If we find x in a range, make sure x is not in isNotPrint list. + + if 0 <= r && r < 1<<16 { + rr, isPrint, isNotPrint := uint16(r), isPrint16, isNotPrint16 + i := bsearch16(isPrint, rr) + if i >= len(isPrint) || rr < isPrint[i&^1] || isPrint[i|1] < rr { + return false + } + j := bsearch16(isNotPrint, rr) + return j >= len(isNotPrint) || isNotPrint[j] != rr + } + + rr, isPrint, isNotPrint := uint32(r), isPrint32, isNotPrint32 + i := bsearch32(isPrint, rr) + if i >= len(isPrint) || rr < isPrint[i&^1] || isPrint[i|1] < rr { + return false + } + if r >= 0x20000 { + return true + } + r -= 0x10000 + j := bsearch16(isNotPrint, uint16(r)) + return j >= len(isNotPrint) || isNotPrint[j] != uint16(r) +} diff --git a/src/strconv/quote_example_test.go b/src/strconv/quote_example_test.go new file mode 100644 index 000000000..405a57eb5 --- /dev/null +++ b/src/strconv/quote_example_test.go @@ -0,0 +1,35 @@ +// Copyright 2013 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package strconv_test + +import ( + "fmt" + "strconv" +) + +func ExampleUnquote() { + test := func(s string) { + t, err := strconv.Unquote(s) + if err != nil { + fmt.Printf("Unquote(%#v): %v\n", s, err) + } else { + fmt.Printf("Unquote(%#v) = %v\n", s, t) + } + } + + s := `cafe\u0301` + // If the string doesn't have quotes, it can't be unquoted. + test(s) // invalid syntax + test("`" + s + "`") + test(`"` + s + `"`) + + test(`'\u00e9'`) + + // Output: + // Unquote("cafe\\u0301"): invalid syntax + // Unquote("`cafe\\u0301`") = cafe\u0301 + // Unquote("\"cafe\\u0301\"") = café + // Unquote("'\\u00e9'") = é +} diff --git a/src/strconv/quote_test.go b/src/strconv/quote_test.go new file mode 100644 index 000000000..3bf162f98 --- /dev/null +++ b/src/strconv/quote_test.go @@ -0,0 +1,266 @@ +// Copyright 2009 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package strconv_test + +import ( + . "strconv" + "testing" + "unicode" +) + +// Verify that our isPrint agrees with unicode.IsPrint +func TestIsPrint(t *testing.T) { + n := 0 + for r := rune(0); r <= unicode.MaxRune; r++ { + if IsPrint(r) != unicode.IsPrint(r) { + t.Errorf("IsPrint(%U)=%t incorrect", r, IsPrint(r)) + n++ + if n > 10 { + return + } + } + } +} + +type quoteTest struct { + in string + out string + ascii string +} + +var quotetests = []quoteTest{ + {"\a\b\f\r\n\t\v", `"\a\b\f\r\n\t\v"`, `"\a\b\f\r\n\t\v"`}, + {"\\", `"\\"`, `"\\"`}, + {"abc\xffdef", `"abc\xffdef"`, `"abc\xffdef"`}, + {"\u263a", `"☺"`, `"\u263a"`}, + {"\U0010ffff", `"\U0010ffff"`, `"\U0010ffff"`}, + {"\x04", `"\x04"`, `"\x04"`}, +} + +func TestQuote(t *testing.T) { + for _, tt := range quotetests { + if out := Quote(tt.in); out != tt.out { + t.Errorf("Quote(%s) = %s, want %s", tt.in, out, tt.out) + } + if out := AppendQuote([]byte("abc"), tt.in); string(out) != "abc"+tt.out { + t.Errorf("AppendQuote(%q, %s) = %s, want %s", "abc", tt.in, out, "abc"+tt.out) + } + } +} + +func TestQuoteToASCII(t *testing.T) { + for _, tt := range quotetests { + if out := QuoteToASCII(tt.in); out != tt.ascii { + t.Errorf("QuoteToASCII(%s) = %s, want %s", tt.in, out, tt.ascii) + } + if out := AppendQuoteToASCII([]byte("abc"), tt.in); string(out) != "abc"+tt.ascii { + t.Errorf("AppendQuoteToASCII(%q, %s) = %s, want %s", "abc", tt.in, out, "abc"+tt.ascii) + } + } +} + +type quoteRuneTest struct { + in rune + out string + ascii string +} + +var quoterunetests = []quoteRuneTest{ + {'a', `'a'`, `'a'`}, + {'\a', `'\a'`, `'\a'`}, + {'\\', `'\\'`, `'\\'`}, + {0xFF, `'ÿ'`, `'\u00ff'`}, + {0x263a, `'☺'`, `'\u263a'`}, + {0xfffd, `'�'`, `'\ufffd'`}, + {0x0010ffff, `'\U0010ffff'`, `'\U0010ffff'`}, + {0x0010ffff + 1, `'�'`, `'\ufffd'`}, + {0x04, `'\x04'`, `'\x04'`}, +} + +func TestQuoteRune(t *testing.T) { + for _, tt := range quoterunetests { + if out := QuoteRune(tt.in); out != tt.out { + t.Errorf("QuoteRune(%U) = %s, want %s", tt.in, out, tt.out) + } + if out := AppendQuoteRune([]byte("abc"), tt.in); string(out) != "abc"+tt.out { + t.Errorf("AppendQuoteRune(%q, %U) = %s, want %s", "abc", tt.in, out, "abc"+tt.out) + } + } +} + +func TestQuoteRuneToASCII(t *testing.T) { + for _, tt := range quoterunetests { + if out := QuoteRuneToASCII(tt.in); out != tt.ascii { + t.Errorf("QuoteRuneToASCII(%U) = %s, want %s", tt.in, out, tt.ascii) + } + if out := AppendQuoteRuneToASCII([]byte("abc"), tt.in); string(out) != "abc"+tt.ascii { + t.Errorf("AppendQuoteRuneToASCII(%q, %U) = %s, want %s", "abc", tt.in, out, "abc"+tt.ascii) + } + } +} + +type canBackquoteTest struct { + in string + out bool +} + +var canbackquotetests = []canBackquoteTest{ + {"`", false}, + {string(0), false}, + {string(1), false}, + {string(2), false}, + {string(3), false}, + {string(4), false}, + {string(5), false}, + {string(6), false}, + {string(7), false}, + {string(8), false}, + {string(9), true}, // \t + {string(10), false}, + {string(11), false}, + {string(12), false}, + {string(13), false}, + {string(14), false}, + {string(15), false}, + {string(16), false}, + {string(17), false}, + {string(18), false}, + {string(19), false}, + {string(20), false}, + {string(21), false}, + {string(22), false}, + {string(23), false}, + {string(24), false}, + {string(25), false}, + {string(26), false}, + {string(27), false}, + {string(28), false}, + {string(29), false}, + {string(30), false}, + {string(31), false}, + {string(0x7F), false}, + {`' !"#$%&'()*+,-./:;<=>?@[\]^_{|}~`, true}, + {`0123456789`, true}, + {`ABCDEFGHIJKLMNOPQRSTUVWXYZ`, true}, + {`abcdefghijklmnopqrstuvwxyz`, true}, + {`☺`, true}, + {"\x80", false}, + {"a\xe0\xa0z", false}, + {"\ufeffabc", false}, + {"a\ufeffz", false}, +} + +func TestCanBackquote(t *testing.T) { + for _, tt := range canbackquotetests { + if out := CanBackquote(tt.in); out != tt.out { + t.Errorf("CanBackquote(%q) = %v, want %v", tt.in, out, tt.out) + } + } +} + +type unQuoteTest struct { + in string + out string +} + +var unquotetests = []unQuoteTest{ + {`""`, ""}, + {`"a"`, "a"}, + {`"abc"`, "abc"}, + {`"☺"`, "☺"}, + {`"hello world"`, "hello world"}, + {`"\xFF"`, "\xFF"}, + {`"\377"`, "\377"}, + {`"\u1234"`, "\u1234"}, + {`"\U00010111"`, "\U00010111"}, + {`"\U0001011111"`, "\U0001011111"}, + {`"\a\b\f\n\r\t\v\\\""`, "\a\b\f\n\r\t\v\\\""}, + {`"'"`, "'"}, + + {`'a'`, "a"}, + {`'☹'`, "☹"}, + {`'\a'`, "\a"}, + {`'\x10'`, "\x10"}, + {`'\377'`, "\377"}, + {`'\u1234'`, "\u1234"}, + {`'\U00010111'`, "\U00010111"}, + {`'\t'`, "\t"}, + {`' '`, " "}, + {`'\''`, "'"}, + {`'"'`, "\""}, + + {"``", ``}, + {"`a`", `a`}, + {"`abc`", `abc`}, + {"`☺`", `☺`}, + {"`hello world`", `hello world`}, + {"`\\xFF`", `\xFF`}, + {"`\\377`", `\377`}, + {"`\\`", `\`}, + {"`\n`", "\n"}, + {"` `", ` `}, + {"` `", ` `}, +} + +var misquoted = []string{ + ``, + `"`, + `"a`, + `"'`, + `b"`, + `"\"`, + `"\9"`, + `"\19"`, + `"\129"`, + `'\'`, + `'\9'`, + `'\19'`, + `'\129'`, + `'ab'`, + `"\x1!"`, + `"\U12345678"`, + `"\z"`, + "`", + "`xxx", + "`\"", + `"\'"`, + `'\"'`, + "\"\n\"", + "\"\\n\n\"", + "'\n'", +} + +func TestUnquote(t *testing.T) { + for _, tt := range unquotetests { + if out, err := Unquote(tt.in); err != nil && out != tt.out { + t.Errorf("Unquote(%#q) = %q, %v want %q, nil", tt.in, out, err, tt.out) + } + } + + // run the quote tests too, backward + for _, tt := range quotetests { + if in, err := Unquote(tt.out); in != tt.in { + t.Errorf("Unquote(%#q) = %q, %v, want %q, nil", tt.out, in, err, tt.in) + } + } + + for _, s := range misquoted { + if out, err := Unquote(s); out != "" || err != ErrSyntax { + t.Errorf("Unquote(%#q) = %q, %v want %q, %v", s, out, err, "", ErrSyntax) + } + } +} + +func BenchmarkUnquoteEasy(b *testing.B) { + for i := 0; i < b.N; i++ { + Unquote(`"Give me a rock, paper and scissors and I will move the world."`) + } +} + +func BenchmarkUnquoteHard(b *testing.B) { + for i := 0; i < b.N; i++ { + Unquote(`"\x47ive me a \x72ock, \x70aper and \x73cissors and \x49 will move the world."`) + } +} diff --git a/src/strconv/strconv_test.go b/src/strconv/strconv_test.go new file mode 100644 index 000000000..9a007dde4 --- /dev/null +++ b/src/strconv/strconv_test.go @@ -0,0 +1,57 @@ +// Copyright 2012 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package strconv_test + +import ( + "runtime" + . "strconv" + "strings" + "testing" +) + +var ( + globalBuf [64]byte + nextToOne = "1.00000000000000011102230246251565404236316680908203125" + strings.Repeat("0", 10000) + "1" + + mallocTest = []struct { + count int + desc string + fn func() + }{ + {0, `AppendInt(localBuf[:0], 123, 10)`, func() { + var localBuf [64]byte + AppendInt(localBuf[:0], 123, 10) + }}, + {0, `AppendInt(globalBuf[:0], 123, 10)`, func() { AppendInt(globalBuf[:0], 123, 10) }}, + {0, `AppendFloat(localBuf[:0], 1.23, 'g', 5, 64)`, func() { + var localBuf [64]byte + AppendFloat(localBuf[:0], 1.23, 'g', 5, 64) + }}, + {0, `AppendFloat(globalBuf[:0], 1.23, 'g', 5, 64)`, func() { AppendFloat(globalBuf[:0], 1.23, 'g', 5, 64) }}, + {0, `ParseFloat("123.45", 64)`, func() { ParseFloat("123.45", 64) }}, + {0, `ParseFloat("123.456789123456789", 64)`, func() { ParseFloat("123.456789123456789", 64) }}, + {0, `ParseFloat("1.000000000000000111022302462515654042363166809082031251", 64)`, func() { + ParseFloat("1.000000000000000111022302462515654042363166809082031251", 64) + }}, + {0, `ParseFloat("1.0000000000000001110223024625156540423631668090820312500...001", 64)`, func() { + ParseFloat(nextToOne, 64) + }}, + } +) + +func TestCountMallocs(t *testing.T) { + if testing.Short() { + t.Skip("skipping malloc count in short mode") + } + if runtime.GOMAXPROCS(0) > 1 { + t.Skip("skipping; GOMAXPROCS>1") + } + for _, mt := range mallocTest { + allocs := testing.AllocsPerRun(100, mt.fn) + if max := float64(mt.count); allocs > max { + t.Errorf("%s: %v allocs, want <=%v", mt.desc, allocs, max) + } + } +} diff --git a/src/strconv/testdata/testfp.txt b/src/strconv/testdata/testfp.txt new file mode 100644 index 000000000..08d3c4ef0 --- /dev/null +++ b/src/strconv/testdata/testfp.txt @@ -0,0 +1,181 @@ +# Floating-point conversion test cases. +# Empty lines and lines beginning with # are ignored. +# The rest have four fields per line: type, format, input, and output. +# The input is given either in decimal or binary scientific notation. +# The output is the string that should be produced by formatting the +# input with the given format. +# +# The formats are as in C's printf, except that %b means print +# binary scientific notation: NpE = N x 2^E. + +# TODO: +# Powers of 10. +# Powers of 2. +# %.20g versions. +# random sources +# random targets +# random targets ± half a ULP + +# Difficult boundary cases, derived from tables given in +# Vern Paxson, A Program for Testing IEEE Decimal-Binary Conversion +# ftp://ftp.ee.lbl.gov/testbase-report.ps.Z + +# Table 1: Stress Inputs for Conversion to 53-bit Binary, < 1/2 ULP +float64 %b 5e+125 6653062250012735p+365 +float64 %b 69e+267 4705683757438170p+841 +float64 %b 999e-026 6798841691080350p-129 +float64 %b 7861e-034 8975675289889240p-153 +float64 %b 75569e-254 6091718967192243p-880 +float64 %b 928609e-261 7849264900213743p-900 +float64 %b 9210917e+080 8341110837370930p+236 +float64 %b 84863171e+114 4625202867375927p+353 +float64 %b 653777767e+273 5068902999763073p+884 +float64 %b 5232604057e-298 5741343011915040p-1010 +float64 %b 27235667517e-109 6707124626673586p-380 +float64 %b 653532977297e-123 7078246407265384p-422 +float64 %b 3142213164987e-294 8219991337640559p-988 +float64 %b 46202199371337e-072 5224462102115359p-246 +float64 %b 231010996856685e-073 5224462102115359p-247 +float64 %b 9324754620109615e+212 5539753864394442p+705 +float64 %b 78459735791271921e+049 8388176519442766p+166 +float64 %b 272104041512242479e+200 5554409530847367p+670 +float64 %b 6802601037806061975e+198 5554409530847367p+668 +float64 %b 20505426358836677347e-221 4524032052079546p-722 +float64 %b 836168422905420598437e-234 5070963299887562p-760 +float64 %b 4891559871276714924261e+222 6452687840519111p+757 + +# Table 2: Stress Inputs for Conversion to 53-bit Binary, > 1/2 ULP +float64 %b 9e-265 8168427841980010p-930 +float64 %b 85e-037 6360455125664090p-169 +float64 %b 623e+100 6263531988747231p+289 +float64 %b 3571e+263 6234526311072170p+833 +float64 %b 81661e+153 6696636728760206p+472 +float64 %b 920657e-023 5975405561110124p-109 +float64 %b 4603285e-024 5975405561110124p-110 +float64 %b 87575437e-309 8452160731874668p-1053 +float64 %b 245540327e+122 4985336549131723p+381 +float64 %b 6138508175e+120 4985336549131723p+379 +float64 %b 83356057653e+193 5986732817132056p+625 +float64 %b 619534293513e+124 4798406992060657p+399 +float64 %b 2335141086879e+218 5419088166961646p+713 +float64 %b 36167929443327e-159 8135819834632444p-536 +float64 %b 609610927149051e-255 4576664294594737p-850 +float64 %b 3743626360493413e-165 6898586531774201p-549 +float64 %b 94080055902682397e-242 6273271706052298p-800 +float64 %b 899810892172646163e+283 7563892574477827p+947 +float64 %b 7120190517612959703e+120 5385467232557565p+409 +float64 %b 25188282901709339043e-252 5635662608542340p-825 +float64 %b 308984926168550152811e-052 5644774693823803p-157 +float64 %b 6372891218502368041059e+064 4616868614322430p+233 + +# Table 3: Stress Inputs for Converting 53-bit Binary to Decimal, < 1/2 ULP +float64 %.0e 8511030020275656p-342 9e-88 +float64 %.1e 5201988407066741p-824 4.6e-233 +float64 %.2e 6406892948269899p+237 1.41e+87 +float64 %.3e 8431154198732492p+72 3.981e+37 +float64 %.4e 6475049196144587p+99 4.1040e+45 +float64 %.5e 8274307542972842p+726 2.92084e+234 +float64 %.6e 5381065484265332p-456 2.891946e-122 +float64 %.7e 6761728585499734p-1057 4.3787718e-303 +float64 %.8e 7976538478610756p+376 1.22770163e+129 +float64 %.9e 5982403858958067p+377 1.841552452e+129 +float64 %.10e 5536995190630837p+93 5.4835744350e+43 +float64 %.11e 7225450889282194p+710 3.89190181146e+229 +float64 %.12e 7225450889282194p+709 1.945950905732e+229 +float64 %.13e 8703372741147379p+117 1.4460958381605e+51 +float64 %.14e 8944262675275217p-1001 4.17367747458531e-286 +float64 %.15e 7459803696087692p-707 1.107950772878888e-197 +float64 %.16e 6080469016670379p-381 1.2345501366327440e-99 +float64 %.17e 8385515147034757p+721 9.25031711960365024e+232 +float64 %.18e 7514216811389786p-828 4.198047150284889840e-234 +float64 %.19e 8397297803260511p-345 1.1716315319786511046e-88 +float64 %.20e 6733459239310543p+202 4.32810072844612493629e+76 +float64 %.21e 8091450587292794p-473 3.317710118160031081518e-127 + +# Table 4: Stress Inputs for Converting 53-bit Binary to Decimal, > 1/2 ULP +float64 %.0e 6567258882077402p+952 3e+302 +float64 %.1e 6712731423444934p+535 7.6e+176 +float64 %.2e 6712731423444934p+534 3.78e+176 +float64 %.3e 5298405411573037p-957 4.350e-273 +float64 %.4e 5137311167659507p-144 2.3037e-28 +float64 %.5e 6722280709661868p+363 1.26301e+125 +float64 %.6e 5344436398034927p-169 7.142211e-36 +float64 %.7e 8369123604277281p-853 1.3934574e-241 +float64 %.8e 8995822108487663p-780 1.41463449e-219 +float64 %.9e 8942832835564782p-383 4.539277920e-100 +float64 %.10e 8942832835564782p-384 2.2696389598e-100 +float64 %.11e 8942832835564782p-385 1.13481947988e-100 +float64 %.12e 6965949469487146p-249 7.700366561890e-60 +float64 %.13e 6965949469487146p-250 3.8501832809448e-60 +float64 %.14e 6965949469487146p-251 1.92509164047238e-60 +float64 %.15e 7487252720986826p+548 6.898586531774201e+180 +float64 %.16e 5592117679628511p+164 1.3076622631878654e+65 +float64 %.17e 8887055249355788p+665 1.36052020756121240e+216 +float64 %.18e 6994187472632449p+690 3.592810217475959676e+223 +float64 %.19e 8797576579012143p+588 8.9125197712484551899e+192 +float64 %.20e 7363326733505337p+272 5.58769757362301140950e+97 +float64 %.21e 8549497411294502p-448 1.176257830728540379990e-119 + +# Table 14: Stress Inputs for Conversion to 24-bit Binary, <1/2 ULP +# NOTE: The lines with exponent p-149 have been changed from the +# paper. Those entries originally read p-150 and had a mantissa +# twice as large (and even), but IEEE single-precision has no p-150: +# that's the start of the denormals. +float32 %b 5e-20 15474250p-88 +float32 %b 67e+14 12479722p+29 +float32 %b 985e+15 14333636p+36 +# float32 %b 7693e-42 10979816p-150 +float32 %b 7693e-42 5489908p-149 +float32 %b 55895e-16 12888509p-61 +# float32 %b 996622e-44 14224264p-150 +float32 %b 996622e-44 7112132p-149 +float32 %b 7038531e-32 11420669p-107 +# float32 %b 60419369e-46 8623340p-150 +float32 %b 60419369e-46 4311670p-149 +float32 %b 702990899e-20 16209866p-61 +# float32 %b 6930161142e-48 9891056p-150 +float32 %b 6930161142e-48 4945528p-149 +float32 %b 25933168707e+13 14395800p+54 +float32 %b 596428896559e+20 12333860p+82 + +# Table 15: Stress Inputs for Conversion to 24-bit Binary, >1/2 ULP +float32 %b 3e-23 9507380p-98 +float32 %b 57e+18 12960300p+42 +float32 %b 789e-35 10739312p-130 +float32 %b 2539e-18 11990089p-72 +float32 %b 76173e+28 9845130p+86 +float32 %b 887745e-11 9760860p-40 +float32 %b 5382571e-37 11447463p-124 +float32 %b 82381273e-35 8554961p-113 +float32 %b 750486563e-38 9975678p-120 +float32 %b 3752432815e-39 9975678p-121 +float32 %b 75224575729e-45 13105970p-137 +float32 %b 459926601011e+15 12466336p+65 + +# Table 16: Stress Inputs for Converting 24-bit Binary to Decimal, < 1/2 ULP +float32 %.0e 12676506p-102 2e-24 +float32 %.1e 12676506p-103 1.2e-24 +float32 %.2e 15445013p+86 1.19e+33 +float32 %.3e 13734123p-138 3.941e-35 +float32 %.4e 12428269p-130 9.1308e-33 +float32 %.5e 15334037p-146 1.71900e-37 +float32 %.6e 11518287p-41 5.237910e-06 +float32 %.7e 12584953p-145 2.8216440e-37 +float32 %.8e 15961084p-125 3.75243281e-31 +float32 %.9e 14915817p-146 1.672120916e-37 +float32 %.10e 10845484p-102 2.1388945814e-24 +float32 %.11e 16431059p-61 7.12583594561e-12 + +# Table 17: Stress Inputs for Converting 24-bit Binary to Decimal, > 1/2 ULP +float32 %.0e 16093626p+69 1e+28 +float32 %.1e 9983778p+25 3.4e+14 +float32 %.2e 12745034p+104 2.59e+38 +float32 %.3e 12706553p+72 6.001e+28 +float32 %.4e 11005028p+45 3.8721e+20 +float32 %.5e 15059547p+71 3.55584e+28 +float32 %.6e 16015691p-99 2.526831e-23 +float32 %.7e 8667859p+56 6.2458507e+23 +float32 %.8e 14855922p-82 3.07213267e-18 +float32 %.9e 14855922p-83 1.536066333e-18 +float32 %.10e 10144164p-110 7.8147796834e-27 +float32 %.11e 13248074p+95 5.24810279937e+35 |