← Back to branch summary

~john-koepi/ubuntu/trusty/golang/default

« back to all changes in this revision

Viewing changes to src/pkg/strconv/atof.go

  • Committer: Bazaar Package Importer
  • Author(s): Ondřej Surý
  • Date: 2011-04-20 17:36:48 UTC
  • Revision ID: james.westby@ubuntu.com-20110420173648-ifergoxyrm832trd
Tags: upstream-2011.03.07.1
Import upstream version 2011.03.07.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
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
// 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
}