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.
56#![cfg(feature = "power-of-two")]
7#![doc(hidden)]
89#[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;
1516use crate::float::{ExtendedFloat80, RawFloat};
17use crate::mask::lower_n_halfway;
18use crate::number::Number;
19use crate::shared;
2021// ALGORITHM
22// ---------
2324/// 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 {
27let format = NumberFormat::<{ FORMAT }> {};
28debug_assert!(
29matches!(format.radix(), 2 | 4 | 8 | 16 | 32),
30"algorithm requires a power-of-two"
31);
3233let fp_zero = ExtendedFloat80 {
34 mant: 0,
35 exp: 0,
36 };
3738// Normalize our mantissa for simpler results.
39let ctlz = num.mantissa.leading_zeros();
40let mantissa = num.mantissa << ctlz;
4142// 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.
53let power2 = shared::calculate_power2::<F, FORMAT>(num.exponent, ctlz);
54if -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.
58return fp_zero;
59 }
6061// 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.
64let shift = shared::calculate_shift::<F>(power2);
6566// Determine if we can see if we're at a halfway point.
67let last_bit = 1u64 << shift;
68let truncated = last_bit - 1;
69let halfway = lower_n_halfway(shift as u64);
70let is_even = mantissa & last_bit == 0;
71let is_halfway = mantissa & truncated == halfway;
72if !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.
75return ExtendedFloat80 {
76 mant: mantissa,
77 exp: power2 + shared::INVALID_FP,
78 };
79 }
8081// Shift our digits into place, and round up if needed.
82let is_above = mantissa & truncated > halfway;
83let round_up = is_above || (!is_even && is_halfway);
84let mut fp = ExtendedFloat80 {
85 mant: mantissa,
86 exp: power2,
87 };
8889 shared::round::<F, _>(&mut fp, |f, s| {
90 shared::round_nearest_tie_even(f, s, |_, _, _| round_up);
91 });
92 fp
93}
9495/// 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>(
104mut iter: Iter,
105 mantissa: &mut u64,
106 step: &mut usize,
107 overflowed: &mut bool,
108 zero: &mut bool,
109) where
110Iter: DigitsIter<'a>,
111{
112let format = NumberFormat::<{ FORMAT }> {};
113let radix = format.radix() as u64;
114115// Try to parse 8 digits at a time, if we can.
116#[cfg(not(feature = "compact"))]
117if can_try_parse_multidigit!(iter, radix) {
118debug_assert!(radix < 16, "larger radices will wrap on radix^8");
119let radix8 = format.radix8() as u64;
120while *step > 8 {
121if 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 {
125break;
126 }
127 }
128 }
129130// Parse single digits at a time.
131for &c in iter {
132let digit = char_to_valid_digit_const(c, radix as u32);
133if !*overflowed {
134let result = mantissa.checked_mul(radix).and_then(|x| x.checked_add(digit as u64));
135if 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}
147148/// 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 {
154let format = NumberFormat::<{ FORMAT }> {};
155let radix = format.radix();
156debug_assert!(matches!(radix, 2 | 4 | 8 | 16 | 32), "algorithm requires a power-of-two");
157158// 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.
161162 // 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.
165166let mut mantissa = 0_u64;
167let mut overflow = false;
168let mut zero = true;
169170// Parse the integer digits.
171let mut step = u64_step(radix);
172let 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 );
181182// Parse the fraction digits.
183if let Some(fraction) = num.fraction {
184let mut fraction = fraction.bytes::<FORMAT>();
185if 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 }
196197// 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.
200201 // Normalize our mantissa for simpler results.
202let ctlz = mantissa.leading_zeros();
203 mantissa <<= ctlz;
204let power2 = shared::calculate_power2::<F, FORMAT>(num.exponent, ctlz);
205206let mut fp = ExtendedFloat80 {
207 mant: mantissa,
208 exp: power2,
209 };
210211 shared::round::<F, _>(&mut fp, |f, s| {
212 shared::round_nearest_tie_even(f, s, |_, _, _| !zero);
213 });
214 fp
215}