Source file src/pkg/strconv/atof.go
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 implements conversions to and from string representations 6 // of basic data types. 7 package strconv 8 9 // decimal to binary floating point conversion. 10 // Algorithm: 11 // 1) Store input in multiprecision decimal. 12 // 2) Multiply/divide decimal by powers of two until in range [0.5, 1) 13 // 3) Multiply by 2^precision and round to get mantissa. 14 15 import "math" 16 17 var optimize = true // can change for testing 18 19 func equalIgnoreCase(s1, s2 string) bool { 20 if len(s1) != len(s2) { 21 return false 22 } 23 for i := 0; i < len(s1); i++ { 24 c1 := s1[i] 25 if 'A' <= c1 && c1 <= 'Z' { 26 c1 += 'a' - 'A' 27 } 28 c2 := s2[i] 29 if 'A' <= c2 && c2 <= 'Z' { 30 c2 += 'a' - 'A' 31 } 32 if c1 != c2 { 33 return false 34 } 35 } 36 return true 37 } 38 39 func special(s string) (f float64, ok bool) { 40 switch { 41 case equalIgnoreCase(s, "nan"): 42 return math.NaN(), true 43 case equalIgnoreCase(s, "-inf"), 44 equalIgnoreCase(s, "-infinity"): 45 return math.Inf(-1), true 46 case equalIgnoreCase(s, "+inf"), 47 equalIgnoreCase(s, "+infinity"), 48 equalIgnoreCase(s, "inf"), 49 equalIgnoreCase(s, "infinity"): 50 return math.Inf(1), true 51 } 52 return 53 } 54 55 func (b *decimal) set(s string) (ok bool) { 56 i := 0 57 b.neg = false 58 b.trunc = false 59 60 // optional sign 61 if i >= len(s) { 62 return 63 } 64 switch { 65 case s[i] == '+': 66 i++ 67 case s[i] == '-': 68 b.neg = true 69 i++ 70 } 71 72 // digits 73 sawdot := false 74 sawdigits := false 75 for ; i < len(s); i++ { 76 switch { 77 case s[i] == '.': 78 if sawdot { 79 return 80 } 81 sawdot = true 82 b.dp = b.nd 83 continue 84 85 case '0' <= s[i] && s[i] <= '9': 86 sawdigits = true 87 if s[i] == '0' && b.nd == 0 { // ignore leading zeros 88 b.dp-- 89 continue 90 } 91 if b.nd < len(b.d) { 92 b.d[b.nd] = s[i] 93 b.nd++ 94 } else if s[i] != '0' { 95 b.trunc = true 96 } 97 continue 98 } 99 break 100 } 101 if !sawdigits { 102 return 103 } 104 if !sawdot { 105 b.dp = b.nd 106 } 107 108 // optional exponent moves decimal point. 109 // if we read a very large, very long number, 110 // just be sure to move the decimal point by 111 // a lot (say, 100000). it doesn't matter if it's 112 // not the exact number. 113 if i < len(s) && (s[i] == 'e' || s[i] == 'E') { 114 i++ 115 if i >= len(s) { 116 return 117 } 118 esign := 1 119 if s[i] == '+' { 120 i++ 121 } else if s[i] == '-' { 122 i++ 123 esign = -1 124 } 125 if i >= len(s) || s[i] < '0' || s[i] > '9' { 126 return 127 } 128 e := 0 129 for ; i < len(s) && '0' <= s[i] && s[i] <= '9'; i++ { 130 if e < 10000 { 131 e = e*10 + int(s[i]) - '0' 132 } 133 } 134 b.dp += e * esign 135 } 136 137 if i != len(s) { 138 return 139 } 140 141 ok = true 142 return 143 } 144 145 // decimal power of ten to binary power of two. 146 var powtab = []int{1, 3, 6, 9, 13, 16, 19, 23, 26} 147 148 func (d *decimal) floatBits(flt *floatInfo) (b uint64, overflow bool) { 149 var exp int 150 var mant uint64 151 152 // Zero is always a special case. 153 if d.nd == 0 { 154 mant = 0 155 exp = flt.bias 156 goto out 157 } 158 159 // Obvious overflow/underflow. 160 // These bounds are for 64-bit floats. 161 // Will have to change if we want to support 80-bit floats in the future. 162 if d.dp > 310 { 163 goto overflow 164 } 165 if d.dp < -330 { 166 // zero 167 mant = 0 168 exp = flt.bias 169 goto out 170 } 171 172 // Scale by powers of two until in range [0.5, 1.0) 173 exp = 0 174 for d.dp > 0 { 175 var n int 176 if d.dp >= len(powtab) { 177 n = 27 178 } else { 179 n = powtab[d.dp] 180 } 181 d.Shift(-n) 182 exp += n 183 } 184 for d.dp < 0 || d.dp == 0 && d.d[0] < '5' { 185 var n int 186 if -d.dp >= len(powtab) { 187 n = 27 188 } else { 189 n = powtab[-d.dp] 190 } 191 d.Shift(n) 192 exp -= n 193 } 194 195 // Our range is [0.5,1) but floating point range is [1,2). 196 exp-- 197 198 // Minimum representable exponent is flt.bias+1. 199 // If the exponent is smaller, move it up and 200 // adjust d accordingly. 201 if exp < flt.bias+1 { 202 n := flt.bias + 1 - exp 203 d.Shift(-n) 204 exp += n 205 } 206 207 if exp-flt.bias >= 1<<flt.expbits-1 { 208 goto overflow 209 } 210 211 // Extract 1+flt.mantbits bits. 212 d.Shift(int(1 + flt.mantbits)) 213 mant = d.RoundedInteger() 214 215 // Rounding might have added a bit; shift down. 216 if mant == 2<<flt.mantbits { 217 mant >>= 1 218 exp++ 219 if exp-flt.bias >= 1<<flt.expbits-1 { 220 goto overflow 221 } 222 } 223 224 // Denormalized? 225 if mant&(1<<flt.mantbits) == 0 { 226 exp = flt.bias 227 } 228 goto out 229 230 overflow: 231 // ±Inf 232 mant = 0 233 exp = 1<<flt.expbits - 1 + flt.bias 234 overflow = true 235 236 out: 237 // Assemble bits. 238 bits := mant & (uint64(1)<<flt.mantbits - 1) 239 bits |= uint64((exp-flt.bias)&(1<<flt.expbits-1)) << flt.mantbits 240 if d.neg { 241 bits |= 1 << flt.mantbits << flt.expbits 242 } 243 return bits, overflow 244 } 245 246 // Compute exact floating-point integer from d's digits. 247 // Caller is responsible for avoiding overflow. 248 func (d *decimal) atof64int() float64 { 249 f := 0.0 250 for i := 0; i < d.nd; i++ { 251 f = f*10 + float64(d.d[i]-'0') 252 } 253 if d.neg { 254 f = -f 255 } 256 return f 257 } 258 259 func (d *decimal) atof32int() float32 { 260 f := float32(0) 261 for i := 0; i < d.nd; i++ { 262 f = f*10 + float32(d.d[i]-'0') 263 } 264 if d.neg { 265 f = -f 266 } 267 return f 268 } 269 270 // Reads a uint64 decimal mantissa, which might be truncated. 271 func (d *decimal) atou64() (mant uint64, digits int) { 272 const uint64digits = 19 273 for i, c := range d.d[:d.nd] { 274 if i == uint64digits { 275 return mant, i 276 } 277 mant = 10*mant + uint64(c-'0') 278 } 279 return mant, d.nd 280 } 281 282 // Exact powers of 10. 283 var float64pow10 = []float64{ 284 1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 285 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19, 286 1e20, 1e21, 1e22, 287 } 288 var float32pow10 = []float32{1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10} 289 290 // If possible to convert decimal d to 64-bit float f exactly, 291 // entirely in floating-point math, do so, avoiding the expense of decimalToFloatBits. 292 // Three common cases: 293 // value is exact integer 294 // value is exact integer * exact power of ten 295 // value is exact integer / exact power of ten 296 // These all produce potentially inexact but correctly rounded answers. 297 func (d *decimal) atof64() (f float64, ok bool) { 298 // Exact integers are <= 10^15. 299 // Exact powers of ten are <= 10^22. 300 if d.nd > 15 { 301 return 302 } 303 switch { 304 case d.dp == d.nd: // int 305 f := d.atof64int() 306 return f, true 307 308 case d.dp > d.nd && d.dp <= 15+22: // int * 10^k 309 f := d.atof64int() 310 k := d.dp - d.nd 311 // If exponent is big but number of digits is not, 312 // can move a few zeros into the integer part. 313 if k > 22 { 314 f *= float64pow10[k-22] 315 k = 22 316 } 317 return f * float64pow10[k], true 318 319 case d.dp < d.nd && d.nd-d.dp <= 22: // int / 10^k 320 f := d.atof64int() 321 return f / float64pow10[d.nd-d.dp], true 322 } 323 return 324 } 325 326 // If possible to convert decimal d to 32-bit float f exactly, 327 // entirely in floating-point math, do so, avoiding the machinery above. 328 func (d *decimal) atof32() (f float32, ok bool) { 329 // Exact integers are <= 10^7. 330 // Exact powers of ten are <= 10^10. 331 if d.nd > 7 { 332 return 333 } 334 switch { 335 case d.dp == d.nd: // int 336 f := d.atof32int() 337 return f, true 338 339 case d.dp > d.nd && d.dp <= 7+10: // int * 10^k 340 f := d.atof32int() 341 k := d.dp - d.nd 342 // If exponent is big but number of digits is not, 343 // can move a few zeros into the integer part. 344 if k > 10 { 345 f *= float32pow10[k-10] 346 k = 10 347 } 348 return f * float32pow10[k], true 349 350 case d.dp < d.nd && d.nd-d.dp <= 10: // int / 10^k 351 f := d.atof32int() 352 return f / float32pow10[d.nd-d.dp], true 353 } 354 return 355 } 356 357 const fnParseFloat = "ParseFloat" 358 359 func atof32(s string) (f float32, err error) { 360 if val, ok := special(s); ok { 361 return float32(val), nil 362 } 363 364 var d decimal 365 if !d.set(s) { 366 return 0, syntaxError(fnParseFloat, s) 367 } 368 if optimize { 369 if f, ok := d.atof32(); ok { 370 return f, nil 371 } 372 } 373 b, ovf := d.floatBits(&float32info) 374 f = math.Float32frombits(uint32(b)) 375 if ovf { 376 err = rangeError(fnParseFloat, s) 377 } 378 return f, err 379 } 380 381 func atof64(s string) (f float64, err error) { 382 if val, ok := special(s); ok { 383 return val, nil 384 } 385 386 var d decimal 387 if !d.set(s) { 388 return 0, syntaxError(fnParseFloat, s) 389 } 390 if optimize { 391 if f, ok := d.atof64(); ok { 392 return f, nil 393 } 394 395 // Try another fast path. 396 ext := new(extFloat) 397 if ok := ext.AssignDecimal(&d); ok { 398 b, ovf := ext.floatBits() 399 f = math.Float64frombits(b) 400 if ovf { 401 err = rangeError(fnParseFloat, s) 402 } 403 return f, err 404 } 405 } 406 b, ovf := d.floatBits(&float64info) 407 f = math.Float64frombits(b) 408 if ovf { 409 err = rangeError(fnParseFloat, s) 410 } 411 return f, err 412 } 413 414 // ParseFloat converts the string s to a floating-point number 415 // with the precision specified by bitSize: 32 for float32, or 64 for float64. 416 // When bitSize=32, the result still has type float64, but it will be 417 // convertible to float32 without changing its value. 418 // 419 // If s is well-formed and near a valid floating point number, 420 // ParseFloat returns the nearest floating point number rounded 421 // using IEEE754 unbiased rounding. 422 // 423 // The errors that ParseFloat returns have concrete type *NumError 424 // and include err.Num = s. 425 // 426 // If s is not syntactically well-formed, ParseFloat returns err.Error = ErrSyntax. 427 // 428 // If s is syntactically well-formed but is more than 1/2 ULP 429 // away from the largest floating point number of the given size, 430 // ParseFloat returns f = ±Inf, err.Error = ErrRange. 431 func ParseFloat(s string, bitSize int) (f float64, err error) { 432 if bitSize == 32 { 433 f1, err1 := atof32(s) 434 return float64(f1), err1 435 } 436 f1, err1 := atof64(s) 437 return f1, err1 438 }