Skip to main content

arrow_buffer/buffer/
ops.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
5use super::{Buffer, MutableBuffer};
6use crate::BooleanBuffer;
7use crate::util::bit_util::ceil;
8
9/// Apply a bitwise operation `op` to four inputs and return the result as a Buffer.
10///
11/// The inputs are treated as bitmaps, meaning that offsets and length are
12/// specified in number of bits.
13///
14/// NOTE: The operation `op` is applied to chunks of 64 bits (u64) and any bits
15/// outside the offsets and len are set to zero out before calling `op`.
16pub fn bitwise_quaternary_op_helper<F>(
17    buffers: [&Buffer; 4],
18    offsets: [usize; 4],
19    len_in_bits: usize,
20    op: F,
21) -> Buffer
22where
23    F: Fn(u64, u64, u64, u64) -> u64,
24{
25    let first_chunks = buffers[0].bit_chunks(offsets[0], len_in_bits);
26    let second_chunks = buffers[1].bit_chunks(offsets[1], len_in_bits);
27    let third_chunks = buffers[2].bit_chunks(offsets[2], len_in_bits);
28    let fourth_chunks = buffers[3].bit_chunks(offsets[3], len_in_bits);
29
30    let chunks = first_chunks
31        .iter()
32        .zip(second_chunks.iter())
33        .zip(third_chunks.iter())
34        .zip(fourth_chunks.iter())
35        .map(|(((first, second), third), fourth)| op(first, second, third, fourth));
36    // Soundness: `BitChunks` is a `BitChunks` iterator which
37    // correctly reports its upper bound
38    let mut buffer = unsafe { MutableBuffer::from_trusted_len_iter(chunks) };
39
40    let remainder_bytes = ceil(first_chunks.remainder_len(), 8);
41    let rem = op(
42        first_chunks.remainder_bits(),
43        second_chunks.remainder_bits(),
44        third_chunks.remainder_bits(),
45        fourth_chunks.remainder_bits(),
46    );
47    // we are counting its starting from the least significant bit, to to_le_bytes should be correct
48    let rem = &rem.to_le_bytes()[0..remainder_bytes];
49    buffer.extend_from_slice(rem);
50
51    buffer.into()
52}
53
54/// Apply a bitwise operation `op` to two inputs and return the result as a Buffer.
55///
56/// The inputs are treated as bitmaps, meaning that offsets and length are
57/// specified in number of bits.
58///
59/// NOTE: The operation `op` is applied to chunks of 64 bits (u64) and any bits
60/// outside the offsets and len are set to zero out before calling `op`.
61pub fn bitwise_bin_op_helper<F>(
62    left: &Buffer,
63    left_offset_in_bits: usize,
64    right: &Buffer,
65    right_offset_in_bits: usize,
66    len_in_bits: usize,
67    mut op: F,
68) -> Buffer
69where
70    F: FnMut(u64, u64) -> u64,
71{
72    let left_chunks = left.bit_chunks(left_offset_in_bits, len_in_bits);
73    let right_chunks = right.bit_chunks(right_offset_in_bits, len_in_bits);
74
75    let chunks = left_chunks
76        .iter()
77        .zip(right_chunks.iter())
78        .map(|(left, right)| op(left, right));
79    // Soundness: `BitChunks` is a `BitChunks` iterator which
80    // correctly reports its upper bound
81    let mut buffer = unsafe { MutableBuffer::from_trusted_len_iter(chunks) };
82
83    let remainder_bytes = ceil(left_chunks.remainder_len(), 8);
84    let rem = op(left_chunks.remainder_bits(), right_chunks.remainder_bits());
85    // we are counting its starting from the least significant bit, to to_le_bytes should be correct
86    let rem = &rem.to_le_bytes()[0..remainder_bytes];
87    buffer.extend_from_slice(rem);
88
89    buffer.into()
90}
91
92/// Apply a bitwise operation `op` to one input and return the result as a Buffer.
93///
94/// The input is treated as a bitmap, meaning that offset and length are
95/// specified in number of bits.
96///
97/// NOTE: The operation `op` is applied to chunks of 64 bits (u64) and any bits
98/// outside the offsets and len are set to zero out before calling `op`.
99pub fn bitwise_unary_op_helper<F>(
100    left: &Buffer,
101    offset_in_bits: usize,
102    len_in_bits: usize,
103    mut op: F,
104) -> Buffer
105where
106    F: FnMut(u64) -> u64,
107{
108    // reserve capacity and set length so we can get a typed view of u64 chunks
109    let mut result =
110        MutableBuffer::new(ceil(len_in_bits, 8)).with_bitset(len_in_bits / 64 * 8, false);
111
112    let left_chunks = left.bit_chunks(offset_in_bits, len_in_bits);
113
114    let result_chunks = result.typed_data_mut::<u64>().iter_mut();
115
116    result_chunks
117        .zip(left_chunks.iter())
118        .for_each(|(res, left)| {
119            *res = op(left);
120        });
121
122    let remainder_bytes = ceil(left_chunks.remainder_len(), 8);
123    let rem = op(left_chunks.remainder_bits());
124    // we are counting its starting from the least significant bit, to to_le_bytes should be correct
125    let rem = &rem.to_le_bytes()[0..remainder_bytes];
126    result.extend_from_slice(rem);
127
128    result.into()
129}
130
131/// Apply a bitwise and to two inputs and return the result as a Buffer.
132/// The inputs are treated as bitmaps, meaning that offsets and length are specified in number of bits.
133///
134/// # See Also
135/// * [`BooleanBuffer::from_bitwise_binary_op`] for creating `BooleanBuffer`s directly
136pub fn buffer_bin_and(
137    left: &Buffer,
138    left_offset_in_bits: usize,
139    right: &Buffer,
140    right_offset_in_bits: usize,
141    len_in_bits: usize,
142) -> Buffer {
143    let result = BooleanBuffer::from_bitwise_binary_op(
144        left,
145        left_offset_in_bits,
146        right,
147        right_offset_in_bits,
148        len_in_bits,
149        |a, b| a & b,
150    );
151    // Normalize non-zero BooleanBuffer offsets back to a zero-offset Buffer.
152    if result.offset() == 0 {
153        result.into_inner()
154    } else {
155        result.sliced()
156    }
157}
158
159/// Apply a bitwise or to two inputs and return the result as a Buffer.
160/// The inputs are treated as bitmaps, meaning that offsets and length are specified in number of bits.
161///
162/// # See Also
163/// * [`BooleanBuffer::from_bitwise_binary_op`] for creating `BooleanBuffer`s directly
164pub fn buffer_bin_or(
165    left: &Buffer,
166    left_offset_in_bits: usize,
167    right: &Buffer,
168    right_offset_in_bits: usize,
169    len_in_bits: usize,
170) -> Buffer {
171    let result = BooleanBuffer::from_bitwise_binary_op(
172        left,
173        left_offset_in_bits,
174        right,
175        right_offset_in_bits,
176        len_in_bits,
177        |a, b| a | b,
178    );
179    // Normalize non-zero BooleanBuffer offsets back to a zero-offset Buffer.
180    if result.offset() == 0 {
181        result.into_inner()
182    } else {
183        result.sliced()
184    }
185}
186
187/// Apply a bitwise xor to two inputs and return the result as a Buffer.
188/// The inputs are treated as bitmaps, meaning that offsets and length are specified in number of bits.
189///
190/// # See Also
191/// * [`BooleanBuffer::from_bitwise_binary_op`] for creating `BooleanBuffer`s directly
192pub fn buffer_bin_xor(
193    left: &Buffer,
194    left_offset_in_bits: usize,
195    right: &Buffer,
196    right_offset_in_bits: usize,
197    len_in_bits: usize,
198) -> Buffer {
199    let result = BooleanBuffer::from_bitwise_binary_op(
200        left,
201        left_offset_in_bits,
202        right,
203        right_offset_in_bits,
204        len_in_bits,
205        |a, b| a ^ b,
206    );
207    // Normalize non-zero BooleanBuffer offsets back to a zero-offset Buffer.
208    if result.offset() == 0 {
209        result.into_inner()
210    } else {
211        result.sliced()
212    }
213}
214
215/// Apply a bitwise and_not to two inputs and return the result as a Buffer.
216/// The inputs are treated as bitmaps, meaning that offsets and length are specified in number of bits.
217///
218/// # See Also
219/// * [`BooleanBuffer::from_bitwise_binary_op`] for creating `BooleanBuffer`s directly
220pub fn buffer_bin_and_not(
221    left: &Buffer,
222    left_offset_in_bits: usize,
223    right: &Buffer,
224    right_offset_in_bits: usize,
225    len_in_bits: usize,
226) -> Buffer {
227    let result = BooleanBuffer::from_bitwise_binary_op(
228        left,
229        left_offset_in_bits,
230        right,
231        right_offset_in_bits,
232        len_in_bits,
233        |a, b| a & !b,
234    );
235    // Normalize non-zero BooleanBuffer offsets back to a zero-offset Buffer.
236    if result.offset() == 0 {
237        result.into_inner()
238    } else {
239        result.sliced()
240    }
241}
242
243/// Apply a bitwise not to one input and return the result as a Buffer.
244/// The input is treated as a bitmap, meaning that offset and length are specified in number of bits.
245///
246/// # See Also
247/// * [`BooleanBuffer::from_bitwise_unary_op`] for creating `BooleanBuffer`s directly
248pub fn buffer_unary_not(left: &Buffer, offset_in_bits: usize, len_in_bits: usize) -> Buffer {
249    BooleanBuffer::from_bitwise_unary_op(left, offset_in_bits, len_in_bits, |a| !a).into_inner()
250}
251
252#[cfg(test)]
253mod tests {
254    use super::*;
255
256    #[test]
257    fn test_buffer_bin_ops_return_zero_offset_buffers() {
258        let left = Buffer::from(vec![0b1010_1100, 0b0110_1001]);
259        let right = Buffer::from(vec![0, 0, 0, 0, 0, 0, 0, 0, 0b1110_0101, 0b0101_1000]);
260
261        let left_offset = 1;
262        let right_offset = 65; // same mod 64 as left_offset, so from_bitwise_binary_op returns non-zero offset
263        let len = 7;
264
265        // Reuse the same offset scenario for all four binary wrappers:
266        // each wrapper should return the logically equivalent offset-0 Buffer,
267        // even though the underlying BooleanBuffer result has offset 1.
268        for (op, wrapper) in [
269            (
270                (|a, b| a & b) as fn(u64, u64) -> u64,
271                buffer_bin_and as fn(&Buffer, usize, &Buffer, usize, usize) -> Buffer,
272            ),
273            (((|a, b| a | b) as fn(u64, u64) -> u64), buffer_bin_or),
274            (((|a, b| a ^ b) as fn(u64, u64) -> u64), buffer_bin_xor),
275            (((|a, b| a & !b) as fn(u64, u64) -> u64), buffer_bin_and_not),
276        ] {
277            let unsliced = BooleanBuffer::from_bitwise_binary_op(
278                &left,
279                left_offset,
280                &right,
281                right_offset,
282                len,
283                op,
284            );
285            assert_eq!(unsliced.offset(), 1);
286
287            let result = wrapper(&left, left_offset, &right, right_offset, len);
288
289            assert_eq!(result, unsliced.sliced());
290            assert_eq!(result.len(), 1);
291        }
292    }
293}