// Trivet
// Copyright (c) 2023 by Stacy Prowell.  All rights reserved.
// https://gitlab.com/binary-tools/trivet

//! Parse hexadecimal-encoded floating point numbers.

use crate::{
    errors::{syntax_error, ParseResult},
    ParserCore,
};

/// Convert a hexadecimal digit to an unsigned 32-bit value.  It is guaranteed that if the input
/// is a valid hexadecimal digit (regardless of case) then the result is in the range [0,15].
/// Otherwise it may be greater than 15.
#[inline]
fn hex_digit_value(ch: char) -> u64 {
    let dig = ch as u64;
    if (0x30..=0x39).contains(&dig) {
        dig - 0x30
    } else if (0x41..0x5B).contains(&(dig & 0xdf)) {
        (dig & 0xdf) - 0x37
    } else {
        255
    }
}

/// Given a value in the range [1,15], compute the index of the first one bit in the number.  This
/// is used to bias the exponent when we encounter the first non-zero digit.  The result will be
/// 1, 2, 3, or 4.
#[inline]
fn exponent_adjust(value: u64) -> i32 {
    64i32 - (value.leading_zeros() as i32)
}

/// Parse a floating point number represented in hexadecimal.  This presumes the sign and any radix
/// signifier have been parsed, and the parser is at the first digit of the hexadecimal number.
/// If the number is negative, indicate this with the `negative` argument.  If underscores are
/// permitted, indicate this with the `underscores` argument.
///
/// This method does not handle `inf`, `infinity`, or `nan`.  Parse those separately.
///
/// Non-hexadecimal digits cause an error.  If no digits are found,
/// this will cause an error.  A character that causes the error is consumed.
///
/// If there are too many significant digits then the mantissa will overflow and this will generate
/// an error.
///
/// For example, the following are ways to encode 1/2.
///
/// - `0.8`
/// - `8e-1`
/// - `0.800000`
/// - `.8`
/// - `8000e-4`
///
pub fn parse_hexadecimal_float(
    parser: &mut ParserCore,
    negative: bool,
    underscores: bool,
) -> ParseResult<f64> {
    /* Some examples.  The exponent is a power of 2, so e2 here means *2**2.
     *
     * 100          -> 1. e 8
     * 100.1        -> 1.001 e 8
     * 100.0000     -> 1. e 8
     * 000100       -> 1. e 8
     * 0.01         -> 1. e -8
     * 0.01001      -> 1. e -8
     * .01001       -> 1.001 e -8
     *
     * The initial exponent depends on the position of the first non-zero digit, if
     * any.  We work as follows.
     *
     * If we have not hit the decimal, but we have hit the first non-zero digit, then
     * add four to the exponent for every additional digit we find.
     *
     * If we have hit the decimal, but have not hit the first non-zero digit, then
     * subtract four for each digit we find, including the first non-zero digit, if any.
     *
     * State Machine for Mantissa and Initial Exponent:
     *
     * Have not found a digit or a decimal point.
     * [] 0 -> [0]
     *    X -> [1]
     *    . -> [.]
     *    _ -> []
     *
     * Have found a digit, but not a leading one or decimal point.
     * [0] 0 -> [0]
     *     X -> [1]
     *     . -> [0.]
     *     _ -> [0]
     *
     * Have found a leading one, but not a decimal point.
     * [1] 0 -> [1]     exponent += 1
     *     X -> [1]     exponent += 1
     *     . -> [1.]
     *     _ -> [1]
     *
     * Have found a decimal point, but not a digit.
     * [.] 0 -> [0.]    exponent -= 1
     *     X -> [1.]    exponent -= 1
     *     . -> err
     *     _ -> [.]
     *
     * Have found a digit and decimal point, but not a leading one.
     * [0.] 0 -> [0.]   exponent -= 1
     *      X -> [1.]   exponent -= 1
     *      . -> err
     *      _ -> [0.]
     *
     * [1.] 0 -> [1.]
     *      X -> [1.]
     *      . -> err
     *      _ -> [1.]
     *
     * State    name
     * []       None
     * [0]      Digit
     * [1]      One
     * [.]      Decimal
     * [0.]     DigitDecimal
     * [1.]     OneDecimal
     *
     * Examples:
     *
     * decimal  state           exponent
     *          None            0
     * 0        Digit           0
     * .        DigitDecimal    0
     * 0        DigitDecimal    -1
     * 1        OneDecimal      -2
     *
     * decimal  state           exponent
     *          None            0
     * 0        Digit           0
     * 1        One             0
     * 0        One             1
     * 0        One             2
     * .        OneDecimal      2
     * 0        OneDecimal      2
     * 0        OneDecimal      2
     */

    #[derive(Debug)]
    enum State {
        None,
        Digit,
        One,
        Decimal,
        DigitDecimal,
        OneDecimal,
    }
    let mut state = State::None;
    let mut mantissa = 0u64;
    let mut exponent = 0i32;

    // Parse the significand.  This obtains the mantissa and the exponent.  This implements
    // the state machine given above, except that we keep track of the exponent as a power
    // of two.  This can be a bit tricky, but it should be *equivalent* to what we would do
    // if we shifted the bits individually.  This really only matters on the first non-zero
    // digit.
    while !parser.is_at_eof() {
        let ch = parser.peek();
        if underscores && ch == '_' {
            parser.consume();
            continue;
        }
        match state {
            State::None => match ch {
                '0' => {
                    state = State::Digit;
                }
                ch if ch.is_ascii_hexdigit() => {
                    mantissa = hex_digit_value(ch);
                    exponent = exponent_adjust(mantissa) - 1;
                    state = State::One;
                }
                '.' => {
                    state = State::Decimal;
                }
                ch if ch.is_alphanumeric() => {
                    parser.consume();
                    return Err(syntax_error(
                        parser.loc(),
                        format!("Invalid hexadecimal digit '{}'", ch).as_str(),
                    ));
                }
                _ => {
                    break;
                }
            },
            State::Digit => match ch {
                '0' => {}
                ch if ch.is_ascii_hexdigit() => {
                    mantissa = hex_digit_value(ch);
                    exponent = exponent_adjust(mantissa) - 1;
                    state = State::One;
                }
                '.' => {
                    state = State::DigitDecimal;
                }
                'p' | 'P' => {
                    break;
                }
                ch if ch.is_alphanumeric() => {
                    parser.consume();
                    return Err(syntax_error(
                        parser.loc(),
                        format!("Invalid hexadecimal digit '{}'", ch).as_str(),
                    ));
                }
                _ => {
                    break;
                }
            },
            State::One => match ch {
                '0' => {
                    if mantissa >= 0x1000_0000_0000_0000 {
                        parser.consume();
                        return Err(syntax_error(parser.loc(), "Too many significant digits"));
                    }
                    mantissa <<= 4;
                    exponent += 4;
                }
                ch if ch.is_ascii_hexdigit() => {
                    if mantissa >= 0x1000_0000_0000_0000 {
                        parser.consume();
                        return Err(syntax_error(parser.loc(), "Too many significant digits"));
                    }
                    mantissa <<= 4;
                    mantissa |= hex_digit_value(ch);
                    exponent += 4;
                }
                '.' => {
                    state = State::OneDecimal;
                }
                'p' | 'P' => {
                    break;
                }
                ch if ch.is_alphanumeric() => {
                    parser.consume();
                    return Err(syntax_error(
                        parser.loc(),
                        format!("Invalid hexadecimal digit '{}'", ch).as_str(),
                    ));
                }
                _ => {
                    break;
                }
            },
            State::Decimal => match ch {
                '0' => {
                    exponent -= 4;
                    state = State::DigitDecimal;
                }
                ch if ch.is_ascii_hexdigit() => {
                    mantissa = hex_digit_value(ch);
                    exponent = exponent_adjust(mantissa) - 5;
                    state = State::OneDecimal;
                }
                'p' | 'P' => {
                    break;
                }
                ch if ch.is_alphanumeric() => {
                    parser.consume();
                    return Err(syntax_error(
                        parser.loc(),
                        format!("Invalid hexadecimal digit '{}'", ch).as_str(),
                    ));
                }
                _ => {
                    break;
                }
            },
            State::DigitDecimal => match ch {
                '0' => {
                    exponent -= 4;
                }
                ch if ch.is_ascii_hexdigit() => {
                    mantissa = hex_digit_value(ch);
                    exponent += exponent_adjust(mantissa) - 5;
                    state = State::OneDecimal;
                }
                'p' | 'P' => {
                    break;
                }
                ch if ch.is_alphanumeric() => {
                    parser.consume();
                    return Err(syntax_error(
                        parser.loc(),
                        format!("Invalid hexadecimal digit '{}'", ch).as_str(),
                    ));
                }
                _ => {
                    break;
                }
            },
            State::OneDecimal => match ch {
                '0' => {
                    if mantissa >= 0x1000_0000_0000_0000 {
                        parser.consume();
                        return Err(syntax_error(parser.loc(), "Too many significant digits"));
                    }
                    mantissa <<= 4;
                }
                ch if ch.is_ascii_hexdigit() => {
                    if mantissa >= 0x1000_0000_0000_0000 {
                        parser.consume();
                        return Err(syntax_error(parser.loc(), "Too many significant digits"));
                    }
                    mantissa <<= 4;
                    mantissa |= hex_digit_value(ch);
                }
                'p' | 'P' => {
                    break;
                }
                ch if ch.is_alphanumeric() => {
                    parser.consume();
                    return Err(syntax_error(
                        parser.loc(),
                        format!("Invalid hexadecimal digit '{}'", ch).as_str(),
                    ));
                }
                _ => {
                    break;
                }
            },
        }
        parser.consume();
    }

    // If we didn't find a digit then this is not a valid number.
    match state {
        State::None | State::Decimal => {
            return Err(syntax_error(
                parser.loc(),
                "Expected a number but did not find one",
            ));
        }
        _ => {}
    }

    // Look for and parse any power specification.
    let ch = parser.peek();
    if ch == 'p' || ch == 'P' {
        parser.consume();
        let loc = parser.loc();
        let negexp = if parser.peek_and_consume('-') {
            true
        } else {
            parser.peek_and_consume('+');
            false
        };
        let digits = if underscores {
            parser.take_while_unless(|ch| ch.is_ascii_digit(), |ch| ch == '_')
        } else {
            parser.take_while(|ch| ch.is_ascii_digit())
        };
        let power = match digits.parse::<i32>() {
            Ok(value) => value,
            Err(msg) => return Err(syntax_error(loc, &msg.to_string())),
        };
        // We computed a power of two above, but any explicit power is a power of 16, so we need
        // to multiply by four.
        if negexp {
            exponent -= power * 4;
        } else {
            exponent += power * 4;
        }
    }

    // If the mantissa is zero, return zero.  The exponent doesn't matter.
    match state {
        State::One | State::OneDecimal => {}
        _ => return Ok(0.0),
    }

    /*
     * At this point there is a leading one somehwere.
     *
     * Now we need to create a float from the pieces.  The first bit (63) is the sign bit.
     * The next eleven bits (62 through 52, inclusive) are the exponent biased by 1024.
     * The remaining 52 bits (51 through 0, inclusive) are the mantissa.
     *
     * 6666 5555 5555 5544 4444 4444 3333 3333 3322 2222 2222 1111 1111 1100 0000 0000
     * 3210 9876 5432 1098 7654 3210 9876 5432 1098 7654 3210 9876 5432 1098 7654 3210
     * seee eeee eeee mmmm mmmm mmmm mmmm mmmm mmmm mmmm mmmm mmmm mmmm mmmm mmmm mmmm
     */

    // Bias the exponent and then shift it into place.
    if !(f64::MIN_EXP - 1..f64::MAX_EXP).contains(&exponent) {
        return Err(syntax_error(parser.loc(), "Exponent is out of range"));
    }
    let mut bits = ((exponent + 1023) as u64) << 52;

    // Shift the mantissa so that the first non-zero digit is at position 52.  To do
    // that we get the number of leading zeros.  This means the first one (and there
    // must be one because we check above) will be at 63 - leading zero count.  That
    // is, we want 11 leading zeros.
    let leading_zeros = mantissa.leading_zeros();
    match leading_zeros.cmp(&11) {
        std::cmp::Ordering::Less => {
            mantissa >>= 11 - leading_zeros;
        }
        std::cmp::Ordering::Greater => {
            mantissa <<= leading_zeros - 11;
        }
        _ => {}
    }

    // Now discard the leading one from the mantissa.  There must be one since we dealt with zeros
    // above.
    mantissa &= 0x000f_ffff_ffff_ffff;

    // Add the mantissa to the bits.
    bits |= mantissa;

    // Add the sign bit.
    if negative {
        bits |= 0x8000_0000_0000_0000;
    }

    // Construct and return the double from the bits.
    Ok(f64::from_bits(bits))
}

