Debian Codegraph @

.cargo/vendor/serde_json/src/lexical/algorithm.rs

raw
1 // Adapted from https://github.com/Alexhuszagh/rust-lexical.
2
3 //! Algorithms to efficiently convert strings to floats.
4
5 use super::bhcomp::*;
6 use super::cached::*;
7 use super::errors::*;
8 use super::float::ExtendedFloat;
9 use super::num::*;
10 use 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.
18 pub(crate) fn fast_path<F>(mantissa: u64, exponent: i32) -> Option<F>
19 where
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.
81 fn multiply_exponent_extended<F>(fp: &mut ExtendedFloat, exponent: i32, truncated: bool) -> bool
82 where
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]
148 pub(crate) fn moderate_path<F>(
149 mantissa: u64,
150 exponent: i32,
151 truncated: bool,
152 ) -> (ExtendedFloat, bool)
153 where
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.
171 pub(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
179 where
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 }