Skip to main content

arrow_buffer/util/
bit_mask.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 packed bit masks
6
7use crate::bit_util::ceil;
8
9/// Util function to set bits in a slice of bytes.
10///
11/// This will sets all bits on `write_data` in the range `[offset_write..offset_write+len]`
12/// to be equal to the bits in `data` in the range `[offset_read..offset_read+len]`
13/// returns the number of `0` bits `data[offset_read..offset_read+len]`
14/// `offset_write`, `offset_read`, and `len` are in terms of bits
15///
16/// # Panics
17///
18/// Panics if `offset_write + len` exceeds `write_data.len() * 8`, or if
19/// `offset_read + len` exceeds `data.len() * 8`
20pub fn set_bits(
21    write_data: &mut [u8],
22    data: &[u8],
23    offset_write: usize,
24    offset_read: usize,
25    len: usize,
26) -> usize {
27    assert!(
28        offset_write
29            .checked_add(len)
30            .expect("operation will overflow write buffer")
31            <= write_data.len() * 8
32    );
33    assert!(
34        offset_read
35            .checked_add(len)
36            .expect("operation will overflow read buffer")
37            <= data.len() * 8
38    );
39    let mut null_count = 0;
40    let mut acc = 0;
41    while len > acc {
42        // SAFETY: the arguments to `set_upto_64bits` are within the valid range because
43        // (offset_write + acc) + (len - acc) == offset_write + len <= write_data.len() * 8
44        // (offset_read + acc) + (len - acc) == offset_read + len <= data.len() * 8
45        let (n, len_set) = unsafe {
46            set_upto_64bits(
47                write_data,
48                data,
49                offset_write + acc,
50                offset_read + acc,
51                len - acc,
52            )
53        };
54        null_count += n;
55        acc += len_set;
56    }
57
58    null_count
59}
60
61/// Similar to `set_bits` but sets only upto 64 bits, actual number of bits set may vary.
62/// Returns a pair of the number of `0` bits and the number of bits set
63///
64/// # Safety
65/// The caller must ensure all arguments are within the valid range.
66#[inline]
67unsafe fn set_upto_64bits(
68    write_data: &mut [u8],
69    data: &[u8],
70    offset_write: usize,
71    offset_read: usize,
72    len: usize,
73) -> (usize, usize) {
74    let read_byte = offset_read / 8;
75    let read_shift = offset_read % 8;
76    let write_byte = offset_write / 8;
77    let write_shift = offset_write % 8;
78
79    if len >= 64 {
80        let chunk = unsafe { data.as_ptr().add(read_byte).cast::<u64>().read_unaligned() };
81        if read_shift == 0 {
82            if write_shift == 0 {
83                // no shifting necessary
84                let len = 64;
85                let null_count = chunk.count_zeros() as usize;
86                unsafe { write_u64_bytes(write_data, write_byte, chunk) };
87                (null_count, len)
88            } else {
89                // only write shifting necessary
90                let len = 64 - write_shift;
91                let chunk = chunk << write_shift;
92                let null_count = len - chunk.count_ones() as usize;
93                unsafe { or_write_u64_bytes(write_data, write_byte, chunk) };
94                (null_count, len)
95            }
96        } else if write_shift == 0 {
97            // only read shifting necessary
98            let len = 64 - 8; // 56 bits so the next set_upto_64bits call will see write_shift == 0
99            let chunk = (chunk >> read_shift) & 0x00FFFFFFFFFFFFFF; // 56 bits mask
100            let null_count = len - chunk.count_ones() as usize;
101            unsafe { write_u64_bytes(write_data, write_byte, chunk) };
102            (null_count, len)
103        } else {
104            let len = 64 - std::cmp::max(read_shift, write_shift);
105            let chunk = (chunk >> read_shift) << write_shift;
106            let null_count = len - chunk.count_ones() as usize;
107            unsafe { or_write_u64_bytes(write_data, write_byte, chunk) };
108            (null_count, len)
109        }
110    } else if len == 1 {
111        let byte_chunk = (unsafe { data.get_unchecked(read_byte) } >> read_shift) & 1;
112        unsafe { *write_data.get_unchecked_mut(write_byte) |= byte_chunk << write_shift };
113        ((byte_chunk ^ 1) as usize, 1)
114    } else {
115        let len = std::cmp::min(len, 64 - std::cmp::max(read_shift, write_shift));
116        let bytes = ceil(len + read_shift, 8);
117        // SAFETY: the args of `read_bytes_to_u64` are valid as read_byte + bytes <= data.len()
118        let chunk = unsafe { read_bytes_to_u64(data, read_byte, bytes) };
119        let mask = u64::MAX >> (64 - len);
120        let chunk = (chunk >> read_shift) & mask; // masking to read `len` bits only
121        let chunk = chunk << write_shift; // shifting back to align with `write_data`
122        let null_count = len - chunk.count_ones() as usize;
123        let bytes = ceil(len + write_shift, 8);
124        for (i, c) in chunk.to_le_bytes().iter().enumerate().take(bytes) {
125            unsafe { *write_data.get_unchecked_mut(write_byte + i) |= c };
126        }
127        (null_count, len)
128    }
129}
130
131/// # Safety
132/// The caller must ensure `data` has `offset..(offset + 8)` range, and `count <= 8`.
133#[inline]
134unsafe fn read_bytes_to_u64(data: &[u8], offset: usize, count: usize) -> u64 {
135    debug_assert!(count <= 8);
136    let mut tmp: u64 = 0;
137    let src = unsafe { data.as_ptr().add(offset) };
138    unsafe { std::ptr::copy_nonoverlapping(src, std::ptr::from_mut(&mut tmp).cast::<u8>(), count) };
139    tmp
140}
141
142/// # Safety
143/// The caller must ensure `data` has `offset..(offset + 8)` range
144#[inline]
145unsafe fn write_u64_bytes(data: &mut [u8], offset: usize, chunk: u64) {
146    #[expect(
147        clippy::cast_ptr_alignment,
148        reason = "the pointer is only written through `write_unaligned`"
149    )]
150    let ptr = unsafe { data.as_mut_ptr().add(offset) }.cast::<u64>();
151    unsafe { ptr.write_unaligned(chunk) };
152}
153
154/// Similar to `write_u64_bytes`, but this method ORs the offset addressed `data` and `chunk`
155/// instead of overwriting
156///
157/// # Safety
158/// The caller must ensure `data` has `offset..(offset + 8)` range
159#[inline]
160unsafe fn or_write_u64_bytes(data: &mut [u8], offset: usize, chunk: u64) {
161    let ptr = unsafe { data.as_mut_ptr().add(offset) };
162    let chunk = chunk | (unsafe { *ptr }) as u64;
163    unsafe { ptr.cast::<u64>().write_unaligned(chunk) };
164}
165
166#[cfg(test)]
167mod tests {
168    use super::*;
169    use crate::bit_util::{get_bit, set_bit, unset_bit};
170    use rand::prelude::StdRng;
171    use rand::{RngExt, SeedableRng, TryRng};
172    use std::fmt::Display;
173
174    #[test]
175    fn test_set_bits_aligned() {
176        SetBitsTest {
177            write_data: vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
178            data: vec![
179                0b11100111, 0b10100101, 0b10011001, 0b11011011, 0b11101011, 0b11000011, 0b11100111,
180                0b10100101,
181            ],
182            offset_write: 8,
183            offset_read: 0,
184            len: 64,
185            expected_data: vec![
186                0, 0b11100111, 0b10100101, 0b10011001, 0b11011011, 0b11101011, 0b11000011,
187                0b11100111, 0b10100101, 0,
188            ],
189            expected_null_count: 24,
190        }
191        .verify();
192    }
193
194    #[test]
195    fn test_set_bits_unaligned_destination_start() {
196        SetBitsTest {
197            write_data: vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
198            data: vec![
199                0b11100111, 0b10100101, 0b10011001, 0b11011011, 0b11101011, 0b11000011, 0b11100111,
200                0b10100101,
201            ],
202            offset_write: 3,
203            offset_read: 0,
204            len: 64,
205            expected_data: vec![
206                0b00111000, 0b00101111, 0b11001101, 0b11011100, 0b01011110, 0b00011111, 0b00111110,
207                0b00101111, 0b00000101, 0b00000000,
208            ],
209            expected_null_count: 24,
210        }
211        .verify();
212    }
213
214    #[test]
215    fn test_set_bits_unaligned_destination_end() {
216        SetBitsTest {
217            write_data: vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
218            data: vec![
219                0b11100111, 0b10100101, 0b10011001, 0b11011011, 0b11101011, 0b11000011, 0b11100111,
220                0b10100101,
221            ],
222            offset_write: 8,
223            offset_read: 0,
224            len: 62,
225            expected_data: vec![
226                0, 0b11100111, 0b10100101, 0b10011001, 0b11011011, 0b11101011, 0b11000011,
227                0b11100111, 0b00100101, 0,
228            ],
229            expected_null_count: 23,
230        }
231        .verify();
232    }
233
234    #[test]
235    fn test_set_bits_unaligned() {
236        SetBitsTest {
237            write_data: vec![0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
238            data: vec![
239                0b11100111, 0b10100101, 0b10011001, 0b11011011, 0b11101011, 0b11000011, 0b11100111,
240                0b10100101, 0b10011001, 0b11011011, 0b11101011, 0b11000011, 0b11100111, 0b10100101,
241                0b10011001, 0b11011011, 0b11101011, 0b11000011,
242            ],
243            offset_write: 3,
244            offset_read: 5,
245            len: 95,
246            expected_data: vec![
247                0b01111000, 0b01101001, 0b11100110, 0b11110110, 0b11111010, 0b11110000, 0b01111001,
248                0b01101001, 0b11100110, 0b11110110, 0b11111010, 0b11110000, 0b00000001,
249            ],
250            expected_null_count: 35,
251        }
252        .verify();
253    }
254
255    #[test]
256    fn set_bits_fuzz() {
257        let mut rng = StdRng::seed_from_u64(42);
258        let mut data = SetBitsTest::new();
259        for _ in 0..100 {
260            data.regen(&mut rng);
261            data.verify();
262        }
263    }
264
265    #[derive(Debug, Default)]
266    struct SetBitsTest {
267        /// target write data
268        write_data: Vec<u8>,
269        /// source data
270        data: Vec<u8>,
271        offset_write: usize,
272        offset_read: usize,
273        len: usize,
274        /// the expected contents of write_data after the test
275        expected_data: Vec<u8>,
276        /// the expected number of nulls copied at the end of the test
277        expected_null_count: usize,
278    }
279
280    /// prints a byte slice as a binary string like "01010101 10101010"
281    struct BinaryFormatter<'a>(&'a [u8]);
282    impl Display for BinaryFormatter<'_> {
283        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
284            for byte in self.0 {
285                write!(f, "{byte:08b} ")?;
286            }
287            write!(f, " ")?;
288            Ok(())
289        }
290    }
291
292    impl Display for SetBitsTest {
293        fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
294            writeln!(f, "SetBitsTest {{")?;
295            writeln!(f, "  write_data:    {}", BinaryFormatter(&self.write_data))?;
296            writeln!(f, "  data:          {}", BinaryFormatter(&self.data))?;
297            writeln!(
298                f,
299                "  expected_data: {}",
300                BinaryFormatter(&self.expected_data)
301            )?;
302            writeln!(f, "  offset_write: {}", self.offset_write)?;
303            writeln!(f, "  offset_read: {}", self.offset_read)?;
304            writeln!(f, "  len: {}", self.len)?;
305            writeln!(f, "  expected_null_count: {}", self.expected_null_count)?;
306            writeln!(f, "}}")
307        }
308    }
309
310    impl SetBitsTest {
311        /// create a new instance of FuzzData
312        fn new() -> Self {
313            Self::default()
314        }
315
316        /// Update this instance's fields with randomly selected values and expected data
317        fn regen(&mut self, rng: &mut StdRng) {
318            //  (read) data
319            // ------------------+-----------------+-------
320            // .. offset_read .. | data            | ...
321            // ------------------+-----------------+-------
322
323            // Write data
324            // -------------------+-----------------+-------
325            // .. offset_write .. | (data to write) | ...
326            // -------------------+-----------------+-------
327
328            // length of data to copy
329            let len = rng.random_range(0..=200);
330
331            // randomly pick where we will write to
332            let offset_write_bits = rng.random_range(0..=200);
333            let offset_write_bytes = if offset_write_bits % 8 == 0 {
334                offset_write_bits / 8
335            } else {
336                (offset_write_bits / 8) + 1
337            };
338            let extra_write_data_bytes = rng.random_range(0..=5); // ensure 0 shows up often
339
340            // randomly decide where we will read from
341            let extra_read_data_bytes = rng.random_range(0..=5); // make sure 0 shows up often
342            let offset_read_bits = rng.random_range(0..=200);
343            let offset_read_bytes = if offset_read_bits % 8 != 0 {
344                (offset_read_bits / 8) + 1
345            } else {
346                offset_read_bits / 8
347            };
348
349            // create space for writing
350            self.write_data.clear();
351            self.write_data
352                .resize(offset_write_bytes + len + extra_write_data_bytes, 0);
353
354            // interestingly set_bits seems to assume the output is already zeroed
355            // the fuzz tests fail when this is uncommented
356            //self.write_data.try_fill(rng).unwrap();
357            self.offset_write = offset_write_bits;
358
359            // make source data
360            self.data
361                .resize(offset_read_bytes + len + extra_read_data_bytes, 0);
362            // fill source data with random bytes
363            rng.try_fill_bytes(self.data.as_mut_slice()).unwrap();
364            self.offset_read = offset_read_bits;
365
366            self.len = len;
367
368            // generated expectated output (not efficient)
369            self.expected_data.resize(self.write_data.len(), 0);
370            self.expected_data.copy_from_slice(&self.write_data);
371
372            self.expected_null_count = 0;
373            for i in 0..self.len {
374                let bit = get_bit(&self.data, self.offset_read + i);
375                if bit {
376                    set_bit(&mut self.expected_data, self.offset_write + i);
377                } else {
378                    unset_bit(&mut self.expected_data, self.offset_write + i);
379                    self.expected_null_count += 1;
380                }
381            }
382        }
383
384        /// call set_bits with the given parameters and compare with the expected output
385        fn verify(&self) {
386            // call set_bits and compare
387            let mut actual = self.write_data.clone();
388            let null_count = set_bits(
389                &mut actual,
390                &self.data,
391                self.offset_write,
392                self.offset_read,
393                self.len,
394            );
395
396            assert_eq!(actual, self.expected_data, "self: {self}");
397            assert_eq!(null_count, self.expected_null_count, "self: {self}");
398        }
399    }
400
401    #[test]
402    fn test_set_upto_64bits() {
403        // len >= 64
404        let write_data: &mut [u8] = &mut [0; 9];
405        let data: &[u8] = &[
406            0b00000001, 0b00000001, 0b00000001, 0b00000001, 0b00000001, 0b00000001, 0b00000001,
407            0b00000001, 0b00000001,
408        ];
409        let offset_write = 1;
410        let offset_read = 0;
411        let len = 65;
412        let (n, len_set) =
413            unsafe { set_upto_64bits(write_data, data, offset_write, offset_read, len) };
414        assert_eq!(n, 55);
415        assert_eq!(len_set, 63);
416        assert_eq!(
417            write_data,
418            &[
419                0b00000010, 0b00000010, 0b00000010, 0b00000010, 0b00000010, 0b00000010, 0b00000010,
420                0b00000010, 0b00000000
421            ]
422        );
423
424        // len = 1
425        let write_data: &mut [u8] = &mut [0b00000000];
426        let data: &[u8] = &[0b00000001];
427        let offset_write = 1;
428        let offset_read = 0;
429        let len = 1;
430        let (n, len_set) =
431            unsafe { set_upto_64bits(write_data, data, offset_write, offset_read, len) };
432        assert_eq!(n, 0);
433        assert_eq!(len_set, 1);
434        assert_eq!(write_data, &[0b00000010]);
435    }
436
437    #[test]
438    #[should_panic(expected = "operation will overflow read buffer")]
439    fn test_overflow_read_buffer_bounds() {
440        // Tiny buffers so any huge computed index is out-of-bounds.
441        let data = [0u8; 1];
442        let mut write_data = [0u8; 1];
443
444        // Choose values so (offset_read + len) wraps to a small number in release builds.
445        // offset_read = usize::MAX - 7, len = 8 => wraps to 0.
446        // This can bypass `assert!(offset_read + len <= data.len() * 8)`.
447        let offset_write: usize = 0;
448        let offset_read: usize = usize::MAX - 7;
449        let len: usize = 8;
450
451        // should panic on bounds check overflow
452        let _nulls = set_bits(&mut write_data, &data, offset_write, offset_read, len);
453    }
454
455    #[test]
456    #[should_panic(expected = "operation will overflow write buffer")]
457    fn test_overflow_write_buffer_bounds() {
458        // Tiny buffers so any huge computed index is out-of-bounds.
459        let data = [0u8; 1];
460        let mut write_data = [0u8; 1];
461
462        // Choose values so (offset_write + len) wraps to a small number in release builds.
463        // offset_write = usize::MAX - 7, len = 8 => wraps to 0.
464        // This can bypass `assert!(offset_write + len <= write_data.len() * 8)`.
465        let offset_write: usize = usize::MAX - 7;
466        let offset_read: usize = 0;
467        let len: usize = 8;
468
469        // should panic on bounds check overflow
470        let _nulls = set_bits(&mut write_data, &data, offset_write, offset_read, len);
471    }
472}