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