crypto_bigint/uint/
cmp.rs

1//! [`Uint`] comparisons.
2//!
3//! By default, these are all constant-time.
4
5use core::cmp::Ordering;
6
7use subtle::{Choice, ConstantTimeEq, ConstantTimeGreater, ConstantTimeLess};
8
9use crate::{ConstChoice, Limb};
10
11use super::Uint;
12
13impl<const LIMBS: usize> Uint<LIMBS> {
14    /// Return `b` if `c` is truthy, otherwise return `a`.
15    #[inline]
16    pub(crate) const fn select(a: &Self, b: &Self, c: ConstChoice) -> Self {
17        let mut limbs = [Limb::ZERO; LIMBS];
18
19        let mut i = 0;
20        while i < LIMBS {
21            limbs[i] = Limb::select(a.limbs[i], b.limbs[i], c);
22            i += 1;
23        }
24
25        Uint { limbs }
26    }
27
28    /// Returns the truthy value if `self`!=0 or the falsy value otherwise.
29    #[inline]
30    pub(crate) const fn is_nonzero(&self) -> ConstChoice {
31        let mut b = 0;
32        let mut i = 0;
33        while i < LIMBS {
34            b |= self.limbs[i].0;
35            i += 1;
36        }
37        Limb(b).is_nonzero()
38    }
39
40    /// Returns the truthy value if `self` is odd or the falsy value otherwise.
41    pub(crate) const fn is_odd(&self) -> ConstChoice {
42        ConstChoice::from_word_lsb(self.limbs[0].0 & 1)
43    }
44
45    /// Returns the truthy value if `self == rhs` or the falsy value otherwise.
46    #[inline]
47    pub(crate) const fn eq(lhs: &Self, rhs: &Self) -> ConstChoice {
48        let mut acc = 0;
49        let mut i = 0;
50
51        while i < LIMBS {
52            acc |= lhs.limbs[i].0 ^ rhs.limbs[i].0;
53            i += 1;
54        }
55
56        // acc == 0 if and only if self == rhs
57        Limb(acc).is_nonzero().not()
58    }
59
60    /// Returns the truthy value if `self < rhs` and the falsy value otherwise.
61    #[inline]
62    pub(crate) const fn lt(lhs: &Self, rhs: &Self) -> ConstChoice {
63        // We could use the same approach as in Limb::ct_lt(),
64        // but since we have to use Uint::wrapping_sub(), which calls `sbb()`,
65        // there are no savings compared to just calling `sbb()` directly.
66        let (_res, borrow) = lhs.sbb(rhs, Limb::ZERO);
67        ConstChoice::from_word_mask(borrow.0)
68    }
69
70    /// Returns the truthy value if `self <= rhs` and the falsy value otherwise.
71    #[inline]
72    pub(crate) const fn lte(lhs: &Self, rhs: &Self) -> ConstChoice {
73        Self::gt(lhs, rhs).not()
74    }
75
76    /// Returns the truthy value if `self > rhs` and the falsy value otherwise.
77    #[inline]
78    pub(crate) const fn gt(lhs: &Self, rhs: &Self) -> ConstChoice {
79        let (_res, borrow) = rhs.sbb(lhs, Limb::ZERO);
80        ConstChoice::from_word_mask(borrow.0)
81    }
82
83    /// Returns the ordering between `self` and `rhs` as an i8.
84    /// Values correspond to the Ordering enum:
85    ///   -1 is Less
86    ///   0 is Equal
87    ///   1 is Greater
88    #[inline]
89    pub(crate) const fn cmp(lhs: &Self, rhs: &Self) -> i8 {
90        let mut i = 0;
91        let mut borrow = Limb::ZERO;
92        let mut diff = Limb::ZERO;
93
94        while i < LIMBS {
95            let (w, b) = rhs.limbs[i].sbb(lhs.limbs[i], borrow);
96            diff = diff.bitor(w);
97            borrow = b;
98            i += 1;
99        }
100        let sgn = ((borrow.0 & 2) as i8) - 1;
101        (diff.is_nonzero().to_u8() as i8) * sgn
102    }
103
104    /// Returns the Ordering between `self` and `rhs` in variable time.
105    pub const fn cmp_vartime(&self, rhs: &Self) -> Ordering {
106        let mut i = LIMBS - 1;
107        loop {
108            let (val, borrow) = self.limbs[i].sbb(rhs.limbs[i], Limb::ZERO);
109            if val.0 != 0 {
110                return if borrow.0 != 0 {
111                    Ordering::Less
112                } else {
113                    Ordering::Greater
114                };
115            }
116            if i == 0 {
117                return Ordering::Equal;
118            }
119            i -= 1;
120        }
121    }
122}
123
124impl<const LIMBS: usize> ConstantTimeEq for Uint<LIMBS> {
125    #[inline]
126    fn ct_eq(&self, other: &Self) -> Choice {
127        Uint::eq(self, other).into()
128    }
129}
130
131impl<const LIMBS: usize> ConstantTimeGreater for Uint<LIMBS> {
132    #[inline]
133    fn ct_gt(&self, other: &Self) -> Choice {
134        Uint::gt(self, other).into()
135    }
136}
137
138impl<const LIMBS: usize> ConstantTimeLess for Uint<LIMBS> {
139    #[inline]
140    fn ct_lt(&self, other: &Self) -> Choice {
141        Uint::lt(self, other).into()
142    }
143}
144
145impl<const LIMBS: usize> Eq for Uint<LIMBS> {}
146
147impl<const LIMBS: usize> Ord for Uint<LIMBS> {
148    fn cmp(&self, other: &Self) -> Ordering {
149        let c = Self::cmp(self, other);
150        match c {
151            -1 => Ordering::Less,
152            0 => Ordering::Equal,
153            _ => Ordering::Greater,
154        }
155    }
156}
157
158impl<const LIMBS: usize> PartialOrd for Uint<LIMBS> {
159    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
160        Some(self.cmp(other))
161    }
162}
163
164impl<const LIMBS: usize> PartialEq for Uint<LIMBS> {
165    fn eq(&self, other: &Self) -> bool {
166        self.ct_eq(other).into()
167    }
168}
169
170#[cfg(test)]
171mod tests {
172    use core::cmp::Ordering;
173
174    use subtle::{ConstantTimeEq, ConstantTimeGreater, ConstantTimeLess};
175
176    use crate::{Integer, Uint, Zero, U128};
177
178    #[test]
179    fn is_zero() {
180        assert!(bool::from(U128::ZERO.is_zero()));
181        assert!(!bool::from(U128::ONE.is_zero()));
182        assert!(!bool::from(U128::MAX.is_zero()));
183    }
184
185    #[test]
186    fn is_odd() {
187        // inherent methods
188        assert!(!bool::from(U128::ZERO.is_odd()));
189        assert!(bool::from(U128::ONE.is_odd()));
190        assert!(bool::from(U128::MAX.is_odd()));
191
192        // `Integer` methods
193        assert!(!bool::from(<U128 as Integer>::is_odd(&U128::ZERO)));
194        assert!(bool::from(<U128 as Integer>::is_odd(&U128::ONE)));
195        assert!(bool::from(<U128 as Integer>::is_odd(&U128::MAX)));
196    }
197
198    #[test]
199    fn ct_eq() {
200        let a = U128::ZERO;
201        let b = U128::MAX;
202
203        assert!(bool::from(a.ct_eq(&a)));
204        assert!(!bool::from(a.ct_eq(&b)));
205        assert!(!bool::from(b.ct_eq(&a)));
206        assert!(bool::from(b.ct_eq(&b)));
207    }
208
209    #[test]
210    fn ct_gt() {
211        let a = U128::ZERO;
212        let b = U128::ONE;
213        let c = U128::MAX;
214
215        assert!(bool::from(b.ct_gt(&a)));
216        assert!(bool::from(c.ct_gt(&a)));
217        assert!(bool::from(c.ct_gt(&b)));
218
219        assert!(!bool::from(a.ct_gt(&a)));
220        assert!(!bool::from(b.ct_gt(&b)));
221        assert!(!bool::from(c.ct_gt(&c)));
222
223        assert!(!bool::from(a.ct_gt(&b)));
224        assert!(!bool::from(a.ct_gt(&c)));
225        assert!(!bool::from(b.ct_gt(&c)));
226    }
227
228    #[test]
229    fn ct_lt() {
230        let a = U128::ZERO;
231        let b = U128::ONE;
232        let c = U128::MAX;
233
234        assert!(bool::from(a.ct_lt(&b)));
235        assert!(bool::from(a.ct_lt(&c)));
236        assert!(bool::from(b.ct_lt(&c)));
237
238        assert!(!bool::from(a.ct_lt(&a)));
239        assert!(!bool::from(b.ct_lt(&b)));
240        assert!(!bool::from(c.ct_lt(&c)));
241
242        assert!(!bool::from(b.ct_lt(&a)));
243        assert!(!bool::from(c.ct_lt(&a)));
244        assert!(!bool::from(c.ct_lt(&b)));
245    }
246
247    #[test]
248    fn lte() {
249        let a = U128::ZERO;
250        let b = U128::ONE;
251        let c = U128::MAX;
252
253        assert!(bool::from(Uint::lte(&a, &b)));
254        assert!(bool::from(Uint::lte(&a, &c)));
255        assert!(bool::from(Uint::lte(&b, &c)));
256
257        assert!(bool::from(Uint::lte(&a, &a)));
258        assert!(bool::from(Uint::lte(&b, &b)));
259        assert!(bool::from(Uint::lte(&c, &c)));
260
261        assert!(!bool::from(Uint::lte(&b, &a)));
262        assert!(!bool::from(Uint::lte(&c, &a)));
263        assert!(!bool::from(Uint::lte(&c, &b)));
264    }
265
266    #[test]
267    fn cmp() {
268        let a = U128::ZERO;
269        let b = U128::ONE;
270        let c = U128::MAX;
271
272        assert_eq!(a.cmp(&b), Ordering::Less);
273        assert_eq!(a.cmp(&c), Ordering::Less);
274        assert_eq!(b.cmp(&c), Ordering::Less);
275
276        assert_eq!(a.cmp(&a), Ordering::Equal);
277        assert_eq!(b.cmp(&b), Ordering::Equal);
278        assert_eq!(c.cmp(&c), Ordering::Equal);
279
280        assert_eq!(b.cmp(&a), Ordering::Greater);
281        assert_eq!(c.cmp(&a), Ordering::Greater);
282        assert_eq!(c.cmp(&b), Ordering::Greater);
283    }
284
285    #[test]
286    fn cmp_vartime() {
287        let a = U128::ZERO;
288        let b = U128::ONE;
289        let c = U128::MAX;
290
291        assert_eq!(a.cmp_vartime(&b), Ordering::Less);
292        assert_eq!(a.cmp_vartime(&c), Ordering::Less);
293        assert_eq!(b.cmp_vartime(&c), Ordering::Less);
294
295        assert_eq!(a.cmp_vartime(&a), Ordering::Equal);
296        assert_eq!(b.cmp_vartime(&b), Ordering::Equal);
297        assert_eq!(c.cmp_vartime(&c), Ordering::Equal);
298
299        assert_eq!(b.cmp_vartime(&a), Ordering::Greater);
300        assert_eq!(c.cmp_vartime(&a), Ordering::Greater);
301        assert_eq!(c.cmp_vartime(&b), Ordering::Greater);
302    }
303}
crypto_bigint/uint/cmp.rs

crypto_bigint/uint/
cmp.rs
