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