// 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/bits"
	"unsafe"
)

const (
	lowerhex = "0123456789abcdef"
	upperhex = "0123456789ABCDEF"
)

const (
	float32MantBits = 23
	float32ExpBits  = 8
	float32Bias     = -127
	float32MinExp   = -189

	float64MantBits = 52
	float64ExpBits  = 11
	float64Bias     = -1023
	float64MinExp   = -1085
)

// 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.
// The exponent is written as a decimal integer;
// for all formats other than 'b', it will be at least two digits.
func FormatFloat(f float64, fmt byte, prec, bitSize int) string {
	if bitSize == 32 {
		return string(ftoa32(make([]byte, 0, max(prec+4, 24)), float32(f), fmt, prec))
	}
	if bitSize == 64 {
		return string(ftoa64(make([]byte, 0, max(prec+4, 24)), f, fmt, prec))
	}
	panic("strconv: illegal FormatFloat 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 {
	if bitSize == 32 {
		return ftoa32(dst, float32(f), fmt, prec)
	}
	if bitSize == 64 {
		return ftoa64(dst, f, fmt, prec)
	}
	panic("strconv: illegal AppendFloat bitSize")
}

// TODO(rsc): This should be ftoa[F float32 | float64](dst []byte, val F, ...),
// but due to some bad interaction between inlining, escape analysis, and generic functions,
// the result appears to escape dst to the heap with -l=4, which breaks
// TestAbstractOriginSanity. See go.dev/issue/79547.
// For now we make two manual specializations ftoa32 and ftoa64 instead.

func ftoa32(dst []byte, val float32, fmt byte, prec int) []byte {
	type F = float32
	var b uint64
	var expBits, mantBits, bias int // parameterized constants
	switch 8 * unsafe.Sizeof(val) {
	case 32:
		b = uint64(float32bits(float32(val)))
		expBits = float32ExpBits
		mantBits = float32MantBits
		bias = float32Bias
	case 64:
		b = float64bits(float64(val))
		expBits = float64ExpBits
		mantBits = float64MantBits
		bias = float64Bias
	}

	neg := b>>(expBits+mantBits) != 0
	exp := int(b>>mantBits) & (1<<expBits - 1)
	mant := b & (1<<mantBits - 1)
	if exp == 1<<expBits-1 {
		if mant != 0 {
			return append(dst, "NaN"...)
		}
		if neg {
			return append(dst, "-Inf"...)
		}
		return append(dst, "+Inf"...)
	}
	if exp == 0 {
		exp++
	} else {
		mant |= 1 << mantBits
	}
	exp += bias

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

	// Pick off zero.
	if mant == 0 {
		return fmtEFG(dst, neg, nil, 0, 0, prec, fmt, prec < 0)
	}

	// Negative precision means "only as much as needed to be exact."
	if prec < 0 {
		// Use fast unrounded scaling.
		var buf [32]byte
		s := 64 - bits.Len64(mant)
		m := mant << s
		e := exp - s
		d, p := shortFloat[F](m, e-mantBits)
		dp, nd := setDigits(buf[:], d, p, numDigits(d))
		// Precision for shortest representation mode.
		switch fmt {
		case 'e', 'E':
			prec = max(nd-1, 0)
		case 'f':
			prec = max(nd-dp, 0)
		case 'g', 'G':
			prec = nd
		}
		return fmtEFG(dst, neg, buf[:], dp, nd, prec, fmt, true)
	}

	if optimize {
		// Fixed number of digits.
		digits := prec
		switch fmt {
		case 'f':
			// %f precision specifies digits after the decimal point.
			// Estimate an upper bound on the total number of digits needed.
			// ftoaFixed will shorten as needed according to prec.
			if exp >= 0 {
				digits = 1 + log10Pow2(1+exp) + prec
			} else {
				digits = 1 + prec - log10Pow2(-exp)
			}
		case 'e', 'E':
			digits++
		case 'g', 'G':
			if prec == 0 {
				prec = 1
			}
			digits = prec
		default:
			// Invalid mode.
			digits = 1
		}
		if digits <= 18 {
			// digits <= 0 happens for %f on very small numbers
			// and means that we're guaranteed to print all zeros.
			var buf [24]byte
			var dp, nd int
			if digits > 0 {
				s := 64 - bits.Len64(mant)
				m := mant << s
				e := exp - s
				d, p := fixedWidthFloat(m, e-mantBits, digits, prec, fmt)
				if d != 0 {
					dp, nd = setDigits(buf[:], d, p, numDigits(d))
				}
			}
			return fmtEFG(dst, neg, buf[:], dp, nd, prec, fmt, false)
		}
	}

	// Slow bignum case. Only for non-shortest results.
	d := new(decimal)
	d.Assign(mant)
	d.Shift(exp - mantBits)
	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)
	}
	return fmtEFG(dst, neg, d.d[:], d.dp, d.nd, prec, fmt, false)
}

