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

package strconv

// decimal to binary floating point conversion.
// Algorithm:
//   1) Store input in multiprecision decimal.
//   2) Multiply/divide decimal by powers of two until in range [0.5, 1)
//   3) Multiply by 2^precision and round to get mantissa.

import 

var optimize = true // set to false to force slow-path conversions for testing

// commonPrefixLenIgnoreCase returns the length of the common
// prefix of s and prefix, with the character case of s ignored.
// The prefix argument must be all lower-case.
func commonPrefixLenIgnoreCase(,  string) int {
	 := len()
	if  > len() {
		 = len()
	}
	for  := 0;  < ; ++ {
		 := []
		if 'A' <=  &&  <= 'Z' {
			 += 'a' - 'A'
		}
		if  != [] {
			return 
		}
	}
	return 
}

// special returns the floating-point value for the special,
// possibly signed floating-point representations inf, infinity,
// and NaN. The result is ok if a prefix of s contains one
// of these representations and n is the length of that prefix.
// The character case is ignored.
func special( string) ( float64,  int,  bool) {
	if len() == 0 {
		return 0, 0, false
	}
	 := 1
	 := 0
	switch [0] {
	case '+', '-':
		if [0] == '-' {
			 = -1
		}
		 = 1
		 = [1:]
		fallthrough
	case 'i', 'I':
		 := commonPrefixLenIgnoreCase(, "infinity")
		// Anything longer than "inf" is ok, but if we
		// don't have "infinity", only consume "inf".
		if 3 <  &&  < 8 {
			 = 3
		}
		if  == 3 ||  == 8 {
			return math.Inf(),  + , true
		}
	case 'n', 'N':
		if commonPrefixLenIgnoreCase(, "nan") == 3 {
			return math.NaN(), 3, true
		}
	}
	return 0, 0, false
}

func ( *decimal) ( string) ( bool) {
	 := 0
	.neg = false
	.trunc = false

	// optional sign
	if  >= len() {
		return
	}
	switch {
	case [] == '+':
		++
	case [] == '-':
		.neg = true
		++
	}

	// digits
	 := false
	 := false
	for ;  < len(); ++ {
		switch {
		case [] == '_':
			// readFloat already checked underscores
			continue
		case [] == '.':
			if  {
				return
			}
			 = true
			.dp = .nd
			continue

		case '0' <= [] && [] <= '9':
			 = true
			if [] == '0' && .nd == 0 { // ignore leading zeros
				.dp--
				continue
			}
			if .nd < len(.d) {
				.d[.nd] = []
				.nd++
			} else if [] != '0' {
				.trunc = true
			}
			continue
		}
		break
	}
	if ! {
		return
	}
	if ! {
		.dp = .nd
	}

	// optional exponent moves decimal point.
	// if we read a very large, very long number,
	// just be sure to move the decimal point by
	// a lot (say, 100000).  it doesn't matter if it's
	// not the exact number.
	if  < len() && lower([]) == 'e' {
		++
		if  >= len() {
			return
		}
		 := 1
		if [] == '+' {
			++
		} else if [] == '-' {
			++
			 = -1
		}
		if  >= len() || [] < '0' || [] > '9' {
			return
		}
		 := 0
		for ;  < len() && ('0' <= [] && [] <= '9' || [] == '_'); ++ {
			if [] == '_' {
				// readFloat already checked underscores
				continue
			}
			if  < 10000 {
				 = *10 + int([]) - '0'
			}
		}
		.dp +=  * 
	}

	if  != len() {
		return
	}

	 = true
	return
}

