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        let position = self.n.lowest_one()?;
58        let value = self.n.isolate_lowest_one();
59        self.n ^= value;
60        Some((position, value))
61    }
62}
63
64/// Computes the population count for each bit position across 4 input masks.
65///
66/// Returns three masks `[bit0, bit1, bit2]` that encode, per bit position, the 3-bit count
67/// of how many of the 4 inputs have that bit set.
68///
69/// For example, if a given bit is set in 3 inputs, then that bit would be set in `bit0` and `bit1`.
70/// If a given bit is set in all 4 inputs, then that bit would only be set in `bit2`.
71///
72/// # Examples
73/// ```
74/// # use utils::bit::bitwise_count4;
75/// let [bit0, bit1, bit2] = bitwise_count4::<u8>(&[
76///     0b10000,
77///     0b11000,
78///     0b11100,
79///     0b11110,
80/// ]);
81/// assert_eq!(bit0, 0b01010);
82/// assert_eq!(bit1, 0b01100);
83/// assert_eq!(bit2, 0b10000);
84/// ```
85#[inline]
86#[must_use]
87pub fn bitwise_count4<T: UnsignedInteger>(m: &[T; 4]) -> [T; 3] {
88    let (sum, carry1) = carry_save_adder(m[0], m[1], m[2]);
89    let (bit0, carry2) = carry_save_adder(sum, m[3], T::ZERO);
90    let (bit1, bit2) = carry_save_adder(carry1, carry2, T::ZERO);
91    [bit0, bit1, bit2]
92}
93
94/// Computes the population count for each bit position across 8 input masks.
95///
96/// Returns four masks `[bit0, bit1, bit2, bit3]` that encode, per bit position, the 4-bit count
97/// of how many of the 8 inputs have that bit set.
98///
99/// For example, if a given bit is set in 5 inputs, then that bit would be set in `bit0` and `bit2`.
100/// If a given bit is set in all 8 inputs, then that bit would only be set in `bit3`.
101///
102/// # Examples
103/// ```
104/// # use utils::bit::bitwise_count8;
105/// let [bit0, bit1, bit2, bit3] = bitwise_count8::<u16>(&[
106///                  0b100000000,
107///                  0b110000000,
108///                  0b111000000,
109///                  0b111100000,
110///                  0b111110000,
111///                  0b111111000,
112///                  0b111111100,
113///                  0b111111110,
114/// ]);
115/// assert_eq!(bit0, 0b010101010);
116/// assert_eq!(bit1, 0b011001100);
117/// assert_eq!(bit2, 0b011110000);
118/// assert_eq!(bit3, 0b100000000);
119/// ```
120///
121/// ```
122/// # use utils::bit::bitwise_count8;
123/// let [bit0, bit1, bit2, bit3] = bitwise_count8::<u64>(&[
124///                  0b00111000_01001000_10000111_11111111_10111000_11100010_00110010_01010011,
125///                  0b01110000_00100111_01011101_11011000_10001100_00011000_10100101_00110010,
126///                  0b00000101_11010011_10110011_10000000_00000000_11110110_00000101_11111010,
127///                  0b01101001_01001100_00111001_01101100_00110111_00101011_00010101_10011101,
128///                  0b00011100_11101111_00111111_01101011_00011101_01011110_11101101_10101101,
129///                  0b10111100_11101111_00001001_10100100_01010110_10101011_01011000_11111100,
130///                  0b11110110_00010001_11101111_00101101_01110111_10000011_11110110_10101011,
131///                  0b01110001_01100010_01111101_01001000_01011001_10110100_11100110_11100000,
132/// ]);
133/// assert_eq!(bit0, 0b00000011_10000011_11110100_01100001_01100110_11100101_00100010_00011100);
134/// assert_eq!(bit1, 0b10110001_11010000_11001000_00011011_11110010_01000111_00001110_10100100);
135/// assert_eq!(bit2, 0b01111100_01101111_00111110_11101100_00011101_10111010_11110101_11111011);
136/// assert_eq!(bit3, 0b00000000_00000000_00000001_00000000_00000000_00000000_00000000_00000000);
137/// ```
138#[inline]
139#[must_use]
140pub fn bitwise_count8<T: UnsignedInteger>(m: &[T; 8]) -> [T; 4] {
141    let (s1, c1) = carry_save_adder(m[0], m[1], m[2]);
142    let (s2, c2) = carry_save_adder(m[3], m[4], m[5]);
143    let (s3, c3) = carry_save_adder(m[6], m[7], T::ZERO);
144    let (s4, c4) = carry_save_adder(c1, c2, c3);
145    let (bit0, c5) = carry_save_adder(s1, s2, s3);
146    let (bit1, c6) = carry_save_adder(s4, c5, T::ZERO);
147    let (bit2, bit3) = carry_save_adder(c4, c6, T::ZERO);
148    [bit0, bit1, bit2, bit3]
149}
150
151#[inline]
152#[must_use]
153fn carry_save_adder<T: UnsignedInteger>(a: T, b: T, c: T) -> (T, T) {
154    let sum_ab = a ^ b;
155    let carry_ab = a & b;
156    let sum_abc = sum_ab ^ c;
157    let carry_abc = carry_ab | (sum_ab & c);
158    (sum_abc, carry_abc)
159}
utils/bit.rs

utils/
bit.rs
