1//! Parse byte iterators to float.
2
3#![doc(hidden)]
4
5#[cfg(feature = "compact")]
6use crate::bellerophon::bellerophon;
7use crate::extended_float::{extended_to_float, ExtendedFloat};
8#[cfg(not(feature = "compact"))]
9use crate::lemire::lemire;
10use crate::num::Float;
11use crate::number::Number;
12use crate::slow::slow;
13
14/// Try to parse the significant digits quickly.
15///
16/// This attempts a very quick parse, to deal with common cases.
17///
18/// * `integer` - Slice containing the integer digits.
19/// * `fraction` - Slice containing the fraction digits.
20#[inline]
21fn parse_number_fast<'a, Iter1, Iter2>(
22 integer: Iter1,
23 fraction: Iter2,
24 exponent: i32,
25) -> Option<Number>
26where
27 Iter1: Iterator<Item = &'a u8>,
28 Iter2: Iterator<Item = &'a u8>,
29{
30 let mut num: Number = Number::default();
31 let mut integer_count: usize = 0;
32 let mut fraction_count: usize = 0;
33 for &c: u8 in integer {
34 integer_count += 1;
35 let digit: u8 = c - b'0';
36 num.mantissa = num.mantissa.wrapping_mul(10).wrapping_add(digit as u64);
37 }
38 for &c: u8 in fraction {
39 fraction_count += 1;
40 let digit: u8 = c - b'0';
41 num.mantissa = num.mantissa.wrapping_mul(10).wrapping_add(digit as u64);
42 }
43
44 if integer_count + fraction_count <= 19 {
45 // Can't overflow, since must be <= 19.
46 num.exponent = exponent.saturating_sub(fraction_count as i32);
47 Some(num)
48 } else {
49 None
50 }
51}
52
53/// Parse the significant digits of the float and adjust the exponent.
54///
55/// * `integer` - Slice containing the integer digits.
56/// * `fraction` - Slice containing the fraction digits.
57#[inline]
58fn parse_number<'a, Iter1, Iter2>(mut integer: Iter1, mut fraction: Iter2, exponent: i32) -> Number
59where
60 Iter1: Iterator<Item = &'a u8> + Clone,
61 Iter2: Iterator<Item = &'a u8> + Clone,
62{
63 // NOTE: for performance, we do this in 2 passes:
64 if let Some(num) = parse_number_fast(integer.clone(), fraction.clone(), exponent) {
65 return num;
66 }
67
68 // Can only add 19 digits.
69 let mut num = Number::default();
70 let mut count = 0;
71 while let Some(&c) = integer.next() {
72 count += 1;
73 if count == 20 {
74 // Only the integer digits affect the exponent.
75 num.many_digits = true;
76 num.exponent = exponent.saturating_add(into_i32(1 + integer.count()));
77 return num;
78 } else {
79 let digit = c - b'0';
80 num.mantissa = num.mantissa * 10 + digit as u64;
81 }
82 }
83
84 // Skip leading fraction zeros.
85 // This is required otherwise we might have a 0 mantissa and many digits.
86 let mut fraction_count: usize = 0;
87 if count == 0 {
88 for &c in &mut fraction {
89 fraction_count += 1;
90 if c != b'0' {
91 count += 1;
92 let digit = c - b'0';
93 num.mantissa = num.mantissa * 10 + digit as u64;
94 break;
95 }
96 }
97 }
98 for c in fraction {
99 fraction_count += 1;
100 count += 1;
101 if count == 20 {
102 num.many_digits = true;
103 // This can't wrap, since we have at most 20 digits.
104 // We've adjusted the exponent too high by `fraction_count - 1`.
105 // Note: -1 is due to incrementing this loop iteration, which we
106 // didn't use.
107 num.exponent = exponent.saturating_sub(fraction_count as i32 - 1);
108 return num;
109 } else {
110 let digit = c - b'0';
111 num.mantissa = num.mantissa * 10 + digit as u64;
112 }
113 }
114
115 // No truncated digits: easy.
116 // Cannot overflow: <= 20 digits.
117 num.exponent = exponent.saturating_sub(fraction_count as i32);
118 num
119}
120
121/// Parse float from extracted float components.
122///
123/// * `integer` - Cloneable, forward iterator over integer digits.
124/// * `fraction` - Cloneable, forward iterator over integer digits.
125/// * `exponent` - Parsed, 32-bit exponent.
126///
127/// # Preconditions
128/// 1. The integer should not have leading zeros.
129/// 2. The fraction should not have trailing zeros.
130/// 3. All bytes in `integer` and `fraction` should be valid digits,
131/// in the range [`b'0', b'9'].
132///
133/// # Panics
134///
135/// Although passing garbage input will not cause memory safety issues,
136/// it is very likely to cause a panic with a large number of digits, or
137/// in debug mode. The big-integer arithmetic without the `alloc` feature
138/// assumes a maximum, fixed-width input, which assumes at maximum a
139/// value of `10^(769 + 342)`, or ~4000 bits of storage. Passing in
140/// nonsensical digits may require up to ~6000 bits of storage, which will
141/// panic when attempting to add it to the big integer. It is therefore
142/// up to the caller to validate this input.
143///
144/// We cannot efficiently remove trailing zeros while only accepting a
145/// forward iterator.
146pub fn parse_float<'a, F, Iter1, Iter2>(integer: Iter1, fraction: Iter2, exponent: i32) -> F
147where
148 F: Float,
149 Iter1: Iterator<Item = &'a u8> + Clone,
150 Iter2: Iterator<Item = &'a u8> + Clone,
151{
152 // Parse the mantissa and attempt the fast and moderate-path algorithms.
153 let num: Number = parse_number(integer.clone(), fraction.clone(), exponent);
154 // Try the fast-path algorithm.
155 if let Some(value: F) = num.try_fast_path() {
156 return value;
157 }
158
159 // Now try the moderate path algorithm.
160 let mut fp: ExtendedFloat = moderate_path::<F>(&num);
161 if fp.exp < 0 {
162 // Undo the invalid extended float biasing.
163 fp.exp -= F::INVALID_FP;
164 fp = slow::<F, _, _>(num, fp, integer, fraction);
165 }
166
167 // Unable to correctly round the float using the fast or moderate algorithms.
168 // Fallback to a slower, but always correct algorithm. If we have
169 // lossy, we can't be here.
170 extended_to_float::<F>(fp)
171}
172
173/// Wrapper for different moderate-path algorithms.
174/// A return exponent of `-1` indicates an invalid value.
175#[inline]
176pub fn moderate_path<F: Float>(num: &Number) -> ExtendedFloat {
177 #[cfg(not(feature = "compact"))]
178 return lemire::<F>(num);
179
180 #[cfg(feature = "compact")]
181 return bellerophon::<F>(num);
182}
183
184/// Convert usize into i32 without overflow.
185///
186/// This is needed to ensure when adjusting the exponent relative to
187/// the mantissa we do not overflow for comically-long exponents.
188#[inline]
189fn into_i32(value: usize) -> i32 {
190 if value > i32::max_value() as usize {
191 i32::max_value()
192 } else {
193 value as i32
194 }
195}
196
197// Add digit to mantissa.
198#[inline]
199pub fn add_digit(value: u64, digit: u8) -> Option<u64> {
200 value.checked_mul(10)?.checked_add(digit as u64)
201}
202