16992591828

Committed 15 Aug 2025 02:51PM UTC coverage: 87.203% (-0.5%) from 87.72%

Build # 16992591828

Build Type

Pull #2456

github

Committed by

web-flow

Commit Message

Merge fe7e226a7 into 4a23f65b3

Pull Request Pull Request #2456: feat: basic BoolBuffer / BoolBufferMut

Run Details

476 of 1230 new or added lines in 107 files covered. (38.7%)

74 existing lines in 19 files now uncovered.

56525 of 64820 relevant lines covered (87.2%)

623751.88 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

0.0

/vortex-buffer/src/bit/unaligned.rs

1	// SPDX-License-Identifier: Apache-2.0
2	// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4	use vortex_error::VortexExpect;
5
6	use crate::trusted_len::TrustedLen;
7	use crate::{Buffer, BufferIterator, ByteBuffer, get_bit_unchecked};
8
9	#[inline]
NEW 10	fn read_u64(input: &[u8]) -> u64 {	×
NEW 11	let len = input.len().min(8);	×
NEW 12	let mut buf = [0u8; 8];	×
NEW 13	buf[..len].copy_from_slice(input);	×
NEW 14	u64::from_le_bytes(buf)	×
NEW 15	}	×
16
17	#[inline]
NEW 18	fn compute_prefix_mask(lead_padding: usize) -> u64 {	×
NEW 19	!((1 << lead_padding) - 1)	×
NEW 20	}	×
21
22	#[inline]
NEW 23	fn compute_suffix_mask(len: usize, lead_padding: usize) -> (u64, usize) {	×
NEW 24	let trailing_bits = (len + lead_padding) % 64;	×
25
NEW 26	if trailing_bits == 0 {	×
NEW 27	return (u64::MAX, 0);	×
NEW 28	}	×
29
NEW 30	let trailing_padding = 64 - trailing_bits;	×
NEW 31	let suffix_mask = (1 << trailing_bits) - 1;	×
NEW 32	(suffix_mask, trailing_padding)	×
NEW 33	}	×
34
35	pub struct UnalignedBitChunks {
36	lead_padding: usize,
37	trailing_padding: usize,
38	prefix: Option<u64>,
39	chunks: Buffer<u64>,
40	suffix: Option<u64>,
41	}
42
43	impl UnalignedBitChunks {
NEW 44	pub fn new(buffer: ByteBuffer, offset: usize, len: usize) -> Self {	×
NEW 45	if len == 0 {	×
NEW 46	return Self {	×
NEW 47	lead_padding: 0,	×
NEW 48	trailing_padding: 0,	×
NEW 49	prefix: None,	×
NEW 50	chunks: Buffer::empty(),	×
NEW 51	suffix: None,	×
NEW 52	};	×
NEW 53	}	×
NEW 54	let byte_offset = offset / 8;	×
NEW 55	let offset_padding = offset % 8;	×
NEW 56	let bytes_len = (len + offset_padding).div_ceil(8);	×
57
NEW 58	let buffer = buffer.slice(byte_offset..byte_offset + bytes_len);	×
59
NEW 60	let prefix_mask = compute_prefix_mask(offset_padding);	×
61
62	// If less than 8 bytes, read into prefix
NEW 63	if buffer.len() <= 8 {	×
NEW 64	let (suffix_mask, trailing_padding) = compute_suffix_mask(len, offset_padding);	×
NEW 65	let prefix = read_u64(&buffer) & suffix_mask & prefix_mask;	×
66
NEW 67	return Self {	×
NEW 68	lead_padding: offset_padding,	×
NEW 69	trailing_padding,	×
NEW 70	prefix: Some(prefix),	×
NEW 71	chunks: Buffer::empty(),	×
NEW 72	suffix: None,	×
NEW 73	};	×
NEW 74	}	×
75
76	// If less than 16 bytes, read into prefix and suffix
NEW 77	if buffer.len() <= 16 {	×
NEW 78	let (suffix_mask, trailing_padding) = compute_suffix_mask(len, offset_padding);	×
NEW 79	let prefix = read_u64(&buffer[..8]) & prefix_mask;	×
NEW 80	let suffix = read_u64(&buffer[8..]) & suffix_mask;	×
81
NEW 82	return Self {	×
NEW 83	lead_padding: offset_padding,	×
NEW 84	trailing_padding,	×
NEW 85	prefix: Some(prefix),	×
NEW 86	chunks: Buffer::empty(),	×
NEW 87	suffix: Some(suffix),	×
NEW 88	};	×
NEW 89	}	×
90
NEW 91	let (prefix, mut chunks, suffix) = buffer.align_to::<u64>();	×
NEW 92	assert!(	×
NEW 93	prefix.len() < 8 && suffix.len() < 8,	×
NEW 94	"align_to did not return largest possible aligned slice"	×
95	);
NEW 96	let (alignment_padding, prefix) = match (offset_padding, prefix.is_empty()) {	×
NEW 97	(0, true) => (0, None),	×
98	(_, true) => {
NEW 99	let prefix = chunks[0] & prefix_mask;	×
NEW 100	chunks = chunks.slice(1..);	×
NEW 101	(0, Some(prefix))	×
102	}
103	(_, false) => {
NEW 104	let alignment_padding = (8 - prefix.len()) * 8;	×
105
NEW 106	let prefix = (read_u64(&prefix) & prefix_mask) << alignment_padding;	×
NEW 107	(alignment_padding, Some(prefix))	×
108	}
109	};
110
NEW 111	let lead_padding = offset_padding + alignment_padding;	×
NEW 112	let (suffix_mask, trailing_padding) = compute_suffix_mask(len, lead_padding);	×
113
NEW 114	let suffix = match (trailing_padding, suffix.is_empty()) {	×
NEW 115	(0, _) => None,	×
116	(_, true) => {
NEW 117	let suffix = chunks[chunks.len() - 1] & suffix_mask;	×
NEW 118	chunks = chunks.slice(..chunks.len() - 1);	×
NEW 119	Some(suffix)	×
120	}
NEW 121	(_, false) => Some(read_u64(&suffix) & suffix_mask),	×
122	};
123
NEW 124	Self {	×
NEW 125	lead_padding,	×
NEW 126	trailing_padding,	×
NEW 127	prefix,	×
NEW 128	chunks,	×
NEW 129	suffix,	×
NEW 130	}	×
NEW 131	}	×
132
NEW 133	pub fn iter(&self) -> UnalignedBitChunkIterator {	×
NEW 134	self.prefix	×
NEW 135	.into_iter()	×
NEW 136	.chain(self.chunks.clone())	×
NEW 137	.chain(self.suffix)	×
NEW 138	}	×
139
NEW 140	pub fn prefix_padding(&self) -> usize {	×
NEW 141	self.lead_padding	×
NEW 142	}	×
143
NEW 144	pub fn prefix(&self) -> Option<u64> {	×
NEW 145	self.prefix	×
NEW 146	}	×
147
NEW 148	pub fn suffix_padding(&self) -> usize {	×
NEW 149	self.trailing_padding	×
NEW 150	}	×
151
NEW 152	pub fn suffix(&self) -> Option<u64> {	×
NEW 153	self.suffix	×
NEW 154	}	×
155
NEW 156	pub fn count_ones(&self) -> usize {	×
NEW 157	self.iter().map(\|x\| x.count_ones() as usize).sum()	×
NEW 158	}	×
159	}
160
161	pub type UnalignedBitChunkIterator = core::iter::Chain<
162	core::iter::Chain<core::option::IntoIter<u64>, BufferIterator<u64>>,
163	core::option::IntoIter<u64>,
164	>;
165
166	/// Iterator over bits in the byte buffer
167	pub struct BitIterator {
168	buffer: ByteBuffer,
169	current_offset: usize,
170	end_offset: usize,
171	}
172
173	impl BitIterator {
NEW 174	pub fn new(buffer: ByteBuffer, offset: usize, len: usize) -> Self {	×
NEW 175	let end_offset = offset + len;	×
NEW 176	assert!(	×
NEW 177	buffer.len() >= end_offset.div_ceil(8),	×
NEW 178	"Buffer {} too small for requested offset and len {}",	×
NEW 179	buffer.len(),	×
NEW 180	end_offset.div_ceil(8)	×
181	);
182
NEW 183	Self {	×
NEW 184	buffer,	×
NEW 185	current_offset: offset,	×
NEW 186	end_offset,	×
NEW 187	}	×
NEW 188	}	×
189	}
190
191	impl Iterator for BitIterator {
192	type Item = bool;
193
NEW 194	fn next(&mut self) -> Option<Self::Item> {	×
NEW 195	if self.current_offset == self.end_offset {	×
NEW 196	return None;	×
NEW 197	}	×
198	// SAFETY: current_offset is in bounds
NEW 199	let v = unsafe { get_bit_unchecked(&self.buffer, self.current_offset) };	×
NEW 200	self.current_offset += 1;	×
NEW 201	Some(v)	×
NEW 202	}	×
203
NEW 204	fn size_hint(&self) -> (usize, Option<usize>) {	×
NEW 205	let remaining_bits = self.end_offset - self.current_offset;	×
NEW 206	(remaining_bits, Some(remaining_bits))	×
NEW 207	}	×
208	}
209
210	unsafe impl TrustedLen for BitIterator {}
211
212	impl ExactSizeIterator for BitIterator {}
213
214	impl DoubleEndedIterator for BitIterator {
NEW 215	fn next_back(&mut self) -> Option<Self::Item> {	×
NEW 216	if self.current_offset == self.end_offset {	×
NEW 217	return None;	×
NEW 218	}	×
NEW 219	self.end_offset -= 1;	×
220	// Safety: end_offset is in bounds
NEW 221	Some(unsafe { get_bit_unchecked(&self.buffer, self.end_offset) })	×
NEW 222	}	×
223	}
224
225	pub struct BitIndexIterator {
226	current_chunk: u64,
227	chunk_offset: i64,
228	iter: UnalignedBitChunkIterator,
229	}
230
231	impl BitIndexIterator {
NEW 232	pub fn new(buffer: ByteBuffer, offset: usize, len: usize) -> Self {	×
NEW 233	let chunks = UnalignedBitChunks::new(buffer, offset, len);	×
NEW 234	let mut iter = chunks.iter();	×
NEW 235	let current_chunk = iter.next().unwrap_or(0);	×
NEW 236	let chunk_offset = -(chunks.prefix_padding() as i64);	×
237
NEW 238	Self {	×
NEW 239	current_chunk,	×
NEW 240	chunk_offset,	×
NEW 241	iter,	×
NEW 242	}	×
NEW 243	}	×
244	}
245
246	impl Iterator for BitIndexIterator {
247	type Item = usize;
248
NEW 249	fn next(&mut self) -> Option<Self::Item> {	×
250	loop {
NEW 251	if self.current_chunk != 0 {	×
NEW 252	let bit_pos = self.current_chunk.trailing_zeros();	×
NEW 253	self.current_chunk ^= 1 << bit_pos;	×
NEW 254	return Some(	×
NEW 255	usize::try_from(self.chunk_offset + bit_pos as i64)	×
NEW 256	.vortex_expect("bit index must be a usize"),	×
NEW 257	);	×
NEW 258	}	×
259
NEW 260	self.current_chunk = self.iter.next()?;	×
NEW 261	self.chunk_offset += 64;	×
262	}
NEW 263	}	×
264	}
265
266	pub struct BitSliceIterator {
267	iter: UnalignedBitChunkIterator,
268	len: usize,
269	current_offset: i64,
270	current_chunk: u64,
271	}
272
273	impl BitSliceIterator {
NEW 274	pub fn new(buffer: ByteBuffer, offset: usize, len: usize) -> Self {	×
NEW 275	let chunks = UnalignedBitChunks::new(buffer, offset, len);	×
NEW 276	let mut iter = chunks.iter();	×
NEW 277	let current_chunk = iter.next().unwrap_or(0);	×
NEW 278	let current_offset = -(chunks.prefix_padding() as i64);	×
279
NEW 280	Self {	×
NEW 281	iter,	×
NEW 282	len,	×
NEW 283	current_offset,	×
NEW 284	current_chunk,	×
NEW 285	}	×
NEW 286	}	×
287
288	/// Returns `Some((chunk_offset, bit_offset))` for the next chunk that has at
289	/// least one bit set, or None if there is no such chunk.
290	///
291	/// Where `chunk_offset` is the bit offset to the current `u64` chunk
292	/// and `bit_offset` is the offset of the first `1` bit in that chunk
NEW 293	fn advance_to_set_bit(&mut self) -> Option<(i64, u32)> {	×
294	loop {
NEW 295	if self.current_chunk != 0 {	×
296	// Find the index of the first 1
NEW 297	let bit_pos = self.current_chunk.trailing_zeros();	×
NEW 298	return Some((self.current_offset, bit_pos));	×
NEW 299	}	×
300
NEW 301	self.current_chunk = self.iter.next()?;	×
NEW 302	self.current_offset += 64;	×
303	}
NEW 304	}	×
305	}
306
307	impl Iterator for BitSliceIterator {
308	type Item = (usize, usize);
309
NEW 310	fn next(&mut self) -> Option<Self::Item> {	×
NEW 311	if self.len == 0 {	×
NEW 312	return None;	×
NEW 313	}	×
314
NEW 315	let (start_chunk, start_bit) = self.advance_to_set_bit()?;	×
316
317	// Set bits up to start
NEW 318	self.current_chunk \|= (1 << start_bit) - 1;	×
319
320	loop {
NEW 321	if self.current_chunk != u64::MAX {	×
322	// Find the index of the first 0
NEW 323	let end_bit = self.current_chunk.trailing_ones();	×
324
325	// Zero out up to end_bit
NEW 326	self.current_chunk &= !((1 << end_bit) - 1);	×
327
NEW 328	return Some((	×
NEW 329	usize::try_from(start_chunk + start_bit as i64)	×
NEW 330	.vortex_expect("bit offset must be a usize"),	×
NEW 331	usize::try_from(self.current_offset + end_bit as i64)	×
NEW 332	.vortex_expect("bit offset must be a usize"),	×
NEW 333	));	×
NEW 334	}	×
335
NEW 336	match self.iter.next() {	×
NEW 337	Some(next) => {	×
NEW 338	self.current_chunk = next;	×
NEW 339	self.current_offset += 64;	×
NEW 340	}	×
341	None => {
NEW 342	return Some((	×
NEW 343	usize::try_from(start_chunk + start_bit as i64)	×
NEW 344	.vortex_expect("bit offset must be a usize"),	×
NEW 345	std::mem::take(&mut self.len),	×
NEW 346	));	×
347	}
348	}
349	}
NEW 350	}	×
351	}

vortex-data / vortex / 16992591828

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous