// 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 "solod.dev/so/math/bits"

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

// dst must have enough length to hold the result.

func FormatUint(dst []byte, i uint64, base int) string {

buf := dst[:0]

if base == 10 {

if i < nSmalls {

s := small(int(i))

buf = append(buf, s...)

return string(buf)

}

var a [24]byte

j := formatBase10(a[:], i)

buf = append(buf, a[j:]...)

return string(buf)

}

buf = formatBits(buf, i, base, false)

return string(buf)

}

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

// dst must have enough length to hold the result.

func FormatInt(dst []byte, i int64, base int) string {

buf := dst[:0]

if base == 10 {

if 0 <= i && i < nSmalls {

s := small(int(i))

buf = append(buf, s...)

return string(buf)

}

var a [24]byte

u := uint64(i)

if i < 0 {

u = -u

}

j := formatBase10(a[:], u)

if i < 0 {

j--

a[j] = '-'

}

buf = append(buf, a[j:]...)

return string(buf)

}

buf = formatBits(buf, uint64(i), base, i < 0)

return string(buf)

}

// Itoa is equivalent to [FormatInt](int64(i), 10).

func Itoa(dst []byte, i int) string {

return FormatInt(dst, int64(i), 10)

}

// AppendInt appends the string form of the integer i,

// as generated by [FormatInt], to dst and returns the extended buffer.

// dst must have enough capacity to hold the result.

func AppendInt(dst []byte, i int64, base int) []byte {

u := uint64(i)

if i < 0 {

dst = append(dst, '-')

u = -u

}

return AppendUint(dst, u, base)

}

// AppendUint appends the string form of the unsigned integer i,

// as generated by [FormatUint], to dst and returns the extended buffer.

// dst must have enough capacity to hold the result.

func AppendUint(dst []byte, i uint64, base int) []byte {

if base == 10 {

if i < nSmalls {

return append(dst, small(int(i))...)

}

var a [24]byte

j := formatBase10(a[:], i)

return append(dst, a[j:]...)

}

dst = formatBits(dst, i, base, false)

return dst

}

const digits = "0123456789abcdefghijklmnopqrstuvwxyz"

// formatBits computes the string representation of u in the given base.

// Appends the string to dst and returns the resulting byte slice.

// dst must have enough capacity to hold the result.

// If neg is set, u is treated as negative int64 value.

// The caller is expected to have handled base 10 separately for speed.

func formatBits(dst []byte, u uint64, base int, neg bool) []byte {

if base < 2 || base == 10 || 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

// We use uint values where we can because those will

// fit into a single register even on a 32bit machine.

if isPowerOfTwo(base) {

// Use shifts and masks instead of / and %.

shift := uint(bits.TrailingZeros(uint(base)))

b := uint64(base)

m := uint(base) - 1 // == 1<<shift - 1

for u >= b {

i--

a[i] = digits[uint(u)&m]

u >>= shift

}

// u < base

i--

a[i] = digits[uint(u)]

} else {

// general case

b := uint64(base)

for u >= b {

i--

// Avoid using r = a%b in addition to q = a/b

// since 64bit division and modulo operations

// are calculated by runtime functions on 32bit machines.

q := u / b

a[i] = digits[uint(u-q*b)]

u = q

}

// u < base

i--

a[i] = digits[uint(u)]

}

// add sign, if any

if neg {

i--

a[i] = '-'

}

d := append(dst, a[i:]...)

return d

}

func isPowerOfTwo(x int) bool {

return x&(x-1) == 0

}

const nSmalls = 100

// smalls is the formatting of 00..99 concatenated.

// It is then padded out with 56 x's to 256 bytes,

// so that smalls[x&0xFF] has no bounds check.

const smalls = "00010203040506070809" +

"10111213141516171819" +

"20212223242526272829" +

"30313233343536373839" +

"40414243444546474849" +

"50515253545556575859" +

"60616263646566676869" +

"70717273747576777879" +

"80818283848586878889" +

"90919293949596979899"

const host64bit = ^uint(0)>>32 != 0

// small returns the string for an i with 0 <= i < nSmalls.

func small(i int) string {

if i < 10 {

return digits[i : i+1]

}

return smalls[i*2 : i*2+2]

}

// formatBase10 formats the decimal representation of u into the tail of a

// and returns the offset of the first byte written to a. That is, after

//

// i := formatBase10(a, u)

//

// the decimal representation is in a[i:].

func formatBase10(a []byte, u uint64) int {

// Split into 9-digit chunks that fit in uint32s

// and convert each chunk using uint32 math instead of uint64 math.

// The obvious way to write the outer loop is "for u >= 1000000000", but most numbers are small,

// so the setup for the comparison u >= 1000000000 is usually pure overhead.

// Instead, we approximate it by u>>29 != 0, which is usually faster and good enough.

i := len(a)

for (host64bit && u>>29 != 0) || (!host64bit && uint32(u)>>29|uint32(u>>32) != 0) {

lo := uint32(u % 1000000000)

u = u / 1000000000

// Convert 9 digits.

for range 4 {

dd := (lo % 100) * 2

lo = lo / 100

i -= 2

a[i+0], a[i+1] = smalls[dd+0], smalls[dd+1]

}

i--

a[i] = smalls[lo*2+1]

// If we'd been using u >= 1000000000 then we would be guaranteed that u/1000000000 > 0,

// but since we used u>>29 != 0, u/1000000000 might be 0, so we might be done.

// (If u is now 0, then at the start we had 2²⁹ ≤ u < 10⁹, so it was still correct

// to write 9 digits; we have not accidentally written any leading zeros.)

if u == 0 {

return i

}

}

// Convert final chunk, at most 8 digits.

lo := uint32(u)

for lo >= 100 {

dd := (lo % 100) * 2

lo = lo / 100

i -= 2

a[i+0], a[i+1] = smalls[dd+0], smalls[dd+1]

}

i--

dd := lo * 2

a[i] = smalls[dd+1]

if lo >= 10 {

i--

a[i] = smalls[dd+0]

}

return i

}