Skip to main content

arrow_buffer/util/
bit_chunk_iterator.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4
5//! Types for iterating over bitmasks in 64-bit chunks
6
7#[cfg(target_arch = "aarch64")]
8use crate::ToByteSlice;
9use crate::util::bit_util::ceil;
10use std::fmt::Debug;
11
12/// Iterates over an arbitrarily aligned byte buffer
13///
14/// Yields an iterator of aligned u64, along with the leading and trailing
15/// u64 necessary to align the buffer to a 8-byte boundary
16///
17/// This is unlike [`BitChunkIterator`] which only exposes a trailing u64,
18/// and consequently has to perform more work for each read
19#[derive(Debug)]
20pub struct UnalignedBitChunk<'a> {
21    lead_padding: usize,
22    trailing_padding: usize,
23
24    prefix: Option<u64>,
25    chunks: &'a [u64],
26    suffix: Option<u64>,
27}
28
29impl<'a> UnalignedBitChunk<'a> {
30    /// Create from a byte array, offset and length in bits
31    pub fn new(buffer: &'a [u8], offset: usize, len: usize) -> Self {
32        if len == 0 {
33            return Self {
34                lead_padding: 0,
35                trailing_padding: 0,
36                prefix: None,
37                chunks: &[],
38                suffix: None,
39            };
40        }
41
42        let byte_offset = offset / 8;
43        let offset_padding = offset % 8;
44
45        let bytes_len = (len + offset_padding).div_ceil(8);
46        let buffer = &buffer[byte_offset..byte_offset + bytes_len];
47
48        let prefix_mask = compute_prefix_mask(offset_padding);
49
50        // If less than 8 bytes, read into prefix
51        if buffer.len() <= 8 {
52            let (suffix_mask, trailing_padding) = compute_suffix_mask(len, offset_padding);
53            let prefix = read_u64(buffer) & suffix_mask & prefix_mask;
54
55            return Self {
56                lead_padding: offset_padding,
57                trailing_padding,
58                prefix: Some(prefix),
59                chunks: &[],
60                suffix: None,
61            };
62        }
63
64        // If less than 16 bytes, read into prefix and suffix
65        if buffer.len() <= 16 {
66            let (suffix_mask, trailing_padding) = compute_suffix_mask(len, offset_padding);
67            let prefix = read_u64(&buffer[..8]) & prefix_mask;
68            let suffix = read_u64(&buffer[8..]) & suffix_mask;
69
70            return Self {
71                lead_padding: offset_padding,
72                trailing_padding,
73                prefix: Some(prefix),
74                chunks: &[],
75                suffix: Some(suffix),
76            };
77        }
78
79        // Read into prefix and suffix as needed
80        // Safety: u64 has no invalid bit patterns so reinterpreting initialized u8 bytes as u64 is sound.
81        let (prefix, mut chunks, suffix) = unsafe { buffer.align_to::<u64>() };
82        assert!(
83            prefix.len() < 8 && suffix.len() < 8,
84            "align_to did not return largest possible aligned slice"
85        );
86
87        let (alignment_padding, prefix) = match (offset_padding, prefix.is_empty()) {
88            (0, true) => (0, None),
89            (_, true) => {
90                let prefix = chunks[0] & prefix_mask;
91                chunks = &chunks[1..];
92                (0, Some(prefix))
93            }
94            (_, false) => {
95                let alignment_padding = (8 - prefix.len()) * 8;
96
97                let prefix = (read_u64(prefix) & prefix_mask) << alignment_padding;
98                (alignment_padding, Some(prefix))
99            }
100        };
101
102        let lead_padding = offset_padding + alignment_padding;
103        let (suffix_mask, trailing_padding) = compute_suffix_mask(len, lead_padding);
104
105        let suffix = match (trailing_padding, suffix.is_empty()) {
106            (0, _) => None,
107            (_, true) => {
108                let suffix = chunks[chunks.len() - 1] & suffix_mask;
109                chunks = &chunks[..chunks.len() - 1];
110                Some(suffix)
111            }
112            (_, false) => Some(read_u64(suffix) & suffix_mask),
113        };
114
115        Self {
116            lead_padding,
117            trailing_padding,
118            prefix,
119            chunks,
120            suffix,
121        }
122    }
123
124    /// Returns the number of leading padding bits
125    pub fn lead_padding(&self) -> usize {
126        self.lead_padding
127    }
128
129    /// Returns the number of trailing padding bits
130    pub fn trailing_padding(&self) -> usize {
131        self.trailing_padding
132    }
133
134    /// Returns the prefix, if any
135    pub fn prefix(&self) -> Option<u64> {
136        self.prefix
137    }
138
139    /// Returns the suffix, if any
140    pub fn suffix(&self) -> Option<u64> {
141        self.suffix
142    }
143
144    /// Returns reference to the chunks
145    pub fn chunks(&self) -> &'a [u64] {
146        self.chunks
147    }
148
149    /// Returns an iterator over the chunks
150    #[inline]
151    pub fn iter(&self) -> UnalignedBitChunkIterator<'a> {
152        self.prefix
153            .into_iter()
154            .chain(self.chunks.iter().copied())
155            .chain(self.suffix)
156    }
157
158    /// Counts the number of ones
159    pub fn count_ones(&self) -> usize {
160        let edges = self.prefix.into_iter().chain(self.suffix);
161        edges.map(|x| x.count_ones() as usize).sum::<usize>() + count_ones_words(self.chunks)
162    }
163}
164
165#[cfg(not(target_arch = "aarch64"))]
166fn count_ones_words(words: &[u64]) -> usize {
167    words.iter().map(|x| x.count_ones() as usize).sum()
168}
169
170/// Summing four byte popcounts in `u8` lanes before widening lets LLVM emit one
171/// widening per 64-byte block. A `u64::count_ones` sum widens every 16 bytes. On x86
172/// the `u64` sum measured faster (#11776), so this is only used on aarch64.
173#[cfg(target_arch = "aarch64")]
174fn count_ones_words(words: &[u64]) -> usize {
175    // A block is 8 words (64 bytes), the unit that is widened once.
176    let (blocks, tail) = words.as_chunks::<8>();
177    let mut total = 0;
178    // `lane_counts` counts in u16 lanes so that one widening per block suffices. Each
179    // lane gains at most 32 (four bytes of eight bits) per block, so flush the lanes
180    // (add them into `total` and reset them) before they can overflow.
181    const BLOCKS_PER_FLUSH: usize = (u16::MAX / 32) as usize;
182    for flush_group in blocks.chunks(BLOCKS_PER_FLUSH) {
183        let mut lane_counts = [0u16; 16];
184        for block in flush_group {
185            let bytes = block.as_slice().to_byte_slice();
186            // Lane `lane` sums byte `lane` of each of the block's four 16-byte vectors.
187            for lane in 0..16 {
188                let count = bytes[lane].count_ones() as u8
189                    + bytes[16 + lane].count_ones() as u8
190                    + bytes[32 + lane].count_ones() as u8
191                    + bytes[48 + lane].count_ones() as u8;
192                lane_counts[lane] += count as u16;
193            }
194        }
195        total += lane_counts.iter().copied().map(usize::from).sum::<usize>();
196    }
197    // Counting the tail in words avoids widening each byte popcount to u64.
198    total + tail.iter().map(|w| w.count_ones() as usize).sum::<usize>()
199}
200
201impl<'a> IntoIterator for &UnalignedBitChunk<'a> {
202    type Item = u64;
203    type IntoIter = UnalignedBitChunkIterator<'a>;
204
205    fn into_iter(self) -> Self::IntoIter {
206        self.iter()
207    }
208}
209
210/// Iterator over an [`UnalignedBitChunk`]
211pub type UnalignedBitChunkIterator<'a> = std::iter::Chain<
212    std::iter::Chain<std::option::IntoIter<u64>, std::iter::Copied<std::slice::Iter<'a, u64>>>,
213    std::option::IntoIter<u64>,
214>;
215
216#[inline]
217fn read_u64(input: &[u8]) -> u64 {
218    let len = input.len().min(8);
219    let mut buf = [0_u8; 8];
220    buf[..len].copy_from_slice(input);
221    u64::from_le_bytes(buf)
222}
223
224#[inline]
225fn compute_prefix_mask(lead_padding: usize) -> u64 {
226    !((1 << lead_padding) - 1)
227}
228
229#[inline]
230fn compute_suffix_mask(len: usize, lead_padding: usize) -> (u64, usize) {
231    let trailing_bits = (len + lead_padding) % 64;
232
233    if trailing_bits == 0 {
234        return (u64::MAX, 0);
235    }
236
237    let trailing_padding = 64 - trailing_bits;
238    let suffix_mask = (1 << trailing_bits) - 1;
239    (suffix_mask, trailing_padding)
240}
241
242/// Iterates over an arbitrarily aligned byte buffer 64 bits at a time
243///
244/// [`Self::iter`] yields iterator of `u64`, and a remainder. The first byte in the buffer
245/// will be the least significant byte in output u64
246#[derive(Debug)]
247pub struct BitChunks<'a> {
248    buffer: &'a [u8],
249    /// offset inside a byte, guaranteed to be between 0 and 7 (inclusive)
250    bit_offset: usize,
251    /// number of complete u64 chunks
252    chunk_len: usize,
253    /// number of remaining bits, guaranteed to be between 0 and 63 (inclusive)
254    remainder_len: usize,
255}
256
257impl<'a> BitChunks<'a> {
258    /// Create a new [`BitChunks`] from a byte array, and an offset and length in bits
259    pub fn new(buffer: &'a [u8], offset: usize, len: usize) -> Self {
260        let end = offset.checked_add(len).expect("offset + len out of bounds");
261        assert!(ceil(end, 8) <= buffer.len(), "offset + len out of bounds");
262
263        let byte_offset = offset / 8;
264        let bit_offset = offset % 8;
265
266        // number of complete u64 chunks
267        let chunk_len = len / 64;
268        // number of remaining bits
269        let remainder_len = len % 64;
270
271        BitChunks::<'a> {
272            buffer: &buffer[byte_offset..],
273            bit_offset,
274            chunk_len,
275            remainder_len,
276        }
277    }
278}
279
280/// Iterator over chunks of 64 bits represented as an u64
281#[derive(Debug)]
282pub struct BitChunkIterator<'a> {
283    buffer: &'a [u8],
284    bit_offset: usize,
285    chunk_len: usize,
286    index: usize,
287}
288
289impl<'a> BitChunks<'a> {
290    /// Returns the number of remaining bits, guaranteed to be between 0 and 63 (inclusive)
291    #[inline]
292    pub const fn remainder_len(&self) -> usize {
293        self.remainder_len
294    }
295
296    /// Returns the number of `u64` chunks
297    #[inline]
298    pub const fn chunk_len(&self) -> usize {
299        self.chunk_len
300    }
301
302    /// Returns the bitmask of remaining bits
303    #[inline]
304    pub fn remainder_bits(&self) -> u64 {
305        let bit_len = self.remainder_len;
306        if bit_len == 0 {
307            0
308        } else {
309            let bit_offset = self.bit_offset;
310            // number of bytes to read
311            // might be one more than sizeof(u64) if the offset is in the middle of a byte
312            let byte_len = ceil(bit_len + bit_offset, 8);
313            // pointer to remainder bytes after all complete chunks
314            // Safety: the buffer contains `chunk_len * 8 + ceil(remainder_len + bit_offset, 8)`
315            // bytes, so offsetting by `chunk_len * 8` and reading `byte_len` bytes is in-bounds.
316            let base = unsafe {
317                self.buffer
318                    .as_ptr()
319                    .add(self.chunk_len * std::mem::size_of::<u64>())
320            };
321
322            let mut bits = unsafe { std::ptr::read(base) } as u64 >> bit_offset;
323            for i in 1..byte_len {
324                let byte = unsafe { std::ptr::read(base.add(i)) };
325                bits |= (byte as u64) << (i * 8 - bit_offset);
326            }
327
328            bits & ((1 << bit_len) - 1)
329        }
330    }
331
332    /// Return the number of `u64` that are needed to represent all bits
333    /// (including remainder).
334    ///
335    /// This is equal to `chunk_len + 1` if there is a remainder,
336    /// otherwise it is equal to `chunk_len`.
337    #[inline]
338    pub fn num_u64s(&self) -> usize {
339        if self.remainder_len == 0 {
340            self.chunk_len
341        } else {
342            self.chunk_len + 1
343        }
344    }
345
346    /// Return the number of *bytes* that are needed to represent all bits
347    /// (including remainder).
348    #[inline]
349    pub fn num_bytes(&self) -> usize {
350        ceil(self.chunk_len * 64 + self.remainder_len, 8)
351    }
352
353    /// Returns the `index`th complete chunk of 64 bits, the value
354    /// [`Self::iter`] yields at that position
355    ///
356    /// # Panics
357    ///
358    /// Panics if `index >= self.chunk_len()`
359    ///
360    /// # Example
361    ///
362    /// ```
363    /// # use arrow_buffer::Buffer;
364    /// let buffer = Buffer::from((0..17_u8).collect::<Vec<_>>());
365    /// // Start at bit 8, so chunk 1 holds bytes 9 through 16
366    /// let chunks = buffer.bit_chunks(8, 128);
367    /// assert_eq!(chunks.chunk_len(), 2);
368    /// assert_eq!(chunks.chunk(1), 0x100f0e0d0c0b0a09);
369    /// assert_eq!(chunks.iter().nth(1), Some(chunks.chunk(1)));
370    /// ```
371    #[inline]
372    pub fn chunk(&self, index: usize) -> u64 {
373        assert!(index < self.chunk_len, "chunk index out of bounds");
374        // Safety: `index < chunk_len`, and the constructor checked the buffer
375        // covers every complete chunk plus the remainder byte
376        unsafe { read_chunk(self.buffer, self.bit_offset, index) }
377    }
378
379    /// Returns an iterator over chunks of 64 bits represented as an `u64`
380    #[inline]
381    pub const fn iter(&self) -> BitChunkIterator<'a> {
382        BitChunkIterator::<'a> {
383            buffer: self.buffer,
384            bit_offset: self.bit_offset,
385            chunk_len: self.chunk_len,
386            index: 0,
387        }
388    }
389
390    /// Returns an iterator over chunks of 64 bits, with the remaining bits zero padded to 64-bits
391    #[inline]
392    pub fn iter_padded(&self) -> impl Iterator<Item = u64> + 'a {
393        self.iter().chain(std::iter::once(self.remainder_bits()))
394    }
395}
396
397impl<'a> IntoIterator for BitChunks<'a> {
398    type Item = u64;
399    type IntoIter = BitChunkIterator<'a>;
400
401    fn into_iter(self) -> Self::IntoIter {
402        self.iter()
403    }
404}
405
406impl<'a> IntoIterator for &BitChunks<'a> {
407    type Item = u64;
408    type IntoIter = BitChunkIterator<'a>;
409
410    fn into_iter(self) -> Self::IntoIter {
411        self.iter()
412    }
413}
414
415/// Reads the `index`th complete 64-bit chunk of `buffer`, whose bits start
416/// at `bit_offset` (in `0..8`)
417///
418/// # Safety
419///
420/// `index` must be less than the number of complete chunks, so that the
421/// buffer holds at least `index * 8 + 8` bytes, plus one more byte when
422/// `bit_offset != 0` (the remainder byte the constructor guarantees)
423#[inline]
424unsafe fn read_chunk(buffer: &[u8], bit_offset: usize, index: usize) -> u64 {
425    debug_assert!(bit_offset < 8);
426    debug_assert!(buffer.len() >= index * 8 + 8 + usize::from(bit_offset != 0));
427    // cast to *const u64 should be fine since we are using read_unaligned below
428    #[expect(clippy::cast_ptr_alignment)]
429    let raw_data = buffer.as_ptr().cast::<u64>();
430
431    // bit-packed buffers are stored starting with the least-significant byte first
432    // so when reading as u64 on a big-endian machine, the bytes need to be swapped
433    // Safety: the caller guarantees `raw_data.add(index)` is in bounds;
434    // `read_unaligned` handles any pointer alignment.
435    let current = unsafe { std::ptr::read_unaligned(raw_data.add(index)).to_le() };
436
437    if bit_offset == 0 {
438        current
439    } else {
440        // the constructor ensures that bit_offset is in 0..8
441        // that means we need to read at most one additional byte to fill in the high bits
442        // Safety: the caller guarantees the byte at `index + 1` is in bounds
443        let next = unsafe { std::ptr::read_unaligned(raw_data.add(index + 1).cast::<u8>()) as u64 };
444
445        (current >> bit_offset) | (next << (64 - bit_offset))
446    }
447}
448
449impl Iterator for BitChunkIterator<'_> {
450    type Item = u64;
451
452    #[inline]
453    fn next(&mut self) -> Option<u64> {
454        let index = self.index;
455        if index >= self.chunk_len {
456            return None;
457        }
458
459        // Safety: `index < self.chunk_len`, and the constructor checked the
460        // buffer covers every complete chunk plus the remainder byte
461        let combined = unsafe { read_chunk(self.buffer, self.bit_offset, index) };
462
463        self.index = index + 1;
464
465        Some(combined)
466    }
467
468    #[inline]
469    fn size_hint(&self) -> (usize, Option<usize>) {
470        (
471            self.chunk_len - self.index,
472            Some(self.chunk_len - self.index),
473        )
474    }
475}
476
477impl ExactSizeIterator for BitChunkIterator<'_> {
478    #[inline]
479    fn len(&self) -> usize {
480        self.chunk_len - self.index
481    }
482}
483
484#[cfg(test)]
485mod tests {
486    use rand::distr::uniform::UniformSampler;
487    use rand::distr::uniform::UniformUsize;
488    use rand::prelude::*;
489    use rand::rng;
490
491    use crate::buffer::Buffer;
492    use crate::util::bit_chunk_iterator::UnalignedBitChunk;
493    use crate::util::bit_util::get_bit;
494
495    #[test]
496    fn test_iter_aligned() {
497        let input: &[u8] = &[0, 1, 2, 3, 4, 5, 6, 7];
498        let buffer: Buffer = Buffer::from(input);
499
500        let bitchunks = buffer.bit_chunks(0, 64);
501        let result = bitchunks.into_iter().collect::<Vec<_>>();
502
503        assert_eq!(vec![0x0706050403020100], result);
504    }
505
506    #[test]
507    fn test_iter_unaligned() {
508        let input: &[u8] = &[
509            0b00000000, 0b00000001, 0b00000010, 0b00000100, 0b00001000, 0b00010000, 0b00100000,
510            0b01000000, 0b11111111,
511        ];
512        let buffer: Buffer = Buffer::from(input);
513
514        let bitchunks = buffer.bit_chunks(4, 64);
515
516        assert_eq!(0, bitchunks.remainder_len());
517        assert_eq!(0, bitchunks.remainder_bits());
518
519        let result = bitchunks.into_iter().collect::<Vec<_>>();
520
521        assert_eq!(
522            vec![0b1111010000000010000000010000000010000000010000000010000000010000],
523            result
524        );
525    }
526
527    #[test]
528    fn test_iter_unaligned_remainder_1_byte() {
529        let input: &[u8] = &[
530            0b00000000, 0b00000001, 0b00000010, 0b00000100, 0b00001000, 0b00010000, 0b00100000,
531            0b01000000, 0b11111111,
532        ];
533        let buffer: Buffer = Buffer::from(input);
534
535        let bitchunks = buffer.bit_chunks(4, 66);
536
537        assert_eq!(2, bitchunks.remainder_len());
538        assert_eq!(0b00000011, bitchunks.remainder_bits());
539
540        let result = bitchunks.into_iter().collect::<Vec<_>>();
541
542        assert_eq!(
543            vec![0b1111010000000010000000010000000010000000010000000010000000010000],
544            result
545        );
546    }
547
548    #[test]
549    fn test_iter_unaligned_remainder_bits_across_bytes() {
550        let input: &[u8] = &[0b00111111, 0b11111100];
551        let buffer: Buffer = Buffer::from(input);
552
553        // remainder contains bits from both bytes
554        // result should be the highest 2 bits from first byte followed by lowest 5 bits of second bytes
555        let bitchunks = buffer.bit_chunks(6, 7);
556
557        assert_eq!(7, bitchunks.remainder_len());
558        assert_eq!(0b1110000, bitchunks.remainder_bits());
559    }
560
561    #[test]
562    fn test_iter_unaligned_remainder_bits_large() {
563        let input: &[u8] = &[
564            0b11111111, 0b00000000, 0b11111111, 0b00000000, 0b11111111, 0b00000000, 0b11111111,
565            0b00000000, 0b11111111,
566        ];
567        let buffer: Buffer = Buffer::from(input);
568
569        let bitchunks = buffer.bit_chunks(2, 63);
570
571        assert_eq!(63, bitchunks.remainder_len());
572        assert_eq!(
573            0b100_0000_0011_1111_1100_0000_0011_1111_1100_0000_0011_1111_1100_0000_0011_1111,
574            bitchunks.remainder_bits()
575        );
576    }
577
578    #[test]
579    fn test_chunk_aligned() {
580        let input: Vec<u8> = (0..24).collect();
581        let buffer = Buffer::from(input);
582
583        let bitchunks = buffer.bit_chunks(0, 24 * 8);
584        assert_eq!(3, bitchunks.chunk_len());
585        assert_eq!(0x0706050403020100, bitchunks.chunk(0));
586        assert_eq!(0x0f0e0d0c0b0a0908, bitchunks.chunk(1));
587        assert_eq!(0x1716151413121110, bitchunks.chunk(2));
588    }
589
590    #[test]
591    fn test_chunk_matches_iter() {
592        // 26 bytes cover three complete chunks at every offset below, with
593        // the last one needing the byte after its eight when the bit offset
594        // is not zero
595        let input: Vec<u8> = (0..26_u8).map(|i| i.wrapping_mul(13)).collect();
596        let buffer = Buffer::from(input);
597
598        // Bit offsets within a byte and across one, lengths ending on and
599        // off a word boundary
600        for offset in (0..8).chain([8, 13]) {
601            for len in [64, 65, 128, 130, 191, 192] {
602                let bitchunks = buffer.bit_chunks(offset, len);
603                assert_eq!(len / 64, bitchunks.chunk_len());
604                for index in 0..bitchunks.chunk_len() {
605                    assert_eq!(
606                        bitchunks.iter().nth(index),
607                        Some(bitchunks.chunk(index)),
608                        "offset {offset} len {len} chunk {index}"
609                    );
610                }
611            }
612        }
613    }
614
615    #[test]
616    #[should_panic(expected = "chunk index out of bounds")]
617    fn test_chunk_out_of_bounds() {
618        let buffer = Buffer::from(vec![0xFF_u8; 16]);
619        let bitchunks = buffer.bit_chunks(0, 128);
620        assert_eq!(2, bitchunks.chunk_len());
621        bitchunks.chunk(2);
622    }
623
624    #[test]
625    #[should_panic(expected = "chunk index out of bounds")]
626    fn test_chunk_out_of_bounds_no_complete_chunk() {
627        let buffer = Buffer::from(vec![0xFF_u8; 8]);
628        let bitchunks = buffer.bit_chunks(1, 63);
629        assert_eq!(0, bitchunks.chunk_len());
630        bitchunks.chunk(0);
631    }
632
633    #[test]
634    fn test_iter_remainder_out_of_bounds() {
635        // allocating a full page should trigger a fault when reading out of bounds
636        const ALLOC_SIZE: usize = 4 * 1024;
637        let input = vec![0xFF_u8; ALLOC_SIZE];
638
639        let buffer: Buffer = Buffer::from_vec(input);
640
641        let bitchunks = buffer.bit_chunks(57, ALLOC_SIZE * 8 - 57);
642
643        assert_eq!(u64::MAX, bitchunks.iter().last().unwrap());
644        assert_eq!(0x7F, bitchunks.remainder_bits());
645    }
646
647    #[test]
648    #[should_panic(expected = "offset + len out of bounds")]
649    fn test_out_of_bound_should_panic_length_is_more_than_buffer_length() {
650        const ALLOC_SIZE: usize = 4 * 1024;
651        let input = vec![0xFF_u8; ALLOC_SIZE];
652
653        let buffer: Buffer = Buffer::from_vec(input);
654
655        // We are reading more than exists in the buffer
656        buffer.bit_chunks(0, (ALLOC_SIZE + 1) * 8);
657    }
658
659    #[test]
660    #[should_panic(expected = "offset + len out of bounds")]
661    fn test_out_of_bound_should_panic_length_is_more_than_buffer_length_but_not_when_not_using_ceil()
662     {
663        const ALLOC_SIZE: usize = 4 * 1024;
664        let input = vec![0xFF_u8; ALLOC_SIZE];
665
666        let buffer: Buffer = Buffer::from_vec(input);
667
668        // We are reading more than exists in the buffer
669        buffer.bit_chunks(0, (ALLOC_SIZE * 8) + 1);
670    }
671
672    #[test]
673    #[should_panic(expected = "offset + len out of bounds")]
674    fn test_out_of_bound_should_panic_when_offset_is_not_zero_and_length_is_the_entire_buffer_length()
675     {
676        const ALLOC_SIZE: usize = 4 * 1024;
677        let input = vec![0xFF_u8; ALLOC_SIZE];
678
679        let buffer: Buffer = Buffer::from_vec(input);
680
681        // We are reading more than exists in the buffer
682        buffer.bit_chunks(8, ALLOC_SIZE * 8);
683    }
684
685    #[test]
686    #[should_panic(expected = "offset + len out of bounds")]
687    fn test_out_of_bound_should_panic_when_offset_is_not_zero_and_length_is_the_entire_buffer_length_with_ceil()
688     {
689        const ALLOC_SIZE: usize = 4 * 1024;
690        let input = vec![0xFF_u8; ALLOC_SIZE];
691
692        let buffer: Buffer = Buffer::from_vec(input);
693
694        // We are reading more than exists in the buffer
695        buffer.bit_chunks(1, ALLOC_SIZE * 8);
696    }
697
698    #[test]
699    #[should_panic(expected = "offset + len out of bounds")]
700    fn test_out_of_bound_should_panic_when_offset_and_length_overflow() {
701        let buffer = Buffer::from(vec![0xFF_u8; 8]);
702        buffer.bit_chunks(1, usize::MAX);
703    }
704
705    #[test]
706    fn test_unaligned_bit_chunk_iterator() {
707        let buffer = Buffer::from(&[0xFF; 5]);
708        let unaligned = UnalignedBitChunk::new(buffer.as_slice(), 0, 40);
709
710        assert!(unaligned.chunks().is_empty()); // Less than 128 elements
711        assert_eq!(unaligned.lead_padding(), 0);
712        assert_eq!(unaligned.trailing_padding(), 24);
713        // 24x 1 bit then 40x 0 bits
714        assert_eq!(
715            unaligned.prefix(),
716            Some(0b0000000000000000000000001111111111111111111111111111111111111111)
717        );
718        assert_eq!(unaligned.suffix(), None);
719
720        let buffer = buffer.slice(1);
721        let unaligned = UnalignedBitChunk::new(buffer.as_slice(), 0, 32);
722
723        assert!(unaligned.chunks().is_empty()); // Less than 128 elements
724        assert_eq!(unaligned.lead_padding(), 0);
725        assert_eq!(unaligned.trailing_padding(), 32);
726        // 32x 1 bit then 32x 0 bits
727        assert_eq!(
728            unaligned.prefix(),
729            Some(0b0000000000000000000000000000000011111111111111111111111111111111)
730        );
731        assert_eq!(unaligned.suffix(), None);
732
733        let unaligned = UnalignedBitChunk::new(buffer.as_slice(), 5, 27);
734
735        assert!(unaligned.chunks().is_empty()); // Less than 128 elements
736        assert_eq!(unaligned.lead_padding(), 5); // 5 % 8 == 5
737        assert_eq!(unaligned.trailing_padding(), 32);
738        // 5x 0 bit, 27x 1 bit then 32x 0 bits
739        assert_eq!(
740            unaligned.prefix(),
741            Some(0b0000000000000000000000000000000011111111111111111111111111100000)
742        );
743        assert_eq!(unaligned.suffix(), None);
744
745        let unaligned = UnalignedBitChunk::new(buffer.as_slice(), 12, 20);
746
747        assert!(unaligned.chunks().is_empty()); // Less than 128 elements
748        assert_eq!(unaligned.lead_padding(), 4); // 12 % 8 == 4
749        assert_eq!(unaligned.trailing_padding(), 40);
750        // 4x 0 bit, 20x 1 bit then 40x 0 bits
751        assert_eq!(
752            unaligned.prefix(),
753            Some(0b0000000000000000000000000000000000000000111111111111111111110000)
754        );
755        assert_eq!(unaligned.suffix(), None);
756
757        let buffer = Buffer::from(&[0xFF; 14]);
758
759        // Verify buffer alignment
760        let (prefix, aligned, suffix) = unsafe { buffer.as_slice().align_to::<u64>() };
761        assert_eq!(prefix.len(), 0);
762        assert_eq!(aligned.len(), 1);
763        assert_eq!(suffix.len(), 6);
764
765        let unaligned = UnalignedBitChunk::new(buffer.as_slice(), 0, 112);
766
767        assert!(unaligned.chunks().is_empty()); // Less than 128 elements
768        assert_eq!(unaligned.lead_padding(), 0); // No offset and buffer aligned on 64-bit boundary
769        assert_eq!(unaligned.trailing_padding(), 16);
770        assert_eq!(unaligned.prefix(), Some(u64::MAX));
771        assert_eq!(unaligned.suffix(), Some((1 << 48) - 1));
772
773        let buffer = Buffer::from(&[0xFF; 16]);
774
775        // Verify buffer alignment
776        let (prefix, aligned, suffix) = unsafe { buffer.as_slice().align_to::<u64>() };
777        assert_eq!(prefix.len(), 0);
778        assert_eq!(aligned.len(), 2);
779        assert_eq!(suffix.len(), 0);
780
781        let unaligned = UnalignedBitChunk::new(buffer.as_slice(), 0, 128);
782
783        assert_eq!(unaligned.prefix(), Some(u64::MAX));
784        assert_eq!(unaligned.suffix(), Some(u64::MAX));
785        assert!(unaligned.chunks().is_empty()); // Exactly 128 elements
786
787        let buffer = Buffer::from(&[0xFF; 64]);
788
789        // Verify buffer alignment
790        let (prefix, aligned, suffix) = unsafe { buffer.as_slice().align_to::<u64>() };
791        assert_eq!(prefix.len(), 0);
792        assert_eq!(aligned.len(), 8);
793        assert_eq!(suffix.len(), 0);
794
795        let unaligned = UnalignedBitChunk::new(buffer.as_slice(), 0, 512);
796
797        // Buffer is completely aligned and larger than 128 elements -> all in chunks array
798        assert_eq!(unaligned.suffix(), None);
799        assert_eq!(unaligned.prefix(), None);
800        assert_eq!(unaligned.chunks(), [u64::MAX; 8].as_slice());
801        assert_eq!(unaligned.lead_padding(), 0);
802        assert_eq!(unaligned.trailing_padding(), 0);
803
804        let buffer = buffer.slice(1); // Offset buffer 1 byte off 64-bit alignment
805
806        // Verify buffer alignment
807        let (prefix, aligned, suffix) = unsafe { buffer.as_slice().align_to::<u64>() };
808        assert_eq!(prefix.len(), 7);
809        assert_eq!(aligned.len(), 7);
810        assert_eq!(suffix.len(), 0);
811
812        let unaligned = UnalignedBitChunk::new(buffer.as_slice(), 0, 504);
813
814        // Need a prefix with 1 byte of lead padding to bring the buffer into alignment
815        assert_eq!(unaligned.prefix(), Some(u64::MAX - 0xFF));
816        assert_eq!(unaligned.suffix(), None);
817        assert_eq!(unaligned.chunks(), [u64::MAX; 7].as_slice());
818        assert_eq!(unaligned.lead_padding(), 8);
819        assert_eq!(unaligned.trailing_padding(), 0);
820
821        let unaligned = UnalignedBitChunk::new(buffer.as_slice(), 17, 300);
822
823        // Out of 64-bit alignment by 8 bits from buffer, and 17 bits from provided offset
824        //   => need 8 + 17 = 25 bits of lead padding + 39 bits in prefix
825        //
826        // This leaves 300 - 17 = 261 bits remaining
827        //   => 4x 64-bit aligned 64-bit chunks + 5 remaining bits
828        //   => trailing padding of 59 bits
829        assert_eq!(unaligned.lead_padding(), 25);
830        assert_eq!(unaligned.trailing_padding(), 59);
831        assert_eq!(unaligned.prefix(), Some(u64::MAX - (1 << 25) + 1));
832        assert_eq!(unaligned.suffix(), Some(0b11111));
833        assert_eq!(unaligned.chunks(), [u64::MAX; 4].as_slice());
834
835        let unaligned = UnalignedBitChunk::new(buffer.as_slice(), 17, 0);
836
837        assert_eq!(unaligned.prefix(), None);
838        assert_eq!(unaligned.suffix(), None);
839        assert!(unaligned.chunks().is_empty());
840        assert_eq!(unaligned.lead_padding(), 0);
841        assert_eq!(unaligned.trailing_padding(), 0);
842
843        let unaligned = UnalignedBitChunk::new(buffer.as_slice(), 17, 1);
844
845        assert_eq!(unaligned.prefix(), Some(2));
846        assert_eq!(unaligned.suffix(), None);
847        assert!(unaligned.chunks().is_empty());
848        assert_eq!(unaligned.lead_padding(), 1);
849        assert_eq!(unaligned.trailing_padding(), 62);
850    }
851
852    #[test]
853    fn test_unaligned_bit_chunk_count_ones() {
854        // Sizes in bytes around the 64-byte block and the 2047-block flush in
855        // `count_ones_words`. With all-ones input, this fails if the flush comes too
856        // late and a u16 lane counter overflows. Random input (`None`) fails if a
857        // lane counts the wrong bytes, which uniform input hides.
858        let sizes = [
859            0, 1, 7, 8, 63, 64, 65, 72, 136, 131_008, 131_072, 131_136, 131_207,
860        ];
861        let mut rng = StdRng::seed_from_u64(42);
862        for size in sizes {
863            for byte in [Some(0xFF_u8), Some(0xA5), Some(0x00), None] {
864                let bytes = match byte {
865                    Some(byte) => vec![byte; size],
866                    None => (0..size).map(|_| rng.random()).collect(),
867                };
868                let buffer = Buffer::from(bytes);
869                let bits = size * 8;
870                for offset in [0, 3.min(bits), 64.min(bits)] {
871                    let len = bits - offset;
872                    let unaligned = UnalignedBitChunk::new(buffer.as_slice(), offset, len);
873                    let expected = (offset..bits)
874                        .filter(|i| get_bit(buffer.as_slice(), *i))
875                        .count();
876                    assert_eq!(
877                        unaligned.count_ones(),
878                        expected,
879                        "{size} {byte:#x?} {offset}"
880                    );
881                }
882            }
883        }
884    }
885
886    #[test]
887    fn fuzz_unaligned_bit_chunk_iterator() {
888        let mut rng = rng();
889
890        let uusize = UniformUsize::new(usize::MIN, usize::MAX).unwrap();
891        for _ in 0..100 {
892            let mask_len = rng.random_range(0..1024);
893            let bools: Vec<_> = std::iter::from_fn(|| Some(rng.random()))
894                .take(mask_len)
895                .collect();
896
897            let buffer = Buffer::from_iter(bools.iter().copied());
898
899            let max_offset = 64.min(mask_len);
900            let offset = uusize.sample(&mut rng).checked_rem(max_offset).unwrap_or(0);
901
902            let max_truncate = 128.min(mask_len - offset);
903            let truncate = uusize
904                .sample(&mut rng)
905                .checked_rem(max_truncate)
906                .unwrap_or(0);
907
908            let unaligned =
909                UnalignedBitChunk::new(buffer.as_slice(), offset, mask_len - offset - truncate);
910
911            let bool_slice = &bools[offset..mask_len - truncate];
912
913            let count = unaligned.count_ones();
914            let expected_count = bool_slice.iter().filter(|x| **x).count();
915
916            assert_eq!(count, expected_count);
917
918            let collected: Vec<u64> = unaligned.iter().collect();
919
920            let get_bit = |idx: usize| -> bool {
921                let padded_index = idx + unaligned.lead_padding();
922                let byte_idx = padded_index / 64;
923                let bit_idx = padded_index % 64;
924                (collected[byte_idx] & (1 << bit_idx)) != 0
925            };
926
927            for (idx, b) in bool_slice.iter().enumerate() {
928                assert_eq!(*b, get_bit(idx))
929            }
930        }
931    }
932}