serde_json/lexical/
algorithm.rs

1// Adapted from https://github.com/Alexhuszagh/rust-lexical.
2
3//! Algorithms to efficiently convert strings to floats.
4
5use super::bhcomp::*;
6use super::cached::*;
7use super::errors::*;
8use super::float::ExtendedFloat;
9use super::num::*;
10use super::small_powers::*;
11
12// FAST
13// ----
14
15/// Convert mantissa to exact value for a non-base2 power.
16///
17/// Returns the resulting float and if the value can be represented exactly.
18pub(crate) fn fast_path<F>(mantissa: u64, exponent: i32) -> Option<F>
19where
20    F: Float,
21{
22    // `mantissa >> (F::MANTISSA_SIZE+1) != 0` effectively checks if the
23    // value has a no bits above the hidden bit, which is what we want.
24    let (min_exp, max_exp) = F::exponent_limit();
25    let shift_exp = F::mantissa_limit();
26    let mantissa_size = F::MANTISSA_SIZE + 1;
27    if mantissa == 0 {
28        Some(F::ZERO)
29    } else if mantissa >> mantissa_size != 0 {
30        // Would require truncation of the mantissa.
31        None
32    } else if exponent == 0 {
33        // 0 exponent, same as value, exact representation.
34        let float = F::as_cast(mantissa);
35        Some(float)
36    } else if exponent >= min_exp && exponent <= max_exp {
37        // Value can be exactly represented, return the value.
38        // Do not use powi, since powi can incrementally introduce
39        // error.
40        let float = F::as_cast(mantissa);
41        Some(float.pow10(exponent))
42    } else if exponent >= 0 && exponent <= max_exp + shift_exp {
43        // Check to see if we have a disguised fast-path, where the
44        // number of digits in the mantissa is very small, but and
45        // so digits can be shifted from the exponent to the mantissa.
46        // https://www.exploringbinary.com/fast-path-decimal-to-floating-point-conversion/
47        let small_powers = POW10_64;
48        let shift = exponent - max_exp;
49        let power = small_powers[shift as usize];
50
51        // Compute the product of the power, if it overflows,
52        // prematurely return early, otherwise, if we didn't overshoot,
53        // we can get an exact value.
54        let value = match mantissa.checked_mul(power) {
55            None => return None,
56            Some(value) => value,
57        };
58        if value >> mantissa_size != 0 {
59            None
60        } else {
61            // Use powi, since it's correct, and faster on
62            // the fast-path.
63            let float = F::as_cast(value);
64            Some(float.pow10(max_exp))
65        }
66    } else {
67        // Cannot be exactly represented, exponent too small or too big,
68        // would require truncation.
69        None
70    }
71}
72
73// MODERATE
74// --------
75
76/// Multiply the floating-point by the exponent.
77///
78/// Multiply by pre-calculated powers of the base, modify the extended-
79/// float, and return if new value and if the value can be represented
80/// accurately.
81fn multiply_exponent_extended<F>(fp: &mut ExtendedFloat, exponent: i32, truncated: bool) -> bool
82where
83    F: Float,
84{
85    let powers = ExtendedFloat::get_powers();
86    let exponent = exponent.saturating_add(powers.bias);
87    let small_index = exponent % powers.step;
88    let large_index = exponent / powers.step;
89    if exponent < 0 {
90        // Guaranteed underflow (assign 0).
91        fp.mant = 0;
92        true
93    } else if large_index as usize >= powers.large.len() {
94        // Overflow (assign infinity)
95        fp.mant = 1 << 63;
96        fp.exp = 0x7FF;
97        true
98    } else {
99        // Within the valid exponent range, multiply by the large and small
100        // exponents and return the resulting value.
101
102        // Track errors to as a factor of unit in last-precision.
103        let mut errors: u32 = 0;
104        if truncated {
105            errors += u64::error_halfscale();
106        }
107
108        // Multiply by the small power.
109        // Check if we can directly multiply by an integer, if not,
110        // use extended-precision multiplication.
111        match fp
112            .mant
113            .overflowing_mul(powers.get_small_int(small_index as usize))
114        {
115            // Overflow, multiplication unsuccessful, go slow path.
116            (_, true) => {
117                fp.normalize();
118                fp.imul(&powers.get_small(small_index as usize));
119                errors += u64::error_halfscale();
120            }
121            // No overflow, multiplication successful.
122            (mant, false) => {
123                fp.mant = mant;
124                fp.normalize();
125            }
126        }
127
128        // Multiply by the large power
129        fp.imul(&powers.get_large(large_index as usize));
130        if errors > 0 {
131            errors += 1;
132        }
133        errors += u64::error_halfscale();
134
135        // Normalize the floating point (and the errors).
136        let shift = fp.normalize();
137        errors <<= shift;
138
139        u64::error_is_accurate::<F>(errors, fp)
140    }
141}
142
143/// Create a precise native float using an intermediate extended-precision float.
144///
145/// Return the float approximation and if the value can be accurately
146/// represented with mantissa bits of precision.
147#[inline]
148pub(crate) fn moderate_path<F>(
149    mantissa: u64,
150    exponent: i32,
151    truncated: bool,
152) -> (ExtendedFloat, bool)
153where
154    F: Float,
155{
156    let mut fp = ExtendedFloat {
157        mant: mantissa,
158        exp: 0,
159    };
160    let valid = multiply_exponent_extended::<F>(&mut fp, exponent, truncated);
161    (fp, valid)
162}
163
164// FALLBACK
165// --------
166
167/// Fallback path when the fast path does not work.
168///
169/// Uses the moderate path, if applicable, otherwise, uses the slow path
170/// as required.
171pub(crate) fn fallback_path<F>(
172    integer: &[u8],
173    fraction: &[u8],
174    mantissa: u64,
175    exponent: i32,
176    mantissa_exponent: i32,
177    truncated: bool,
178) -> F
179where
180    F: Float,
181{
182    // Moderate path (use an extended 80-bit representation).
183    let (fp, valid) = moderate_path::<F>(mantissa, mantissa_exponent, truncated);
184    if valid {
185        return fp.into_float::<F>();
186    }
187
188    // Slow path, fast path didn't work.
189    let b = fp.into_downward_float::<F>();
190    if b.is_special() {
191        // We have a non-finite number, we get to leave early.
192        b
193    } else {
194        bhcomp(b, integer, fraction, exponent)
195    }
196}