crypto_bigint/uint/
cmp.rs

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

crypto_bigint/uint/
cmp.rs
