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 // can change 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 if sawdot { 88 return 89 } 90 sawdot = true 91 b.dp = b.nd 92 continue 93 94 case '0' <= s[i] && s[i] <= '9': 95 sawdigits = true 96 if s[i] == '0' && b.nd == 0 { // ignore leading zeros 97 b.dp-- 98 continue 99 } 100 if b.nd < len(b.d) { 101 b.d[b.nd] = s[i] 102 b.nd++ 103 } else if s[i] != '0' { 104 b.trunc = true 105 } 106 continue 107 } 108 break 109 } 110 if !sawdigits { 111 return 112 } 113 if !sawdot { 114 b.dp = b.nd 115 } 116 117 // optional exponent moves decimal point. 118 // if we read a very large, very long number, 119 // just be sure to move the decimal point by 120 // a lot (say, 100000). it doesn't matter if it's 121 // not the exact number. 122 if i < len(s) && (s[i] == 'e' || s[i] == 'E') { 123 i++ 124 if i >= len(s) { 125 return 126 } 127 esign := 1 128 if s[i] == '+' { 129 i++ 130 } else if s[i] == '-' { 131 i++ 132 esign = -1 133 } 134 if i >= len(s) || s[i] < '0' || s[i] > '9' { 135 return 136 } 137 e := 0 138 for ; i < len(s) && '0' <= s[i] && s[i] <= '9'; i++ { 139 if e < 10000 { 140 e = e*10 + int(s[i]) - '0' 141 } 142 } 143 b.dp += e * esign 144 } 145 146 if i != len(s) { 147 return 148 } 149 150 ok = true 151 return 152 } 153 154 // readFloat reads a decimal mantissa and exponent from a float 155 // string representation. It sets ok to false if the number could 156 // not fit return types or is invalid. 157 func readFloat(s string) (mantissa uint64, exp int, neg, trunc, ok bool) { 158 const uint64digits = 19 159 i := 0 160 161 // optional sign 162 if i >= len(s) { 163 return 164 } 165 switch { 166 case s[i] == '+': 167 i++ 168 case s[i] == '-': 169 neg = true 170 i++ 171 } 172 173 // digits 174 sawdot := false 175 sawdigits := false 176 nd := 0 177 ndMant := 0 178 dp := 0 179 for ; i < len(s); i++ { 180 switch c := s[i]; true { 181 case c == '.': 182 if sawdot { 183 return 184 } 185 sawdot = true 186 dp = nd 187 continue 188 189 case '0' <= c && c <= '9': 190 sawdigits = true 191 if c == '0' && nd == 0 { // ignore leading zeros 192 dp-- 193 continue 194 } 195 nd++ 196 if ndMant < uint64digits { 197 mantissa *= 10 198 mantissa += uint64(c - '0') 199 ndMant++ 200 } else if s[i] != '0' { 201 trunc = true 202 } 203 continue 204 } 205 break 206 } 207 if !sawdigits { 208 return 209 } 210 if !sawdot { 211 dp = nd 212 } 213 214 // optional exponent moves decimal point. 215 // if we read a very large, very long number, 216 // just be sure to move the decimal point by 217 // a lot (say, 100000). it doesn't matter if it's 218 // not the exact number. 219 if i < len(s) && (s[i] == 'e' || s[i] == 'E') { 220 i++ 221 if i >= len(s) { 222 return 223 } 224 esign := 1 225 if s[i] == '+' { 226 i++ 227 } else if s[i] == '-' { 228 i++ 229 esign = -1 230 } 231 if i >= len(s) || s[i] < '0' || s[i] > '9' { 232 return 233 } 234 e := 0 235 for ; i < len(s) && '0' <= s[i] && s[i] <= '9'; i++ { 236 if e < 10000 { 237 e = e*10 + int(s[i]) - '0' 238 } 239 } 240 dp += e * esign 241 } 242 243 if i != len(s) { 244 return 245 } 246 247 if mantissa != 0 { 248 exp = dp - ndMant 249 } 250 ok = true 251 return 252 253 } 254 255 // decimal power of ten to binary power of two. 256 var powtab = []int{1, 3, 6, 9, 13, 16, 19, 23, 26} 257 258 func (d *decimal) floatBits(flt *floatInfo) (b uint64, overflow bool) { 259 var exp int 260 var mant uint64 261 262 // Zero is always a special case. 263 if d.nd == 0 { 264 mant = 0 265 exp = flt.bias 266 goto out 267 } 268 269 // Obvious overflow/underflow. 270 // These bounds are for 64-bit floats. 271 // Will have to change if we want to support 80-bit floats in the future. 272 if d.dp > 310 { 273 goto overflow 274 } 275 if d.dp < -330 { 276 // zero 277 mant = 0 278 exp = flt.bias 279 goto out 280 } 281 282 // Scale by powers of two until in range [0.5, 1.0) 283 exp = 0 284 for d.dp > 0 { 285 var n int 286 if d.dp >= len(powtab) { 287 n = 27 288 } else { 289 n = powtab[d.dp] 290 } 291 d.Shift(-n) 292 exp += n 293 } 294 for d.dp < 0 || d.dp == 0 && d.d[0] < '5' { 295 var n int 296 if -d.dp >= len(powtab) { 297 n = 27 298 } else { 299 n = powtab[-d.dp] 300 } 301 d.Shift(n) 302 exp -= n 303 } 304 305 // Our range is [0.5,1) but floating point range is [1,2). 306 exp-- 307 308 // Minimum representable exponent is flt.bias+1. 309 // If the exponent is smaller, move it up and 310 // adjust d accordingly. 311 if exp < flt.bias+1 { 312 n := flt.bias + 1 - exp 313 d.Shift(-n) 314 exp += n 315 } 316 317 if exp-flt.bias >= 1<<flt.expbits-1 { 318 goto overflow 319 } 320 321 // Extract 1+flt.mantbits bits. 322 d.Shift(int(1 + flt.mantbits)) 323 mant = d.RoundedInteger() 324 325 // Rounding might have added a bit; shift down. 326 if mant == 2<<flt.mantbits { 327 mant >>= 1 328 exp++ 329 if exp-flt.bias >= 1<<flt.expbits-1 { 330 goto overflow 331 } 332 } 333 334 // Denormalized? 335 if mant&(1<<flt.mantbits) == 0 { 336 exp = flt.bias 337 } 338 goto out 339 340 overflow: 341 // Inf 342 mant = 0 343 exp = 1<<flt.expbits - 1 + flt.bias 344 overflow = true 345 346 out: 347 // Assemble bits. 348 bits := mant & (uint64(1)<<flt.mantbits - 1) 349 bits |= uint64((exp-flt.bias)&(1<<flt.expbits-1)) << flt.mantbits 350 if d.neg { 351 bits |= 1 << flt.mantbits << flt.expbits 352 } 353 return bits, overflow 354 } 355 356 // Exact powers of 10. 357 var float64pow10 = []float64{ 358 1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 359 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19, 360 1e20, 1e21, 1e22, 361 } 362 var float32pow10 = []float32{1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10} 363 364 // If possible to convert decimal representation to 64-bit float f exactly, 365 // entirely in floating-point math, do so, avoiding the expense of decimalToFloatBits. 366 // Three common cases: 367 // value is exact integer 368 // value is exact integer * exact power of ten 369 // value is exact integer / exact power of ten 370 // These all produce potentially inexact but correctly rounded answers. 371 func atof64exact(mantissa uint64, exp int, neg bool) (f float64, ok bool) { 372 if mantissa>>float64info.mantbits != 0 { 373 return 374 } 375 f = float64(mantissa) 376 if neg { 377 f = -f 378 } 379 switch { 380 case exp == 0: 381 // an integer. 382 return f, true 383 // Exact integers are <= 10^15. 384 // Exact powers of ten are <= 10^22. 385 case exp > 0 && exp <= 15+22: // int * 10^k 386 // If exponent is big but number of digits is not, 387 // can move a few zeros into the integer part. 388 if exp > 22 { 389 f *= float64pow10[exp-22] 390 exp = 22 391 } 392 if f > 1e15 || f < -1e15 { 393 // the exponent was really too large. 394 return 395 } 396 return f * float64pow10[exp], true 397 case exp < 0 && exp >= -22: // int / 10^k 398 return f / float64pow10[-exp], true 399 } 400 return 401 } 402 403 // If possible to compute mantissa*10^exp to 32-bit float f exactly, 404 // entirely in floating-point math, do so, avoiding the machinery above. 405 func atof32exact(mantissa uint64, exp int, neg bool) (f float32, ok bool) { 406 if mantissa>>float32info.mantbits != 0 { 407 return 408 } 409 f = float32(mantissa) 410 if neg { 411 f = -f 412 } 413 switch { 414 case exp == 0: 415 return f, true 416 // Exact integers are <= 10^7. 417 // Exact powers of ten are <= 10^10. 418 case exp > 0 && exp <= 7+10: // int * 10^k 419 // If exponent is big but number of digits is not, 420 // can move a few zeros into the integer part. 421 if exp > 10 { 422 f *= float32pow10[exp-10] 423 exp = 10 424 } 425 if f > 1e7 || f < -1e7 { 426 // the exponent was really too large. 427 return 428 } 429 return f * float32pow10[exp], true 430 case exp < 0 && exp >= -10: // int / 10^k 431 return f / float32pow10[-exp], true 432 } 433 return 434 } 435 436 const fnParseFloat = "ParseFloat" 437 438 func atof32(s string) (f float32, err error) { 439 if val, ok := special(s); ok { 440 return float32(val), nil 441 } 442 443 if optimize { 444 // Parse mantissa and exponent. 445 mantissa, exp, neg, trunc, ok := readFloat(s) 446 if ok { 447 // Try pure floating-point arithmetic conversion. 448 if !trunc { 449 if f, ok := atof32exact(mantissa, exp, neg); ok { 450 return f, nil 451 } 452 } 453 // Try another fast path. 454 ext := new(extFloat) 455 if ok := ext.AssignDecimal(mantissa, exp, neg, trunc, &float32info); ok { 456 b, ovf := ext.floatBits(&float32info) 457 f = math.Float32frombits(uint32(b)) 458 if ovf { 459 err = rangeError(fnParseFloat, s) 460 } 461 return f, err 462 } 463 } 464 } 465 var d decimal 466 if !d.set(s) { 467 return 0, syntaxError(fnParseFloat, s) 468 } 469 b, ovf := d.floatBits(&float32info) 470 f = math.Float32frombits(uint32(b)) 471 if ovf { 472 err = rangeError(fnParseFloat, s) 473 } 474 return f, err 475 } 476 477 func atof64(s string) (f float64, err error) { 478 if val, ok := special(s); ok { 479 return val, nil 480 } 481 482 if optimize { 483 // Parse mantissa and exponent. 484 mantissa, exp, neg, trunc, ok := readFloat(s) 485 if ok { 486 // Try pure floating-point arithmetic conversion. 487 if !trunc { 488 if f, ok := atof64exact(mantissa, exp, neg); ok { 489 return f, nil 490 } 491 } 492 // Try another fast path. 493 ext := new(extFloat) 494 if ok := ext.AssignDecimal(mantissa, exp, neg, trunc, &float64info); ok { 495 b, ovf := ext.floatBits(&float64info) 496 f = math.Float64frombits(b) 497 if ovf { 498 err = rangeError(fnParseFloat, s) 499 } 500 return f, err 501 } 502 } 503 } 504 var d decimal 505 if !d.set(s) { 506 return 0, syntaxError(fnParseFloat, s) 507 } 508 b, ovf := d.floatBits(&float64info) 509 f = math.Float64frombits(b) 510 if ovf { 511 err = rangeError(fnParseFloat, s) 512 } 513 return f, err 514 } 515 516 // ParseFloat converts the string s to a floating-point number 517 // with the precision specified by bitSize: 32 for float32, or 64 for float64. 518 // When bitSize=32, the result still has type float64, but it will be 519 // convertible to float32 without changing its value. 520 // 521 // If s is well-formed and near a valid floating point number, 522 // ParseFloat returns the nearest floating point number rounded 523 // using IEEE754 unbiased rounding. 524 // 525 // The errors that ParseFloat returns have concrete type *NumError 526 // and include err.Num = s. 527 // 528 // If s is not syntactically well-formed, ParseFloat returns err.Err = ErrSyntax. 529 // 530 // If s is syntactically well-formed but is more than 1/2 ULP 531 // away from the largest floating point number of the given size, 532 // ParseFloat returns f = Inf, err.Err = ErrRange. 533 func ParseFloat(s string, bitSize int) (float64, error) { 534 if bitSize == 32 { 535 f, err := atof32(s) 536 return float64(f), err 537 } 538 return atof64(s) 539 } 540
