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 "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.shr(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 := make([]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 = make([]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