Skip to main content

deq_runtime/misc/
bit_vector.rs

1use crate::util::BitVector;
2
3pub fn pack_bits(array: &[bool]) -> Vec<u8> {
4    let mut packed: Vec<u8> = vec![0; bit_vector_len(array.len() as u64)];
5    for (i, &bit) in array.iter().enumerate() {
6        if bit {
7            packed[i / 8] |= 1 << (7 - (i % 8));
8        }
9    }
10    packed
11}
12
13pub fn unpack_bits(data: &[u8], size: u64) -> Vec<bool> {
14    debug_assert!(data.len() == bit_vector_len(size));
15    assert!((size as usize) <= data.len() * 8);
16    let mut bits: Vec<bool> = vec![false; size as usize];
17    for i in 0..size as usize {
18        bits[i] = (data[i / 8] & (1 << (7 - (i % 8)))) != 0;
19    }
20    bits
21}
22
23pub fn xor_bits(a: &BitVector, b: &BitVector) -> BitVector {
24    let mut result = a.clone();
25    xor_bits_in_place(&mut result, b);
26    result
27}
28
29pub fn xor_bits_in_place(a: &mut BitVector, b: &BitVector) {
30    debug_assert!(a.size == b.size);
31    for i in 0..a.data.len() {
32        a.data[i] ^= b.data[i];
33    }
34}
35
36#[inline]
37pub fn byte_bit_index(index: u64) -> (usize, u8) {
38    let byte_index = (index / 8) as usize;
39    let bit_index = 7 - ((index % 8) as u8);
40    (byte_index, bit_index)
41}
42
43#[inline]
44pub fn bit_vector_len(size: u64) -> usize {
45    size.div_ceil(8) as usize // (size + 7) / 8
46}
47
48pub fn from_sparse_indices(size: u64, indices: &[u64]) -> BitVector {
49    let mut data = vec![0u8; bit_vector_len(size)];
50    for &idx in indices {
51        let (byte_index, bit_index) = byte_bit_index(idx);
52        data[byte_index] |= 1 << bit_index;
53    }
54    BitVector { size, data }
55}
56
57pub fn to_sparse_indices(bit_vector: &BitVector) -> Vec<u64> {
58    let mut indices = vec![];
59    for index in 0..bit_vector.size {
60        if get_bit(bit_vector, index) {
61            indices.push(index);
62        }
63    }
64    indices
65}
66
67/// Return whether every meaningful bit is zero, ignoring unused padding bits in
68/// the final byte.
69pub fn is_zero(bit_vector: &BitVector) -> bool {
70    debug_assert!(crate::misc::validation::validate_data_len(bit_vector, "bit vector").is_ok());
71    let full_bytes = (bit_vector.size / 8) as usize;
72    if bit_vector.data[..full_bytes].iter().any(|&byte| byte != 0) {
73        return false;
74    }
75    let remainder = bit_vector.size % 8;
76    remainder == 0 || bit_vector.data[full_bytes] >> (8 - remainder) == 0
77}
78
79pub fn extend_num_bits(bit_vector: &mut BitVector, extending_length: u64) {
80    bit_vector.size += extending_length;
81    let new_data_len = bit_vector_len(bit_vector.size);
82    bit_vector.data.resize(new_data_len, 0u8);
83}
84
85pub fn get_bit(bit_vector: &BitVector, index: u64) -> bool {
86    debug_assert!(index < bit_vector.size);
87    let (byte_index, bit_index) = byte_bit_index(index);
88    (bit_vector.data[byte_index] & (1 << bit_index)) != 0
89}
90
91pub fn set_bit(bit_vector: &mut BitVector, index: u64, value: bool) {
92    debug_assert!(index < bit_vector.size);
93    let (byte_index, bit_index) = byte_bit_index(index);
94    if value {
95        bit_vector.data[byte_index] |= 1 << bit_index;
96    } else {
97        bit_vector.data[byte_index] &= !(1 << bit_index);
98    }
99}
100
101pub fn flip_bit(bit_vector: &mut BitVector, index: u64) {
102    debug_assert!(index < bit_vector.size);
103    let (byte_index, bit_index) = byte_bit_index(index);
104    bit_vector.data[byte_index] ^= 1 << bit_index;
105}
106
107pub fn bit_vector_to_string(bit_vector: &BitVector) -> String {
108    let mut s = String::with_capacity(bit_vector.size as usize);
109    for i in 0..bit_vector.size {
110        if get_bit(bit_vector, i) {
111            s.push('1');
112        } else {
113            s.push('0');
114        }
115    }
116    s
117}
118
119pub fn binar_bitvec_to_bit_vector(bit_vec: &binar::BitVec, length: usize) -> BitVector {
120    let mut data = vec![0u8; bit_vector_len(length as u64)];
121    for (index, value) in (0..length).zip(bit_vec.iter()) {
122        let (byte_index, bit_index) = byte_bit_index(index as u64);
123        data[byte_index] |= (value as u8) << bit_index;
124    }
125    BitVector {
126        size: length as u64,
127        data,
128    }
129}
130
131/// Extract a contiguous slice of bits from a BitVector
132pub fn slice(bit_vector: &BitVector, start: usize, length: usize) -> BitVector {
133    debug_assert!(start + length <= bit_vector.size as usize);
134    let mut result = BitVector {
135        size: length as u64,
136        data: vec![0u8; bit_vector_len(length as u64)],
137    };
138    for i in 0..length {
139        if get_bit(bit_vector, (start + i) as u64) {
140            set_bit(&mut result, i as u64, true);
141        }
142    }
143    result
144}
145
146/// Append bits from another BitVector to the end of this one
147pub fn append(bit_vector: &mut BitVector, other: &BitVector) {
148    let original_size = bit_vector.size;
149    extend_num_bits(bit_vector, other.size);
150    for i in 0..other.size {
151        if get_bit(other, i) {
152            set_bit(bit_vector, original_size + i, true);
153        }
154    }
155}
156
157#[cfg(test)]
158mod tests {
159    use super::*;
160
161    fn bits(string: &str) -> Vec<bool> {
162        string
163            .chars()
164            .map(|c| match c {
165                '0' => false,
166                '1' => true,
167                _ => panic!("invalid character in bit string"),
168            })
169            .collect()
170    }
171
172    #[test]
173    fn bit_pack() {
174        // cargo test bit_pack -- --nocapture
175
176        // np.packbits([1,0,0,0,0,0,0,0]) = array([128], dtype=uint8)
177        assert!(pack_bits(&bits("10000000")) == vec![128u8]);
178        // np.packbits([1,0,0,0,0,0,0,0,0,1]) = array([128,  64], dtype=uint8)
179        assert!(pack_bits(&bits("1000000001")) == vec![128u8, 64u8]);
180        // np.packbits([0,0,0,1,0,1,0,0,1,1]) = array([ 20, 192], dtype=uint8)
181        assert!(pack_bits(&bits("0001010011")) == vec![20u8, 192u8]);
182
183        assert!(unpack_bits(&[128u8], 8) == bits("10000000"));
184        assert!(unpack_bits(&[128u8, 64u8], 10) == bits("1000000001"));
185        assert!(unpack_bits(&[20u8, 192u8], 10) == bits("0001010011"));
186    }
187
188    #[test]
189    fn zero_check_ignores_padding_bits() {
190        assert!(is_zero(&BitVector { size: 0, data: vec![] }));
191        assert!(is_zero(&BitVector {
192            size: 1,
193            data: vec![0b0111_1111]
194        }));
195        assert!(!is_zero(&BitVector {
196            size: 1,
197            data: vec![0b1000_0000]
198        }));
199        assert!(is_zero(&BitVector {
200            size: 9,
201            data: vec![0, 0b0111_1111],
202        }));
203        assert!(!is_zero(&BitVector {
204            size: 9,
205            data: vec![0, 0b1000_0000],
206        }));
207    }
208}