lexical_parse_float/
binary.rs

Help
1//! Optimized float parser for radixes powers of 2.
2//!
3//! Note: this does not require the mantissa radix and the
4//! exponent base to be the same.
5
6#![cfg(feature = "power-of-two")]
7#![doc(hidden)]
8
9#[cfg(not(feature = "compact"))]
10use lexical_parse_integer::algorithm;
11use lexical_util::digit::char_to_valid_digit_const;
12use lexical_util::format::NumberFormat;
13use lexical_util::iterator::{AsBytes, DigitsIter};
14use lexical_util::step::u64_step;
15
16use crate::float::{ExtendedFloat80, RawFloat};
17use crate::mask::lower_n_halfway;
18use crate::number::Number;
19use crate::shared;
20
21// ALGORITHM
22// ---------
23
24/// Algorithm specialized for radixes of powers-of-two.
25#[cfg_attr(not(feature = "compact"), inline(always))]
26pub fn binary<F: RawFloat, const FORMAT: u128>(num: &Number, lossy: bool) -> ExtendedFloat80 {
27    let format = NumberFormat::<{ FORMAT }> {};
28    debug_assert!(
29        matches!(format.radix(), 2 | 4 | 8 | 16 | 32),
30        "algorithm requires a power-of-two"
31    );
32
33    let fp_zero = ExtendedFloat80 {
34        mant: 0,
35        exp: 0,
36    };
37
38    // Normalize our mantissa for simpler results.
39    let ctlz = num.mantissa.leading_zeros();
40    let mantissa = num.mantissa << ctlz;
41
42    // Quick check if we're close to a halfway point.
43    // Since we're using powers-of-two, we can clearly tell if we're at
44    // a halfway point, unless it's even and we're exactly halfway so far.
45    // This is true even for radixes like 8 and 32, where `log2(radix)`
46    // is not a power-of-two. If it's odd and we're at halfway, we'll
47    // always round-up **anyway**.
48    //
49    // We need to check the truncated bits are equal to `0b100000....`,
50    // if it's above that, always round-up. If it's odd, we can always
51    // disambiguate the float. If it's even, and exactly halfway, this
52    // step fails.
53    let power2 = shared::calculate_power2::<F, FORMAT>(num.exponent, ctlz);
54    if -power2 + 1 >= 64 {
55        // Have more than 63 bits below the minimum exponent, must be 0.
56        // Since we can't have partial digit rounding, this is true always
57        // if the power-of-two >= 64.
58        return fp_zero;
59    }
60
61    // Get our shift to shift the digits to the hidden bit, or correct spot.
62    // This differs for denormal floats, so do that carefully, but that's
63    // relative to the current leading zeros of the float.
64    let shift = shared::calculate_shift::<F>(power2);
65
66    // Determine if we can see if we're at a halfway point.
67    let last_bit = 1u64 << shift;
68    let truncated = last_bit - 1;
69    let halfway = lower_n_halfway(shift as u64);
70    let is_even = mantissa & last_bit == 0;
71    let is_halfway = mantissa & truncated == halfway;
72    if !lossy && is_even && is_halfway && num.many_digits {
73        // Exactly halfway and even, cannot safely determine our representation.
74        // Bias the exponent so we know it's invalid.
75        return ExtendedFloat80 {
76            mant: mantissa,
77            exp: power2 + shared::INVALID_FP,
78        };
79    }
80
81    // Shift our digits into place, and round up if needed.
82    let is_above = mantissa & truncated > halfway;
83    let round_up = is_above || (!is_even && is_halfway);
84    let mut fp = ExtendedFloat80 {
85        mant: mantissa,
86        exp: power2,
87    };
88
89    shared::round::<F, _>(&mut fp, |f, s| {
90        shared::round_nearest_tie_even(f, s, |_, _, _| round_up);
91    });
92    fp
93}
94
95/// Iteratively parse and consume digits without overflowing.
96///
97/// We're guaranteed to have a large number of digits here
98/// (in general, 20+ or much higher), due to how close we
99/// are to a halfway representation, so an unchecked loop
100/// optimization isn't worth it.
101#[cfg_attr(not(feature = "compact"), inline(always))]
102#[allow(unused_mut)]
103pub fn parse_u64_digits<'a, Iter, const FORMAT: u128>(
104    mut iter: Iter,
105    mantissa: &mut u64,
106    step: &mut usize,
107    overflowed: &mut bool,
108    zero: &mut bool,
109) where
110    Iter: DigitsIter<'a>,
111{
112    let format = NumberFormat::<{ FORMAT }> {};
113    let radix = format.radix() as u64;
114
115    // Try to parse 8 digits at a time, if we can.
116    #[cfg(not(feature = "compact"))]
117    if can_try_parse_multidigit!(iter, radix) {
118        debug_assert!(radix < 16, "larger radices will wrap on radix^8");
119        let radix8 = format.radix8() as u64;
120        while *step > 8 {
121            if let Some(v) = algorithm::try_parse_8digits::<u64, _, FORMAT>(&mut iter) {
122                *mantissa = mantissa.wrapping_mul(radix8).wrapping_add(v);
123                *step -= 8;
124            } else {
125                break;
126            }
127        }
128    }
129
130    // Parse single digits at a time.
131    for &c in iter {
132        let digit = char_to_valid_digit_const(c, radix as u32);
133        if !*overflowed {
134            let result = mantissa.checked_mul(radix).and_then(|x| x.checked_add(digit as u64));
135            if let Some(mant) = result {
136                *mantissa = mant;
137            } else {
138                *overflowed = true;
139                *zero &= digit == 0;
140            }
141        } else {
142            *zero &= digit == 0;
143        }
144        *step = step.saturating_sub(1);
145    }
146}
147
148/// Fallback, slow algorithm optimized for powers-of-two.
149///
150/// This avoids the need for arbitrary-precision arithmetic, since the result
151/// will always be a near-halfway representation where rounded-down it's even.
152#[cfg_attr(not(feature = "compact"), inline(always))]
153pub fn slow_binary<F: RawFloat, const FORMAT: u128>(num: Number) -> ExtendedFloat80 {
154    let format = NumberFormat::<{ FORMAT }> {};
155    let radix = format.radix();
156    debug_assert!(matches!(radix, 2 | 4 | 8 | 16 | 32), "algorithm requires a power-of-two");
157
158    // This assumes the sign bit has already been parsed, and we're
159    // starting with the integer digits, and the float format has been
160    // correctly validated.
161
162    // This is quite simple: parse till we get overflow, check if all
163    // the remaining digits are zero/non-zero, and determine if we round-up
164    // or down as a result.
165
166    let mut mantissa = 0_u64;
167    let mut overflow = false;
168    let mut zero = true;
169
170    // Parse the integer digits.
171    let mut step = u64_step(radix);
172    let mut integer = num.integer.bytes::<FORMAT>();
173    integer.integer_iter().skip_zeros();
174    parse_u64_digits::<_, FORMAT>(
175        integer.integer_iter(),
176        &mut mantissa,
177        &mut step,
178        &mut overflow,
179        &mut zero,
180    );
181
182    // Parse the fraction digits.
183    if let Some(fraction) = num.fraction {
184        let mut fraction = fraction.bytes::<FORMAT>();
185        if mantissa == 0 {
186            fraction.fraction_iter().skip_zeros();
187        }
188        parse_u64_digits::<_, FORMAT>(
189            fraction.fraction_iter(),
190            &mut mantissa,
191            &mut step,
192            &mut overflow,
193            &mut zero,
194        );
195    }
196
197    // Note: we're not guaranteed to have overflowed here, although it's
198    // very, very likely. We can also skip the exponent, since we already
199    // know it, and we already know the total parsed digits.
200
201    // Normalize our mantissa for simpler results.
202    let ctlz = mantissa.leading_zeros();
203    mantissa <<= ctlz;
204    let power2 = shared::calculate_power2::<F, FORMAT>(num.exponent, ctlz);
205
206    let mut fp = ExtendedFloat80 {
207        mant: mantissa,
208        exp: power2,
209    };
210
211    shared::round::<F, _>(&mut fp, |f, s| {
212        shared::round_nearest_tie_even(f, s, |_, _, _| !zero);
213    });
214    fp
215}
lexical_parse_float/binary.rs

lexical_parse_float/
binary.rs
