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
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
|
// 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 "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.
func FormatUint(i uint64, base int) string {
if base == 10 {
if i < nSmalls {
return small(int(i))
}
var a [24]byte
j := formatBase10(a[:], i)
return string(a[j:])
}
_, s := formatBits(nil, i, base, false, false)
return s
}
// 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.
func FormatInt(i int64, base int) string {
if base == 10 {
if 0 <= i && i < nSmalls {
return small(int(i))
}
var a [24]byte
u := uint64(i)
if i < 0 {
u = -u
}
j := formatBase10(a[:], u)
if i < 0 {
j--
a[j] = '-'
}
return string(a[j:])
}
_, s := formatBits(nil, uint64(i), base, i < 0, false)
return s
}
// Itoa is equivalent to [FormatInt](int64(i), 10).
func Itoa(i int) string {
return FormatInt(int64(i), 10)
}
// AppendInt appends the string form of the integer i,
// as generated by [FormatInt], to dst and returns the extended buffer.
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.
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, true)
return dst
}
const digits = "0123456789abcdefghijklmnopqrstuvwxyz"
// formatBits computes the string representation of u in the given base.
// If neg is set, u is treated as negative int64 value. If append_ is
// set, the string is appended to dst and the resulting byte slice is
// returned as the first result value; otherwise the string is returned
// as the second result value.
// The caller is expected to have handled base 10 separately for speed.
func formatBits(dst []byte, u uint64, base int, neg, append_ bool) (d []byte, s string) {
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] = '-'
}
if append_ {
d = append(dst, a[i:]...)
return
}
s = string(a[i:])
return
}
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]
}
// RuntimeFormatBase10 formats u into the tail of a
// and returns the offset to the first byte written to a.
// It is only for use by package runtime.
// Other packages should use AppendUint.
func RuntimeFormatBase10(a []byte, u uint64) int {
return formatBase10(a, u)
}
// 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 >= 1e9", but most numbers are small,
// so the setup for the comparison u >= 1e9 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) {
var lo uint32
u, lo = u/1e9, uint32(u%1e9)
// Convert 9 digits.
for range 4 {
var dd uint32
lo, dd = lo/100, (lo%100)*2
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 >= 1e9 then we would be guaranteed that u/1e9 > 0,
// but since we used u>>29 != 0, u/1e9 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 {
var dd uint32
lo, dd = lo/100, (lo%100)*2
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
}
|
