Source file src/strconv/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	//
    89	func formatBits(dst []byte, u uint64, base int, neg, append_ bool) (d []byte, s string) {
    90		if base < 2 || base > len(digits) {
    91			panic("strconv: illegal AppendInt/FormatInt base")
    92		}
    93		// 2 <= base && base <= len(digits)
    94	
    95		var a [64 + 1]byte // +1 for sign of 64bit value in base 2
    96		i := len(a)
    97	
    98		if neg {
    99			u = -u
   100		}
   101	
   102		// convert bits
   103		// We use uint values where we can because those will
   104		// fit into a single register even on a 32bit machine.
   105		if base == 10 {
   106			// common case: use constants for / because
   107			// the compiler can optimize it into a multiply+shift
   108	
   109			if host32bit {
   110				// convert the lower digits using 32bit operations
   111				for u >= 1e9 {
   112					// Avoid using r = a%b in addition to q = a/b
   113					// since 64bit division and modulo operations
   114					// are calculated by runtime functions on 32bit machines.
   115					q := u / 1e9
   116					us := uint(u - q*1e9) // u % 1e9 fits into a uint
   117					for j := 4; j > 0; j-- {
   118						is := us % 100 * 2
   119						us /= 100
   120						i -= 2
   121						a[i+1] = smallsString[is+1]
   122						a[i+0] = smallsString[is+0]
   123					}
   124	
   125					// us < 10, since it contains the last digit
   126					// from the initial 9-digit us.
   127					i--
   128					a[i] = smallsString[us*2+1]
   129	
   130					u = q
   131				}
   132				// u < 1e9
   133			}
   134	
   135			// u guaranteed to fit into a uint
   136			us := uint(u)
   137			for us >= 100 {
   138				is := us % 100 * 2
   139				us /= 100
   140				i -= 2
   141				a[i+1] = smallsString[is+1]
   142				a[i+0] = smallsString[is+0]
   143			}
   144	
   145			// us < 100
   146			is := us * 2
   147			i--
   148			a[i] = smallsString[is+1]
   149			if us >= 10 {
   150				i--
   151				a[i] = smallsString[is]
   152			}
   153	
   154		} else if isPowerOfTwo(base) {
   155			// Use shifts and masks instead of / and %.
   156			// Base is a power of 2 and 2 <= base <= len(digits) where len(digits) is 36.
   157			// The largest power of 2 below or equal to 36 is 32, which is 1 << 5;
   158			// i.e., the largest possible shift count is 5. By &-ind that value with
   159			// the constant 7 we tell the compiler that the shift count is always
   160			// less than 8 which is smaller than any register width. This allows
   161			// the compiler to generate better code for the shift operation.
   162			shift := uint(bits.TrailingZeros(uint(base))) & 7
   163			b := uint64(base)
   164			m := uint(base) - 1 // == 1<<shift - 1
   165			for u >= b {
   166				i--
   167				a[i] = digits[uint(u)&m]
   168				u >>= shift
   169			}
   170			// u < base
   171			i--
   172			a[i] = digits[uint(u)]
   173		} else {
   174			// general case
   175			b := uint64(base)
   176			for u >= b {
   177				i--
   178				// Avoid using r = a%b in addition to q = a/b
   179				// since 64bit division and modulo operations
   180				// are calculated by runtime functions on 32bit machines.
   181				q := u / b
   182				a[i] = digits[uint(u-q*b)]
   183				u = q
   184			}
   185			// u < base
   186			i--
   187			a[i] = digits[uint(u)]
   188		}
   189	
   190		// add sign, if any
   191		if neg {
   192			i--
   193			a[i] = '-'
   194		}
   195	
   196		if append_ {
   197			d = append(dst, a[i:]...)
   198			return
   199		}
   200		s = string(a[i:])
   201		return
   202	}
   203	
   204	func isPowerOfTwo(x int) bool {
   205		return x&(x-1) == 0
   206	}
   207	

View as plain text