#[cfg(test)]
mod test {
    use crate::{
        decoder::Decode,
        numbers::hexadecimal_float::{hex_digit_value, parse_hexadecimal_float},
        ParserCore,
    };

    fn parse(value: &str) -> ParserCore {
        let decoder = Decode::from_string(value);
        ParserCore::new("<string>>", decoder)
    }

    #[test]
    fn zero_test() {
        assert!(parse_hexadecimal_float(&mut parse(""), false, false).is_err());
        assert_eq!(
            parse_hexadecimal_float(&mut parse("0"), false, false).unwrap(),
            0.0
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("0"), true, false).unwrap(),
            0.0
        );
    }

    #[test]
    fn one_test() {
        assert_eq!(
            parse_hexadecimal_float(&mut parse("1"), false, false).unwrap(),
            1.0
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("1"), true, false).unwrap(),
            -1.0
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("01"), false, false).unwrap(),
            1.0
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("001"), true, false).unwrap(),
            -1.0
        );
    }

    #[test]
    fn integer_test_1() {
        assert_eq!(
            parse_hexadecimal_float(&mut parse("f"), false, false).unwrap(),
            15.0
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("8"), true, false).unwrap(),
            -8.0
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("81e4"), true, false).unwrap(),
            -33252.0
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("2120"), true, false).unwrap(),
            -8480.0
        );
    }

    #[test]
    fn integer_test_2() {
        assert_eq!(
            parse_hexadecimal_float(&mut parse("6f"), false, false).unwrap(),
            111.0
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("48_e2"), false, true).unwrap(),
            18658.0
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("197ffe664cb333"), true, false).unwrap(),
            -7177605032489779.0
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("2_9_9"), false, true).unwrap(),
            665.0
        );
    }

    #[test]
    fn fraction_test_1() {
        assert_eq!(
            parse_hexadecimal_float(&mut parse("0.1"), false, false).unwrap(),
            1.0 / 16.0
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("0.02"), false, false).unwrap(),
            2.0 / 16.0 / 16.0
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("0.8"), false, false).unwrap(),
            0.5
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("1.8"), false, false).unwrap(),
            1.5
        );
    }

    #[test]
    fn fraction_test_2() {
        assert_eq!(
            parse_hexadecimal_float(&mut parse("0.08"), false, false).unwrap(),
            0.03125
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("10.008"), false, false).unwrap(),
            16.001953125
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("e.e"), false, false).unwrap(),
            14.875
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("000.0000"), false, false).unwrap(),
            0.0
        );
    }

    #[test]
    fn fraction_test_3() {
        assert_eq!(
            parse_hexadecimal_float(&mut parse("0.8,"), false, false).unwrap(),
            0.5
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("1.8,"), false, false).unwrap(),
            1.5
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse(".08,"), false, false).unwrap(),
            1.0 / 32.0
        );
    }

    #[test]
    fn exponent_test_1() {
        assert_eq!(
            parse_hexadecimal_float(&mut parse("0p1000"), false, false).unwrap(),
            0.0
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("10p1"), false, false).unwrap(),
            256.0
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("10p-1"), false, false).unwrap(),
            1.0
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("0.001p3"), false, false).unwrap(),
            1.0
        );
    }

    #[test]
    fn exponent_test_2() {
        assert_eq!(
            parse_hexadecimal_float(&mut parse("1021p-3"), false, false).unwrap(),
            1.008056640625
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("44p-3"), false, false).unwrap(),
            0.0166015625
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("0.1p0,"), false, false).unwrap(),
            1.0 / 16.0
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("1.p0,"), false, false).unwrap(),
            1.0
        );
    }

    #[test]
    fn exponent_test_3() {
        assert_eq!(
            parse_hexadecimal_float(&mut parse("0.p12"), false, false).unwrap(),
            0.0
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse(".0p12"), false, false).unwrap(),
            0.0
        );
    }

    #[test]
    fn limits_test() {
        assert_eq!(
            parse_hexadecimal_float(&mut parse("f.f_ffff_ffff_ffffp255"), false, true).unwrap(),
            f64::MAX
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("f.f_ffff_ffff_ffffp255"), true, true).unwrap(),
            f64::MIN
        );
        assert_eq!(
            parse_hexadecimal_float(&mut parse("0.4p-255"), false, true).unwrap(),
            f64::MIN_POSITIVE
        );
    }

    #[test]
    fn overflow_test() {
        assert!(parse_hexadecimal_float(&mut parse("1p256"), false, false).is_err());
        assert!(parse_hexadecimal_float(&mut parse("2p-256"), false, false).is_err());
        assert_eq!(
            parse_hexadecimal_float(&mut parse("ff_ff_ff_ff_ff_ff_ff_ff"), false, true).unwrap(),
            1.844674407370955e19f64
        );
        assert!(
            parse_hexadecimal_float(&mut parse("ff_ff_ff_ff_ff_ff_ff_ff_1"), false, true).is_err()
        );
    }

    #[test]
    fn digit_test() {
        for ch in "0123456789abcdefABCDEF".chars() {
            assert_eq!(
                hex_digit_value(ch),
                u64::from_str_radix(&ch.to_string(), 16).unwrap()
            );
        }
        assert_eq!(hex_digit_value('*'), 255 as u64);
    }

    #[test]
    fn reject_test_1() {
        assert!(parse_hexadecimal_float(&mut parse("g"), false, false).is_err());
        assert!(parse_hexadecimal_float(&mut parse(","), false, false).is_err());
    }

    #[test]
    fn reject_test_2() {
        assert!(parse_hexadecimal_float(&mut parse("0g"), false, false).is_err());
        assert_eq!(
            parse_hexadecimal_float(&mut parse("0,"), false, false).unwrap(),
            0.0
        );
        assert!(parse_hexadecimal_float(&mut parse("1g"), false, false).is_err());
        assert_eq!(
            parse_hexadecimal_float(&mut parse("1,"), false, false).unwrap(),
            1.0
        );
    }

    #[test]
    fn reject_test_3() {
        assert!(parse_hexadecimal_float(&mut parse("0.g"), false, false).is_err());
        assert_eq!(
            parse_hexadecimal_float(&mut parse("0.,"), false, false).unwrap(),
            0.0
        );
        assert!(parse_hexadecimal_float(&mut parse("1.g"), false, false).is_err());
        assert_eq!(
            parse_hexadecimal_float(&mut parse("1.,"), false, false).unwrap(),
            1.0
        );
    }

    #[test]
    fn reject_test_4() {
        assert!(parse_hexadecimal_float(&mut parse("0.0g"), false, false).is_err());
        assert!(parse_hexadecimal_float(&mut parse("1.0g"), false, false).is_err());
    }

    #[test]
    fn reject_test_5() {
        assert!(parse_hexadecimal_float(&mut parse(".g"), false, false).is_err());
        assert!(parse_hexadecimal_float(&mut parse(".,"), false, false).is_err());
    }

    #[test]
    fn reject_test_6() {
        assert!(
            parse_hexadecimal_float(&mut parse("0.1_fffff_ffff_ffff_ffff_ffff"), false, true)
                .is_err()
        );
        assert!(
            parse_hexadecimal_float(&mut parse("1.1_fffff_ffff_ffff_ffff_ffff"), false, true)
                .is_err()
        );
        assert!(
            parse_hexadecimal_float(&mut parse("0.1_fffff_ffff_ffff_ffff_fff0"), false, true)
                .is_err()
        );
        assert!(
            parse_hexadecimal_float(&mut parse("1.1_fffff_ffff_ffff_ffff_fff0"), false, true)
                .is_err()
        );
    }

    #[test]
    fn reject_test_7() {
        assert!(parse_hexadecimal_float(&mut parse("11000_0000_0000_0000"), false, true).is_err());
        assert!(parse_hexadecimal_float(&mut parse("1.1000_0000_0000_0000"), false, true).is_err());
    }
}