// 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 

// 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 ( float64,  byte, ,  int) string {
	return string(genericFtoa(make([]byte, 0, max(+4, 24)), , , , ))
}

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

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

	 := >>(.expbits+.mantbits) != 0
	 := int(>>.mantbits) & (1<<.expbits - 1)
	 :=  & (uint64(1)<<.mantbits - 1)

	switch  {
	case 1<<.expbits - 1:
		// Inf, NaN
		var  string
		switch {
		case  != 0:
			 = "NaN"
		case :
			 = "-Inf"
		default:
			 = "+Inf"
		}
		return append(, ...)

	case 0:
		// denormalized
		++

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

	// Pick off easy binary, hex formats.
	if  == 'b' {
		return fmtB(, , , , )
	}
	if  == 'x' ||  == 'X' {
		return fmtX(, , , , , , )
	}

	if !optimize {
		return bigFtoa(, , , , , , )
	}

	var  decimalSlice
	 := false
	// Negative precision means "only as much as needed to be exact."
	 :=  < 0
	if  {
		// Try Grisu3 algorithm.
		 := new(extFloat)
		,  := .AssignComputeBounds(, , , )
		var  [32]byte
		.d = [:]
		 = .ShortestDecimal(&, &, &)
		if ! {
			return bigFtoa(, , , , , , )
		}
		// Precision for shortest representation mode.
		switch  {
		case 'e', 'E':
			 = max(.nd-1, 0)
		case 'f':
			 = max(.nd-.dp, 0)
		case 'g', 'G':
			 = .nd
		}
	} else if  != 'f' {
		// Fixed number of digits.
		 := 
		switch  {
		case 'e', 'E':
			++
		case 'g', 'G':
			if  == 0 {
				 = 1
			}
			 = 
		}
		if  <= 15 {
			// try fast algorithm when the number of digits is reasonable.
			var  [24]byte
			.d = [:]
			 := extFloat{,  - int(.mantbits), }
			 = .FixedDecimal(&, )
		}
	}
	if ! {
		return bigFtoa(, , , , , , )
	}
	return formatDigits(, , , , , )
}

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

func formatDigits( []byte,  bool,  bool,  decimalSlice,  int,  byte) []byte {
	switch  {
	case 'e', 'E':
		return fmtE(, , , , )
	case 'f':
		return fmtF(, , , )
	case 'g', 'G':
		// trailing fractional zeros in 'e' form will be trimmed.
		 := 
		if  > .nd && .nd >= .dp {
			 = .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  {
			 = 6
		}
		 := .dp - 1
		if  < -4 ||  >=  {
			if  > .nd {
				 = .nd
			}
			return fmtE(, , , -1, +'e'-'g')
		}
		if  > .dp {
			 = .nd
		}
		return fmtF(, , , max(-.dp, 0))
	}

	// unknown format
	return append(, '%', )
}

// 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( *decimal,  uint64,  int,  *floatInfo) {
	// If mantissa is zero, the number is zero; stop now.
	if  == 0 {
		.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).
	 := .bias + 1 // minimum possible exponent
	if  >  && 332*(.dp-.nd) >= 100*(-int(.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.
	 := new(decimal)
	.Assign(*2 + 1)
	.Shift( - int(.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  uint64
	var  int
	if  > 1<<.mantbits ||  ==  {
		 =  - 1
		 = 
	} else {
		 = *2 - 1
		 =  - 1
	}
	 := new(decimal)
	.Assign(*2 + 1)
	.Shift( - int(.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.
	 := %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  uint8

	// Now we can figure out the minimum number of digits required.
	// Walk along until d has distinguished itself from upper and lower.
	for  := 0; ; ++ {
		// 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.
		 :=  - .dp + .dp
		if  >= .nd {
			break
		}
		 :=  - .dp + .dp
		 := byte('0') // lower digit
		if  >= 0 &&  < .nd {
			 = .d[]
		}
		 := byte('0') // middle digit
		if  >= 0 {
			 = .d[]
		}
		 := byte('0') // upper digit
		if  < .nd {
			 = .d[]
		}

		// 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).
		 :=  !=  ||  && +1 == .nd

		switch {
		case  == 0 && +1 < :
			// Example:
			// m = 12345xxx
			// u = 12347xxx
			 = 2
		case  == 0 &&  != :
			// Example:
			// m = 12345xxx
			// u = 12346xxx
			 = 1
		case  == 1 && ( != '9' ||  != '0'):
			// Example:
			// m = 1234598x
			// u = 1234600x
			 = 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.
		 :=  > 0 && ( ||  > 1 || +1 < .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  && :
			.Round( + 1)
			return
		case :
			.RoundDown( + 1)
			return
		case :
			.RoundUp( + 1)
			return
		}
	}
}

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

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

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

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

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

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

	return 
}

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

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

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

	return 
}

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

	// mantissa
	, _ = formatBits(, , 10, false, true)

	// p
	 = append(, 'p')

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

	return 
}

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

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

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

	 := lowerhex
	if  == 'X' {
		 = upperhex
	}

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

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

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

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

	return 
}

func min(,  int) int {
	if  <  {
		return 
	}
	return 
}

func max(,  int) int {
	if  >  {
		return 
	}
	return 
}