...
Run Format

Source file src/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		if len(s) == 0 {
    41			return
    42		}
    43		switch s[0] {
    44		default:
    45			return
    46		case '+':
    47			if equalIgnoreCase(s, "+inf") || equalIgnoreCase(s, "+infinity") {
    48				return math.Inf(1), true
    49			}
    50		case '-':
    51			if equalIgnoreCase(s, "-inf") || equalIgnoreCase(s, "-infinity") {
    52				return math.Inf(-1), true
    53			}
    54		case 'n', 'N':
    55			if equalIgnoreCase(s, "nan") {
    56				return math.NaN(), true
    57			}
    58		case 'i', 'I':
    59			if equalIgnoreCase(s, "inf") || equalIgnoreCase(s, "infinity") {
    60				return math.Inf(1), true
    61			}
    62		}
    63		return
    64	}
    65	
    66	func (b *decimal) set(s string) (ok bool) {
    67		i := 0
    68		b.neg = false
    69		b.trunc = false
    70	
    71		// optional sign
    72		if i >= len(s) {
    73			return
    74		}
    75		switch {
    76		case s[i] == '+':
    77			i++
    78		case s[i] == '-':
    79			b.neg = true
    80			i++
    81		}
    82	
    83		// digits
    84		sawdot := false
    85		sawdigits := false
    86		for ; i < len(s); i++ {
    87			switch {
    88			case s[i] == '.':
    89				if sawdot {
    90					return
    91				}
    92				sawdot = true
    93				b.dp = b.nd
    94				continue
    95	
    96			case '0' <= s[i] && s[i] <= '9':
    97				sawdigits = true
    98				if s[i] == '0' && b.nd == 0 { // ignore leading zeros
    99					b.dp--
   100					continue
   101				}
   102				if b.nd < len(b.d) {
   103					b.d[b.nd] = s[i]
   104					b.nd++
   105				} else if s[i] != '0' {
   106					b.trunc = true
   107				}
   108				continue
   109			}
   110			break
   111		}
   112		if !sawdigits {
   113			return
   114		}
   115		if !sawdot {
   116			b.dp = b.nd
   117		}
   118	
   119		// optional exponent moves decimal point.
   120		// if we read a very large, very long number,
   121		// just be sure to move the decimal point by
   122		// a lot (say, 100000).  it doesn't matter if it's
   123		// not the exact number.
   124		if i < len(s) && (s[i] == 'e' || s[i] == 'E') {
   125			i++
   126			if i >= len(s) {
   127				return
   128			}
   129			esign := 1
   130			if s[i] == '+' {
   131				i++
   132			} else if s[i] == '-' {
   133				i++
   134				esign = -1
   135			}
   136			if i >= len(s) || s[i] < '0' || s[i] > '9' {
   137				return
   138			}
   139			e := 0
   140			for ; i < len(s) && '0' <= s[i] && s[i] <= '9'; i++ {
   141				if e < 10000 {
   142					e = e*10 + int(s[i]) - '0'
   143				}
   144			}
   145			b.dp += e * esign
   146		}
   147	
   148		if i != len(s) {
   149			return
   150		}
   151	
   152		ok = true
   153		return
   154	}
   155	
   156	// readFloat reads a decimal mantissa and exponent from a float
   157	// string representation. It sets ok to false if the number could
   158	// not fit return types or is invalid.
   159	func readFloat(s string) (mantissa uint64, exp int, neg, trunc, ok bool) {
   160		const uint64digits = 19
   161		i := 0
   162	
   163		// optional sign
   164		if i >= len(s) {
   165			return
   166		}
   167		switch {
   168		case s[i] == '+':
   169			i++
   170		case s[i] == '-':
   171			neg = true
   172			i++
   173		}
   174	
   175		// digits
   176		sawdot := false
   177		sawdigits := false
   178		nd := 0
   179		ndMant := 0
   180		dp := 0
   181		for ; i < len(s); i++ {
   182			switch c := s[i]; true {
   183			case c == '.':
   184				if sawdot {
   185					return
   186				}
   187				sawdot = true
   188				dp = nd
   189				continue
   190	
   191			case '0' <= c && c <= '9':
   192				sawdigits = true
   193				if c == '0' && nd == 0 { // ignore leading zeros
   194					dp--
   195					continue
   196				}
   197				nd++
   198				if ndMant < uint64digits {
   199					mantissa *= 10
   200					mantissa += uint64(c - '0')
   201					ndMant++
   202				} else if s[i] != '0' {
   203					trunc = true
   204				}
   205				continue
   206			}
   207			break
   208		}
   209		if !sawdigits {
   210			return
   211		}
   212		if !sawdot {
   213			dp = nd
   214		}
   215	
   216		// optional exponent moves decimal point.
   217		// if we read a very large, very long number,
   218		// just be sure to move the decimal point by
   219		// a lot (say, 100000).  it doesn't matter if it's
   220		// not the exact number.
   221		if i < len(s) && (s[i] == 'e' || s[i] == 'E') {
   222			i++
   223			if i >= len(s) {
   224				return
   225			}
   226			esign := 1
   227			if s[i] == '+' {
   228				i++
   229			} else if s[i] == '-' {
   230				i++
   231				esign = -1
   232			}
   233			if i >= len(s) || s[i] < '0' || s[i] > '9' {
   234				return
   235			}
   236			e := 0
   237			for ; i < len(s) && '0' <= s[i] && s[i] <= '9'; i++ {
   238				if e < 10000 {
   239					e = e*10 + int(s[i]) - '0'
   240				}
   241			}
   242			dp += e * esign
   243		}
   244	
   245		if i != len(s) {
   246			return
   247		}
   248	
   249		exp = dp - ndMant
   250		ok = true
   251		return
   252	
   253	}
   254	
   255	// decimal power of ten to binary power of two.
   256	var powtab = []int{1, 3, 6, 9, 13, 16, 19, 23, 26}
   257	
   258	func (d *decimal) floatBits(flt *floatInfo) (b uint64, overflow bool) {
   259		var exp int
   260		var mant uint64
   261	
   262		// Zero is always a special case.
   263		if d.nd == 0 {
   264			mant = 0
   265			exp = flt.bias
   266			goto out
   267		}
   268	
   269		// Obvious overflow/underflow.
   270		// These bounds are for 64-bit floats.
   271		// Will have to change if we want to support 80-bit floats in the future.
   272		if d.dp > 310 {
   273			goto overflow
   274		}
   275		if d.dp < -330 {
   276			// zero
   277			mant = 0
   278			exp = flt.bias
   279			goto out
   280		}
   281	
   282		// Scale by powers of two until in range [0.5, 1.0)
   283		exp = 0
   284		for d.dp > 0 {
   285			var n int
   286			if d.dp >= len(powtab) {
   287				n = 27
   288			} else {
   289				n = powtab[d.dp]
   290			}
   291			d.Shift(-n)
   292			exp += n
   293		}
   294		for d.dp < 0 || d.dp == 0 && d.d[0] < '5' {
   295			var n int
   296			if -d.dp >= len(powtab) {
   297				n = 27
   298			} else {
   299				n = powtab[-d.dp]
   300			}
   301			d.Shift(n)
   302			exp -= n
   303		}
   304	
   305		// Our range is [0.5,1) but floating point range is [1,2).
   306		exp--
   307	
   308		// Minimum representable exponent is flt.bias+1.
   309		// If the exponent is smaller, move it up and
   310		// adjust d accordingly.
   311		if exp < flt.bias+1 {
   312			n := flt.bias + 1 - exp
   313			d.Shift(-n)
   314			exp += n
   315		}
   316	
   317		if exp-flt.bias >= 1<<flt.expbits-1 {
   318			goto overflow
   319		}
   320	
   321		// Extract 1+flt.mantbits bits.
   322		d.Shift(int(1 + flt.mantbits))
   323		mant = d.RoundedInteger()
   324	
   325		// Rounding might have added a bit; shift down.
   326		if mant == 2<<flt.mantbits {
   327			mant >>= 1
   328			exp++
   329			if exp-flt.bias >= 1<<flt.expbits-1 {
   330				goto overflow
   331			}
   332		}
   333	
   334		// Denormalized?
   335		if mant&(1<<flt.mantbits) == 0 {
   336			exp = flt.bias
   337		}
   338		goto out
   339	
   340	overflow:
   341		// ±Inf
   342		mant = 0
   343		exp = 1<<flt.expbits - 1 + flt.bias
   344		overflow = true
   345	
   346	out:
   347		// Assemble bits.
   348		bits := mant & (uint64(1)<<flt.mantbits - 1)
   349		bits |= uint64((exp-flt.bias)&(1<<flt.expbits-1)) << flt.mantbits
   350		if d.neg {
   351			bits |= 1 << flt.mantbits << flt.expbits
   352		}
   353		return bits, overflow
   354	}
   355	
   356	// Exact powers of 10.
   357	var float64pow10 = []float64{
   358		1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9,
   359		1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19,
   360		1e20, 1e21, 1e22,
   361	}
   362	var float32pow10 = []float32{1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10}
   363	
   364	// If possible to convert decimal representation to 64-bit float f exactly,
   365	// entirely in floating-point math, do so, avoiding the expense of decimalToFloatBits.
   366	// Three common cases:
   367	//	value is exact integer
   368	//	value is exact integer * exact power of ten
   369	//	value is exact integer / exact power of ten
   370	// These all produce potentially inexact but correctly rounded answers.
   371	func atof64exact(mantissa uint64, exp int, neg bool) (f float64, ok bool) {
   372		if mantissa>>float64info.mantbits != 0 {
   373			return
   374		}
   375		f = float64(mantissa)
   376		if neg {
   377			f = -f
   378		}
   379		switch {
   380		case exp == 0:
   381			// an integer.
   382			return f, true
   383		// Exact integers are <= 10^15.
   384		// Exact powers of ten are <= 10^22.
   385		case exp > 0 && exp <= 15+22: // int * 10^k
   386			// If exponent is big but number of digits is not,
   387			// can move a few zeros into the integer part.
   388			if exp > 22 {
   389				f *= float64pow10[exp-22]
   390				exp = 22
   391			}
   392			if f > 1e15 || f < -1e15 {
   393				// the exponent was really too large.
   394				return
   395			}
   396			return f * float64pow10[exp], true
   397		case exp < 0 && exp >= -22: // int / 10^k
   398			return f / float64pow10[-exp], true
   399		}
   400		return
   401	}
   402	
   403	// If possible to compute mantissa*10^exp to 32-bit float f exactly,
   404	// entirely in floating-point math, do so, avoiding the machinery above.
   405	func atof32exact(mantissa uint64, exp int, neg bool) (f float32, ok bool) {
   406		if mantissa>>float32info.mantbits != 0 {
   407			return
   408		}
   409		f = float32(mantissa)
   410		if neg {
   411			f = -f
   412		}
   413		switch {
   414		case exp == 0:
   415			return f, true
   416		// Exact integers are <= 10^7.
   417		// Exact powers of ten are <= 10^10.
   418		case exp > 0 && exp <= 7+10: // int * 10^k
   419			// If exponent is big but number of digits is not,
   420			// can move a few zeros into the integer part.
   421			if exp > 10 {
   422				f *= float32pow10[exp-10]
   423				exp = 10
   424			}
   425			if f > 1e7 || f < -1e7 {
   426				// the exponent was really too large.
   427				return
   428			}
   429			return f * float32pow10[exp], true
   430		case exp < 0 && exp >= -10: // int / 10^k
   431			return f / float32pow10[-exp], true
   432		}
   433		return
   434	}
   435	
   436	const fnParseFloat = "ParseFloat"
   437	
   438	func atof32(s string) (f float32, err error) {
   439		if val, ok := special(s); ok {
   440			return float32(val), nil
   441		}
   442	
   443		if optimize {
   444			// Parse mantissa and exponent.
   445			mantissa, exp, neg, trunc, ok := readFloat(s)
   446			if ok {
   447				// Try pure floating-point arithmetic conversion.
   448				if !trunc {
   449					if f, ok := atof32exact(mantissa, exp, neg); ok {
   450						return f, nil
   451					}
   452				}
   453				// Try another fast path.
   454				ext := new(extFloat)
   455				if ok := ext.AssignDecimal(mantissa, exp, neg, trunc, &float32info); ok {
   456					b, ovf := ext.floatBits(&float32info)
   457					f = math.Float32frombits(uint32(b))
   458					if ovf {
   459						err = rangeError(fnParseFloat, s)
   460					}
   461					return f, err
   462				}
   463			}
   464		}
   465		var d decimal
   466		if !d.set(s) {
   467			return 0, syntaxError(fnParseFloat, s)
   468		}
   469		b, ovf := d.floatBits(&float32info)
   470		f = math.Float32frombits(uint32(b))
   471		if ovf {
   472			err = rangeError(fnParseFloat, s)
   473		}
   474		return f, err
   475	}
   476	
   477	func atof64(s string) (f float64, err error) {
   478		if val, ok := special(s); ok {
   479			return val, nil
   480		}
   481	
   482		if optimize {
   483			// Parse mantissa and exponent.
   484			mantissa, exp, neg, trunc, ok := readFloat(s)
   485			if ok {
   486				// Try pure floating-point arithmetic conversion.
   487				if !trunc {
   488					if f, ok := atof64exact(mantissa, exp, neg); ok {
   489						return f, nil
   490					}
   491				}
   492				// Try another fast path.
   493				ext := new(extFloat)
   494				if ok := ext.AssignDecimal(mantissa, exp, neg, trunc, &float64info); ok {
   495					b, ovf := ext.floatBits(&float64info)
   496					f = math.Float64frombits(b)
   497					if ovf {
   498						err = rangeError(fnParseFloat, s)
   499					}
   500					return f, err
   501				}
   502			}
   503		}
   504		var d decimal
   505		if !d.set(s) {
   506			return 0, syntaxError(fnParseFloat, s)
   507		}
   508		b, ovf := d.floatBits(&float64info)
   509		f = math.Float64frombits(b)
   510		if ovf {
   511			err = rangeError(fnParseFloat, s)
   512		}
   513		return f, err
   514	}
   515	
   516	// ParseFloat converts the string s to a floating-point number
   517	// with the precision specified by bitSize: 32 for float32, or 64 for float64.
   518	// When bitSize=32, the result still has type float64, but it will be
   519	// convertible to float32 without changing its value.
   520	//
   521	// If s is well-formed and near a valid floating point number,
   522	// ParseFloat returns the nearest floating point number rounded
   523	// using IEEE754 unbiased rounding.
   524	//
   525	// The errors that ParseFloat returns have concrete type *NumError
   526	// and include err.Num = s.
   527	//
   528	// If s is not syntactically well-formed, ParseFloat returns err.Err = ErrSyntax.
   529	//
   530	// If s is syntactically well-formed but is more than 1/2 ULP
   531	// away from the largest floating point number of the given size,
   532	// ParseFloat returns f = ±Inf, err.Err = ErrRange.
   533	func ParseFloat(s string, bitSize int) (f float64, err error) {
   534		if bitSize == 32 {
   535			f1, err1 := atof32(s)
   536			return float64(f1), err1
   537		}
   538		f1, err1 := atof64(s)
   539		return f1, err1
   540	}
   541	

View as plain text