ctutils/traits/
ct_find.rs

1use crate::{Choice, CtAssign, CtOption};
2
3#[cfg(doc)]
4use core::iter::Iterator;
5
6/// Constant-time equivalent of [`Iterator::find`], which can search a collection by iterating over
7/// every element and applying the given predicate to each item, then selecting the first matching
8/// entry.
9pub trait CtFind<T: CtAssign> {
10    /// Iterate through every `T` item in `&self`, applying the given `predicate` which can select
11    /// a specific item by returning [`Choice::TRUE`].
12    ///
13    /// The first item where `predicate` returns [`Choice::TRUE`] is selected, or the [`CtOption`]
14    /// equivalent of `None` is returned if the `predicate` returns [`Choice::FALSE`] for all items.
15    #[must_use]
16    fn ct_find<P>(&self, predicate: P) -> CtOption<T>
17    where
18        P: Fn(&T) -> Choice;
19}
20
21impl<T> CtFind<T> for [T]
22where
23    T: CtAssign + Default,
24{
25    #[inline]
26    fn ct_find<P>(&self, predicate: P) -> CtOption<T>
27    where
28        P: Fn(&T) -> Choice,
29    {
30        let mut ret = CtOption::none();
31
32        for item in self {
33            ret.insert_if(item, predicate(item) & ret.is_none());
34        }
35
36        ret
37    }
38}
39
40impl<T, const N: usize> CtFind<T> for [T; N]
41where
42    T: CtAssign + Default,
43{
44    #[inline]
45    fn ct_find<P>(&self, predicate: P) -> CtOption<T>
46    where
47        P: Fn(&T) -> Choice,
48    {
49        self.as_slice().ct_find(predicate)
50    }
51}
52
53#[cfg(feature = "alloc")]
54mod alloc {
55    use super::{Choice, CtAssign, CtFind, CtOption};
56    use ::alloc::{boxed::Box, vec::Vec};
57
58    impl<T> CtFind<T> for Box<[T]>
59    where
60        T: CtAssign + Default,
61    {
62        #[inline]
63        fn ct_find<P>(&self, predicate: P) -> CtOption<T>
64        where
65            P: Fn(&T) -> Choice,
66        {
67            (**self).ct_find(predicate)
68        }
69    }
70
71    #[cfg(feature = "alloc")]
72    impl<T> CtFind<T> for Vec<T>
73    where
74        T: CtAssign + Default,
75    {
76        #[inline]
77        fn ct_find<P>(&self, predicate: P) -> CtOption<T>
78        where
79            P: Fn(&T) -> Choice,
80        {
81            self.as_slice().ct_find(predicate)
82        }
83    }
84}
85
86#[cfg(test)]
87mod tests {
88    use super::CtFind;
89
90    mod array {
91        use super::*;
92        use crate::{CtEq, CtGt};
93
94        const ARRAY: [u8; 6] = [0, 0, 0, 1, 2, 3];
95
96        #[test]
97        fn ct_find() {
98            // Find the first nonzero even number
99            assert_eq!(
100                ARRAY.ct_find(|n| n.ct_ne(&0) & (n & 1).ct_eq(&0)).unwrap(),
101                2
102            );
103
104            // Predicate where nothing matches
105            assert!(ARRAY.ct_find(|n| n.ct_gt(&3)).is_none().to_bool());
106        }
107    }
108
109    mod slice {
110        use super::*;
111        use crate::{CtEq, CtGt};
112
113        const SLICE: &[u8] = &[0, 0, 0, 1, 2, 3];
114
115        #[test]
116        fn ct_find() {
117            // Find the first nonzero even number
118            assert_eq!(
119                SLICE.ct_find(|n| n.ct_ne(&0) & (n & 1).ct_eq(&0)).unwrap(),
120                2
121            );
122
123            // Predicate where nothing matches
124            assert!(SLICE.ct_find(|n| n.ct_gt(&3)).is_none().to_bool());
125        }
126    }
127}
ctutils/traits/ct_find.rs

ctutils/traits/
ct_find.rs
