16992684502

Committed 15 Aug 2025 02:56PM UTC coverage: 87.875% (+0.2%) from 87.72%

Build # 16992684502

Build Type

Pull #2456

github

Committed by

web-flow

Commit Message

Merge 2d540e578 into 4a23f65b3

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

Run Details

1275 of 1428 new or added lines in 110 files covered. (89.29%)

334 existing lines in 31 files now uncovered.

57169 of 65057 relevant lines covered (87.88%)

658056.52 hits per line

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

87.44

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

// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright the Vortex contributors

use vortex_error::VortexExpect;

use crate::trusted_len::TrustedLen;
use crate::{Buffer, BufferIterator, ByteBuffer, get_bit_unchecked};

#[inline]
fn read_u64(input: &[u8]) -> u64 {
    let len = input.len().min(8);
    let mut buf = [0u8; 8];
    buf[..len].copy_from_slice(input);
    u64::from_le_bytes(buf)
}

#[inline]
fn compute_prefix_mask(lead_padding: usize) -> u64 {
    !((1 << lead_padding) - 1)
}

#[inline]
fn compute_suffix_mask(len: usize, lead_padding: usize) -> (u64, usize) {
    let trailing_bits = (len + lead_padding) % 64;

    if trailing_bits == 0 {
        return (u64::MAX, 0);
    }

    let trailing_padding = 64 - trailing_bits;
    let suffix_mask = (1 << trailing_bits) - 1;
    (suffix_mask, trailing_padding)
}

pub struct UnalignedBitChunks {
    lead_padding: usize,
    trailing_padding: usize,
    prefix: Option<u64>,
    chunks: Buffer<u64>,
    suffix: Option<u64>,
}

impl UnalignedBitChunks {
    pub fn new(buffer: ByteBuffer, offset: usize, len: usize) -> Self {
        if len == 0 {
            return Self {
                lead_padding: 0,
                trailing_padding: 0,
                prefix: None,
                chunks: Buffer::empty(),
                suffix: None,
            };
        }
        let byte_offset = offset / 8;
        let offset_padding = offset % 8;
        let bytes_len = (len + offset_padding).div_ceil(8);

        let buffer = buffer.slice(byte_offset..byte_offset + bytes_len);

        let prefix_mask = compute_prefix_mask(offset_padding);

        // If less than 8 bytes, read into prefix
        if buffer.len() <= 8 {
            let (suffix_mask, trailing_padding) = compute_suffix_mask(len, offset_padding);
            let prefix = read_u64(&buffer) & suffix_mask & prefix_mask;

            return Self {
                lead_padding: offset_padding,
                trailing_padding,
                prefix: Some(prefix),
                chunks: Buffer::empty(),
                suffix: None,
            };
        }

        // If less than 16 bytes, read into prefix and suffix
        if buffer.len() <= 16 {
            let (suffix_mask, trailing_padding) = compute_suffix_mask(len, offset_padding);
            let prefix = read_u64(&buffer[..8]) & prefix_mask;
            let suffix = read_u64(&buffer[8..]) & suffix_mask;

            return Self {
                lead_padding: offset_padding,
                trailing_padding,
                prefix: Some(prefix),
                chunks: Buffer::empty(),
                suffix: Some(suffix),
            };
        }

        let (prefix, mut chunks, suffix) = buffer.align_to::<u64>();
        assert!(
            prefix.len() < 8 && suffix.len() < 8,
            "align_to did not return largest possible aligned slice"
        );
        let (alignment_padding, prefix) = match (offset_padding, prefix.is_empty()) {
            (0, true) => (0, None),
            (_, true) => {
                let prefix = chunks[0] & prefix_mask;
                chunks = chunks.slice(1..);
                (0, Some(prefix))
            }
            (_, false) => {
                let alignment_padding = (8 - prefix.len()) * 8;

                let prefix = (read_u64(&prefix) & prefix_mask) << alignment_padding;
                (alignment_padding, Some(prefix))
            }
        };

        let lead_padding = offset_padding + alignment_padding;
        let (suffix_mask, trailing_padding) = compute_suffix_mask(len, lead_padding);

        let suffix = match (trailing_padding, suffix.is_empty()) {
            (0, _) => None,
            (_, true) => {
                let suffix = chunks[chunks.len() - 1] & suffix_mask;
                chunks = chunks.slice(..chunks.len() - 1);
                Some(suffix)
            }
            (_, false) => Some(read_u64(&suffix) & suffix_mask),
        };

        Self {
            lead_padding,
            trailing_padding,
            prefix,
            chunks,
            suffix,
        }
    }

