golang natconv 代码
文件路径：/src/math/big/natconv.go
/ Copyright 2015 The Go Authors. All rights reserved.
/ Use of this source code is governed by a BSD-style
/ license that can be found in the LICENSE file.
/ This file implements nat-to-string conversion functions.
package big
import (
"errors"
"fmt"
"io"
"math"
"math/bits"
"sync"
)
const digits = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
/ Note: MaxBase = len(digits), but it must remain an untyped rune constant
/ for API compatibility.
/ MaxBase is the largest number base accepted for string conversions.
const MaxBase = 10 + ('z' - 'a' + 1) + ('Z' - 'A' + 1)
const maxBaseSmall = 10 + ('z' - 'a' + 1)
/ maxPow returns (b**n, n) such that b**n is the largest power b**n <= _M.
/ For instance maxPow(10) == (1e19, 19) for 19 decimal digits in a 64bit Word.
/ In other words, at most n digits in base b fit into a Word.
/ TODO(gri) replace this with a table, generated at build time.
func maxPow(b Word) (p Word, n int) {
p, n = b, 1 / assuming b <= _M
for max := _M / b; p <= max; {
/ p == b**n && p <= max
p *= b
n++
}
/ p == b**n && p <= _M
return
}
/ pow returns x**n for n > 0, and 1 otherwise.
func pow(x Word, n int) (p Word) {
/ n == sum of bi * 2**i, for 0 <= i < imax, and bi is 0 or 1
/ thus x**n == product of x**(2**i) for all i where bi == 1
/ (Russian Peasant Method for exponentiation)
p = 1
for n > 0 {
if n&1 != 0 {
p *= x
}
x *= x
n >>= 1
}
return
}
/ scan errors
var (
errNoDigits = errors.New("number has no digits")
errInvalSep = errors.New("'_' must separate successive digits")
)
/ scan scans the number corresponding to the longest possible prefix
/ from r representing an unsigned number in a given conversion base.
/ scan returns the corresponding natural number res, the actual base b,
/ a digit count, and a read or syntax error err, if any.
/
/ For base 0, an underscore character “_” may appear between a base
/ prefix and an adjacent digit, and between successive digits; such
/ underscores do not change the value of the number, or the returned
/ digit count. Incorrect placement of underscores is reported as an
/ error if there are no other errors. If base != 0, underscores are
/ not recognized and thus terminate scanning like any other character
/ that is not a valid radix point or digit.
/
/ number = mantissa | prefix pmantissa .
/ prefix = "0" [ "b" | "B" | "o" | "O" | "x" | "X" ] .
/ mantissa = digits "." [ digits ] | digits | "." digits .
/ pmantissa = [ "_" ] digits "." [ digits ] | [ "_" ] digits | "." digits .
/ digits = digit { [ "_" ] digit } .
/ digit = "0" ... "9" | "a" ... "z" | "A" ... "Z" .
/
/ Unless fracOk is set, the base argument must be 0 or a value between
/ 2 and MaxBase. If fracOk is set, the base argument must be one of
/ 0, 2, 8, 10, or 16. Providing an invalid base argument leads to a run-
/ time panic.
/
/ For base 0, the number prefix determines the actual base: A prefix of
/ “0b” or “0B” selects base 2, “0o” or “0O” selects base 8, and
/ “0x” or “0X” selects base 16. If fracOk is false, a “0” prefix
/ (immediately followed by digits) selects base 8 as well. Otherwise,
/ the selected base is 10 and no prefix is accepted.
/
/ If fracOk is set, a period followed by a fractional part is permitted.
/ The result value is computed as if there were no period present; and
/ the count value is used to determine the fractional part.
/
/ For bases <= 36, lower and upper case letters are considered the same:
/ The letters 'a' to 'z' and 'A' to 'Z' represent digit values 10 to 35.
/ For bases > 36, the upper case letters 'A' to 'Z' represent the digit
/ values 36 to 61.
/
/ A result digit count > 0 corresponds to the number of (non-prefix) digits
/ parsed. A digit count <= 0 indicates the presence of a period (if fracOk
/ is set, only), and -count is the number of fractional digits found.
/ In this case, the actual value of the scanned number is res * b**count.
func (z nat) scan(r io.ByteScanner, base int, fracOk bool) (res nat, b, count int, err error) {
/ reject invalid bases
baseOk := base == 0 ||
!fracOk && 2 <= base && base <= MaxBase ||
fracOk && (base == 2 || base == 8 || base == 10 || base == 16)
if !baseOk {
panic(fmt.Sprintf("invalid number base %d", base))
}
/ prev encodes the previously seen char: it is one
/ of '_', '0' (a digit), or '.' (anything else). A
/ valid separator '_' may only occur after a digit
/ and if base == 0.
prev := '.'
invalSep := false
/ one char look-ahead
ch, err := r.ReadByte()
/ determine actual base
b, prefix := base, 0
if base == 0 {
/ actual base is 10 unless there's a base prefix
b = 10
if err == nil && ch == '0' {
prev = '0'
count = 1
ch, err = r.ReadByte()
if err == nil {
/ possibly one of 0b, 0B, 0o, 0O, 0x, 0X
switch ch {
case 'b', 'B':
b, prefix = 2, 'b'
case 'o', 'O':
b, prefix = 8, 'o'
case 'x', 'X':
b, prefix = 16, 'x'
default:
if !fracOk {
b, prefix = 8, '0'
}
}
if prefix != 0 {
count = 0 / prefix is not counted
if prefix != '0' {
ch, err = r.ReadByte()
}
}
}
}
}
/ convert string
/ Algorithm: Collect digits in groups of at most n digits in di
/ and then use mulAddWW for every such group to add them to the
/ result.
z = z[:0]
b1 := Word(b)
bn, n := maxPow(b1) / at most n digits in base b1 fit into Word
di := Word(0) / 0 <= di < b1**i < bn
i := 0 / 0 <= i < n
dp := -1 / position of decimal point
for err == nil {
if ch == '.' && fracOk {
fracOk = false
if prev == '_' {
invalSep = true
}
prev = '.'
dp = count
} else if ch == '_' && base == 0 {
if prev != '0' {
invalSep = true
}
prev = '_'
} else {
/ convert rune into digit value d1
var d1 Word
switch {
case '0' <= ch && ch <= '9':
d1 = Word(ch - '0')
case 'a' <= ch && ch <= 'z':
d1 = Word(ch - 'a' + 10)
case 'A' <= ch && ch <= 'Z':
if b <= maxBaseSmall {
d1 = Word(ch - 'A' + 10)
} else {
d1 = Word(ch - 'A' + maxBaseSmall)
}
default:
d1 = MaxBase + 1
}
if d1 >= b1 {
r.UnreadByte() / ch does not belong to number anymore
break
}
prev = '0'
count++
/ collect d1 in di
di = di*b1 + d1
i++
/ if di is "full", add it to the result
if i == n {
z = z.mulAddWW(z, bn, di)
di = 0
i = 0
}
}
ch, err = r.ReadByte()
}
if err == io.EOF {
err = nil
}
/ other errors take precedence over invalid separators
if err == nil && (invalSep || prev == '_') {
err = errInvalSep
}
if count == 0 {
/ no digits found
if prefix == '0' {
/ there was only the octal prefix 0 (possibly followed by separators and digits > 7);
/ interpret as decimal 0
return z[:0], 10, 1, err
}
err = errNoDigits / fall through; result will be 0
}
/ add remaining digits to result
if i > 0 {
z = z.mulAddWW(z, pow(b1, i), di)
}
res = z.norm()
/ adjust count for fraction, if any
if dp >= 0 {
/ 0 <= dp <= count
count = dp - count
}
return
}
/ utoa converts x to an ASCII representation in the given base;
/ base must be between 2 and MaxBase, inclusive.
func (x nat) utoa(base int) []byte {
return x.itoa(false, base)
}
/ itoa is like utoa but it prepends a '-' if neg && x != 0.
func (x nat) itoa(neg bool, base int) []byte {
if base < 2 || base > MaxBase {
panic("invalid base")
}
/ x == 0
if len(x) == 0 {
return []byte("0")
}
/ len(x) > 0
/ allocate buffer for conversion
i := int(float64(x.bitLen())/math.Log2(float64(base))) + 1 / off by 1 at most
if neg {
i++
}
s := make([]byte, i)
/ convert power of two and non power of two bases separately
if b := Word(base); b == b&-b {
/ shift is base b digit size in bits
shift := uint(bits.TrailingZeros(uint(b))) / shift > 0 because b >= 2
mask := Word(1<<shift - 1)
w := x[0] / current word
nbits := uint(_W) / number of unprocessed bits in w
/ convert less-significant words (include leading zeros)
for k := 1; k < len(x); k++ {
/ convert full digits
for nbits >= shift {
i--
s[i] = digits[w&mask]
w >>= shift
nbits -= shift
}
/ convert any partial leading digit and advance to next word
if nbits == 0 {
/ no partial digit remaining, just advance
w = x[k]
nbits = _W
} else {
/ partial digit in current word w (== x[k-1]) and next word x[k]
w |= x[k] << nbits
i--
s[i] = digits[w&mask]
/ advance
w = x[k] >> (shift - nbits)
nbits = _W - (shift - nbits)
}
}
/ convert digits of most-significant word w (omit leading zeros)
for w != 0 {
i--
s[i] = digits[w&mask]
w >>= shift
}
} else {
bb, ndigits := maxPow(b)
/ construct table of successive squares of bb*leafSize to use in subdivisions
/ result (table != nil) <=> (len(x) > leafSize > 0)
table := divisors(len(x), b, ndigits, bb)
/ preserve x, create local copy for use by convertWords
q := nat(nil).set(x)
/ convert q to string s in base b
q.convertWords(s, b, ndigits, bb, table)
/ strip leading zeros
/ (x != 0; thus s must contain at least one non-zero digit
/ and the loop will terminate)
i = 0
for s[i] == '0' {
i++
}
}
if neg {
i--
s[i] = '-'
}
return s[i:]
}
/ Convert words of q to base b digits in s. If q is large, it is recursively "split in half"
/ by nat/nat division using tabulated divisors. Otherwise, it is converted iteratively using
/ repeated nat/Word division.
/
/ The iterative method processes n Words by n divW() calls, each of which visits every Word in the
/ incrementally shortened q for a total of n + (n-1) + (n-2) ... + 2 + 1, or n(n+1)/2 divW()'s.
/ Recursive conversion divides q by its approximate square root, yielding two parts, each half
/ the size of q. Using the iterative method on both halves means 2 * (n/2)(n/2 + 1)/2 divW()'s
/ plus the expensive long div(). Asymptotically, the ratio is favorable at 1/2 the divW()'s, and
/ is made better by splitting the subblocks recursively. Best is to split blocks until one more
/ split would take longer (because of the nat/nat div()) than the twice as many divW()'s of the
/ iterative approach. This threshold is represented by leafSize. Benchmarking of leafSize in the
/ range 2..64 shows that values of 8 and 16 work well, with a 4x speedup at medium lengths and
/ ~30x for 20000 digits. Use nat_test.go's BenchmarkLeafSize tests to optimize leafSize for
/ specific hardware.
func (q nat) convertWords(s []byte, b Word, ndigits int, bb Word, table []divisor) {
/ split larger blocks recursively
if table != nil {
/ len(q) > leafSize > 0
var r nat
index := len(table) - 1
for len(q) > leafSize {
/ find divisor close to sqrt(q) if possible, but in any case < q
maxLength := q.bitLen() / ~= log2 q, or at of least largest possible q of this bit length
minLength := maxLength >> 1 / ~= log2 sqrt(q)
for index > 0 && table[index-1].nbits > minLength {
index-- / desired
}
if table[index].nbits >= maxLength && table[index].bbb.cmp(q) >= 0 {
index--
if index < 0 {
panic("internal inconsistency")
}
}
/ split q into the two digit number (q'*bbb + r) to form independent subblocks
q, r = q.div(r, q, table[index].bbb)
/ convert subblocks and collect results in s[:h] and s[h:]
h := len(s) - table[index].ndigits
r.convertWords(s[h:], b, ndigits, bb, table[0:index])
s = s[:h] / == q.convertWords(s, b, ndigits, bb, table[0:index+1])
}
}
/ having split any large blocks now process the remaining (small) block iteratively
i := len(s)
var r Word
if b == 10 {
/ hard-coding for 10 here speeds this up by 1.25x (allows for / and % by constants)
for len(q) > 0 {
/ extract least significant, base bb "digit"
q, r = q.divW(q, bb)
for j := 0; j < ndigits && i > 0; j++ {
i--
/ avoid % computation since r%10 == r - int(r/10)*10;
/ this appears to be faster for BenchmarkString10000Base10
/ and smaller strings (but a bit slower for larger ones)
t := r / 10
s[i] = '0' + byte(r-t*10)
r = t
}
}
} else {
for len(q) > 0 {
/ extract least significant, base bb "digit"
q, r = q.divW(q, bb)
for j := 0; j < ndigits && i > 0; j++ {
i--
s[i] = digits[r%b]
r /= b
}
}
}
/ prepend high-order zeros
for i > 0 { / while need more leading zeros
i--
s[i] = '0'
}
}
/ Split blocks greater than leafSize Words (or set to 0 to disable recursive conversion)
/ Benchmark and configure leafSize using: go test -bench="Leaf"
/
/ 8 and 16 effective on 3.0 GHz Xeon "Clovertown" CPU (128 byte cache lines)
/ 8 and 16 effective on 2.66 GHz Core 2 Duo "Penryn" CPU
var leafSize int = 8 / number of Word-size binary values treat as a monolithic block
type divisor struct {
bbb nat / divisor
nbits int / bit length of divisor (discounting leading zeros) ~= log2(bbb)
ndigits int / digit length of divisor in terms of output base digits
}
var cacheBase10 struct {
sync.Mutex
table [64]divisor / cached divisors for base 10
}
/ expWW computes x**y
func (z nat) expWW(x, y Word) nat {
return z.expNN(nat(nil).setWord(x), nat(nil).setWord(y), nil)
}
/ construct table of powers of bb*leafSize to use in subdivisions
func divisors(m int, b Word, ndigits int, bb Word) []divisor {
/ only compute table when recursive conversion is enabled and x is large
if leafSize == 0 || m <= leafSize {
return nil
}
/ determine k where (bb**leafSize)**(2**k) >= sqrt(x)
k := 1
for words := leafSize; words < m>>1 && k < len(cacheBase10.table); words <<= 1 {
k++
}
/ reuse and extend existing table of divisors or create new table as appropriate
var table []divisor / for b == 10, table overlaps with cacheBase10.table
if b == 10 {
cacheBase10.Lock()
table = cacheBase10.table[0:k] / reuse old table for this conversion
} else {
table = make([]divisor, k) / create new table for this conversion
}
/ extend table
if table[k-1].ndigits == 0 {
/ add new entries as needed
var larger nat
for i := 0; i < k; i++ {
if table[i].ndigits == 0 {
if i == 0 {
table[0].bbb = nat(nil).expWW(bb, Word(leafSize))
table[0].ndigits = ndigits * leafSize
} else {
table[i].bbb = nat(nil).sqr(table[i-1].bbb)
table[i].ndigits = 2 * table[i-1].ndigits
}
/ optimization: exploit aggregated extra bits in macro blocks
larger = nat(nil).set(table[i].bbb)
for mulAddVWW(larger, larger, b, 0) == 0 {
table[i].bbb = table[i].bbb.set(larger)
table[i].ndigits++
}
table[i].nbits = table[i].bbb.bitLen()
}
}
}
if b == 10 {
cacheBase10.Unlock()
}
return table
}