lexical_parse_float/

binary.rs

//! Optimized float parser for radixes powers of 2.
//!
//! Note: this does not require the mantissa radix and the
//! exponent base to be the same.

#![cfg(feature = "power-of-two")]
#![doc(hidden)]

use crate::float::{ExtendedFloat80, RawFloat};
use crate::mask::lower_n_halfway;
use crate::number::Number;
use crate::shared;
#[cfg(not(feature = "compact"))]
use lexical_parse_integer::algorithm;
use lexical_util::digit::char_to_valid_digit_const;
use lexical_util::format::NumberFormat;
use lexical_util::iterator::{AsBytes, BytesIter};
use lexical_util::step::u64_step;

// ALGORITHM
// ---------

/// Algorithm specialized for radixes of powers-of-two.
#[inline]
pub fn binary<F: RawFloat, const FORMAT: u128>(num: &Number, lossy: bool) -> ExtendedFloat80 {
    let format = NumberFormat::<{ FORMAT }> {};
    debug_assert!(matches!(format.radix(), 2 | 4 | 8 | 16 | 32));

    let fp_zero = ExtendedFloat80 {
        mant: 0,
        exp: 0,
    };

    // Normalize our mantissa for simpler results.
    let ctlz = num.mantissa.leading_zeros();
    let mantissa = num.mantissa << ctlz;

    // Quick check if we're close to a halfway point.
    // Since we're using powers-of-two, we can clearly tell if we're at
    // a halfway point, unless it's even and we're exactly halfway so far.
    // This is true even for radixes like 8 and 32, where `log2(radix)`
    // is not a power-of-two. If it's odd and we're at halfway, we'll
    // always round-up **anyway**.
    //
    // We need to check the truncated bits are equal to 0b100000....,
    // if it's above that, always round-up. If it's odd, we can always
    // disambiguate the float. If it's even, and exactly halfway, this
    // step fails.
    let power2 = shared::calculate_power2::<F, FORMAT>(num.exponent, ctlz);
    if -power2 + 1 >= 64 {
        // Have more than 63 bits below the minimum exponent, must be 0.
        // Since we can't have partial digit rounding, this is true always
        // if the power-of-two >= 64.
        return fp_zero;
    }

    // Get our shift to shift the digits to the hidden bit, or correct spot.
    // This differs for denormal floats, so do that carefully, but that's
    // relative to the current leading zeros of the float.
    let shift = shared::calculate_shift::<F>(power2);

    // Determine if we can see if we're at a halfway point.
    let last_bit = 1u64 << shift;
    let truncated = last_bit - 1;
    let halfway = lower_n_halfway(shift as u64);
    let is_even = mantissa & last_bit == 0;
    let is_halfway = mantissa & truncated == halfway;
    if !lossy && is_even && is_halfway && num.many_digits {
        // Exactly halfway and even, cannot safely determine our representation.
        // Bias the exponent so we know it's invalid.
        return ExtendedFloat80 {
            mant: mantissa,
            exp: power2 + shared::INVALID_FP,
        };
    }

    // Shift our digits into place, and round up if needed.
    let is_above = mantissa & truncated > halfway;
    let round_up = is_above || (!is_even && is_halfway);
    let mut fp = ExtendedFloat80 {
        mant: mantissa,
        exp: power2,
    };

    shared::round::<F, _>(&mut fp, |f, s| {
        shared::round_nearest_tie_even(f, s, |_, _, _| round_up);
    });
    fp
}

/// Iteratively parse and consume digits without overflowing.
#[inline]
#[allow(unused_mut)]
pub fn parse_u64_digits<'a, Iter, const FORMAT: u128>(
    mut iter: Iter,
    mantissa: &mut u64,
    step: &mut usize,
    overflowed: &mut bool,
    zero: &mut bool,
) where
    Iter: BytesIter<'a>,
{
    let format = NumberFormat::<{ FORMAT }> {};
    let radix = format.radix() as u64;

    // Try to parse 8 digits at a time, if we can.
    #[cfg(not(feature = "compact"))]
    if can_try_parse_8digits!(iter, radix) {
        let radix2 = radix.wrapping_mul(radix);
        let radix4 = radix2.wrapping_mul(radix2);
        let radix8 = radix4.wrapping_mul(radix4);
        while *step > 8 {
            if let Some(v) = algorithm::try_parse_8digits::<u64, _, FORMAT>(&mut iter) {
                *mantissa = mantissa.wrapping_mul(radix8).wrapping_add(v);
                *step -= 8;
            } else {
                break;
            }
        }
    }

    // Parse single digits at a time.
    for &c in iter {
        let digit = char_to_valid_digit_const(c, radix as _);
        if !*overflowed {
            let result = mantissa.checked_mul(radix as _).and_then(|x| x.checked_add(digit as _));
            if let Some(mant) = result {
                *mantissa = mant;
            } else {
                *overflowed = true;
                *zero &= digit == 0;
            }
        } else {
            *zero &= digit == 0;
        }
        *step = step.saturating_sub(1);
    }
}

/// Fallback, slow algorithm optimized for powers-of-two.
///
/// This avoids the need for arbitrary-precision arithmetic, since the result
/// will always be a near-halfway representation where rounded-down it's even.
#[inline]
pub fn slow_binary<F: RawFloat, const FORMAT: u128>(num: Number) -> ExtendedFloat80 {
    let format = NumberFormat::<{ FORMAT }> {};
    let radix = format.radix();
    debug_assert!(matches!(radix, 2 | 4 | 8 | 16 | 32));

    // This assumes the sign bit has already been parsed, and we're
    // starting with the integer digits, and the float format has been
    // correctly validated.

    // This is quite simple: parse till we get overflow, check if all
    // the remaining digits are zero/non-zero, and determine if we round-up
    // or down as a result.

    let mut mantissa = 0_u64;
    let mut overflow = false;
    let mut zero = true;

    // Parse the integer digits.
    let mut step = u64_step(radix);
    let mut integer = num.integer.bytes::<FORMAT>();
    integer.integer_iter().skip_zeros();
    parse_u64_digits::<_, FORMAT>(
        integer.integer_iter(),
        &mut mantissa,
        &mut step,
        &mut overflow,
        &mut zero,
    );

    // Parse the fraction digits.
    if let Some(fraction) = num.fraction {
        let mut fraction = fraction.bytes::<FORMAT>();
        if mantissa == 0 {
            fraction.fraction_iter().skip_zeros();
        }
        parse_u64_digits::<_, FORMAT>(
            fraction.fraction_iter(),
            &mut mantissa,
            &mut step,
            &mut overflow,
            &mut zero,
        );
    }

    // Note: we're not guaranteed to have overflowed here, although it's
    // very, very likely. We can also skip the exponent, since we already
    // know it, and we already know the total parsed digits.

    // Normalize our mantissa for simpler results.
    let ctlz = mantissa.leading_zeros();
    mantissa <<= ctlz;
    let power2 = shared::calculate_power2::<F, FORMAT>(num.exponent, ctlz);

    let mut fp = ExtendedFloat80 {
        mant: mantissa,
        exp: power2,
    };

    shared::round::<F, _>(&mut fp, |f, s| {
        shared::round_nearest_tie_even(f, s, |_, _, _| !zero);
    });
    fp
}