src/internal/strconv/math.go

// 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
}