crypto_bigint/uint/ref_type/
cmp.rs

1//! [`UintRef`] comparison operations.
2//!
3//! Constant time unless explicitly noted otherwise.
4
5use core::{cmp::Ordering, mem::transmute};
6
7use super::UintRef;
8use crate::{Choice, Limb, word};
9
10impl UintRef {
11    /// Returns the truthy value if `self` is odd or the falsy value otherwise.
12    #[inline]
13    #[must_use]
14    pub const fn is_odd(&self) -> Choice {
15        debug_assert!(self.nlimbs() >= 1, "should have limbs");
16        word::choice_from_lsb(self.limbs[0].0 & 1)
17    }
18
19    /// Returns [`Choice::TRUE`] if `self` != `0` or [`Choice::FALSE`] otherwise.
20    #[inline]
21    #[must_use]
22    pub const fn is_nonzero(&self) -> Choice {
23        let mut b = 0;
24        let mut i = 0;
25        while i < self.nlimbs() {
26            b |= self.limbs[i].0;
27            i += 1;
28        }
29        Limb(b).is_nonzero()
30    }
31
32    /// Are all of limbs equal to `0`?
33    #[inline]
34    #[must_use]
35    pub const fn is_zero(&self) -> Choice {
36        self.is_nonzero().not()
37    }
38
39    /// Determine in variable time whether the `self` is zero.
40    #[inline]
41    pub(crate) const fn is_zero_vartime(&self) -> bool {
42        let mut i = 0;
43        while i < self.nlimbs() {
44            if self.limbs[i].0 != 0 {
45                return false;
46            }
47            i += 1;
48        }
49        true
50    }
51
52    /// Returns the Ordering between `lhs` and `rhs`.
53    #[allow(clippy::cast_possible_wrap)]
54    #[inline(always)]
55    pub(crate) const fn cmp(lhs: &Self, rhs: &Self) -> Ordering {
56        let overlap = if lhs.nlimbs() < rhs.nlimbs() {
57            lhs.nlimbs()
58        } else {
59            rhs.nlimbs()
60        };
61
62        let mut borrow = Limb::ZERO;
63        let mut diff = Limb::ZERO;
64        let mut i = 0;
65
66        while i < overlap {
67            let (w, b) = rhs.limbs[i].borrowing_sub(lhs.limbs[i], borrow);
68            diff = diff.bitor(w);
69            borrow = b;
70            i += 1;
71        }
72        let lesser = rhs.trailing(overlap).is_nonzero();
73        let greater = lhs.trailing(overlap).is_nonzero();
74
75        // FIXME cast_signed() is stable in Rust 1.87
76        let sgn = borrow
77            .lsb_to_choice()
78            .and(lesser.not())
79            .or(greater)
80            .select_u8(255, 1) as i8;
81        let ord = (diff.is_nonzero().or(lesser).or(greater).to_u8_vartime() as i8) * sgn;
82
83        #[allow(unsafe_code)]
84        // SAFETY: Ordering is repr(i8)
85        unsafe {
86            transmute(ord)
87        }
88    }
89
90    /// Returns the Ordering between `self` and `rhs` in variable time.
91    #[inline(always)]
92    #[must_use]
93    pub const fn cmp_vartime(&self, rhs: &Self) -> Ordering {
94        if self.nlimbs() < rhs.nlimbs() {
95            return rhs.cmp_vartime(self).reverse();
96        }
97
98        let mut i = self.nlimbs();
99        while i > rhs.nlimbs() {
100            i -= 1;
101            if self.limbs[i].0 != 0 {
102                return Ordering::Greater;
103            }
104        }
105        while i > 0 {
106            i -= 1;
107            let (val, borrow) = self.limbs[i].borrowing_sub(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        }
116
117        Ordering::Equal
118    }
119
120    /// Returns the truthy value if `self < rhs` and the falsy value otherwise.
121    #[inline(always)]
122    pub(crate) const fn lt(lhs: &Self, rhs: &Self) -> Choice {
123        let overlap = if lhs.nlimbs() < rhs.nlimbs() {
124            lhs.nlimbs()
125        } else {
126            rhs.nlimbs()
127        };
128
129        // NOTE: this is effectively a `borrowing_sub` that only computes the borrow
130        let mut i = 0;
131        let mut borrow = Limb::ZERO;
132
133        while i < overlap {
134            borrow = lhs.limbs[i].borrowing_sub(rhs.limbs[i], borrow).1;
135            i += 1;
136        }
137        let lesser = rhs.trailing(overlap).is_nonzero();
138        let greater = lhs.trailing(overlap).is_nonzero();
139        borrow.lsb_to_choice().and(greater.not()).or(lesser)
140    }
141}
142
143#[cfg(test)]
144mod tests {
145    use core::cmp::Ordering;
146
147    use super::UintRef;
148    use crate::Limb;
149
150    #[test]
151    fn cmp() {
152        let z_small = UintRef::new(&[Limb::ZERO, Limb::ZERO]);
153        let z_big = UintRef::new(&[Limb::ZERO, Limb::ZERO, Limb::ZERO]);
154        let a = UintRef::new(&[Limb::ZERO, Limb::ZERO, Limb::ONE]);
155        let b = UintRef::new(&[Limb::ONE, Limb::ZERO]);
156
157        assert_eq!(UintRef::cmp(z_small, z_big), Ordering::Equal);
158        assert_eq!(UintRef::cmp(z_big, z_small), Ordering::Equal);
159        assert_eq!(UintRef::cmp(z_small, a), Ordering::Less);
160        assert_eq!(UintRef::cmp(z_big, a), Ordering::Less);
161        assert_eq!(UintRef::cmp(a, z_small), Ordering::Greater);
162        assert_eq!(UintRef::cmp(a, z_big), Ordering::Greater);
163        assert_eq!(UintRef::cmp(a, b), Ordering::Greater);
164        assert_eq!(UintRef::cmp(b, a), Ordering::Less);
165
166        assert_eq!(UintRef::cmp_vartime(z_small, z_big), Ordering::Equal);
167        assert_eq!(UintRef::cmp_vartime(z_big, z_small), Ordering::Equal);
168        assert_eq!(UintRef::cmp_vartime(z_small, a), Ordering::Less);
169        assert_eq!(UintRef::cmp_vartime(z_big, a), Ordering::Less);
170        assert_eq!(UintRef::cmp_vartime(a, z_small), Ordering::Greater);
171        assert_eq!(UintRef::cmp_vartime(a, z_big), Ordering::Greater);
172        assert_eq!(UintRef::cmp_vartime(a, b), Ordering::Greater);
173        assert_eq!(UintRef::cmp_vartime(b, a), Ordering::Less);
174    }
175
176    #[test]
177    fn lt() {
178        let lesser = UintRef::new(&[Limb::ZERO, Limb::ZERO, Limb::ZERO]);
179        let greater = UintRef::new(&[Limb::ZERO, Limb::ONE, Limb::ZERO]);
180        assert!(UintRef::lt(lesser, greater).to_bool());
181        assert!(!UintRef::lt(greater, lesser).to_bool());
182
183        let smaller = UintRef::new(&[Limb::ZERO, Limb::ZERO]);
184        let bigger = UintRef::new(&[Limb::ZERO, Limb::ZERO, Limb::ONE]);
185        assert!(UintRef::lt(smaller, bigger).to_bool());
186        assert!(!UintRef::lt(bigger, smaller).to_bool());
187    }
188}
crypto_bigint/uint/ref_type/cmp.rs

crypto_bigint/uint/ref_type/
cmp.rs
