itoa.go

     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  
     5  package strconv
     6  
     7  import "math/bits"
     8  
     9  // FormatUint returns the string representation of i in the given base,
    10  // for 2 <= base <= 36. The result uses the lower-case letters 'a' to 'z'
    11  // for digit values >= 10.
    12  func FormatUint(i uint64, base int) string {
    13  	if base == 10 {
    14  		if i < nSmalls {
    15  			return small(int(i))
    16  		}
    17  		var a [24]byte
    18  		j := formatBase10(a[:], i)
    19  		return string(a[j:])
    20  	}
    21  	_, s := formatBits(nil, i, base, false, false)
    22  	return s
    23  }
    24  
    25  // FormatInt returns the string representation of i in the given base,
    26  // for 2 <= base <= 36. The result uses the lower-case letters 'a' to 'z'
    27  // for digit values >= 10.
    28  func FormatInt(i int64, base int) string {
    29  	if base == 10 {
    30  		if 0 <= i && i < nSmalls {
    31  			return small(int(i))
    32  		}
    33  		var a [24]byte
    34  		u := uint64(i)
    35  		if i < 0 {
    36  			u = -u
    37  		}
    38  		j := formatBase10(a[:], u)
    39  		if i < 0 {
    40  			j--
    41  			a[j] = '-'
    42  		}
    43  		return string(a[j:])
    44  	}
    45  	_, s := formatBits(nil, uint64(i), base, i < 0, false)
    46  	return s
    47  }
    48  
    49  // Itoa is equivalent to [FormatInt](int64(i), 10).
    50  func Itoa(i int) string {
    51  	return FormatInt(int64(i), 10)
    52  }
    53  
    54  // AppendInt appends the string form of the integer i,
    55  // as generated by [FormatInt], to dst and returns the extended buffer.
    56  func AppendInt(dst []byte, i int64, base int) []byte {
    57  	u := uint64(i)
    58  	if i < 0 {
    59  		dst = append(dst, '-')
    60  		u = -u
    61  	}
    62  	return AppendUint(dst, u, base)
    63  }
    64  
    65  // AppendUint appends the string form of the unsigned integer i,
    66  // as generated by [FormatUint], to dst and returns the extended buffer.
    67  func AppendUint(dst []byte, i uint64, base int) []byte {
    68  	if base == 10 {
    69  		if i < nSmalls {
    70  			return append(dst, small(int(i))...)
    71  		}
    72  		var a [24]byte
    73  		j := formatBase10(a[:], i)
    74  		return append(dst, a[j:]...)
    75  	}
    76  	dst, _ = formatBits(dst, i, base, false, true)
    77  	return dst
    78  }
    79  
    80  const digits = "0123456789abcdefghijklmnopqrstuvwxyz"
    81  
    82  // formatBits computes the string representation of u in the given base.
    83  // If neg is set, u is treated as negative int64 value. If append_ is
    84  // set, the string is appended to dst and the resulting byte slice is
    85  // returned as the first result value; otherwise the string is returned
    86  // as the second result value.
    87  // The caller is expected to have handled base 10 separately for speed.
    88  func formatBits(dst []byte, u uint64, base int, neg, append_ bool) (d []byte, s string) {
    89  	if base < 2 || base == 10 || 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  	if neg {
    97  		u = -u
    98  	}
    99  
   100  	// convert bits
   101  	// We use uint values where we can because those will
   102  	// fit into a single register even on a 32bit machine.
   103  	if isPowerOfTwo(base) {
   104  		// Use shifts and masks instead of / and %.
   105  		shift := uint(bits.TrailingZeros(uint(base)))
   106  		b := uint64(base)
   107  		m := uint(base) - 1 // == 1<<shift - 1
   108  		for u >= b {
   109  			i--
   110  			a[i] = digits[uint(u)&m]
   111  			u >>= shift
   112  		}
   113  		// u < base
   114  		i--
   115  		a[i] = digits[uint(u)]
   116  	} else {
   117  		// general case
   118  		b := uint64(base)
   119  		for u >= b {
   120  			i--
   121  			// Avoid using r = a%b in addition to q = a/b
   122  			// since 64bit division and modulo operations
   123  			// are calculated by runtime functions on 32bit machines.
   124  			q := u / b
   125  			a[i] = digits[uint(u-q*b)]
   126  			u = q
   127  		}
   128  		// u < base
   129  		i--
   130  		a[i] = digits[uint(u)]
   131  	}
   132  
   133  	// add sign, if any
   134  	if neg {
   135  		i--
   136  		a[i] = '-'
   137  	}
   138  
   139  	if append_ {
   140  		d = append(dst, a[i:]...)
   141  		return
   142  	}
   143  	s = string(a[i:])
   144  	return
   145  }
   146  
   147  func isPowerOfTwo(x int) bool {
   148  	return x&(x-1) == 0
   149  }
   150  
   151  const nSmalls = 100
   152  
   153  // smalls is the formatting of 00..99 concatenated.
   154  // It is then padded out with 56 x's to 256 bytes,
   155  // so that smalls[x&0xFF] has no bounds check.
   156  const smalls = "00010203040506070809" +
   157  	"10111213141516171819" +
   158  	"20212223242526272829" +
   159  	"30313233343536373839" +
   160  	"40414243444546474849" +
   161  	"50515253545556575859" +
   162  	"60616263646566676869" +
   163  	"70717273747576777879" +
   164  	"80818283848586878889" +
   165  	"90919293949596979899"
   166  
   167  const host64bit = ^uint(0)>>32 != 0
   168  
   169  // small returns the string for an i with 0 <= i < nSmalls.
   170  func small(i int) string {
   171  	if i < 10 {
   172  		return digits[i : i+1]
   173  	}
   174  	return smalls[i*2 : i*2+2]
   175  }
   176  
   177  // RuntimeFormatBase10 formats u into the tail of a
   178  // and returns the offset to the first byte written to a.
   179  // It is only for use by package runtime.
   180  // Other packages should use AppendUint.
   181  func RuntimeFormatBase10(a []byte, u uint64) int {
   182  	return formatBase10(a, u)
   183  }
   184  
   185  // formatBase10 formats the decimal representation of u into the tail of a
   186  // and returns the offset of the first byte written to a. That is, after
   187  //
   188  //	i := formatBase10(a, u)
   189  //
   190  // the decimal representation is in a[i:].
   191  func formatBase10(a []byte, u uint64) int {
   192  	// Split into 9-digit chunks that fit in uint32s
   193  	// and convert each chunk using uint32 math instead of uint64 math.
   194  	// The obvious way to write the outer loop is "for u >= 1e9", but most numbers are small,
   195  	// so the setup for the comparison u >= 1e9 is usually pure overhead.
   196  	// Instead, we approximate it by u>>29 != 0, which is usually faster and good enough.
   197  	i := len(a)
   198  	for (host64bit && u>>29 != 0) || (!host64bit && uint32(u)>>29|uint32(u>>32) != 0) {
   199  		var lo uint32
   200  		u, lo = u/1e9, uint32(u%1e9)
   201  
   202  		// Convert 9 digits.
   203  		for range 4 {
   204  			var dd uint32
   205  			lo, dd = lo/100, (lo%100)*2
   206  			i -= 2
   207  			a[i+0], a[i+1] = smalls[dd+0], smalls[dd+1]
   208  		}
   209  		i--
   210  		a[i] = smalls[lo*2+1]
   211  
   212  		// If we'd been using u >= 1e9 then we would be guaranteed that u/1e9 > 0,
   213  		// but since we used u>>29 != 0, u/1e9 might be 0, so we might be done.
   214  		// (If u is now 0, then at the start we had 2²⁹ ≤ u < 10⁹, so it was still correct
   215  		// to write 9 digits; we have not accidentally written any leading zeros.)
   216  		if u == 0 {
   217  			return i
   218  		}
   219  	}
   220  
   221  	// Convert final chunk, at most 8 digits.
   222  	lo := uint32(u)
   223  	for lo >= 100 {
   224  		var dd uint32
   225  		lo, dd = lo/100, (lo%100)*2
   226  		i -= 2
   227  		a[i+0], a[i+1] = smalls[dd+0], smalls[dd+1]
   228  	}
   229  	i--
   230  	dd := lo * 2
   231  	a[i] = smalls[dd+1]
   232  	if lo >= 10 {
   233  		i--
   234  		a[i] = smalls[dd+0]
   235  	}
   236  	return i
   237  }
   238
View as plain text