crypto_bigint/
const_choice.rs

1use subtle::{Choice, CtOption};
2
3use crate::{modular::SafeGcdInverter, Int, Limb, NonZero, Odd, Uint, WideWord, Word};
4
5/// A boolean value returned by constant-time `const fn`s.
6// TODO: should be replaced by `subtle::Choice` or `CtOption`
7// when `subtle` starts supporting const fns.
8#[derive(Debug, Copy, Clone)]
9pub struct ConstChoice(Word);
10
11impl ConstChoice {
12    /// The falsy value.
13    pub const FALSE: Self = Self(0);
14
15    /// The truthy value.
16    pub const TRUE: Self = Self(Word::MAX);
17
18    #[inline]
19    #[allow(trivial_numeric_casts)]
20    pub(crate) const fn as_u32_mask(&self) -> u32 {
21        self.0 as u32
22    }
23
24    #[inline]
25    #[cfg(target_pointer_width = "32")]
26    pub(crate) const fn as_u64_mask(&self) -> u64 {
27        ((self.0 as u64) << 32) | (self.0 as u64)
28    }
29
30    #[inline]
31    #[cfg(target_pointer_width = "64")]
32    pub(crate) const fn as_u64_mask(&self) -> u64 {
33        self.0
34    }
35
36    /// Returns the truthy value if `value == Word::MAX`, and the falsy value if `value == 0`.
37    /// Panics for other values.
38    #[inline]
39    pub(crate) const fn from_word_mask(value: Word) -> Self {
40        debug_assert!(value == Self::FALSE.0 || value == Self::TRUE.0);
41        Self(value)
42    }
43
44    /// Returns the truthy value if `value == 1`, and the falsy value if `value == 0`.
45    /// Panics for other values.
46    #[inline]
47    pub(crate) const fn from_word_lsb(value: Word) -> Self {
48        debug_assert!(value == 0 || value == 1);
49        Self(value.wrapping_neg())
50    }
51
52    /// Returns the truthy value if the most significant bit of `value` is `1`,
53    /// and the falsy value if it equals `0`.
54    #[inline]
55    pub(crate) const fn from_word_msb(value: Word) -> Self {
56        Self::from_word_lsb(value >> (Word::BITS - 1))
57    }
58
59    /// Returns the truthy value if `value == 1`, and the falsy value if `value == 0`.
60    /// Panics for other values.
61    #[inline]
62    pub(crate) const fn from_wide_word_lsb(value: WideWord) -> Self {
63        debug_assert!(value == 0 || value == 1);
64        Self(value.wrapping_neg() as Word)
65    }
66
67    #[inline]
68    pub(crate) const fn from_u32_lsb(value: u32) -> Self {
69        debug_assert!(value == 0 || value == 1);
70        #[allow(trivial_numeric_casts)]
71        Self((value as Word).wrapping_neg())
72    }
73
74    #[inline]
75    pub(crate) const fn from_u64_lsb(value: u64) -> Self {
76        debug_assert!(value == 0 || value == 1);
77        #[allow(trivial_numeric_casts)]
78        Self((value as Word).wrapping_neg())
79    }
80
81    /// Returns the truthy value if `value != 0`, and the falsy value otherwise.
82    #[inline]
83    pub(crate) const fn from_u32_nonzero(value: u32) -> Self {
84        Self::from_u32_lsb((value | value.wrapping_neg()) >> (u32::BITS - 1))
85    }
86
87    /// Returns the truthy value if `value != 0`, and the falsy value otherwise.
88    #[inline]
89    pub(crate) const fn from_u64_nonzero(value: u64) -> Self {
90        Self::from_u64_lsb((value | value.wrapping_neg()) >> (u64::BITS - 1))
91    }
92
93    /// Returns the truthy value if `value != 0`, and the falsy value otherwise.
94    #[inline]
95    pub(crate) const fn from_word_nonzero(value: Word) -> Self {
96        Self::from_word_lsb((value | value.wrapping_neg()) >> (Word::BITS - 1))
97    }
98
99    /// Returns the truthy value if `x == y`, and the falsy value otherwise.
100    #[inline]
101    pub(crate) const fn from_u32_eq(x: u32, y: u32) -> Self {
102        Self::from_u32_nonzero(x ^ y).not()
103    }
104
105    /// Returns the truthy value if `x == y`, and the falsy value otherwise.
106    #[inline]
107    pub(crate) const fn from_u64_eq(x: u64, y: u64) -> Self {
108        Self::from_u64_nonzero(x ^ y).not()
109    }
110
111    /// Returns the truthy value if `x == y`, and the falsy value otherwise.
112    #[inline]
113    pub(crate) const fn from_word_eq(x: Word, y: Word) -> Self {
114        Self::from_word_nonzero(x ^ y).not()
115    }
116
117    /// Returns the truthy value if `x < y`, and the falsy value otherwise.
118    #[inline]
119    pub(crate) const fn from_word_lt(x: Word, y: Word) -> Self {
120        // See "Hacker's Delight" 2nd ed, section 2-12 (Comparison predicates)
121        let bit = (((!x) & y) | (((!x) | y) & (x.wrapping_sub(y)))) >> (Word::BITS - 1);
122        Self::from_word_lsb(bit)
123    }
124
125    /// Returns the truthy value if `x > y`, and the falsy value otherwise.
126    #[inline]
127    pub(crate) const fn from_word_gt(x: Word, y: Word) -> Self {
128        Self::from_word_lt(y, x)
129    }
130
131    /// Returns the truthy value if `x < y`, and the falsy value otherwise.
132    #[inline]
133    pub(crate) const fn from_u32_lt(x: u32, y: u32) -> Self {
134        // See "Hacker's Delight" 2nd ed, section 2-12 (Comparison predicates)
135        let bit = (((!x) & y) | (((!x) | y) & (x.wrapping_sub(y)))) >> (u32::BITS - 1);
136        Self::from_u32_lsb(bit)
137    }
138
139    /// Returns the truthy value if `x <= y` and the falsy value otherwise.
140    #[inline]
141    pub(crate) const fn from_word_le(x: Word, y: Word) -> Self {
142        // See "Hacker's Delight" 2nd ed, section 2-12 (Comparison predicates)
143        let bit = (((!x) | y) & ((x ^ y) | !(y.wrapping_sub(x)))) >> (Word::BITS - 1);
144        Self::from_word_lsb(bit)
145    }
146
147    /// Returns the truthy value if `x <= y` and the falsy value otherwise.
148    #[inline]
149    pub(crate) const fn from_wide_word_le(x: WideWord, y: WideWord) -> Self {
150        // See "Hacker's Delight" 2nd ed, section 2-12 (Comparison predicates)
151        let bit = (((!x) | y) & ((x ^ y) | !(y.wrapping_sub(x)))) >> (WideWord::BITS - 1);
152        Self::from_wide_word_lsb(bit)
153    }
154
155    /// Returns the truthy value if `x <= y` and the falsy value otherwise.
156    #[inline]
157    pub(crate) const fn from_u32_le(x: u32, y: u32) -> Self {
158        // See "Hacker's Delight" 2nd ed, section 2-12 (Comparison predicates)
159        let bit = (((!x) | y) & ((x ^ y) | !(y.wrapping_sub(x)))) >> (u32::BITS - 1);
160        Self::from_u32_lsb(bit)
161    }
162
163    /// Returns the truthy value if `x < y`, and the falsy value otherwise.
164    #[inline]
165    pub(crate) const fn from_u64_lt(x: u64, y: u64) -> Self {
166        // See "Hacker's Delight" 2nd ed, section 2-12 (Comparison predicates)
167        let bit = (((!x) & y) | (((!x) | y) & (x.wrapping_sub(y)))) >> (u64::BITS - 1);
168        Self::from_u64_lsb(bit)
169    }
170
171    /// Returns the truthy value if `x > y`, and the falsy value otherwise.
172    #[inline]
173    pub(crate) const fn from_u64_gt(x: u64, y: u64) -> Self {
174        Self::from_u64_lt(y, x)
175    }
176
177    #[inline]
178    pub(crate) const fn not(&self) -> Self {
179        Self(!self.0)
180    }
181
182    #[inline]
183    pub(crate) const fn or(&self, other: Self) -> Self {
184        Self(self.0 | other.0)
185    }
186
187    #[inline]
188    pub(crate) const fn and(&self, other: Self) -> Self {
189        Self(self.0 & other.0)
190    }
191
192    #[inline]
193    pub(crate) const fn xor(&self, other: Self) -> Self {
194        Self(self.0 ^ other.0)
195    }
196
197    #[inline]
198    pub(crate) const fn ne(&self, other: Self) -> Self {
199        Self::xor(self, other)
200    }
201
202    #[inline]
203    pub(crate) const fn eq(&self, other: Self) -> Self {
204        Self::ne(self, other).not()
205    }
206
207    /// Return `b` if `self` is truthy, otherwise return `a`.
208    #[inline]
209    pub(crate) const fn select_word(&self, a: Word, b: Word) -> Word {
210        a ^ (self.0 & (a ^ b))
211    }
212
213    /// Return `b` if `self` is truthy, otherwise return `a`.
214    #[inline]
215    pub(crate) const fn select_wide_word(&self, a: WideWord, b: WideWord) -> WideWord {
216        let mask = ((self.0 as WideWord) << Word::BITS) | (self.0 as WideWord);
217        a ^ (mask & (a ^ b))
218    }
219
220    /// Return `b` if `self` is truthy, otherwise return `a`.
221    #[inline]
222    pub(crate) const fn select_u32(&self, a: u32, b: u32) -> u32 {
223        a ^ (self.as_u32_mask() & (a ^ b))
224    }
225
226    /// Return `b` if `self` is truthy, otherwise return `a`.
227    #[inline]
228    pub(crate) const fn select_u64(&self, a: u64, b: u64) -> u64 {
229        a ^ (self.as_u64_mask() & (a ^ b))
230    }
231
232    /// Return `x` if `self` is truthy, otherwise return 0.
233    #[inline]
234    pub(crate) const fn if_true_word(&self, x: Word) -> Word {
235        x & self.0
236    }
237
238    /// Return `x` if `self` is truthy, otherwise return 0.
239    #[inline]
240    pub(crate) const fn if_true_u32(&self, x: u32) -> u32 {
241        x & self.as_u32_mask()
242    }
243
244    #[inline]
245    pub(crate) const fn is_true_vartime(&self) -> bool {
246        self.0 == ConstChoice::TRUE.0
247    }
248
249    #[inline]
250    pub(crate) const fn to_u8(self) -> u8 {
251        (self.0 as u8) & 1
252    }
253
254    /// WARNING: this method should only be used in contexts that aren't constant-time critical!
255    #[inline]
256    pub(crate) const fn to_bool_vartime(self) -> bool {
257        self.to_u8() != 0
258    }
259}
260
261impl From<ConstChoice> for Choice {
262    #[inline]
263    fn from(choice: ConstChoice) -> Self {
264        Choice::from(choice.to_u8())
265    }
266}
267
268impl From<Choice> for ConstChoice {
269    #[inline]
270    fn from(choice: Choice) -> Self {
271        ConstChoice::from_word_lsb(choice.unwrap_u8() as Word)
272    }
273}
274
275impl From<ConstChoice> for bool {
276    fn from(choice: ConstChoice) -> Self {
277        choice.is_true_vartime()
278    }
279}
280
281impl PartialEq for ConstChoice {
282    fn eq(&self, other: &Self) -> bool {
283        self.0 == other.0
284    }
285}
286
287/// An equivalent of `subtle::CtOption` usable in a `const fn` context.
288#[derive(Debug, Clone)]
289pub struct ConstCtOption<T> {
290    value: T,
291    is_some: ConstChoice,
292}
293
294impl<T> ConstCtOption<T> {
295    #[inline]
296    pub(crate) const fn new(value: T, is_some: ConstChoice) -> Self {
297        Self { value, is_some }
298    }
299
300    #[inline]
301    pub(crate) const fn some(value: T) -> Self {
302        Self {
303            value,
304            is_some: ConstChoice::TRUE,
305        }
306    }
307
308    #[inline]
309    pub(crate) const fn none(dummy_value: T) -> Self {
310        Self {
311            value: dummy_value,
312            is_some: ConstChoice::FALSE,
313        }
314    }
315
316    /// Returns a reference to the contents of this structure.
317    ///
318    /// **Note:** if the second element is `None`, the first value may take any value.
319    #[inline]
320    pub(crate) const fn components_ref(&self) -> (&T, ConstChoice) {
321        // Since Rust is not smart enough to tell that we would be moving the value,
322        // and hence no destructors will be called, we have to return a reference instead.
323        // See https://github.com/rust-lang/rust/issues/66753
324        (&self.value, self.is_some)
325    }
326
327    /// Returns a true [`ConstChoice`] if this value is `Some`.
328    #[inline]
329    pub const fn is_some(&self) -> ConstChoice {
330        self.is_some
331    }
332
333    /// Returns a true [`ConstChoice`] if this value is `None`.
334    #[inline]
335    pub const fn is_none(&self) -> ConstChoice {
336        self.is_some.not()
337    }
338
339    /// This returns the underlying value but panics if it is not `Some`.
340    #[inline]
341    pub fn unwrap(self) -> T {
342        assert!(self.is_some.is_true_vartime());
343        self.value
344    }
345
346    /// Apply an additional [`ConstChoice`] requirement to `is_some`.
347    #[inline]
348    pub(crate) const fn and_choice(mut self, is_some: ConstChoice) -> Self {
349        self.is_some = self.is_some.and(is_some);
350        self
351    }
352}
353
354impl<T> From<ConstCtOption<T>> for CtOption<T> {
355    #[inline]
356    fn from(value: ConstCtOption<T>) -> Self {
357        CtOption::new(value.value, value.is_some.into())
358    }
359}
360
361impl<T> From<ConstCtOption<T>> for Option<T> {
362    #[inline]
363    fn from(value: ConstCtOption<T>) -> Self {
364        if value.is_some.into() {
365            Some(value.value)
366        } else {
367            None
368        }
369    }
370}
371
372// Need specific implementations to work around the
373// "destructors cannot be evaluated at compile-time" error
374// See https://github.com/rust-lang/rust/issues/66753
375
376impl<const LIMBS: usize> ConstCtOption<Uint<LIMBS>> {
377    /// This returns the underlying value if it is `Some` or the provided value otherwise.
378    #[inline]
379    pub const fn unwrap_or(self, def: Uint<LIMBS>) -> Uint<LIMBS> {
380        Uint::select(&def, &self.value, self.is_some)
381    }
382
383    /// Returns the contained value, consuming the `self` value.
384    ///
385    /// # Panics
386    ///
387    /// Panics if the value is none with a custom panic message provided by
388    /// `msg`.
389    #[inline]
390    pub const fn expect(self, msg: &str) -> Uint<LIMBS> {
391        assert!(self.is_some.is_true_vartime(), "{}", msg);
392        self.value
393    }
394
395    /// Returns the contained value, interpreting the underlying [`Uint`] value as an [`Int`].
396    #[inline]
397    pub const fn as_int(&self) -> ConstCtOption<Int<LIMBS>> {
398        ConstCtOption::new(self.value.as_int(), self.is_some)
399    }
400}
401
402impl<const LIMBS: usize> ConstCtOption<(Uint<LIMBS>, Uint<LIMBS>)> {
403    /// Returns the contained value, consuming the `self` value.
404    ///
405    /// # Panics
406    ///
407    /// Panics if the value is none with a custom panic message provided by
408    /// `msg`.
409    #[inline]
410    pub const fn expect(self, msg: &str) -> (Uint<LIMBS>, Uint<LIMBS>) {
411        assert!(self.is_some.is_true_vartime(), "{}", msg);
412        self.value
413    }
414}
415
416impl<const LIMBS: usize> ConstCtOption<NonZero<Uint<LIMBS>>> {
417    /// Returns the contained value, consuming the `self` value.
418    ///
419    /// # Panics
420    ///
421    /// Panics if the value is none with a custom panic message provided by
422    /// `msg`.
423    #[inline]
424    pub const fn expect(self, msg: &str) -> NonZero<Uint<LIMBS>> {
425        assert!(self.is_some.is_true_vartime(), "{}", msg);
426        self.value
427    }
428}
429
430impl<const LIMBS: usize> ConstCtOption<Odd<Uint<LIMBS>>> {
431    /// Returns the contained value, consuming the `self` value.
432    ///
433    /// # Panics
434    ///
435    /// Panics if the value is none with a custom panic message provided by
436    /// `msg`.
437    #[inline]
438    pub const fn expect(self, msg: &str) -> Odd<Uint<LIMBS>> {
439        assert!(self.is_some.is_true_vartime(), "{}", msg);
440        self.value
441    }
442}
443
444impl<const LIMBS: usize> ConstCtOption<Int<LIMBS>> {
445    /// This returns the underlying value if it is `Some` or the provided value otherwise.
446    #[inline]
447    pub const fn unwrap_or(self, def: Int<LIMBS>) -> Int<LIMBS> {
448        Int::select(&def, &self.value, self.is_some)
449    }
450
451    /// Returns the contained value, consuming the `self` value.
452    ///
453    /// # Panics
454    ///
455    /// Panics if the value is none with a custom panic message provided by
456    /// `msg`.
457    #[inline]
458    pub const fn expect(self, msg: &str) -> Int<LIMBS> {
459        assert!(self.is_some.is_true_vartime(), "{}", msg);
460        self.value
461    }
462}
463
464impl ConstCtOption<NonZero<Limb>> {
465    /// Returns the contained value, consuming the `self` value.
466    ///
467    /// # Panics
468    ///
469    /// Panics if the value is none with a custom panic message provided by
470    /// `msg`.
471    #[inline]
472    pub const fn expect(self, msg: &str) -> NonZero<Limb> {
473        assert!(self.is_some.is_true_vartime(), "{}", msg);
474        self.value
475    }
476}
477
478impl<const SAT_LIMBS: usize, const UNSAT_LIMBS: usize>
479    ConstCtOption<SafeGcdInverter<SAT_LIMBS, UNSAT_LIMBS>>
480{
481    /// Returns the contained value, consuming the `self` value.
482    ///
483    /// # Panics
484    ///
485    /// Panics if the value is none with a custom panic message provided by
486    /// `msg`.
487    #[inline]
488    pub const fn expect(self, msg: &str) -> SafeGcdInverter<SAT_LIMBS, UNSAT_LIMBS> {
489        assert!(self.is_some.is_true_vartime(), "{}", msg);
490        self.value
491    }
492}
493
494#[cfg(test)]
495mod tests {
496    use crate::{WideWord, Word};
497
498    use super::ConstChoice;
499
500    #[test]
501    fn from_u64_lsb() {
502        assert_eq!(ConstChoice::from_u64_lsb(0), ConstChoice::FALSE);
503        assert_eq!(ConstChoice::from_u64_lsb(1), ConstChoice::TRUE);
504    }
505
506    #[test]
507    fn from_word_lt() {
508        assert_eq!(ConstChoice::from_word_lt(4, 5), ConstChoice::TRUE);
509        assert_eq!(ConstChoice::from_word_lt(5, 5), ConstChoice::FALSE);
510        assert_eq!(ConstChoice::from_word_lt(6, 5), ConstChoice::FALSE);
511    }
512
513    #[test]
514    fn from_word_gt() {
515        assert_eq!(ConstChoice::from_word_gt(4, 5), ConstChoice::FALSE);
516        assert_eq!(ConstChoice::from_word_gt(5, 5), ConstChoice::FALSE);
517        assert_eq!(ConstChoice::from_word_gt(6, 5), ConstChoice::TRUE);
518    }
519
520    #[test]
521    fn from_wide_word_le() {
522        assert_eq!(ConstChoice::from_wide_word_le(4, 5), ConstChoice::TRUE);
523        assert_eq!(ConstChoice::from_wide_word_le(5, 5), ConstChoice::TRUE);
524        assert_eq!(ConstChoice::from_wide_word_le(6, 5), ConstChoice::FALSE);
525    }
526
527    #[test]
528    fn select_u32() {
529        let a: u32 = 1;
530        let b: u32 = 2;
531        assert_eq!(ConstChoice::TRUE.select_u32(a, b), b);
532        assert_eq!(ConstChoice::FALSE.select_u32(a, b), a);
533    }
534
535    #[test]
536    fn select_u64() {
537        let a: u64 = 1;
538        let b: u64 = 2;
539        assert_eq!(ConstChoice::TRUE.select_u64(a, b), b);
540        assert_eq!(ConstChoice::FALSE.select_u64(a, b), a);
541    }
542
543    #[test]
544    fn select_word() {
545        let a: Word = 1;
546        let b: Word = 2;
547        assert_eq!(ConstChoice::TRUE.select_word(a, b), b);
548        assert_eq!(ConstChoice::FALSE.select_word(a, b), a);
549    }
550
551    #[test]
552    fn select_wide_word() {
553        let a: WideWord = (1 << Word::BITS) + 1;
554        let b: WideWord = (3 << Word::BITS) + 4;
555        assert_eq!(ConstChoice::TRUE.select_wide_word(a, b), b);
556        assert_eq!(ConstChoice::FALSE.select_wide_word(a, b), a);
557    }
558}
crypto_bigint/const_choice.rs

crypto_bigint/
const_choice.rs
