utils/
bit.rs

1//! Bit manipulation helpers.
2
3use crate::number::UnsignedInteger;
4
5/// Iterator which yields all the set or unset bits in a provided number.
6pub struct BitIterator<T: UnsignedInteger> {
7    n: T,
8}
9
10impl<T: UnsignedInteger> BitIterator<T> {
11    /// Returns an iterator that yields the positions and values of all the set bits in the provided
12    /// number.
13    ///
14    /// # Examples
15    /// ```
16    /// # use utils::bit::BitIterator;
17    /// assert_eq!(
18    ///     BitIterator::ones(0b1001_1101u8).collect::<Vec<(u32, u8)>>(),
19    ///     vec![
20    ///         (0, 1),
21    ///         (2, 4),
22    ///         (3, 8),
23    ///         (4, 16),
24    ///         (7, 128),
25    ///     ],
26    /// );
27    /// ```
28    pub fn ones(n: T) -> Self {
29        BitIterator { n }
30    }
31
32    /// Returns an iterator that yields the positions and values of all the unset bits in the
33    /// provided number.
34    ///
35    /// # Examples
36    /// ```
37    /// # use utils::bit::BitIterator;
38    /// assert_eq!(
39    ///     BitIterator::zeroes(0b1001_1101u8).collect::<Vec<(u32, u8)>>(),
40    ///     vec![
41    ///         (1, 2),
42    ///         (5, 32),
43    ///         (6, 64),
44    ///     ],
45    /// );
46    /// ```
47    pub fn zeroes(n: T) -> Self {
48        BitIterator { n: !n }
49    }
50}
51
52impl<T: UnsignedInteger> Iterator for BitIterator<T> {
53    type Item = (u32, T);
54
55    #[inline]
56    fn next(&mut self) -> Option<Self::Item> {
57        if self.n == T::ZERO {
58            None
59        } else {
60            let position = self.n.trailing_zeros();
61            let value = T::ONE << position;
62            self.n &= !value;
63            Some((position, value))
64        }
65    }
66}
67
68/// Computes the population count for each bit position across 8 input masks.
69///
70/// Returns four masks `[bit0, bit1, bit2, bit3]` that encode, per bit position, the 4-bit count
71/// of how many of the 8 inputs have that bit set.
72///
73/// For example, if a given bit is set in 5 inputs, then that bit would be set in `bit0` and `bit2`.
74/// If a given bit is set in all 8 inputs, then that bit would only be set in `bit3`.
75///
76/// # Examples
77/// ```
78/// # use utils::bit::bitwise_count8;
79/// let [bit0, bit1, bit2, bit3] = bitwise_count8::<u16>(&[
80///                  0b100000000,
81///                  0b110000000,
82///                  0b111000000,
83///                  0b111100000,
84///                  0b111110000,
85///                  0b111111000,
86///                  0b111111100,
87///                  0b111111110,
88/// ]);
89/// assert_eq!(bit0, 0b010101010);
90/// assert_eq!(bit1, 0b011001100);
91/// assert_eq!(bit2, 0b011110000);
92/// assert_eq!(bit3, 0b100000000);
93/// ```
94///
95/// ```
96/// # use utils::bit::bitwise_count8;
97/// let [bit0, bit1, bit2, bit3] = bitwise_count8::<u64>(&[
98///                  0b00111000_01001000_10000111_11111111_10111000_11100010_00110010_01010011,
99///                  0b01110000_00100111_01011101_11011000_10001100_00011000_10100101_00110010,
100///                  0b00000101_11010011_10110011_10000000_00000000_11110110_00000101_11111010,
101///                  0b01101001_01001100_00111001_01101100_00110111_00101011_00010101_10011101,
102///                  0b00011100_11101111_00111111_01101011_00011101_01011110_11101101_10101101,
103///                  0b10111100_11101111_00001001_10100100_01010110_10101011_01011000_11111100,
104///                  0b11110110_00010001_11101111_00101101_01110111_10000011_11110110_10101011,
105///                  0b01110001_01100010_01111101_01001000_01011001_10110100_11100110_11100000,
106/// ]);
107/// assert_eq!(bit0, 0b00000011_10000011_11110100_01100001_01100110_11100101_00100010_00011100);
108/// assert_eq!(bit1, 0b10110001_11010000_11001000_00011011_11110010_01000111_00001110_10100100);
109/// assert_eq!(bit2, 0b01111100_01101111_00111110_11101100_00011101_10111010_11110101_11111011);
110/// assert_eq!(bit3, 0b00000000_00000000_00000001_00000000_00000000_00000000_00000000_00000000);
111/// ```
112#[inline]
113#[must_use]
114pub fn bitwise_count8<T: UnsignedInteger>(m: &[T; 8]) -> [T; 4] {
115    let (s1, c1) = carry_save_adder(m[0], m[1], m[2]);
116    let (s2, c2) = carry_save_adder(m[3], m[4], m[5]);
117    let (s3, c3) = carry_save_adder(m[6], m[7], T::ZERO);
118    let (s4, c4) = carry_save_adder(c1, c2, c3);
119    let (bit0, c5) = carry_save_adder(s1, s2, s3);
120    let (bit1, c6) = carry_save_adder(s4, c5, T::ZERO);
121    let (bit2, bit3) = carry_save_adder(c4, c6, T::ZERO);
122    [bit0, bit1, bit2, bit3]
123}
124
125#[inline]
126#[must_use]
127fn carry_save_adder<T: UnsignedInteger>(a: T, b: T, c: T) -> (T, T) {
128    let sum_ab = a ^ b;
129    let carry_ab = a & b;
130    let sum_abc = sum_ab ^ c;
131    let carry_abc = carry_ab | (sum_ab & c);
132    (sum_abc, carry_abc)
133}
utils/bit.rs

utils/
bit.rs
