1 // Copyright 2009 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 package strconv 6 7 // decimal to binary floating point conversion. 8 // Algorithm: 9 // 1) Store input in multiprecision decimal. 10 // 2) Multiply/divide decimal by powers of two until in range [0.5, 1) 11 // 3) Multiply by 2^precision and round to get mantissa. 12 13 import "math" 14 15 var optimize = true // set to false to force slow-path conversions for testing 16 17 func equalIgnoreCase(s1, s2 string) bool { 18 if len(s1) != len(s2) { 19 return false 20 } 21 for i := 0; i < len(s1); i++ { 22 c1 := s1[i] 23 if 'A' <= c1 && c1 <= 'Z' { 24 c1 += 'a' - 'A' 25 } 26 c2 := s2[i] 27 if 'A' <= c2 && c2 <= 'Z' { 28 c2 += 'a' - 'A' 29 } 30 if c1 != c2 { 31 return false 32 } 33 } 34 return true 35 } 36 37 func special(s string) (f float64, ok bool) { 38 if len(s) == 0 { 39 return 40 } 41 switch s[0] { 42 default: 43 return 44 case '+': 45 if equalIgnoreCase(s, "+inf") || equalIgnoreCase(s, "+infinity") { 46 return math.Inf(1), true 47 } 48 case '-': 49 if equalIgnoreCase(s, "-inf") || equalIgnoreCase(s, "-infinity") { 50 return math.Inf(-1), true 51 } 52 case 'n', 'N': 53 if equalIgnoreCase(s, "nan") { 54 return math.NaN(), true 55 } 56 case 'i', 'I': 57 if equalIgnoreCase(s, "inf") || equalIgnoreCase(s, "infinity") { 58 return math.Inf(1), true 59 } 60 } 61 return 62 } 63 64 func (b *decimal) set(s string) (ok bool) { 65 i := 0 66 b.neg = false 67 b.trunc = false 68 69 // optional sign 70 if i >= len(s) { 71 return 72 } 73 switch { 74 case s[i] == '+': 75 i++ 76 case s[i] == '-': 77 b.neg = true 78 i++ 79 } 80 81 // digits 82 sawdot := false 83 sawdigits := false 84 for ; i < len(s); i++ { 85 switch { 86 case s[i] == '_': 87 // underscoreOK already called 88 continue 89 case s[i] == '.': 90 if sawdot { 91 return 92 } 93 sawdot = true 94 b.dp = b.nd 95 continue 96 97 case '0' <= s[i] && s[i] <= '9': 98 sawdigits = true 99 if s[i] == '0' && b.nd == 0 { // ignore leading zeros 100 b.dp-- 101 continue 102 } 103 if b.nd < len(b.d) { 104 b.d[b.nd] = s[i] 105 b.nd++ 106 } else if s[i] != '0' { 107 b.trunc = true 108 } 109 continue 110 } 111 break 112 } 113 if !sawdigits { 114 return 115 } 116 if !sawdot { 117 b.dp = b.nd 118 } 119 120 // optional exponent moves decimal point. 121 // if we read a very large, very long number, 122 // just be sure to move the decimal point by 123 // a lot (say, 100000). it doesn't matter if it's 124 // not the exact number. 125 if i < len(s) && lower(s[i]) == 'e' { 126 i++ 127 if i >= len(s) { 128 return 129 } 130 esign := 1 131 if s[i] == '+' { 132 i++ 133 } else if s[i] == '-' { 134 i++ 135 esign = -1 136 } 137 if i >= len(s) || s[i] < '0' || s[i] > '9' { 138 return 139 } 140 e := 0 141 for ; i < len(s) && ('0' <= s[i] && s[i] <= '9' || s[i] == '_'); i++ { 142 if s[i] == '_' { 143 // underscoreOK already called 144 continue 145 } 146 if e < 10000 { 147 e = e*10 + int(s[i]) - '0' 148 } 149 } 150 b.dp += e * esign 151 } 152 153 if i != len(s) { 154 return 155 } 156 157 ok = true 158 return 159 } 160 161 // readFloat reads a decimal mantissa and exponent from a float 162 // string representation. It returns ok==false if the number could 163 // not fit return types or is invalid. 164 func readFloat(s string) (mantissa uint64, exp int, neg, trunc, hex, ok bool) { 165 i := 0 166 167 // optional sign 168 if i >= len(s) { 169 return 170 } 171 switch { 172 case s[i] == '+': 173 i++ 174 case s[i] == '-': 175 neg = true 176 i++ 177 } 178 179 // digits 180 base := uint64(10) 181 maxMantDigits := 19 // 10^19 fits in uint64 182 expChar := byte('e') 183 if i+2 < len(s) && s[i] == '0' && lower(s[i+1]) == 'x' { 184 base = 16 185 maxMantDigits = 16 // 16^16 fits in uint64 186 i += 2 187 expChar = 'p' 188 hex = true 189 } 190 sawdot := false 191 sawdigits := false 192 nd := 0 193 ndMant := 0 194 dp := 0 195 for ; i < len(s); i++ { 196 switch c := s[i]; true { 197 case c == '_': 198 // underscoreOK already called 199 continue 200 201 case c == '.': 202 if sawdot { 203 return 204 } 205 sawdot = true 206 dp = nd 207 continue 208 209 case '0' <= c && c <= '9': 210 sawdigits = true 211 if c == '0' && nd == 0 { // ignore leading zeros 212 dp-- 213 continue 214 } 215 nd++ 216 if ndMant < maxMantDigits { 217 mantissa *= base 218 mantissa += uint64(c - '0') 219 ndMant++ 220 } else if c != '0' { 221 trunc = true 222 } 223 continue 224 225 case base == 16 && 'a' <= lower(c) && lower(c) <= 'f': 226 sawdigits = true 227 nd++ 228 if ndMant < maxMantDigits { 229 mantissa *= 16 230 mantissa += uint64(lower(c) - 'a' + 10) 231 ndMant++ 232 } else { 233 trunc = true 234 } 235 continue 236 } 237 break 238 } 239 if !sawdigits { 240 return 241 } 242 if !sawdot { 243 dp = nd 244 } 245 246 if base == 16 { 247 dp *= 4 248 ndMant *= 4 249 } 250 251 // optional exponent moves decimal point. 252 // if we read a very large, very long number, 253 // just be sure to move the decimal point by 254 // a lot (say, 100000). it doesn't matter if it's 255 // not the exact number. 256 if i < len(s) && lower(s[i]) == expChar { 257 i++ 258 if i >= len(s) { 259 return 260 } 261 esign := 1 262 if s[i] == '+' { 263 i++ 264 } else if s[i] == '-' { 265 i++ 266 esign = -1 267 } 268 if i >= len(s) || s[i] < '0' || s[i] > '9' { 269 return 270 } 271 e := 0 272 for ; i < len(s) && ('0' <= s[i] && s[i] <= '9' || s[i] == '_'); i++ { 273 if s[i] == '_' { 274 // underscoreOK already called 275 continue 276 } 277 if e < 10000 { 278 e = e*10 + int(s[i]) - '0' 279 } 280 } 281 dp += e * esign 282 } else if base == 16 { 283 // Must have exponent. 284 return 285 } 286 287 if i != len(s) { 288 return 289 } 290 291 if mantissa != 0 { 292 exp = dp - ndMant 293 } 294 ok = true 295 return 296 } 297 298 // decimal power of ten to binary power of two. 299 var powtab = []int{1, 3, 6, 9, 13, 16, 19, 23, 26} 300 301 func (d *decimal) floatBits(flt *floatInfo) (b uint64, overflow bool) { 302 var exp int 303 var mant uint64 304 305 // Zero is always a special case. 306 if d.nd == 0 { 307 mant = 0 308 exp = flt.bias 309 goto out 310 } 311 312 // Obvious overflow/underflow. 313 // These bounds are for 64-bit floats. 314 // Will have to change if we want to support 80-bit floats in the future. 315 if d.dp > 310 { 316 goto overflow 317 } 318 if d.dp < -330 { 319 // zero 320 mant = 0 321 exp = flt.bias 322 goto out 323 } 324 325 // Scale by powers of two until in range [0.5, 1.0) 326 exp = 0 327 for d.dp > 0 { 328 var n int 329 if d.dp >= len(powtab) { 330 n = 27 331 } else { 332 n = powtab[d.dp] 333 } 334 d.Shift(-n) 335 exp += n 336 } 337 for d.dp < 0 || d.dp == 0 && d.d[0] < '5' { 338 var n int 339 if -d.dp >= len(powtab) { 340 n = 27 341 } else { 342 n = powtab[-d.dp] 343 } 344 d.Shift(n) 345 exp -= n 346 } 347 348 // Our range is [0.5,1) but floating point range is [1,2). 349 exp-- 350 351 // Minimum representable exponent is flt.bias+1. 352 // If the exponent is smaller, move it up and 353 // adjust d accordingly. 354 if exp < flt.bias+1 { 355 n := flt.bias + 1 - exp 356 d.Shift(-n) 357 exp += n 358 } 359 360 if exp-flt.bias >= 1<<flt.expbits-1 { 361 goto overflow 362 } 363 364 // Extract 1+flt.mantbits bits. 365 d.Shift(int(1 + flt.mantbits)) 366 mant = d.RoundedInteger() 367 368 // Rounding might have added a bit; shift down. 369 if mant == 2<<flt.mantbits { 370 mant >>= 1 371 exp++ 372 if exp-flt.bias >= 1<<flt.expbits-1 { 373 goto overflow 374 } 375 } 376 377 // Denormalized? 378 if mant&(1<<flt.mantbits) == 0 { 379 exp = flt.bias 380 } 381 goto out 382 383 overflow: 384 // ±Inf 385 mant = 0 386 exp = 1<<flt.expbits - 1 + flt.bias 387 overflow = true 388 389 out: 390 // Assemble bits. 391 bits := mant & (uint64(1)<<flt.mantbits - 1) 392 bits |= uint64((exp-flt.bias)&(1<<flt.expbits-1)) << flt.mantbits 393 if d.neg { 394 bits |= 1 << flt.mantbits << flt.expbits 395 } 396 return bits, overflow 397 } 398 399 // Exact powers of 10. 400 var float64pow10 = []float64{ 401 1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 402 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19, 403 1e20, 1e21, 1e22, 404 } 405 var float32pow10 = []float32{1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10} 406 407 // If possible to convert decimal representation to 64-bit float f exactly, 408 // entirely in floating-point math, do so, avoiding the expense of decimalToFloatBits. 409 // Three common cases: 410 // value is exact integer 411 // value is exact integer * exact power of ten 412 // value is exact integer / exact power of ten 413 // These all produce potentially inexact but correctly rounded answers. 414 func atof64exact(mantissa uint64, exp int, neg bool) (f float64, ok bool) { 415 if mantissa>>float64info.mantbits != 0 { 416 return 417 } 418 f = float64(mantissa) 419 if neg { 420 f = -f 421 } 422 switch { 423 case exp == 0: 424 // an integer. 425 return f, true 426 // Exact integers are <= 10^15. 427 // Exact powers of ten are <= 10^22. 428 case exp > 0 && exp <= 15+22: // int * 10^k 429 // If exponent is big but number of digits is not, 430 // can move a few zeros into the integer part. 431 if exp > 22 { 432 f *= float64pow10[exp-22] 433 exp = 22 434 } 435 if f > 1e15 || f < -1e15 { 436 // the exponent was really too large. 437 return 438 } 439 return f * float64pow10[exp], true 440 case exp < 0 && exp >= -22: // int / 10^k 441 return f / float64pow10[-exp], true 442 } 443 return 444 } 445 446 // If possible to compute mantissa*10^exp to 32-bit float f exactly, 447 // entirely in floating-point math, do so, avoiding the machinery above. 448 func atof32exact(mantissa uint64, exp int, neg bool) (f float32, ok bool) { 449 if mantissa>>float32info.mantbits != 0 { 450 return 451 } 452 f = float32(mantissa) 453 if neg { 454 f = -f 455 } 456 switch { 457 case exp == 0: 458 return f, true 459 // Exact integers are <= 10^7. 460 // Exact powers of ten are <= 10^10. 461 case exp > 0 && exp <= 7+10: // int * 10^k 462 // If exponent is big but number of digits is not, 463 // can move a few zeros into the integer part. 464 if exp > 10 { 465 f *= float32pow10[exp-10] 466 exp = 10 467 } 468 if f > 1e7 || f < -1e7 { 469 // the exponent was really too large. 470 return 471 } 472 return f * float32pow10[exp], true 473 case exp < 0 && exp >= -10: // int / 10^k 474 return f / float32pow10[-exp], true 475 } 476 return 477 } 478 479 // atofHex converts the hex floating-point string s 480 // to a rounded float32 or float64 value (depending on flt==&float32info or flt==&float64info) 481 // and returns it as a float64. 482 // The string s has already been parsed into a mantissa, exponent, and sign (neg==true for negative). 483 // If trunc is true, trailing non-zero bits have been omitted from the mantissa. 484 func atofHex(s string, flt *floatInfo, mantissa uint64, exp int, neg, trunc bool) (float64, error) { 485 maxExp := 1<<flt.expbits + flt.bias - 2 486 minExp := flt.bias + 1 487 exp += int(flt.mantbits) // mantissa now implicitly divided by 2^mantbits. 488 489 // Shift mantissa and exponent to bring representation into float range. 490 // Eventually we want a mantissa with a leading 1-bit followed by mantbits other bits. 491 // For rounding, we need two more, where the bottom bit represents 492 // whether that bit or any later bit was non-zero. 493 // (If the mantissa has already lost non-zero bits, trunc is true, 494 // and we OR in a 1 below after shifting left appropriately.) 495 for mantissa != 0 && mantissa>>(flt.mantbits+2) == 0 { 496 mantissa <<= 1 497 exp-- 498 } 499 if trunc { 500 mantissa |= 1 501 } 502 for mantissa>>(1+flt.mantbits+2) != 0 { 503 mantissa = mantissa>>1 | mantissa&1 504 exp++ 505 } 506 507 // If exponent is too negative, 508 // denormalize in hopes of making it representable. 509 // (The -2 is for the rounding bits.) 510 for mantissa > 1 && exp < minExp-2 { 511 mantissa = mantissa>>1 | mantissa&1 512 exp++ 513 } 514 515 // Round using two bottom bits. 516 round := mantissa & 3 517 mantissa >>= 2 518 round |= mantissa & 1 // round to even (round up if mantissa is odd) 519 exp += 2 520 if round == 3 { 521 mantissa++ 522 if mantissa == 1<<(1+flt.mantbits) { 523 mantissa >>= 1 524 exp++ 525 } 526 } 527 528 if mantissa>>flt.mantbits == 0 { // Denormal or zero. 529 exp = flt.bias 530 } 531 var err error 532 if exp > maxExp { // infinity and range error 533 mantissa = 1 << flt.mantbits 534 exp = maxExp + 1 535 err = rangeError(fnParseFloat, s) 536 } 537 538 bits := mantissa & (1<<flt.mantbits - 1) 539 bits |= uint64((exp-flt.bias)&(1<<flt.expbits-1)) << flt.mantbits 540 if neg { 541 bits |= 1 << flt.mantbits << flt.expbits 542 } 543 if flt == &float32info { 544 return float64(math.Float32frombits(uint32(bits))), err 545 } 546 return math.Float64frombits(bits), err 547 } 548 549 const fnParseFloat = "ParseFloat" 550 551 func atof32(s string) (f float32, err error) { 552 if val, ok := special(s); ok { 553 return float32(val), nil 554 } 555 556 mantissa, exp, neg, trunc, hex, ok := readFloat(s) 557 if hex && ok { 558 f, err := atofHex(s, &float32info, mantissa, exp, neg, trunc) 559 return float32(f), err 560 } 561 562 if optimize && ok { 563 // Try pure floating-point arithmetic conversion. 564 if !trunc { 565 if f, ok := atof32exact(mantissa, exp, neg); ok { 566 return f, nil 567 } 568 } 569 // Try another fast path. 570 ext := new(extFloat) 571 if ok := ext.AssignDecimal(mantissa, exp, neg, trunc, &float32info); ok { 572 b, ovf := ext.floatBits(&float32info) 573 f = math.Float32frombits(uint32(b)) 574 if ovf { 575 err = rangeError(fnParseFloat, s) 576 } 577 return f, err 578 } 579 } 580 581 // Slow fallback. 582 var d decimal 583 if !d.set(s) { 584 return 0, syntaxError(fnParseFloat, s) 585 } 586 b, ovf := d.floatBits(&float32info) 587 f = math.Float32frombits(uint32(b)) 588 if ovf { 589 err = rangeError(fnParseFloat, s) 590 } 591 return f, err 592 } 593 594 func atof64(s string) (f float64, err error) { 595 if val, ok := special(s); ok { 596 return val, nil 597 } 598 599 mantissa, exp, neg, trunc, hex, ok := readFloat(s) 600 if hex && ok { 601 return atofHex(s, &float64info, mantissa, exp, neg, trunc) 602 } 603 604 if optimize && ok { 605 // Try pure floating-point arithmetic conversion. 606 if !trunc { 607 if f, ok := atof64exact(mantissa, exp, neg); ok { 608 return f, nil 609 } 610 } 611 // Try another fast path. 612 ext := new(extFloat) 613 if ok := ext.AssignDecimal(mantissa, exp, neg, trunc, &float64info); ok { 614 b, ovf := ext.floatBits(&float64info) 615 f = math.Float64frombits(b) 616 if ovf { 617 err = rangeError(fnParseFloat, s) 618 } 619 return f, err 620 } 621 } 622 623 // Slow fallback. 624 var d decimal 625 if !d.set(s) { 626 return 0, syntaxError(fnParseFloat, s) 627 } 628 b, ovf := d.floatBits(&float64info) 629 f = math.Float64frombits(b) 630 if ovf { 631 err = rangeError(fnParseFloat, s) 632 } 633 return f, err 634 } 635 636 // ParseFloat converts the string s to a floating-point number 637 // with the precision specified by bitSize: 32 for float32, or 64 for float64. 638 // When bitSize=32, the result still has type float64, but it will be 639 // convertible to float32 without changing its value. 640 // 641 // ParseFloat accepts decimal and hexadecimal floating-point number syntax. 642 // If s is well-formed and near a valid floating-point number, 643 // ParseFloat returns the nearest floating-point number rounded 644 // using IEEE754 unbiased rounding. 645 // (Parsing a hexadecimal floating-point value only rounds when 646 // there are more bits in the hexadecimal representation than 647 // will fit in the mantissa.) 648 // 649 // The errors that ParseFloat returns have concrete type *NumError 650 // and include err.Num = s. 651 // 652 // If s is not syntactically well-formed, ParseFloat returns err.Err = ErrSyntax. 653 // 654 // If s is syntactically well-formed but is more than 1/2 ULP 655 // away from the largest floating point number of the given size, 656 // ParseFloat returns f = ±Inf, err.Err = ErrRange. 657 // 658 // ParseFloat recognizes the strings "NaN", "+Inf", and "-Inf" as their 659 // respective special floating point values. It ignores case when matching. 660 func ParseFloat(s string, bitSize int) (float64, error) { 661 if !underscoreOK(s) { 662 return 0, syntaxError(fnParseFloat, s) 663 } 664 if bitSize == 32 { 665 f, err := atof32(s) 666 return float64(f), err 667 } 668 return atof64(s) 669 } 670
View as plain text