codekingpro/portable-devtools

1// Copyright 2015 The Go Authors. All rights reserved.2// Use of this source code is governed by a BSD-style3// license that can be found in the LICENSE file.4 5// This file implements nat-to-string conversion functions.6 7package big8 9import (10	"errors"11	"fmt"12	"io"13	"math"14	"math/bits"15	"slices"16	"sync"17)18 19const digits = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"20 21// Note: MaxBase = len(digits), but it must remain an untyped rune constant22//       for API compatibility.23 24// MaxBase is the largest number base accepted for string conversions.25const MaxBase = 10 + ('z' - 'a' + 1) + ('Z' - 'A' + 1)26const maxBaseSmall = 10 + ('z' - 'a' + 1)27 28// maxPow returns (b**n, n) such that b**n is the largest power b**n <= _M.29// For instance maxPow(10) == (1e19, 19) for 19 decimal digits in a 64bit Word.30// In other words, at most n digits in base b fit into a Word.31// TODO(gri) replace this with a table, generated at build time.32func maxPow(b Word) (p Word, n int) {33	p, n = b, 1 // assuming b <= _M34	for max := _M / b; p <= max; {35		// p == b**n && p <= max36		p *= b37		n++38	}39	// p == b**n && p <= _M40	return41}42 43// pow returns x**n for n > 0, and 1 otherwise.44func pow(x Word, n int) (p Word) {45	// n == sum of bi * 2**i, for 0 <= i < imax, and bi is 0 or 146	// thus x**n == product of x**(2**i) for all i where bi == 147	// (Russian Peasant Method for exponentiation)48	p = 149	for n > 0 {50		if n&1 != 0 {51			p *= x52		}53		x *= x54		n >>= 155	}56	return57}58 59// scan errors60var (61	errNoDigits = errors.New("number has no digits")62	errInvalSep = errors.New("'_' must separate successive digits")63)64 65// scan scans the number corresponding to the longest possible prefix66// from r representing an unsigned number in a given conversion base.67// scan returns the corresponding natural number res, the actual base b,68// a digit count, and a read or syntax error err, if any.69//70// For base 0, an underscore character “_” may appear between a base71// prefix and an adjacent digit, and between successive digits; such72// underscores do not change the value of the number, or the returned73// digit count. Incorrect placement of underscores is reported as an74// error if there are no other errors. If base != 0, underscores are75// not recognized and thus terminate scanning like any other character76// that is not a valid radix point or digit.77//78//	number    = mantissa | prefix pmantissa .79//	prefix    = "0" [ "b" | "B" | "o" | "O" | "x" | "X" ] .80//	mantissa  = digits "." [ digits ] | digits | "." digits .81//	pmantissa = [ "_" ] digits "." [ digits ] | [ "_" ] digits | "." digits .82//	digits    = digit { [ "_" ] digit } .83//	digit     = "0" ... "9" | "a" ... "z" | "A" ... "Z" .84//85// Unless fracOk is set, the base argument must be 0 or a value between86// 2 and MaxBase. If fracOk is set, the base argument must be one of87// 0, 2, 8, 10, or 16. Providing an invalid base argument leads to a run-88// time panic.89//90// For base 0, the number prefix determines the actual base: A prefix of91// “0b” or “0B” selects base 2, “0o” or “0O” selects base 8, and92// “0x” or “0X” selects base 16. If fracOk is false, a “0” prefix93// (immediately followed by digits) selects base 8 as well. Otherwise,94// the selected base is 10 and no prefix is accepted.95//96// If fracOk is set, a period followed by a fractional part is permitted.97// The result value is computed as if there were no period present; and98// the count value is used to determine the fractional part.99//100// For bases <= 36, lower and upper case letters are considered the same:101// The letters 'a' to 'z' and 'A' to 'Z' represent digit values 10 to 35.102// For bases > 36, the upper case letters 'A' to 'Z' represent the digit103// values 36 to 61.104//105// A result digit count > 0 corresponds to the number of (non-prefix) digits106// parsed. A digit count <= 0 indicates the presence of a period (if fracOk107// is set, only), and -count is the number of fractional digits found.108// In this case, the actual value of the scanned number is res * b**count.109func (z nat) scan(r io.ByteScanner, base int, fracOk bool) (res nat, b, count int, err error) {110	// Reject invalid bases.111	baseOk := base == 0 ||112		!fracOk && 2 <= base && base <= MaxBase ||113		fracOk && (base == 2 || base == 8 || base == 10 || base == 16)114	if !baseOk {115		panic(fmt.Sprintf("invalid number base %d", base))116	}117 118	// prev encodes the previously seen char: it is one119	// of '_', '0' (a digit), or '.' (anything else). A120	// valid separator '_' may only occur after a digit121	// and if base == 0.122	prev := '.'123	invalSep := false124 125	// one char look-ahead126	ch, err := r.ReadByte()127 128	// Determine actual base.129	b, prefix := base, 0130	if base == 0 {131		// Actual base is 10 unless there's a base prefix.132		b = 10133		if err == nil && ch == '0' {134			prev = '0'135			count = 1136			ch, err = r.ReadByte()137			if err == nil {138				// possibly one of 0b, 0B, 0o, 0O, 0x, 0X139				switch ch {140				case 'b', 'B':141					b, prefix = 2, 'b'142				case 'o', 'O':143					b, prefix = 8, 'o'144				case 'x', 'X':145					b, prefix = 16, 'x'146				default:147					if !fracOk {148						b, prefix = 8, '0'149					}150				}151				if prefix != 0 {152					count = 0 // prefix is not counted153					if prefix != '0' {154						ch, err = r.ReadByte()155					}156				}157			}158		}159	}160 161	// Convert string.162	// Algorithm: Collect digits in groups of at most n digits in di.163	// For bases that pack exactly into words (2, 4, 16), append di's164	// directly to the int representation and then reverse at the end (bn==0 marks this case).165	// For other bases, use mulAddWW for every such group to shift166	// z up one group and add di to the result.167	// With more cleverness we could also handle binary bases like 8 and 32168	// (corresponding to 3-bit and 5-bit chunks) that don't pack nicely into169	// words, but those are not too important.170	z = z[:0]171	b1 := Word(b)172	var bn Word // b1**n (or 0 for the special bit-packing cases b=2,4,16)173	var n int   // max digits that fit into Word174	switch b {175	case 2: // 1 bit per digit176		n = _W177	case 4: // 2 bits per digit178		n = _W / 2179	case 16: // 4 bits per digit180		n = _W / 4181	default:182		bn, n = maxPow(b1)183	}184	di := Word(0) // 0 <= di < b1**i < bn185	i := 0        // 0 <= i < n186	dp := -1      // position of decimal point187	for err == nil {188		if ch == '.' && fracOk {189			fracOk = false190			if prev == '_' {191				invalSep = true192			}193			prev = '.'194			dp = count195		} else if ch == '_' && base == 0 {196			if prev != '0' {197				invalSep = true198			}199			prev = '_'200		} else {201			// convert rune into digit value d1202			var d1 Word203			switch {204			case '0' <= ch && ch <= '9':205				d1 = Word(ch - '0')206			case 'a' <= ch && ch <= 'z':207				d1 = Word(ch - 'a' + 10)208			case 'A' <= ch && ch <= 'Z':209				if b <= maxBaseSmall {210					d1 = Word(ch - 'A' + 10)211				} else {212					d1 = Word(ch - 'A' + maxBaseSmall)213				}214			default:215				d1 = MaxBase + 1216			}217			if d1 >= b1 {218				r.UnreadByte() // ch does not belong to number anymore219				break220			}221			prev = '0'222			count++223 224			// collect d1 in di225			di = di*b1 + d1226			i++227 228			// if di is "full", add it to the result229			if i == n {230				if bn == 0 {231					z = append(z, di)232				} else {233					z = z.mulAddWW(z, bn, di)234				}235				di = 0236				i = 0237			}238		}239 240		ch, err = r.ReadByte()241	}242 243	if err == io.EOF {244		err = nil245	}246 247	// other errors take precedence over invalid separators248	if err == nil && (invalSep || prev == '_') {249		err = errInvalSep250	}251 252	if count == 0 {253		// no digits found254		if prefix == '0' {255			// there was only the octal prefix 0 (possibly followed by separators and digits > 7);256			// interpret as decimal 0257			return z[:0], 10, 1, err258		}259		err = errNoDigits // fall through; result will be 0260	}261 262	if bn == 0 {263		if i > 0 {264			// Add remaining digit chunk to result.265			// Left-justify group's digits; will shift back down after reverse.266			z = append(z, di*pow(b1, n-i))267		}268		slices.Reverse(z)269		z = z.norm()270		if i > 0 {271			z = z.rsh(z, uint(n-i)*uint(_W/n))272		}273	} else {274		if i > 0 {275			// Add remaining digit chunk to result.276			z = z.mulAddWW(z, pow(b1, i), di)277		}278	}279	res = z280 281	// adjust count for fraction, if any282	if dp >= 0 {283		// 0 <= dp <= count284		count = dp - count285	}286 287	return288}289 290// utoa converts x to an ASCII representation in the given base;291// base must be between 2 and MaxBase, inclusive.292func (x nat) utoa(base int) []byte {293	return x.itoa(false, base)294}295 296// itoa is like utoa but it prepends a '-' if neg && x != 0.297func (x nat) itoa(neg bool, base int) []byte {298	if base < 2 || base > MaxBase {299		panic("invalid base")300	}301 302	// x == 0303	if len(x) == 0 {304		return []byte("0")305	}306	// len(x) > 0307 308	// allocate buffer for conversion309	i := int(float64(x.bitLen())/math.Log2(float64(base))) + 1 // off by 1 at most310	if neg {311		i++312	}313	s := make([]byte, i)314 315	// convert power of two and non power of two bases separately316	if b := Word(base); b == b&-b {317		// shift is base b digit size in bits318		shift := uint(bits.TrailingZeros(uint(b))) // shift > 0 because b >= 2319		mask := Word(1<<shift - 1)320		w := x[0]         // current word321		nbits := uint(_W) // number of unprocessed bits in w322 323		// convert less-significant words (include leading zeros)324		for k := 1; k < len(x); k++ {325			// convert full digits326			for nbits >= shift {327				i--328				s[i] = digits[w&mask]329				w >>= shift330				nbits -= shift331			}332 333			// convert any partial leading digit and advance to next word334			if nbits == 0 {335				// no partial digit remaining, just advance336				w = x[k]337				nbits = _W338			} else {339				// partial digit in current word w (== x[k-1]) and next word x[k]340				w |= x[k] << nbits341				i--342				s[i] = digits[w&mask]343 344				// advance345				w = x[k] >> (shift - nbits)346				nbits = _W - (shift - nbits)347			}348		}349 350		// convert digits of most-significant word w (omit leading zeros)351		for w != 0 {352			i--353			s[i] = digits[w&mask]354			w >>= shift355		}356 357	} else {358		stk := getStack()359		defer stk.free()360 361		bb, ndigits := maxPow(b)362 363		// construct table of successive squares of bb*leafSize to use in subdivisions364		// result (table != nil) <=> (len(x) > leafSize > 0)365		table := divisors(stk, len(x), b, ndigits, bb)366 367		// preserve x, create local copy for use by convertWords368		q := nat(nil).set(x)369 370		// convert q to string s in base b371		q.convertWords(stk, s, b, ndigits, bb, table)372 373		// strip leading zeros374		// (x != 0; thus s must contain at least one non-zero digit375		// and the loop will terminate)376		i = 0377		for s[i] == '0' {378			i++379		}380	}381 382	if neg {383		i--384		s[i] = '-'385	}386 387	return s[i:]388}389 390// Convert words of q to base b digits in s. If q is large, it is recursively "split in half"391// by nat/nat division using tabulated divisors. Otherwise, it is converted iteratively using392// repeated nat/Word division.393//394// The iterative method processes n Words by n divW() calls, each of which visits every Word in the395// incrementally shortened q for a total of n + (n-1) + (n-2) ... + 2 + 1, or n(n+1)/2 divW()'s.396// Recursive conversion divides q by its approximate square root, yielding two parts, each half397// the size of q. Using the iterative method on both halves means 2 * (n/2)(n/2 + 1)/2 divW()'s398// plus the expensive long div(). Asymptotically, the ratio is favorable at 1/2 the divW()'s, and399// is made better by splitting the subblocks recursively. Best is to split blocks until one more400// split would take longer (because of the nat/nat div()) than the twice as many divW()'s of the401// iterative approach. This threshold is represented by leafSize. Benchmarking of leafSize in the402// range 2..64 shows that values of 8 and 16 work well, with a 4x speedup at medium lengths and403// ~30x for 20000 digits. Use nat_test.go's BenchmarkLeafSize tests to optimize leafSize for404// specific hardware.405func (q nat) convertWords(stk *stack, s []byte, b Word, ndigits int, bb Word, table []divisor) {406	// split larger blocks recursively407	if table != nil {408		// len(q) > leafSize > 0409		var r nat410		index := len(table) - 1411		for len(q) > leafSize {412			// find divisor close to sqrt(q) if possible, but in any case < q413			maxLength := q.bitLen()     // ~= log2 q, or at of least largest possible q of this bit length414			minLength := maxLength >> 1 // ~= log2 sqrt(q)415			for index > 0 && table[index-1].nbits > minLength {416				index-- // desired417			}418			if table[index].nbits >= maxLength && table[index].bbb.cmp(q) >= 0 {419				index--420				if index < 0 {421					panic("internal inconsistency")422				}423			}424 425			// split q into the two digit number (q'*bbb + r) to form independent subblocks426			q, r = q.div(stk, r, q, table[index].bbb)427 428			// convert subblocks and collect results in s[:h] and s[h:]429			h := len(s) - table[index].ndigits430			r.convertWords(stk, s[h:], b, ndigits, bb, table[0:index])431			s = s[:h] // == q.convertWords(stk, s, b, ndigits, bb, table[0:index+1])432		}433	}434 435	// having split any large blocks now process the remaining (small) block iteratively436	i := len(s)437	var r Word438	if b == 10 {439		// hard-coding for 10 here speeds this up by 1.25x (allows for / and % by constants)440		for len(q) > 0 {441			// extract least significant, base bb "digit"442			q, r = q.divW(q, bb)443			for j := 0; j < ndigits && i > 0; j++ {444				i--445				// avoid % computation since r%10 == r - int(r/10)*10;446				// this appears to be faster for BenchmarkString10000Base10447				// and smaller strings (but a bit slower for larger ones)448				t := r / 10449				s[i] = '0' + byte(r-t*10)450				r = t451			}452		}453	} else {454		for len(q) > 0 {455			// extract least significant, base bb "digit"456			q, r = q.divW(q, bb)457			for j := 0; j < ndigits && i > 0; j++ {458				i--459				s[i] = digits[r%b]460				r /= b461			}462		}463	}464 465	// prepend high-order zeros466	for i > 0 { // while need more leading zeros467		i--468		s[i] = '0'469	}470}471 472// Split blocks greater than leafSize Words (or set to 0 to disable recursive conversion)473// Benchmark and configure leafSize using: go test -bench="Leaf"474//475//	8 and 16 effective on 3.0 GHz Xeon "Clovertown" CPU (128 byte cache lines)476//	8 and 16 effective on 2.66 GHz Core 2 Duo "Penryn" CPU477var leafSize int = 8 // number of Word-size binary values treat as a monolithic block478 479type divisor struct {480	bbb     nat // divisor481	nbits   int // bit length of divisor (discounting leading zeros) ~= log2(bbb)482	ndigits int // digit length of divisor in terms of output base digits483}484 485var cacheBase10 struct {486	sync.Mutex487	table [64]divisor // cached divisors for base 10488}489 490// expWW computes x**y491func (z nat) expWW(stk *stack, x, y Word) nat {492	return z.expNN(stk, nat(nil).setWord(x), nat(nil).setWord(y), nil, false)493}494 495// construct table of powers of bb*leafSize to use in subdivisions.496func divisors(stk *stack, m int, b Word, ndigits int, bb Word) []divisor {497	// only compute table when recursive conversion is enabled and x is large498	if leafSize == 0 || m <= leafSize {499		return nil500	}501 502	// determine k where (bb**leafSize)**(2**k) >= sqrt(x)503	k := 1504	for words := leafSize; words < m>>1 && k < len(cacheBase10.table); words <<= 1 {505		k++506	}507 508	// reuse and extend existing table of divisors or create new table as appropriate509	var table []divisor // for b == 10, table overlaps with cacheBase10.table510	if b == 10 {511		cacheBase10.Lock()512		table = cacheBase10.table[0:k] // reuse old table for this conversion513	} else {514		table = make([]divisor, k) // create new table for this conversion515	}516 517	// extend table518	if table[k-1].ndigits == 0 {519		// add new entries as needed520		var larger nat521		for i := 0; i < k; i++ {522			if table[i].ndigits == 0 {523				if i == 0 {524					table[0].bbb = nat(nil).expWW(stk, bb, Word(leafSize))525					table[0].ndigits = ndigits * leafSize526				} else {527					table[i].bbb = nat(nil).sqr(stk, table[i-1].bbb)528					table[i].ndigits = 2 * table[i-1].ndigits529				}530 531				// optimization: exploit aggregated extra bits in macro blocks532				larger = nat(nil).set(table[i].bbb)533				for mulAddVWW(larger, larger, b, 0) == 0 {534					table[i].bbb = table[i].bbb.set(larger)535					table[i].ndigits++536				}537 538				table[i].nbits = table[i].bbb.bitLen()539			}540		}541	}542 543	if b == 10 {544		cacheBase10.Unlock()545	}546 547	return table548}549