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  		nd := numDigits(i)
    19  		formatBase10(a[:nd], i)
    20  		return string(a[:nd])
    21  	}
    22  	_, s := formatBits(nil, i, base, false, false)
    23  	return s
    24  }
    25  
    26  // FormatInt returns the string representation of i in the given base,
    27  // for 2 <= base <= 36. The result uses the lower-case letters 'a' to 'z'
    28  // for digit values >= 10.
    29  func FormatInt(i int64, base int) string {
    30  	if base == 10 {
    31  		if 0 <= i && i < nSmalls {
    32  			return small(int(i))
    33  		}
    34  		var a [24]byte
    35  		u := uint64(i)
    36  		if i < 0 {
    37  			u = -u
    38  		}
    39  		nd := numDigits(u)
    40  		formatBase10(a[1:1+nd], u)
    41  		if i < 0 {
    42  			a[0] = '-'
    43  			return string(a[:1+nd])
    44  		}
    45  		return string(a[1 : 1+nd])
    46  	}
    47  	_, s := formatBits(nil, uint64(i), base, i < 0, false)
    48  	return s
    49  }
    50  
    51  // Itoa is equivalent to [FormatInt](int64(i), 10).
    52  func Itoa(i int) string {
    53  	return FormatInt(int64(i), 10)
    54  }
    55  
    56  // AppendInt appends the string form of the integer i,
    57  // as generated by [FormatInt], to dst and returns the extended buffer.
    58  func AppendInt(dst []byte, i int64, base int) []byte {
    59  	u := uint64(i)
    60  	if i < 0 {
    61  		dst = append(dst, '-')
    62  		u = -u
    63  	}
    64  	return AppendUint(dst, u, base)
    65  }
    66  
    67  // AppendUint appends the string form of the unsigned integer i,
    68  // as generated by [FormatUint], to dst and returns the extended buffer.
    69  func AppendUint(dst []byte, i uint64, base int) []byte {
    70  	if base == 10 {
    71  		if i < nSmalls {
    72  			return append(dst, small(int(i))...)
    73  		}
    74  		var a [24]byte
    75  		nd := numDigits(i)
    76  		formatBase10(a[:nd], i)
    77  		return append(dst, a[:nd]...)
    78  	}
    79  	dst, _ = formatBits(dst, i, base, false, true)
    80  	return dst
    81  }
    82  
    83  const digits = "0123456789abcdefghijklmnopqrstuvwxyz"
    84  
    85  // formatBits computes the string representation of u in the given base.
    86  // If neg is set, u is treated as negative int64 value. If append_ is
    87  // set, the string is appended to dst and the resulting byte slice is
    88  // returned as the first result value; otherwise the string is returned
    89  // as the second result value.
    90  // The caller is expected to have handled base 10 separately for speed.
    91  func formatBits(dst []byte, u uint64, base int, neg, append_ bool) (d []byte, s string) {
    92  	if base < 2 || base == 10 || base > len(digits) {
    93  		panic("strconv: illegal AppendInt/FormatInt base")
    94  	}
    95  	// 2 <= base && base <= len(digits)
    96  
    97  	var a [64 + 1]byte // +1 for sign of 64bit value in base 2
    98  	i := len(a)
    99  	if neg {
   100  		u = -u
   101  	}
   102  
   103  	// convert bits
   104  	// We use uint values where we can because those will
   105  	// fit into a single register even on a 32bit machine.
   106  	if isPowerOfTwo(base) {
   107  		// Use shifts and masks instead of / and %.
   108  		shift := uint(bits.TrailingZeros(uint(base)))
   109  		b := uint64(base)
   110  		m := uint(base) - 1 // == 1<<shift - 1
   111  		for u >= b {
   112  			i--
   113  			a[i] = digits[uint(u)&m]
   114  			u >>= shift
   115  		}
   116  		// u < base
   117  		i--
   118  		a[i] = digits[uint(u)]
   119  	} else {
   120  		// general case
   121  		b := uint64(base)
   122  		for u >= b {
   123  			i--
   124  			// Avoid using r = a%b in addition to q = a/b
   125  			// since 64bit division and modulo operations
   126  			// are calculated by runtime functions on 32bit machines.
   127  			q := u / b
   128  			a[i] = digits[uint(u-q*b)]
   129  			u = q
   130  		}
   131  		// u < base
   132  		i--
   133  		a[i] = digits[uint(u)]
   134  	}
   135  
   136  	// add sign, if any
   137  	if neg {
   138  		i--
   139  		a[i] = '-'
   140  	}
   141  
   142  	if append_ {
   143  		d = append(dst, a[i:]...)
   144  		return
   145  	}
   146  	s = string(a[i:])
   147  	return
   148  }
   149  
   150  func isPowerOfTwo(x int) bool {
   151  	return x&(x-1) == 0
   152  }
   153  
   154  const nSmalls = 100
   155  
   156  // smalls is the formatting of 00..99 concatenated.
   157  // It is then padded out with 56 x's to 256 bytes,
   158  // so that smalls[x&0xFF] has no bounds check.
   159  const smalls = "00010203040506070809" +
   160  	"10111213141516171819" +
   161  	"20212223242526272829" +
   162  	"30313233343536373839" +
   163  	"40414243444546474849" +
   164  	"50515253545556575859" +
   165  	"60616263646566676869" +
   166  	"70717273747576777879" +
   167  	"80818283848586878889" +
   168  	"90919293949596979899"
   169  
   170  // small returns the string for an i with 0 <= i < nSmalls.
   171  func small(i int) string {
   172  	if i < 10 {
   173  		return digits[i : i+1]
   174  	}
   175  	return smalls[i*2 : i*2+2]
   176  }
   177  
   178  // RuntimeFormatBase10 formats u into the tail of a
   179  // and returns the offset to the first byte written to a.
   180  // It is only for use by package runtime.
   181  // Other packages should use AppendUint.
   182  func RuntimeFormatBase10(a []byte, u uint64) int {
   183  	// Note: numDigits requires an argument ≥ 1.
   184  	// The |1 changes 0 to 1 without adding an extra digit
   185  	// to any other value.
   186  	i := len(a) - numDigits(u|1)
   187  	formatBase10(a[i:], u)
   188  	return i
   189  }
   190  
   191  // formatBase10 formats the decimal representation of u into a.
   192  // The caller is responsible for ensuring that a is big enough to hold u.
   193  // If a is too big, leading zeros will be filled in as needed.
   194  func formatBase10(a []byte, u uint64) {
   195  	nd := len(a)
   196  	for nd >= 8 {
   197  		// Format last 8 digits (4 pairs).
   198  		x3210 := uint32(u % 1e8)
   199  		u /= 1e8
   200  		x32, x10 := x3210/1e4, x3210%1e4
   201  		x1, x0 := (x10/100)*2, (x10%100)*2
   202  		x3, x2 := (x32/100)*2, (x32%100)*2
   203  		a[nd-1], a[nd-2] = smalls[x0+1], smalls[x0]
   204  		a[nd-3], a[nd-4] = smalls[x1+1], smalls[x1]
   205  		a[nd-5], a[nd-6] = smalls[x2+1], smalls[x2]
   206  		a[nd-7], a[nd-8] = smalls[x3+1], smalls[x3]
   207  		nd -= 8
   208  	}
   209  
   210  	x := uint32(u)
   211  	if nd >= 4 {
   212  		// Format last 4 digits (2 pairs).
   213  		x10 := x % 1e4
   214  		x /= 1e4
   215  		x1, x0 := (x10/100)*2, (x10%100)*2
   216  		a[nd-1], a[nd-2] = smalls[x0+1], smalls[x0]
   217  		a[nd-3], a[nd-4] = smalls[x1+1], smalls[x1]
   218  		nd -= 4
   219  	}
   220  	if nd >= 2 {
   221  		// Format last 2 digits.
   222  		x0 := (x % 1e2) * 2
   223  		x /= 1e2
   224  		a[nd-1], a[nd-2] = smalls[x0+1], smalls[x0]
   225  		nd -= 2
   226  	}
   227  	if nd > 0 {
   228  		// Format final digit.
   229  		a[0] = byte('0' + x)
   230  	}
   231  }
   232
View as plain text