Skip to main content

arrow_buffer/util/
bit_util.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//! Utils for working with bits
6
7use crate::bit_chunk_iterator::BitChunks;
8
9/// Parallel bit extract: for each set bit in `mask`, extract the
10/// corresponding bit from `value` and pack them contiguously into the low
11/// bits of the return value.
12///
13/// Equivalent to the x86 BMI2 `PEXT` instruction. When compiled with the
14/// `bmi2` target feature enabled (for example `-C target-cpu=x86-64-v3`)
15/// this lowers to the hardware `pext` instruction; otherwise it falls back
16/// to a portable version that picks its method by the number of set bits in
17/// the mask.
18///
19/// # Functional Example
20///
21/// Using 8 bits for brevity (the function operates on all 64). Each
22/// set bit in `mask` selects the bit at the same position in `value`; the
23/// selected bits are then shifted down so they are contiguous in the low
24/// bits of the result, in their original order:
25///
26/// ```text
27/// bit:     7 6 5 4 3 2 1 0
28/// value:   a b c d e f g h
29/// mask:    0 1 1 0 1 1 0 1      set bits select b, c, e, f and h
30///            | |   | |   |
31///            v v   v v   v      copy the relevant bits into result
32/// result:  0 0 0 b c e f h
33/// ```
34///
35/// # Code Example
36///
37/// ```
38/// # use arrow_buffer::bit_util::compress;
39/// assert_eq!(compress(0b1011_0100, 0b0110_1101), 0b0000_1010);
40/// ```
41//
42// When `uint_gather_scatter_bits` is stabilised
43// (<https://github.com/rust-lang/rust/issues/149069>), measure
44// `value.extract_bits(mask)` against this before switching. Its portable
45// version runs six shift stages for every mask, with each stage's mask taken
46// from prefix counts of zero bits (Hacker's Delight 7-4, see
47// <https://github.com/rust-lang/rust/blob/main/library/core/src/num/imp/int_bits.rs>).
48// The fallback here does less work on sparse and dense masks, and on x86 also
49// in between (three stages inside each byte plus one multiply, fewer shifts in
50// total); on big AArch64 cores the six-stage version is faster in that middle
51// band.
52#[inline]
53pub fn compress(value: u64, mask: u64) -> u64 {
54    #[cfg(all(target_arch = "x86_64", target_feature = "bmi2"))]
55    {
56        // SAFETY: the `bmi2` target feature is statically enabled for this
57        // build, so the `pext` instruction is guaranteed to be available.
58        unsafe { std::arch::x86_64::_pext_u64(value, mask) }
59    }
60
61    #[cfg(not(all(target_arch = "x86_64", target_feature = "bmi2")))]
62    {
63        compress_portable(value, mask)
64    }
65}
66
67/// [`compress`] without `pext`, by the number of kept bits `k`:
68///
69/// * `k <= 2`: the two lowest kept bits, tested directly
70/// * `k <= 16`: one step per kept bit
71/// * `k >= 62`: `value` with its at most two dropped bits removed
72/// * otherwise [`compress_bytes`]
73///
74/// The two ends need no loop, so no loop exit to mispredict when `k`
75/// varies from word to word.
76// Always: called once a word, so a call would cost more than a sparse word
77#[cfg(any(test, not(all(target_arch = "x86_64", target_feature = "bmi2"))))]
78#[inline(always)]
79fn compress_portable(value: u64, mask: u64) -> u64 {
80    let kept = mask.count_ones();
81    if kept <= 2 {
82        let lowest = mask & mask.wrapping_neg();
83        let second = mask ^ lowest;
84        u64::from(value & lowest != 0) | (u64::from(value & second != 0) << 1)
85    } else if kept <= 16 {
86        let mut mask = mask;
87        let mut result = 0_u64;
88        let mut dest_bit = 1_u64;
89        while mask != 0 {
90            // Clear the lowest set bit; the loop-carried dependency is only
91            // this two-operation chain, everything else hangs off it
92            let rest = mask & (mask - 1);
93            let lowest = mask ^ rest;
94            let keep = ((value & lowest) != 0) as u64;
95            result |= dest_bit & keep.wrapping_neg();
96            dest_bit <<= 1;
97            mask = rest;
98        }
99        result
100    } else if kept >= 62 {
101        if kept == 64 {
102            return value;
103        }
104        // Remove the highest dropped bit first, so the lower ones stay put.
105        // With nothing left to drop a step keeps every bit, and each step
106        // shifts a zero in at the top.
107        let mut value = value;
108        let mut dropped = !mask;
109        for _ in 0..2 {
110            let below = if dropped == 0 {
111                u64::MAX
112            } else {
113                (1 << dropped.ilog2()) - 1
114            };
115            value = (value & below) | ((value >> 1) & !below);
116            dropped &= below;
117        }
118        value
119    } else {
120        compress_bytes(value, mask)
121    }
122}
123
124/// `b` in every byte of a `u64`
125#[cfg(any(test, not(all(target_arch = "x86_64", target_feature = "bmi2"))))]
126const fn repeat_byte(b: u8) -> u64 {
127    b as u64 * 0x0101_0101_0101_0101
128}
129
130/// [`compress`] in constant time, a byte at a time and all bytes at once.
131///
132/// Within a byte each kept bit moves down by the number of dropped bits
133/// below it. Written in binary, that distance is at most 7, so three rounds
134/// move by 1, 2 and 4 the bits whose distance has that bit set (the parallel
135/// suffix network, Hacker's Delight 7-4); shifts are masked to stay within
136/// the byte. Byte `j` then lands at the sum of the kept counts of bytes
137/// `0..j`, all eight sums from one multiply by `0x0101..01`.
138#[cfg(any(test, not(all(target_arch = "x86_64", target_feature = "bmi2"))))]
139#[inline]
140fn compress_bytes(value: u64, mask: u64) -> u64 {
141    let mut packed = value & mask;
142    let mut dropped = !mask;
143    let mut shift = 1;
144    while shift < 8 {
145        // The move mask of this round: the parity of the dropped bits
146        // below each bit, in strides of `shift`
147        let mut move_mask = dropped;
148        let mut step = shift;
149        while step < 8 {
150            move_mask ^= (move_mask << step) & repeat_byte(0xFF << step);
151            step <<= 1;
152        }
153        let moving = packed & move_mask;
154        packed ^= moving ^ ((moving >> shift) & repeat_byte(0xFF >> shift));
155        dropped &= !move_mask;
156        dropped ^= (dropped >> shift) & repeat_byte(0xFF >> shift);
157        shift <<= 1;
158    }
159    // Kept bits per byte (SWAR popcount, HD 5-1)
160    let pairs = mask - ((mask >> 1) & repeat_byte(0x55));
161    let nibbles = (pairs & repeat_byte(0x33)) + ((pairs >> 2) & repeat_byte(0x33));
162    let kept = (nibbles + (nibbles >> 4)) & repeat_byte(0x0F);
163    // Where byte `j` lands: the kept bits of bytes 0..j, all eight at once
164    let dest = kept.wrapping_mul(repeat_byte(1)) << 8;
165    let mut result = 0;
166    for j in 0..8 {
167        result |= ((packed >> (8 * j)) & 0xFF) << ((dest >> (8 * j)) & 0xFF);
168    }
169    result
170}
171
172/// Parallel bit deposit: scatter the lowest `mask.count_ones()` bits of
173/// `value` into the set positions of `mask`, preserving their order.
174/// All other bits in the result are zero; excess input bits are ignored.
175///
176/// This is the inverse of [`compress`] on the selected bits:
177/// `expand(compress(value, mask), mask) == value & mask`.
178///
179/// Equivalent to the x86 BMI2 `PDEP` instruction. When compiled with the
180/// `bmi2` target feature enabled (for example `-C target-cpu=x86-64-v3`)
181/// this lowers to the hardware `pdep` instruction; otherwise it falls back
182/// to a portable scalar loop that visits whichever is fewer: unset or set
183/// bits in `mask`.
184///
185/// # Functional Example
186///
187/// Using 8 bits for brevity (the function operates on all 64). The low bits
188/// of `value` are scattered into the set positions of `mask`:
189///
190/// ```text
191/// bit:     7 6 5 4 3 2 1 0
192/// value:   0 0 0 b c e f h
193/// mask:    0 1 1 0 1 1 0 1
194/// result:  0 b c 0 e f 0 h
195/// ```
196///
197/// # Code Example
198///
199/// ```
200/// # use arrow_buffer::bit_util::{compress, expand};
201/// assert_eq!(expand(0b0000_1010, 0b0110_1101), 0b0010_0100);
202/// let value = 0b1011_0100;
203/// let mask = 0b0110_1101;
204/// assert_eq!(expand(compress(value, mask), mask), value & mask);
205/// ```
206#[inline]
207pub fn expand(value: u64, mask: u64) -> u64 {
208    #[cfg(all(target_arch = "x86_64", target_feature = "bmi2"))]
209    {
210        // SAFETY: the `bmi2` target feature is statically enabled for this
211        // build, so the `pdep` instruction is guaranteed to be available.
212        unsafe { std::arch::x86_64::_pdep_u64(value, mask) }
213    }
214
215    #[cfg(not(all(target_arch = "x86_64", target_feature = "bmi2")))]
216    {
217        let mut value = value;
218        if value == 0 {
219            return 0;
220        }
221
222        let mut zeros = !mask;
223        if zeros.count_ones() <= 32 {
224            // Insert zeros from low to high; excess input bits shift out.
225            while zeros != 0 {
226                let lower = (1_u64 << zeros.trailing_zeros()) - 1;
227                value = (value & lower) | ((value & !lower) << 1);
228                zeros &= zeros - 1;
229            }
230            value
231        } else {
232            let mut output = 0;
233            let mut ones = mask;
234            while ones != 0 {
235                output |= (value & 1) << ones.trailing_zeros();
236                value >>= 1;
237                ones &= ones - 1;
238            }
239            output
240        }
241    }
242}
243
244/// Returns the nearest number that is `>=` than `num` and is a multiple of 64
245///
246/// # Panics
247///
248/// Panics if rounding `num` up overflows `usize`
249#[inline]
250pub fn round_upto_multiple_of_64(num: usize) -> usize {
251    num.checked_next_multiple_of(64)
252        .expect("failed to round upto multiple of 64")
253}
254
255/// Returns the nearest multiple of `factor` that is `>=` than `num`. Here `factor` must
256/// be a power of 2.
257///
258/// # Panics
259///
260/// Panics if rounding `num` up overflows `usize`
261pub fn round_upto_power_of_2(num: usize, factor: usize) -> usize {
262    debug_assert!(factor > 0 && factor.is_power_of_two());
263    num.checked_add(factor - 1)
264        .expect("failed to round to next highest power of 2")
265        & !(factor - 1)
266}
267
268/// Returns whether bit at position `i` in `data` is set or not
269///
270/// # Panics
271///
272/// Panics if `i / 8 >= data.len()`
273#[inline]
274pub fn get_bit(data: &[u8], i: usize) -> bool {
275    data[i / 8] & (1 << (i % 8)) != 0
276}
277
278/// Returns whether bit at position `i` in `data` is set or not.
279///
280/// # Safety
281///
282/// Note this doesn't do any bound checking, for performance reason. The caller is
283/// responsible to guarantee that `i` is within bounds.
284#[inline]
285pub unsafe fn get_bit_raw(data: *const u8, i: usize) -> bool {
286    unsafe { (*data.add(i / 8) & (1 << (i % 8))) != 0 }
287}
288
289/// Sets bit at position `i` for `data` to 1
290///
291/// # Panics
292///
293/// Panics if `i / 8 >= data.len()`
294#[inline]
295pub fn set_bit(data: &mut [u8], i: usize) {
296    data[i / 8] |= 1 << (i % 8);
297}
298
299/// Sets bit at position `i` for `data`
300///
301/// # Safety
302///
303/// Note this doesn't do any bound checking, for performance reason. The caller is
304/// responsible to guarantee that `i` is within bounds.
305#[inline]
306pub unsafe fn set_bit_raw(data: *mut u8, i: usize) {
307    unsafe {
308        *data.add(i / 8) |= 1 << (i % 8);
309    }
310}
311
312/// Sets bit at position `i` for `data` to 0
313///
314/// # Panics
315///
316/// Panics if `i / 8 >= data.len()`
317#[inline]
318pub fn unset_bit(data: &mut [u8], i: usize) {
319    data[i / 8] &= !(1 << (i % 8));
320}
321
322/// Sets bit at position `i` for `data` to 0
323///
324/// # Safety
325///
326/// Note this doesn't do any bound checking, for performance reason. The caller is
327/// responsible to guarantee that `i` is within bounds.
328#[inline]
329pub unsafe fn unset_bit_raw(data: *mut u8, i: usize) {
330    unsafe {
331        *data.add(i / 8) &= !(1 << (i % 8));
332    }
333}
334
335/// Returns the ceil of `value`/`divisor`
336#[inline]
337pub fn ceil(value: usize, divisor: usize) -> usize {
338    value.div_ceil(divisor)
339}
340
341/// Read a u64 from a byte slice, padding with zeros if necessary
342#[inline]
343pub(crate) fn read_u64(input: &[u8]) -> u64 {
344    let len = input.len().min(8);
345    let mut buf = [0_u8; 8];
346    buf[..len].copy_from_slice(input);
347    u64::from_le_bytes(buf)
348}
349
350/// Read up to 8 bits from a byte slice starting at a given bit offset.
351///
352/// # Arguments
353///
354/// * `slice` - The byte slice to read from
355/// * `number_of_bits_to_read` - Number of bits to read (must be < 8)
356/// * `bit_offset` - Starting bit offset within the first byte (must be < 8)
357///
358/// # Returns
359///
360/// A `u8` containing the requested bits in the least significant positions
361///
362/// # Panics
363/// - Panics if `number_of_bits_to_read` is 0 or >= 8
364/// - Panics if `bit_offset` is >= 8
365/// - Panics if `slice` is empty or too small to read the requested bits
366///
367#[inline]
368pub(crate) fn read_up_to_byte_from_offset(
369    slice: &[u8],
370    number_of_bits_to_read: usize,
371    bit_offset: usize,
372) -> u8 {
373    assert!(number_of_bits_to_read < 8, "can read up to 8 bits only");
374    assert!(bit_offset < 8, "bit offset must be less than 8");
375    assert_ne!(
376        number_of_bits_to_read, 0,
377        "number of bits to read must be greater than 0"
378    );
379    assert_ne!(slice.len(), 0, "slice must not be empty");
380
381    let number_of_bytes_to_read = ceil(number_of_bits_to_read + bit_offset, 8);
382
383    // number of bytes to read
384    assert!(slice.len() >= number_of_bytes_to_read, "slice is too small");
385
386    let mut bits = slice[0] >> bit_offset;
387    for (i, &byte) in slice
388        .iter()
389        .take(number_of_bytes_to_read)
390        .enumerate()
391        .skip(1)
392    {
393        bits |= byte << (i * 8 - bit_offset);
394    }
395
396    bits & ((1 << number_of_bits_to_read) - 1)
397}
398
399/// Applies a bitwise operation relative to another bit-packed byte slice
400/// (right) in place
401///
402/// Note: applies the operation 64-bits (u64) at a time.
403///
404/// # Arguments
405///
406/// * `left` - The mutable buffer to be modified in-place
407/// * `offset_in_bits` - Starting bit offset in Self buffer
408/// * `right` - slice of bit-packed bytes in LSB order
409/// * `right_offset_in_bits` - Starting bit offset in the right buffer
410/// * `len_in_bits` - Number of bits to process
411/// * `op` - Binary operation to apply (e.g., `|a, b| a & b`). Applied a word at a time
412///
413/// Only the bits in `left_offset_in_bits..left_offset_in_bits + len_in_bits` are
414/// modified. Bits of `left` outside that range are left unchanged, including the
415/// bits sharing a byte with either end of the range.
416///
417/// # Example: Modify entire buffer
418/// ```
419/// # use arrow_buffer::MutableBuffer;
420/// # use arrow_buffer::bit_util::apply_bitwise_binary_op;
421/// let mut left = MutableBuffer::new(2);
422/// left.extend_from_slice(&[0b11110000u8, 0b00110011u8]);
423/// let right = &[0b10101010u8, 0b10101010u8];
424/// // apply bitwise AND between left and right buffers, updating left in place
425/// apply_bitwise_binary_op(left.as_slice_mut(), 0, right, 0, 16, |a, b| a & b);
426/// assert_eq!(left.as_slice(), &[0b10100000u8, 0b00100010u8]);
427/// ```
428///
429/// # Example: Modify buffer with offsets
430/// ```
431/// # use arrow_buffer::MutableBuffer;
432/// # use arrow_buffer::bit_util::apply_bitwise_binary_op;
433/// let mut left = MutableBuffer::new(2);
434/// left.extend_from_slice(&[0b00000000u8, 0b00000000u8]);
435/// let right = &[0b10110011u8, 0b11111110u8];
436/// // apply bitwise OR between left and right buffers,
437/// // Apply only 8 bits starting from bit offset 3 in left and bit offset 2 in right
438/// apply_bitwise_binary_op(left.as_slice_mut(), 3, right, 2, 8, |a, b| a | b);
439/// assert_eq!(left.as_slice(), &[0b01100000, 0b00000101u8]);
440/// ```
441///
442/// # Panics
443///
444/// If the offset or lengths exceed the buffer or slice size.
445pub fn apply_bitwise_binary_op<F>(
446    left: &mut [u8],
447    left_offset_in_bits: usize,
448    right: impl AsRef<[u8]>,
449    right_offset_in_bits: usize,
450    len_in_bits: usize,
451    mut op: F,
452) where
453    F: FnMut(u64, u64) -> u64,
454{
455    if len_in_bits == 0 {
456        return;
457    }
458
459    // offset inside a byte
460    let bit_offset = left_offset_in_bits % 8;
461
462    let is_mutable_buffer_byte_aligned = bit_offset == 0;
463
464    if is_mutable_buffer_byte_aligned {
465        byte_aligned_bitwise_bin_op_helper(
466            left,
467            left_offset_in_bits,
468            right,
469            right_offset_in_bits,
470            len_in_bits,
471            op,
472        );
473    } else {
474        // If we are not byte aligned, run `op` on the first few bits to reach byte alignment
475        let bits_to_next_byte = (8 - bit_offset)
476            // Minimum with the amount of bits we need to process
477            // to avoid reading out of bounds
478            .min(len_in_bits);
479
480        {
481            let right_byte_offset = right_offset_in_bits / 8;
482
483            // Read the same amount of bits from the right buffer
484            let right_first_byte = crate::util::bit_util::read_up_to_byte_from_offset(
485                &right.as_ref()[right_byte_offset..],
486                bits_to_next_byte,
487                // Right bit offset
488                right_offset_in_bits % 8,
489            );
490
491            align_to_byte(
492                left,
493                // Hope it gets inlined
494                &mut |left| op(left, right_first_byte as u64),
495                left_offset_in_bits,
496                bits_to_next_byte,
497            );
498        }
499
500        let offset_in_bits = left_offset_in_bits + bits_to_next_byte;
501        let right_offset_in_bits = right_offset_in_bits + bits_to_next_byte;
502        let len_in_bits = len_in_bits.saturating_sub(bits_to_next_byte);
503
504        if len_in_bits == 0 {
505            return;
506        }
507
508        // We are now byte aligned
509        byte_aligned_bitwise_bin_op_helper(
510            left,
511            offset_in_bits,
512            right,
513            right_offset_in_bits,
514            len_in_bits,
515            op,
516        );
517    }
518}
519
520/// Apply a bitwise operation to a mutable buffer, updating it in place.
521///
522/// Note: applies the operation 64-bits (u64) at a time.
523///
524/// # Arguments
525///
526/// * `offset_in_bits` - Starting bit offset for the current buffer
527/// * `len_in_bits` - Number of bits to process
528/// * `op` - Unary operation to apply (e.g., `|a| !a`). Applied a word at a time
529///
530/// Only the bits in `offset_in_bits..offset_in_bits + len_in_bits` are modified.
531/// Bits outside that range are left unchanged, including the bits sharing a byte
532/// with either end of the range.
533///
534/// # Example: Modify entire buffer
535/// ```
536/// # use arrow_buffer::MutableBuffer;
537/// # use arrow_buffer::bit_util::apply_bitwise_unary_op;
538/// let mut buffer = MutableBuffer::new(2);
539/// buffer.extend_from_slice(&[0b11110000u8, 0b00110011u8]);
540/// // apply bitwise NOT to the buffer in place
541/// apply_bitwise_unary_op(buffer.as_slice_mut(), 0, 16, |a| !a);
542/// assert_eq!(buffer.as_slice(), &[0b00001111u8, 0b11001100u8]);
543/// ```
544///
545/// # Example: Modify buffer with offsets
546/// ```
547/// # use arrow_buffer::MutableBuffer;
548/// # use arrow_buffer::bit_util::apply_bitwise_unary_op;
549/// let mut buffer = MutableBuffer::new(2);
550/// buffer.extend_from_slice(&[0b00000000u8, 0b00000000u8]);
551/// // apply bitwise NOT to 8 bits starting from bit offset 3
552/// apply_bitwise_unary_op(buffer.as_slice_mut(), 3, 8, |a| !a);
553/// assert_eq!(buffer.as_slice(), &[0b11111000u8, 0b00000111u8]);
554/// ```
555///
556/// # Panics
557///
558/// If the offset and length exceed the buffer size.
559pub fn apply_bitwise_unary_op<F>(
560    buffer: &mut [u8],
561    offset_in_bits: usize,
562    len_in_bits: usize,
563    mut op: F,
564) where
565    F: FnMut(u64) -> u64,
566{
567    if len_in_bits == 0 {
568        return;
569    }
570
571    // offset inside a byte
572    let left_bit_offset = offset_in_bits % 8;
573
574    let is_mutable_buffer_byte_aligned = left_bit_offset == 0;
575
576    if is_mutable_buffer_byte_aligned {
577        byte_aligned_bitwise_unary_op_helper(buffer, offset_in_bits, len_in_bits, op);
578    } else {
579        align_to_byte(buffer, &mut op, offset_in_bits, len_in_bits);
580
581        // If we are not byte aligned we will read the first few bits
582        let bits_to_next_byte = 8 - left_bit_offset;
583
584        let offset_in_bits = offset_in_bits + bits_to_next_byte;
585        let len_in_bits = len_in_bits.saturating_sub(bits_to_next_byte);
586
587        if len_in_bits == 0 {
588            return;
589        }
590
591        // We are now byte aligned
592        byte_aligned_bitwise_unary_op_helper(buffer, offset_in_bits, len_in_bits, op);
593    }
594}
595
596/// Perform bitwise binary operation on byte-aligned buffers (i.e. not offsetting into a middle of a byte).
597///
598/// This is the optimized path for byte-aligned operations. It processes data in
599/// u64 chunks for maximum efficiency, then handles any remainder bits.
600///
601/// # Arguments
602///
603/// * `left` - The left mutable buffer (must be byte-aligned)
604/// * `left_offset_in_bits` - Starting bit offset in the left buffer (must be multiple of 8)
605/// * `right` - The right buffer as byte slice
606/// * `right_offset_in_bits` - Starting bit offset in the right buffer
607/// * `len_in_bits` - Number of bits to process
608/// * `op` - Binary operation to apply
609#[inline]
610fn byte_aligned_bitwise_bin_op_helper<F>(
611    left: &mut [u8],
612    left_offset_in_bits: usize,
613    right: impl AsRef<[u8]>,
614    right_offset_in_bits: usize,
615    len_in_bits: usize,
616    mut op: F,
617) where
618    F: FnMut(u64, u64) -> u64,
619{
620    // Must not reach here if we not byte aligned
621    assert_eq!(
622        left_offset_in_bits % 8,
623        0,
624        "offset_in_bits must be byte aligned"
625    );
626
627    // 1. Prepare the buffers
628    let (complete_u64_chunks, remainder_bytes) =
629        U64UnalignedSlice::split(left, left_offset_in_bits, len_in_bits);
630
631    let right_chunks = BitChunks::new(right.as_ref(), right_offset_in_bits, len_in_bits);
632    assert_eq!(
633        self::ceil(right_chunks.remainder_len(), 8),
634        remainder_bytes.len()
635    );
636
637    let right_chunks_iter = right_chunks.iter();
638    assert_eq!(right_chunks_iter.len(), complete_u64_chunks.len());
639
640    // 2. Process complete u64 chunks
641    complete_u64_chunks.zip_modify(right_chunks_iter, &mut op);
642
643    // Handle remainder bits if any
644    if right_chunks.remainder_len() > 0 {
645        handle_mutable_buffer_remainder(
646            &mut op,
647            remainder_bytes,
648            right_chunks.remainder_bits(),
649            right_chunks.remainder_len(),
650        )
651    }
652}
653
654/// Perform bitwise unary operation on byte-aligned buffer.
655///
656/// This is the optimized path for byte-aligned unary operations. It processes data in
657/// u64 chunks for maximum efficiency, then handles any remainder bits.
658///
659/// # Arguments
660///
661/// * `buffer` - The mutable buffer (must be byte-aligned)
662/// * `offset_in_bits` - Starting bit offset (must be multiple of 8)
663/// * `len_in_bits` - Number of bits to process
664/// * `op` - Unary operation to apply (e.g., `|a| !a`)
665#[inline]
666fn byte_aligned_bitwise_unary_op_helper<F>(
667    buffer: &mut [u8],
668    offset_in_bits: usize,
669    len_in_bits: usize,
670    mut op: F,
671) where
672    F: FnMut(u64) -> u64,
673{
674    // Must not reach here if we not byte aligned
675    assert_eq!(offset_in_bits % 8, 0, "offset_in_bits must be byte aligned");
676
677    let remainder_len = len_in_bits % 64;
678
679    let (complete_u64_chunks, remainder_bytes) =
680        U64UnalignedSlice::split(buffer, offset_in_bits, len_in_bits);
681
682    assert_eq!(self::ceil(remainder_len, 8), remainder_bytes.len());
683
684    // 2. Process complete u64 chunks
685    complete_u64_chunks.apply_unary_op(&mut op);
686
687    // Handle remainder bits if any
688    if remainder_len > 0 {
689        handle_mutable_buffer_remainder_unary(&mut op, remainder_bytes, remainder_len)
690    }
691}
692
693/// Align to byte boundary by applying operation to bits before the next byte boundary.
694///
695/// This function handles non-byte-aligned operations by processing bits from the current
696/// position up to the next byte boundary, while preserving all other bits in the byte.
697///
698/// # Arguments
699///
700/// * `op` - Unary operation to apply
701/// * `buffer` - The mutable buffer to modify
702/// * `offset_in_bits` - Starting bit offset (not byte-aligned)
703/// * `remaining_len_in_bits` - Number of bits still to process starting at `offset_in_bits`.
704///   When this is smaller than the number of bits left in the byte, the trailing bits of
705///   the byte are left untouched.
706fn align_to_byte<F>(
707    buffer: &mut [u8],
708    op: &mut F,
709    offset_in_bits: usize,
710    remaining_len_in_bits: usize,
711) where
712    F: FnMut(u64) -> u64,
713{
714    let byte_offset = offset_in_bits / 8;
715    let bit_offset = offset_in_bits % 8;
716
717    // Byte aligned offsets must take the byte aligned path instead
718    debug_assert_ne!(bit_offset, 0, "offset_in_bits must not be byte aligned");
719
720    // 1. read the first byte from the buffer
721    let first_byte: u8 = buffer[byte_offset];
722
723    // 2. Shift byte by the bit offset, keeping only the relevant bits
724    let relevant_first_byte = first_byte >> bit_offset;
725
726    // 3. run the op on the first byte only
727    let result_first_byte = op(relevant_first_byte as u64) as u8;
728
729    // 4. Shift back the result to the original position
730    let result_first_byte = result_first_byte << bit_offset;
731
732    // 5. Mask in only the bits the caller asked to process, i.e. the bits in
733    //    `bit_offset..bit_offset + bits_in_this_byte`. The request may end before the
734    //    byte boundary, in which case the trailing bits must be preserved as well.
735    //
736    //    `bit_offset` is in `1..=7` per the assert above, so `bits_in_this_byte` is at
737    //    most 7 and `bits_in_this_byte + bit_offset <= 8`, keeping the mask within a `u8`.
738    let bits_in_this_byte = (8 - bit_offset).min(remaining_len_in_bits);
739    let write_mask = ((1u8 << bits_in_this_byte) - 1) << bit_offset;
740
741    let result_first_byte = (first_byte & !write_mask) | (result_first_byte & write_mask);
742
743    // 6. write back the result to the buffer
744    buffer[byte_offset] = result_first_byte;
745}
746
747/// Centralized structure to handle a mutable u8 slice as a mutable u64 pointer.
748///
749/// Handle the following:
750/// 1. the lifetime is correct
751/// 2. we read/write within the bounds
752/// 3. We read and write using unaligned
753///
754/// This does not deallocate the underlying pointer when dropped
755///
756/// This is the only place that uses unsafe code to read and write unaligned
757///
758struct U64UnalignedSlice<'a> {
759    /// Pointer to the start of the u64 data
760    ///
761    /// We are using raw pointer as the data came from a u8 slice so we need to read and write unaligned
762    ptr: *mut u64,
763
764    /// Number of u64 elements
765    len: usize,
766
767    /// Marker to tie the lifetime of the pointer to the lifetime of the u8 slice
768    _marker: std::marker::PhantomData<&'a u8>,
769}
770
771impl<'a> U64UnalignedSlice<'a> {
772    /// Create a new [`U64UnalignedSlice`] from a `&mut [u8]` buffer
773    ///
774    /// return the [`U64UnalignedSlice`] and slice of bytes that are not part of the u64 chunks (guaranteed to be less than 8 bytes)
775    ///
776    fn split(
777        buffer: &'a mut [u8],
778        offset_in_bits: usize,
779        len_in_bits: usize,
780    ) -> (Self, &'a mut [u8]) {
781        // 1. Prepare the buffers
782        let left_buffer_mut: &mut [u8] = {
783            let last_offset = self::ceil(offset_in_bits + len_in_bits, 8);
784            assert!(last_offset <= buffer.len());
785
786            let byte_offset = offset_in_bits / 8;
787
788            &mut buffer[byte_offset..last_offset]
789        };
790
791        let number_of_u64_we_can_fit = len_in_bits / (u64::BITS as usize);
792
793        // 2. Split
794        let u64_len_in_bytes = number_of_u64_we_can_fit * size_of::<u64>();
795
796        assert!(u64_len_in_bytes <= left_buffer_mut.len());
797        let (bytes_for_u64, remainder) = left_buffer_mut.split_at_mut(u64_len_in_bytes);
798
799        #[expect(
800            clippy::cast_ptr_alignment,
801            reason = "`U64UnalignedSlice` only reads and writes through the unaligned methods"
802        )]
803        let ptr = bytes_for_u64.as_mut_ptr().cast::<u64>();
804
805        let this = Self {
806            ptr,
807            len: number_of_u64_we_can_fit,
808            _marker: std::marker::PhantomData,
809        };
810
811        (this, remainder)
812    }
813
814    fn len(&self) -> usize {
815        self.len
816    }
817
818    /// Modify the underlying u64 data in place using a binary operation
819    /// with another iterator.
820    fn zip_modify(
821        mut self,
822        mut zip_iter: impl ExactSizeIterator<Item = u64>,
823        mut map: impl FnMut(u64, u64) -> u64,
824    ) {
825        assert_eq!(self.len, zip_iter.len());
826
827        // In order to avoid advancing the pointer at the end of the loop which will
828        // make the last pointer invalid, we handle the first element outside the loop
829        // and then advance the pointer at the start of the loop
830        // making sure that the iterator is not empty
831        if let Some(right) = zip_iter.next() {
832            // SAFETY: We asserted that the iterator length and the current length are the same
833            // and the iterator is not empty, so the pointer is valid
834            unsafe {
835                self.apply_bin_op(right, &mut map);
836            }
837
838            // Because this consumes self we don't update the length
839        }
840
841        for right in zip_iter {
842            // Advance the pointer
843            //
844            // SAFETY: We asserted that the iterator length and the current length are the same
845            self.ptr = unsafe { self.ptr.add(1) };
846
847            // SAFETY: the pointer is valid as we are within the length
848            unsafe {
849                self.apply_bin_op(right, &mut map);
850            }
851
852            // Because this consumes self we don't update the length
853        }
854    }
855
856    /// Centralized function to correctly read the current u64 value and write back the result
857    ///
858    /// # SAFETY
859    /// the caller must ensure that the pointer is valid for reads and writes
860    ///
861    #[inline]
862    unsafe fn apply_bin_op(&mut self, right: u64, mut map: impl FnMut(u64, u64) -> u64) {
863        // SAFETY: The constructor ensures the pointer is valid,
864        // and as to all modifications in U64UnalignedSlice
865        let current_input = unsafe {
866            self.ptr
867                // Reading unaligned as we came from u8 slice
868                .read_unaligned()
869                // bit-packed buffers are stored starting with the least-significant byte first
870                // so when reading as u64 on a big-endian machine, the bytes need to be swapped
871                .to_le()
872        };
873
874        let combined = map(current_input, right);
875
876        // Write the result back
877        //
878        // The pointer came from mutable u8 slice so the pointer is valid for writes,
879        // and we need to write unaligned
880        unsafe { self.ptr.write_unaligned(combined) }
881    }
882
883    /// Modify the underlying u64 data in place using a unary operation.
884    fn apply_unary_op(mut self, mut map: impl FnMut(u64) -> u64) {
885        if self.len == 0 {
886            return;
887        }
888
889        // In order to avoid advancing the pointer at the end of the loop which will
890        // make the last pointer invalid, we handle the first element outside the loop
891        // and then advance the pointer at the start of the loop
892        // making sure that the iterator is not empty
893        // Safety: `self.len > 0` (checked above) and the pointer has not been advanced yet,
894        // so it is valid for reads and writes.
895        unsafe {
896            // I hope the function get inlined and the compiler remove the dead right parameter
897            self.apply_bin_op(0, &mut |left, _| map(left));
898
899            // Because this consumes self we don't update the length
900        }
901
902        for _ in 1..self.len {
903            // Advance the pointer
904            //
905            // SAFETY: we only advance the pointer within the length and not beyond
906            self.ptr = unsafe { self.ptr.add(1) };
907
908            // SAFETY: the pointer is valid as we are within the length
909            unsafe {
910                // I hope the function get inlined and the compiler remove the dead right parameter
911                self.apply_bin_op(0, &mut |left, _| map(left));
912            }
913
914            // Because this consumes self we don't update the length
915        }
916    }
917}
918
919/// Handle remainder bits (< 64 bits) for binary operations.
920///
921/// This function processes the bits that don't form a complete u64 chunk,
922/// ensuring that bits outside the operation range are preserved.
923///
924/// # Arguments
925///
926/// * `op` - Binary operation to apply
927/// * `start_remainder_mut_slice` - slice to the start of remainder bytes
928///   the length must be equal to `ceil(remainder_len, 8)`
929/// * `right_remainder_bits` - Right operand bits
930/// * `remainder_len` - Number of remainder bits
931#[inline]
932fn handle_mutable_buffer_remainder<F>(
933    op: &mut F,
934    start_remainder_mut_slice: &mut [u8],
935    right_remainder_bits: u64,
936    remainder_len: usize,
937) where
938    F: FnMut(u64, u64) -> u64,
939{
940    // Only read from slice the number of remainder bits
941    let left_remainder_bits = get_remainder_bits(start_remainder_mut_slice, remainder_len);
942
943    // Apply the operation
944    let rem = op(left_remainder_bits, right_remainder_bits);
945
946    // Write only the relevant bits back the result to the mutable slice
947    set_remainder_bits(start_remainder_mut_slice, rem, remainder_len);
948}
949
950/// Write remainder bits back to buffer while preserving bits outside the range.
951///
952/// This function carefully updates only the specified bits, leaving all other
953/// bits in the affected bytes unchanged.
954///
955/// # Arguments
956///
957/// * `start_remainder_mut_slice` - the slice of bytes to write the remainder bits to,
958///   the length must be equal to `ceil(remainder_len, 8)`
959/// * `rem` - The result bits to write
960/// * `remainder_len` - Number of bits to write
961#[inline]
962fn set_remainder_bits(start_remainder_mut_slice: &mut [u8], rem: u64, remainder_len: usize) {
963    assert_ne!(
964        start_remainder_mut_slice.len(),
965        0,
966        "start_remainder_mut_slice must not be empty"
967    );
968    assert!(remainder_len < 64, "remainder_len must be less than 64");
969
970    // This assertion is to make sure that the last byte in the slice is the boundary byte
971    // (i.e., the byte that contains both remainder bits and bits outside the remainder)
972    assert_eq!(
973        start_remainder_mut_slice.len(),
974        self::ceil(remainder_len, 8),
975        "start_remainder_mut_slice length must be equal to ceil(remainder_len, 8)"
976    );
977
978    // Need to update the remainder bytes in the mutable buffer
979    // but not override the bits outside the remainder
980
981    // Update `rem` end with the current bytes in the mutable buffer
982    // to preserve the bits outside the remainder
983    let rem = {
984        // 1. Read the byte that we will override
985        //    we only read the last byte as we verified that start_remainder_mut_slice length is
986        //    equal to ceil(remainder_len, 8), which means the last byte is the boundary byte
987        //    containing both remainder bits and bits outside the remainder
988        let current = start_remainder_mut_slice
989            .last()
990            // Unwrap as we already validated the slice is not empty
991            .unwrap();
992
993        // Shift the boundary byte to the position it occupies within `rem`, otherwise
994        // its bits would be compared against the wrong end of the mask below
995        let current = (*current as u64) << ((start_remainder_mut_slice.len() - 1) * 8);
996
997        // Mask where the bits that are inside the remainder are 1
998        // and the bits outside the remainder are 0
999        let inside_remainder_mask = (1 << remainder_len) - 1;
1000        // Mask where the bits that are outside the remainder are 1
1001        // and the bits inside the remainder are 0
1002        let outside_remainder_mask = !inside_remainder_mask;
1003
1004        // 2. Only keep the bits that are outside the remainder for the value from the mutable buffer
1005        let current = current & outside_remainder_mask;
1006
1007        // 3. Only keep the bits that are inside the remainder for the value from the operation
1008        let rem = rem & inside_remainder_mask;
1009
1010        // 4. Combine the two values
1011        current | rem
1012    };
1013
1014    // Write back the result to the mutable slice
1015    {
1016        let remainder_bytes = start_remainder_mut_slice.len();
1017
1018        // we are counting starting from the least significant bit, so to_le_bytes should be correct
1019        let rem = &rem.to_le_bytes()[0..remainder_bytes];
1020
1021        // this assumes that `[ToByteSlice]` can be copied directly
1022        // without calling `to_byte_slice` for each element,
1023        // which is correct for all ArrowNativeType implementations including u64.
1024        let src = rem.as_ptr();
1025        // Safety: `rem` has length `remainder_bytes`, `start_remainder_mut_slice` has length
1026        // `remainder_bytes`, and the two slices are non-overlapping (rem is derived from a
1027        // local `to_le_bytes()` call; start_remainder_mut_slice is the caller's mutable buffer).
1028        unsafe {
1029            std::ptr::copy_nonoverlapping(
1030                src,
1031                start_remainder_mut_slice.as_mut_ptr(),
1032                remainder_bytes,
1033            )
1034        };
1035    }
1036}
1037
1038/// Read remainder bits from a slice.
1039///
1040/// Reads the specified number of bits from slice and returns them as a u64.
1041///
1042/// # Arguments
1043///
1044/// * `remainder` - slice to the start of the bits
1045/// * `remainder_len` - Number of bits to read (must be < 64)
1046///
1047/// # Returns
1048///
1049/// A u64 containing the bits in the least significant positions
1050#[inline]
1051fn get_remainder_bits(remainder: &[u8], remainder_len: usize) -> u64 {
1052    assert!(remainder.len() < 64, "remainder_len must be less than 64");
1053    assert_eq!(
1054        remainder.len(),
1055        self::ceil(remainder_len, 8),
1056        "remainder and remainder len ceil must be the same"
1057    );
1058
1059    let bits = remainder
1060        .iter()
1061        .enumerate()
1062        .fold(0_u64, |acc, (index, &byte)| {
1063            acc | ((byte as u64) << (index * 8))
1064        });
1065
1066    bits & ((1 << remainder_len) - 1)
1067}
1068
1069/// Handle remainder bits (< 64 bits) for unary operations.
1070///
1071/// This function processes the bits that don't form a complete u64 chunk,
1072/// ensuring that bits outside the operation range are preserved.
1073///
1074/// # Arguments
1075///
1076/// * `op` - Unary operation to apply
1077/// * `start_remainder_mut` - Slice of bytes to write the remainder bits to
1078/// * `remainder_len` - Number of remainder bits
1079#[inline]
1080fn handle_mutable_buffer_remainder_unary<F>(
1081    op: &mut F,
1082    start_remainder_mut: &mut [u8],
1083    remainder_len: usize,
1084) where
1085    F: FnMut(u64) -> u64,
1086{
1087    // Only read from the slice the number of remainder bits
1088    let left_remainder_bits = get_remainder_bits(start_remainder_mut, remainder_len);
1089
1090    // Apply the operation
1091    let rem = op(left_remainder_bits);
1092
1093    // Write only the relevant bits back the result to the slice
1094    set_remainder_bits(start_remainder_mut, rem, remainder_len);
1095}
1096
1097#[cfg(test)]
1098mod tests {
1099    use std::collections::HashSet;
1100
1101    use super::*;
1102    use crate::bit_iterator::BitIterator;
1103    use crate::{BooleanBuffer, BooleanBufferBuilder, MutableBuffer};
1104    use rand::rngs::StdRng;
1105    use rand::{RngExt, SeedableRng};
1106
1107    /// Reference for [`compress`]: gather the `mask`-selected bits of `value`
1108    /// into contiguous low bits, least-significant first
1109    fn compress_reference(value: u64, mask: u64) -> u64 {
1110        (0..64)
1111            .filter(|&i| (mask >> i) & 1 == 1)
1112            .enumerate()
1113            .map(|(dest, i)| ((value >> i) & 1) << dest)
1114            .sum()
1115    }
1116
1117    #[test]
1118    fn test_compress() {
1119        assert_eq!(compress(0b1010, 0b1111), 0b1010);
1120        assert_eq!(compress(0b1010, 0b1010), 0b11);
1121        assert_eq!(compress(0b1010, 0b0101), 0);
1122        assert_eq!(compress(u64::MAX, 0), 0);
1123        assert_eq!(compress(0, u64::MAX), 0);
1124        assert_eq!(compress(u64::MAX, u64::MAX), u64::MAX);
1125
1126        // On a `bmi2` build this validates the hardware `pext` path,
1127        // otherwise the portable fallback
1128        let mut rng = StdRng::seed_from_u64(42);
1129        for _ in 0..1024 {
1130            let (value, mask): (u64, u64) = rng.random();
1131            assert_eq!(
1132                compress(value, mask),
1133                compress_reference(value, mask),
1134                "value={value:#x} mask={mask:#x}"
1135            );
1136        }
1137    }
1138
1139    #[test]
1140    fn test_compress_portable() {
1141        // Every path of the fallback, whatever this build compiles
1142        // `compress` to: uniform random masks alone have about 32 kept bits
1143        // and would only reach `compress_bytes`
1144        let check = |value: u64, mask: u64| {
1145            let want = compress_reference(value, mask);
1146            let kept = mask.count_ones();
1147            assert_eq!(
1148                compress_portable(value, mask),
1149                want,
1150                "value={value:#x} mask={mask:#x} kept={kept}"
1151            );
1152        };
1153        let mut rng = StdRng::seed_from_u64(42);
1154
1155        // Every mask with at most two kept or at most two dropped bits
1156        let value: u64 = rng.random();
1157        check(value, 0);
1158        check(value, u64::MAX);
1159        for i in 0..64 {
1160            check(value, 1 << i);
1161            check(value, !(1 << i));
1162            for j in i + 1..64 {
1163                let two = (1 << i) | (1 << j);
1164                check(value, two);
1165                check(value, !two);
1166            }
1167        }
1168
1169        // Random masks at every density: ANDing random words thins them out,
1170        // ORing fills them in
1171        for _ in 0..4096 {
1172            let value: u64 = rng.random();
1173            let mut sparse = u64::MAX;
1174            let mut dense = 0;
1175            for _ in 0..8 {
1176                let word: u64 = rng.random();
1177                sparse &= word;
1178                dense |= word;
1179                check(value, sparse);
1180                check(value, dense);
1181            }
1182            // every popcount from 0 to 64
1183            let kept = rng.random_range(0..=64);
1184            let mut mask = 0_u64;
1185            while mask.count_ones() < kept {
1186                mask |= 1 << rng.random_range(0..64);
1187            }
1188            check(value, mask);
1189        }
1190    }
1191
1192    #[test]
1193    fn test_expand() {
1194        fn reference(values: u64, mask: u64) -> u64 {
1195            let mut expected = 0;
1196            let mut input_idx = 0;
1197            for output_idx in 0..64 {
1198                if mask & (1 << output_idx) != 0 {
1199                    expected |= ((values >> input_idx) & 1) << output_idx;
1200                    input_idx += 1;
1201                }
1202            }
1203            expected
1204        }
1205
1206        assert_eq!(expand(0b1010, 0b1111), 0b1010);
1207        assert_eq!(expand(0b11, 0b1010), 0b1010);
1208        assert_eq!(expand(u64::MAX, 0), 0);
1209        assert_eq!(expand(0, u64::MAX), 0);
1210        assert_eq!(expand(0, 0x5555_5555_5555_5555), 0);
1211        assert_eq!(expand(u64::MAX, u64::MAX), u64::MAX);
1212
1213        let mut rng = StdRng::seed_from_u64(0x2b7e_1516_28ae_d2a6);
1214
1215        // Masks with at most one unset bit or at most one set bit
1216        for bit in 0..64 {
1217            for mask in [u64::MAX, !(1 << bit), 1 << bit, 0] {
1218                for _ in 0..16 {
1219                    let values = rng.random::<u64>();
1220                    assert_eq!(expand(values, mask), reference(values, mask), "{mask:#x}");
1221                }
1222            }
1223        }
1224
1225        // Masks across the full density range, exercising the hardware `pdep`
1226        // path on a `bmi2` build or both portable loops otherwise.
1227        for _ in 0..20_000 {
1228            let density = rng.random_range(0.0..=1.0);
1229            let mask = (0..64).fold(0_u64, |mask, bit| {
1230                mask | ((rng.random_bool(density) as u64) << bit)
1231            });
1232            let values = rng.random::<u64>();
1233            assert_eq!(expand(compress(values, mask), mask), values & mask);
1234            assert_eq!(expand(values, mask), reference(values, mask), "{mask:#x}");
1235        }
1236    }
1237
1238    #[test]
1239    fn test_round_upto_multiple_of_64() {
1240        assert_eq!(0, round_upto_multiple_of_64(0));
1241        assert_eq!(64, round_upto_multiple_of_64(1));
1242        assert_eq!(64, round_upto_multiple_of_64(63));
1243        assert_eq!(64, round_upto_multiple_of_64(64));
1244        assert_eq!(128, round_upto_multiple_of_64(65));
1245        assert_eq!(192, round_upto_multiple_of_64(129));
1246    }
1247
1248    #[test]
1249    #[should_panic(expected = "failed to round upto multiple of 64")]
1250    fn test_round_upto_multiple_of_64_panic() {
1251        let _ = round_upto_multiple_of_64(usize::MAX);
1252    }
1253
1254    #[test]
1255    #[should_panic(expected = "failed to round to next highest power of 2")]
1256    fn test_round_upto_panic() {
1257        let _ = round_upto_power_of_2(usize::MAX, 2);
1258    }
1259
1260    #[test]
1261    fn test_get_bit() {
1262        // 00001101
1263        assert!(get_bit(&[0b00001101], 0));
1264        assert!(!get_bit(&[0b00001101], 1));
1265        assert!(get_bit(&[0b00001101], 2));
1266        assert!(get_bit(&[0b00001101], 3));
1267
1268        // 01001001 01010010
1269        assert!(get_bit(&[0b01001001, 0b01010010], 0));
1270        assert!(!get_bit(&[0b01001001, 0b01010010], 1));
1271        assert!(!get_bit(&[0b01001001, 0b01010010], 2));
1272        assert!(get_bit(&[0b01001001, 0b01010010], 3));
1273        assert!(!get_bit(&[0b01001001, 0b01010010], 4));
1274        assert!(!get_bit(&[0b01001001, 0b01010010], 5));
1275        assert!(get_bit(&[0b01001001, 0b01010010], 6));
1276        assert!(!get_bit(&[0b01001001, 0b01010010], 7));
1277        assert!(!get_bit(&[0b01001001, 0b01010010], 8));
1278        assert!(get_bit(&[0b01001001, 0b01010010], 9));
1279        assert!(!get_bit(&[0b01001001, 0b01010010], 10));
1280        assert!(!get_bit(&[0b01001001, 0b01010010], 11));
1281        assert!(get_bit(&[0b01001001, 0b01010010], 12));
1282        assert!(!get_bit(&[0b01001001, 0b01010010], 13));
1283        assert!(get_bit(&[0b01001001, 0b01010010], 14));
1284        assert!(!get_bit(&[0b01001001, 0b01010010], 15));
1285    }
1286
1287    pub fn seedable_rng() -> StdRng {
1288        StdRng::seed_from_u64(42)
1289    }
1290
1291    #[test]
1292    fn test_get_bit_raw() {
1293        const NUM_BYTE: usize = 10;
1294        let mut buf = [0; NUM_BYTE];
1295        let mut expected = vec![];
1296        let mut rng = seedable_rng();
1297        for i in 0..8 * NUM_BYTE {
1298            let b = rng.random_bool(0.5);
1299            expected.push(b);
1300            if b {
1301                set_bit(&mut buf[..], i)
1302            }
1303        }
1304
1305        let raw_ptr = buf.as_ptr();
1306        for (i, b) in expected.iter().enumerate() {
1307            unsafe {
1308                assert_eq!(*b, get_bit_raw(raw_ptr, i));
1309            }
1310        }
1311    }
1312
1313    #[test]
1314    fn test_set_bit() {
1315        let mut b = [0b00000010];
1316        set_bit(&mut b, 0);
1317        assert_eq!([0b00000011], b);
1318        set_bit(&mut b, 1);
1319        assert_eq!([0b00000011], b);
1320        set_bit(&mut b, 7);
1321        assert_eq!([0b10000011], b);
1322    }
1323
1324    #[test]
1325    fn test_unset_bit() {
1326        let mut b = [0b11111101];
1327        unset_bit(&mut b, 0);
1328        assert_eq!([0b11111100], b);
1329        unset_bit(&mut b, 1);
1330        assert_eq!([0b11111100], b);
1331        unset_bit(&mut b, 7);
1332        assert_eq!([0b01111100], b);
1333    }
1334
1335    #[test]
1336    fn test_set_bit_raw() {
1337        const NUM_BYTE: usize = 10;
1338        let mut buf = vec![0; NUM_BYTE];
1339        let mut expected = vec![];
1340        let mut rng = seedable_rng();
1341        for i in 0..8 * NUM_BYTE {
1342            let b = rng.random_bool(0.5);
1343            expected.push(b);
1344            if b {
1345                unsafe {
1346                    set_bit_raw(buf.as_mut_ptr(), i);
1347                }
1348            }
1349        }
1350
1351        let raw_ptr = buf.as_ptr();
1352        for (i, b) in expected.iter().enumerate() {
1353            unsafe {
1354                assert_eq!(*b, get_bit_raw(raw_ptr, i));
1355            }
1356        }
1357    }
1358
1359    #[test]
1360    fn test_unset_bit_raw() {
1361        const NUM_BYTE: usize = 10;
1362        let mut buf = vec![255; NUM_BYTE];
1363        let mut expected = vec![];
1364        let mut rng = seedable_rng();
1365        for i in 0..8 * NUM_BYTE {
1366            let b = rng.random_bool(0.5);
1367            expected.push(b);
1368            if !b {
1369                unsafe {
1370                    unset_bit_raw(buf.as_mut_ptr(), i);
1371                }
1372            }
1373        }
1374
1375        let raw_ptr = buf.as_ptr();
1376        for (i, b) in expected.iter().enumerate() {
1377            unsafe {
1378                assert_eq!(*b, get_bit_raw(raw_ptr, i));
1379            }
1380        }
1381    }
1382
1383    #[test]
1384    fn test_get_set_bit_roundtrip() {
1385        const NUM_BYTES: usize = 10;
1386        const NUM_SETS: usize = 10;
1387
1388        let mut buffer: [u8; NUM_BYTES * 8] = [0; NUM_BYTES * 8];
1389        let mut v = HashSet::new();
1390        let mut rng = seedable_rng();
1391        for _ in 0..NUM_SETS {
1392            let offset = rng.random_range(0..8 * NUM_BYTES);
1393            v.insert(offset);
1394            set_bit(&mut buffer[..], offset);
1395        }
1396        for i in 0..NUM_BYTES * 8 {
1397            assert_eq!(v.contains(&i), get_bit(&buffer[..], i));
1398        }
1399    }
1400
1401    #[test]
1402    fn test_ceil() {
1403        assert_eq!(ceil(0, 1), 0);
1404        assert_eq!(ceil(1, 1), 1);
1405        assert_eq!(ceil(1, 2), 1);
1406        assert_eq!(ceil(1, 8), 1);
1407        assert_eq!(ceil(7, 8), 1);
1408        assert_eq!(ceil(8, 8), 1);
1409        assert_eq!(ceil(9, 8), 2);
1410        assert_eq!(ceil(9, 9), 1);
1411        assert_eq!(ceil(10000000000, 10), 1000000000);
1412        assert_eq!(ceil(10, 10000000000), 1);
1413        assert_eq!(ceil(10000000000, 1000000000), 10);
1414    }
1415
1416    #[test]
1417    fn test_read_up_to() {
1418        let all_ones = &[0b10111001, 0b10001100];
1419
1420        for (bit_offset, expected) in [
1421            (0, 0b00000001),
1422            (1, 0b00000000),
1423            (2, 0b00000000),
1424            (3, 0b00000001),
1425            (4, 0b00000001),
1426            (5, 0b00000001),
1427            (6, 0b00000000),
1428            (7, 0b00000001),
1429        ] {
1430            let result = read_up_to_byte_from_offset(all_ones, 1, bit_offset);
1431            assert_eq!(
1432                result, expected,
1433                "failed at bit_offset {bit_offset}. result, expected:\n{result:08b}\n{expected:08b}"
1434            );
1435        }
1436
1437        for (bit_offset, expected) in [
1438            (0, 0b00000001),
1439            (1, 0b00000000),
1440            (2, 0b00000010),
1441            (3, 0b00000011),
1442            (4, 0b00000011),
1443            (5, 0b00000001),
1444            (6, 0b00000010),
1445            (7, 0b00000001),
1446        ] {
1447            let result = read_up_to_byte_from_offset(all_ones, 2, bit_offset);
1448            assert_eq!(
1449                result, expected,
1450                "failed at bit_offset {bit_offset}. result, expected:\n{result:08b}\n{expected:08b}"
1451            );
1452        }
1453
1454        for (bit_offset, expected) in [
1455            (0, 0b00111001),
1456            (1, 0b00011100),
1457            (2, 0b00101110),
1458            (3, 0b00010111),
1459            (4, 0b00001011),
1460            (5, 0b00100101),
1461            (6, 0b00110010),
1462            (7, 0b00011001),
1463        ] {
1464            let result = read_up_to_byte_from_offset(all_ones, 6, bit_offset);
1465            assert_eq!(
1466                result, expected,
1467                "failed at bit_offset {bit_offset}. result, expected:\n{result:08b}\n{expected:08b}"
1468            );
1469        }
1470
1471        for (bit_offset, expected) in [
1472            (0, 0b00111001),
1473            (1, 0b01011100),
1474            (2, 0b00101110),
1475            (3, 0b00010111),
1476            (4, 0b01001011),
1477            (5, 0b01100101),
1478            (6, 0b00110010),
1479            (7, 0b00011001),
1480        ] {
1481            let result = read_up_to_byte_from_offset(all_ones, 7, bit_offset);
1482            assert_eq!(
1483                result, expected,
1484                "failed at bit_offset {bit_offset}. result, expected:\n{result:08b}\n{expected:08b}"
1485            );
1486        }
1487    }
1488
1489    /// Verifies that a unary operation applied to a buffer using u64 chunks
1490    /// is the same as applying the operation bit by bit.
1491    fn test_mutable_buffer_bin_op_helper<F, G>(
1492        left_data: &[bool],
1493        right_data: &[bool],
1494        left_offset_in_bits: usize,
1495        right_offset_in_bits: usize,
1496        len_in_bits: usize,
1497        op: F,
1498        mut expected_op: G,
1499    ) where
1500        F: FnMut(u64, u64) -> u64,
1501        G: FnMut(bool, bool) -> bool,
1502    {
1503        let mut left_buffer = BooleanBufferBuilder::new(len_in_bits);
1504        left_buffer.append_slice(left_data);
1505        let right_buffer = BooleanBuffer::from(right_data);
1506
1507        let expected: Vec<bool> = left_data
1508            .iter()
1509            .skip(left_offset_in_bits)
1510            .zip(right_data.iter().skip(right_offset_in_bits))
1511            .take(len_in_bits)
1512            .map(|(l, r)| expected_op(*l, *r))
1513            .collect();
1514
1515        let before = left_buffer.as_slice().to_vec();
1516
1517        apply_bitwise_binary_op(
1518            left_buffer.as_slice_mut(),
1519            left_offset_in_bits,
1520            right_buffer.inner(),
1521            right_offset_in_bits,
1522            len_in_bits,
1523            op,
1524        );
1525
1526        let result: Vec<bool> =
1527            BitIterator::new(left_buffer.as_slice(), left_offset_in_bits, len_in_bits).collect();
1528
1529        assert_eq!(
1530            result, expected,
1531            "Failed with left_offset={left_offset_in_bits}, right_offset={right_offset_in_bits}, len={len_in_bits}"
1532        );
1533
1534        assert_bits_outside_range_preserved(
1535            &before,
1536            left_buffer.as_slice(),
1537            left_offset_in_bits,
1538            len_in_bits,
1539            &format!(
1540                "left_offset={left_offset_in_bits}, right_offset={right_offset_in_bits}, len={len_in_bits}"
1541            ),
1542        );
1543    }
1544
1545    /// Asserts that every bit outside `offset_in_bits..offset_in_bits + len_in_bits`
1546    /// is identical in `before` and `after`.
1547    fn assert_bits_outside_range_preserved(
1548        before: &[u8],
1549        after: &[u8],
1550        offset_in_bits: usize,
1551        len_in_bits: usize,
1552        context: &str,
1553    ) {
1554        assert_eq!(before.len(), after.len());
1555        for i in 0..before.len() * 8 {
1556            if i >= offset_in_bits && i < offset_in_bits + len_in_bits {
1557                continue;
1558            }
1559            assert_eq!(
1560                get_bit(before, i),
1561                get_bit(after, i),
1562                "bit {i} outside the requested range was modified ({context})"
1563            );
1564        }
1565    }
1566
1567    /// Verifies that a unary operation applied to a buffer using u64 chunks
1568    /// is the same as applying the operation bit by bit.
1569    fn test_mutable_buffer_unary_op_helper<F, G>(
1570        data: &[bool],
1571        offset_in_bits: usize,
1572        len_in_bits: usize,
1573        op: F,
1574        mut expected_op: G,
1575    ) where
1576        F: FnMut(u64) -> u64,
1577        G: FnMut(bool) -> bool,
1578    {
1579        let mut buffer = BooleanBufferBuilder::new(len_in_bits);
1580        buffer.append_slice(data);
1581
1582        let expected: Vec<bool> = data
1583            .iter()
1584            .skip(offset_in_bits)
1585            .take(len_in_bits)
1586            .map(|b| expected_op(*b))
1587            .collect();
1588
1589        let before = buffer.as_slice().to_vec();
1590
1591        apply_bitwise_unary_op(buffer.as_slice_mut(), offset_in_bits, len_in_bits, op);
1592
1593        let result: Vec<bool> =
1594            BitIterator::new(buffer.as_slice(), offset_in_bits, len_in_bits).collect();
1595
1596        assert_eq!(
1597            result, expected,
1598            "Failed with offset={offset_in_bits}, len={len_in_bits}"
1599        );
1600
1601        assert_bits_outside_range_preserved(
1602            &before,
1603            buffer.as_slice(),
1604            offset_in_bits,
1605            len_in_bits,
1606            &format!("offset={offset_in_bits}, len={len_in_bits}"),
1607        );
1608    }
1609
1610    // Helper to create test data of specific length
1611    fn create_test_data(len: usize) -> (Vec<bool>, Vec<bool>) {
1612        let mut rng = rand::rng();
1613        let left: Vec<bool> = (0..len).map(|_| rng.random_bool(0.5)).collect();
1614        let right: Vec<bool> = (0..len).map(|_| rng.random_bool(0.5)).collect();
1615        (left, right)
1616    }
1617
1618    /// Test all binary operations (AND, OR, XOR) with the given parameters
1619    fn test_all_binary_ops(
1620        left_data: &[bool],
1621        right_data: &[bool],
1622        left_offset_in_bits: usize,
1623        right_offset_in_bits: usize,
1624        len_in_bits: usize,
1625    ) {
1626        // Test AND
1627        test_mutable_buffer_bin_op_helper(
1628            left_data,
1629            right_data,
1630            left_offset_in_bits,
1631            right_offset_in_bits,
1632            len_in_bits,
1633            |a, b| a & b,
1634            |a, b| a & b,
1635        );
1636
1637        // Test OR
1638        test_mutable_buffer_bin_op_helper(
1639            left_data,
1640            right_data,
1641            left_offset_in_bits,
1642            right_offset_in_bits,
1643            len_in_bits,
1644            |a, b| a | b,
1645            |a, b| a | b,
1646        );
1647
1648        // Test XOR
1649        test_mutable_buffer_bin_op_helper(
1650            left_data,
1651            right_data,
1652            left_offset_in_bits,
1653            right_offset_in_bits,
1654            len_in_bits,
1655            |a, b| a ^ b,
1656            |a, b| a ^ b,
1657        );
1658    }
1659
1660    // ===== Combined Binary Operation Tests =====
1661
1662    #[test]
1663    fn test_binary_ops_less_than_byte() {
1664        let (left, right) = create_test_data(4);
1665        test_all_binary_ops(&left, &right, 0, 0, 4);
1666    }
1667
1668    #[test]
1669    fn test_binary_ops_less_than_byte_across_boundary() {
1670        let (left, right) = create_test_data(16);
1671        test_all_binary_ops(&left, &right, 6, 6, 4);
1672    }
1673
1674    #[test]
1675    fn test_binary_ops_exactly_byte() {
1676        let (left, right) = create_test_data(16);
1677        test_all_binary_ops(&left, &right, 0, 0, 8);
1678    }
1679
1680    #[test]
1681    fn test_binary_ops_more_than_byte_less_than_u64() {
1682        let (left, right) = create_test_data(64);
1683        test_all_binary_ops(&left, &right, 0, 0, 32);
1684    }
1685
1686    #[test]
1687    fn test_binary_ops_exactly_u64() {
1688        let (left, right) = create_test_data(180);
1689        test_all_binary_ops(&left, &right, 0, 0, 64);
1690        test_all_binary_ops(&left, &right, 64, 9, 64);
1691        test_all_binary_ops(&left, &right, 8, 100, 64);
1692        test_all_binary_ops(&left, &right, 1, 15, 64);
1693        test_all_binary_ops(&left, &right, 12, 10, 64);
1694        test_all_binary_ops(&left, &right, 180 - 64, 2, 64);
1695    }
1696
1697    #[test]
1698    fn test_binary_ops_more_than_u64_not_multiple() {
1699        let (left, right) = create_test_data(200);
1700        test_all_binary_ops(&left, &right, 0, 0, 100);
1701    }
1702
1703    #[test]
1704    fn test_binary_ops_exactly_multiple_u64() {
1705        let (left, right) = create_test_data(256);
1706        test_all_binary_ops(&left, &right, 0, 0, 128);
1707    }
1708
1709    #[test]
1710    fn test_binary_ops_more_than_multiple_u64() {
1711        let (left, right) = create_test_data(300);
1712        test_all_binary_ops(&left, &right, 0, 0, 200);
1713    }
1714
1715    #[test]
1716    fn test_binary_ops_byte_aligned_no_remainder() {
1717        let (left, right) = create_test_data(200);
1718        test_all_binary_ops(&left, &right, 0, 0, 128);
1719    }
1720
1721    #[test]
1722    fn test_binary_ops_byte_aligned_with_remainder() {
1723        let (left, right) = create_test_data(200);
1724        test_all_binary_ops(&left, &right, 0, 0, 100);
1725    }
1726
1727    #[test]
1728    fn test_binary_ops_not_byte_aligned_no_remainder() {
1729        let (left, right) = create_test_data(200);
1730        test_all_binary_ops(&left, &right, 3, 3, 128);
1731    }
1732
1733    #[test]
1734    fn test_binary_ops_not_byte_aligned_with_remainder() {
1735        let (left, right) = create_test_data(200);
1736        test_all_binary_ops(&left, &right, 5, 5, 100);
1737    }
1738
1739    #[test]
1740    fn test_binary_ops_different_offsets() {
1741        let (left, right) = create_test_data(200);
1742        test_all_binary_ops(&left, &right, 3, 7, 50);
1743    }
1744
1745    #[test]
1746    fn test_binary_ops_offsets_greater_than_8_less_than_64() {
1747        let (left, right) = create_test_data(200);
1748        test_all_binary_ops(&left, &right, 13, 27, 100);
1749    }
1750
1751    // ===== NOT (Unary) Operation Tests =====
1752
1753    #[test]
1754    fn test_not_less_than_byte() {
1755        let data = vec![true, false, true, false];
1756        test_mutable_buffer_unary_op_helper(&data, 0, 4, |a| !a, |a| !a);
1757    }
1758
1759    #[test]
1760    fn test_not_less_than_byte_across_boundary() {
1761        let data: Vec<bool> = (0..16).map(|i| i % 2 == 0).collect();
1762        test_mutable_buffer_unary_op_helper(&data, 6, 4, |a| !a, |a| !a);
1763    }
1764
1765    #[test]
1766    fn test_not_exactly_byte() {
1767        let data: Vec<bool> = (0..16).map(|i| i % 2 == 0).collect();
1768        test_mutable_buffer_unary_op_helper(&data, 0, 8, |a| !a, |a| !a);
1769    }
1770
1771    #[test]
1772    fn test_not_more_than_byte_less_than_u64() {
1773        let data: Vec<bool> = (0..64).map(|i| i % 2 == 0).collect();
1774        test_mutable_buffer_unary_op_helper(&data, 0, 32, |a| !a, |a| !a);
1775    }
1776
1777    #[test]
1778    fn test_not_exactly_u64() {
1779        let data: Vec<bool> = (0..128).map(|i| i % 2 == 0).collect();
1780        test_mutable_buffer_unary_op_helper(&data, 0, 64, |a| !a, |a| !a);
1781    }
1782
1783    #[test]
1784    fn test_not_more_than_u64_not_multiple() {
1785        let data: Vec<bool> = (0..200).map(|i| i % 2 == 0).collect();
1786        test_mutable_buffer_unary_op_helper(&data, 0, 100, |a| !a, |a| !a);
1787    }
1788
1789    #[test]
1790    fn test_not_exactly_multiple_u64() {
1791        let data: Vec<bool> = (0..256).map(|i| i % 2 == 0).collect();
1792        test_mutable_buffer_unary_op_helper(&data, 0, 128, |a| !a, |a| !a);
1793    }
1794
1795    #[test]
1796    fn test_not_more_than_multiple_u64() {
1797        let data: Vec<bool> = (0..300).map(|i| i % 2 == 0).collect();
1798        test_mutable_buffer_unary_op_helper(&data, 0, 200, |a| !a, |a| !a);
1799    }
1800
1801    #[test]
1802    fn test_not_byte_aligned_no_remainder() {
1803        let data: Vec<bool> = (0..200).map(|i| i % 2 == 0).collect();
1804        test_mutable_buffer_unary_op_helper(&data, 0, 128, |a| !a, |a| !a);
1805    }
1806
1807    #[test]
1808    fn test_not_byte_aligned_with_remainder() {
1809        let data: Vec<bool> = (0..200).map(|i| i % 2 == 0).collect();
1810        test_mutable_buffer_unary_op_helper(&data, 0, 100, |a| !a, |a| !a);
1811    }
1812
1813    #[test]
1814    fn test_not_not_byte_aligned_no_remainder() {
1815        let data: Vec<bool> = (0..200).map(|i| i % 2 == 0).collect();
1816        test_mutable_buffer_unary_op_helper(&data, 3, 128, |a| !a, |a| !a);
1817    }
1818
1819    #[test]
1820    fn test_not_not_byte_aligned_with_remainder() {
1821        let data: Vec<bool> = (0..200).map(|i| i % 2 == 0).collect();
1822        test_mutable_buffer_unary_op_helper(&data, 5, 100, |a| !a, |a| !a);
1823    }
1824
1825    // ===== Edge Cases =====
1826
1827    #[test]
1828    fn test_empty_length() {
1829        let (left, right) = create_test_data(16);
1830        test_all_binary_ops(&left, &right, 0, 0, 0);
1831    }
1832
1833    #[test]
1834    fn test_single_bit() {
1835        let (left, right) = create_test_data(16);
1836        test_all_binary_ops(&left, &right, 0, 0, 1);
1837    }
1838
1839    #[test]
1840    fn test_single_bit_at_offset() {
1841        let (left, right) = create_test_data(16);
1842        test_all_binary_ops(&left, &right, 7, 7, 1);
1843    }
1844
1845    #[test]
1846    fn test_not_single_bit() {
1847        let data = vec![true, false, true, false];
1848        test_mutable_buffer_unary_op_helper(&data, 0, 1, |a| !a, |a| !a);
1849    }
1850
1851    #[test]
1852    fn test_not_empty_length() {
1853        let data = vec![true, false, true, false];
1854        test_mutable_buffer_unary_op_helper(&data, 0, 0, |a| !a, |a| !a);
1855    }
1856
1857    #[test]
1858    fn test_less_than_byte_unaligned_and_not_enough_bits() {
1859        let left_offset_in_bits = 2;
1860        let right_offset_in_bits = 4;
1861        let len_in_bits = 1;
1862
1863        // Single byte
1864        let right = (0..8).map(|i| (i / 2) % 2 == 0).collect::<Vec<_>>();
1865        // less than a byte
1866        let left = (0..3).map(|i| i % 2 == 0).collect::<Vec<_>>();
1867        test_all_binary_ops(
1868            &left,
1869            &right,
1870            left_offset_in_bits,
1871            right_offset_in_bits,
1872            len_in_bits,
1873        );
1874    }
1875
1876    /// Ranges that start and end inside the same non-byte-aligned byte must not
1877    /// touch the trailing bits of that byte.
1878    #[test]
1879    fn test_ops_ending_inside_the_first_partial_byte() {
1880        let (left, right) = create_test_data(32);
1881        for offset in 1..8 {
1882            // Inclusive so the range ending exactly on the byte boundary is covered too
1883            for len in 1..=(8 - offset) {
1884                test_all_binary_ops(&left, &right, offset, offset, len);
1885                test_all_binary_ops(&left, &right, offset, (offset + 3) % 8, len);
1886                test_mutable_buffer_unary_op_helper(&left, offset, len, |a| !a, |a| !a);
1887            }
1888        }
1889    }
1890
1891    #[test]
1892    fn test_and_within_first_partial_byte_preserves_trailing_bits() {
1893        let mut left = vec![0b11111111u8, 0b11111111u8];
1894        let right = vec![0b00000000u8, 0b00000000u8];
1895        // AND a single bit at bit offset 1: only bit 1 may be cleared
1896        apply_bitwise_binary_op(&mut left, 1, &right, 0, 1, |a, b| a & b);
1897        assert_eq!(left, vec![0b11111101u8, 0b11111111u8]);
1898    }
1899
1900    #[test]
1901    fn test_not_within_first_partial_byte_preserves_trailing_bits() {
1902        let mut buffer = vec![0b00000000u8];
1903        // NOT two bits at bit offset 3: only bits 3 and 4 may be flipped
1904        apply_bitwise_unary_op(&mut buffer, 3, 2, |a| !a);
1905        assert_eq!(buffer, vec![0b00011000u8]);
1906    }
1907
1908    /// When the remainder spans more than one byte, the byte holding the end of the
1909    /// range is the *last* byte of the remainder, not the first. Its bits above the
1910    /// remainder must survive.
1911    #[test]
1912    fn test_or_with_multi_byte_remainder_preserves_boundary_bits() {
1913        let mut left = vec![0b00000000u8, 0b00000000u8, 0b11110000u8];
1914        let right = vec![0b11111111u8, 0b11111111u8, 0b11111111u8];
1915        // OR over 20 bits: bits 20..24 of `left` are outside the range and must stay set
1916        apply_bitwise_binary_op(&mut left, 0, &right, 0, 20, |a, b| a | b);
1917        assert_eq!(
1918            left,
1919            vec![0b11111111u8, 0b11111111u8, 0b11111111u8],
1920            "the boundary byte lost its out-of-range bits"
1921        );
1922    }
1923
1924    #[test]
1925    fn test_not_with_multi_byte_remainder_preserves_boundary_bits() {
1926        let mut buffer = vec![0b00000000u8, 0b00000000u8, 0b11111111u8];
1927        // NOT over 20 bits: only bits 16..20 of the last byte may be flipped
1928        apply_bitwise_unary_op(&mut buffer, 0, 20, |a| !a);
1929        assert_eq!(
1930            buffer,
1931            vec![0b11111111u8, 0b11111111u8, 0b11110000u8],
1932            "the boundary byte lost its out-of-range bits"
1933        );
1934    }
1935
1936    #[test]
1937    fn test_bitwise_binary_op_offset_out_of_bounds() {
1938        let input = vec![0b10101010u8, 0b01010101u8];
1939        let mut buffer = MutableBuffer::new(2); // space for 16 bits
1940        buffer.extend_from_slice(&input); // only 2 bytes
1941        apply_bitwise_binary_op(
1942            buffer.as_slice_mut(),
1943            100, // exceeds buffer length, becomes a noop
1944            [0b11110000u8, 0b00001111u8],
1945            0,
1946            0,
1947            |a, b| a & b,
1948        );
1949        assert_eq!(buffer.as_slice(), &input);
1950    }
1951
1952    #[test]
1953    #[should_panic(expected = "assertion failed: last_offset <= buffer.len()")]
1954    fn test_bitwise_binary_op_length_out_of_bounds() {
1955        let mut buffer = MutableBuffer::new(2); // space for 16 bits
1956        buffer.extend_from_slice(&[0b10101010u8, 0b01010101u8]); // only 2 bytes
1957        apply_bitwise_binary_op(
1958            buffer.as_slice_mut(),
1959            0, // exceeds buffer length
1960            [0b11110000u8, 0b00001111u8],
1961            0,
1962            100,
1963            |a, b| a & b,
1964        );
1965        assert_eq!(buffer.as_slice(), &[0b10101010u8, 0b01010101u8]);
1966    }
1967
1968    #[test]
1969    #[should_panic(expected = "offset + len out of bounds")]
1970    fn test_bitwise_binary_op_right_len_out_of_bounds() {
1971        let mut buffer = MutableBuffer::new(2); // space for 16 bits
1972        buffer.extend_from_slice(&[0b10101010u8, 0b01010101u8]); // only 2 bytes
1973        apply_bitwise_binary_op(
1974            buffer.as_slice_mut(),
1975            0, // exceeds buffer length
1976            [0b11110000u8, 0b00001111u8],
1977            1000,
1978            16,
1979            |a, b| a & b,
1980        );
1981        assert_eq!(buffer.as_slice(), &[0b10101010u8, 0b01010101u8]);
1982    }
1983
1984    #[test]
1985    #[should_panic(expected = "the len is 2 but the index is 12")]
1986    fn test_bitwise_unary_op_offset_out_of_bounds() {
1987        let input = vec![0b10101010u8, 0b01010101u8];
1988        let mut buffer = MutableBuffer::new(2); // space for 16 bits
1989        buffer.extend_from_slice(&input); // only 2 bytes
1990        apply_bitwise_unary_op(
1991            buffer.as_slice_mut(),
1992            100, // exceeds buffer length, becomes a noop
1993            8,
1994            |a| !a,
1995        );
1996        assert_eq!(buffer.as_slice(), &input);
1997    }
1998
1999    #[test]
2000    #[should_panic(expected = "assertion failed: last_offset <= buffer.len()")]
2001    fn test_bitwise_unary_op_length_out_of_bounds2() {
2002        let input = vec![0b10101010u8, 0b01010101u8];
2003        let mut buffer = MutableBuffer::new(2); // space for 16 bits
2004        buffer.extend_from_slice(&input); // only 2 bytes
2005        apply_bitwise_unary_op(
2006            buffer.as_slice_mut(),
2007            3,   // start at bit 3, to exercise different path
2008            100, // exceeds buffer length
2009            |a| !a,
2010        );
2011        assert_eq!(buffer.as_slice(), &input);
2012    }
2013}