...
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
     6	
     7	// decimal to binary floating point conversion.
     8	// Algorithm:
     9	//   1) Store input in multiprecision decimal.
    10	//   2) Multiply/divide decimal by powers of two until in range [0.5, 1)
    11	//   3) Multiply by 2^precision and round to get mantissa.
    12	
    13	import "math"
    14	
    15	var optimize = true // can change for testing
    16	
    17	func equalIgnoreCase(s1, s2 string) bool {
    18		if len(s1) != len(s2) {
    19			return false
    20		}
    21		for i := 0; i < len(s1); i++ {
    22			c1 := s1[i]
    23			if 'A' <= c1 && c1 <= 'Z' {
    24				c1 += 'a' - 'A'
    25			}
    26			c2 := s2[i]
    27			if 'A' <= c2 && c2 <= 'Z' {
    28				c2 += 'a' - 'A'
    29			}
    30			if c1 != c2 {
    31				return false
    32			}
    33		}
    34		return true
    35	}
    36	
    37	func special(s string) (f float64, ok bool) {
    38		if len(s) == 0 {
    39			return
    40		}
    41		switch s[0] {
    42		default:
    43			return
    44		case '+':
    45			if equalIgnoreCase(s, "+inf") || equalIgnoreCase(s, "+infinity") {
    46				return math.Inf(1), true
    47			}
    48		case '-':
    49			if equalIgnoreCase(s, "-inf") || equalIgnoreCase(s, "-infinity") {
    50				return math.Inf(-1), true
    51			}
    52		case 'n', 'N':
    53			if equalIgnoreCase(s, "nan") {
    54				return math.NaN(), true
    55			}
    56		case 'i', 'I':
    57			if equalIgnoreCase(s, "inf") || equalIgnoreCase(s, "infinity") {
    58				return math.Inf(1), true
    59			}
    60		}
    61		return
    62	}
    63	
    64	func (b *decimal) set(s string) (ok bool) {
    65		i := 0
    66		b.neg = false
    67		b.trunc = false
    68	
    69		// optional sign
    70		if i >= len(s) {
    71			return
    72		}
    73		switch {
    74		case s[i] == '+':
    75			i++
    76		case s[i] == '-':
    77			b.neg = true
    78			i++
    79		}
    80	
    81		// digits
    82		sawdot := false
    83		sawdigits := false
    84		for ; i < len(s); i++ {
    85			switch {
    86			case s[i] == '.':
    87				if sawdot {
    88					return
    89				}
    90				sawdot = true
    91				b.dp = b.nd
    92				continue
    93	
    94			case '0' <= s[i] && s[i] <= '9':
    95				sawdigits = true
    96				if s[i] == '0' && b.nd == 0 { // ignore leading zeros
    97					b.dp--
    98					continue
    99				}
   100				if b.nd < len(b.d) {
   101					b.d[b.nd] = s[i]
   102					b.nd++
   103				} else if s[i] != '0' {
   104					b.trunc = true
   105				}
   106				continue
   107			}
   108			break
   109		}
   110		if !sawdigits {
   111			return
   112		}
   113		if !sawdot {
   114			b.dp = b.nd
   115		}
   116	
   117		// optional exponent moves decimal point.
   118		// if we read a very large, very long number,
   119		// just be sure to move the decimal point by
   120		// a lot (say, 100000).  it doesn't matter if it's
   121		// not the exact number.
   122		if i < len(s) && (s[i] == 'e' || s[i] == 'E') {
   123			i++
   124			if i >= len(s) {
   125				return
   126			}
   127			esign := 1
   128			if s[i] == '+' {
   129				i++
   130			} else if s[i] == '-' {
   131				i++
   132				esign = -1
   133			}
   134			if i >= len(s) || s[i] < '0' || s[i] > '9' {
   135				return
   136			}
   137			e := 0
   138			for ; i < len(s) && '0' <= s[i] && s[i] <= '9'; i++ {
   139				if e < 10000 {
   140					e = e*10 + int(s[i]) - '0'
   141				}
   142			}
   143			b.dp += e * esign
   144		}
   145	
   146		if i != len(s) {
   147			return
   148		}
   149	
   150		ok = true
   151		return
   152	}
   153	
   154	// readFloat reads a decimal mantissa and exponent from a float
   155	// string representation. It sets ok to false if the number could
   156	// not fit return types or is invalid.
   157	func readFloat(s string) (mantissa uint64, exp int, neg, trunc, ok bool) {
   158		const uint64digits = 19
   159		i := 0
   160	
   161		// optional sign
   162		if i >= len(s) {
   163			return
   164		}
   165		switch {
   166		case s[i] == '+':
   167			i++
   168		case s[i] == '-':
   169			neg = true
   170			i++
   171		}
   172	
   173		// digits
   174		sawdot := false
   175		sawdigits := false
   176		nd := 0
   177		ndMant := 0
   178		dp := 0
   179		for ; i < len(s); i++ {
   180			switch c := s[i]; true {
   181			case c == '.':
   182				if sawdot {
   183					return
   184				}
   185				sawdot = true
   186				dp = nd
   187				continue
   188	
   189			case '0' <= c && c <= '9':
   190				sawdigits = true
   191				if c == '0' && nd == 0 { // ignore leading zeros
   192					dp--
   193					continue
   194				}
   195				nd++
   196				if ndMant < uint64digits {
   197					mantissa *= 10
   198					mantissa += uint64(c - '0')
   199					ndMant++
   200				} else if s[i] != '0' {
   201					trunc = true
   202				}
   203				continue
   204			}
   205			break
   206		}
   207		if !sawdigits {
   208			return
   209		}
   210		if !sawdot {
   211			dp = nd
   212		}
   213	
   214		// optional exponent moves decimal point.
   215		// if we read a very large, very long number,
   216		// just be sure to move the decimal point by
   217		// a lot (say, 100000).  it doesn't matter if it's
   218		// not the exact number.
   219		if i < len(s) && (s[i] == 'e' || s[i] == 'E') {
   220			i++
   221			if i >= len(s) {
   222				return
   223			}
   224			esign := 1
   225			if s[i] == '+' {
   226				i++
   227			} else if s[i] == '-' {
   228				i++
   229				esign = -1
   230			}
   231			if i >= len(s) || s[i] < '0' || s[i] > '9' {
   232				return
   233			}
   234			e := 0
   235			for ; i < len(s) && '0' <= s[i] && s[i] <= '9'; i++ {
   236				if e < 10000 {
   237					e = e*10 + int(s[i]) - '0'
   238				}
   239			}
   240			dp += e * esign
   241		}
   242	
   243		if i != len(s) {
   244			return
   245		}
   246	
   247		if mantissa != 0 {
   248			exp = dp - ndMant
   249		}
   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) (float64, error) {
   534		if bitSize == 32 {
   535			f, err := atof32(s)
   536			return float64(f), err
   537		}
   538		return atof64(s)
   539	}
   540	

View as plain text