````// Copyright 2009 The Go Authors. All rights reserved.`
`// Use of this source code is governed by a BSD-style`
`// license that can be found in the LICENSE file.`

`// Binary to decimal floating point conversion.`
`// Algorithm:`
`//   1) store mantissa in multiprecision decimal`
`//   2) shift decimal by exponent`
`//   3) read digits out & format`

`package strconv`

`import "math"`

`// TODO: move elsewhere?`
`type floatInfo struct {`
`	mantbits uint`
`	expbits  uint`
`	bias     int`
`}`

`var float32info = floatInfo{23, 8, -127}`
`var float64info = floatInfo{52, 11, -1023}`

`// FormatFloat converts the floating-point number f to a string,`
`// according to the format fmt and precision prec. It rounds the`
`// result assuming that the original was obtained from a floating-point`
`// value of bitSize bits (32 for float32, 64 for float64).`
`//`
`// The format fmt is one of`
`// 'b' (-ddddp±ddd, a binary exponent),`
`// 'e' (-d.dddde±dd, a decimal exponent),`
`// 'E' (-d.ddddE±dd, a decimal exponent),`
`// 'f' (-ddd.dddd, no exponent),`
`// 'g' ('e' for large exponents, 'f' otherwise),`
`// 'G' ('E' for large exponents, 'f' otherwise),`
`// 'x' (-0xd.ddddp±ddd, a hexadecimal fraction and binary exponent), or`
`// 'X' (-0Xd.ddddP±ddd, a hexadecimal fraction and binary exponent).`
`//`
`// The precision prec controls the number of digits (excluding the exponent)`
`// printed by the 'e', 'E', 'f', 'g', 'G', 'x', and 'X' formats.`
`// For 'e', 'E', 'f', 'x', and 'X', it is the number of digits after the decimal point.`
`// For 'g' and 'G' it is the maximum number of significant digits (trailing`
`// zeros are removed).`
`// The special precision -1 uses the smallest number of digits`
`// necessary such that ParseFloat will return f exactly.`
`func FormatFloat(f float64, fmt byte, prec, bitSize int) string {`
`	return string(genericFtoa(make([]byte, 0, max(prec+4, 24)), f, fmt, prec, bitSize))`
`}`

`// AppendFloat appends the string form of the floating-point number f,`
`// as generated by FormatFloat, to dst and returns the extended buffer.`
`func AppendFloat(dst []byte, f float64, fmt byte, prec, bitSize int) []byte {`
`	return genericFtoa(dst, f, fmt, prec, bitSize)`
`}`

`func genericFtoa(dst []byte, val float64, fmt byte, prec, bitSize int) []byte {`
`	var bits uint64`
`	var flt *floatInfo`
`	switch bitSize {`
`	case 32:`
`		bits = uint64(math.Float32bits(float32(val)))`
`		flt = &float32info`
`	case 64:`
`		bits = math.Float64bits(val)`
`		flt = &float64info`
`	default:`
`		panic("strconv: illegal AppendFloat/FormatFloat bitSize")`
`	}`

`	neg := bits>>(flt.expbits+flt.mantbits) != 0`
`	exp := int(bits>>flt.mantbits) & (1<<flt.expbits - 1)`
`	mant := bits & (uint64(1)<<flt.mantbits - 1)`

`	switch exp {`
`	case 1<<flt.expbits - 1:`
`		// Inf, NaN`
`		var s string`
`		switch {`
`		case mant != 0:`
`			s = "NaN"`
`		case neg:`
`			s = "-Inf"`
`		default:`
`			s = "+Inf"`
`		}`
`		return append(dst, s...)`

`	case 0:`
`		// denormalized`
`		exp++`

`	default:`
`		// add implicit top bit`
`		mant |= uint64(1) << flt.mantbits`
`	}`
`	exp += flt.bias`

`	// Pick off easy binary, hex formats.`
`	if fmt == 'b' {`
`		return fmtB(dst, neg, mant, exp, flt)`
`	}`
`	if fmt == 'x' || fmt == 'X' {`
`		return fmtX(dst, prec, fmt, neg, mant, exp, flt)`
`	}`

