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 "slices"
16 "sync"
17 )
18 19 const digits = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
20 21 // Note: MaxBase = len(digits), but it must remain an untyped rune constant
22 // for API compatibility.
23 24 // MaxBase is the largest number base accepted for string conversions.
25 const MaxBase = 10 + ('z' - 'a' + 1) + ('Z' - 'A' + 1)
26 const 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.
32 func maxPow(b Word) (p Word, n int) {
33 p, n = b, 1 // assuming b <= _M
34 for max := _M / b; p <= max; {
35 // p == b**n && p <= max
36 p *= b
37 n++
38 }
39 // p == b**n && p <= _M
40 return
41 }
42 43 // pow returns x**n for n > 0, and 1 otherwise.
44 func pow(x Word, n int) (p Word) {
45 // n == sum of bi * 2**i, for 0 <= i < imax, and bi is 0 or 1
46 // thus x**n == product of x**(2**i) for all i where bi == 1
47 // (Russian Peasant Method for exponentiation)
48 p = 1
49 for n > 0 {
50 if n&1 != 0 {
51 p *= x
52 }
53 x *= x
54 n >>= 1
55 }
56 return
57 }
58 59 // scan errors
60 var (
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 prefix
66 // 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 base
71 // prefix and an adjacent digit, and between successive digits; such
72 // underscores do not change the value of the number, or the returned
73 // digit count. Incorrect placement of underscores is reported as an
74 // error if there are no other errors. If base != 0, underscores are
75 // not recognized and thus terminate scanning like any other character
76 // 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 between
86 // 2 and MaxBase. If fracOk is set, the base argument must be one of
87 // 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 of
91 // “0b” or “0B” selects base 2, “0o” or “0O” selects base 8, and
92 // “0x” or “0X” selects base 16. If fracOk is false, a “0” prefix
93 // (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; and
98 // 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 digit
103 // values 36 to 61.
104 //
105 // A result digit count > 0 corresponds to the number of (non-prefix) digits
106 // parsed. A digit count <= 0 indicates the presence of a period (if fracOk
107 // 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.
109 func (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 one
119 // of '_', '0' (a digit), or '.' (anything else). A
120 // valid separator '_' may only occur after a digit
121 // and if base == 0.
122 prev := '.'
123 invalSep := false
124 125 // one char look-ahead
126 ch, err := r.ReadByte()
127 128 // Determine actual base.
129 b, prefix := base, 0
130 if base == 0 {
131 // Actual base is 10 unless there's a base prefix.
132 b = 10
133 if err == nil && ch == '0' {
134 prev = '0'
135 count = 1
136 ch, err = r.ReadByte()
137 if err == nil {
138 // possibly one of 0b, 0B, 0o, 0O, 0x, 0X
139 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 counted
153 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's
164 // 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 shift
166 // z up one group and add di to the result.
167 // With more cleverness we could also handle binary bases like 8 and 32
168 // (corresponding to 3-bit and 5-bit chunks) that don't pack nicely into
169 // 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 Word
174 switch b {
175 case 2: // 1 bit per digit
176 n = _W
177 case 4: // 2 bits per digit
178 n = _W / 2
179 case 16: // 4 bits per digit
180 n = _W / 4
181 default:
182 bn, n = maxPow(b1)
183 }
184 di := Word(0) // 0 <= di < b1**i < bn
185 i := 0 // 0 <= i < n
186 dp := -1 // position of decimal point
187 for err == nil {
188 if ch == '.' && fracOk {
189 fracOk = false
190 if prev == '_' {
191 invalSep = true
192 }
193 prev = '.'
194 dp = count
195 } else if ch == '_' && base == 0 {
196 if prev != '0' {
197 invalSep = true
198 }
199 prev = '_'
200 } else {
201 // convert rune into digit value d1
202 var d1 Word
203 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 + 1
216 }
217 if d1 >= b1 {
218 r.UnreadByte() // ch does not belong to number anymore
219 break
220 }
221 prev = '0'
222 count++
223 224 // collect d1 in di
225 di = di*b1 + d1
226 i++
227 228 // if di is "full", add it to the result
229 if i == n {
230 if bn == 0 {
231 z = append(z, di)
232 } else {
233 z = z.mulAddWW(z, bn, di)
234 }
235 di = 0
236 i = 0
237 }
238 }
239 240 ch, err = r.ReadByte()
241 }
242 243 if err == io.EOF {
244 err = nil
245 }
246 247 // other errors take precedence over invalid separators
248 if err == nil && (invalSep || prev == '_') {
249 err = errInvalSep
250 }
251 252 if count == 0 {
253 // no digits found
254 if prefix == '0' {
255 // there was only the octal prefix 0 (possibly followed by separators and digits > 7);
256 // interpret as decimal 0
257 return z[:0], 10, 1, err
258 }
259 err = errNoDigits // fall through; result will be 0
260 }
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 = z
280 281 // adjust count for fraction, if any
282 if dp >= 0 {
283 // 0 <= dp <= count
284 count = dp - count
285 }
286 287 return
288 }
289 290 // utoa converts x to an ASCII representation in the given base;
291 // base must be between 2 and MaxBase, inclusive.
292 func (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.
297 func (x nat) itoa(neg bool, base int) []byte {
298 if base < 2 || base > MaxBase {
299 panic("invalid base")
300 }
301 302 // x == 0
303 if len(x) == 0 {
304 return []byte("0")
305 }
306 // len(x) > 0
307 308 // allocate buffer for conversion
309 i := int(float64(x.bitLen())/math.Log2(float64(base))) + 1 // off by 1 at most
310 if neg {
311 i++
312 }
313 s := []byte{:i}
314 315 // convert power of two and non power of two bases separately
316 if b := Word(base); b == b&-b {
317 // shift is base b digit size in bits
318 shift := uint(bits.TrailingZeros(uint(b))) // shift > 0 because b >= 2
319 mask := Word(1<<shift - 1)
320 w := x[0] // current word
321 nbits := uint(_W) // number of unprocessed bits in w
322 323 // convert less-significant words (include leading zeros)
324 for k := 1; k < len(x); k++ {
325 // convert full digits
326 for nbits >= shift {
327 i--
328 s[i] = digits[w&mask]
329 w >>= shift
330 nbits -= shift
331 }
332 333 // convert any partial leading digit and advance to next word
334 if nbits == 0 {
335 // no partial digit remaining, just advance
336 w = x[k]
337 nbits = _W
338 } else {
339 // partial digit in current word w (== x[k-1]) and next word x[k]
340 w |= x[k] << nbits
341 i--
342 s[i] = digits[w&mask]
343 344 // advance
345 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 >>= shift
355 }
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 subdivisions
364 // 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 convertWords
368 q := nat(nil).set(x)
369 370 // convert q to string s in base b
371 q.convertWords(stk, s, b, ndigits, bb, table)
372 373 // strip leading zeros
374 // (x != 0; thus s must contain at least one non-zero digit
375 // and the loop will terminate)
376 i = 0
377 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 using
392 // repeated nat/Word division.
393 //
394 // The iterative method processes n Words by n divW() calls, each of which visits every Word in the
395 // 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 half
397 // the size of q. Using the iterative method on both halves means 2 * (n/2)(n/2 + 1)/2 divW()'s
398 // plus the expensive long div(). Asymptotically, the ratio is favorable at 1/2 the divW()'s, and
399 // is made better by splitting the subblocks recursively. Best is to split blocks until one more
400 // split would take longer (because of the nat/nat div()) than the twice as many divW()'s of the
401 // iterative approach. This threshold is represented by leafSize. Benchmarking of leafSize in the
402 // range 2..64 shows that values of 8 and 16 work well, with a 4x speedup at medium lengths and
403 // ~30x for 20000 digits. Use nat_test.go's BenchmarkLeafSize tests to optimize leafSize for
404 // specific hardware.
405 func (q nat) convertWords(stk *stack, s []byte, b Word, ndigits int, bb Word, table []divisor) {
406 // split larger blocks recursively
407 if table != nil {
408 // len(q) > leafSize > 0
409 var r nat
410 index := len(table) - 1
411 for len(q) > leafSize {
412 // find divisor close to sqrt(q) if possible, but in any case < q
413 maxLength := q.bitLen() // ~= log2 q, or at of least largest possible q of this bit length
414 minLength := maxLength >> 1 // ~= log2 sqrt(q)
415 for index > 0 && table[index-1].nbits > minLength {
416 index-- // desired
417 }
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 subblocks
426 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].ndigits
430 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 iteratively
436 i := len(s)
437 var r Word
438 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 BenchmarkString10000Base10
447 // and smaller strings (but a bit slower for larger ones)
448 t := r / 10
449 s[i] = '0' + byte(r-t*10)
450 r = t
451 }
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 /= b
461 }
462 }
463 }
464 465 // prepend high-order zeros
466 for i > 0 { // while need more leading zeros
467 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" CPU
477 var leafSize int = 8 // number of Word-size binary values treat as a monolithic block
478 479 type divisor struct {
480 bbb nat // divisor
481 nbits int // bit length of divisor (discounting leading zeros) ~= log2(bbb)
482 ndigits int // digit length of divisor in terms of output base digits
483 }
484 485 var cacheBase10 struct {
486 sync.Mutex
487 table [64]divisor // cached divisors for base 10
488 }
489 490 // expWW computes x**y
491 func (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.
496 func divisors(stk *stack, m int, b Word, ndigits int, bb Word) []divisor {
497 // only compute table when recursive conversion is enabled and x is large
498 if leafSize == 0 || m <= leafSize {
499 return nil
500 }
501 502 // determine k where (bb**leafSize)**(2**k) >= sqrt(x)
503 k := 1
504 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 appropriate
509 var table []divisor // for b == 10, table overlaps with cacheBase10.table
510 if b == 10 {
511 cacheBase10.Lock()
512 table = cacheBase10.table[0:k] // reuse old table for this conversion
513 } else {
514 table = []divisor{:k} // create new table for this conversion
515 }
516 517 // extend table
518 if table[k-1].ndigits == 0 {
519 // add new entries as needed
520 var larger nat
521 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 * leafSize
526 } else {
527 table[i].bbb = nat(nil).sqr(stk, table[i-1].bbb)
528 table[i].ndigits = 2 * table[i-1].ndigits
529 }
530 531 // optimization: exploit aggregated extra bits in macro blocks
532 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 table
548 }
549