openzeppelin_crypto/
bits.rs

1//! Bit manipulation utilities.
2
3/// Iterates over bits in big-endian order.
4pub trait BitIteratorBE: Sized {
5    /// Returns an iterator over the bits of the integer, starting from the most
6    /// significant bit.
7    fn bit_be_iter(self) -> impl Iterator<Item = bool>;
8
9    /// Returns an iterator over the bits of the integer, starting from the most
10    /// significant bit, and without leading zeroes.
11    fn bit_be_trimmed_iter(self) -> impl Iterator<Item = bool> {
12        self.bit_be_iter().skip_while(|&b| !b)
13    }
14}
15
16macro_rules! impl_bit_iter_be {
17    ($int:ty) => {
18        impl BitIteratorBE for $int {
19            fn bit_be_iter(self) -> impl Iterator<Item = bool> {
20                (0..<$int>::BITS).rev().map(move |i| self & (1 << i) != 0)
21            }
22        }
23    };
24}
25
26impl_bit_iter_be!(u8);
27impl_bit_iter_be!(u16);
28impl_bit_iter_be!(u32);
29impl_bit_iter_be!(u64);
30impl_bit_iter_be!(u128);
31impl_bit_iter_be!(usize);
32
33#[cfg(test)]
34mod tests {
35    use num_traits::ConstOne;
36    use proptest::prelude::*;
37
38    use super::*;
39
40    #[test]
41    fn known_pattern() {
42        let value = 0b1100u64;
43        let full = value.bit_be_iter().collect::<Vec<_>>();
44        let expected = [false; 60]
45            .iter()
46            .chain(&[true, true, false, false])
47            .copied()
48            .collect::<Vec<_>>();
49        assert_eq!(full, expected);
50
51        let trimmed = value.bit_be_trimmed_iter().collect::<Vec<_>>();
52        let expected = vec![true, true, false, false];
53        assert_eq!(trimmed, expected);
54    }
55
56    macro_rules! trimmed_is_subset_of_full {
57        ($ty:ident) => {{
58            proptest!(|(value: $ty)| {
59                let full: Vec<bool> = value.bit_be_iter().collect();
60                let trimmed: Vec<bool> = value.bit_be_trimmed_iter().collect();
61                let start_idx = value.leading_zeros() as usize;
62                prop_assert_eq!(&full[start_idx..], trimmed);
63            });
64        }};
65    }
66
67    #[test]
68    fn trimmed_is_subset_of_full() {
69        trimmed_is_subset_of_full!(u8);
70        trimmed_is_subset_of_full!(u16);
71        trimmed_is_subset_of_full!(u32);
72        trimmed_is_subset_of_full!(u64);
73        trimmed_is_subset_of_full!(u128);
74        trimmed_is_subset_of_full!(usize);
75    }
76
77    macro_rules! edge_case {
78        ($ty:ident) => {{
79            assert_eq!($ty::MIN.bit_be_trimmed_iter().count(), 0);
80            assert_eq!($ty::MIN.bit_be_iter().count(), $ty::BITS as usize);
81            assert_eq!(
82                $ty::MAX.bit_be_trimmed_iter().count(),
83                $ty::BITS as usize
84            );
85            assert_eq!($ty::MAX.bit_be_iter().count(), $ty::BITS as usize);
86            assert_eq!($ty::ONE.bit_be_trimmed_iter().count(), usize::ONE);
87        }};
88    }
89
90    #[test]
91    fn edge_cases() {
92        edge_case!(u8);
93        edge_case!(u16);
94        edge_case!(u32);
95        edge_case!(u64);
96        edge_case!(u128);
97        edge_case!(usize);
98    }
99}
openzeppelin_crypto/bits.rs

openzeppelin_crypto/
bits.rs
