crypto_bigint/uint/
cmp.rs

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

crypto_bigint/uint/
cmp.rs
