...
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		exp = dp - ndMant
   248		ok = true
   249		return
   250	
   251	}
   252	
   253	// decimal power of ten to binary power of two.
   254	var powtab = []int{1, 3, 6, 9, 13, 16, 19, 23, 26}
   255	
   256	func (d *decimal) floatBits(flt *floatInfo) (b uint64, overflow bool) {
   257		var exp int
   258		var mant uint64
   259	
   260		// Zero is always a special case.
   261		if d.nd == 0 {
   262			mant = 0
   263			exp = flt.bias
   264			goto out
   265		}
   266	
   267		// Obvious overflow/underflow.
   268		// These bounds are for 64-bit floats.
   269		// Will have to change if we want to support 80-bit floats in the future.
   270		if d.dp > 310 {
   271			goto overflow
   272		}
   273		if d.dp < -330 {
   274			// zero
   275			mant = 0
   276			exp = flt.bias
   277			goto out
   278		}
   279	
   280		// Scale by powers of two until in range [0.5, 1.0)
   281		exp = 0
   282		for d.dp > 0 {
   283			var n int
   284			if d.dp >= len(powtab) {
   285				n = 27
   286			} else {
   287				n = powtab[d.dp]
   288			}
   289			d.Shift(-n)
   290			exp += n
   291		}
   292		for d.dp < 0 || d.dp == 0 && d.d[0] < '5' {
   293			var n int
   294			if -d.dp >= len(powtab) {
   295				n = 27
   296			} else {
   297				n = powtab[-d.dp]
   298			}
   299			d.Shift(n)
   300			exp -= n
   301		}
   302	
   303		// Our range is [0.5,1) but floating point range is [1,2).
   304		exp--
   305	
   306		// Minimum representable exponent is flt.bias+1.
   307		// If the exponent is smaller, move it up and
   308		// adjust d accordingly.
   309		if exp < flt.bias+1 {
   310			n := flt.bias + 1 - exp
   311			d.Shift(-n)
   312			exp += n
   313		}
   314	
   315		if exp-flt.bias >= 1<<flt.expbits-1 {
   316			goto overflow
   317		}
   318	
   319		// Extract 1+flt.mantbits bits.
   320		d.Shift(int(1 + flt.mantbits))
   321		mant = d.RoundedInteger()
   322	
   323		// Rounding might have added a bit; shift down.
   324		if mant == 2<<flt.mantbits {
   325			mant >>= 1
   326			exp++
   327			if exp-flt.bias >= 1<<flt.expbits-1 {
   328				goto overflow
   329			}
   330		}
   331	
   332		// Denormalized?
   333		if mant&(1<<flt.mantbits) == 0 {
   334			exp = flt.bias
   335		}
   336		goto out
   337	
   338	overflow:
   339		// ±Inf
   340		mant = 0
   341		exp = 1<<flt.expbits - 1 + flt.bias
   342		overflow = true
   343	
   344	out:
   345		// Assemble bits.
   346		bits := mant & (uint64(1)<<flt.mantbits - 1)
   347		bits |= uint64((exp-flt.bias)&(1<<flt.expbits-1)) << flt.mantbits
   348		if d.neg {
   349			bits |= 1 << flt.mantbits << flt.expbits
   350		}
   351		return bits, overflow
   352	}
   353	
   354	// Exact powers of 10.
   355	var float64pow10 = []float64{
   356		1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9,
   357		1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19,
   358		1e20, 1e21, 1e22,
   359	}
   360	var float32pow10 = []float32{1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10}
   361	
   362	// If possible to convert decimal representation to 64-bit float f exactly,
   363	// entirely in floating-point math, do so, avoiding the expense of decimalToFloatBits.
   364	// Three common cases:
   365	//	value is exact integer
   366	//	value is exact integer * exact power of ten
   367	//	value is exact integer / exact power of ten
   368	// These all produce potentially inexact but correctly rounded answers.
   369	func atof64exact(mantissa uint64, exp int, neg bool) (f float64, ok bool) {
   370		if mantissa>>float64info.mantbits != 0 {
   371			return
   372		}
   373		f = float64(mantissa)
   374		if neg {
   375			f = -f
   376		}
   377		switch {
   378		case exp == 0:
   379			// an integer.
   380			return f, true
   381		// Exact integers are <= 10^15.
   382		// Exact powers of ten are <= 10^22.
   383		case exp > 0 && exp <= 15+22: // int * 10^k
   384			// If exponent is big but number of digits is not,
   385			// can move a few zeros into the integer part.
   386			if exp > 22 {
   387				f *= float64pow10[exp-22]
   388				exp = 22
   389			}
   390			if f > 1e15 || f < -1e15 {
   391				// the exponent was really too large.
   392				return
   393			}
   394			return f * float64pow10[exp], true
   395		case exp < 0 && exp >= -22: // int / 10^k
   396			return f / float64pow10[-exp], true
   397		}
   398		return
   399	}
   400	
   401	// If possible to compute mantissa*10^exp to 32-bit float f exactly,
   402	// entirely in floating-point math, do so, avoiding the machinery above.
   403	func atof32exact(mantissa uint64, exp int, neg bool) (f float32, ok bool) {
   404		if mantissa>>float32info.mantbits != 0 {
   405			return
   406		}
   407		f = float32(mantissa)
   408		if neg {
   409			f = -f
   410		}
   411		switch {
   412		case exp == 0:
   413			return f, true
   414		// Exact integers are <= 10^7.
   415		// Exact powers of ten are <= 10^10.
   416		case exp > 0 && exp <= 7+10: // int * 10^k
   417			// If exponent is big but number of digits is not,
   418			// can move a few zeros into the integer part.
   419			if exp > 10 {
   420				f *= float32pow10[exp-10]
   421				exp = 10
   422			}
   423			if f > 1e7 || f < -1e7 {
   424				// the exponent was really too large.
   425				return
   426			}
   427			return f * float32pow10[exp], true
   428		case exp < 0 && exp >= -10: // int / 10^k
   429			return f / float32pow10[-exp], true
   430		}
   431		return
   432	}
   433	
   434	const fnParseFloat = "ParseFloat"
   435	
   436	func atof32(s string) (f float32, err error) {
   437		if val, ok := special(s); ok {
   438			return float32(val), nil
   439		}
   440	
   441		if optimize {
   442			// Parse mantissa and exponent.
   443			mantissa, exp, neg, trunc, ok := readFloat(s)
   444			if ok {
   445				// Try pure floating-point arithmetic conversion.
   446				if !trunc {
   447					if f, ok := atof32exact(mantissa, exp, neg); ok {
   448						return f, nil
   449					}
   450				}
   451				// Try another fast path.
   452				ext := new(extFloat)
   453				if ok := ext.AssignDecimal(mantissa, exp, neg, trunc, &float32info); ok {
   454					b, ovf := ext.floatBits(&float32info)
   455					f = math.Float32frombits(uint32(b))
   456					if ovf {
   457						err = rangeError(fnParseFloat, s)
   458					}
   459					return f, err
   460				}
   461			}
   462		}
   463		var d decimal
   464		if !d.set(s) {
   465			return 0, syntaxError(fnParseFloat, s)
   466		}
   467		b, ovf := d.floatBits(&float32info)
   468		f = math.Float32frombits(uint32(b))
   469		if ovf {
   470			err = rangeError(fnParseFloat, s)
   471		}
   472		return f, err
   473	}
   474	
   475	func atof64(s string) (f float64, err error) {
   476		if val, ok := special(s); ok {
   477			return val, nil
   478		}
   479	
   480		if optimize {
   481			// Parse mantissa and exponent.
   482			mantissa, exp, neg, trunc, ok := readFloat(s)
   483			if ok {
   484				// Try pure floating-point arithmetic conversion.
   485				if !trunc {
   486					if f, ok := atof64exact(mantissa, exp, neg); ok {
   487						return f, nil
   488					}
   489				}
   490				// Try another fast path.
   491				ext := new(extFloat)
   492				if ok := ext.AssignDecimal(mantissa, exp, neg, trunc, &float64info); ok {
   493					b, ovf := ext.floatBits(&float64info)
   494					f = math.Float64frombits(b)
   495					if ovf {
   496						err = rangeError(fnParseFloat, s)
   497					}
   498					return f, err
   499				}
   500			}
   501		}
   502		var d decimal
   503		if !d.set(s) {
   504			return 0, syntaxError(fnParseFloat, s)
   505		}
   506		b, ovf := d.floatBits(&float64info)
   507		f = math.Float64frombits(b)
   508		if ovf {
   509			err = rangeError(fnParseFloat, s)
   510		}
   511		return f, err
   512	}
   513	
   514	// ParseFloat converts the string s to a floating-point number
   515	// with the precision specified by bitSize: 32 for float32, or 64 for float64.
   516	// When bitSize=32, the result still has type float64, but it will be
   517	// convertible to float32 without changing its value.
   518	//
   519	// If s is well-formed and near a valid floating point number,
   520	// ParseFloat returns the nearest floating point number rounded
   521	// using IEEE754 unbiased rounding.
   522	//
   523	// The errors that ParseFloat returns have concrete type *NumError
   524	// and include err.Num = s.
   525	//
   526	// If s is not syntactically well-formed, ParseFloat returns err.Err = ErrSyntax.
   527	//
   528	// If s is syntactically well-formed but is more than 1/2 ULP
   529	// away from the largest floating point number of the given size,
   530	// ParseFloat returns f = ±Inf, err.Err = ErrRange.
   531	func ParseFloat(s string, bitSize int) (f float64, err error) {
   532		if bitSize == 32 {
   533			f1, err1 := atof32(s)
   534			return float64(f1), err1
   535		}
   536		f1, err1 := atof64(s)
   537		return f1, err1
   538	}
   539	

View as plain text