sanctum_u64_ratio/
lib.rs

1#![cfg_attr(not(test), no_std)]
2#![doc = include_str!("../README.md")]
3
4use core::cmp::{Eq, Ord, Ordering, PartialEq, PartialOrd};
5use core::fmt::{Display, Formatter};
6use core::hash::{Hash, Hasher};
7
8mod div;
9
10pub(crate) mod utils;
11
12pub use div::*;
13
14/// A ratio that is applied to a u64 token amount.
15///
16/// A zero denominator ratio (`self.d == 0`) is treated as zero.
17///
18/// Must use with [`crate::Ceil`] or [`crate::Floor`]
19/// for application on [`u64`]s
20#[derive(Debug, Copy, Clone)]
21pub struct Ratio<N, D> {
22    /// Numerator
23    pub n: N,
24
25    /// Denominator
26    pub d: D,
27}
28
29macro_rules! impl_gcd {
30    ($f:ident, $T:ty) => {
31        /// Takes 1 fewer iteration if a > b compared to b > a.
32        ///
33        /// Never returns 0 unless both args are 0
34        #[inline]
35        const fn $f(mut a: $T, mut b: $T) -> $T {
36            while b > 0 {
37                let r = a % b;
38                a = b;
39                b = r;
40            }
41            a
42        }
43    };
44}
45
46impl_gcd!(gcd_u8, u8);
47impl_gcd!(gcd_u16, u16);
48impl_gcd!(gcd_u32, u32);
49impl_gcd!(gcd_u64, u64);
50
51/// Associated types of a [`Ratio`] for use in arithmetic operations
52///
53/// (because inherent associated types are still unstable)
54pub trait ArithTypes {
55    /// The smaller bitwidth type between `Ratio::N` and `Ratio::D`
56    type Min;
57
58    /// The larger bitwidth type between `Ratio::N` and `Ratio::D`
59    type Max;
60
61    /// The unsigned type that `Ratio::N` and `Ratio::D` must be
62    /// bit-extended (cast) into to avoid overflows on multiplication
63    /// of `Ratio::N` and `Ratio::D`
64    type Ext;
65}
66
67impl<N, D> Ratio<N, D> {
68    /// Convenience constructor for better compatibility with type aliases
69    #[inline]
70    pub const fn new(n: N, d: D) -> Self {
71        Self { n, d }
72    }
73}
74
75macro_rules! impl_ratio {
76    ($N:ty, $D:ty, [$gcd:expr, $MIN: ty, $MAX:ty, $EXT:ty]) => {
77        impl ArithTypes for Ratio<$N, $D> {
78            type Min = $MIN;
79            type Max = $MAX;
80            type Ext = $EXT;
81        }
82
83        impl Ratio<$N, $D> {
84            pub const ZERO: Self = Self { n: 0, d: 0 };
85            pub const ONE: Self = Self { n: 1, d: 1 };
86
87            /// Returns true if this ratio represents `0.0`
88            /// i.e. applying it to any value should output 0
89            #[inline]
90            pub const fn is_zero(&self) -> bool {
91                self.n == 0 || self.d == 0
92            }
93
94            /// Returns true if this ratio represents `1.0`
95            /// i.e. `numerator == denominator` and applying it
96            /// to any value should output the same value
97            #[inline]
98            pub const fn is_one(&self) -> bool {
99                type Max = <Ratio<$N, $D> as ArithTypes>::Max;
100
101                !self.is_zero() && self.n as Max == self.d as Max
102            }
103
104            /// Fraction comparison
105            ///
106            /// ```rust
107            /// use core::cmp::Ordering;
108            /// use sanctum_u64_ratio::Ratio;
109            ///
110            #[doc = concat!("type R = Ratio<", stringify!($N), ", ", stringify!($D), ">;")]
111            ///
112            /// // 1/2 == 4/8 even though n and d are different
113            /// assert_eq!(
114            ///     R::new(1, 2).const_cmp(&R::new(4, 8)),
115            ///     Ordering::Equal,
116            /// );
117            ///
118            /// // 1/3 > 1/4
119            /// assert_eq!(
120            ///     R::new(1, 3).const_cmp(&R::new(1, 4)),
121            ///     Ordering::Greater,
122            /// )
123            /// ```
124            #[inline]
125            pub const fn const_cmp(&self, other: &Self) -> Ordering {
126                type Ext = <Ratio<$N, $D> as ArithTypes>::Ext;
127
128                match (self.is_zero(), other.is_zero()) {
129                    (true, true) => return Ordering::Equal,
130                    (true, false) => return Ordering::Less,
131                    (false, true) => return Ordering::Greater,
132                    (false, false) => (),
133                };
134
135                let lhs = (self.n as Ext) * (other.d as Ext);
136                let rhs = (other.n as Ext) * (self.d as Ext);
137                if lhs == rhs {
138                    Ordering::Equal
139                } else if lhs < rhs {
140                    Ordering::Less
141                } else {
142                    Ordering::Greater
143                }
144            }
145
146            /// Returns the fraction's lowest form.
147            ///
148            /// This is `0/0` if [`Self::is_zero()`]
149            #[inline]
150            pub const fn lowest_form(
151                &self,
152            ) -> Ratio<<Self as ArithTypes>::Max, <Self as ArithTypes>::Max> {
153                type Max = <Ratio<$N, $D> as ArithTypes>::Max;
154
155                if self.is_zero() {
156                    return Ratio::<Max, Max>::ZERO;
157                }
158                let n = self.n as Max;
159                let d = self.d as Max;
160                // usually the denominator is larger, so put it first
161                let gcd = $gcd(d, n);
162                // division-safety: gcd is never 0 due to early return above
163                Ratio {
164                    n: n / gcd,
165                    d: d / gcd,
166                }
167            }
168        }
169
170        impl Default for Ratio<$N, $D> {
171            #[inline]
172            fn default() -> Self {
173                Self::ZERO
174            }
175        }
176
177        /// Uses [`Self::const_cmp`], see its docs for more info
178        impl PartialEq for Ratio<$N, $D> {
179            #[inline]
180            fn eq(&self, rhs: &Self) -> bool {
181                self.const_cmp(rhs).is_eq()
182            }
183        }
184
185        /// Uses [`Self::const_cmp`], see its docs for more info
186        impl Eq for Ratio<$N, $D> {}
187
188        /// Uses [`Self::const_cmp`], see its docs for more info
189        impl PartialOrd for Ratio<$N, $D> {
190            #[inline]
191            fn partial_cmp(&self, rhs: &Self) -> Option<Ordering> {
192                Some(self.cmp(rhs))
193            }
194        }
195
196        /// Uses [`Self::const_cmp`], see its docs for more info
197        impl Ord for Ratio<$N, $D> {
198            #[inline]
199            fn cmp(&self, rhs: &Self) -> Ordering {
200                self.const_cmp(rhs)
201            }
202        }
203
204        /// To ensure that the
205        /// `k1 == k2 -> hash(k1) == hash(k2)`
206        /// invariant is not violated, we need to hash the fraction's lowest form.
207        ///
208        /// More info in [rust std docs](https://doc.rust-lang.org/std/hash/trait.Hash.html#hash-and-eq)
209        impl Hash for Ratio<$N, $D> {
210            #[inline]
211            fn hash<H>(&self, state: &mut H)
212            where
213                H: Hasher,
214            {
215                let Ratio { n, d } = self.lowest_form();
216                n.hash(state);
217                d.hash(state);
218            }
219        }
220
221        /// Displayed as `{numerator}/{denominator}`
222        impl Display for Ratio<$N, $D> {
223            #[inline]
224            fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
225                f.write_fmt(format_args!("{}/{}", self.n, self.d))
226            }
227        }
228    };
229}
230
231impl_ratio!(u8, u8, [gcd_u8, u8, u8, u16]);
232impl_ratio!(u8, u16, [gcd_u16, u8, u16, u32]);
233impl_ratio!(u8, u32, [gcd_u32, u8, u32, u64]);
234impl_ratio!(u8, u64, [gcd_u64, u8, u64, u128]);
235
236impl_ratio!(u16, u8, [gcd_u16, u8, u16, u32]);
237impl_ratio!(u16, u16, [gcd_u16, u16, u16, u32]);
238impl_ratio!(u16, u32, [gcd_u32, u16, u32, u64]);
239impl_ratio!(u16, u64, [gcd_u64, u16, u64, u128]);
240
241impl_ratio!(u32, u8, [gcd_u32, u8, u32, u64]);
242impl_ratio!(u32, u16, [gcd_u32, u16, u32, u64]);
243impl_ratio!(u32, u32, [gcd_u32, u32, u32, u64]);
244impl_ratio!(u32, u64, [gcd_u64, u32, u64, u128]);
245
246impl_ratio!(u64, u8, [gcd_u64, u8, u64, u128]);
247impl_ratio!(u64, u16, [gcd_u64, u16, u64, u128]);
248impl_ratio!(u64, u32, [gcd_u64, u32, u64, u128]);
249impl_ratio!(u64, u64, [gcd_u64, u64, u64, u128]);
250
251#[cfg(test)]
252mod tests {
253    use proptest::prelude::*;
254    use std::hash::DefaultHasher;
255
256    use super::*;
257
258    macro_rules! zero_eq {
259        ($N:ty, $D:ty, $zero:ident) => {
260            proptest! {
261                #[test]
262                fn $zero(a: $N, b: $D) {
263                    type NR = Ratio<$N, $D>;
264                    type DR = Ratio<$D, $N>;
265                    type Max = <NR as ArithTypes>::Max;
266
267                    for nr in [
268                        NR::new(a, 0),
269                        NR::new(0, b),
270                    ] {
271                        prop_assert_eq!(NR::ZERO, nr, "{} != 0", nr);
272                    }
273
274                    for dr in [
275                        DR::new(b, 0),
276                        DR::new(0, a),
277                    ] {
278                        prop_assert_eq!(DR::ZERO, dr, "{} != 0", dr);
279                    }
280
281                    for lowest_form in [
282                        DR::new(0, a).lowest_form(),
283                        NR::new(a, 0).lowest_form(),
284                        NR::new(0, b).lowest_form(),
285                        DR::new(b, 0).lowest_form(),
286                    ] {
287                        prop_assert_eq!(
288                            lowest_form,
289                            Ratio::<Max, Max>::ZERO,
290                            "{} != 0", lowest_form,
291                        );
292                    }
293                }
294            }
295        };
296    }
297
298    macro_rules! lowest_form_ord_iff_ord {
299        ($N: ty, $D:ty, $lowest_form:ident) => {
300            proptest! {
301                #[test]
302                fn $lowest_form(n1: $N, d1: $D, n2: $N, d2: $D) {
303                    type R = Ratio<$N, $D>;
304
305                    let [(r1, l1), (r2, l2)] = [(n1, d1), (n2, d2)]
306                        .map(|(n, d)| {
307                            let r = R::new(n, d);
308                            (r, r.lowest_form())
309                        });
310                    prop_assert_eq!(
311                        r1.const_cmp(&r2),
312                        l1.const_cmp(&l2),
313                        "{}, {}, {}, {}",
314                        r1, l1, r2, l2,
315                    );
316                }
317            }
318        };
319    }
320
321    macro_rules! ord {
322        ($T:ty, $ord:ident) => {
323            proptest! {
324                #[test]
325                fn $ord(common in 1..=<$T>::MAX, a in 1..=<$T>::MAX, b in 1..=<$T>::MAX) {
326                    type R = Ratio<$T, $T>;
327
328                    if a == b {
329                        prop_assert_eq!(
330                            R::new(a, common),
331                            R::new(b, common),
332                        );
333                        prop_assert_eq!(
334                            R::new(common, a),
335                            R::new(common, b),
336                        );
337                        return Ok(());
338                    }
339
340                    let (smaller, larger) = if a < b {
341                        (a, b)
342                    } else {
343                        (b, a)
344                    };
345                    let s = R::new(smaller, common);
346                    let l = R::new(larger, common);
347                    prop_assert!(s < l, "common d {s}, {l}");
348
349                    let s = R::new(common, larger);
350                    let l = R::new(common, smaller);
351                    prop_assert!(s < l, "common n {s}, {l}");
352                }
353            }
354        };
355    }
356
357    macro_rules! eq_implies_hash_eq {
358        ($N: ty, $D:ty, $eqhash:ident) => {
359            proptest! {
360                #[test]
361                fn $eqhash(n1: $N, d1: $D, n2: $N, d2: $D) {
362                    type R = Ratio<$N, $D>;
363
364                    let [r1, r2] = [(n1, d1), (n2, d2)]
365                        .map(|(n, d)| R::new(n, d));
366                    if r1 == r2 {
367                        let [mut h1, mut h2] = core::array::from_fn(|_| DefaultHasher::new());
368                        for (r, h) in [(r1, &mut h1), (r2, &mut h2)] {
369                            r.hash(h);
370                        }
371                        let [h1, h2] = [h1, h2].map(|h| h.finish());
372                        prop_assert_eq!(h1, h2);
373                    }
374                }
375            }
376        };
377    }
378
379    ord!(u8, ord_u8);
380    ord!(u16, ord_u16);
381    ord!(u32, ord_u32);
382    ord!(u64, ord_u64);
383
384    zero_eq!(u8, u8, zero_eq_u8_u8);
385    zero_eq!(u8, u16, zero_eq_u8_u16);
386    zero_eq!(u8, u32, zero_eq_u8_u32);
387    zero_eq!(u8, u64, zero_eq_u8_u64);
388
389    zero_eq!(u16, u8, zero_eq_u16_u8);
390    zero_eq!(u16, u16, zero_eq_u16_u16);
391    zero_eq!(u16, u32, zero_eq_u16_u32);
392    zero_eq!(u16, u64, zero_eq_u16_u64);
393
394    zero_eq!(u32, u8, zero_eq_u32_u8);
395    zero_eq!(u32, u16, zero_eq_u32_u16);
396    zero_eq!(u32, u32, zero_eq_u32_u32);
397    zero_eq!(u32, u64, zero_eq_u32_u64);
398
399    zero_eq!(u64, u8, zero_eq_u64_u8);
400    zero_eq!(u64, u16, zero_eq_u64_u16);
401    zero_eq!(u64, u32, zero_eq_u64_u32);
402    zero_eq!(u64, u64, zero_eq_u64_u64);
403
404    lowest_form_ord_iff_ord!(u8, u8, lowest_form_iff_u8_u8);
405    lowest_form_ord_iff_ord!(u8, u16, lowest_form_iff_u8_u16);
406    lowest_form_ord_iff_ord!(u8, u32, lowest_form_iff_u8_u32);
407    lowest_form_ord_iff_ord!(u8, u64, lowest_form_iff_u8_u64);
408
409    lowest_form_ord_iff_ord!(u16, u8, lowest_form_iff_u16_u8);
410    lowest_form_ord_iff_ord!(u16, u16, lowest_form_iff_u16_u16);
411    lowest_form_ord_iff_ord!(u16, u32, lowest_form_iff_u16_u32);
412    lowest_form_ord_iff_ord!(u16, u64, lowest_form_iff_u16_u64);
413
414    lowest_form_ord_iff_ord!(u32, u8, lowest_form_iff_u32_u8);
415    lowest_form_ord_iff_ord!(u32, u16, lowest_form_iff_u32_u16);
416    lowest_form_ord_iff_ord!(u32, u32, lowest_form_iff_u32_u32);
417    lowest_form_ord_iff_ord!(u32, u64, lowest_form_iff_u32_u64);
418
419    lowest_form_ord_iff_ord!(u64, u8, lowest_form_iff_u64_u8);
420    lowest_form_ord_iff_ord!(u64, u16, lowest_form_iff_u64_u16);
421    lowest_form_ord_iff_ord!(u64, u32, lowest_form_iff_u64_u32);
422    lowest_form_ord_iff_ord!(u64, u64, lowest_form_iff_u64_u64);
423
424    eq_implies_hash_eq!(u8, u8, eq_hash_eq_u8_u8);
425    eq_implies_hash_eq!(u8, u16, eq_hash_eq_u8_u16);
426    eq_implies_hash_eq!(u8, u32, eq_hash_eq_u8_u32);
427    eq_implies_hash_eq!(u8, u64, eq_hash_eq_u8_u64);
428
429    eq_implies_hash_eq!(u16, u8, eq_hash_eq_u16_u8);
430    eq_implies_hash_eq!(u16, u16, eq_hash_eq_u16_u16);
431    eq_implies_hash_eq!(u16, u32, eq_hash_eq_u16_u32);
432    eq_implies_hash_eq!(u16, u64, eq_hash_eq_u16_u64);
433
434    eq_implies_hash_eq!(u32, u8, eq_hash_eq_u32_u8);
435    eq_implies_hash_eq!(u32, u16, eq_hash_eq_u32_u16);
436    eq_implies_hash_eq!(u32, u32, eq_hash_eq_u32_u32);
437    eq_implies_hash_eq!(u32, u64, eq_hash_eq_u32_u64);
438
439    eq_implies_hash_eq!(u64, u8, eq_hash_eq_u64_u8);
440    eq_implies_hash_eq!(u64, u16, eq_hash_eq_u64_u16);
441    eq_implies_hash_eq!(u64, u32, eq_hash_eq_u64_u32);
442    eq_implies_hash_eq!(u64, u64, eq_hash_eq_u64_u64);
443}
sanctum_u64_ratio/lib.rs

sanctum_u64_ratio/
lib.rs
