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 }