Skip to main content

vortex_buffer/bit/
buf.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use std::convert::Infallible;
5use std::fmt::Display;
6use std::fmt::Formatter;
7use std::fmt::Result as FmtResult;
8use std::ops::BitAnd;
9use std::ops::BitOr;
10use std::ops::BitXor;
11use std::ops::Not;
12use std::ops::RangeBounds;
13
14use crate::Alignment;
15use crate::BitBufferMeta;
16use crate::BitBufferMut;
17use crate::Buffer;
18use crate::BufferAllocatorRef;
19use crate::BufferMut;
20use crate::ByteBuffer;
21use crate::bit::BitChunks;
22use crate::bit::BitIndexIterator;
23use crate::bit::BitIterator;
24use crate::bit::BitSliceIterator;
25use crate::bit::UnalignedBitChunk;
26use crate::bit::collect_bool_word;
27use crate::bit::count_ones::count_ones;
28use crate::bit::get_bit_unchecked;
29use crate::bit::ops::bitwise_binary_op;
30use crate::bit::ops::bitwise_binary_op_lhs_owned;
31use crate::bit::ops::bitwise_unary_op;
32use crate::bit::ops::bitwise_unary_op_copy;
33use crate::bit::select::bit_select;
34use crate::bit::select::bit_select_unset;
35
36/// An immutable bitset stored as a packed byte buffer.
37#[derive(Debug, Clone, Eq)]
38#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
39pub struct BitBuffer {
40    buffer: ByteBuffer,
41    /// Represents the offset of the bit buffer into the first byte.
42    ///
43    /// This is always less than 8 (for when the bit buffer is not aligned to a byte).
44    offset: usize,
45    len: usize,
46}
47
48const LIMIT_LEN: usize = 16;
49impl Display for BitBuffer {
50    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
51        let limit = f.precision().unwrap_or(LIMIT_LEN);
52        let buf: Vec<bool> = self.into_iter().take(limit).collect();
53        f.debug_struct("BitBuffer")
54            .field("len", &self.len)
55            .field("buffer", &buf)
56            .finish()
57    }
58}
59
60impl PartialEq for BitBuffer {
61    fn eq(&self, other: &Self) -> bool {
62        if self.len != other.len {
63            return false;
64        }
65
66        if self.len == 0 {
67            return true;
68        }
69
70        // Fast path: both byte-aligned and same length — direct byte comparison.
71        if self.offset == 0 && other.offset == 0 {
72            let full_bytes = self.len / 8;
73            let self_bytes = &self.buffer.as_slice()[..full_bytes];
74            let other_bytes = &other.buffer.as_slice()[..full_bytes];
75            if self_bytes != other_bytes {
76                return false;
77            }
78            // Compare remaining bits in the last partial byte.
79            let rem = self.len % 8;
80            if rem != 0 {
81                let mask = (1u8 << rem) - 1;
82                let a = self.buffer.as_slice()[full_bytes] & mask;
83                let b = other.buffer.as_slice()[full_bytes] & mask;
84                return a == b;
85            }
86            return true;
87        }
88
89        self.chunks()
90            .iter_padded()
91            .zip(other.chunks().iter_padded())
92            .all(|(a, b)| a == b)
93    }
94}
95
96impl BitBuffer {
97    /// Create a new `BoolBuffer` backed by a [`ByteBuffer`] with `len` bits in view.
98    ///
99    /// Panics if the buffer is not large enough to hold `len` bits.
100    #[inline]
101    pub fn new(buffer: ByteBuffer, len: usize) -> Self {
102        assert!(
103            buffer.len() * 8 >= len,
104            "provided ByteBuffer not large enough to back BoolBuffer with len {len}"
105        );
106
107        // BitBuffers make no assumptions on byte alignment, so we strip any alignment.
108        let buffer = buffer.aligned(Alignment::none());
109
110        Self {
111            buffer,
112            len,
113            offset: 0,
114        }
115    }
116
117    /// Create a new `BoolBuffer` backed by a [`ByteBuffer`] with `len` bits in view, starting at
118    /// the given `offset` (in bits).
119    ///
120    /// Panics if the buffer is not large enough to hold `len` bits after the offset.
121    #[inline]
122    pub fn new_with_offset(buffer: ByteBuffer, len: usize, offset: usize) -> Self {
123        assert!(
124            len.saturating_add(offset) <= buffer.len().saturating_mul(8),
125            "provided ByteBuffer (len={}) not large enough to back BoolBuffer with offset {offset} len {len}",
126            buffer.len()
127        );
128
129        // BitBuffers make no assumptions on byte alignment, so we strip any alignment.
130        let buffer = buffer.aligned(Alignment::none());
131
132        // Slice the buffer to ensure the offset is within the first byte
133        let byte_offset = offset / 8;
134        let offset = offset % 8;
135        let buffer = if byte_offset != 0 {
136            buffer.slice(byte_offset..)
137        } else {
138            buffer
139        };
140
141        Self {
142            buffer,
143            offset,
144            len,
145        }
146    }
147
148    /// Create a new `BoolBuffer` of length `len` where all bits are set (true).
149    #[inline]
150    pub fn new_set(len: usize) -> Self {
151        Self::new_set_in(len, BufferAllocatorRef::statically_allocated())
152    }
153
154    /// Create a set bit buffer with the provided allocator.
155    #[inline]
156    pub fn new_set_in(len: usize, allocator: BufferAllocatorRef) -> Self {
157        let words = len.div_ceil(8);
158        let buffer = Buffer::full_in(0xFF, words, allocator);
159
160        Self {
161            buffer,
162            len,
163            offset: 0,
164        }
165    }
166
167    /// Create a new `BoolBuffer` of length `len` where all bits are unset (false).
168    #[inline]
169    pub fn new_unset(len: usize) -> Self {
170        Self::new_unset_in(len, BufferAllocatorRef::statically_allocated())
171    }
172
173    /// Create an unset bit buffer with the provided allocator.
174    #[inline]
175    pub fn new_unset_in(len: usize, allocator: BufferAllocatorRef) -> Self {
176        let words = len.div_ceil(8);
177        let buffer = Buffer::zeroed_in(words, allocator);
178
179        Self {
180            buffer,
181            len,
182            offset: 0,
183        }
184    }
185
186    /// Create a bit buffer of `len` with `indices` set as true.
187    pub fn from_indices(len: usize, indices: impl IntoIterator<Item = usize>) -> BitBuffer {
188        BitBufferMut::from_indices(len, indices).freeze()
189    }
190
191    /// Create a new empty `BitBuffer`.
192    #[inline]
193    pub fn empty() -> Self {
194        Self::new_set(0)
195    }
196
197    /// Create a new `BitBuffer` of length `len` where all bits are set to `value`.
198    #[inline]
199    pub fn full(value: bool, len: usize) -> Self {
200        Self::full_in(value, len, BufferAllocatorRef::statically_allocated())
201    }
202
203    /// Create a full bit buffer with the provided allocator.
204    #[inline]
205    pub fn full_in(value: bool, len: usize, allocator: BufferAllocatorRef) -> Self {
206        if value {
207            Self::new_set_in(len, allocator)
208        } else {
209            Self::new_unset_in(len, allocator)
210        }
211    }
212
213    /// Collects `len` Boolean values from `f` into a packed [`BitBuffer`].
214    ///
215    /// Calls `f` exactly once for each index in `0..len`, in order.
216    ///
217    /// # Code generation
218    ///
219    /// `collect_bool_words` calls `collect_bool_words_inline`, which selects a `pack_bool_word_*`
220    /// kernel at compile time and passes it to `collect_bool_words_with`. That shared word loop
221    /// materializes each full 64-value chunk as a byte-per-value `[bool; 64]`, then passes it to the
222    /// selected kernel. For simple predicates, LLVM vectorizes the loop and removes the physical
223    /// stack array. On AVX-512, it still combines the comparison masks, expands the result into 64
224    /// `0` or `1` bytes with `vpbroadcastq` and `vmovdqu8`, then recreates the mask with `vptestmb`.
225    /// [LLVM issue #219235](https://github.com/llvm/llvm-project/issues/219235) tracks replacing
226    /// that round trip with a direct `kmovq` store. The conversion is per chunk. This method does
227    /// not create a full-column byte buffer.
228    ///
229    /// # Performance
230    ///
231    /// `collect_bool_words_inline` and `collect_bool_words_with` can inline into the caller, so LLVM
232    /// sees `f`, the fill loop, and the packing kernel together. A retained bounds check inside `f`
233    /// can prevent vectorization. A caller that proves `len <= values.len()` can use
234    /// `unsafe { *values.get_unchecked(i) }` because this method only passes indices in `0..len`.
235    ///
236    /// Use this method for general predicates. Use [`Self::collect_bool_multiversioned`] only for
237    /// the specialized predicates described there.
238    #[inline]
239    pub fn collect_bool<F: FnMut(usize) -> bool>(len: usize, f: F) -> Self {
240        BitBufferMut::collect_bool(len, f).freeze()
241    }
242
243    /// Collects predicate results with the provided allocator.
244    #[inline]
245    pub fn collect_bool_in<F: FnMut(usize) -> bool>(
246        len: usize,
247        f: F,
248        allocator: BufferAllocatorRef,
249    ) -> Self {
250        BitBufferMut::collect_bool_in(len, f, allocator).freeze()
251    }
252
253    /// Collects Boolean values with a fill-and-pack loop selected for the current CPU.
254    ///
255    /// This has the same callback contract as [`Self::collect_bool`]. On x86-64,
256    /// `collect_bool_words_multiversioned` selects `collect_bool_words_avx512`,
257    /// `collect_bool_words_avx2`, or `collect_bool_words_inline` at runtime. Each wider version is a
258    /// `#[target_feature]` function, so Rust cannot inline it into a caller compiled without those
259    /// features.
260    ///
261    /// Use this method only for a small, bounds-check-free predicate whose wider loop has been
262    /// benchmarked. Use [`Self::collect_bool`] for general predicates.
263    #[inline]
264    pub fn collect_bool_multiversioned<F: FnMut(usize) -> bool>(len: usize, f: F) -> Self {
265        Self::collect_bool_multiversioned_in(len, f, BufferAllocatorRef::statically_allocated())
266    }
267
268    /// Collects multiversioned predicate results with the provided allocator.
269    #[inline]
270    pub fn collect_bool_multiversioned_in<F: FnMut(usize) -> bool>(
271        len: usize,
272        f: F,
273        allocator: BufferAllocatorRef,
274    ) -> Self {
275        BitBufferMut::collect_bool_multiversioned_in(len, f, allocator).freeze()
276    }
277
278    /// Maps over each bit in this buffer, calling `f(index, bit_value)` and collecting results.
279    ///
280    /// This is more efficient than `collect_bool` when you need to read the current bit value,
281    /// as it unpacks each u64 chunk only once rather than doing random access for each bit.
282    pub fn map_cmp<F>(&self, mut f: F) -> Self
283    where
284        F: FnMut(usize, bool) -> bool,
285    {
286        let len = self.len;
287        let mut buffer: BufferMut<u64> = BufferMut::with_capacity(len.div_ceil(64));
288
289        let chunks_count = len / 64;
290        let remainder = len % 64;
291        let chunks = self.chunks();
292
293        for (chunk_idx, src_chunk) in chunks.iter().enumerate() {
294            let packed = collect_bool_word(64, |bit_idx| {
295                let i = bit_idx + chunk_idx * 64;
296                let bit_value = (src_chunk >> bit_idx) & 1 == 1;
297                f(i, bit_value)
298            });
299
300            // SAFETY: Already allocated sufficient capacity
301            unsafe { buffer.push_unchecked(packed) }
302        }
303
304        if remainder != 0 {
305            let src_chunk = chunks.remainder_bits();
306            let packed = collect_bool_word(remainder, |bit_idx| {
307                let i = bit_idx + chunks_count * 64;
308                let bit_value = (src_chunk >> bit_idx) & 1 == 1;
309                f(i, bit_value)
310            });
311
312            // SAFETY: Already allocated sufficient capacity
313            unsafe { buffer.push_unchecked(packed) }
314        }
315
316        let mut bytes = buffer.into_byte_buffer();
317        bytes.truncate(len.div_ceil(8));
318
319        Self {
320            buffer: bytes.freeze(),
321            offset: 0,
322            len,
323        }
324    }
325
326    /// Clear all bits in the buffer, preserving existing capacity.
327    #[inline]
328    pub fn clear(&mut self) {
329        self.buffer.clear();
330        self.len = 0;
331        self.offset = 0;
332    }
333
334    /// Get the logical length of this `BoolBuffer`.
335    ///
336    /// This may differ from the physical length of the backing buffer, for example if it was
337    /// created using the `new_with_offset` constructor, or if it was sliced.
338    #[inline]
339    pub fn len(&self) -> usize {
340        self.len
341    }
342
343    /// Returns `true` if the `BoolBuffer` is empty.
344    #[inline]
345    pub fn is_empty(&self) -> bool {
346        self.len() == 0
347    }
348
349    /// Offset of the start of the buffer in bits.
350    #[allow(clippy::inline_always)]
351    #[inline(always)]
352    pub fn offset(&self) -> usize {
353        self.offset
354    }
355
356    /// Get a reference to the underlying buffer.
357    #[allow(clippy::inline_always)]
358    #[inline(always)]
359    pub fn inner(&self) -> &ByteBuffer {
360        &self.buffer
361    }
362
363    /// Return the backing bytes for this bit buffer when its logical offset is byte-aligned.
364    ///
365    /// The returned slice contains exactly `self.len().div_ceil(8)` bytes. Bits past the logical
366    /// length in the final byte are outside the buffer's logical range and should be ignored by
367    /// callers.
368    #[inline]
369    pub fn byte_aligned_bytes(&self) -> Option<&[u8]> {
370        if !self.offset.is_multiple_of(8) {
371            return None;
372        }
373
374        let n_bytes = self.len.div_ceil(8);
375        let start = self.offset / 8;
376        let end = start + n_bytes;
377        Some(&self.buffer.as_slice()[start..end])
378    }
379
380    /// Retrieve the value at the given index.
381    ///
382    /// Panics if the index is out of bounds.
383    ///
384    /// Please note for repeatedly calling this function, please prefer [`crate::get_bit`].
385    #[inline]
386    pub fn value(&self, index: usize) -> bool {
387        assert!(index < self.len);
388        unsafe { self.value_unchecked(index) }
389    }
390
391    /// Retrieve the value at the given index without bounds checking
392    ///
393    /// # SAFETY
394    /// Caller must ensure that index is within the range of the buffer
395    #[inline]
396    pub unsafe fn value_unchecked(&self, index: usize) -> bool {
397        unsafe { get_bit_unchecked(self.buffer.as_ptr(), index + self.offset) }
398    }
399
400    /// Create a new zero-copy slice of this BoolBuffer that begins at the `start` index and extends
401    /// for `len` bits.
402    ///
403    /// Panics if the slice would extend beyond the end of the buffer.
404    #[inline]
405    pub fn slice(&self, range: impl RangeBounds<usize>) -> Self {
406        let (byte_offset, meta) = BitBufferMeta::new(self.offset, self.len).slice(range);
407
408        // Trim whole bytes off the front directly rather than going through `new_with_offset`,
409        // which would slice (and re-clone) the clone we'd have to pass it.
410        let buffer = if byte_offset != 0 {
411            self.buffer.slice_unaligned(byte_offset..)
412        } else {
413            self.buffer.clone().aligned(Alignment::none())
414        };
415
416        Self {
417            buffer,
418            offset: meta.offset(),
419            len: meta.len(),
420        }
421    }
422
423    /// Slice any full bytes from the buffer, leaving the offset < 8.
424    pub fn shrink_offset(self) -> Self {
425        let word_start = self.offset / 8;
426        let word_end = (self.offset + self.len).div_ceil(8);
427
428        let buffer = self.buffer.slice(word_start..word_end);
429
430        let bit_offset = self.offset % 8;
431        let len = self.len;
432        BitBuffer::new_with_offset(buffer, len, bit_offset)
433    }
434
435    /// Access chunks of the buffer aligned to 8 byte boundary as [prefix, \<full chunks\>, suffix]
436    #[inline]
437    pub fn unaligned_chunks(&self) -> UnalignedBitChunk<'_> {
438        UnalignedBitChunk::new(self.buffer.as_slice(), self.offset, self.len)
439    }
440
441    /// Access chunks of the underlying buffer as 8 byte chunks with a final trailer
442    ///
443    /// If you're performing operations on a single buffer, prefer [BitBuffer::unaligned_chunks]
444    #[inline]
445    pub fn chunks(&self) -> BitChunks<'_> {
446        BitChunks::new(self.buffer.as_slice(), self.offset, self.len)
447    }
448
449    /// Get the number of set bits in the buffer.
450    #[inline]
451    pub fn true_count(&self) -> usize {
452        count_ones(self.buffer.as_slice(), self.offset, self.len)
453    }
454
455    /// Get the number of set bits in the bit range `[start, end)`.
456    ///
457    /// Unlike `self.slice(start..end).true_count()`, this counts directly over the
458    /// existing backing buffer without allocating or cloning a new [`BitBuffer`],
459    /// making it cheap to call repeatedly over many small ranges.
460    ///
461    /// Panics if `start > end` or `end > len`.
462    #[inline]
463    pub fn count_range(&self, start: usize, end: usize) -> usize {
464        assert!(start <= end, "start {start} exceeds end {end}");
465        assert!(end <= self.len, "end {end} exceeds len {}", self.len);
466        count_ones(self.buffer.as_slice(), self.offset + start, end - start)
467    }
468
469    /// Returns the position of the `nth` set bit (0-indexed).
470    ///
471    /// This is the "select" operation on a bitmap: given a rank `nth`, find
472    /// which logical bit position holds that rank.
473    ///
474    /// Returns `None` if `nth` is greater than or equal to the number of set bits.
475    #[inline]
476    pub fn select(&self, nth: usize) -> Option<usize> {
477        bit_select(self.buffer.as_slice(), self.offset, self.len, nth)
478    }
479
480    /// Returns the position of the `nth` unset bit (0-indexed).
481    ///
482    /// This is the "select0" operation, the counterpart of [`Self::select`] for unset bits:
483    /// given a rank `nth` among the unset bits, find which logical bit position holds it.
484    ///
485    /// Returns `None` if `nth` is greater than or equal to the number of unset bits.
486    #[inline]
487    pub fn select_unset(&self, nth: usize) -> Option<usize> {
488        bit_select_unset(self.buffer.as_slice(), self.offset, self.len, nth)
489    }
490
491    /// Returns the index of the last set bit, or `None` if every bit is unset.
492    ///
493    /// This scans from the end a word at a time, avoiding the full forward scan required by
494    /// [`Self::select`] when selecting the final set bit.
495    #[inline]
496    pub fn last_set_index(&self) -> Option<usize> {
497        let chunks = self.unaligned_chunks();
498        let lead = chunks.lead_padding();
499        let prefix_words = usize::from(chunks.prefix().is_some());
500
501        if let Some(word) = chunks.suffix()
502            && word != 0
503        {
504            let word_index = prefix_words + chunks.chunks().len();
505            return Some(word_index * 64 + 63 - word.leading_zeros() as usize - lead);
506        }
507
508        for (index, &word) in chunks.chunks().iter().enumerate().rev() {
509            if word != 0 {
510                let word_index = prefix_words + index;
511                return Some(word_index * 64 + 63 - word.leading_zeros() as usize - lead);
512            }
513        }
514
515        chunks.prefix().filter(|word| *word != 0).map(|word| {
516            debug_assert!(word.trailing_zeros() as usize >= lead);
517            63 - word.leading_zeros() as usize - lead
518        })
519    }
520
521    /// Get the number of unset bits in the buffer.
522    #[inline]
523    pub fn false_count(&self) -> usize {
524        self.len - self.true_count()
525    }
526
527    /// Iterator over bits in the buffer
528    #[inline]
529    pub fn iter(&self) -> BitIterator<'_> {
530        BitIterator::new(self.buffer.as_slice(), self.offset, self.len)
531    }
532
533    /// Iterator over set indices of the underlying buffer
534    #[inline]
535    pub fn set_indices(&self) -> BitIndexIterator<'_> {
536        BitIndexIterator::new(self.buffer.as_slice(), self.offset, self.len)
537    }
538
539    /// Iterator over set slices of the underlying buffer
540    #[inline]
541    pub fn set_slices(&self) -> BitSliceIterator<'_> {
542        BitSliceIterator::new(self.buffer.as_slice(), self.offset, self.len)
543    }
544
545    /// Invoke `f(index)` for every set bit, in ascending order, processing a `u64`
546    /// word at a time.
547    ///
548    /// This is the fast way to "do something for each set bit": it skips all-zero
549    /// words, fast-paths all-one words, and walks the remaining bits with
550    /// `trailing_zeros`. Prefer it over `for i in 0..len { if buf.value(i) { f(i) } }`
551    /// (which pays a branch per element) and over collecting [`Self::set_indices`]
552    /// (whose per-`next` iterator state does not inline as well).
553    #[inline]
554    pub fn for_each_set_index<F: FnMut(usize)>(&self, mut f: F) {
555        let Ok(()) = self.try_for_each_set_index(|index| {
556            f(index);
557            Ok::<_, Infallible>(())
558        });
559    }
560
561    /// Fallible variant of [`for_each_set_index`](Self::for_each_set_index).
562    ///
563    /// Stops and returns the first error from `f`.
564    #[inline]
565    pub fn try_for_each_set_index<E, F>(&self, f: F) -> Result<(), E>
566    where
567        F: FnMut(usize) -> Result<(), E>,
568    {
569        self.try_for_each_index::<false, E, F>(f)
570    }
571
572    /// Invoke `f(index)` for every unset bit, in ascending order, processing a `u64` word at a
573    /// time.
574    ///
575    /// This is the counterpart of [`for_each_set_index`](Self::for_each_set_index) for unset bits.
576    #[inline]
577    pub fn for_each_unset_index<F: FnMut(usize)>(&self, mut f: F) {
578        let Ok(()) = self.try_for_each_index::<true, _, _>(|index| {
579            f(index);
580            Ok::<_, Infallible>(())
581        });
582    }
583
584    /// The scan behind [`try_for_each_set_index`](Self::try_for_each_set_index). With `UNSET`,
585    /// each word is inverted as it is read, so the same scan visits the unset bits instead.
586    #[inline]
587    fn try_for_each_index<const UNSET: bool, E, F>(&self, mut f: F) -> Result<(), E>
588    where
589        F: FnMut(usize) -> Result<(), E>,
590    {
591        let mut base = 0usize;
592        for word in self.chunks().iter_padded() {
593            let word = if UNSET {
594                // The last word is zero padded past `len`. Setting the padding before inverting
595                // keeps it from being visited.
596                let held = self.len - base;
597                let padding = if held < 64 { u64::MAX << held } else { 0 };
598                !(word | padding)
599            } else {
600                word
601            };
602            if word == u64::MAX {
603                for k in 0..64 {
604                    f(base + k)?;
605                }
606            } else {
607                let mut w = word;
608                while w != 0 {
609                    f(base + w.trailing_zeros() as usize)?;
610                    w &= w - 1;
611                }
612            }
613            base += 64;
614        }
615
616        Ok(())
617    }
618
619    /// Created a new BitBuffer with offset reset to 0
620    pub fn sliced(&self) -> Self {
621        if self.offset.is_multiple_of(8) {
622            return Self::new(
623                self.buffer
624                    .slice(self.offset / 8..(self.offset + self.len).div_ceil(8)),
625                self.len,
626            );
627        }
628
629        // Allocate directly rather than clone + identity op which would fail try_into_mut.
630        bitwise_unary_op_copy(self, |a| a)
631    }
632}
633
634// Conversions
635
636impl BitBuffer {
637    /// Returns the offset, len and underlying buffer.
638    #[inline]
639    pub fn into_inner(self) -> (usize, usize, ByteBuffer) {
640        (self.offset, self.len, self.buffer)
641    }
642
643    /// Attempt to convert this `BitBuffer` into a mutable version.
644    #[inline]
645    pub fn try_into_mut(self) -> Result<BitBufferMut, Self> {
646        match self.buffer.try_into_mut() {
647            Ok(buffer) => Ok(BitBufferMut::from_buffer(buffer, self.offset, self.len)),
648            Err(buffer) => Err(BitBuffer::new_with_offset(buffer, self.len, self.offset)),
649        }
650    }
651}
652
653impl From<&[bool]> for BitBuffer {
654    fn from(value: &[bool]) -> Self {
655        BitBufferMut::from(value).freeze()
656    }
657}
658
659impl From<Vec<bool>> for BitBuffer {
660    fn from(value: Vec<bool>) -> Self {
661        BitBufferMut::from(value).freeze()
662    }
663}
664
665impl FromIterator<bool> for BitBuffer {
666    #[inline]
667    fn from_iter<T: IntoIterator<Item = bool>>(iter: T) -> Self {
668        BitBufferMut::from_iter(iter).freeze()
669    }
670}
671
672impl BitOr for BitBuffer {
673    type Output = Self;
674
675    #[inline]
676    fn bitor(self, rhs: Self) -> Self::Output {
677        bitwise_binary_op_lhs_owned(self, &rhs, |a, b| a | b)
678    }
679}
680
681impl BitOr for &BitBuffer {
682    type Output = BitBuffer;
683
684    #[inline]
685    fn bitor(self, rhs: Self) -> Self::Output {
686        bitwise_binary_op(self, rhs, |a, b| a | b)
687    }
688}
689
690impl BitOr<&BitBuffer> for BitBuffer {
691    type Output = BitBuffer;
692
693    #[inline]
694    fn bitor(self, rhs: &BitBuffer) -> Self::Output {
695        bitwise_binary_op_lhs_owned(self, rhs, |a, b| a | b)
696    }
697}
698
699impl BitAnd for &BitBuffer {
700    type Output = BitBuffer;
701
702    #[inline]
703    fn bitand(self, rhs: Self) -> Self::Output {
704        bitwise_binary_op(self, rhs, |a, b| a & b)
705    }
706}
707
708impl BitAnd<BitBuffer> for &BitBuffer {
709    type Output = BitBuffer;
710
711    #[inline]
712    fn bitand(self, rhs: BitBuffer) -> Self::Output {
713        self.bitand(&rhs)
714    }
715}
716
717impl BitAnd<&BitBuffer> for BitBuffer {
718    type Output = BitBuffer;
719
720    #[inline]
721    fn bitand(self, rhs: &BitBuffer) -> Self::Output {
722        bitwise_binary_op_lhs_owned(self, rhs, |a, b| a & b)
723    }
724}
725
726impl BitAnd<BitBuffer> for BitBuffer {
727    type Output = BitBuffer;
728
729    #[inline]
730    fn bitand(self, rhs: BitBuffer) -> Self::Output {
731        bitwise_binary_op_lhs_owned(self, &rhs, |a, b| a & b)
732    }
733}
734
735impl Not for &BitBuffer {
736    type Output = BitBuffer;
737
738    #[inline]
739    fn not(self) -> Self::Output {
740        // Allocate directly rather than clone+try_into_mut, which always fails
741        // since the clone shares the Arc with the original reference.
742        bitwise_unary_op_copy(self, |a| !a)
743    }
744}
745
746impl Not for BitBuffer {
747    type Output = BitBuffer;
748
749    #[inline]
750    fn not(self) -> Self::Output {
751        bitwise_unary_op(self, |a| !a)
752    }
753}
754
755impl BitXor for &BitBuffer {
756    type Output = BitBuffer;
757
758    #[inline]
759    fn bitxor(self, rhs: Self) -> Self::Output {
760        bitwise_binary_op(self, rhs, |a, b| a ^ b)
761    }
762}
763
764impl BitXor<&BitBuffer> for BitBuffer {
765    type Output = BitBuffer;
766
767    #[inline]
768    fn bitxor(self, rhs: &BitBuffer) -> Self::Output {
769        bitwise_binary_op_lhs_owned(self, rhs, |a, b| a ^ b)
770    }
771}
772
773impl BitBuffer {
774    /// Create a new BitBuffer by performing a bitwise AND NOT operation between two BitBuffers.
775    ///
776    /// This operation is sufficiently common that we provide a dedicated method for it avoid
777    /// making two passes over the data.
778    pub fn bitand_not(&self, rhs: &BitBuffer) -> BitBuffer {
779        bitwise_binary_op(self, rhs, |a, b| a & !b)
780    }
781
782    /// Owned variant of [`bitand_not`](Self::bitand_not) that can mutate in-place when possible.
783    pub fn into_bitand_not(self, rhs: &BitBuffer) -> BitBuffer {
784        bitwise_binary_op_lhs_owned(self, rhs, |a, b| a & !b)
785    }
786
787    /// Iterate through bits in a buffer.
788    ///
789    /// # Arguments
790    ///
791    /// * `f` - Callback function taking (bit_index, is_set)
792    ///
793    /// # Panics
794    ///
795    /// Panics if the range is outside valid bounds of the buffer.
796    #[inline]
797    pub fn iter_bits<F>(&self, mut f: F)
798    where
799        F: FnMut(usize, bool),
800    {
801        let total_bits = self.len;
802        if total_bits == 0 {
803            return;
804        }
805
806        // Process in 64-bit chunks for better ILP and fewer loop iterations.
807        let chunks = self.chunks();
808        let chunks_count = total_bits / 64;
809        let remainder = total_bits % 64;
810
811        for (chunk_idx, chunk) in chunks.iter().enumerate() {
812            let base = chunk_idx * 64;
813            for bit_idx in 0..64 {
814                f(base + bit_idx, (chunk >> bit_idx) & 1 == 1);
815            }
816        }
817
818        if remainder != 0 {
819            let rem_chunk = chunks.remainder_bits();
820            let base = chunks_count * 64;
821            for bit_idx in 0..remainder {
822                f(base + bit_idx, (rem_chunk >> bit_idx) & 1 == 1);
823            }
824        }
825    }
826}
827
828impl<'a> IntoIterator for &'a BitBuffer {
829    type Item = bool;
830    type IntoIter = BitIterator<'a>;
831
832    fn into_iter(self) -> Self::IntoIter {
833        self.iter()
834    }
835}
836
837#[cfg(test)]
838mod tests {
839    use rand::RngExt;
840    use rand::SeedableRng;
841    use rand::rngs::StdRng;
842    use rstest::rstest;
843    use vortex_error::VortexResult;
844
845    use crate::ByteBuffer;
846    use crate::bit::BitBuffer;
847    use crate::buffer;
848
849    #[test]
850    fn test_bool() {
851        // Create a new Buffer<u64> of length 1024 where the 8th bit is set.
852        let buffer: ByteBuffer = buffer![1 << 7; 1024];
853        let bools = BitBuffer::new(buffer, 1024 * 8);
854
855        // sanity checks
856        assert_eq!(bools.len(), 1024 * 8);
857        assert!(!bools.is_empty());
858        assert_eq!(bools.true_count(), 1024);
859        assert_eq!(bools.false_count(), 1024 * 7);
860
861        // Check all the values
862        for word in 0..1024 {
863            for bit in 0..8 {
864                if bit == 7 {
865                    assert!(bools.value(word * 8 + bit));
866                } else {
867                    assert!(!bools.value(word * 8 + bit));
868                }
869            }
870        }
871
872        // Slice the buffer to create a new subset view.
873        let sliced = bools.slice(64..72);
874
875        // sanity checks
876        assert_eq!(sliced.len(), 8);
877        assert!(!sliced.is_empty());
878        assert_eq!(sliced.true_count(), 1);
879        assert_eq!(sliced.false_count(), 7);
880
881        // Check all of the values like before
882        for bit in 0..8 {
883            if bit == 7 {
884                assert!(sliced.value(bit));
885            } else {
886                assert!(!sliced.value(bit));
887            }
888        }
889    }
890
891    #[test]
892    fn test_padded_equaltiy() {
893        let buf1 = BitBuffer::new_set(64); // All bits set.
894        let buf2 = BitBuffer::collect_bool(64, |x| x < 32); // First half set, other half unset.
895
896        for i in 0..32 {
897            assert_eq!(buf1.value(i), buf2.value(i), "Bit {} should be the same", i);
898        }
899
900        for i in 32..64 {
901            assert_ne!(buf1.value(i), buf2.value(i), "Bit {} should differ", i);
902        }
903
904        assert_eq!(
905            buf1.slice(0..32),
906            buf2.slice(0..32),
907            "Buffer slices with same bits should be equal (`PartialEq` needs `iter_padded()`)"
908        );
909        assert_ne!(
910            buf1.slice(32..64),
911            buf2.slice(32..64),
912            "Buffer slices with different bits should not be equal (`PartialEq` needs `iter_padded()`)"
913        );
914    }
915
916    #[test]
917    fn test_slice_offset_calculation() {
918        let buf = BitBuffer::collect_bool(16, |_| true);
919        let sliced = buf.slice(10..16);
920        assert_eq!(sliced.len(), 6);
921        // Ensure the offset is modulo 8
922        assert_eq!(sliced.offset(), 2);
923    }
924
925    #[test]
926    fn test_byte_aligned_bytes() {
927        let bytes: ByteBuffer = buffer![0b1010_0101u8, 0b0000_0011];
928        let buf = BitBuffer::new(bytes.clone(), 10);
929        assert_eq!(buf.byte_aligned_bytes(), Some(bytes.as_slice()));
930
931        let byte_sliced = buf.slice(8..10);
932        assert_eq!(byte_sliced.byte_aligned_bytes(), Some(&[0b0000_0011][..]));
933
934        let bit_sliced = buf.slice(1..9);
935        assert!(bit_sliced.byte_aligned_bytes().is_none());
936    }
937
938    #[test]
939    fn test_from_indices_dense_crosses_words() {
940        let len = 130;
941        let indices = (0..len).filter(|idx| idx % 3 != 1);
942        let buf = BitBuffer::from_indices(len, indices);
943
944        assert_eq!(buf.len(), len);
945        for idx in 0..len {
946            assert_eq!(buf.value(idx), idx % 3 != 1, "mismatch at {idx}");
947        }
948    }
949
950    #[test]
951    #[should_panic(expected = "index 5 exceeds len 5")]
952    fn test_from_indices_out_of_bounds() {
953        BitBuffer::from_indices(5, [0, 5]);
954    }
955
956    #[rstest]
957    #[case(0, 0, None)]
958    #[case(3, 7, None)]
959    #[case(0, 1, Some(0))]
960    #[case(8, 64, Some(63))]
961    #[case(13, 65, Some(0))]
962    #[case(13, 65, Some(64))]
963    #[case(67, 151, Some(97))]
964    #[case(67, 151, Some(150))]
965    fn last_set_index_handles_offsets_and_padding(
966        #[case] offset: usize,
967        #[case] len: usize,
968        #[case] expected: Option<usize>,
969    ) {
970        let backing = BitBuffer::from_iter(
971            std::iter::repeat_n(true, offset)
972                .chain((0..len).map(|index| Some(index) == expected))
973                .chain(std::iter::repeat_n(true, 7)),
974        );
975        let buffer = BitBuffer::new_with_offset(backing.inner().clone(), len, offset);
976
977        assert_eq!(buffer.last_set_index(), expected);
978    }
979
980    #[rstest]
981    #[case(5)]
982    #[case(8)]
983    #[case(10)]
984    #[case(13)]
985    #[case(16)]
986    #[case(23)]
987    #[case(100)]
988    fn test_iter_bits(#[case] len: usize) {
989        let buf = BitBuffer::collect_bool(len, |i| i % 2 == 0);
990
991        let mut collected = Vec::new();
992        buf.iter_bits(|idx, is_set| {
993            collected.push((idx, is_set));
994        });
995
996        let expected: Vec<_> = (0..len).map(|idx| (idx, idx % 2 == 0)).collect();
997        assert_eq!(collected, expected);
998    }
999
1000    #[rstest]
1001    #[case(3, 5)]
1002    #[case(3, 8)]
1003    #[case(5, 10)]
1004    #[case(2, 16)]
1005    #[case(8, 16)]
1006    #[case(9, 16)]
1007    #[case(17, 16)]
1008    fn test_iter_bits_with_offset(#[case] offset: usize, #[case] len: usize) {
1009        let total_bits = offset + len;
1010        let buf = BitBuffer::collect_bool(total_bits, |i| i % 2 == 0);
1011        let buf_with_offset = BitBuffer::new_with_offset(buf.inner().clone(), len, offset);
1012
1013        let mut collected = Vec::new();
1014        buf_with_offset.iter_bits(|idx, is_set| {
1015            collected.push((idx, is_set));
1016        });
1017
1018        let expected: Vec<_> = (0..len)
1019            .map(|idx| (idx, (offset + idx).is_multiple_of(2)))
1020            .collect();
1021        assert_eq!(collected, expected);
1022    }
1023
1024    #[rstest]
1025    #[case(8, 10)]
1026    #[case(9, 7)]
1027    #[case(16, 8)]
1028    #[case(17, 10)]
1029    fn test_iter_bits_catches_wrong_byte_offset(#[case] offset: usize, #[case] len: usize) {
1030        let total_bits = offset + len;
1031        // Alternating pattern to catch byte offset errors: Bits are set for even indexed bytes.
1032        let buf = BitBuffer::collect_bool(total_bits, |i| (i / 8) % 2 == 0);
1033
1034        let buf_with_offset = BitBuffer::new_with_offset(buf.inner().clone(), len, offset);
1035
1036        let mut collected = Vec::new();
1037        buf_with_offset.iter_bits(|idx, is_set| {
1038            collected.push((idx, is_set));
1039        });
1040
1041        let expected: Vec<_> = (0..len)
1042            .map(|idx| (idx, ((offset + idx) / 8).is_multiple_of(2)))
1043            .collect();
1044        assert_eq!(collected, expected);
1045    }
1046
1047    #[rstest]
1048    #[case(5)]
1049    #[case(8)]
1050    #[case(10)]
1051    #[case(64)]
1052    #[case(65)]
1053    #[case(100)]
1054    #[case(128)]
1055    fn test_map_cmp_identity(#[case] len: usize) {
1056        // map_cmp with identity function should return the same buffer
1057        let buf = BitBuffer::collect_bool(len, |i| i % 3 == 0);
1058        let mapped = buf.map_cmp(|_idx, bit| bit);
1059
1060        assert_eq!(buf.len(), mapped.len());
1061        for i in 0..len {
1062            assert_eq!(buf.value(i), mapped.value(i), "Mismatch at index {}", i);
1063        }
1064    }
1065
1066    #[rstest]
1067    #[case(5)]
1068    #[case(8)]
1069    #[case(64)]
1070    #[case(65)]
1071    #[case(100)]
1072    fn test_map_cmp_negate(#[case] len: usize) {
1073        // map_cmp negating all bits
1074        let buf = BitBuffer::collect_bool(len, |i| i % 2 == 0);
1075        let mapped = buf.map_cmp(|_idx, bit| !bit);
1076
1077        assert_eq!(buf.len(), mapped.len());
1078        for i in 0..len {
1079            assert_eq!(!buf.value(i), mapped.value(i), "Mismatch at index {}", i);
1080        }
1081    }
1082
1083    #[rstest]
1084    #[case(0, 0)]
1085    #[case(0, 64)]
1086    #[case(5, 70)]
1087    #[case(64, 130)]
1088    #[case(0, 200)]
1089    fn test_count_range(#[case] start: usize, #[case] end: usize) {
1090        let len = 200;
1091        let buf = BitBuffer::collect_bool(len, |i| i % 3 == 0);
1092        let expected = (start..end).filter(|i| i % 3 == 0).count();
1093        assert_eq!(buf.count_range(start, end), expected);
1094        // Must agree with slicing then counting.
1095        assert_eq!(
1096            buf.count_range(start, end),
1097            buf.slice(start..end).true_count()
1098        );
1099    }
1100
1101    #[rstest]
1102    #[case(3)]
1103    #[case(7)]
1104    fn test_count_range_with_offset(#[case] offset: usize) {
1105        let len = 150;
1106        let buf = BitBuffer::collect_bool(offset + len, |i| i % 2 == 0);
1107        let view = BitBuffer::new_with_offset(buf.inner().clone(), len, offset);
1108        for (start, end) in [(0, len), (10, 100), (1, 2), (63, 129)] {
1109            let expected = (offset + start..offset + end)
1110                .filter(|i| i % 2 == 0)
1111                .count();
1112            assert_eq!(view.count_range(start, end), expected, "[{start}, {end})");
1113        }
1114    }
1115
1116    #[rstest]
1117    #[case(0)]
1118    #[case(1)]
1119    #[case(63)]
1120    #[case(64)]
1121    #[case(65)]
1122    #[case(200)]
1123    #[case(1000)]
1124    fn test_set_index_visitors_match_set_indices(#[case] len: usize) {
1125        let buf = BitBuffer::collect_bool(len, |i| i % 5 == 0 || i % 7 == 0);
1126        let expected: Vec<usize> = buf.set_indices().collect();
1127
1128        let mut got = Vec::new();
1129        buf.for_each_set_index(|i| got.push(i));
1130        assert_eq!(got, expected);
1131
1132        let mut fallible_got = Vec::new();
1133        let result = buf.try_for_each_set_index(|i| {
1134            fallible_got.push(i);
1135            Ok::<(), ()>(())
1136        });
1137        assert_eq!(result, Ok(()));
1138        assert_eq!(fallible_got, expected);
1139    }
1140
1141    #[rstest]
1142    #[case(3, 200)]
1143    #[case(7, 130)]
1144    fn test_for_each_set_index_with_offset(#[case] offset: usize, #[case] len: usize) {
1145        let base = BitBuffer::collect_bool(offset + len, |i| i % 3 == 0);
1146        let view = BitBuffer::new_with_offset(base.inner().clone(), len, offset);
1147        let expected: Vec<usize> = view.set_indices().collect();
1148        let mut got = Vec::new();
1149        view.for_each_set_index(|i| got.push(i));
1150        assert_eq!(got, expected);
1151    }
1152
1153    #[test]
1154    fn test_for_each_set_index_all_set() {
1155        let buf = BitBuffer::new_set(130);
1156        let mut got = Vec::new();
1157        buf.for_each_set_index(|i| got.push(i));
1158        assert_eq!(got, (0..130).collect::<Vec<_>>());
1159    }
1160
1161    #[test]
1162    fn test_try_for_each_set_index_stops_on_error() {
1163        for (buffer, stop) in [
1164            (BitBuffer::new_set(130), 65),
1165            (BitBuffer::collect_bool(130, |i| i % 3 == 0), 66),
1166        ] {
1167            let mut visited = Vec::new();
1168            let result = buffer.try_for_each_set_index(|index| {
1169                visited.push(index);
1170                if index == stop {
1171                    return Err(index);
1172                }
1173
1174                Ok(())
1175            });
1176
1177            assert_eq!(result, Err(stop));
1178            assert_eq!(
1179                visited,
1180                buffer
1181                    .set_indices()
1182                    .take_while(|&i| i <= stop)
1183                    .collect::<Vec<_>>()
1184            );
1185        }
1186    }
1187
1188    #[rstest]
1189    #[case(0)]
1190    #[case(1)]
1191    #[case(63)]
1192    #[case(64)]
1193    #[case(65)]
1194    #[case(128)]
1195    #[case(200)]
1196    fn test_for_each_unset_index_agrees_with_naive(#[case] len: usize) -> VortexResult<()> {
1197        let mut rng = StdRng::seed_from_u64(u64::try_from(len)?);
1198        let random: BitBuffer = (0..len).map(|_| rng.random_bool(0.5)).collect();
1199        // The same kind of bits, starting 3 bits into their buffer.
1200        let offset: BitBuffer = (0..len + 3).map(|_| rng.random_bool(0.5)).collect();
1201        for bits in [
1202            random,
1203            offset.slice(3..),
1204            BitBuffer::new_set(len),
1205            BitBuffer::new_unset(len),
1206        ] {
1207            let expected: Vec<usize> = bits
1208                .iter()
1209                .enumerate()
1210                .filter_map(|(index, set)| (!set).then_some(index))
1211                .collect();
1212            let mut found = Vec::new();
1213            bits.for_each_unset_index(|index| found.push(index));
1214            assert_eq!(found, expected);
1215        }
1216        Ok(())
1217    }
1218
1219    #[test]
1220    fn test_map_cmp_conditional() {
1221        // map_cmp with conditional logic based on index and bit value
1222        let len = 100;
1223        let buf = BitBuffer::collect_bool(len, |i| i % 2 == 0);
1224
1225        // Only keep bits that are set AND at even index divisible by 4
1226        let mapped = buf.map_cmp(|idx, bit| bit && idx % 4 == 0);
1227
1228        for i in 0..len {
1229            let expected = (i % 2 == 0) && (i % 4 == 0);
1230            assert_eq!(mapped.value(i), expected, "Mismatch at index {}", i);
1231        }
1232    }
1233
1234    #[rstest]
1235    #[case(0, 200)]
1236    #[case(3, 197)]
1237    #[case(13, 600)]
1238    fn test_select_unset_sliced(#[case] start: usize, #[case] len: usize) {
1239        let buf = BitBuffer::collect_bool(start + len, |i| i % 3 == 0 || i % 7 == 0);
1240        let sliced = buf.slice(start..start + len);
1241        let expected: Vec<usize> = sliced
1242            .iter()
1243            .enumerate()
1244            .filter_map(|(index, set)| (!set).then_some(index))
1245            .collect();
1246
1247        for (nth, &index) in expected.iter().enumerate() {
1248            assert_eq!(
1249                sliced.select_unset(nth),
1250                Some(index),
1251                "start={start} nth={nth}"
1252            );
1253        }
1254        assert_eq!(sliced.select_unset(expected.len()), None);
1255    }
1256}