// readFloat reads a decimal or hexadecimal mantissa and exponent from a float
// string representation in s; the number may be followed by other characters.
// readFloat reports the number of bytes consumed (i), and whether the number
// is valid (ok).
func readFloat( string) ( uint64,  int, , ,  bool,  int,  bool) {
	 := false

	// optional sign
	if  >= len() {
		return
	}
	switch {
	case [] == '+':
		++
	case [] == '-':
		 = true
		++
	}

	// digits
	 := uint64(10)
	 := 19 // 10^19 fits in uint64
	 := byte('e')
	if +2 < len() && [] == '0' && lower([+1]) == 'x' {
		 = 16
		 = 16 // 16^16 fits in uint64
		 += 2
		 = 'p'
		 = true
	}
	 := false
	 := false
	 := 0
	 := 0
	 := 0
:
	for ;  < len(); ++ {
		switch  := []; true {
		case  == '_':
			 = true
			continue

		case  == '.':
			if  {
				break 
			}
			 = true
			 = 
			continue

		case '0' <=  &&  <= '9':
			 = true
			if  == '0' &&  == 0 { // ignore leading zeros
				--
				continue
			}
			++
			if  <  {
				 *= 
				 += uint64( - '0')
				++
			} else if  != '0' {
				 = true
			}
			continue

		case  == 16 && 'a' <= lower() && lower() <= 'f':
			 = true
			++
			if  <  {
				 *= 16
				 += uint64(lower() - 'a' + 10)
				++
			} else {
				 = true
			}
			continue
		}
		break
	}
	if ! {
		return
	}
	if ! {
		 = 
	}

	if  == 16 {
		 *= 4
		 *= 4
	}

	// optional exponent moves decimal point.
	// if we read a very large, very long number,
	// just be sure to move the decimal point by
	// a lot (say, 100000).  it doesn't matter if it's
	// not the exact number.
	if  < len() && lower([]) ==  {
		++
		if  >= len() {
			return
		}
		 := 1
		if [] == '+' {
			++
		} else if [] == '-' {
			++
			 = -1
		}
		if  >= len() || [] < '0' || [] > '9' {
			return
		}
		 := 0
		for ;  < len() && ('0' <= [] && [] <= '9' || [] == '_'); ++ {
			if [] == '_' {
				 = true
				continue
			}
			if  < 10000 {
				 = *10 + int([]) - '0'
			}
		}
		 +=  * 
	} else if  == 16 {
		// Must have exponent.
		return
	}

	if  != 0 {
		 =  - 
	}

	if  && !underscoreOK([:]) {
		return
	}

	 = true
	return
}

// decimal power of ten to binary power of two.
var powtab = []int{1, 3, 6, 9, 13, 16, 19, 23, 26}

func ( *decimal) ( *floatInfo) ( uint64,  bool) {
	var  int
	var  uint64

	// Zero is always a special case.
	if .nd == 0 {
		 = 0
		 = .bias
		goto 
	}

	// Obvious overflow/underflow.
	// These bounds are for 64-bit floats.
	// Will have to change if we want to support 80-bit floats in the future.
	if .dp > 310 {
		goto 
	}
	if .dp < -330 {
		// zero
		 = 0
		 = .bias
		goto 
	}

	// Scale by powers of two until in range [0.5, 1.0)
	 = 0
	for .dp > 0 {
		var  int
		if .dp >= len(powtab) {
			 = 27
		} else {
			 = powtab[.dp]
		}
		.Shift(-)
		 += 
	}
	for .dp < 0 || .dp == 0 && .d[0] < '5' {
		var  int
		if -.dp >= len(powtab) {
			 = 27
		} else {
			 = powtab[-.dp]
		}
		.Shift()
		 -= 
	}

	// Our range is [0.5,1) but floating point range is [1,2).
	--

	// Minimum representable exponent is flt.bias+1.
	// If the exponent is smaller, move it up and
	// adjust d accordingly.
	if  < .bias+1 {
		 := .bias + 1 - 
		.Shift(-)
		 += 
	}

	if -.bias >= 1<<.expbits-1 {
		goto 
	}

	// Extract 1+flt.mantbits bits.
	.Shift(int(1 + .mantbits))
	 = .RoundedInteger()

	// Rounding might have added a bit; shift down.
	if  == 2<<.mantbits {
		 >>= 1
		++
		if -.bias >= 1<<.expbits-1 {
			goto 
		}
	}

	// Denormalized?
	if &(1<<.mantbits) == 0 {
		 = .bias
	}
	goto 

:
	// ±Inf
	 = 0
	 = 1<<.expbits - 1 + .bias
	 = true

:
	// Assemble bits.
	 :=  & (uint64(1)<<.mantbits - 1)
	 |= uint64((-.bias)&(1<<.expbits-1)) << .mantbits
	if .neg {
		 |= 1 << .mantbits << .expbits
	}
	return , 
}