`	if !optimize {`
`		return bigFtoa(dst, prec, fmt, neg, mant, exp, flt)`
`	}`

`	var digs decimalSlice`
`	ok := false`
`	// Negative precision means "only as much as needed to be exact."`
`	shortest := prec < 0`
`	if shortest {`
`		// Use Ryu algorithm.`
`		var buf [32]byte`
`		digs.d = buf[:]`
`		ryuFtoaShortest(&digs, mant, exp-int(flt.mantbits), flt)`
`		ok = true`
`		// Precision for shortest representation mode.`
`		switch fmt {`
`		case 'e', 'E':`
`			prec = max(digs.nd-1, 0)`
`		case 'f':`
`			prec = max(digs.nd-digs.dp, 0)`
`		case 'g', 'G':`
`			prec = digs.nd`
`		}`
`	} else if fmt != 'f' {`
`		// Fixed number of digits.`
`		digits := prec`
`		switch fmt {`
`		case 'e', 'E':`
`			digits++`
`		case 'g', 'G':`
`			if prec == 0 {`
`				prec = 1`
`			}`
`			digits = prec`
`		default:`
`			// Invalid mode.`
`			digits = 1`
`		}`
`		var buf [24]byte`
`		if bitSize == 32 && digits <= 9 {`
`			digs.d = buf[:]`
`			ryuFtoaFixed32(&digs, uint32(mant), exp-int(flt.mantbits), digits)`
`			ok = true`
`		} else if digits <= 18 {`
`			digs.d = buf[:]`
`			ryuFtoaFixed64(&digs, mant, exp-int(flt.mantbits), digits)`
`			ok = true`
`		}`
`	}`
`	if !ok {`
`		return bigFtoa(dst, prec, fmt, neg, mant, exp, flt)`
`	}`
`	return formatDigits(dst, shortest, neg, digs, prec, fmt)`
`}`

`// bigFtoa uses multiprecision computations to format a float.`
`func bigFtoa(dst []byte, prec int, fmt byte, neg bool, mant uint64, exp int, flt *floatInfo) []byte {`
`	d := new(decimal)`
`	d.Assign(mant)`
`	d.Shift(exp - int(flt.mantbits))`
`	var digs decimalSlice`
`	shortest := prec < 0`
`	if shortest {`
`		roundShortest(d, mant, exp, flt)`
`		digs = decimalSlice{d: d.d[:], nd: d.nd, dp: d.dp}`
`		// Precision for shortest representation mode.`
`		switch fmt {`
`		case 'e', 'E':`
`			prec = digs.nd - 1`
`		case 'f':`
`			prec = max(digs.nd-digs.dp, 0)`
`		case 'g', 'G':`
`			prec = digs.nd`
`		}`
`	} else {`
`		// Round appropriately.`
`		switch fmt {`
`		case 'e', 'E':`
`			d.Round(prec + 1)`
`		case 'f':`
`			d.Round(d.dp + prec)`
`		case 'g', 'G':`
`			if prec == 0 {`
`				prec = 1`
`			}`
`			d.Round(prec)`
`		}`
`		digs = decimalSlice{d: d.d[:], nd: d.nd, dp: d.dp}`
`	}`
`	return formatDigits(dst, shortest, neg, digs, prec, fmt)`
`}`

`func formatDigits(dst []byte, shortest bool, neg bool, digs decimalSlice, prec int, fmt byte) []byte {`
`	switch fmt {`
`	case 'e', 'E':`
`		return fmtE(dst, neg, digs, prec, fmt)`
`	case 'f':`
`		return fmtF(dst, neg, digs, prec)`
`	case 'g', 'G':`
`		// trailing fractional zeros in 'e' form will be trimmed.`
`		eprec := prec`
`		if eprec > digs.nd && digs.nd >= digs.dp {`
`			eprec = digs.nd`
`		}`
`		// %e is used if the exponent from the conversion`
`		// is less than -4 or greater than or equal to the precision.`
`		// if precision was the shortest possible, use precision 6 for this decision.`
`		if shortest {`
`			eprec = 6`
`		}`
`		exp := digs.dp - 1`
`		if exp < -4 || exp >= eprec {`
`			if prec > digs.nd {`
`				prec = digs.nd`
`			}`
`			return fmtE(dst, neg, digs, prec-1, fmt+'e'-'g')`
`		}`
`		if prec > digs.dp {`
`			prec = digs.nd`
`		}`
`		return fmtF(dst, neg, digs, max(prec-digs.dp, 0))`
`	}`

