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  const 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.
    14  func 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.
    25  func 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).
    34  func 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.
    40  func 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.
    50  func 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.
    59  func 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  
    66  const nSmalls = 100
    67  
    68  const smallsString = "00010203040506070809" +
    69  	"10111213141516171819" +
    70  	"20212223242526272829" +
    71  	"30313233343536373839" +
    72  	"40414243444546474849" +
    73  	"50515253545556575859" +
    74  	"60616263646566676869" +
    75  	"70717273747576777879" +
    76  	"80818283848586878889" +
    77  	"90919293949596979899"
    78  
    79  const host32bit = ^uint(0)>>32 == 0
    80  
    81  const 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.
    88  func 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  
   203  func isPowerOfTwo(x int) bool {
   204  	return x&(x-1) == 0
   205  }
   206
View as plain text