libgo: update to go1.9

[official-gcc.git] / libgo / go / 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 = "0123456789abcdefghijklmnopqrstuvwxyz"

// Note: MaxBase = len(digits), but it must remain a rune constant
//       for API compatibility.

// MaxBase is the largest number base accepted for string conversions.
const MaxBase = 'z' - 'a' + 10 + 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 scans the number corresponding to the longest possible prefix
// from r representing an unsigned number in a given conversion base.
// It returns the corresponding natural number res, the actual base b,
// a digit count, and a read or syntax error err, if any.
//
//      number   = [ prefix ] mantissa .
//      prefix   = "0" [ "x" | "X" | "b" | "B" ] .
//      mantissa = 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, 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
// ``0x'' or ``0X'' selects base 16; if fracOk is not set, the ``0'' prefix
// selects base 8, and a ``0b'' or ``0B'' prefix selects base 2. Otherwise
// the selected base is 10 and no prefix is accepted.
//
// If fracOk is set, an octal prefix is ignored (a leading ``0'' simply
// stands for a zero digit), and 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.
//
// 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 illegal bases
        baseOk := base == 0 ||
                !fracOk && 2 <= base && base <= MaxBase ||
                fracOk && (base == 2 || base == 10 || base == 16)
        if !baseOk {
                panic(fmt.Sprintf("illegal number base %d", base))
        }

        // one char look-ahead
        ch, err := r.ReadByte()
        if err != nil {
                return
        }

        // determine actual base
        b = base
        if base == 0 {
                // actual base is 10 unless there's a base prefix
                b = 10
                if ch == '0' {
                        count = 1
                        switch ch, err = r.ReadByte(); err {
                        case nil:
                                // possibly one of 0x, 0X, 0b, 0B
                                if !fracOk {
                                        b = 8
                                }
                                switch ch {
                                case 'x', 'X':
                                        b = 16
                                case 'b', 'B':
                                        b = 2
                                }
                                switch b {
                                case 16, 2:
                                        count = 0 // prefix is not counted
                                        if ch, err = r.ReadByte(); err != nil {
                                                // io.EOF is also an error in this case
                                                return
                                        }
                                case 8:
                                        count = 0 // prefix is not counted
                                }
                        case io.EOF:
                                // input is "0"
                                res = z[:0]
                                err = nil
                                return
                        default:
                                // read error
                                return
                        }
                }
        }

        // 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 {
                if fracOk && ch == '.' {
                        fracOk = false
                        dp = count
                        // advance
                        if ch, err = r.ReadByte(); err != nil {
                                if err == io.EOF {
                                        err = nil
                                        break
                                }
                                return
                        }
                }

                // 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':
                        d1 = Word(ch - 'A' + 10)
                default:
                        d1 = MaxBase + 1
                }
                if d1 >= b1 {
                        r.UnreadByte() // ch does not belong to number anymore
                        break
                }
                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
                }

                // advance
                if ch, err = r.ReadByte(); err != nil {
                        if err == io.EOF {
                                err = nil
                                break
                        }
                        return
                }
        }

        if count == 0 {
                // no digits found
                switch {
                case base == 0 && b == 8:
                        // there was only the octal prefix 0 (possibly followed by digits > 7);
                        // count as one digit and return base 10, not 8
                        count = 1
                        b = 10
                case base != 0 || b != 8:
                        // there was neither a mantissa digit nor the octal prefix 0
                        err = errors.New("syntax error scanning number")
                }
                return
        }
        // count > 0

        // add remaining digits to result
        if i > 0 {
                z = z.mulAddWW(z, pow(b1, i), di)
        }
        res = z.norm()

        // adjust for fraction, if any
        if dp >= 0 {
                // 0 <= dp <= count > 0
                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).mul(table[i-1].bbb, 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
}