`	// unknown format`
`	return append(dst, '%', fmt)`
`}`

`// roundShortest rounds d (= mant * 2^exp) to the shortest number of digits`
`// that will let the original floating point value be precisely reconstructed.`
`func roundShortest(d *decimal, mant uint64, exp int, flt *floatInfo) {`
`	// If mantissa is zero, the number is zero; stop now.`
`	if mant == 0 {`
`		d.nd = 0`
`		return`
`	}`

`	// Compute upper and lower such that any decimal number`
`	// between upper and lower (possibly inclusive)`
`	// will round to the original floating point number.`

`	// We may see at once that the number is already shortest.`
`	//`
`	// Suppose d is not denormal, so that 2^exp <= d < 10^dp.`
`	// The closest shorter number is at least 10^(dp-nd) away.`
`	// The lower/upper bounds computed below are at distance`
`	// at most 2^(exp-mantbits).`
`	//`
`	// So the number is already shortest if 10^(dp-nd) > 2^(exp-mantbits),`
`	// or equivalently log2(10)*(dp-nd) > exp-mantbits.`
`	// It is true if 332/100*(dp-nd) >= exp-mantbits (log2(10) > 3.32).`
`	minexp := flt.bias + 1 // minimum possible exponent`
`	if exp > minexp && 332*(d.dp-d.nd) >= 100*(exp-int(flt.mantbits)) {`
`		// The number is already shortest.`
`		return`
`	}`

`	// d = mant << (exp - mantbits)`
`	// Next highest floating point number is mant+1 << exp-mantbits.`
`	// Our upper bound is halfway between, mant*2+1 << exp-mantbits-1.`
`	upper := new(decimal)`
`	upper.Assign(mant*2 + 1)`
`	upper.Shift(exp - int(flt.mantbits) - 1)`

`	// d = mant << (exp - mantbits)`
`	// Next lowest floating point number is mant-1 << exp-mantbits,`
`	// unless mant-1 drops the significant bit and exp is not the minimum exp,`
`	// in which case the next lowest is mant*2-1 << exp-mantbits-1.`
`	// Either way, call it mantlo << explo-mantbits.`
`	// Our lower bound is halfway between, mantlo*2+1 << explo-mantbits-1.`
`	var mantlo uint64`
`	var explo int`
`	if mant > 1<<flt.mantbits || exp == minexp {`
`		mantlo = mant - 1`
`		explo = exp`
`	} else {`
`		mantlo = mant*2 - 1`
`		explo = exp - 1`
`	}`
`	lower := new(decimal)`
`	lower.Assign(mantlo*2 + 1)`
`	lower.Shift(explo - int(flt.mantbits) - 1)`

`	// The upper and lower bounds are possible outputs only if`
`	// the original mantissa is even, so that IEEE round-to-even`
`	// would round to the original mantissa and not the neighbors.`
`	inclusive := mant%2 == 0`

`	// As we walk the digits we want to know whether rounding up would fall`
`	// within the upper bound. This is tracked by upperdelta:`
`	//`
`	// If upperdelta == 0, the digits of d and upper are the same so far.`
`	//`
`	// If upperdelta == 1, we saw a difference of 1 between d and upper on a`
`	// previous digit and subsequently only 9s for d and 0s for upper.`
`	// (Thus rounding up may fall outside the bound, if it is exclusive.)`
`	//`
`	// If upperdelta == 2, then the difference is greater than 1`
`	// and we know that rounding up falls within the bound.`
`	var upperdelta uint8`

