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