diff options
Diffstat (limited to 'libgo/go/strconv')
| -rw-r--r-- | libgo/go/strconv/atof.go | 2 | ||||
| -rw-r--r-- | libgo/go/strconv/atof_test.go | 3 | ||||
| -rw-r--r-- | libgo/go/strconv/atoi.go | 13 | ||||
| -rw-r--r-- | libgo/go/strconv/atoi_test.go | 10 | ||||
| -rw-r--r-- | libgo/go/strconv/bytealg.go | 15 | ||||
| -rw-r--r-- | libgo/go/strconv/bytealg_bootstrap.go | 18 | ||||
| -rw-r--r-- | libgo/go/strconv/eisel_lemire.go | 16 | ||||
| -rw-r--r-- | libgo/go/strconv/extfloat.go | 517 | ||||
| -rw-r--r-- | libgo/go/strconv/ftoa.go | 23 | ||||
| -rw-r--r-- | libgo/go/strconv/ftoa_test.go | 48 | ||||
| -rw-r--r-- | libgo/go/strconv/ftoaryu.go | 567 | ||||
| -rw-r--r-- | libgo/go/strconv/ftoaryu_test.go | 31 | ||||
| -rw-r--r-- | libgo/go/strconv/internal_test.go | 8 | ||||
| -rw-r--r-- | libgo/go/strconv/makeisprint.go | 5 | ||||
| -rw-r--r-- | libgo/go/strconv/quote.go | 171 | ||||
| -rw-r--r-- | libgo/go/strconv/quote_test.go | 63 |
16 files changed, 879 insertions, 631 deletions
diff --git a/libgo/go/strconv/atof.go b/libgo/go/strconv/atof.go index 1c50057..6ecd4f1 100644 --- a/libgo/go/strconv/atof.go +++ b/libgo/go/strconv/atof.go @@ -695,7 +695,7 @@ func atof64(s string) (f float64, n int, err error) { // as their respective special floating point values. It ignores case when matching. func ParseFloat(s string, bitSize int) (float64, error) { f, n, err := parseFloatPrefix(s, bitSize) - if err == nil && n != len(s) { + if n != len(s) && (err == nil || err.(*NumError).Err != ErrSyntax) { return 0, syntaxError(fnParseFloat, s) } return f, err diff --git a/libgo/go/strconv/atof_test.go b/libgo/go/strconv/atof_test.go index 3c058b9..aa587a4 100644 --- a/libgo/go/strconv/atof_test.go +++ b/libgo/go/strconv/atof_test.go @@ -342,6 +342,9 @@ var atoftests = []atofTest{ {"0x12.345p-_12", "0", ErrSyntax}, {"0x12.345p+1__2", "0", ErrSyntax}, {"0x12.345p+12_", "0", ErrSyntax}, + + {"1e100x", "0", ErrSyntax}, + {"1e1000x", "0", ErrSyntax}, } var atof32tests = []atofTest{ diff --git a/libgo/go/strconv/atoi.go b/libgo/go/strconv/atoi.go index f6c4efa..631b487 100644 --- a/libgo/go/strconv/atoi.go +++ b/libgo/go/strconv/atoi.go @@ -57,6 +57,8 @@ const IntSize = intSize const maxUint64 = 1<<64 - 1 // ParseUint is like ParseInt but for unsigned numbers. +// +// A sign prefix is not permitted. func ParseUint(s string, base int, bitSize int) (uint64, error) { const fnParseUint = "ParseUint" @@ -143,7 +145,7 @@ func ParseUint(s string, base int, bitSize int) (uint64, error) { n1 := n + uint64(d) if n1 < n || n1 > maxVal { - // n+v overflows + // n+d overflows return maxVal, rangeError(fnParseUint, s0) } n = n1 @@ -159,10 +161,13 @@ func ParseUint(s string, base int, bitSize int) (uint64, error) { // ParseInt interprets a string s in the given base (0, 2 to 36) and // bit size (0 to 64) and returns the corresponding value i. // +// The string may begin with a leading sign: "+" or "-". +// // If the base argument is 0, the true base is implied by the string's -// prefix: 2 for "0b", 8 for "0" or "0o", 16 for "0x", and 10 otherwise. -// Also, for argument base 0 only, underscore characters are permitted -// as defined by the Go syntax for integer literals. +// prefix following the sign (if present): 2 for "0b", 8 for "0" or "0o", +// 16 for "0x", and 10 otherwise. Also, for argument base 0 only, +// underscore characters are permitted as defined by the Go syntax for +// integer literals. // // The bitSize argument specifies the integer type // that the result must fit into. Bit sizes 0, 8, 16, 32, and 64 diff --git a/libgo/go/strconv/atoi_test.go b/libgo/go/strconv/atoi_test.go index 178fb01..867fa66 100644 --- a/libgo/go/strconv/atoi_test.go +++ b/libgo/go/strconv/atoi_test.go @@ -33,6 +33,9 @@ var parseUint64Tests = []parseUint64Test{ {"_12345", 0, ErrSyntax}, {"1__2345", 0, ErrSyntax}, {"12345_", 0, ErrSyntax}, + {"-0", 0, ErrSyntax}, + {"-1", 0, ErrSyntax}, + {"+1", 0, ErrSyntax}, } type parseUint64BaseTest struct { @@ -140,8 +143,10 @@ var parseInt64Tests = []parseInt64Test{ {"", 0, ErrSyntax}, {"0", 0, nil}, {"-0", 0, nil}, + {"+0", 0, nil}, {"1", 1, nil}, {"-1", -1, nil}, + {"+1", 1, nil}, {"12345", 12345, nil}, {"-12345", -12345, nil}, {"012345", 12345, nil}, @@ -236,6 +241,11 @@ var parseInt64BaseTests = []parseInt64BaseTest{ {"0__12345", 0, 0, ErrSyntax}, {"01234__5", 0, 0, ErrSyntax}, {"012345_", 0, 0, ErrSyntax}, + + {"+0xf", 0, 0xf, nil}, + {"-0xf", 0, -0xf, nil}, + {"0x+f", 0, 0, ErrSyntax}, + {"0x-f", 0, 0, ErrSyntax}, } type parseUint32Test struct { diff --git a/libgo/go/strconv/bytealg.go b/libgo/go/strconv/bytealg.go new file mode 100644 index 0000000..a2bb12c --- /dev/null +++ b/libgo/go/strconv/bytealg.go @@ -0,0 +1,15 @@ +// 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:build !compiler_bootstrap +// +build !compiler_bootstrap + +package strconv + +import "internal/bytealg" + +// index returns the index of the first instance of c in s, or -1 if missing. +func index(s string, c byte) int { + return bytealg.IndexByteString(s, c) +} diff --git a/libgo/go/strconv/bytealg_bootstrap.go b/libgo/go/strconv/bytealg_bootstrap.go new file mode 100644 index 0000000..0ed79f4 --- /dev/null +++ b/libgo/go/strconv/bytealg_bootstrap.go @@ -0,0 +1,18 @@ +// Copyright 2020 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:build compiler_bootstrap +// +build compiler_bootstrap + +package strconv + +// index returns the index of the first instance of c in s, or -1 if missing. +func index(s string, c byte) int { + for i := 0; i < len(s); i++ { + if s[i] == c { + return i + } + } + return -1 +} diff --git a/libgo/go/strconv/eisel_lemire.go b/libgo/go/strconv/eisel_lemire.go index 6c7f852..fecd1b9 100644 --- a/libgo/go/strconv/eisel_lemire.go +++ b/libgo/go/strconv/eisel_lemire.go @@ -29,7 +29,7 @@ func eiselLemire64(man uint64, exp10 int, neg bool) (f float64, ok bool) { // Exp10 Range. if man == 0 { if neg { - f = math.Float64frombits(0x80000000_00000000) // Negative zero. + f = math.Float64frombits(0x8000000000000000) // Negative zero. } return f, true } @@ -39,7 +39,7 @@ func eiselLemire64(man uint64, exp10 int, neg bool) (f float64, ok bool) { // Normalization. clz := bits.LeadingZeros64(man) - man <<= clz + man <<= uint(clz) const float64ExponentBias = 1023 retExp2 := uint64(217706*exp10>>16+64+float64ExponentBias) - uint64(clz) @@ -84,9 +84,9 @@ func eiselLemire64(man uint64, exp10 int, neg bool) (f float64, ok bool) { if retExp2-1 >= 0x7FF-1 { return 0, false } - retBits := retExp2<<52 | retMantissa&0x000FFFFF_FFFFFFFF + retBits := retExp2<<52 | retMantissa&0x000FFFFFFFFFFFFF if neg { - retBits |= 0x80000000_00000000 + retBits |= 0x8000000000000000 } return math.Float64frombits(retBits), true } @@ -114,7 +114,7 @@ func eiselLemire32(man uint64, exp10 int, neg bool) (f float32, ok bool) { // Normalization. clz := bits.LeadingZeros64(man) - man <<= clz + man <<= uint(clz) const float32ExponentBias = 127 retExp2 := uint64(217706*exp10>>16+64+float32ExponentBias) - uint64(clz) @@ -122,13 +122,13 @@ func eiselLemire32(man uint64, exp10 int, neg bool) (f float32, ok bool) { xHi, xLo := bits.Mul64(man, detailedPowersOfTen[exp10-detailedPowersOfTenMinExp10][1]) // Wider Approximation. - if xHi&0x3F_FFFFFFFF == 0x3F_FFFFFFFF && xLo+man < man { + if xHi&0x3FFFFFFFFF == 0x3FFFFFFFFF && xLo+man < man { yHi, yLo := bits.Mul64(man, detailedPowersOfTen[exp10-detailedPowersOfTenMinExp10][0]) mergedHi, mergedLo := xHi, xLo+yHi if mergedLo < xLo { mergedHi++ } - if mergedHi&0x3F_FFFFFFFF == 0x3F_FFFFFFFF && mergedLo+1 == 0 && yLo+man < man { + if mergedHi&0x3FFFFFFFFF == 0x3FFFFFFFFF && mergedLo+1 == 0 && yLo+man < man { return 0, false } xHi, xLo = mergedHi, mergedLo @@ -140,7 +140,7 @@ func eiselLemire32(man uint64, exp10 int, neg bool) (f float32, ok bool) { retExp2 -= 1 ^ msb // Half-way Ambiguity. - if xLo == 0 && xHi&0x3F_FFFFFFFF == 0 && retMantissa&3 == 1 { + if xLo == 0 && xHi&0x3FFFFFFFFF == 0 && retMantissa&3 == 1 { return 0, false } diff --git a/libgo/go/strconv/extfloat.go b/libgo/go/strconv/extfloat.go deleted file mode 100644 index e7bfe51..0000000 --- a/libgo/go/strconv/extfloat.go +++ /dev/null @@ -1,517 +0,0 @@ -// 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 - -import ( - "math/bits" -) - -// 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. -// https://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 -} - -// 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() uint { - // bits.LeadingZeros64 would return 64 - if f.mant == 0 { - return 0 - } - shift := bits.LeadingZeros64(f.mant) - f.mant <<= uint(shift) - f.exp -= shift - return uint(shift) -} - -// Multiply sets f to the product f*g: the result is correctly rounded, -// but not normalized. -func (f *extFloat) Multiply(g extFloat) { - hi, lo := bits.Mul64(f.mant, g.mant) - // Round up. - f.mant = hi + (lo >> 63) - 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, -} - -// 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 an 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/libgo/go/strconv/ftoa.go b/libgo/go/strconv/ftoa.go index 8ce6ef3..eca04b8 100644 --- a/libgo/go/strconv/ftoa.go +++ b/libgo/go/strconv/ftoa.go @@ -113,15 +113,11 @@ func genericFtoa(dst []byte, val float64, fmt byte, prec, bitSize int) []byte { // 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) + // Use Ryu algorithm. var buf [32]byte digs.d = buf[:] - ok = f.ShortestDecimal(&digs, &lower, &upper) - if !ok { - return bigFtoa(dst, prec, fmt, neg, mant, exp, flt) - } + ryuFtoaShortest(&digs, mant, exp-int(flt.mantbits), flt) + ok = true // Precision for shortest representation mode. switch fmt { case 'e', 'E': @@ -143,12 +139,15 @@ func genericFtoa(dst []byte, val float64, fmt byte, prec, bitSize int) []byte { } digits = prec } - if digits <= 15 { - // try fast algorithm when the number of digits is reasonable. - var buf [24]byte + var buf [24]byte + if bitSize == 32 && digits <= 9 { + digs.d = buf[:] + ryuFtoaFixed32(&digs, uint32(mant), exp-int(flt.mantbits), digits) + ok = true + } else if digits <= 18 { digs.d = buf[:] - f := extFloat{mant, exp - int(flt.mantbits), neg} - ok = f.FixedDecimal(&digs, digits) + ryuFtoaFixed64(&digs, mant, exp-int(flt.mantbits), digits) + ok = true } } if !ok { diff --git a/libgo/go/strconv/ftoa_test.go b/libgo/go/strconv/ftoa_test.go index 99cca17..73008b1 100644 --- a/libgo/go/strconv/ftoa_test.go +++ b/libgo/go/strconv/ftoa_test.go @@ -40,6 +40,7 @@ var ftoatests = []ftoaTest{ {200000, 'x', -1, "0x1.86ap+17"}, {200000, 'X', -1, "0X1.86AP+17"}, {2000000, 'g', -1, "2e+06"}, + {1e10, 'g', -1, "1e+10"}, // g conversion and zero suppression {400, 'g', 2, "4e+02"}, @@ -77,6 +78,15 @@ var ftoatests = []ftoaTest{ {1.2345e6, 'f', 5, "1234500.00000"}, {1.2345e6, 'g', 5, "1.2345e+06"}, + // Round to even + {1.2345e6, 'e', 3, "1.234e+06"}, + {1.2355e6, 'e', 3, "1.236e+06"}, + {1.2345, 'f', 3, "1.234"}, + {1.2355, 'f', 3, "1.236"}, + {1234567890123456.5, 'e', 15, "1.234567890123456e+15"}, + {1234567890123457.5, 'e', 15, "1.234567890123458e+15"}, + {108678236358137.625, 'g', -1, "1.0867823635813762e+14"}, + {1e23, 'e', 17, "9.99999999999999916e+22"}, {1e23, 'f', 17, "99999999999999991611392.00000000000000000"}, {1e23, 'g', 17, "9.9999999999999992e+22"}, @@ -183,6 +193,25 @@ func TestFtoa(t *testing.T) { } } +func TestFtoaPowersOfTwo(t *testing.T) { + for exp := -2048; exp <= 2048; exp++ { + f := math.Ldexp(1, exp) + if !math.IsInf(f, 0) { + s := FormatFloat(f, 'e', -1, 64) + if x, _ := ParseFloat(s, 64); x != f { + t.Errorf("failed roundtrip %v => %s => %v", f, s, x) + } + } + f32 := float32(f) + if !math.IsInf(float64(f32), 0) { + s := FormatFloat(float64(f32), 'e', -1, 32) + if x, _ := ParseFloat(s, 32); float32(x) != f32 { + t.Errorf("failed roundtrip %v => %s => %v", f32, s, float32(x)) + } + } + } +} + func TestFtoaRandom(t *testing.T) { N := int(1e4) if testing.Short() { @@ -232,6 +261,7 @@ var ftoaBenches = []struct { {"Float", 339.7784, 'g', -1, 64}, {"Exp", -5.09e75, 'g', -1, 64}, {"NegExp", -5.11e-95, 'g', -1, 64}, + {"LongExp", 1.234567890123456e-78, 'g', -1, 64}, {"Big", 123456789123456789123456789, 'g', -1, 64}, {"BinaryExp", -1, 'b', -1, 64}, @@ -241,14 +271,30 @@ var ftoaBenches = []struct { {"32Point", 339.7784, 'g', -1, 32}, {"32Exp", -5.09e25, 'g', -1, 32}, {"32NegExp", -5.11e-25, 'g', -1, 32}, + {"32Shortest", 1.234567e-8, 'g', -1, 32}, + {"32Fixed8Hard", math.Ldexp(15961084, -125), 'e', 8, 32}, + {"32Fixed9Hard", math.Ldexp(14855922, -83), 'e', 9, 32}, {"64Fixed1", 123456, 'e', 3, 64}, {"64Fixed2", 123.456, 'e', 3, 64}, {"64Fixed3", 1.23456e+78, 'e', 3, 64}, {"64Fixed4", 1.23456e-78, 'e', 3, 64}, + {"64Fixed12", 1.23456e-78, 'e', 12, 64}, + {"64Fixed16", 1.23456e-78, 'e', 16, 64}, + // From testdata/testfp.txt + {"64Fixed12Hard", math.Ldexp(6965949469487146, -249), 'e', 12, 64}, + {"64Fixed17Hard", math.Ldexp(8887055249355788, 665), 'e', 17, 64}, + {"64Fixed18Hard", math.Ldexp(6994187472632449, 690), 'e', 18, 64}, // Trigger slow path (see issue #15672). - {"Slowpath64", 622666234635.3213e-320, 'e', -1, 64}, + // The shortest is: 8.034137530808823e+43 + {"Slowpath64", 8.03413753080882349e+43, 'e', -1, 64}, + // This denormal is pathological because the lower/upper + // halfways to neighboring floats are: + // 622666234635.321003e-320 ~= 622666234635.321e-320 + // 622666234635.321497e-320 ~= 622666234635.3215e-320 + // making it hard to find the 3rd digit + {"SlowpathDenormal64", 622666234635.3213e-320, 'e', -1, 64}, } func BenchmarkFormatFloat(b *testing.B) { diff --git a/libgo/go/strconv/ftoaryu.go b/libgo/go/strconv/ftoaryu.go new file mode 100644 index 0000000..1c61288 --- /dev/null +++ b/libgo/go/strconv/ftoaryu.go @@ -0,0 +1,567 @@ +// Copyright 2021 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 ( + "math/bits" +) + +// binary to decimal conversion using the Ryū algorithm. +// +// See Ulf Adams, "Ryū: Fast Float-to-String Conversion" (doi:10.1145/3192366.3192369) +// +// Fixed precision formatting is a variant of the original paper's +// algorithm, where a single multiplication by 10^k is required, +// sharing the same rounding guarantees. + +// ryuFtoaFixed32 formats mant*(2^exp) with prec decimal digits. +func ryuFtoaFixed32(d *decimalSlice, mant uint32, exp int, prec int) { + if prec < 0 { + panic("ryuFtoaFixed32 called with negative prec") + } + if prec > 9 { + panic("ryuFtoaFixed32 called with prec > 9") + } + // Zero input. + if mant == 0 { + d.nd, d.dp = 0, 0 + return + } + // Renormalize to a 25-bit mantissa. + e2 := exp + if b := bits.Len32(mant); b < 25 { + mant <<= uint(25 - b) + e2 += int(b) - 25 + } + // Choose an exponent such that rounded mant*(2^e2)*(10^q) has + // at least prec decimal digits, i.e + // mant*(2^e2)*(10^q) >= 10^(prec-1) + // Because mant >= 2^24, it is enough to choose: + // 2^(e2+24) >= 10^(-q+prec-1) + // or q = -mulByLog2Log10(e2+24) + prec - 1 + q := -mulByLog2Log10(e2+24) + prec - 1 + + // Now compute mant*(2^e2)*(10^q). + // Is it an exact computation? + // Only small positive powers of 10 are exact (5^28 has 66 bits). + exact := q <= 27 && q >= 0 + + di, dexp2, d0 := mult64bitPow10(mant, e2, q) + if dexp2 >= 0 { + panic("not enough significant bits after mult64bitPow10") + } + // As a special case, computation might still be exact, if exponent + // was negative and if it amounts to computing an exact division. + // In that case, we ignore all lower bits. + // Note that division by 10^11 cannot be exact as 5^11 has 26 bits. + if q < 0 && q >= -10 && divisibleByPower5(uint64(mant), -q) { + exact = true + d0 = true + } + // Remove extra lower bits and keep rounding info. + extra := uint(-dexp2) + extraMask := uint32(1<<extra - 1) + + di, dfrac := di>>extra, di&extraMask + roundUp := false + if exact { + // If we computed an exact product, d + 1/2 + // should round to d+1 if 'd' is odd. + roundUp = dfrac > 1<<(extra-1) || + (dfrac == 1<<(extra-1) && !d0) || + (dfrac == 1<<(extra-1) && d0 && di&1 == 1) + } else { + // otherwise, d+1/2 always rounds up because + // we truncated below. + roundUp = dfrac>>(extra-1) == 1 + } + if dfrac != 0 { + d0 = false + } + // Proceed to the requested number of digits + formatDecimal(d, uint64(di), !d0, roundUp, prec) + // Adjust exponent + d.dp -= q +} + +// ryuFtoaFixed64 formats mant*(2^exp) with prec decimal digits. +func ryuFtoaFixed64(d *decimalSlice, mant uint64, exp int, prec int) { + if prec > 18 { + panic("ryuFtoaFixed64 called with prec > 18") + } + // Zero input. + if mant == 0 { + d.nd, d.dp = 0, 0 + return + } + // Renormalize to a 55-bit mantissa. + e2 := exp + if b := bits.Len64(mant); b < 55 { + mant = mant << uint(55-b) + e2 += int(b) - 55 + } + // Choose an exponent such that rounded mant*(2^e2)*(10^q) has + // at least prec decimal digits, i.e + // mant*(2^e2)*(10^q) >= 10^(prec-1) + // Because mant >= 2^54, it is enough to choose: + // 2^(e2+54) >= 10^(-q+prec-1) + // or q = -mulByLog2Log10(e2+54) + prec - 1 + // + // The minimal required exponent is -mulByLog2Log10(1025)+18 = -291 + // The maximal required exponent is mulByLog2Log10(1074)+18 = 342 + q := -mulByLog2Log10(e2+54) + prec - 1 + + // Now compute mant*(2^e2)*(10^q). + // Is it an exact computation? + // Only small positive powers of 10 are exact (5^55 has 128 bits). + exact := q <= 55 && q >= 0 + + di, dexp2, d0 := mult128bitPow10(mant, e2, q) + if dexp2 >= 0 { + panic("not enough significant bits after mult128bitPow10") + } + // As a special case, computation might still be exact, if exponent + // was negative and if it amounts to computing an exact division. + // In that case, we ignore all lower bits. + // Note that division by 10^23 cannot be exact as 5^23 has 54 bits. + if q < 0 && q >= -22 && divisibleByPower5(mant, -q) { + exact = true + d0 = true + } + // Remove extra lower bits and keep rounding info. + extra := uint(-dexp2) + extraMask := uint64(1<<extra - 1) + + di, dfrac := di>>extra, di&extraMask + roundUp := false + if exact { + // If we computed an exact product, d + 1/2 + // should round to d+1 if 'd' is odd. + roundUp = dfrac > 1<<(extra-1) || + (dfrac == 1<<(extra-1) && !d0) || + (dfrac == 1<<(extra-1) && d0 && di&1 == 1) + } else { + // otherwise, d+1/2 always rounds up because + // we truncated below. + roundUp = dfrac>>(extra-1) == 1 + } + if dfrac != 0 { + d0 = false + } + // Proceed to the requested number of digits + formatDecimal(d, di, !d0, roundUp, prec) + // Adjust exponent + d.dp -= q +} + +var uint64pow10 = [...]uint64{ + 1, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, + 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19, +} + +// formatDecimal fills d with at most prec decimal digits +// of mantissa m. The boolean trunc indicates whether m +// is truncated compared to the original number being formatted. +func formatDecimal(d *decimalSlice, m uint64, trunc bool, roundUp bool, prec int) { + max := uint64pow10[prec] + trimmed := 0 + for m >= max { + a, b := m/10, m%10 + m = a + trimmed++ + if b > 5 { + roundUp = true + } else if b < 5 { + roundUp = false + } else { // b == 5 + // round up if there are trailing digits, + // or if the new value of m is odd (round-to-even convention) + roundUp = trunc || m&1 == 1 + } + if b != 0 { + trunc = true + } + } + if roundUp { + m++ + } + if m >= max { + // Happens if di was originally 99999....xx + m /= 10 + trimmed++ + } + // render digits (similar to formatBits) + n := uint(prec) + d.nd = int(prec) + v := m + for v >= 100 { + var v1, v2 uint64 + if v>>32 == 0 { + v1, v2 = uint64(uint32(v)/100), uint64(uint32(v)%100) + } else { + v1, v2 = v/100, v%100 + } + n -= 2 + d.d[n+1] = smallsString[2*v2+1] + d.d[n+0] = smallsString[2*v2+0] + v = v1 + } + if v > 0 { + n-- + d.d[n] = smallsString[2*v+1] + } + if v >= 10 { + n-- + d.d[n] = smallsString[2*v] + } + for d.d[d.nd-1] == '0' { + d.nd-- + trimmed++ + } + d.dp = d.nd + trimmed +} + +// ryuFtoaShortest formats mant*2^exp with prec decimal digits. +func ryuFtoaShortest(d *decimalSlice, mant uint64, exp int, flt *floatInfo) { + if mant == 0 { + d.nd, d.dp = 0, 0 + return + } + // If input is an exact integer with fewer bits than the mantissa, + // the previous and next integer are not admissible representations. + if exp <= 0 && bits.TrailingZeros64(mant) >= -exp { + mant >>= uint(-exp) + ryuDigits(d, mant, mant, mant, true, false) + return + } + ml, mc, mu, e2 := computeBounds(mant, exp, flt) + if e2 == 0 { + ryuDigits(d, ml, mc, mu, true, false) + return + } + // Find 10^q *larger* than 2^-e2 + q := mulByLog2Log10(-e2) + 1 + + // We are going to multiply by 10^q using 128-bit arithmetic. + // The exponent is the same for all 3 numbers. + var dl, dc, du uint64 + var dl0, dc0, du0 bool + if flt == &float32info { + var dl32, dc32, du32 uint32 + dl32, _, dl0 = mult64bitPow10(uint32(ml), e2, q) + dc32, _, dc0 = mult64bitPow10(uint32(mc), e2, q) + du32, e2, du0 = mult64bitPow10(uint32(mu), e2, q) + dl, dc, du = uint64(dl32), uint64(dc32), uint64(du32) + } else { + dl, _, dl0 = mult128bitPow10(ml, e2, q) + dc, _, dc0 = mult128bitPow10(mc, e2, q) + du, e2, du0 = mult128bitPow10(mu, e2, q) + } + if e2 >= 0 { + panic("not enough significant bits after mult128bitPow10") + } + // Is it an exact computation? + if q > 55 { + // Large positive powers of ten are not exact + dl0, dc0, du0 = false, false, false + } + if q < 0 && q >= -24 { + // Division by a power of ten may be exact. + // (note that 5^25 is a 59-bit number so division by 5^25 is never exact). + if divisibleByPower5(ml, -q) { + dl0 = true + } + if divisibleByPower5(mc, -q) { + dc0 = true + } + if divisibleByPower5(mu, -q) { + du0 = true + } + } + // Express the results (dl, dc, du)*2^e2 as integers. + // Extra bits must be removed and rounding hints computed. + extra := uint(-e2) + extraMask := uint64(1<<extra - 1) + // Now compute the floored, integral base 10 mantissas. + dl, fracl := dl>>extra, dl&extraMask + dc, fracc := dc>>extra, dc&extraMask + du, fracu := du>>extra, du&extraMask + // Is it allowed to use 'du' as a result? + // It is always allowed when it is truncated, but also + // if it is exact and the original binary mantissa is even + // When disallowed, we can substract 1. + uok := !du0 || fracu > 0 + if du0 && fracu == 0 { + uok = mant&1 == 0 + } + if !uok { + du-- + } + // Is 'dc' the correctly rounded base 10 mantissa? + // The correct rounding might be dc+1 + cup := false // don't round up. + if dc0 { + // If we computed an exact product, the half integer + // should round to next (even) integer if 'dc' is odd. + cup = fracc > 1<<(extra-1) || + (fracc == 1<<(extra-1) && dc&1 == 1) + } else { + // otherwise, the result is a lower truncation of the ideal + // result. + cup = fracc>>(extra-1) == 1 + } + // Is 'dl' an allowed representation? + // Only if it is an exact value, and if the original binary mantissa + // was even. + lok := dl0 && fracl == 0 && (mant&1 == 0) + if !lok { + dl++ + } + // We need to remember whether the trimmed digits of 'dc' are zero. + c0 := dc0 && fracc == 0 + // render digits + ryuDigits(d, dl, dc, du, c0, cup) + d.dp -= q +} + +// mulByLog2Log10 returns math.Floor(x * log(2)/log(10)) for an integer x in +// the range -1600 <= x && x <= +1600. +// +// The range restriction lets us work in faster integer arithmetic instead of +// slower floating point arithmetic. Correctness is verified by unit tests. +func mulByLog2Log10(x int) int { + // log(2)/log(10) ≈ 0.30102999566 ≈ 78913 / 2^18 + return (x * 78913) >> 18 +} + +// mulByLog10Log2 returns math.Floor(x * log(10)/log(2)) for an integer x in +// the range -500 <= x && x <= +500. +// +// The range restriction lets us work in faster integer arithmetic instead of +// slower floating point arithmetic. Correctness is verified by unit tests. +func mulByLog10Log2(x int) int { + // log(10)/log(2) ≈ 3.32192809489 ≈ 108853 / 2^15 + return (x * 108853) >> 15 +} + +// computeBounds returns a floating-point vector (l, c, u)×2^e2 +// where the mantissas are 55-bit (or 26-bit) integers, describing the interval +// represented by the input float64 or float32. +func computeBounds(mant uint64, exp int, flt *floatInfo) (lower, central, upper uint64, e2 int) { + if mant != 1<<flt.mantbits || exp == flt.bias+1-int(flt.mantbits) { + // regular case (or denormals) + lower, central, upper = 2*mant-1, 2*mant, 2*mant+1 + e2 = exp - 1 + return + } else { + // border of an exponent + lower, central, upper = 4*mant-1, 4*mant, 4*mant+2 + e2 = exp - 2 + return + } +} + +func ryuDigits(d *decimalSlice, lower, central, upper uint64, + c0, cup bool) { + lhi, llo := divmod1e9(lower) + chi, clo := divmod1e9(central) + uhi, ulo := divmod1e9(upper) + if uhi == 0 { + // only low digits (for denormals) + ryuDigits32(d, llo, clo, ulo, c0, cup, 8) + } else if lhi < uhi { + // truncate 9 digits at once. + if llo != 0 { + lhi++ + } + c0 = c0 && clo == 0 + cup = (clo > 5e8) || (clo == 5e8 && cup) + ryuDigits32(d, lhi, chi, uhi, c0, cup, 8) + d.dp += 9 + } else { + d.nd = 0 + // emit high part + n := uint(9) + for v := chi; v > 0; { + v1, v2 := v/10, v%10 + v = v1 + n-- + d.d[n] = byte(v2 + '0') + } + d.d = d.d[n:] + d.nd = int(9 - n) + // emit low part + ryuDigits32(d, llo, clo, ulo, + c0, cup, d.nd+8) + } + // trim trailing zeros + for d.nd > 0 && d.d[d.nd-1] == '0' { + d.nd-- + } + // trim initial zeros + for d.nd > 0 && d.d[0] == '0' { + d.nd-- + d.dp-- + d.d = d.d[1:] + } +} + +// ryuDigits32 emits decimal digits for a number less than 1e9. +func ryuDigits32(d *decimalSlice, lower, central, upper uint32, + c0, cup bool, endindex int) { + if upper == 0 { + d.dp = endindex + 1 + return + } + trimmed := 0 + // Remember last trimmed digit to check for round-up. + // c0 will be used to remember zeroness of following digits. + cNextDigit := 0 + for upper > 0 { + // Repeatedly compute: + // l = Ceil(lower / 10^k) + // c = Round(central / 10^k) + // u = Floor(upper / 10^k) + // and stop when c goes out of the (l, u) interval. + l := (lower + 9) / 10 + c, cdigit := central/10, central%10 + u := upper / 10 + if l > u { + // don't trim the last digit as it is forbidden to go below l + // other, trim and exit now. + break + } + // Check that we didn't cross the lower boundary. + // The case where l < u but c == l-1 is essentially impossible, + // but may happen if: + // lower = ..11 + // central = ..19 + // upper = ..31 + // and means that 'central' is very close but less than + // an integer ending with many zeros, and usually + // the "round-up" logic hides the problem. + if l == c+1 && c < u { + c++ + cdigit = 0 + cup = false + } + trimmed++ + // Remember trimmed digits of c + c0 = c0 && cNextDigit == 0 + cNextDigit = int(cdigit) + lower, central, upper = l, c, u + } + // should we round up? + if trimmed > 0 { + cup = cNextDigit > 5 || + (cNextDigit == 5 && !c0) || + (cNextDigit == 5 && c0 && central&1 == 1) + } + if central < upper && cup { + central++ + } + // We know where the number ends, fill directly + endindex -= trimmed + v := central + n := endindex + for n > d.nd { + v1, v2 := v/100, v%100 + d.d[n] = smallsString[2*v2+1] + d.d[n-1] = smallsString[2*v2+0] + n -= 2 + v = v1 + } + if n == d.nd { + d.d[n] = byte(v + '0') + } + d.nd = endindex + 1 + d.dp = d.nd + trimmed +} + +// mult64bitPow10 takes a floating-point input with a 25-bit +// mantissa and multiplies it with 10^q. The resulting mantissa +// is m*P >> 57 where P is a 64-bit element of the detailedPowersOfTen tables. +// It is typically 31 or 32-bit wide. +// The returned boolean is true if all trimmed bits were zero. +// +// That is: +// m*2^e2 * round(10^q) = resM * 2^resE + ε +// exact = ε == 0 +func mult64bitPow10(m uint32, e2, q int) (resM uint32, resE int, exact bool) { + if q == 0 { + // P == 1<<63 + return m << 6, e2 - 6, true + } + if q < detailedPowersOfTenMinExp10 || detailedPowersOfTenMaxExp10 < q { + // This never happens due to the range of float32/float64 exponent + panic("mult64bitPow10: power of 10 is out of range") + } + pow := detailedPowersOfTen[q-detailedPowersOfTenMinExp10][1] + if q < 0 { + // Inverse powers of ten must be rounded up. + pow += 1 + } + hi, lo := bits.Mul64(uint64(m), pow) + e2 += mulByLog10Log2(q) - 63 + 57 + return uint32(hi<<7 | lo>>57), e2, lo<<7 == 0 +} + +// mult128bitPow10 takes a floating-point input with a 55-bit +// mantissa and multiplies it with 10^q. The resulting mantissa +// is m*P >> 119 where P is a 128-bit element of the detailedPowersOfTen tables. +// It is typically 63 or 64-bit wide. +// The returned boolean is true is all trimmed bits were zero. +// +// That is: +// m*2^e2 * round(10^q) = resM * 2^resE + ε +// exact = ε == 0 +func mult128bitPow10(m uint64, e2, q int) (resM uint64, resE int, exact bool) { + if q == 0 { + // P == 1<<127 + return m << 8, e2 - 8, true + } + if q < detailedPowersOfTenMinExp10 || detailedPowersOfTenMaxExp10 < q { + // This never happens due to the range of float32/float64 exponent + panic("mult128bitPow10: power of 10 is out of range") + } + pow := detailedPowersOfTen[q-detailedPowersOfTenMinExp10] + if q < 0 { + // Inverse powers of ten must be rounded up. + pow[0] += 1 + } + e2 += mulByLog10Log2(q) - 127 + 119 + + // long multiplication + l1, l0 := bits.Mul64(m, pow[0]) + h1, h0 := bits.Mul64(m, pow[1]) + mid, carry := bits.Add64(l1, h0, 0) + h1 += carry + return h1<<9 | mid>>55, e2, mid<<9 == 0 && l0 == 0 +} + +func divisibleByPower5(m uint64, k int) bool { + if m == 0 { + return true + } + for i := 0; i < k; i++ { + if m%5 != 0 { + return false + } + m /= 5 + } + return true +} + +// divmod1e9 computes quotient and remainder of division by 1e9, +// avoiding runtime uint64 division on 32-bit platforms. +func divmod1e9(x uint64) (uint32, uint32) { + if !host32bit { + return uint32(x / 1e9), uint32(x % 1e9) + } + // Use the same sequence of operations as the amd64 compiler. + hi, _ := bits.Mul64(x>>1, 0x89705f4136b4a598) // binary digits of 1e-9 + q := hi >> 28 + return uint32(q), uint32(x - q*1e9) +} diff --git a/libgo/go/strconv/ftoaryu_test.go b/libgo/go/strconv/ftoaryu_test.go new file mode 100644 index 0000000..9758619 --- /dev/null +++ b/libgo/go/strconv/ftoaryu_test.go @@ -0,0 +1,31 @@ +// Copyright 2021 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" + . "strconv" + "testing" +) + +func TestMulByLog2Log10(t *testing.T) { + for x := -1600; x <= +1600; x++ { + iMath := MulByLog2Log10(x) + fMath := int(math.Floor(float64(x) * math.Ln2 / math.Ln10)) + if iMath != fMath { + t.Errorf("mulByLog2Log10(%d) failed: %d vs %d\n", x, iMath, fMath) + } + } +} + +func TestMulByLog10Log2(t *testing.T) { + for x := -500; x <= +500; x++ { + iMath := MulByLog10Log2(x) + fMath := int(math.Floor(float64(x) * math.Ln10 / math.Ln2)) + if iMath != fMath { + t.Errorf("mulByLog10Log2(%d) failed: %d vs %d\n", x, iMath, fMath) + } + } +} diff --git a/libgo/go/strconv/internal_test.go b/libgo/go/strconv/internal_test.go index bb4a418..f2cceff 100644 --- a/libgo/go/strconv/internal_test.go +++ b/libgo/go/strconv/internal_test.go @@ -21,3 +21,11 @@ func SetOptimize(b bool) bool { func ParseFloatPrefix(s string, bitSize int) (float64, int, error) { return parseFloatPrefix(s, bitSize) } + +func MulByLog2Log10(x int) int { + return mulByLog2Log10(x) +} + +func MulByLog10Log2(x int) int { + return mulByLog10Log2(x) +} diff --git a/libgo/go/strconv/makeisprint.go b/libgo/go/strconv/makeisprint.go index 0e6e90a..909f9e4 100644 --- a/libgo/go/strconv/makeisprint.go +++ b/libgo/go/strconv/makeisprint.go @@ -2,6 +2,7 @@ // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. +//go:build ignore // +build ignore // @@ -36,7 +37,7 @@ var ( func bsearch16(a []uint16, x uint16) int { i, j := 0, len(a) for i < j { - h := i + (j-i)/2 + h := i + (j-i)>>1 if a[h] < x { i = h + 1 } else { @@ -51,7 +52,7 @@ func bsearch16(a []uint16, x uint16) int { func bsearch32(a []uint32, x uint32) int { i, j := 0, len(a) for i < j { - h := i + (j-i)/2 + h := i + (j-i)>>1 if a[h] < x { i = h + 1 } else { diff --git a/libgo/go/strconv/quote.go b/libgo/go/strconv/quote.go index bcbdbc5..b3bbb16 100644 --- a/libgo/go/strconv/quote.go +++ b/libgo/go/strconv/quote.go @@ -7,7 +7,6 @@ package strconv import ( - "internal/bytealg" "unicode/utf8" ) @@ -16,6 +15,11 @@ const ( upperhex = "0123456789ABCDEF" ) +// contains reports whether the string contains the byte c. +func contains(s string, c byte) bool { + return index(s, c) != -1 +} + func quoteWith(s string, quote byte, ASCIIonly, graphicOnly bool) string { return string(appendQuotedWith(make([]byte, 0, 3*len(s)/2), s, quote, ASCIIonly, graphicOnly)) } @@ -360,85 +364,132 @@ func UnquoteChar(s string, quote byte) (value rune, multibyte bool, tail string, return } +// QuotedPrefix returns the quoted string (as understood by Unquote) at the prefix of s. +// If s does not start with a valid quoted string, QuotedPrefix returns an error. +func QuotedPrefix(s string) (string, error) { + out, _, err := unquote(s, false) + return out, err +} + // 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) (string, error) { - n := len(s) - if n < 2 { + out, rem, err := unquote(s, true) + if len(rem) > 0 { return "", ErrSyntax } - quote := s[0] - if quote != s[n-1] { - return "", ErrSyntax + return out, err +} + +// unquote parses a quoted string at the start of the input, +// returning the parsed prefix, the remaining suffix, and any parse errors. +// If unescape is true, the parsed prefix is unescaped, +// otherwise the input prefix is provided verbatim. +func unquote(in string, unescape bool) (out, rem string, err error) { + // Determine the quote form and optimistically find the terminating quote. + if len(in) < 2 { + return "", in, ErrSyntax } - s = s[1 : n-1] + quote := in[0] + end := index(in[1:], quote) + if end < 0 { + return "", in, ErrSyntax + } + end += 2 // position after terminating quote; may be wrong if escape sequences are present - if quote == '`' { - if contains(s, '`') { - return "", ErrSyntax + switch quote { + case '`': + switch { + case !unescape: + out = in[:end] // include quotes + case !contains(in[:end], '\r'): + out = in[len("`") : end-len("`")] // exclude quotes + default: + // Carriage return characters ('\r') inside raw string literals + // are discarded from the raw string value. + buf := make([]byte, 0, end-len("`")-len("\r")-len("`")) + for i := len("`"); i < end-len("`"); i++ { + if in[i] != '\r' { + buf = append(buf, in[i]) + } + } + out = string(buf) } - if contains(s, '\r') { - // -1 because we know there is at least one \r to remove. - buf := make([]byte, 0, len(s)-1) - for i := 0; i < len(s); i++ { - if s[i] != '\r' { - buf = append(buf, s[i]) + // NOTE: Prior implementations did not verify that raw strings consist + // of valid UTF-8 characters and we continue to not verify it as such. + // The Go specification does not explicitly require valid UTF-8, + // but only mention that it is implicitly valid for Go source code + // (which must be valid UTF-8). + return out, in[end:], nil + case '"', '\'': + // Handle quoted strings without any escape sequences. + if !contains(in[:end], '\\') && !contains(in[:end], '\n') { + var valid bool + switch quote { + case '"': + valid = utf8.ValidString(in[len(`"`) : end-len(`"`)]) + case '\'': + r, n := utf8.DecodeRuneInString(in[len("'") : end-len("'")]) + valid = len("'")+n+len("'") == end && (r != utf8.RuneError || n != 1) + } + if valid { + out = in[:end] + if unescape { + out = out[1 : end-1] // exclude quotes } + return out, in[end:], nil } - return string(buf), nil } - 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 '"': - if utf8.ValidString(s) { - return s, nil + // Handle quoted strings with escape sequences. + var buf []byte + in0 := in + in = in[1:] // skip starting quote + if unescape { + buf = make([]byte, 0, 3*end/2) // try to avoid more allocations + } + for len(in) > 0 && in[0] != quote { + // Process the next character, + // rejecting any unescaped newline characters which are invalid. + r, multibyte, rem, err := UnquoteChar(in, quote) + if in[0] == '\n' || err != nil { + return "", in0, ErrSyntax } - case '\'': - r, size := utf8.DecodeRuneInString(s) - if size == len(s) && (r != utf8.RuneError || size != 1) { - return s, nil + in = rem + + // Append the character if unescaping the input. + if unescape { + if r < utf8.RuneSelf || !multibyte { + buf = append(buf, byte(r)) + } else { + var arr [utf8.UTFMax]byte + n := utf8.EncodeRune(arr[:], r) + buf = append(buf, arr[:n]...) + } } - } - } - 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 + // Single quoted strings must be a single character. + if quote == '\'' { + break + } } - s = ss - if c < utf8.RuneSelf || !multibyte { - buf = append(buf, byte(c)) - } else { - n := utf8.EncodeRune(runeTmp[:], c) - buf = append(buf, runeTmp[:n]...) + + // Verify that the string ends with a terminating quote. + if !(len(in) > 0 && in[0] == quote) { + return "", in0, ErrSyntax } - if quote == '\'' && len(s) != 0 { - // single-quoted must be single character - return "", ErrSyntax + in = in[1:] // skip terminating quote + + if unescape { + return string(buf), in, nil } + return in0[:len(in0)-len(in)], in, nil + default: + return "", in, ErrSyntax } - return string(buf), nil -} - -// contains reports whether the string contains the byte c. -func contains(s string, c byte) bool { - return bytealg.IndexByteString(s, c) != -1 } // bsearch16 returns the smallest i such that a[i] >= x. @@ -446,7 +497,7 @@ func contains(s string, c byte) bool { func bsearch16(a []uint16, x uint16) int { i, j := 0, len(a) for i < j { - h := i + (j-i)/2 + h := i + (j-i)>>1 if a[h] < x { i = h + 1 } else { @@ -461,7 +512,7 @@ func bsearch16(a []uint16, x uint16) int { func bsearch32(a []uint32, x uint32) int { i, j := 0, len(a) for i < j { - h := i + (j-i)/2 + h := i + (j-i)>>1 if a[h] < x { i = h + 1 } else { diff --git a/libgo/go/strconv/quote_test.go b/libgo/go/strconv/quote_test.go index f1faf13..4750be2 100644 --- a/libgo/go/strconv/quote_test.go +++ b/libgo/go/strconv/quote_test.go @@ -6,6 +6,7 @@ package strconv_test import ( . "strconv" + "strings" "testing" "unicode" ) @@ -297,6 +298,7 @@ var misquoted = []string{ `"\z"`, "`", "`xxx", + "``x\r", "`\"", `"\'"`, `'\"'`, @@ -307,22 +309,13 @@ var misquoted = []string{ 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) - } + testUnquote(t, tt.in, tt.out, nil) } - - // 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) - } + testUnquote(t, tt.out, tt.in, nil) } - 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) - } + testUnquote(t, s, "", ErrSyntax) } } @@ -333,26 +326,44 @@ func TestUnquoteInvalidUTF8(t *testing.T) { // one of: want string - wantErr string + wantErr error }{ {in: `"foo"`, want: "foo"}, - {in: `"foo`, wantErr: "invalid syntax"}, + {in: `"foo`, wantErr: ErrSyntax}, {in: `"` + "\xc0" + `"`, want: "\xef\xbf\xbd"}, {in: `"a` + "\xc0" + `"`, want: "a\xef\xbf\xbd"}, {in: `"\t` + "\xc0" + `"`, want: "\t\xef\xbf\xbd"}, } - for i, tt := range tests { - got, err := Unquote(tt.in) - var gotErr string - if err != nil { - gotErr = err.Error() - } - if gotErr != tt.wantErr { - t.Errorf("%d. Unquote(%q) = err %v; want %q", i, tt.in, err, tt.wantErr) - } - if tt.wantErr == "" && err == nil && got != tt.want { - t.Errorf("%d. Unquote(%q) = %02x; want %02x", i, tt.in, []byte(got), []byte(tt.want)) - } + for _, tt := range tests { + testUnquote(t, tt.in, tt.want, tt.wantErr) + } +} + +func testUnquote(t *testing.T, in, want string, wantErr error) { + // Test Unquote. + got, gotErr := Unquote(in) + if got != want || gotErr != wantErr { + t.Errorf("Unquote(%q) = (%q, %v), want (%q, %v)", in, got, gotErr, want, wantErr) + } + + // Test QuotedPrefix. + // Adding an arbitrary suffix should not change the result of QuotedPrefix + // assume that the suffix doesn't accidentally terminate a truncated input. + if gotErr == nil { + want = in + } + suffix := "\n\r\\\"`'" // special characters for quoted strings + if len(in) > 0 { + suffix = strings.ReplaceAll(suffix, in[:1], "") + } + in += suffix + got, gotErr = QuotedPrefix(in) + if gotErr == nil && wantErr != nil { + _, wantErr = Unquote(got) // original input had trailing junk, reparse with only valid prefix + want = got + } + if got != want || gotErr != wantErr { + t.Errorf("QuotedPrefix(%q) = (%q, %v), want (%q, %v)", in, got, gotErr, want, wantErr) } } |