File size: 6,759 Bytes
e36aeda | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 | // Copyright 2025 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"
// A uint128 is a 128-bit uint.
// The fields are exported to make them visible to package strconv_test.
type uint128 struct {
Hi uint64
Lo uint64
}
// umul128 returns the 128-bit product x*y.
func umul128(x, y uint64) uint128 {
hi, lo := bits.Mul64(x, y)
return uint128{hi, lo}
}
// umul192 returns the 192-bit product x*y in three uint64s.
func umul192(x uint64, y uint128) (hi, mid, lo uint64) {
mid1, lo := bits.Mul64(x, y.Lo)
hi, mid2 := bits.Mul64(x, y.Hi)
mid, carry := bits.Add64(mid1, mid2, 0)
return hi + carry, mid, lo
}
// pow10 returns the 128-bit mantissa and binary exponent of 10**e.
// That is, 10^e = mant/2^128 * 2**exp.
// If e is out of range, pow10 returns ok=false.
func pow10(e int) (mant uint128, exp int, ok bool) {
if e < pow10Min || e > pow10Max {
return
}
return pow10Tab[e-pow10Min], 1 + mulLog2_10(e), true
}
// mulLog10_2 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 mulLog10_2(x int) int {
// log(2)/log(10) ≈ 0.30102999566 ≈ 78913 / 2^18
return (x * 78913) >> 18
}
// mulLog2_10 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 mulLog2_10(x int) int {
// log(10)/log(2) ≈ 3.32192809489 ≈ 108853 / 2^15
return (x * 108853) >> 15
}
func bool2uint(b bool) uint {
if b {
return 1
}
return 0
}
// Exact Division and Remainder Checking
//
// An exact division x/c (exact means x%c == 0)
// can be implemented by x*m where m is the multiplicative inverse of c (m*c == 1).
//
// Since c is also the multiplicative inverse of m, x*m is lossless,
// and all the exact multiples of c map to all of [0, maxUint64/c].
// The non-multiples are forced to map to larger values.
// This also gives a quick test for whether x is an exact multiple of c:
// compute the exact division and check whether it's at most maxUint64/c:
// x%c == 0 => x*m <= maxUint64/c.
//
// Only odd c have multiplicative inverses mod powers of two.
// To do an exact divide x / (c<<s) we can use (x/c)>>s instead.
// And to check for remainder, we need to check that those low s
// bits are all zero before we shift them away. We can merge that
// with the <= for the exact odd remainder check by rotating the
// shifted bits into the high part instead:
// x%(c<<s) == 0 => bits.RotateLeft64(x*m, -s) <= maxUint64/c.
//
// The compiler does this transformation automatically in general,
// but we apply it here by hand in a few ways that the compiler can't help with.
//
// For a more detailed explanation, see
// Henry S. Warren, Jr., Hacker's Delight, 2nd ed., sections 10-16 and 10-17.
// divisiblePow5 reports whether x is divisible by 5^p.
// It returns false for p not in [1, 22],
// because we only care about float64 mantissas, and 5^23 > 2^53.
func divisiblePow5(x uint64, p int) bool {
return 1 <= p && p <= 22 && x*div5Tab[p-1][0] <= div5Tab[p-1][1]
}
const maxUint64 = 1<<64 - 1
// div5Tab[p-1] is the multiplicative inverse of 5^p and maxUint64/5^p.
var div5Tab = [22][2]uint64{
{0xcccccccccccccccd, maxUint64 / 5},
{0x8f5c28f5c28f5c29, maxUint64 / 5 / 5},
{0x1cac083126e978d5, maxUint64 / 5 / 5 / 5},
{0xd288ce703afb7e91, maxUint64 / 5 / 5 / 5 / 5},
{0x5d4e8fb00bcbe61d, maxUint64 / 5 / 5 / 5 / 5 / 5},
{0x790fb65668c26139, maxUint64 / 5 / 5 / 5 / 5 / 5 / 5},
{0xe5032477ae8d46a5, maxUint64 / 5 / 5 / 5 / 5 / 5 / 5 / 5},
{0xc767074b22e90e21, maxUint64 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5},
{0x8e47ce423a2e9c6d, maxUint64 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5},
{0x4fa7f60d3ed61f49, maxUint64 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5},
{0x0fee64690c913975, maxUint64 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5},
{0x3662e0e1cf503eb1, maxUint64 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5},
{0xa47a2cf9f6433fbd, maxUint64 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5},
{0x54186f653140a659, maxUint64 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5},
{0x7738164770402145, maxUint64 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5},
{0xe4a4d1417cd9a041, maxUint64 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5},
{0xc75429d9e5c5200d, maxUint64 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5},
{0xc1773b91fac10669, maxUint64 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5},
{0x26b172506559ce15, maxUint64 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5},
{0xd489e3a9addec2d1, maxUint64 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5},
{0x90e860bb892c8d5d, maxUint64 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5},
{0x502e79bf1b6f4f79, maxUint64 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5 / 5},
}
// trimZeros trims trailing zeros from x.
// It finds the largest p such that x % 10^p == 0
// and then returns x / 10^p, p.
//
// This is here for reference and tested, because it is an optimization
// used by other ftoa algorithms, but in our implementations it has
// never been benchmarked to be faster than trimming zeros after
// formatting into decimal bytes.
func trimZeros(x uint64) (uint64, int) {
const (
div1e8m = 0xc767074b22e90e21
div1e8le = maxUint64 / 100000000
div1e4m = 0xd288ce703afb7e91
div1e4le = maxUint64 / 10000
div1e2m = 0x8f5c28f5c28f5c29
div1e2le = maxUint64 / 100
div1e1m = 0xcccccccccccccccd
div1e1le = maxUint64 / 10
)
// _ = assert[x - y] asserts at compile time that x == y.
// Assert that the multiplicative inverses are correct
// by checking that (div1eNm * 5^N) % 1<<64 == 1.
var assert [1]struct{}
_ = assert[(div1e8m*5*5*5*5*5*5*5*5)%(1<<64)-1]
_ = assert[(div1e4m*5*5*5*5)%(1<<64)-1]
_ = assert[(div1e2m*5*5)%(1<<64)-1]
_ = assert[(div1e1m*5)%(1<<64)-1]
// Cut 8 zeros, then 4, then 2, then 1.
p := 0
for d := bits.RotateLeft64(x*div1e8m, -8); d <= div1e8le; d = bits.RotateLeft64(x*div1e8m, -8) {
x = d
p += 8
}
if d := bits.RotateLeft64(x*div1e4m, -4); d <= div1e4le {
x = d
p += 4
}
if d := bits.RotateLeft64(x*div1e2m, -2); d <= div1e2le {
x = d
p += 2
}
if d := bits.RotateLeft64(x*div1e1m, -1); d <= div1e1le {
x = d
p += 1
}
return x, p
}
|