// Exact powers of 10.
var float64pow10 = []float64{
	1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9,
	1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19,
	1e20, 1e21, 1e22,
}
var float32pow10 = []float32{1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10}

// If possible to convert decimal representation to 64-bit float f exactly,
// entirely in floating-point math, do so, avoiding the expense of decimalToFloatBits.
// Three common cases:
//	value is exact integer
//	value is exact integer * exact power of ten
//	value is exact integer / exact power of ten
// These all produce potentially inexact but correctly rounded answers.
func atof64exact( uint64,  int,  bool) ( float64,  bool) {
	if >>float64info.mantbits != 0 {
		return
	}
	 = float64()
	if  {
		 = -
	}
	switch {
	case  == 0:
		// an integer.
		return , true
	// Exact integers are <= 10^15.
	// Exact powers of ten are <= 10^22.
	case  > 0 &&  <= 15+22: // int * 10^k
		// If exponent is big but number of digits is not,
		// can move a few zeros into the integer part.
		if  > 22 {
			 *= float64pow10[-22]
			 = 22
		}
		if  > 1e15 ||  < -1e15 {
			// the exponent was really too large.
			return
		}
		return  * float64pow10[], true
	case  < 0 &&  >= -22: // int / 10^k
		return  / float64pow10[-], true
	}
	return
}

// If possible to compute mantissa*10^exp to 32-bit float f exactly,
// entirely in floating-point math, do so, avoiding the machinery above.
func atof32exact( uint64,  int,  bool) ( float32,  bool) {
	if >>float32info.mantbits != 0 {
		return
	}
	 = float32()
	if  {
		 = -
	}
	switch {
	case  == 0:
		return , true
	// Exact integers are <= 10^7.
	// Exact powers of ten are <= 10^10.
	case  > 0 &&  <= 7+10: // int * 10^k
		// If exponent is big but number of digits is not,
		// can move a few zeros into the integer part.
		if  > 10 {
			 *= float32pow10[-10]
			 = 10
		}
		if  > 1e7 ||  < -1e7 {
			// the exponent was really too large.
			return
		}
		return  * float32pow10[], true
	case  < 0 &&  >= -10: // int / 10^k
		return  / float32pow10[-], true
	}
	return
}

// atofHex converts the hex floating-point string s
// to a rounded float32 or float64 value (depending on flt==&float32info or flt==&float64info)
// and returns it as a float64.
// The string s has already been parsed into a mantissa, exponent, and sign (neg==true for negative).
// If trunc is true, trailing non-zero bits have been omitted from the mantissa.
func atofHex( string,  *floatInfo,  uint64,  int, ,  bool) (float64, error) {
	 := 1<<.expbits + .bias - 2
	 := .bias + 1
	 += int(.mantbits) // mantissa now implicitly divided by 2^mantbits.

	// Shift mantissa and exponent to bring representation into float range.
	// Eventually we want a mantissa with a leading 1-bit followed by mantbits other bits.
	// For rounding, we need two more, where the bottom bit represents
	// whether that bit or any later bit was non-zero.
	// (If the mantissa has already lost non-zero bits, trunc is true,
	// and we OR in a 1 below after shifting left appropriately.)
	for  != 0 && >>(.mantbits+2) == 0 {
		 <<= 1
		--
	}
	if  {
		 |= 1
	}
	for >>(1+.mantbits+2) != 0 {
		 = >>1 | &1
		++
	}

	// If exponent is too negative,
	// denormalize in hopes of making it representable.
	// (The -2 is for the rounding bits.)
	for  > 1 &&  < -2 {
		 = >>1 | &1
		++
	}

	// Round using two bottom bits.
	 :=  & 3
	 >>= 2
	 |=  & 1 // round to even (round up if mantissa is odd)
	 += 2
	if  == 3 {
		++
		if  == 1<<(1+.mantbits) {
			 >>= 1
			++
		}
	}

	if >>.mantbits == 0 { // Denormal or zero.
		 = .bias
	}
	var  error
	if  >  { // infinity and range error
		 = 1 << .mantbits
		 =  + 1
		 = rangeError(fnParseFloat, )
	}

	 :=  & (1<<.mantbits - 1)
	 |= uint64((-.bias)&(1<<.expbits-1)) << .mantbits
	if  {
		 |= 1 << .mantbits << .expbits
	}
	if  == &float32info {
		return float64(math.Float32frombits(uint32())), 
	}
	return math.Float64frombits(), 
}

