1// Copyright 2009 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package strconv
6
7import "math/bits"
8
9const fastSmalls = true // enable fast path for small integers
10
11// FormatUint returns the string representation of i in the given base,
12// for 2 <= base <= 36. The result uses the lower-case letters 'a' to 'z'
13// for digit values >= 10.
14func FormatUint(i uint64, base int) string {
15	if fastSmalls && i < nSmalls && base == 10 {
16		return small(int(i))
17	}
18	_, s := formatBits(nil, i, base, false, false)
19	return s
20}
21
22// FormatInt returns the string representation of i in the given base,
23// for 2 <= base <= 36. The result uses the lower-case letters 'a' to 'z'
24// for digit values >= 10.
25func FormatInt(i int64, base int) string {
26	if fastSmalls && 0 <= i && i < nSmalls && base == 10 {
27		return small(int(i))
28	}
29	_, s := formatBits(nil, uint64(i), base, i < 0, false)
30	return s
31}
32
33// Itoa is equivalent to [FormatInt](int64(i), 10).
34func Itoa(i int) string {
35	return FormatInt(int64(i), 10)
36}
37
38// AppendInt appends the string form of the integer i,
39// as generated by [FormatInt], to dst and returns the extended buffer.
40func AppendInt(dst []byte, i int64, base int) []byte {
41	if fastSmalls && 0 <= i && i < nSmalls && base == 10 {
42		return append(dst, small(int(i))...)
43	}
44	dst, _ = formatBits(dst, uint64(i), base, i < 0, true)
45	return dst
46}
47
48// AppendUint appends the string form of the unsigned integer i,
49// as generated by [FormatUint], to dst and returns the extended buffer.
50func AppendUint(dst []byte, i uint64, base int) []byte {
51	if fastSmalls && i < nSmalls && base == 10 {
52		return append(dst, small(int(i))...)
53	}
54	dst, _ = formatBits(dst, i, base, false, true)
55	return dst
56}
57
58// small returns the string for an i with 0 <= i < nSmalls.
59func small(i int) string {
60	if i < 10 {
61		return digits[i : i+1]
62	}
63	return smallsString[i*2 : i*2+2]
64}
65
66const nSmalls = 100
67
68const smallsString = "00010203040506070809" +
69	"10111213141516171819" +
70	"20212223242526272829" +
71	"30313233343536373839" +
72	"40414243444546474849" +
73	"50515253545556575859" +
74	"60616263646566676869" +
75	"70717273747576777879" +
76	"80818283848586878889" +
77	"90919293949596979899"
78
79const host32bit = ^uint(0)>>32 == 0
80
81const digits = "0123456789abcdefghijklmnopqrstuvwxyz"
82
83// formatBits computes the string representation of u in the given base.
84// If neg is set, u is treated as negative int64 value. If append_ is
85// set, the string is appended to dst and the resulting byte slice is
86// returned as the first result value; otherwise the string is returned
87// as the second result value.
88func formatBits(dst []byte, u uint64, base int, neg, append_ bool) (d []byte, s string) {
89	if base < 2 || base > len(digits) {
90		panic("strconv: illegal AppendInt/FormatInt base")
91	}
92	// 2 <= base && base <= len(digits)
93
94	var a [64 + 1]byte // +1 for sign of 64bit value in base 2
95	i := len(a)
96
97	if neg {
98		u = -u
99	}
100
101	// convert bits
102	// We use uint values where we can because those will
103	// fit into a single register even on a 32bit machine.
104	if base == 10 {
105		// common case: use constants for / because
106		// the compiler can optimize it into a multiply+shift
107
108		if host32bit {
109			// convert the lower digits using 32bit operations
110			for u >= 1e9 {
111				// Avoid using r = a%b in addition to q = a/b
112				// since 64bit division and modulo operations
113				// are calculated by runtime functions on 32bit machines.
114				q := u / 1e9
115				us := uint(u - q*1e9) // u % 1e9 fits into a uint
116				for j := 4; j > 0; j-- {
117					is := us % 100 * 2
118					us /= 100
119					i -= 2
120					a[i+1] = smallsString[is+1]
121					a[i+0] = smallsString[is+0]
122				}
123
124				// us < 10, since it contains the last digit
125				// from the initial 9-digit us.
126				i--
127				a[i] = smallsString[us*2+1]
128
129				u = q
130			}
131			// u < 1e9
132		}
133
134		// u guaranteed to fit into a uint
135		us := uint(u)
136		for us >= 100 {
137			is := us % 100 * 2
138			us /= 100
139			i -= 2
140			a[i+1] = smallsString[is+1]
141			a[i+0] = smallsString[is+0]
142		}
143
144		// us < 100
145		is := us * 2
146		i--
147		a[i] = smallsString[is+1]
148		if us >= 10 {
149			i--
150			a[i] = smallsString[is]
151		}
152
153	} else if isPowerOfTwo(base) {
154		// Use shifts and masks instead of / and %.
155		// Base is a power of 2 and 2 <= base <= len(digits) where len(digits) is 36.
156		// The largest power of 2 below or equal to 36 is 32, which is 1 << 5;
157		// i.e., the largest possible shift count is 5. By &-ind that value with
158		// the constant 7 we tell the compiler that the shift count is always
159		// less than 8 which is smaller than any register width. This allows
160		// the compiler to generate better code for the shift operation.
161		shift := uint(bits.TrailingZeros(uint(base))) & 7
162		b := uint64(base)
163		m := uint(base) - 1 // == 1<<shift - 1
164		for u >= b {
165			i--
166			a[i] = digits[uint(u)&m]
167			u >>= shift
168		}
169		// u < base
170		i--
171		a[i] = digits[uint(u)]
172	} else {
173		// general case
174		b := uint64(base)
175		for u >= b {
176			i--
177			// Avoid using r = a%b in addition to q = a/b
178			// since 64bit division and modulo operations
179			// are calculated by runtime functions on 32bit machines.
180			q := u / b
181			a[i] = digits[uint(u-q*b)]
182			u = q
183		}
184		// u < base
185		i--
186		a[i] = digits[uint(u)]
187	}
188
189	// add sign, if any
190	if neg {
191		i--
192		a[i] = '-'
193	}
194
195	if append_ {
196		d = append(dst, a[i:]...)
197		return
198	}
199	s = string(a[i:])
200	return
201}
202
203func isPowerOfTwo(x int) bool {
204	return x&(x-1) == 0
205}
206