func ftoa64(dst []byte, val float64, fmt byte, prec int) []byte {
	type F = float64
	var b uint64
	var expBits, mantBits, bias int // parameterized constants
	switch 8 * unsafe.Sizeof(val) {
	case 32:
		b = uint64(float32bits(float32(val)))
		expBits = float32ExpBits
		mantBits = float32MantBits
		bias = float32Bias
	case 64:
		b = float64bits(float64(val))
		expBits = float64ExpBits
		mantBits = float64MantBits
		bias = float64Bias
	}

	neg := b>>(expBits+mantBits) != 0
	exp := int(b>>mantBits) & (1<<expBits - 1)
	mant := b & (1<<mantBits - 1)
	if exp == 1<<expBits-1 {
		if mant != 0 {
			return append(dst, "NaN"...)
		}
		if neg {
			return append(dst, "-Inf"...)
		}
		return append(dst, "+Inf"...)
	}
	if exp == 0 {
		exp++
	} else {
		mant |= 1 << mantBits
	}
	exp += bias

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

	// Pick off zero.
	if mant == 0 {
		return fmtEFG(dst, neg, nil, 0, 0, prec, fmt, prec < 0)
	}

	// Negative precision means "only as much as needed to be exact."
	if prec < 0 {
		// Use fast unrounded scaling.
		var buf [32]byte
		s := 64 - bits.Len64(mant)
		m := mant << s
		e := exp - s
		d, p := shortFloat[F](m, e-mantBits)
		dp, nd := setDigits(buf[:], d, p, numDigits(d))
		// Precision for shortest representation mode.
		switch fmt {
		case 'e', 'E':
			prec = max(nd-1, 0)
		case 'f':
			prec = max(nd-dp, 0)
		case 'g', 'G':
			prec = nd
		}
		return fmtEFG(dst, neg, buf[:], dp, nd, prec, fmt, true)
	}

	if optimize {
		// Fixed number of digits.
		digits := prec
		switch fmt {
		case 'f':
			// %f precision specifies digits after the decimal point.
			// Estimate an upper bound on the total number of digits needed.
			// ftoaFixed will shorten as needed according to prec.
			if exp >= 0 {
				digits = 1 + log10Pow2(1+exp) + prec
			} else {
				digits = 1 + prec - log10Pow2(-exp)
			}
		case 'e', 'E':
			digits++
		case 'g', 'G':
			if prec == 0 {
				prec = 1
			}
			digits = prec
		default:
			// Invalid mode.
			digits = 1
		}
		if digits <= 18 {
			// digits <= 0 happens for %f on very small numbers
			// and means that we're guaranteed to print all zeros.
			var buf [24]byte
			var dp, nd int
			if digits > 0 {
				s := 64 - bits.Len64(mant)
				m := mant << s
				e := exp - s
				d, p := fixedWidthFloat(m, e-mantBits, digits, prec, fmt)
				if d != 0 {
					dp, nd = setDigits(buf[:], d, p, numDigits(d))
				}
			}
			return fmtEFG(dst, neg, buf[:], dp, nd, prec, fmt, false)
		}
	}

	// Slow bignum case. Only for non-shortest results.
	d := new(decimal)
	d.Assign(mant)
	d.Shift(exp - mantBits)
	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)
	}
	return fmtEFG(dst, neg, d.d[:], d.dp, d.nd, prec, fmt, false)
}

func fmtEFG(dst []byte, neg bool, s []byte, dp, nd, prec int, fmt byte, shortest bool) []byte {
	if fmt == 'g' || fmt == 'G' {
		// trailing fractional zeros in 'e' form will be trimmed.
		eprec := prec
		if eprec > nd && nd >= dp {
			eprec = 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 := dp - 1
		if exp < -4 || exp >= eprec {
			if prec > nd {
				prec = nd
			}
			prec--
			fmt = fmt + 'e' - 'g'
		} else {
			if prec > dp {
				prec = nd
			}
			prec = max(prec-dp, 0)
			fmt = 'f'
		}
	}

	switch fmt {
	case 'e', 'E': // %e: -d.ddddde±dd
		// sign
		if neg {
			dst = append(dst, '-')
		}

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

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

		// e±
		dst = append(dst, fmt)
		exp := dp - 1
		if 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

	case 'f': // %f: -ddddddd.ddddd
		// sign
		if neg {
			dst = append(dst, '-')
		}

		// integer, padded with zeros as needed.
		if dp > 0 {
			m := min(nd, dp)
			for _, c := range s[:m] {
				dst = append(dst, c)
			}
			for range dp - m {
				dst = append(dst, '0')
			}
		} else {
			dst = append(dst, '0')
		}

		// fraction
		if prec > 0 {
			dst = append(dst, '.')
			lz := min(prec, max(0, -dp)) // leading zeros
			off := dp + lz
			m := min(prec-lz, max(0, nd-off)) // middle digits
			tz := max(0, prec-lz-m)           // trailing zeros
			for range lz {
				dst = append(dst, '0')
			}
			for i := range m {
				dst = append(dst, s[off+i])
			}
			for range tz {
				dst = append(dst, '0')
			}
		}
		return dst
	}

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

// %b: -ddddddddp±ddd
func fmtB(dst []byte, neg bool, mant uint64, exp int) []byte {
	if neg {
		dst = append(dst, '-')
	}
	dst = AppendUint(dst, mant, 10)
	dst = append(dst, 'p')
	if exp >= 0 {
		dst = append(dst, '+')
	}
	dst = AppendInt(dst, int64(exp), 10)
	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, mantBits int) []byte {
	if mant == 0 {
		exp = 0
	}

	// Shift digits so leading 1 (if any) is at bit 1<<60.
	// TODO: Is this the right way to handle subnormals?
	mant <<= 60 - 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
}