`	// Now we can figure out the minimum number of digits required.`
`	// Walk along until d has distinguished itself from upper and lower.`
`	for ui := 0; ; ui++ {`
`		// lower, d, and upper may have the decimal points at different`
`		// places. In this case upper is the longest, so we iterate from`
`		// ui==0 and start li and mi at (possibly) -1.`
`		mi := ui - upper.dp + d.dp`
`		if mi >= d.nd {`
`			break`
`		}`
`		li := ui - upper.dp + lower.dp`
`		l := byte('0') // lower digit`
`		if li >= 0 && li < lower.nd {`
`			l = lower.d[li]`
`		}`
`		m := byte('0') // middle digit`
`		if mi >= 0 {`
`			m = d.d[mi]`
`		}`
`		u := byte('0') // upper digit`
`		if ui < upper.nd {`
`			u = upper.d[ui]`
`		}`

`		// Okay to round down (truncate) if lower has a different digit`
`		// or if lower is inclusive and is exactly the result of rounding`
`		// down (i.e., and we have reached the final digit of lower).`
`		okdown := l != m || inclusive && li+1 == lower.nd`

`		switch {`
`		case upperdelta == 0 && m+1 < u:`
`			// Example:`
`			// m = 12345xxx`
`			// u = 12347xxx`
`			upperdelta = 2`
`		case upperdelta == 0 && m != u:`
`			// Example:`
`			// m = 12345xxx`
`			// u = 12346xxx`
`			upperdelta = 1`
`		case upperdelta == 1 && (m != '9' || u != '0'):`
`			// Example:`
`			// m = 1234598x`
`			// u = 1234600x`
`			upperdelta = 2`
`		}`
`		// Okay to round up if upper has a different digit and either upper`
`		// is inclusive or upper is bigger than the result of rounding up.`
`		okup := upperdelta > 0 && (inclusive || upperdelta > 1 || ui+1 < upper.nd)`

`		// If it's okay to do either, then round to the nearest one.`
`		// If it's okay to do only one, do it.`
`		switch {`
`		case okdown && okup:`
`			d.Round(mi + 1)`
`			return`
`		case okdown:`
`			d.RoundDown(mi + 1)`
`			return`
`		case okup:`
`			d.RoundUp(mi + 1)`
`			return`
`		}`
`	}`
`}`

`type decimalSlice struct {`
`	d      []byte`
`	nd, dp int`
`}`

`// %e: -d.ddddde±dd`
`func fmtE(dst []byte, neg bool, d decimalSlice, prec int, fmt byte) []byte {`
`	// sign`
`	if neg {`
`		dst = append(dst, '-')`
`	}`

`	// first digit`
`	ch := byte('0')`
`	if d.nd != 0 {`
`		ch = d.d[0]`
`	}`
`	dst = append(dst, ch)`

`	// .moredigits`
`	if prec > 0 {`
`		dst = append(dst, '.')`
`		i := 1`
`		m := min(d.nd, prec+1)`
`		if i < m {`
`			dst = append(dst, d.d[i:m]...)`
`			i = m`
`		}`
`		for ; i <= prec; i++ {`
`			dst = append(dst, '0')`
`		}`
`	}`

`	// e±`
`	dst = append(dst, fmt)`
`	exp := d.dp - 1`
`	if d.nd == 0 { // special case: 0 has exponent 0`
`		exp = 0`
`	}`
`	if exp < 0 {`
`		ch = '-'`
`		exp = -exp`
`	} else {`
`		ch = '+'`
`	}`
`	dst = append(dst, ch)`

`	// dd or ddd`
`	switch {`
`	case exp < 10:`
`		dst = append(dst, '0', byte(exp)+'0')`
`	case exp < 100:`
`		dst = append(dst, byte(exp/10)+'0', byte(exp%10)+'0')`
`	default:`
`		dst = append(dst, byte(exp/100)+'0', byte(exp/10)%10+'0', byte(exp%10)+'0')`
`	}`

`	return dst`
`}`

`// %f: -ddddddd.ddddd`
`func fmtF(dst []byte, neg bool, d decimalSlice, prec int) []byte {`
`	// sign`
`	if neg {`
`		dst = append(dst, '-')`
`	}`

