1 | // Adapted from https://github.com/Alexhuszagh/rust-lexical. |
2 | |
3 | //! Utilities for Rust numbers. |
4 | |
5 | use core::ops; |
6 | |
7 | /// Precalculated values of radix**i for i in range [0, arr.len()-1]. |
8 | /// Each value can be **exactly** represented as that type. |
9 | const F32_POW10: [f32; 11] = [ |
10 | 1.0, |
11 | 10.0, |
12 | 100.0, |
13 | 1000.0, |
14 | 10000.0, |
15 | 100000.0, |
16 | 1000000.0, |
17 | 10000000.0, |
18 | 100000000.0, |
19 | 1000000000.0, |
20 | 10000000000.0, |
21 | ]; |
22 | |
23 | /// Precalculated values of radix**i for i in range [0, arr.len()-1]. |
24 | /// Each value can be **exactly** represented as that type. |
25 | const F64_POW10: [f64; 23] = [ |
26 | 1.0, |
27 | 10.0, |
28 | 100.0, |
29 | 1000.0, |
30 | 10000.0, |
31 | 100000.0, |
32 | 1000000.0, |
33 | 10000000.0, |
34 | 100000000.0, |
35 | 1000000000.0, |
36 | 10000000000.0, |
37 | 100000000000.0, |
38 | 1000000000000.0, |
39 | 10000000000000.0, |
40 | 100000000000000.0, |
41 | 1000000000000000.0, |
42 | 10000000000000000.0, |
43 | 100000000000000000.0, |
44 | 1000000000000000000.0, |
45 | 10000000000000000000.0, |
46 | 100000000000000000000.0, |
47 | 1000000000000000000000.0, |
48 | 10000000000000000000000.0, |
49 | ]; |
50 | |
51 | /// Type that can be converted to primitive with `as`. |
52 | pub trait AsPrimitive: Sized + Copy + PartialOrd { |
53 | fn as_u32(self) -> u32; |
54 | fn as_u64(self) -> u64; |
55 | fn as_u128(self) -> u128; |
56 | fn as_usize(self) -> usize; |
57 | fn as_f32(self) -> f32; |
58 | fn as_f64(self) -> f64; |
59 | } |
60 | |
61 | macro_rules! as_primitive_impl { |
62 | ($($ty:ident)*) => { |
63 | $( |
64 | impl AsPrimitive for $ty { |
65 | #[inline] |
66 | fn as_u32(self) -> u32 { |
67 | self as u32 |
68 | } |
69 | |
70 | #[inline] |
71 | fn as_u64(self) -> u64 { |
72 | self as u64 |
73 | } |
74 | |
75 | #[inline] |
76 | fn as_u128(self) -> u128 { |
77 | self as u128 |
78 | } |
79 | |
80 | #[inline] |
81 | fn as_usize(self) -> usize { |
82 | self as usize |
83 | } |
84 | |
85 | #[inline] |
86 | fn as_f32(self) -> f32 { |
87 | self as f32 |
88 | } |
89 | |
90 | #[inline] |
91 | fn as_f64(self) -> f64 { |
92 | self as f64 |
93 | } |
94 | } |
95 | )* |
96 | }; |
97 | } |
98 | |
99 | as_primitive_impl! { u32 u64 u128 usize f32 f64 } |
100 | |
101 | /// An interface for casting between machine scalars. |
102 | pub trait AsCast: AsPrimitive { |
103 | /// Creates a number from another value that can be converted into |
104 | /// a primitive via the `AsPrimitive` trait. |
105 | fn as_cast<N: AsPrimitive>(n: N) -> Self; |
106 | } |
107 | |
108 | macro_rules! as_cast_impl { |
109 | ($ty:ident, $method:ident) => { |
110 | impl AsCast for $ty { |
111 | #[inline] |
112 | fn as_cast<N: AsPrimitive>(n: N) -> Self { |
113 | n.$method() |
114 | } |
115 | } |
116 | }; |
117 | } |
118 | |
119 | as_cast_impl!(u32, as_u32); |
120 | as_cast_impl!(u64, as_u64); |
121 | as_cast_impl!(u128, as_u128); |
122 | as_cast_impl!(usize, as_usize); |
123 | as_cast_impl!(f32, as_f32); |
124 | as_cast_impl!(f64, as_f64); |
125 | |
126 | /// Numerical type trait. |
127 | pub trait Number: AsCast + ops::Add<Output = Self> {} |
128 | |
129 | macro_rules! number_impl { |
130 | ($($ty:ident)*) => { |
131 | $( |
132 | impl Number for $ty {} |
133 | )* |
134 | }; |
135 | } |
136 | |
137 | number_impl! { u32 u64 u128 usize f32 f64 } |
138 | |
139 | /// Defines a trait that supports integral operations. |
140 | pub trait Integer: Number + ops::BitAnd<Output = Self> + ops::Shr<i32, Output = Self> { |
141 | const ZERO: Self; |
142 | } |
143 | |
144 | macro_rules! integer_impl { |
145 | ($($ty:tt)*) => { |
146 | $( |
147 | impl Integer for $ty { |
148 | const ZERO: Self = 0; |
149 | } |
150 | )* |
151 | }; |
152 | } |
153 | |
154 | integer_impl! { u32 u64 u128 usize } |
155 | |
156 | /// Type trait for the mantissa type. |
157 | pub trait Mantissa: Integer { |
158 | /// Mask to extract the high bits from the integer. |
159 | const HIMASK: Self; |
160 | /// Mask to extract the low bits from the integer. |
161 | const LOMASK: Self; |
162 | /// Full size of the integer, in bits. |
163 | const FULL: i32; |
164 | /// Half size of the integer, in bits. |
165 | const HALF: i32 = Self::FULL / 2; |
166 | } |
167 | |
168 | impl Mantissa for u64 { |
169 | const HIMASK: u64 = 0xFFFFFFFF00000000; |
170 | const LOMASK: u64 = 0x00000000FFFFFFFF; |
171 | const FULL: i32 = 64; |
172 | } |
173 | |
174 | /// Get exact exponent limit for radix. |
175 | pub trait Float: Number { |
176 | /// Unsigned type of the same size. |
177 | type Unsigned: Integer; |
178 | |
179 | /// Literal zero. |
180 | const ZERO: Self; |
181 | /// Maximum number of digits that can contribute in the mantissa. |
182 | /// |
183 | /// We can exactly represent a float in radix `b` from radix 2 if |
184 | /// `b` is divisible by 2. This function calculates the exact number of |
185 | /// digits required to exactly represent that float. |
186 | /// |
187 | /// According to the "Handbook of Floating Point Arithmetic", |
188 | /// for IEEE754, with emin being the min exponent, p2 being the |
189 | /// precision, and b being the radix, the number of digits follows as: |
190 | /// |
191 | /// `−emin + p2 + ⌊(emin + 1) log(2, b) − log(1 − 2^(−p2), b)⌋` |
192 | /// |
193 | /// For f32, this follows as: |
194 | /// emin = -126 |
195 | /// p2 = 24 |
196 | /// |
197 | /// For f64, this follows as: |
198 | /// emin = -1022 |
199 | /// p2 = 53 |
200 | /// |
201 | /// In Python: |
202 | /// `-emin + p2 + math.floor((emin+1)*math.log(2, b) - math.log(1-2**(-p2), b))` |
203 | /// |
204 | /// This was used to calculate the maximum number of digits for [2, 36]. |
205 | const MAX_DIGITS: usize; |
206 | |
207 | // MASKS |
208 | |
209 | /// Bitmask for the sign bit. |
210 | const SIGN_MASK: Self::Unsigned; |
211 | /// Bitmask for the exponent, including the hidden bit. |
212 | const EXPONENT_MASK: Self::Unsigned; |
213 | /// Bitmask for the hidden bit in exponent, which is an implicit 1 in the fraction. |
214 | const HIDDEN_BIT_MASK: Self::Unsigned; |
215 | /// Bitmask for the mantissa (fraction), excluding the hidden bit. |
216 | const MANTISSA_MASK: Self::Unsigned; |
217 | |
218 | // PROPERTIES |
219 | |
220 | /// Positive infinity as bits. |
221 | const INFINITY_BITS: Self::Unsigned; |
222 | /// Positive infinity as bits. |
223 | const NEGATIVE_INFINITY_BITS: Self::Unsigned; |
224 | /// Size of the significand (mantissa) without hidden bit. |
225 | const MANTISSA_SIZE: i32; |
226 | /// Bias of the exponet |
227 | const EXPONENT_BIAS: i32; |
228 | /// Exponent portion of a denormal float. |
229 | const DENORMAL_EXPONENT: i32; |
230 | /// Maximum exponent value in float. |
231 | const MAX_EXPONENT: i32; |
232 | |
233 | // ROUNDING |
234 | |
235 | /// Default number of bits to shift (or 64 - mantissa size - 1). |
236 | const DEFAULT_SHIFT: i32; |
237 | /// Mask to determine if a full-carry occurred (1 in bit above hidden bit). |
238 | const CARRY_MASK: u64; |
239 | |
240 | /// Get min and max exponent limits (exact) from radix. |
241 | fn exponent_limit() -> (i32, i32); |
242 | |
243 | /// Get the number of digits that can be shifted from exponent to mantissa. |
244 | fn mantissa_limit() -> i32; |
245 | |
246 | // Re-exported methods from std. |
247 | fn pow10(self, n: i32) -> Self; |
248 | fn from_bits(u: Self::Unsigned) -> Self; |
249 | fn to_bits(self) -> Self::Unsigned; |
250 | fn is_sign_positive(self) -> bool; |
251 | fn is_sign_negative(self) -> bool; |
252 | |
253 | /// Returns true if the float is a denormal. |
254 | #[inline ] |
255 | fn is_denormal(self) -> bool { |
256 | self.to_bits() & Self::EXPONENT_MASK == Self::Unsigned::ZERO |
257 | } |
258 | |
259 | /// Returns true if the float is a NaN or Infinite. |
260 | #[inline ] |
261 | fn is_special(self) -> bool { |
262 | self.to_bits() & Self::EXPONENT_MASK == Self::EXPONENT_MASK |
263 | } |
264 | |
265 | /// Returns true if the float is infinite. |
266 | #[inline ] |
267 | fn is_inf(self) -> bool { |
268 | self.is_special() && (self.to_bits() & Self::MANTISSA_MASK) == Self::Unsigned::ZERO |
269 | } |
270 | |
271 | /// Get exponent component from the float. |
272 | #[inline ] |
273 | fn exponent(self) -> i32 { |
274 | if self.is_denormal() { |
275 | return Self::DENORMAL_EXPONENT; |
276 | } |
277 | |
278 | let bits = self.to_bits(); |
279 | let biased_e = ((bits & Self::EXPONENT_MASK) >> Self::MANTISSA_SIZE).as_u32(); |
280 | biased_e as i32 - Self::EXPONENT_BIAS |
281 | } |
282 | |
283 | /// Get mantissa (significand) component from float. |
284 | #[inline ] |
285 | fn mantissa(self) -> Self::Unsigned { |
286 | let bits = self.to_bits(); |
287 | let s = bits & Self::MANTISSA_MASK; |
288 | if !self.is_denormal() { |
289 | s + Self::HIDDEN_BIT_MASK |
290 | } else { |
291 | s |
292 | } |
293 | } |
294 | |
295 | /// Get next greater float for a positive float. |
296 | /// Value must be >= 0.0 and < INFINITY. |
297 | #[inline ] |
298 | fn next_positive(self) -> Self { |
299 | debug_assert!(self.is_sign_positive() && !self.is_inf()); |
300 | Self::from_bits(self.to_bits() + Self::Unsigned::as_cast(1u32)) |
301 | } |
302 | |
303 | /// Round a positive number to even. |
304 | #[inline ] |
305 | fn round_positive_even(self) -> Self { |
306 | if self.mantissa() & Self::Unsigned::as_cast(1u32) == Self::Unsigned::as_cast(1u32) { |
307 | self.next_positive() |
308 | } else { |
309 | self |
310 | } |
311 | } |
312 | } |
313 | |
314 | impl Float for f32 { |
315 | type Unsigned = u32; |
316 | |
317 | const ZERO: f32 = 0.0; |
318 | const MAX_DIGITS: usize = 114; |
319 | const SIGN_MASK: u32 = 0x80000000; |
320 | const EXPONENT_MASK: u32 = 0x7F800000; |
321 | const HIDDEN_BIT_MASK: u32 = 0x00800000; |
322 | const MANTISSA_MASK: u32 = 0x007FFFFF; |
323 | const INFINITY_BITS: u32 = 0x7F800000; |
324 | const NEGATIVE_INFINITY_BITS: u32 = Self::INFINITY_BITS | Self::SIGN_MASK; |
325 | const MANTISSA_SIZE: i32 = 23; |
326 | const EXPONENT_BIAS: i32 = 127 + Self::MANTISSA_SIZE; |
327 | const DENORMAL_EXPONENT: i32 = 1 - Self::EXPONENT_BIAS; |
328 | const MAX_EXPONENT: i32 = 0xFF - Self::EXPONENT_BIAS; |
329 | const DEFAULT_SHIFT: i32 = u64::FULL - f32::MANTISSA_SIZE - 1; |
330 | const CARRY_MASK: u64 = 0x1000000; |
331 | |
332 | #[inline ] |
333 | fn exponent_limit() -> (i32, i32) { |
334 | (-10, 10) |
335 | } |
336 | |
337 | #[inline ] |
338 | fn mantissa_limit() -> i32 { |
339 | 7 |
340 | } |
341 | |
342 | #[inline ] |
343 | fn pow10(self, n: i32) -> f32 { |
344 | // Check the exponent is within bounds in debug builds. |
345 | debug_assert!({ |
346 | let (min, max) = Self::exponent_limit(); |
347 | n >= min && n <= max |
348 | }); |
349 | |
350 | if n > 0 { |
351 | self * F32_POW10[n as usize] |
352 | } else { |
353 | self / F32_POW10[-n as usize] |
354 | } |
355 | } |
356 | |
357 | #[inline ] |
358 | fn from_bits(u: u32) -> f32 { |
359 | f32::from_bits(u) |
360 | } |
361 | |
362 | #[inline ] |
363 | fn to_bits(self) -> u32 { |
364 | f32::to_bits(self) |
365 | } |
366 | |
367 | #[inline ] |
368 | fn is_sign_positive(self) -> bool { |
369 | f32::is_sign_positive(self) |
370 | } |
371 | |
372 | #[inline ] |
373 | fn is_sign_negative(self) -> bool { |
374 | f32::is_sign_negative(self) |
375 | } |
376 | } |
377 | |
378 | impl Float for f64 { |
379 | type Unsigned = u64; |
380 | |
381 | const ZERO: f64 = 0.0; |
382 | const MAX_DIGITS: usize = 769; |
383 | const SIGN_MASK: u64 = 0x8000000000000000; |
384 | const EXPONENT_MASK: u64 = 0x7FF0000000000000; |
385 | const HIDDEN_BIT_MASK: u64 = 0x0010000000000000; |
386 | const MANTISSA_MASK: u64 = 0x000FFFFFFFFFFFFF; |
387 | const INFINITY_BITS: u64 = 0x7FF0000000000000; |
388 | const NEGATIVE_INFINITY_BITS: u64 = Self::INFINITY_BITS | Self::SIGN_MASK; |
389 | const MANTISSA_SIZE: i32 = 52; |
390 | const EXPONENT_BIAS: i32 = 1023 + Self::MANTISSA_SIZE; |
391 | const DENORMAL_EXPONENT: i32 = 1 - Self::EXPONENT_BIAS; |
392 | const MAX_EXPONENT: i32 = 0x7FF - Self::EXPONENT_BIAS; |
393 | const DEFAULT_SHIFT: i32 = u64::FULL - f64::MANTISSA_SIZE - 1; |
394 | const CARRY_MASK: u64 = 0x20000000000000; |
395 | |
396 | #[inline ] |
397 | fn exponent_limit() -> (i32, i32) { |
398 | (-22, 22) |
399 | } |
400 | |
401 | #[inline ] |
402 | fn mantissa_limit() -> i32 { |
403 | 15 |
404 | } |
405 | |
406 | #[inline ] |
407 | fn pow10(self, n: i32) -> f64 { |
408 | // Check the exponent is within bounds in debug builds. |
409 | debug_assert!({ |
410 | let (min, max) = Self::exponent_limit(); |
411 | n >= min && n <= max |
412 | }); |
413 | |
414 | if n > 0 { |
415 | self * F64_POW10[n as usize] |
416 | } else { |
417 | self / F64_POW10[-n as usize] |
418 | } |
419 | } |
420 | |
421 | #[inline ] |
422 | fn from_bits(u: u64) -> f64 { |
423 | f64::from_bits(u) |
424 | } |
425 | |
426 | #[inline ] |
427 | fn to_bits(self) -> u64 { |
428 | f64::to_bits(self) |
429 | } |
430 | |
431 | #[inline ] |
432 | fn is_sign_positive(self) -> bool { |
433 | f64::is_sign_positive(self) |
434 | } |
435 | |
436 | #[inline ] |
437 | fn is_sign_negative(self) -> bool { |
438 | f64::is_sign_negative(self) |
439 | } |
440 | } |
441 | |