    pub fn iter(&self) -> UnalignedBitChunkIterator {
        self.prefix
            .into_iter()
            .chain(self.chunks.clone())
            .chain(self.suffix)
    }

    pub fn prefix_padding(&self) -> usize {
        self.lead_padding
    }

    pub fn prefix(&self) -> Option<u64> {
        self.prefix
    }

    pub fn suffix_padding(&self) -> usize {
        self.trailing_padding
    }

    pub fn suffix(&self) -> Option<u64> {
        self.suffix
    }

    pub fn count_ones(&self) -> usize {
        self.iter().map(|x| x.count_ones() as usize).sum()
    }
}

pub type UnalignedBitChunkIterator = core::iter::Chain<
    core::iter::Chain<core::option::IntoIter<u64>, BufferIterator<u64>>,
    core::option::IntoIter<u64>,
>;

/// Iterator over bits in the byte buffer
pub struct BitIterator {
    buffer: ByteBuffer,
    current_offset: usize,
    end_offset: usize,
}

impl BitIterator {
    pub fn new(buffer: ByteBuffer, offset: usize, len: usize) -> Self {
        let end_offset = offset + len;
        assert!(
            buffer.len() >= end_offset.div_ceil(8),
            "Buffer {} too small for requested offset and len {}",
            buffer.len(),
            end_offset.div_ceil(8)
        );

        Self {
            buffer,
            current_offset: offset,
            end_offset,
        }
    }
}

impl Iterator for BitIterator {
    type Item = bool;

    fn next(&mut self) -> Option<Self::Item> {
        if self.current_offset == self.end_offset {
            return None;
        }
        // SAFETY: current_offset is in bounds
        let v = unsafe { get_bit_unchecked(&self.buffer, self.current_offset) };
        self.current_offset += 1;
        Some(v)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let remaining_bits = self.end_offset - self.current_offset;
        (remaining_bits, Some(remaining_bits))
    }
}

unsafe impl TrustedLen for BitIterator {}

impl ExactSizeIterator for BitIterator {}

impl DoubleEndedIterator for BitIterator {
    fn next_back(&mut self) -> Option<Self::Item> {
        if self.current_offset == self.end_offset {
            return None;
        }
        self.end_offset -= 1;
        // Safety: end_offset is in bounds
        Some(unsafe { get_bit_unchecked(&self.buffer, self.end_offset) })
    }
}

pub struct BitIndexIterator {
    current_chunk: u64,
    chunk_offset: i64,
    iter: UnalignedBitChunkIterator,
}

impl BitIndexIterator {
    pub fn new(buffer: ByteBuffer, offset: usize, len: usize) -> Self {
        let chunks = UnalignedBitChunks::new(buffer, offset, len);
        let mut iter = chunks.iter();
        let current_chunk = iter.next().unwrap_or(0);
        let chunk_offset = -(chunks.prefix_padding() as i64);

        Self {
            current_chunk,
            chunk_offset,
            iter,
        }
    }
}

impl Iterator for BitIndexIterator {
    type Item = usize;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            if self.current_chunk != 0 {
                let bit_pos = self.current_chunk.trailing_zeros();
                self.current_chunk ^= 1 << bit_pos;
                return Some(
                    usize::try_from(self.chunk_offset + bit_pos as i64)
                        .vortex_expect("bit index must be a usize"),
                );
            }

            self.current_chunk = self.iter.next()?;
            self.chunk_offset += 64;
        }
    }
}

pub struct BitSliceIterator {
    iter: UnalignedBitChunkIterator,
    len: usize,
    current_offset: i64,
    current_chunk: u64,
}

impl BitSliceIterator {
    pub fn new(buffer: ByteBuffer, offset: usize, len: usize) -> Self {
        let chunks = UnalignedBitChunks::new(buffer, offset, len);
        let mut iter = chunks.iter();
        let current_chunk = iter.next().unwrap_or(0);
        let current_offset = -(chunks.prefix_padding() as i64);

        Self {
            iter,
            len,
            current_offset,
            current_chunk,
        }
    }

