Source file src/math/big/natconv.go

     1  // Copyright 2015 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  // This file implements nat-to-string conversion functions.
     6  
     7  package big
     8  
     9  import (
    10  	"errors"
    11  	"fmt"
    12  	"io"
    13  	"math"
    14  	"math/bits"
    15  	"sync"
    16  )
    17  
    18  const digits = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    19  
    20  // Note: MaxBase = len(digits), but it must remain an untyped rune constant
    21  //       for API compatibility.
    22  
    23  // MaxBase is the largest number base accepted for string conversions.
    24  const MaxBase = 10 + ('z' - 'a' + 1) + ('Z' - 'A' + 1)
    25  const maxBaseSmall = 10 + ('z' - 'a' + 1)
    26  
    27  // maxPow returns (b**n, n) such that b**n is the largest power b**n <= _M.
    28  // For instance maxPow(10) == (1e19, 19) for 19 decimal digits in a 64bit Word.
    29  // In other words, at most n digits in base b fit into a Word.
    30  // TODO(gri) replace this with a table, generated at build time.
    31  func maxPow(b Word) (p Word, n int) {
    32  	p, n = b, 1 // assuming b <= _M
    33  	for max := _M / b; p <= max; {
    34  		// p == b**n && p <= max
    35  		p *= b
    36  		n++
    37  	}
    38  	// p == b**n && p <= _M
    39  	return
    40  }
    41  
    42  // pow returns x**n for n > 0, and 1 otherwise.
    43  func pow(x Word, n int) (p Word) {
    44  	// n == sum of bi * 2**i, for 0 <= i < imax, and bi is 0 or 1
    45  	// thus x**n == product of x**(2**i) for all i where bi == 1
    46  	// (Russian Peasant Method for exponentiation)
    47  	p = 1
    48  	for n > 0 {
    49  		if n&1 != 0 {
    50  			p *= x
    51  		}
    52  		x *= x
    53  		n >>= 1
    54  	}
    55  	return
    56  }
    57  
    58  // scan errors
    59  var (
    60  	errNoDigits = errors.New("number has no digits")
    61  	errInvalSep = errors.New("'_' must separate successive digits")
    62  )
    63  
    64  // scan scans the number corresponding to the longest possible prefix
    65  // from r representing an unsigned number in a given conversion base.
    66  // scan returns the corresponding natural number res, the actual base b,
    67  // a digit count, and a read or syntax error err, if any.
    68  //
    69  // For base 0, an underscore character “_” may appear between a base
    70  // prefix and an adjacent digit, and between successive digits; such
    71  // underscores do not change the value of the number, or the returned
    72  // digit count. Incorrect placement of underscores is reported as an
    73  // error if there are no other errors. If base != 0, underscores are
    74  // not recognized and thus terminate scanning like any other character
    75  // that is not a valid radix point or digit.
    76  //
    77  //	number    = mantissa | prefix pmantissa .
    78  //	prefix    = "0" [ "b" | "B" | "o" | "O" | "x" | "X" ] .
    79  //	mantissa  = digits "." [ digits ] | digits | "." digits .
    80  //	pmantissa = [ "_" ] digits "." [ digits ] | [ "_" ] digits | "." digits .
    81  //	digits    = digit { [ "_" ] digit } .
    82  //	digit     = "0" ... "9" | "a" ... "z" | "A" ... "Z" .
    83  //
    84  // Unless fracOk is set, the base argument must be 0 or a value between
    85  // 2 and MaxBase. If fracOk is set, the base argument must be one of
    86  // 0, 2, 8, 10, or 16. Providing an invalid base argument leads to a run-
    87  // time panic.
    88  //
    89  // For base 0, the number prefix determines the actual base: A prefix of
    90  // “0b” or “0B” selects base 2, “0o” or “0O” selects base 8, and
    91  // “0x” or “0X” selects base 16. If fracOk is false, a “0” prefix
    92  // (immediately followed by digits) selects base 8 as well. Otherwise,
    93  // the selected base is 10 and no prefix is accepted.
    94  //
    95  // If fracOk is set, a period followed by a fractional part is permitted.
    96  // The result value is computed as if there were no period present; and
    97  // the count value is used to determine the fractional part.
    98  //
    99  // For bases <= 36, lower and upper case letters are considered the same:
   100  // The letters 'a' to 'z' and 'A' to 'Z' represent digit values 10 to 35.
   101  // For bases > 36, the upper case letters 'A' to 'Z' represent the digit
   102  // values 36 to 61.
   103  //
   104  // A result digit count > 0 corresponds to the number of (non-prefix) digits
   105  // parsed. A digit count <= 0 indicates the presence of a period (if fracOk
   106  // is set, only), and -count is the number of fractional digits found.
   107  // In this case, the actual value of the scanned number is res * b**count.
   108  func (z nat) scan(r io.ByteScanner, base int, fracOk bool) (res nat, b, count int, err error) {
   109  	// reject invalid bases
   110  	baseOk := base == 0 ||
   111  		!fracOk && 2 <= base && base <= MaxBase ||
   112  		fracOk && (base == 2 || base == 8 || base == 10 || base == 16)
   113  	if !baseOk {
   114  		panic(fmt.Sprintf("invalid number base %d", base))
   115  	}
   116  
   117  	// prev encodes the previously seen char: it is one
   118  	// of '_', '0' (a digit), or '.' (anything else). A
   119  	// valid separator '_' may only occur after a digit
   120  	// and if base == 0.
   121  	prev := '.'
   122  	invalSep := false
   123  
   124  	// one char look-ahead
   125  	ch, err := r.ReadByte()
   126  
   127  	// determine actual base
   128  	b, prefix := base, 0
   129  	if base == 0 {
   130  		// actual base is 10 unless there's a base prefix
   131  		b = 10
   132  		if err == nil && ch == '0' {
   133  			prev = '0'
   134  			count = 1
   135  			ch, err = r.ReadByte()
   136  			if err == nil {
   137  				// possibly one of 0b, 0B, 0o, 0O, 0x, 0X
   138  				switch ch {
   139  				case 'b', 'B':
   140  					b, prefix = 2, 'b'
   141  				case 'o', 'O':
   142  					b, prefix = 8, 'o'
   143  				case 'x', 'X':
   144  					b, prefix = 16, 'x'
   145  				default:
   146  					if !fracOk {
   147  						b, prefix = 8, '0'
   148  					}
   149  				}
   150  				if prefix != 0 {
   151  					count = 0 // prefix is not counted
   152  					if prefix != '0' {
   153  						ch, err = r.ReadByte()
   154  					}
   155  				}
   156  			}
   157  		}
   158  	}
   159  
   160  	// convert string
   161  	// Algorithm: Collect digits in groups of at most n digits in di
   162  	// and then use mulAddWW for every such group to add them to the
   163  	// result.
   164  	z = z[:0]
   165  	b1 := Word(b)
   166  	bn, n := maxPow(b1) // at most n digits in base b1 fit into Word
   167  	di := Word(0)       // 0 <= di < b1**i < bn
   168  	i := 0              // 0 <= i < n
   169  	dp := -1            // position of decimal point
   170  	for err == nil {
   171  		if ch == '.' && fracOk {
   172  			fracOk = false
   173  			if prev == '_' {
   174  				invalSep = true
   175  			}
   176  			prev = '.'
   177  			dp = count
   178  		} else if ch == '_' && base == 0 {
   179  			if prev != '0' {
   180  				invalSep = true
   181  			}
   182  			prev = '_'
   183  		} else {
   184  			// convert rune into digit value d1
   185  			var d1 Word
   186  			switch {
   187  			case '0' <= ch && ch <= '9':
   188  				d1 = Word(ch - '0')
   189  			case 'a' <= ch && ch <= 'z':
   190  				d1 = Word(ch - 'a' + 10)
   191  			case 'A' <= ch && ch <= 'Z':
   192  				if b <= maxBaseSmall {
   193  					d1 = Word(ch - 'A' + 10)
   194  				} else {
   195  					d1 = Word(ch - 'A' + maxBaseSmall)
   196  				}
   197  			default:
   198  				d1 = MaxBase + 1
   199  			}
   200  			if d1 >= b1 {
   201  				r.UnreadByte() // ch does not belong to number anymore
   202  				break
   203  			}
   204  			prev = '0'
   205  			count++
   206  
   207  			// collect d1 in di
   208  			di = di*b1 + d1
   209  			i++
   210  
   211  			// if di is "full", add it to the result
   212  			if i == n {
   213  				z = z.mulAddWW(z, bn, di)
   214  				di = 0
   215  				i = 0
   216  			}
   217  		}
   218  
   219  		ch, err = r.ReadByte()
   220  	}
   221  
   222  	if err == io.EOF {
   223  		err = nil
   224  	}
   225  
   226  	// other errors take precedence over invalid separators
   227  	if err == nil && (invalSep || prev == '_') {
   228  		err = errInvalSep
   229  	}
   230  
   231  	if count == 0 {
   232  		// no digits found
   233  		if prefix == '0' {
   234  			// there was only the octal prefix 0 (possibly followed by separators and digits > 7);
   235  			// interpret as decimal 0
   236  			return z[:0], 10, 1, err
   237  		}
   238  		err = errNoDigits // fall through; result will be 0
   239  	}
   240  
   241  	// add remaining digits to result
   242  	if i > 0 {
   243  		z = z.mulAddWW(z, pow(b1, i), di)
   244  	}
   245  	res = z.norm()
   246  
   247  	// adjust count for fraction, if any
   248  	if dp >= 0 {
   249  		// 0 <= dp <= count
   250  		count = dp - count
   251  	}
   252  
   253  	return
   254  }
   255  
   256  // utoa converts x to an ASCII representation in the given base;
   257  // base must be between 2 and MaxBase, inclusive.
   258  func (x nat) utoa(base int) []byte {
   259  	return x.itoa(false, base)
   260  }
   261  
   262  // itoa is like utoa but it prepends a '-' if neg && x != 0.
   263  func (x nat) itoa(neg bool, base int) []byte {
   264  	if base < 2 || base > MaxBase {
   265  		panic("invalid base")
   266  	}
   267  
   268  	// x == 0
   269  	if len(x) == 0 {
   270  		return []byte("0")
   271  	}
   272  	// len(x) > 0
   273  
   274  	// allocate buffer for conversion
   275  	i := int(float64(x.bitLen())/math.Log2(float64(base))) + 1 // off by 1 at most
   276  	if neg {
   277  		i++
   278  	}
   279  	s := make([]byte, i)
   280  
   281  	// convert power of two and non power of two bases separately
   282  	if b := Word(base); b == b&-b {
   283  		// shift is base b digit size in bits
   284  		shift := uint(bits.TrailingZeros(uint(b))) // shift > 0 because b >= 2
   285  		mask := Word(1<<shift - 1)
   286  		w := x[0]         // current word
   287  		nbits := uint(_W) // number of unprocessed bits in w
   288  
   289  		// convert less-significant words (include leading zeros)
   290  		for k := 1; k < len(x); k++ {
   291  			// convert full digits
   292  			for nbits >= shift {
   293  				i--
   294  				s[i] = digits[w&mask]
   295  				w >>= shift
   296  				nbits -= shift
   297  			}
   298  
   299  			// convert any partial leading digit and advance to next word
   300  			if nbits == 0 {
   301  				// no partial digit remaining, just advance
   302  				w = x[k]
   303  				nbits = _W
   304  			} else {
   305  				// partial digit in current word w (== x[k-1]) and next word x[k]
   306  				w |= x[k] << nbits
   307  				i--
   308  				s[i] = digits[w&mask]
   309  
   310  				// advance
   311  				w = x[k] >> (shift - nbits)
   312  				nbits = _W - (shift - nbits)
   313  			}
   314  		}
   315  
   316  		// convert digits of most-significant word w (omit leading zeros)
   317  		for w != 0 {
   318  			i--
   319  			s[i] = digits[w&mask]
   320  			w >>= shift
   321  		}
   322  
   323  	} else {
   324  		bb, ndigits := maxPow(b)
   325  
   326  		// construct table of successive squares of bb*leafSize to use in subdivisions
   327  		// result (table != nil) <=> (len(x) > leafSize > 0)
   328  		table := divisors(len(x), b, ndigits, bb)
   329  
   330  		// preserve x, create local copy for use by convertWords
   331  		q := nat(nil).set(x)
   332  
   333  		// convert q to string s in base b
   334  		q.convertWords(s, b, ndigits, bb, table)
   335  
   336  		// strip leading zeros
   337  		// (x != 0; thus s must contain at least one non-zero digit
   338  		// and the loop will terminate)
   339  		i = 0
   340  		for s[i] == '0' {
   341  			i++
   342  		}
   343  	}
   344  
   345  	if neg {
   346  		i--
   347  		s[i] = '-'
   348  	}
   349  
   350  	return s[i:]
   351  }
   352  
   353  // Convert words of q to base b digits in s. If q is large, it is recursively "split in half"
   354  // by nat/nat division using tabulated divisors. Otherwise, it is converted iteratively using
   355  // repeated nat/Word division.
   356  //
   357  // The iterative method processes n Words by n divW() calls, each of which visits every Word in the
   358  // incrementally shortened q for a total of n + (n-1) + (n-2) ... + 2 + 1, or n(n+1)/2 divW()'s.
   359  // Recursive conversion divides q by its approximate square root, yielding two parts, each half
   360  // the size of q. Using the iterative method on both halves means 2 * (n/2)(n/2 + 1)/2 divW()'s
   361  // plus the expensive long div(). Asymptotically, the ratio is favorable at 1/2 the divW()'s, and
   362  // is made better by splitting the subblocks recursively. Best is to split blocks until one more
   363  // split would take longer (because of the nat/nat div()) than the twice as many divW()'s of the
   364  // iterative approach. This threshold is represented by leafSize. Benchmarking of leafSize in the
   365  // range 2..64 shows that values of 8 and 16 work well, with a 4x speedup at medium lengths and
   366  // ~30x for 20000 digits. Use nat_test.go's BenchmarkLeafSize tests to optimize leafSize for
   367  // specific hardware.
   368  func (q nat) convertWords(s []byte, b Word, ndigits int, bb Word, table []divisor) {
   369  	// split larger blocks recursively
   370  	if table != nil {
   371  		// len(q) > leafSize > 0
   372  		var r nat
   373  		index := len(table) - 1
   374  		for len(q) > leafSize {
   375  			// find divisor close to sqrt(q) if possible, but in any case < q
   376  			maxLength := q.bitLen()     // ~= log2 q, or at of least largest possible q of this bit length
   377  			minLength := maxLength >> 1 // ~= log2 sqrt(q)
   378  			for index > 0 && table[index-1].nbits > minLength {
   379  				index-- // desired
   380  			}
   381  			if table[index].nbits >= maxLength && table[index].bbb.cmp(q) >= 0 {
   382  				index--
   383  				if index < 0 {
   384  					panic("internal inconsistency")
   385  				}
   386  			}
   387  
   388  			// split q into the two digit number (q'*bbb + r) to form independent subblocks
   389  			q, r = q.div(r, q, table[index].bbb)
   390  
   391  			// convert subblocks and collect results in s[:h] and s[h:]
   392  			h := len(s) - table[index].ndigits
   393  			r.convertWords(s[h:], b, ndigits, bb, table[0:index])
   394  			s = s[:h] // == q.convertWords(s, b, ndigits, bb, table[0:index+1])
   395  		}
   396  	}
   397  
   398  	// having split any large blocks now process the remaining (small) block iteratively
   399  	i := len(s)
   400  	var r Word
   401  	if b == 10 {
   402  		// hard-coding for 10 here speeds this up by 1.25x (allows for / and % by constants)
   403  		for len(q) > 0 {
   404  			// extract least significant, base bb "digit"
   405  			q, r = q.divW(q, bb)
   406  			for j := 0; j < ndigits && i > 0; j++ {
   407  				i--
   408  				// avoid % computation since r%10 == r - int(r/10)*10;
   409  				// this appears to be faster for BenchmarkString10000Base10
   410  				// and smaller strings (but a bit slower for larger ones)
   411  				t := r / 10
   412  				s[i] = '0' + byte(r-t*10)
   413  				r = t
   414  			}
   415  		}
   416  	} else {
   417  		for len(q) > 0 {
   418  			// extract least significant, base bb "digit"
   419  			q, r = q.divW(q, bb)
   420  			for j := 0; j < ndigits && i > 0; j++ {
   421  				i--
   422  				s[i] = digits[r%b]
   423  				r /= b
   424  			}
   425  		}
   426  	}
   427  
   428  	// prepend high-order zeros
   429  	for i > 0 { // while need more leading zeros
   430  		i--
   431  		s[i] = '0'
   432  	}
   433  }
   434  
   435  // Split blocks greater than leafSize Words (or set to 0 to disable recursive conversion)
   436  // Benchmark and configure leafSize using: go test -bench="Leaf"
   437  //
   438  //	8 and 16 effective on 3.0 GHz Xeon "Clovertown" CPU (128 byte cache lines)
   439  //	8 and 16 effective on 2.66 GHz Core 2 Duo "Penryn" CPU
   440  var leafSize int = 8 // number of Word-size binary values treat as a monolithic block
   441  
   442  type divisor struct {
   443  	bbb     nat // divisor
   444  	nbits   int // bit length of divisor (discounting leading zeros) ~= log2(bbb)
   445  	ndigits int // digit length of divisor in terms of output base digits
   446  }
   447  
   448  var cacheBase10 struct {
   449  	sync.Mutex
   450  	table [64]divisor // cached divisors for base 10
   451  }
   452  
   453  // expWW computes x**y
   454  func (z nat) expWW(x, y Word) nat {
   455  	return z.expNN(nat(nil).setWord(x), nat(nil).setWord(y), nil, false)
   456  }
   457  
   458  // construct table of powers of bb*leafSize to use in subdivisions.
   459  func divisors(m int, b Word, ndigits int, bb Word) []divisor {
   460  	// only compute table when recursive conversion is enabled and x is large
   461  	if leafSize == 0 || m <= leafSize {
   462  		return nil
   463  	}
   464  
   465  	// determine k where (bb**leafSize)**(2**k) >= sqrt(x)
   466  	k := 1
   467  	for words := leafSize; words < m>>1 && k < len(cacheBase10.table); words <<= 1 {
   468  		k++
   469  	}
   470  
   471  	// reuse and extend existing table of divisors or create new table as appropriate
   472  	var table []divisor // for b == 10, table overlaps with cacheBase10.table
   473  	if b == 10 {
   474  		cacheBase10.Lock()
   475  		table = cacheBase10.table[0:k] // reuse old table for this conversion
   476  	} else {
   477  		table = make([]divisor, k) // create new table for this conversion
   478  	}
   479  
   480  	// extend table
   481  	if table[k-1].ndigits == 0 {
   482  		// add new entries as needed
   483  		var larger nat
   484  		for i := 0; i < k; i++ {
   485  			if table[i].ndigits == 0 {
   486  				if i == 0 {
   487  					table[0].bbb = nat(nil).expWW(bb, Word(leafSize))
   488  					table[0].ndigits = ndigits * leafSize
   489  				} else {
   490  					table[i].bbb = nat(nil).sqr(table[i-1].bbb)
   491  					table[i].ndigits = 2 * table[i-1].ndigits
   492  				}
   493  
   494  				// optimization: exploit aggregated extra bits in macro blocks
   495  				larger = nat(nil).set(table[i].bbb)
   496  				for mulAddVWW(larger, larger, b, 0) == 0 {
   497  					table[i].bbb = table[i].bbb.set(larger)
   498  					table[i].ndigits++
   499  				}
   500  
   501  				table[i].nbits = table[i].bbb.bitLen()
   502  			}
   503  		}
   504  	}
   505  
   506  	if b == 10 {
   507  		cacheBase10.Unlock()
   508  	}
   509  
   510  	return table
   511  }
   512  

View as plain text