Source file src/pkg/strconv/ftoa.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	// Binary to decimal floating point conversion.
     6	// Algorithm:
     7	//   1) store mantissa in multiprecision decimal
     8	//   2) shift decimal by exponent
     9	//   3) read digits out & format
    10	
    11	package strconv
    12	
    13	import "math"
    14	
    15	// TODO: move elsewhere?
    16	type floatInfo struct {
    17		mantbits uint
    18		expbits  uint
    19		bias     int
    20	}
    21	
    22	var float32info = floatInfo{23, 8, -127}
    23	var float64info = floatInfo{52, 11, -1023}
    24	
    25	// FormatFloat converts the floating-point number f to a string,
    26	// according to the format fmt and precision prec. It rounds the
    27	// result assuming that the original was obtained from a floating-point
    28	// value of bitSize bits (32 for float32, 64 for float64).
    29	//
    30	// The format fmt is one of
    31	// 'b' (-ddddp±ddd, a binary exponent),
    32	// 'e' (-d.dddde±dd, a decimal exponent),
    33	// 'E' (-d.ddddE±dd, a decimal exponent),
    34	// 'f' (-ddd.dddd, no exponent),
    35	// 'g' ('e' for large exponents, 'f' otherwise),
    36	// 'G' ('E' for large exponents, 'f' otherwise),
    37	// 'x' (-0xd.ddddp±ddd, a hexadecimal fraction and binary exponent), or
    38	// 'X' (-0Xd.ddddP±ddd, a hexadecimal fraction and binary exponent).
    39	//
    40	// The precision prec controls the number of digits (excluding the exponent)
    41	// printed by the 'e', 'E', 'f', 'g', 'G', 'x', and 'X' formats.
    42	// For 'e', 'E', 'f', 'x', and 'X', it is the number of digits after the decimal point.
    43	// For 'g' and 'G' it is the maximum number of significant digits (trailing
    44	// zeros are removed).
    45	// The special precision -1 uses the smallest number of digits
    46	// necessary such that ParseFloat will return f exactly.
    47	func FormatFloat(f float64, fmt byte, prec, bitSize int) string {
    48		return string(genericFtoa(make([]byte, 0, max(prec+4, 24)), f, fmt, prec, bitSize))
    49	}
    50	
    51	// AppendFloat appends the string form of the floating-point number f,
    52	// as generated by FormatFloat, to dst and returns the extended buffer.
    53	func AppendFloat(dst []byte, f float64, fmt byte, prec, bitSize int) []byte {
    54		return genericFtoa(dst, f, fmt, prec, bitSize)
    55	}
    56	
    57	func genericFtoa(dst []byte, val float64, fmt byte, prec, bitSize int) []byte {
    58		var bits uint64
    59		var flt *floatInfo
    60		switch bitSize {
    61		case 32:
    62			bits = uint64(math.Float32bits(float32(val)))
    63			flt = &float32info
    64		case 64:
    65			bits = math.Float64bits(val)
    66			flt = &float64info
    67		default:
    68			panic("strconv: illegal AppendFloat/FormatFloat bitSize")
    69		}
    70	
    71		neg := bits>>(flt.expbits+flt.mantbits) != 0
    72		exp := int(bits>>flt.mantbits) & (1<<flt.expbits - 1)
    73		mant := bits & (uint64(1)<<flt.mantbits - 1)
    74	
    75		switch exp {
    76		case 1<<flt.expbits - 1:
    77			// Inf, NaN
    78			var s string
    79			switch {
    80			case mant != 0:
    81				s = "NaN"
    82			case neg:
    83				s = "-Inf"
    84			default:
    85				s = "+Inf"
    86			}
    87			return append(dst, s...)
    88	
    89		case 0:
    90			// denormalized
    91			exp++
    92	
    93		default:
    94			// add implicit top bit
    95			mant |= uint64(1) << flt.mantbits
    96		}
    97		exp += flt.bias
    98	
    99		// Pick off easy binary, hex formats.
   100		if fmt == 'b' {
   101			return fmtB(dst, neg, mant, exp, flt)
   102		}
   103		if fmt == 'x' || fmt == 'X' {
   104			return fmtX(dst, prec, fmt, neg, mant, exp, flt)
   105		}
   106	
   107		if !optimize {
   108			return bigFtoa(dst, prec, fmt, neg, mant, exp, flt)
   109		}
   110	
   111		var digs decimalSlice
   112		ok := false
   113		// Negative precision means "only as much as needed to be exact."
   114		shortest := prec < 0
   115		if shortest {
   116			// Try Grisu3 algorithm.
   117			f := new(extFloat)
   118			lower, upper := f.AssignComputeBounds(mant, exp, neg, flt)
   119			var buf [32]byte
   120			digs.d = buf[:]
   121			ok = f.ShortestDecimal(&digs, &lower, &upper)
   122			if !ok {
   123				return bigFtoa(dst, prec, fmt, neg, mant, exp, flt)
   124			}
   125			// Precision for shortest representation mode.
   126			switch fmt {
   127			case 'e', 'E':
   128				prec = max(digs.nd-1, 0)
   129			case 'f':
   130				prec = max(digs.nd-digs.dp, 0)
   131			case 'g', 'G':
   132				prec = digs.nd
   133			}
   134		} else if fmt != 'f' {
   135			// Fixed number of digits.
   136			digits := prec
   137			switch fmt {
   138			case 'e', 'E':
   139				digits++
   140			case 'g', 'G':
   141				if prec == 0 {
   142					prec = 1
   143				}
   144				digits = prec
   145			}
   146			if digits <= 15 {
   147				// try fast algorithm when the number of digits is reasonable.
   148				var buf [24]byte
   149				digs.d = buf[:]
   150				f := extFloat{mant, exp - int(flt.mantbits), neg}
   151				ok = f.FixedDecimal(&digs, digits)
   152			}
   153		}
   154		if !ok {
   155			return bigFtoa(dst, prec, fmt, neg, mant, exp, flt)
   156		}
   157		return formatDigits(dst, shortest, neg, digs, prec, fmt)
   158	}
   159	
   160	// bigFtoa uses multiprecision computations to format a float.
   161	func bigFtoa(dst []byte, prec int, fmt byte, neg bool, mant uint64, exp int, flt *floatInfo) []byte {
   162		d := new(decimal)
   163		d.Assign(mant)
   164		d.Shift(exp - int(flt.mantbits))
   165		var digs decimalSlice
   166		shortest := prec < 0
   167		if shortest {
   168			roundShortest(d, mant, exp, flt)
   169			digs = decimalSlice{d: d.d[:], nd: d.nd, dp: d.dp}
   170			// Precision for shortest representation mode.
   171			switch fmt {
   172			case 'e', 'E':
   173				prec = digs.nd - 1
   174			case 'f':
   175				prec = max(digs.nd-digs.dp, 0)
   176			case 'g', 'G':
   177				prec = digs.nd
   178			}
   179		} else {
   180			// Round appropriately.
   181			switch fmt {
   182			case 'e', 'E':
   183				d.Round(prec + 1)
   184			case 'f':
   185				d.Round(d.dp + prec)
   186			case 'g', 'G':
   187				if prec == 0 {
   188					prec = 1
   189				}
   190				d.Round(prec)
   191			}
   192			digs = decimalSlice{d: d.d[:], nd: d.nd, dp: d.dp}
   193		}
   194		return formatDigits(dst, shortest, neg, digs, prec, fmt)
   195	}
   196	
   197	func formatDigits(dst []byte, shortest bool, neg bool, digs decimalSlice, prec int, fmt byte) []byte {
   198		switch fmt {
   199		case 'e', 'E':
   200			return fmtE(dst, neg, digs, prec, fmt)
   201		case 'f':
   202			return fmtF(dst, neg, digs, prec)
   203		case 'g', 'G':
   204			// trailing fractional zeros in 'e' form will be trimmed.
   205			eprec := prec
   206			if eprec > digs.nd && digs.nd >= digs.dp {
   207				eprec = digs.nd
   208			}
   209			// %e is used if the exponent from the conversion
   210			// is less than -4 or greater than or equal to the precision.
   211			// if precision was the shortest possible, use precision 6 for this decision.
   212			if shortest {
   213				eprec = 6
   214			}
   215			exp := digs.dp - 1
   216			if exp < -4 || exp >= eprec {
   217				if prec > digs.nd {
   218					prec = digs.nd
   219				}
   220				return fmtE(dst, neg, digs, prec-1, fmt+'e'-'g')
   221			}
   222			if prec > digs.dp {
   223				prec = digs.nd
   224			}
   225			return fmtF(dst, neg, digs, max(prec-digs.dp, 0))
   226		}
   227	
   228		// unknown format
   229		return append(dst, '%', fmt)
   230	}
   231	
   232	// roundShortest rounds d (= mant * 2^exp) to the shortest number of digits
   233	// that will let the original floating point value be precisely reconstructed.
   234	func roundShortest(d *decimal, mant uint64, exp int, flt *floatInfo) {
   235		// If mantissa is zero, the number is zero; stop now.
   236		if mant == 0 {
   237			d.nd = 0
   238			return
   239		}
   240	
   241		// Compute upper and lower such that any decimal number
   242		// between upper and lower (possibly inclusive)
   243		// will round to the original floating point number.
   244	
   245		// We may see at once that the number is already shortest.
   246		//
   247		// Suppose d is not denormal, so that 2^exp <= d < 10^dp.
   248		// The closest shorter number is at least 10^(dp-nd) away.
   249		// The lower/upper bounds computed below are at distance
   250		// at most 2^(exp-mantbits).
   251		//
   252		// So the number is already shortest if 10^(dp-nd) > 2^(exp-mantbits),
   253		// or equivalently log2(10)*(dp-nd) > exp-mantbits.
   254		// It is true if 332/100*(dp-nd) >= exp-mantbits (log2(10) > 3.32).
   255		minexp := flt.bias + 1 // minimum possible exponent
   256		if exp > minexp && 332*(d.dp-d.nd) >= 100*(exp-int(flt.mantbits)) {
   257			// The number is already shortest.
   258			return
   259		}
   260	
   261		// d = mant << (exp - mantbits)
   262		// Next highest floating point number is mant+1 << exp-mantbits.
   263		// Our upper bound is halfway between, mant*2+1 << exp-mantbits-1.
   264		upper := new(decimal)
   265		upper.Assign(mant*2 + 1)
   266		upper.Shift(exp - int(flt.mantbits) - 1)
   267	
   268		// d = mant << (exp - mantbits)
   269		// Next lowest floating point number is mant-1 << exp-mantbits,
   270		// unless mant-1 drops the significant bit and exp is not the minimum exp,
   271		// in which case the next lowest is mant*2-1 << exp-mantbits-1.
   272		// Either way, call it mantlo << explo-mantbits.
   273		// Our lower bound is halfway between, mantlo*2+1 << explo-mantbits-1.
   274		var mantlo uint64
   275		var explo int
   276		if mant > 1<<flt.mantbits || exp == minexp {
   277			mantlo = mant - 1
   278			explo = exp
   279		} else {
   280			mantlo = mant*2 - 1
   281			explo = exp - 1
   282		}
   283		lower := new(decimal)
   284		lower.Assign(mantlo*2 + 1)
   285		lower.Shift(explo - int(flt.mantbits) - 1)
   286	
   287		// The upper and lower bounds are possible outputs only if
   288		// the original mantissa is even, so that IEEE round-to-even
   289		// would round to the original mantissa and not the neighbors.
   290		inclusive := mant%2 == 0
   291	
   292		// As we walk the digits we want to know whether rounding up would fall
   293		// within the upper bound. This is tracked by upperdelta:
   294		//
   295		// If upperdelta == 0, the digits of d and upper are the same so far.
   296		//
   297		// If upperdelta == 1, we saw a difference of 1 between d and upper on a
   298		// previous digit and subsequently only 9s for d and 0s for upper.
   299		// (Thus rounding up may fall outside the bound, if it is exclusive.)
   300		//
   301		// If upperdelta == 2, then the difference is greater than 1
   302		// and we know that rounding up falls within the bound.
   303		var upperdelta uint8
   304	
   305		// Now we can figure out the minimum number of digits required.
   306		// Walk along until d has distinguished itself from upper and lower.
   307		for ui := 0; ; ui++ {
   308			// lower, d, and upper may have the decimal points at different
   309			// places. In this case upper is the longest, so we iterate from
   310			// ui==0 and start li and mi at (possibly) -1.
   311			mi := ui - upper.dp + d.dp
   312			if mi >= d.nd {
   313				break
   314			}
   315			li := ui - upper.dp + lower.dp
   316			l := byte('0') // lower digit
   317			if li >= 0 && li < lower.nd {
   318				l = lower.d[li]
   319			}
   320			m := byte('0') // middle digit
   321			if mi >= 0 {
   322				m = d.d[mi]
   323			}
   324			u := byte('0') // upper digit
   325			if ui < upper.nd {
   326				u = upper.d[ui]
   327			}
   328	
   329			// Okay to round down (truncate) if lower has a different digit
   330			// or if lower is inclusive and is exactly the result of rounding
   331			// down (i.e., and we have reached the final digit of lower).
   332			okdown := l != m || inclusive && li+1 == lower.nd
   333	
   334			switch {
   335			case upperdelta == 0 && m+1 < u:
   336				// Example:
   337				// m = 12345xxx
   338				// u = 12347xxx
   339				upperdelta = 2
   340			case upperdelta == 0 && m != u:
   341				// Example:
   342				// m = 12345xxx
   343				// u = 12346xxx
   344				upperdelta = 1
   345			case upperdelta == 1 && (m != '9' || u != '0'):
   346				// Example:
   347				// m = 1234598x
   348				// u = 1234600x
   349				upperdelta = 2
   350			}
   351			// Okay to round up if upper has a different digit and either upper
   352			// is inclusive or upper is bigger than the result of rounding up.
   353			okup := upperdelta > 0 && (inclusive || upperdelta > 1 || ui+1 < upper.nd)
   354	
   355			// If it's okay to do either, then round to the nearest one.
   356			// If it's okay to do only one, do it.
   357			switch {
   358			case okdown && okup:
   359				d.Round(mi + 1)
   360				return
   361			case okdown:
   362				d.RoundDown(mi + 1)
   363				return
   364			case okup:
   365				d.RoundUp(mi + 1)
   366				return
   367			}
   368		}
   369	}
   370	
   371	type decimalSlice struct {
   372		d      []byte
   373		nd, dp int
   374		neg    bool
   375	}
   376	
   377	// %e: -d.ddddde±dd
   378	func fmtE(dst []byte, neg bool, d decimalSlice, prec int, fmt byte) []byte {
   379		// sign
   380		if neg {
   381			dst = append(dst, '-')
   382		}
   383	
   384		// first digit
   385		ch := byte('0')
   386		if d.nd != 0 {
   387			ch = d.d[0]
   388		}
   389		dst = append(dst, ch)
   390	
   391		// .moredigits
   392		if prec > 0 {
   393			dst = append(dst, '.')
   394			i := 1
   395			m := min(d.nd, prec+1)
   396			if i < m {
   397				dst = append(dst, d.d[i:m]...)
   398				i = m
   399			}
   400			for ; i <= prec; i++ {
   401				dst = append(dst, '0')
   402			}
   403		}
   404	
   405		// e±
   406		dst = append(dst, fmt)
   407		exp := d.dp - 1
   408		if d.nd == 0 { // special case: 0 has exponent 0
   409			exp = 0
   410		}
   411		if exp < 0 {
   412			ch = '-'
   413			exp = -exp
   414		} else {
   415			ch = '+'
   416		}
   417		dst = append(dst, ch)
   418	
   419		// dd or ddd
   420		switch {
   421		case exp < 10:
   422			dst = append(dst, '0', byte(exp)+'0')
   423		case exp < 100:
   424			dst = append(dst, byte(exp/10)+'0', byte(exp%10)+'0')
   425		default:
   426			dst = append(dst, byte(exp/100)+'0', byte(exp/10)%10+'0', byte(exp%10)+'0')
   427		}
   428	
   429		return dst
   430	}
   431	
   432	// %f: -ddddddd.ddddd
   433	func fmtF(dst []byte, neg bool, d decimalSlice, prec int) []byte {
   434		// sign
   435		if neg {
   436			dst = append(dst, '-')
   437		}
   438	
   439		// integer, padded with zeros as needed.
   440		if d.dp > 0 {
   441			m := min(d.nd, d.dp)
   442			dst = append(dst, d.d[:m]...)
   443			for ; m < d.dp; m++ {
   444				dst = append(dst, '0')
   445			}
   446		} else {
   447			dst = append(dst, '0')
   448		}
   449	
   450		// fraction
   451		if prec > 0 {
   452			dst = append(dst, '.')
   453			for i := 0; i < prec; i++ {
   454				ch := byte('0')
   455				if j := d.dp + i; 0 <= j && j < d.nd {
   456					ch = d.d[j]
   457				}
   458				dst = append(dst, ch)
   459			}
   460		}
   461	
   462		return dst
   463	}
   464	
   465	// %b: -ddddddddp±ddd
   466	func fmtB(dst []byte, neg bool, mant uint64, exp int, flt *floatInfo) []byte {
   467		// sign
   468		if neg {
   469			dst = append(dst, '-')
   470		}
   471	
   472		// mantissa
   473		dst, _ = formatBits(dst, mant, 10, false, true)
   474	
   475		// p
   476		dst = append(dst, 'p')
   477	
   478		// ±exponent
   479		exp -= int(flt.mantbits)
   480		if exp >= 0 {
   481			dst = append(dst, '+')
   482		}
   483		dst, _ = formatBits(dst, uint64(exp), 10, exp < 0, true)
   484	
   485		return dst
   486	}
   487	
   488	// %x: -0x1.yyyyyyyyp±ddd or -0x0p+0. (y is hex digit, d is decimal digit)
   489	func fmtX(dst []byte, prec int, fmt byte, neg bool, mant uint64, exp int, flt *floatInfo) []byte {
   490		if mant == 0 {
   491			exp = 0
   492		}
   493	
   494		// Shift digits so leading 1 (if any) is at bit 1<<60.
   495		mant <<= 60 - flt.mantbits
   496		for mant != 0 && mant&(1<<60) == 0 {
   497			mant <<= 1
   498			exp--
   499		}
   500	
   501		// Round if requested.
   502		if prec >= 0 && prec < 15 {
   503			shift := uint(prec * 4)
   504			extra := (mant << shift) & (1<<60 - 1)
   505			mant >>= 60 - shift
   506			if extra|(mant&1) > 1<<59 {
   507				mant++
   508			}
   509			mant <<= 60 - shift
   510			if mant&(1<<61) != 0 {
   511				// Wrapped around.
   512				mant >>= 1
   513				exp++
   514			}
   515		}
   516	
   517		hex := lowerhex
   518		if fmt == 'X' {
   519			hex = upperhex
   520		}
   521	
   522		// sign, 0x, leading digit
   523		if neg {
   524			dst = append(dst, '-')
   525		}
   526		dst = append(dst, '0', fmt, '0'+byte((mant>>60)&1))
   527	
   528		// .fraction
   529		mant <<= 4 // remove leading 0 or 1
   530		if prec < 0 && mant != 0 {
   531			dst = append(dst, '.')
   532			for mant != 0 {
   533				dst = append(dst, hex[(mant>>60)&15])
   534				mant <<= 4
   535			}
   536		} else if prec > 0 {
   537			dst = append(dst, '.')
   538			for i := 0; i < prec; i++ {
   539				dst = append(dst, hex[(mant>>60)&15])
   540				mant <<= 4
   541			}
   542		}
   543	
   544		// p±
   545		ch := byte('P')
   546		if fmt == lower(fmt) {
   547			ch = 'p'
   548		}
   549		dst = append(dst, ch)
   550		if exp < 0 {
   551			ch = '-'
   552			exp = -exp
   553		} else {
   554			ch = '+'
   555		}
   556		dst = append(dst, ch)
   557	
   558		// dd or ddd or dddd
   559		switch {
   560		case exp < 100:
   561			dst = append(dst, byte(exp/10)+'0', byte(exp%10)+'0')
   562		case exp < 1000:
   563			dst = append(dst, byte(exp/100)+'0', byte((exp/10)%10)+'0', byte(exp%10)+'0')
   564		default:
   565			dst = append(dst, byte(exp/1000)+'0', byte(exp/100)%10+'0', byte((exp/10)%10)+'0', byte(exp%10)+'0')
   566		}
   567	
   568		return dst
   569	}
   570	
   571	func min(a, b int) int {
   572		if a < b {
   573			return a
   574		}
   575		return b
   576	}
   577	
   578	func max(a, b int) int {
   579		if a > b {
   580			return a
   581		}
   582		return b
   583	}
   584	

View as plain text