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
7// FormatUint returns the string representation of i in the given base,
8// for 2 <= base <= 36. The result uses the lower-case letters 'a' to 'z'
9// for digit values >= 10.
10func FormatUint(i uint64, base int) string {
11	_, s := formatBits(nil, i, base, false, false)
12	return s
13}
14
15// FormatInt returns the string representation of i in the given base,
16// for 2 <= base <= 36. The result uses the lower-case letters 'a' to 'z'
17// for digit values >= 10.
18func FormatInt(i int64, base int) string {
19	_, s := formatBits(nil, uint64(i), base, i < 0, false)
20	return s
21}
22
23// Itoa is shorthand for FormatInt(int64(i), 10).
24func Itoa(i int) string {
25	return FormatInt(int64(i), 10)
26}
27
28// AppendInt appends the string form of the integer i,
29// as generated by FormatInt, to dst and returns the extended buffer.
30func AppendInt(dst []byte, i int64, base int) []byte {
31	dst, _ = formatBits(dst, uint64(i), base, i < 0, true)
32	return dst
33}
34
35// AppendUint appends the string form of the unsigned integer i,
36// as generated by FormatUint, to dst and returns the extended buffer.
37func AppendUint(dst []byte, i uint64, base int) []byte {
38	dst, _ = formatBits(dst, i, base, false, true)
39	return dst
40}
41
42const (
43	digits = "0123456789abcdefghijklmnopqrstuvwxyz"
44)
45
46var shifts = [len(digits) + 1]uint{
47	1 << 1: 1,
48	1 << 2: 2,
49	1 << 3: 3,
50	1 << 4: 4,
51	1 << 5: 5,
52}
53
54// formatBits computes the string representation of u in the given base.
55// If neg is set, u is treated as negative int64 value. If append_ is
56// set, the string is appended to dst and the resulting byte slice is
57// returned as the first result value; otherwise the string is returned
58// as the second result value.
59//
60func formatBits(dst []byte, u uint64, base int, neg, append_ bool) (d []byte, s string) {
61	if base < 2 || base > len(digits) {
62		panic("strconv: illegal AppendInt/FormatInt base")
63	}
64	// 2 <= base && base <= len(digits)
65
66	var a [64 + 1]byte // +1 for sign of 64bit value in base 2
67	i := len(a)
68
69	if neg {
70		u = -u
71	}
72
73	// convert bits
74	if base == 10 {
75		// common case: use constants for / because
76		// the compiler can optimize it into a multiply+shift
77
78		if ^uintptr(0)>>32 == 0 {
79			for u > uint64(^uintptr(0)) {
80				q := u / 1e9
81				us := uintptr(u - q*1e9) // us % 1e9 fits into a uintptr
82				for j := 9; j > 0; j-- {
83					i--
84					qs := us / 10
85					a[i] = byte(us - qs*10 + '0')
86					us = qs
87				}
88				u = q
89			}
90		}
91
92		// u guaranteed to fit into a uintptr
93		us := uintptr(u)
94		for us >= 10 {
95			i--
96			q := us / 10
97			a[i] = byte(us - q*10 + '0')
98			us = q
99		}
100		// u < 10
101		i--
102		a[i] = byte(us + '0')
103
104	} else if s := shifts[base]; s > 0 {
105		// base is power of 2: use shifts and masks instead of / and %
106		b := uint64(base)
107		m := uintptr(b) - 1 // == 1<<s - 1
108		for u >= b {
109			i--
110			a[i] = digits[uintptr(u)&m]
111			u >>= s
112		}
113		// u < base
114		i--
115		a[i] = digits[uintptr(u)]
116
117	} else {
118		// general case
119		b := uint64(base)
120		for u >= b {
121			i--
122			q := u / b
123			a[i] = digits[uintptr(u-q*b)]
124			u = q
125		}
126		// u < base
127		i--
128		a[i] = digits[uintptr(u)]
129	}
130
131	// add sign, if any
132	if neg {
133		i--
134		a[i] = '-'
135	}
136
137	if append_ {
138		d = append(dst, a[i:]...)
139		return
140	}
141	s = string(a[i:])
142	return
143}
144