deq_runtime/misc/
bit_vector.rs1use 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 }
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
67pub 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
131pub 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
146pub 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 assert!(pack_bits(&bits("10000000")) == vec![128u8]);
178 assert!(pack_bits(&bits("1000000001")) == vec![128u8, 64u8]);
180 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}