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