crypto_bigint/limb/
cmp.rs

Help
1//! Limb comparisons
2
3use super::{Limb, SignedWord, WideSignedWord, Word, HI_BIT};
4use core::cmp::Ordering;
5use subtle::{Choice, ConstantTimeEq, ConstantTimeGreater, ConstantTimeLess};
6
7impl Limb {
8    /// Is this limb an odd number?
9    #[inline]
10    pub fn is_odd(&self) -> Choice {
11        Choice::from(self.0 as u8 & 1)
12    }
13
14    /// Perform a comparison of the inner value in variable-time.
15    ///
16    /// Note that the [`PartialOrd`] and [`Ord`] impls wrap constant-time
17    /// comparisons using the `subtle` crate.
18    pub fn cmp_vartime(&self, other: &Self) -> Ordering {
19        self.0.cmp(&other.0)
20    }
21
22    /// Performs an equality check in variable-time.
23    pub const fn eq_vartime(&self, other: &Self) -> bool {
24        self.0 == other.0
25    }
26
27    /// Returns all 1's if `a`!=0 or 0 if `a`==0.
28    ///
29    /// Const-friendly: we can't yet use `subtle` in `const fn` contexts.
30    #[inline]
31    pub(crate) const fn is_nonzero(self) -> Word {
32        let inner = self.0 as SignedWord;
33        ((inner | inner.saturating_neg()) >> HI_BIT) as Word
34    }
35
36    #[inline]
37    pub(crate) const fn ct_cmp(lhs: Self, rhs: Self) -> SignedWord {
38        let a = lhs.0 as WideSignedWord;
39        let b = rhs.0 as WideSignedWord;
40        let gt = ((b - a) >> Limb::BIT_SIZE) & 1;
41        let lt = ((a - b) >> Limb::BIT_SIZE) & 1 & !gt;
42        (gt as SignedWord) - (lt as SignedWord)
43    }
44}
45
46impl ConstantTimeEq for Limb {
47    #[inline]
48    fn ct_eq(&self, other: &Self) -> Choice {
49        self.0.ct_eq(&other.0)
50    }
51}
52
53impl ConstantTimeGreater for Limb {
54    #[inline]
55    fn ct_gt(&self, other: &Self) -> Choice {
56        self.0.ct_gt(&other.0)
57    }
58}
59
60impl ConstantTimeLess for Limb {
61    #[inline]
62    fn ct_lt(&self, other: &Self) -> Choice {
63        self.0.ct_lt(&other.0)
64    }
65}
66
67impl Eq for Limb {}
68
69impl Ord for Limb {
70    fn cmp(&self, other: &Self) -> Ordering {
71        let mut n = 0i8;
72        n -= self.ct_lt(other).unwrap_u8() as i8;
73        n += self.ct_gt(other).unwrap_u8() as i8;
74
75        match n {
76            -1 => Ordering::Less,
77            1 => Ordering::Greater,
78            _ => {
79                debug_assert_eq!(n, 0);
80                debug_assert!(bool::from(self.ct_eq(other)));
81                Ordering::Equal
82            }
83        }
84    }
85}
86
87impl PartialOrd for Limb {
88    #[inline]
89    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
90        Some(self.cmp(other))
91    }
92}
93
94impl PartialEq for Limb {
95    #[inline]
96    fn eq(&self, other: &Self) -> bool {
97        self.ct_eq(other).into()
98    }
99}
100
101#[cfg(test)]
102mod tests {
103    use crate::{Limb, Zero};
104    use core::cmp::Ordering;
105    use subtle::{ConstantTimeEq, ConstantTimeGreater, ConstantTimeLess};
106
107    #[test]
108    fn is_zero() {
109        assert!(bool::from(Limb::ZERO.is_zero()));
110        assert!(!bool::from(Limb::ONE.is_zero()));
111        assert!(!bool::from(Limb::MAX.is_zero()));
112    }
113
114    #[test]
115    fn is_odd() {
116        assert!(!bool::from(Limb::ZERO.is_odd()));
117        assert!(bool::from(Limb::ONE.is_odd()));
118        assert!(bool::from(Limb::MAX.is_odd()));
119    }
120
121    #[test]
122    fn ct_eq() {
123        let a = Limb::ZERO;
124        let b = Limb::MAX;
125
126        assert!(bool::from(a.ct_eq(&a)));
127        assert!(!bool::from(a.ct_eq(&b)));
128        assert!(!bool::from(b.ct_eq(&a)));
129        assert!(bool::from(b.ct_eq(&b)));
130    }
131
132    #[test]
133    fn ct_gt() {
134        let a = Limb::ZERO;
135        let b = Limb::ONE;
136        let c = Limb::MAX;
137
138        assert!(bool::from(b.ct_gt(&a)));
139        assert!(bool::from(c.ct_gt(&a)));
140        assert!(bool::from(c.ct_gt(&b)));
141
142        assert!(!bool::from(a.ct_gt(&a)));
143        assert!(!bool::from(b.ct_gt(&b)));
144        assert!(!bool::from(c.ct_gt(&c)));
145
146        assert!(!bool::from(a.ct_gt(&b)));
147        assert!(!bool::from(a.ct_gt(&c)));
148        assert!(!bool::from(b.ct_gt(&c)));
149    }
150
151    #[test]
152    fn ct_lt() {
153        let a = Limb::ZERO;
154        let b = Limb::ONE;
155        let c = Limb::MAX;
156
157        assert!(bool::from(a.ct_lt(&b)));
158        assert!(bool::from(a.ct_lt(&c)));
159        assert!(bool::from(b.ct_lt(&c)));
160
161        assert!(!bool::from(a.ct_lt(&a)));
162        assert!(!bool::from(b.ct_lt(&b)));
163        assert!(!bool::from(c.ct_lt(&c)));
164
165        assert!(!bool::from(b.ct_lt(&a)));
166        assert!(!bool::from(c.ct_lt(&a)));
167        assert!(!bool::from(c.ct_lt(&b)));
168    }
169
170    #[test]
171    fn cmp() {
172        assert_eq!(Limb::ZERO.cmp(&Limb::ONE), Ordering::Less);
173        assert_eq!(Limb::ONE.cmp(&Limb::ONE), Ordering::Equal);
174        assert_eq!(Limb::MAX.cmp(&Limb::ONE), Ordering::Greater);
175    }
176}
crypto_bigint/limb/cmp.rs

crypto_bigint/limb/
cmp.rs
