fixed_bigint/heapless/
abs_diff.rs

1//! `const_num_traits::AbsDiff` for `HeaplessBigInt`.
2//!
3//! `|a - b|` = the larger minus the smaller. The `Nct` arm branches on the
4//! comparison; the `Ct` arm computes `a - b` (with its borrow) and `b - a`
5//! and picks branchlessly with `ct_select`, mirroring `FixedUInt`'s Ct
6//! `abs_diff`.
7
8use super::HeaplessBigInt;
9use super::cmp::ct_select;
10use crate::MachineWord;
11use const_num_traits::{AbsDiff, Ct, Nct, OverflowingSub, WrappingSub, Zero};
12
13impl<T, const CAP: usize> AbsDiff for HeaplessBigInt<T, CAP, Nct>
14where
15    T: MachineWord,
16{
17    type Output = Self;
18    fn abs_diff(self, other: Self) -> Self {
19        if self >= other {
20            self - other
21        } else {
22            other - self
23        }
24    }
25}
26
27impl<T, const CAP: usize> AbsDiff for HeaplessBigInt<T, CAP, Ct>
28where
29    T: MachineWord + subtle::ConditionallySelectable,
30{
31    type Output = Self;
32    fn abs_diff(self, other: Self) -> Self {
33        // `a - b` wraps to `-(b - a)` when `a < b` (borrow set), so the branchless
34        // result is `select(diff, -diff, borrow)`.
35        let (diff, borrow) = OverflowingSub::overflowing_sub(self, other);
36        let neg_diff = WrappingSub::wrapping_sub(Self::zero(), diff);
37        ct_select(&diff, &neg_diff, borrow)
38    }
39}
40
41// `&Self` mirrors so `(&h).abs_diff(&g)` resolves without an explicit copy.
42impl<T, const CAP: usize> AbsDiff for &HeaplessBigInt<T, CAP, Nct>
43where
44    T: MachineWord,
45{
46    type Output = HeaplessBigInt<T, CAP, Nct>;
47    fn abs_diff(self, other: Self) -> Self::Output {
48        <HeaplessBigInt<T, CAP, Nct> as AbsDiff>::abs_diff(*self, *other)
49    }
50}
51
52impl<T, const CAP: usize> AbsDiff for &HeaplessBigInt<T, CAP, Ct>
53where
54    T: MachineWord + subtle::ConditionallySelectable,
55{
56    type Output = HeaplessBigInt<T, CAP, Ct>;
57    fn abs_diff(self, other: Self) -> Self::Output {
58        <HeaplessBigInt<T, CAP, Ct> as AbsDiff>::abs_diff(*self, *other)
59    }
60}
61
62#[cfg(test)]
63mod tests {
64    use super::HeaplessBigInt;
65    use const_num_traits::{AbsDiff, Ct, Nct};
66
67    type HN = HeaplessBigInt<u8, 4, Nct>;
68    type HC = HeaplessBigInt<u8, 4, Ct>;
69
70    #[test]
71    fn ct_abs_diff_matches_nct_and_value() {
72        for (a, b) in [(10u32, 3), (3, 10), (0, 0), (u32::MAX, 1), (1, u32::MAX)] {
73            let expected = a.abs_diff(b);
74            assert_eq!(
75                AbsDiff::abs_diff(HC::from(a), HC::from(b)),
76                HC::from(expected),
77                "ct abs_diff({a}, {b})"
78            );
79            assert_eq!(
80                AbsDiff::abs_diff(HN::from(a), HN::from(b)),
81                HN::from(expected)
82            );
83        }
84    }
85
86    #[test]
87    fn byref_matches_value() {
88        let (an, bn) = (HN::from(10u8), HN::from(3u8));
89        assert_eq!(AbsDiff::abs_diff(&an, &bn), AbsDiff::abs_diff(an, bn));
90        let (ac, bc) = (HC::from(3u8), HC::from(10u8));
91        assert_eq!(AbsDiff::abs_diff(&ac, &bc), AbsDiff::abs_diff(ac, bc));
92    }
93}
fixed_bigint/heapless/abs_diff.rs

fixed_bigint/heapless/
abs_diff.rs
