crypto_bigint/limb/
cmp.rs

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

crypto_bigint/limb/
cmp.rs