`	// integer, padded with zeros as needed.`
`	if d.dp > 0 {`
`		m := min(d.nd, d.dp)`
`		dst = append(dst, d.d[:m]...)`
`		for ; m < d.dp; m++ {`
`			dst = append(dst, '0')`
`		}`
`	} else {`
`		dst = append(dst, '0')`
`	}`

`	// fraction`
`	if prec > 0 {`
`		dst = append(dst, '.')`
`		for i := 0; i < prec; i++ {`
`			ch := byte('0')`
`			if j := d.dp + i; 0 <= j && j < d.nd {`
`				ch = d.d[j]`
`			}`
`			dst = append(dst, ch)`
`		}`
`	}`

`	return dst`
`}`

`// %b: -ddddddddp±ddd`
`func fmtB(dst []byte, neg bool, mant uint64, exp int, flt *floatInfo) []byte {`
`	// sign`
`	if neg {`
`		dst = append(dst, '-')`
`	}`

`	// mantissa`
`	dst, _ = formatBits(dst, mant, 10, false, true)`

`	// p`
`	dst = append(dst, 'p')`

`	// ±exponent`
`	exp -= int(flt.mantbits)`
`	if exp >= 0 {`
`		dst = append(dst, '+')`
`	}`
`	dst, _ = formatBits(dst, uint64(exp), 10, exp < 0, true)`

`	return dst`
`}`

`// %x: -0x1.yyyyyyyyp±ddd or -0x0p+0. (y is hex digit, d is decimal digit)`
`func fmtX(dst []byte, prec int, fmt byte, neg bool, mant uint64, exp int, flt *floatInfo) []byte {`
`	if mant == 0 {`
`		exp = 0`
`	}`

`	// Shift digits so leading 1 (if any) is at bit 1<<60.`
`	mant <<= 60 - flt.mantbits`
`	for mant != 0 && mant&(1<<60) == 0 {`
`		mant <<= 1`
`		exp--`
`	}`

`	// Round if requested.`
`	if prec >= 0 && prec < 15 {`
`		shift := uint(prec * 4)`
`		extra := (mant << shift) & (1<<60 - 1)`
`		mant >>= 60 - shift`
`		if extra|(mant&1) > 1<<59 {`
`			mant++`
`		}`
`		mant <<= 60 - shift`
`		if mant&(1<<61) != 0 {`
`			// Wrapped around.`
`			mant >>= 1`
`			exp++`
`		}`
`	}`

`	hex := lowerhex`
`	if fmt == 'X' {`
`		hex = upperhex`
`	}`

`	// sign, 0x, leading digit`
`	if neg {`
`		dst = append(dst, '-')`
`	}`
`	dst = append(dst, '0', fmt, '0'+byte((mant>>60)&1))`

`	// .fraction`
`	mant <<= 4 // remove leading 0 or 1`
`	if prec < 0 && mant != 0 {`
`		dst = append(dst, '.')`
`		for mant != 0 {`
`			dst = append(dst, hex[(mant>>60)&15])`
`			mant <<= 4`
`		}`
`	} else if prec > 0 {`
`		dst = append(dst, '.')`
`		for i := 0; i < prec; i++ {`
`			dst = append(dst, hex[(mant>>60)&15])`
`			mant <<= 4`
`		}`
`	}`

`	// p±`
`	ch := byte('P')`
`	if fmt == lower(fmt) {`
`		ch = 'p'`
`	}`
`	dst = append(dst, ch)`
`	if exp < 0 {`
`		ch = '-'`
`		exp = -exp`
`	} else {`
`		ch = '+'`
`	}`
`	dst = append(dst, ch)`

`	// dd or ddd or dddd`
`	switch {`
`	case exp < 100:`
`		dst = append(dst, byte(exp/10)+'0', byte(exp%10)+'0')`
`	case exp < 1000:`
`		dst = append(dst, byte(exp/100)+'0', byte((exp/10)%10)+'0', byte(exp%10)+'0')`
`	default:`
`		dst = append(dst, byte(exp/1000)+'0', byte(exp/100)%10+'0', byte((exp/10)%10)+'0', byte(exp%10)+'0')`
`	}`

`	return dst`
`}`
```