The Go Programming Language

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 (
    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			equalIgnoreCase(s, "-infinity"):
    48			return math.Inf(-1), true
    49		case equalIgnoreCase(s, "+inf"),
    50			equalIgnoreCase(s, "+infinity"),
    51			equalIgnoreCase(s, "inf"),
    52			equalIgnoreCase(s, "infinity"):
    53			return math.Inf(1), true
    54		}
    55		return
    56	}
    57	
    58	// TODO(rsc): Better truncation handling.
    59	func stringToDecimal(s string) (neg bool, d *decimal, trunc bool, ok bool) {
    60		i := 0
    61	
    62		// optional sign
    63		if i >= len(s) {
    64			return
    65		}
    66		switch {
    67		case s[i] == '+':
    68			i++
    69		case s[i] == '-':
    70			neg = true
    71			i++
    72		}
    73	
    74		// digits
    75		b := new(decimal)
    76		sawdot := false
    77		sawdigits := false
    78		for ; i < len(s); i++ {
    79			switch {
    80			case s[i] == '.':
    81				if sawdot {
    82					return
    83				}
    84				sawdot = true
    85				b.dp = b.nd
    86				continue
    87	
    88			case '0' <= s[i] && s[i] <= '9':
    89				sawdigits = true
    90				if s[i] == '0' && b.nd == 0 { // ignore leading zeros
    91					b.dp--
    92					continue
    93				}
    94				b.d[b.nd] = s[i]
    95				b.nd++
    96				continue
    97			}
    98			break
    99		}
   100		if !sawdigits {
   101			return
   102		}
   103		if !sawdot {
   104			b.dp = b.nd
   105		}
   106	
   107		// optional exponent moves decimal point.
   108		// if we read a very large, very long number,
   109		// just be sure to move the decimal point by
   110		// a lot (say, 100000).  it doesn't matter if it's
   111		// not the exact number.
   112		if i < len(s) && (s[i] == 'e' || s[i] == 'E') {
   113			i++
   114			if i >= len(s) {
   115				return
   116			}
   117			esign := 1
   118			if s[i] == '+' {
   119				i++
   120			} else if s[i] == '-' {
   121				i++
   122				esign = -1
   123			}
   124			if i >= len(s) || s[i] < '0' || s[i] > '9' {
   125				return
   126			}
   127			e := 0
   128			for ; i < len(s) && '0' <= s[i] && s[i] <= '9'; i++ {
   129				if e < 10000 {
   130					e = e*10 + int(s[i]) - '0'
   131				}
   132			}
   133			b.dp += e * esign
   134		}
   135	
   136		if i != len(s) {
   137			return
   138		}
   139	
   140		d = b
   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 decimalToFloatBits(neg bool, d *decimal, trunc bool, 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		mant = d.Shift(int(1 + flt.mantbits)).RoundedInteger()
   213	
   214		// Rounding might have added a bit; shift down.
   215		if mant == 2<<flt.mantbits {
   216			mant >>= 1
   217			exp++
   218			if exp-flt.bias >= 1<<flt.expbits-1 {
   219				goto overflow
   220			}
   221		}
   222	
   223		// Denormalized?
   224		if mant&(1<<flt.mantbits) == 0 {
   225			exp = flt.bias
   226		}
   227		goto out
   228	
   229	overflow:
   230		// ±Inf
   231		mant = 0
   232		exp = 1<<flt.expbits - 1 + flt.bias
   233		overflow = true
   234	
   235	out:
   236		// Assemble bits.
   237		bits := mant & (uint64(1)<<flt.mantbits - 1)
   238		bits |= uint64((exp-flt.bias)&(1<<flt.expbits-1)) << flt.mantbits
   239		if neg {
   240			bits |= 1 << flt.mantbits << flt.expbits
   241		}
   242		return bits, overflow
   243	}
   244	
   245	// Compute exact floating-point integer from d's digits.
   246	// Caller is responsible for avoiding overflow.
   247	func decimalAtof64Int(neg bool, d *decimal) float64 {
   248		f := 0.0
   249		for i := 0; i < d.nd; i++ {
   250			f = f*10 + float64(d.d[i]-'0')
   251		}
   252		if neg {
   253			f *= -1 // BUG work around 6g f = -f.
   254		}
   255		return f
   256	}
   257	
   258	func decimalAtof32Int(neg bool, d *decimal) float32 {
   259		f := float32(0)
   260		for i := 0; i < d.nd; i++ {
   261			f = f*10 + float32(d.d[i]-'0')
   262		}
   263		if neg {
   264			f *= -1 // BUG work around 6g f = -f.
   265		}
   266		return f
   267	}
   268	
   269	// Exact powers of 10.
   270	var float64pow10 = []float64{
   271		1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9,
   272		1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19,
   273		1e20, 1e21, 1e22,
   274	}
   275	var float32pow10 = []float32{1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10}
   276	
   277	// If possible to convert decimal d to 64-bit float f exactly,
   278	// entirely in floating-point math, do so, avoiding the expense of decimalToFloatBits.
   279	// Three common cases:
   280	//	value is exact integer
   281	//	value is exact integer * exact power of ten
   282	//	value is exact integer / exact power of ten
   283	// These all produce potentially inexact but correctly rounded answers.
   284	func decimalAtof64(neg bool, d *decimal, trunc bool) (f float64, ok bool) {
   285		// Exact integers are <= 10^15.
   286		// Exact powers of ten are <= 10^22.
   287		if d.nd > 15 {
   288			return
   289		}
   290		switch {
   291		case d.dp == d.nd: // int
   292			f := decimalAtof64Int(neg, d)
   293			return f, true
   294	
   295		case d.dp > d.nd && d.dp <= 15+22: // int * 10^k
   296			f := decimalAtof64Int(neg, d)
   297			k := d.dp - d.nd
   298			// If exponent is big but number of digits is not,
   299			// can move a few zeros into the integer part.
   300			if k > 22 {
   301				f *= float64pow10[k-22]
   302				k = 22
   303			}
   304			return f * float64pow10[k], true
   305	
   306		case d.dp < d.nd && d.nd-d.dp <= 22: // int / 10^k
   307			f := decimalAtof64Int(neg, d)
   308			return f / float64pow10[d.nd-d.dp], true
   309		}
   310		return
   311	}
   312	
   313	// If possible to convert decimal d to 32-bit float f exactly,
   314	// entirely in floating-point math, do so, avoiding the machinery above.
   315	func decimalAtof32(neg bool, d *decimal, trunc bool) (f float32, ok bool) {
   316		// Exact integers are <= 10^7.
   317		// Exact powers of ten are <= 10^10.
   318		if d.nd > 7 {
   319			return
   320		}
   321		switch {
   322		case d.dp == d.nd: // int
   323			f := decimalAtof32Int(neg, d)
   324			return f, true
   325	
   326		case d.dp > d.nd && d.dp <= 7+10: // int * 10^k
   327			f := decimalAtof32Int(neg, d)
   328			k := d.dp - d.nd
   329			// If exponent is big but number of digits is not,
   330			// can move a few zeros into the integer part.
   331			if k > 10 {
   332				f *= float32pow10[k-10]
   333				k = 10
   334			}
   335			return f * float32pow10[k], true
   336	
   337		case d.dp < d.nd && d.nd-d.dp <= 10: // int / 10^k
   338			f := decimalAtof32Int(neg, d)
   339			return f / float32pow10[d.nd-d.dp], true
   340		}
   341		return
   342	}
   343	
   344	// Atof32 converts the string s to a 32-bit floating-point number.
   345	//
   346	// If s is well-formed and near a valid floating point number,
   347	// Atof32 returns the nearest floating point number rounded
   348	// using IEEE754 unbiased rounding.
   349	//
   350	// The errors that Atof32 returns have concrete type *NumError
   351	// and include err.Num = s.
   352	//
   353	// If s is not syntactically well-formed, Atof32 returns err.Error = os.EINVAL.
   354	//
   355	// If s is syntactically well-formed but is more than 1/2 ULP
   356	// away from the largest floating point number of the given size,
   357	// Atof32 returns f = ±Inf, err.Error = os.ERANGE.
   358	func Atof32(s string) (f float32, err os.Error) {
   359		if val, ok := special(s); ok {
   360			return float32(val), nil
   361		}
   362	
   363		neg, d, trunc, ok := stringToDecimal(s)
   364		if !ok {
   365			return 0, &NumError{s, os.EINVAL}
   366		}
   367		if optimize {
   368			if f, ok := decimalAtof32(neg, d, trunc); ok {
   369				return f, nil
   370			}
   371		}
   372		b, ovf := decimalToFloatBits(neg, d, trunc, &float32info)
   373		f = math.Float32frombits(uint32(b))
   374		if ovf {
   375			err = &NumError{s, os.ERANGE}
   376		}
   377		return f, err
   378	}
   379	
   380	// Atof64 converts the string s to a 64-bit floating-point number.
   381	// Except for the type of its result, its definition is the same as that
   382	// of Atof32.
   383	func Atof64(s string) (f float64, err os.Error) {
   384		if val, ok := special(s); ok {
   385			return val, nil
   386		}
   387	
   388		neg, d, trunc, ok := stringToDecimal(s)
   389		if !ok {
   390			return 0, &NumError{s, os.EINVAL}
   391		}
   392		if optimize {
   393			if f, ok := decimalAtof64(neg, d, trunc); ok {
   394				return f, nil
   395			}
   396		}
   397		b, ovf := decimalToFloatBits(neg, d, trunc, &float64info)
   398		f = math.Float64frombits(b)
   399		if ovf {
   400			err = &NumError{s, os.ERANGE}
   401		}
   402		return f, err
   403	}
   404	
   405	// AtofN converts the string s to a 64-bit floating-point number,
   406	// but it rounds the result assuming that it will be stored in a value
   407	// of n bits (32 or 64).
   408	func AtofN(s string, n int) (f float64, err os.Error) {
   409		if n == 32 {
   410			f1, err1 := Atof32(s)
   411			return float64(f1), err1
   412		}
   413		f1, err1 := Atof64(s)
   414		return f1, err1
   415	}

release.r60.3. Except as noted, this content is licensed under a Creative Commons Attribution 3.0 License.