    /// Returns `Some((chunk_offset, bit_offset))` for the next chunk that has at
    /// least one bit set, or None if there is no such chunk.
    ///
    /// Where `chunk_offset` is the bit offset to the current `u64` chunk
    /// and `bit_offset` is the offset of the first `1` bit in that chunk
    fn advance_to_set_bit(&mut self) -> Option<(i64, u32)> {
        loop {
            if self.current_chunk != 0 {
                // Find the index of the first 1
                let bit_pos = self.current_chunk.trailing_zeros();
                return Some((self.current_offset, bit_pos));
            }

            self.current_chunk = self.iter.next()?;
            self.current_offset += 64;
        }
    }
}

impl Iterator for BitSliceIterator {
    type Item = (usize, usize);

    fn next(&mut self) -> Option<Self::Item> {
        if self.len == 0 {
            return None;
        }

        let (start_chunk, start_bit) = self.advance_to_set_bit()?;

        // Set bits up to start
        self.current_chunk |= (1 << start_bit) - 1;

        loop {
            if self.current_chunk != u64::MAX {
                // Find the index of the first 0
                let end_bit = self.current_chunk.trailing_ones();

                // Zero out up to end_bit
                self.current_chunk &= !((1 << end_bit) - 1);

                return Some((
                    usize::try_from(start_chunk + start_bit as i64)
                        .vortex_expect("bit offset must be a usize"),
                    usize::try_from(self.current_offset + end_bit as i64)
                        .vortex_expect("bit offset must be a usize"),
                ));
            }

            match self.iter.next() {
                Some(next) => {
                    self.current_chunk = next;
                    self.current_offset += 64;
                }
                None => {
                    return Some((
                        usize::try_from(start_chunk + start_bit as i64)
                            .vortex_expect("bit offset must be a usize"),
                        std::mem::take(&mut self.len),
                    ));
                }
            }
        }
    }
}

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]
10	fn read_u64(input: &[u8]) -> u64 {	632,564✔
11	let len = input.len().min(8);	632,564✔
12	let mut buf = [0u8; 8];	632,564✔
13	buf[..len].copy_from_slice(input);	632,564✔
14	u64::from_le_bytes(buf)	632,564✔
15	}	632,564✔
16
17	#[inline]
18	fn compute_prefix_mask(lead_padding: usize) -> u64 {	634,724✔
19	!((1 << lead_padding) - 1)	634,724✔
20	}	634,724✔
21
22	#[inline]
23	fn compute_suffix_mask(len: usize, lead_padding: usize) -> (u64, usize) {	634,724✔
24	let trailing_bits = (len + lead_padding) % 64;	634,724✔
25
26	if trailing_bits == 0 {	634,724✔
27	return (u64::MAX, 0);	22,454✔
28	}	612,270✔
29
30	let trailing_padding = 64 - trailing_bits;	612,270✔
31	let suffix_mask = (1 << trailing_bits) - 1;	612,270✔
32	(suffix_mask, trailing_padding)	612,270✔
33	}	634,724✔
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 {
44	pub fn new(buffer: ByteBuffer, offset: usize, len: usize) -> Self {	634,982✔
45	if len == 0 {	634,982✔
46	return Self {	258✔
47	lead_padding: 0,	258✔
48	trailing_padding: 0,	258✔
49	prefix: None,	258✔
50	chunks: Buffer::empty(),	258✔
51	suffix: None,	258✔
52	};	258✔
53	}	634,724✔
54	let byte_offset = offset / 8;	634,724✔
55	let offset_padding = offset % 8;	634,724✔
56	let bytes_len = (len + offset_padding).div_ceil(8);	634,724✔
57
58	let buffer = buffer.slice(byte_offset..byte_offset + bytes_len);	634,724✔
59
60	let prefix_mask = compute_prefix_mask(offset_padding);	634,724✔
61
62	// If less than 8 bytes, read into prefix
63	if buffer.len() <= 8 {	634,724✔
64	let (suffix_mask, trailing_padding) = compute_suffix_mask(len, offset_padding);	540,388✔
65	let prefix = read_u64(&buffer) & suffix_mask & prefix_mask;	540,388✔
66
67	return Self {	540,388✔
68	lead_padding: offset_padding,	540,388✔
69	trailing_padding,	540,388✔
70	prefix: Some(prefix),	540,388✔
71	chunks: Buffer::empty(),	540,388✔
72	suffix: None,	540,388✔
73	};	540,388✔
74	}	94,336✔
75
76	// If less than 16 bytes, read into prefix and suffix
77	if buffer.len() <= 16 {	94,336✔
78	let (suffix_mask, trailing_padding) = compute_suffix_mask(len, offset_padding);	21,896✔
79	let prefix = read_u64(&buffer[..8]) & prefix_mask;	21,896✔
80	let suffix = read_u64(&buffer[8..]) & suffix_mask;	21,896✔
81
82	return Self {	21,896✔
83	lead_padding: offset_padding,	21,896✔
84	trailing_padding,	21,896✔
85	prefix: Some(prefix),	21,896✔
86	chunks: Buffer::empty(),	21,896✔
87	suffix: Some(suffix),	21,896✔
88	};	21,896✔
89	}	72,440✔
90
91	let (prefix, mut chunks, suffix) = buffer.align_to::<u64>();	72,440✔
92	assert!(	72,440✔
93	prefix.len() < 8 && suffix.len() < 8,	72,440✔
NEW 94	"align_to did not return largest possible aligned slice"	×
95	);
96	let (alignment_padding, prefix) = match (offset_padding, prefix.is_empty()) {	72,440✔
97	(0, true) => (0, None),	72,440✔
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
111	let lead_padding = offset_padding + alignment_padding;	72,440✔
112	let (suffix_mask, trailing_padding) = compute_suffix_mask(len, lead_padding);	72,440✔
113
114	let suffix = match (trailing_padding, suffix.is_empty()) {	72,440✔
115	(0, _) => None,	22,058✔
116	(_, true) => {
117	let suffix = chunks[chunks.len() - 1] & suffix_mask;	1,998✔
118	chunks = chunks.slice(..chunks.len() - 1);	1,998✔
119	Some(suffix)	1,998✔
120	}
121	(_, false) => Some(read_u64(&suffix) & suffix_mask),	48,384✔
122	};
123
124	Self {	72,440✔
125	lead_padding,	72,440✔
126	trailing_padding,	72,440✔
127	prefix,	72,440✔
128	chunks,	72,440✔
129	suffix,	72,440✔
130	}	72,440✔
131	}	634,982✔
132
133	pub fn iter(&self) -> UnalignedBitChunkIterator {	634,982✔
134	self.prefix	634,982✔
135	.into_iter()	634,982✔
136	.chain(self.chunks.clone())	634,982✔
137	.chain(self.suffix)	634,982✔
138	}	634,982✔
139
140	pub fn prefix_padding(&self) -> usize {	78,418✔
141	self.lead_padding	78,418✔
142	}	78,418✔
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
156	pub fn count_ones(&self) -> usize {	556,564✔
157	self.iter().map(\|x\| x.count_ones() as usize).sum()	14,217,892✔
158	}	556,564✔
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 {
174	pub fn new(buffer: ByteBuffer, offset: usize, len: usize) -> Self {	59,632✔
175	let end_offset = offset + len;	59,632✔
176	assert!(	59,632✔
177	buffer.len() >= end_offset.div_ceil(8),	59,632✔
NEW 178	"Buffer {} too small for requested offset and len {}",	×
NEW 179	buffer.len(),	×
NEW 180	end_offset.div_ceil(8)	×
181	);
182
183	Self {	59,632✔
184	buffer,	59,632✔
185	current_offset: offset,	59,632✔
186	end_offset,	59,632✔
187	}	59,632✔
188	}	59,632✔
189	}
190
191	impl Iterator for BitIterator {
192	type Item = bool;
193
194	fn next(&mut self) -> Option<Self::Item> {	6,367,198✔
195	if self.current_offset == self.end_offset {	6,367,198✔
196	return None;	42,389✔
197	}	6,324,809✔
198	// SAFETY: current_offset is in bounds
199	let v = unsafe { get_bit_unchecked(&self.buffer, self.current_offset) };	6,324,809✔
200	self.current_offset += 1;	6,324,809✔
201	Some(v)	6,324,809✔
202	}	6,367,198✔
203
204	fn size_hint(&self) -> (usize, Option<usize>) {	30,712✔
205	let remaining_bits = self.end_offset - self.current_offset;	30,712✔
206	(remaining_bits, Some(remaining_bits))	30,712✔
207	}	30,712✔
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 {
232	pub fn new(buffer: ByteBuffer, offset: usize, len: usize) -> Self {	69,648✔
233	let chunks = UnalignedBitChunks::new(buffer, offset, len);	69,648✔
234	let mut iter = chunks.iter();	69,648✔
235	let current_chunk = iter.next().unwrap_or(0);	69,648✔
236	let chunk_offset = -(chunks.prefix_padding() as i64);	69,648✔
237
238	Self {	69,648✔
239	current_chunk,	69,648✔
240	chunk_offset,	69,648✔
241	iter,	69,648✔
242	}	69,648✔
243	}	69,648✔
244	}
245
246	impl Iterator for BitIndexIterator {
247	type Item = usize;
248
249	fn next(&mut self) -> Option<Self::Item> {	38,070,736✔
250	loop {
251	if self.current_chunk != 0 {	41,639,163✔
252	let bit_pos = self.current_chunk.trailing_zeros();	38,004,137✔
253	self.current_chunk ^= 1 << bit_pos;	38,004,137✔
254	return Some(	38,004,137✔
255	usize::try_from(self.chunk_offset + bit_pos as i64)	38,004,137✔
256	.vortex_expect("bit index must be a usize"),	38,004,137✔
257	);	38,004,137✔
258	}	3,635,026✔
259
260	self.current_chunk = self.iter.next()?;	3,635,026✔
261	self.chunk_offset += 64;	3,568,427✔
262	}
263	}	38,070,736✔
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 {
274	pub fn new(buffer: ByteBuffer, offset: usize, len: usize) -> Self {	8,770✔
275	let chunks = UnalignedBitChunks::new(buffer, offset, len);	8,770✔
276	let mut iter = chunks.iter();	8,770✔
277	let current_chunk = iter.next().unwrap_or(0);	8,770✔
278	let current_offset = -(chunks.prefix_padding() as i64);	8,770✔
279
280	Self {	8,770✔
281	iter,	8,770✔
282	len,	8,770✔
283	current_offset,	8,770✔
284	current_chunk,	8,770✔
285	}	8,770✔
286	}	8,770✔
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
293	fn advance_to_set_bit(&mut self) -> Option<(i64, u32)> {	505,733✔
294	loop {
295	if self.current_chunk != 0 {	515,411✔
296	// Find the index of the first 1
297	let bit_pos = self.current_chunk.trailing_zeros();	500,067✔
298	return Some((self.current_offset, bit_pos));	500,067✔
299	}	15,344✔
300
301	self.current_chunk = self.iter.next()?;	15,344✔
302	self.current_offset += 64;	9,678✔
303	}
304	}	505,733✔
305	}
306
307	impl Iterator for BitSliceIterator {
308	type Item = (usize, usize);
309
310	fn next(&mut self) -> Option<Self::Item> {	506,471✔
311	if self.len == 0 {	506,471✔
312	return None;	738✔
313	}	505,733✔
314
315	let (start_chunk, start_bit) = self.advance_to_set_bit()?;	505,733✔
316
317	// Set bits up to start
318	self.current_chunk \|= (1 << start_bit) - 1;	500,067✔
319
320	loop {
321	if self.current_chunk != u64::MAX {	1,341,562✔
322	// Find the index of the first 0
323	let end_bit = self.current_chunk.trailing_ones();	499,329✔
324
325	// Zero out up to end_bit
326	self.current_chunk &= !((1 << end_bit) - 1);	499,329✔
327
328	return Some((	499,329✔
329	usize::try_from(start_chunk + start_bit as i64)	499,329✔
330	.vortex_expect("bit offset must be a usize"),	499,329✔
331	usize::try_from(self.current_offset + end_bit as i64)	499,329✔
332	.vortex_expect("bit offset must be a usize"),	499,329✔
333	));	499,329✔
334	}	842,233✔
335
336	match self.iter.next() {	842,233✔
337	Some(next) => {	841,495✔
338	self.current_chunk = next;	841,495✔
339	self.current_offset += 64;	841,495✔
340	}	841,495✔
341	None => {
342	return Some((	738✔
343	usize::try_from(start_chunk + start_bit as i64)	738✔
344	.vortex_expect("bit offset must be a usize"),	738✔
345	std::mem::take(&mut self.len),	738✔
346	));	738✔
347	}
348	}
349	}
350	}	506,471✔
351	}

vortex-data / vortex / 16992684502

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