const fnParseFloat = "ParseFloat"

func atof32( string) ( float32,  int,  error) {
	if , ,  := special();  {
		return float32(), , nil
	}

	, , , , , ,  := readFloat()
	if ! {
		return 0, , syntaxError(fnParseFloat, )
	}

	if  {
		,  := atofHex([:], &float32info, , , , )
		return float32(), , 
	}

	if optimize {
		// Try pure floating-point arithmetic conversion, and if that fails,
		// the Eisel-Lemire algorithm.
		if ! {
			if ,  := atof32exact(, , );  {
				return , , nil
			}
		}
		,  := eiselLemire32(, , )
		if  {
			if ! {
				return , , nil
			}
			// Even if the mantissa was truncated, we may
			// have found the correct result. Confirm by
			// converting the upper mantissa bound.
			,  := eiselLemire32(+1, , )
			if  &&  ==  {
				return , , nil
			}
		}
	}

	// Slow fallback.
	var  decimal
	if !.set([:]) {
		return 0, , syntaxError(fnParseFloat, )
	}
	,  := .floatBits(&float32info)
	 = math.Float32frombits(uint32())
	if  {
		 = rangeError(fnParseFloat, )
	}
	return , , 
}

func atof64( string) ( float64,  int,  error) {
	if , ,  := special();  {
		return , , nil
	}

	, , , , , ,  := readFloat()
	if ! {
		return 0, , syntaxError(fnParseFloat, )
	}

	if  {
		,  := atofHex([:], &float64info, , , , )
		return , , 
	}

	if optimize {
		// Try pure floating-point arithmetic conversion, and if that fails,
		// the Eisel-Lemire algorithm.
		if ! {
			if ,  := atof64exact(, , );  {
				return , , nil
			}
		}
		,  := eiselLemire64(, , )
		if  {
			if ! {
				return , , nil
			}
			// Even if the mantissa was truncated, we may
			// have found the correct result. Confirm by
			// converting the upper mantissa bound.
			,  := eiselLemire64(+1, , )
			if  &&  ==  {
				return , , nil
			}
		}
	}

	// Slow fallback.
	var  decimal
	if !.set([:]) {
		return 0, , syntaxError(fnParseFloat, )
	}
	,  := .floatBits(&float64info)
	 = math.Float64frombits()
	if  {
		 = rangeError(fnParseFloat, )
	}
	return , , 
}

// ParseFloat converts the string s to a floating-point number
// with the precision specified by bitSize: 32 for float32, or 64 for float64.
// When bitSize=32, the result still has type float64, but it will be
// convertible to float32 without changing its value.
//
// ParseFloat accepts decimal and hexadecimal floating-point number syntax.
// If s is well-formed and near a valid floating-point number,
// ParseFloat returns the nearest floating-point number rounded
// using IEEE754 unbiased rounding.
// (Parsing a hexadecimal floating-point value only rounds when
// there are more bits in the hexadecimal representation than
// will fit in the mantissa.)
//
// The errors that ParseFloat returns have concrete type *NumError
// and include err.Num = s.
//
// If s is not syntactically well-formed, ParseFloat returns err.Err = ErrSyntax.
//
// If s is syntactically well-formed but is more than 1/2 ULP
// away from the largest floating point number of the given size,
// ParseFloat returns f = ±Inf, err.Err = ErrRange.
//
// ParseFloat recognizes the strings "NaN", and the (possibly signed) strings "Inf" and "Infinity"
// as their respective special floating point values. It ignores case when matching.
func ( string,  int) (float64, error) {
	, ,  := parseFloatPrefix(, )
	if  == nil &&  != len() {
		return 0, syntaxError(fnParseFloat, )
	}
	return , 
}

func parseFloatPrefix( string,  int) (float64, int, error) {
	if  == 32 {
		, ,  := atof32()
		return float64(), , 
	}
	return atof64()
}