alamb commented on a change in pull request #8664: URL: https://github.com/apache/arrow/pull/8664#discussion_r525228463
########## File path: rust/arrow/src/util/bit_ops.rs ########## @@ -0,0 +1,407 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +use crate::buffer::Buffer; + +use bitvec::prelude::*; +use bitvec::slice::ChunksExact; + +use std::fmt::Debug; + +/// +/// Immutable bit slice representation of buffer data +#[derive(Debug)] +pub struct BufferBitSlice<'a> { + buffer_data: &'a [u8], + bit_slice: &'a BitSlice<LocalBits, u8>, +} + +impl<'a> BufferBitSlice<'a> { + /// + /// Creates a immutable bit slice over the given data + #[inline] + pub fn new(buffer_data: &'a [u8]) -> Self { + let bit_slice = BitSlice::<LocalBits, _>::from_slice(buffer_data).unwrap(); + + BufferBitSlice { + buffer_data, + bit_slice: &bit_slice, + } + } + + /// + /// Returns immutable view with the given offset in bits and length in bits. + /// This view have zero-copy representation over the actual data. + #[inline] + pub fn view(&self, offset_in_bits: usize, len_in_bits: usize) -> Self { + Self { + buffer_data: self.buffer_data, + bit_slice: &self.bit_slice[offset_in_bits..offset_in_bits + len_in_bits], + } + } + + /// + /// Returns bit chunks in native 64-bit allocation size. + /// Native representations in Arrow follows 64-bit convention. + /// Chunks can still be reinterpreted in any primitive type lower than u64. + #[inline] Review comment: I am a little confused about this function -- specifically, all instantiations of `chunks<_>` that I could find use `u64` and the documentation on this function says it returns "native 64-bit alignment size", however, it is generic over `T: BitMemory` suggesting it could be used for I suggest we document what `T` type logically means / reasons someone would use something other than `u64` when invoking it in arrow, or perhaps just make `chunks` non generic and use `u64` directly in the implementation ########## File path: rust/arrow/src/util/bit_ops.rs ########## @@ -0,0 +1,407 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +use crate::buffer::Buffer; + +use bitvec::prelude::*; +use bitvec::slice::ChunksExact; + +use std::fmt::Debug; + +/// +/// Immutable bit slice representation of buffer data +#[derive(Debug)] +pub struct BufferBitSlice<'a> { + buffer_data: &'a [u8], + bit_slice: &'a BitSlice<LocalBits, u8>, +} + +impl<'a> BufferBitSlice<'a> { + /// + /// Creates a immutable bit slice over the given data + #[inline] + pub fn new(buffer_data: &'a [u8]) -> Self { + let bit_slice = BitSlice::<LocalBits, _>::from_slice(buffer_data).unwrap(); + + BufferBitSlice { + buffer_data, + bit_slice: &bit_slice, + } + } + + /// + /// Returns immutable view with the given offset in bits and length in bits. + /// This view have zero-copy representation over the actual data. + #[inline] + pub fn view(&self, offset_in_bits: usize, len_in_bits: usize) -> Self { Review comment: Stylistically if this were called `slice` it would keep the terminology more consistent and be easier to read. This function is effectively "slicing" the slice ########## File path: rust/arrow/src/util/bit_ops.rs ########## @@ -0,0 +1,407 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +use crate::buffer::Buffer; + +use bitvec::prelude::*; +use bitvec::slice::ChunksExact; + +use std::fmt::Debug; + +/// +/// Immutable bit slice representation of buffer data +#[derive(Debug)] +pub struct BufferBitSlice<'a> { + buffer_data: &'a [u8], + bit_slice: &'a BitSlice<LocalBits, u8>, +} + +impl<'a> BufferBitSlice<'a> { + /// + /// Creates a immutable bit slice over the given data + #[inline] + pub fn new(buffer_data: &'a [u8]) -> Self { + let bit_slice = BitSlice::<LocalBits, _>::from_slice(buffer_data).unwrap(); + + BufferBitSlice { + buffer_data, + bit_slice: &bit_slice, + } + } + + /// + /// Returns immutable view with the given offset in bits and length in bits. + /// This view have zero-copy representation over the actual data. + #[inline] + pub fn view(&self, offset_in_bits: usize, len_in_bits: usize) -> Self { + Self { + buffer_data: self.buffer_data, + bit_slice: &self.bit_slice[offset_in_bits..offset_in_bits + len_in_bits], + } + } + + /// + /// Returns bit chunks in native 64-bit allocation size. + /// Native representations in Arrow follows 64-bit convention. + /// Chunks can still be reinterpreted in any primitive type lower than u64. + #[inline] + pub fn chunks<T>(&self) -> BufferBitChunksExact<T> + where + T: BitMemory, + { + let offset_size_in_bits = 8 * std::mem::size_of::<T>(); + let chunks_exact = self.bit_slice.chunks_exact(offset_size_in_bits); + let remainder_bits = chunks_exact.remainder(); + let remainder: T = if remainder_bits.len() == 0 { + T::default() + } else { + remainder_bits.load::<T>() + }; + BufferBitChunksExact { + chunks_exact, + remainder, + remainder_len_in_bits: remainder_bits.len(), + } + } + + /// + /// Converts the bit view into the Buffer. + /// Buffer is always byte-aligned and well-aligned. + #[inline] + pub fn as_buffer(&self) -> Buffer { + Buffer::from(self.bit_slice.as_slice()) + } + + /// + /// Count ones in the given bit view + #[inline] + pub fn count_ones(&self) -> usize { + self.bit_slice.count_ones() + } + + /// + /// Count zeros in the given bit view + #[inline] + pub fn count_zeros(&self) -> usize { + self.bit_slice.count_zeros() + } + + /// + /// Get bit value at the given index in this bit view + #[inline] + pub fn get_bit(&self, index: usize) -> bool { + *unsafe { self.bit_slice.get_unchecked(index) } + } + + /// + /// Get bits in this view as vector of booleans + #[inline] + pub fn typed_bits(&self) -> Vec<bool> { + self.bit_slice.iter().map(|e| *e).collect() + } + + /// + /// Get manipulated data as byte slice + #[inline] + pub fn to_slice(&self) -> &[u8] { + self.bit_slice.as_slice() + } +} + +impl<'a> PartialEq for BufferBitSlice<'a> { + fn eq(&self, other: &Self) -> bool { + self.bit_slice == other.bit_slice + } +} + +/// +/// Conversion from mutable slice to immutable bit slice +impl<'a> From<&'a [u8]> for BufferBitSlice<'a> { + fn from(data: &'a [u8]) -> Self { + BufferBitSlice::new(data) + } +} + +/// +/// Mutable bit slice representation of buffer data Review comment: ```suggestion /// /// Mutable bit slice view of buffer data /// /// `BufferBitSliceMut` does not own any underlying data, but rather /// has methods for addressing and interacting with individual bits. ``` ########## File path: rust/arrow/src/util/bit_ops.rs ########## @@ -0,0 +1,407 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +use crate::buffer::Buffer; + +use bitvec::prelude::*; +use bitvec::slice::ChunksExact; + +use std::fmt::Debug; + +/// +/// Immutable bit slice representation of buffer data +#[derive(Debug)] +pub struct BufferBitSlice<'a> { + buffer_data: &'a [u8], + bit_slice: &'a BitSlice<LocalBits, u8>, +} + +impl<'a> BufferBitSlice<'a> { + /// + /// Creates a immutable bit slice over the given data + #[inline] + pub fn new(buffer_data: &'a [u8]) -> Self { + let bit_slice = BitSlice::<LocalBits, _>::from_slice(buffer_data).unwrap(); + + BufferBitSlice { + buffer_data, + bit_slice: &bit_slice, + } + } + + /// + /// Returns immutable view with the given offset in bits and length in bits. + /// This view have zero-copy representation over the actual data. + #[inline] + pub fn view(&self, offset_in_bits: usize, len_in_bits: usize) -> Self { + Self { + buffer_data: self.buffer_data, + bit_slice: &self.bit_slice[offset_in_bits..offset_in_bits + len_in_bits], + } + } + + /// + /// Returns bit chunks in native 64-bit allocation size. + /// Native representations in Arrow follows 64-bit convention. + /// Chunks can still be reinterpreted in any primitive type lower than u64. + #[inline] + pub fn chunks<T>(&self) -> BufferBitChunksExact<T> + where + T: BitMemory, + { + let offset_size_in_bits = 8 * std::mem::size_of::<T>(); + let chunks_exact = self.bit_slice.chunks_exact(offset_size_in_bits); + let remainder_bits = chunks_exact.remainder(); + let remainder: T = if remainder_bits.len() == 0 { + T::default() + } else { + remainder_bits.load::<T>() + }; + BufferBitChunksExact { + chunks_exact, + remainder, + remainder_len_in_bits: remainder_bits.len(), + } + } + + /// + /// Converts the bit view into the Buffer. + /// Buffer is always byte-aligned and well-aligned. + #[inline] + pub fn as_buffer(&self) -> Buffer { + Buffer::from(self.bit_slice.as_slice()) + } + + /// + /// Count ones in the given bit view + #[inline] + pub fn count_ones(&self) -> usize { + self.bit_slice.count_ones() + } + + /// + /// Count zeros in the given bit view + #[inline] + pub fn count_zeros(&self) -> usize { + self.bit_slice.count_zeros() + } + + /// + /// Get bit value at the given index in this bit view + #[inline] + pub fn get_bit(&self, index: usize) -> bool { + *unsafe { self.bit_slice.get_unchecked(index) } + } + + /// + /// Get bits in this view as vector of booleans + #[inline] + pub fn typed_bits(&self) -> Vec<bool> { + self.bit_slice.iter().map(|e| *e).collect() + } + + /// + /// Get manipulated data as byte slice + #[inline] + pub fn to_slice(&self) -> &[u8] { + self.bit_slice.as_slice() + } +} + +impl<'a> PartialEq for BufferBitSlice<'a> { + fn eq(&self, other: &Self) -> bool { + self.bit_slice == other.bit_slice + } +} + +/// +/// Conversion from mutable slice to immutable bit slice +impl<'a> From<&'a [u8]> for BufferBitSlice<'a> { + fn from(data: &'a [u8]) -> Self { + BufferBitSlice::new(data) + } +} + +/// +/// Mutable bit slice representation of buffer data +#[derive(Debug)] +pub struct BufferBitSliceMut<'a> { + bit_slice: &'a mut BitSlice<LocalBits, u8>, +} + +impl<'a> BufferBitSliceMut<'a> { + /// + /// Creates a mutable bit slice over the given data + #[inline] + pub fn new(buffer_data: &'a mut [u8]) -> Self { + let bit_slice = BitSlice::<LocalBits, _>::from_slice_mut(buffer_data).unwrap(); + + BufferBitSliceMut { bit_slice } + } + + /// + /// Returns mutable view with the given offset in bits and length in bits. + /// This view have zero-copy representation over the actual data. + #[inline] + pub fn view(&'a mut self, offset_in_bits: usize, len_in_bits: usize) -> Self { + Self { + bit_slice: &mut self.bit_slice[offset_in_bits..offset_in_bits + len_in_bits], + } + } + + /// + /// Set given bit at the position to a given value + #[inline] + pub fn set_bit_all(&mut self, value: bool) { + self.bit_slice.set_all(value) + } + + /// + /// Count zeros in the given bit view + #[inline] + pub fn set_bit(&mut self, index: usize, value: bool) { + unsafe { self.bit_slice.set_unchecked(index, value) } + } + + /// + /// Converts the bit view into the Buffer. Review comment: ```suggestion /// Converts the bit view into a Buffer. ``` ########## File path: rust/arrow/src/util/bit_ops.rs ########## @@ -0,0 +1,407 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +use crate::buffer::Buffer; + +use bitvec::prelude::*; +use bitvec::slice::ChunksExact; + +use std::fmt::Debug; + +/// +/// Immutable bit slice representation of buffer data +#[derive(Debug)] +pub struct BufferBitSlice<'a> { + buffer_data: &'a [u8], + bit_slice: &'a BitSlice<LocalBits, u8>, +} + +impl<'a> BufferBitSlice<'a> { + /// + /// Creates a immutable bit slice over the given data + #[inline] + pub fn new(buffer_data: &'a [u8]) -> Self { + let bit_slice = BitSlice::<LocalBits, _>::from_slice(buffer_data).unwrap(); + + BufferBitSlice { + buffer_data, + bit_slice: &bit_slice, + } + } + + /// + /// Returns immutable view with the given offset in bits and length in bits. + /// This view have zero-copy representation over the actual data. + #[inline] + pub fn view(&self, offset_in_bits: usize, len_in_bits: usize) -> Self { + Self { + buffer_data: self.buffer_data, + bit_slice: &self.bit_slice[offset_in_bits..offset_in_bits + len_in_bits], + } + } + + /// + /// Returns bit chunks in native 64-bit allocation size. + /// Native representations in Arrow follows 64-bit convention. + /// Chunks can still be reinterpreted in any primitive type lower than u64. + #[inline] + pub fn chunks<T>(&self) -> BufferBitChunksExact<T> + where + T: BitMemory, + { + let offset_size_in_bits = 8 * std::mem::size_of::<T>(); + let chunks_exact = self.bit_slice.chunks_exact(offset_size_in_bits); + let remainder_bits = chunks_exact.remainder(); + let remainder: T = if remainder_bits.len() == 0 { + T::default() + } else { + remainder_bits.load::<T>() + }; + BufferBitChunksExact { + chunks_exact, + remainder, + remainder_len_in_bits: remainder_bits.len(), + } + } + + /// + /// Converts the bit view into the Buffer. + /// Buffer is always byte-aligned and well-aligned. + #[inline] + pub fn as_buffer(&self) -> Buffer { + Buffer::from(self.bit_slice.as_slice()) + } + + /// + /// Count ones in the given bit view + #[inline] + pub fn count_ones(&self) -> usize { + self.bit_slice.count_ones() + } + + /// + /// Count zeros in the given bit view + #[inline] + pub fn count_zeros(&self) -> usize { + self.bit_slice.count_zeros() + } + + /// + /// Get bit value at the given index in this bit view + #[inline] + pub fn get_bit(&self, index: usize) -> bool { + *unsafe { self.bit_slice.get_unchecked(index) } + } + + /// + /// Get bits in this view as vector of booleans + #[inline] + pub fn typed_bits(&self) -> Vec<bool> { + self.bit_slice.iter().map(|e| *e).collect() + } + + /// + /// Get manipulated data as byte slice + #[inline] + pub fn to_slice(&self) -> &[u8] { + self.bit_slice.as_slice() + } +} + +impl<'a> PartialEq for BufferBitSlice<'a> { + fn eq(&self, other: &Self) -> bool { + self.bit_slice == other.bit_slice + } +} + +/// +/// Conversion from mutable slice to immutable bit slice +impl<'a> From<&'a [u8]> for BufferBitSlice<'a> { + fn from(data: &'a [u8]) -> Self { + BufferBitSlice::new(data) + } +} + +/// +/// Mutable bit slice representation of buffer data +#[derive(Debug)] +pub struct BufferBitSliceMut<'a> { + bit_slice: &'a mut BitSlice<LocalBits, u8>, +} + +impl<'a> BufferBitSliceMut<'a> { + /// + /// Creates a mutable bit slice over the given data + #[inline] + pub fn new(buffer_data: &'a mut [u8]) -> Self { + let bit_slice = BitSlice::<LocalBits, _>::from_slice_mut(buffer_data).unwrap(); + + BufferBitSliceMut { bit_slice } + } + + /// + /// Returns mutable view with the given offset in bits and length in bits. + /// This view have zero-copy representation over the actual data. + #[inline] + pub fn view(&'a mut self, offset_in_bits: usize, len_in_bits: usize) -> Self { + Self { + bit_slice: &mut self.bit_slice[offset_in_bits..offset_in_bits + len_in_bits], + } + } + + /// + /// Set given bit at the position to a given value Review comment: ```suggestion /// Sets all bits in this slice to the given value ``` ########## File path: rust/arrow/src/util/bit_ops.rs ########## @@ -0,0 +1,407 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +use crate::buffer::Buffer; + +use bitvec::prelude::*; +use bitvec::slice::ChunksExact; + +use std::fmt::Debug; + +/// +/// Immutable bit slice representation of buffer data +#[derive(Debug)] +pub struct BufferBitSlice<'a> { + buffer_data: &'a [u8], + bit_slice: &'a BitSlice<LocalBits, u8>, +} + +impl<'a> BufferBitSlice<'a> { + /// + /// Creates a immutable bit slice over the given data + #[inline] + pub fn new(buffer_data: &'a [u8]) -> Self { + let bit_slice = BitSlice::<LocalBits, _>::from_slice(buffer_data).unwrap(); + + BufferBitSlice { + buffer_data, + bit_slice: &bit_slice, + } + } + + /// + /// Returns immutable view with the given offset in bits and length in bits. + /// This view have zero-copy representation over the actual data. + #[inline] + pub fn view(&self, offset_in_bits: usize, len_in_bits: usize) -> Self { + Self { + buffer_data: self.buffer_data, + bit_slice: &self.bit_slice[offset_in_bits..offset_in_bits + len_in_bits], + } + } + + /// + /// Returns bit chunks in native 64-bit allocation size. + /// Native representations in Arrow follows 64-bit convention. + /// Chunks can still be reinterpreted in any primitive type lower than u64. + #[inline] + pub fn chunks<T>(&self) -> BufferBitChunksExact<T> + where + T: BitMemory, + { + let offset_size_in_bits = 8 * std::mem::size_of::<T>(); + let chunks_exact = self.bit_slice.chunks_exact(offset_size_in_bits); + let remainder_bits = chunks_exact.remainder(); + let remainder: T = if remainder_bits.len() == 0 { + T::default() + } else { + remainder_bits.load::<T>() + }; + BufferBitChunksExact { + chunks_exact, + remainder, + remainder_len_in_bits: remainder_bits.len(), + } + } + + /// + /// Converts the bit view into the Buffer. + /// Buffer is always byte-aligned and well-aligned. + #[inline] + pub fn as_buffer(&self) -> Buffer { + Buffer::from(self.bit_slice.as_slice()) + } + + /// + /// Count ones in the given bit view + #[inline] + pub fn count_ones(&self) -> usize { + self.bit_slice.count_ones() + } + + /// + /// Count zeros in the given bit view + #[inline] + pub fn count_zeros(&self) -> usize { + self.bit_slice.count_zeros() + } + + /// + /// Get bit value at the given index in this bit view + #[inline] + pub fn get_bit(&self, index: usize) -> bool { + *unsafe { self.bit_slice.get_unchecked(index) } + } + + /// + /// Get bits in this view as vector of booleans + #[inline] + pub fn typed_bits(&self) -> Vec<bool> { + self.bit_slice.iter().map(|e| *e).collect() + } + + /// + /// Get manipulated data as byte slice + #[inline] + pub fn to_slice(&self) -> &[u8] { + self.bit_slice.as_slice() + } +} + +impl<'a> PartialEq for BufferBitSlice<'a> { + fn eq(&self, other: &Self) -> bool { + self.bit_slice == other.bit_slice + } +} + +/// +/// Conversion from mutable slice to immutable bit slice +impl<'a> From<&'a [u8]> for BufferBitSlice<'a> { + fn from(data: &'a [u8]) -> Self { + BufferBitSlice::new(data) + } +} + +/// +/// Mutable bit slice representation of buffer data +#[derive(Debug)] +pub struct BufferBitSliceMut<'a> { + bit_slice: &'a mut BitSlice<LocalBits, u8>, +} + +impl<'a> BufferBitSliceMut<'a> { + /// + /// Creates a mutable bit slice over the given data + #[inline] + pub fn new(buffer_data: &'a mut [u8]) -> Self { + let bit_slice = BitSlice::<LocalBits, _>::from_slice_mut(buffer_data).unwrap(); + + BufferBitSliceMut { bit_slice } + } + + /// + /// Returns mutable view with the given offset in bits and length in bits. + /// This view have zero-copy representation over the actual data. + #[inline] + pub fn view(&'a mut self, offset_in_bits: usize, len_in_bits: usize) -> Self { + Self { + bit_slice: &mut self.bit_slice[offset_in_bits..offset_in_bits + len_in_bits], + } + } + + /// + /// Set given bit at the position to a given value + #[inline] + pub fn set_bit_all(&mut self, value: bool) { + self.bit_slice.set_all(value) + } + + /// + /// Count zeros in the given bit view + #[inline] + pub fn set_bit(&mut self, index: usize, value: bool) { + unsafe { self.bit_slice.set_unchecked(index, value) } + } + + /// + /// Converts the bit view into the Buffer. + /// Buffer is always byte-aligned and well-aligned. + #[inline] + pub fn as_buffer(&self) -> Buffer { + Buffer::from(self.bit_slice.as_slice()) + } + + /// + /// Count ones in the given bit view + #[inline] + pub fn count_ones(&self) -> usize { + self.bit_slice.count_ones() + } + + /// + /// Count zeros in the given bit view + #[inline] + pub fn count_zeros(&self) -> usize { + self.bit_slice.count_zeros() + } + + /// + /// Get bit value at the given index in this bit view + #[inline] + pub fn get_bit(&self, index: usize) -> bool { + *unsafe { self.bit_slice.get_unchecked(index) } + } + + /// + /// Get bits in this view as vector of booleans + #[inline] + pub fn typed_bits(&self) -> Vec<bool> { + self.bit_slice.iter().map(|e| *e).collect() + } + + /// + /// Get manipulated data as byte slice + #[inline] + pub fn to_slice(&self) -> &[u8] { + self.bit_slice.as_slice() + } +} + +impl<'a> PartialEq for BufferBitSliceMut<'a> { + fn eq(&self, other: &Self) -> bool { + self.bit_slice == other.bit_slice + } +} + +/// +/// Conversion from mutable slice to mutable bit slice +impl<'a> From<&'a mut [u8]> for BufferBitSliceMut<'a> { + fn from(data: &'a mut [u8]) -> Self { + BufferBitSliceMut::new(data) + } +} + +/// +/// Exact chunk view over the bit slice +#[derive(Clone, Debug)] Review comment: ```suggestion /// /// The view is represented as some number of aligned T-sized chunks, /// followed by some number of remainder bits #[derive(Clone, Debug)] ``` ########## File path: rust/arrow/src/util/bit_ops.rs ########## @@ -0,0 +1,407 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +use crate::buffer::Buffer; + +use bitvec::prelude::*; +use bitvec::slice::ChunksExact; + +use std::fmt::Debug; + +/// +/// Immutable bit slice representation of buffer data +#[derive(Debug)] +pub struct BufferBitSlice<'a> { + buffer_data: &'a [u8], Review comment: It looks to me like `buffer_data` is not read -- I wonder if we could omit it and just keep `bit_slice` ########## File path: rust/arrow/src/util/utils.rs ########## @@ -0,0 +1,119 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +//! Utils for working with bits + +#[cfg(feature = "simd")] +use packed_simd::u8x64; + +/// Returns the nearest number that is `>=` than `num` and is a multiple of 64 +#[inline] +pub fn round_upto_multiple_of_64(num: usize) -> usize { Review comment: This code seems ~ the same as what is in https://github.com/apache/arrow/blob/master/rust/arrow/src/util/bit_util.rs and this PR removes that module [here](https://github.com/apache/arrow/pull/8664/files#diff-10923f5e6e9ac82323735492c134734372787553fee0801d6bb12afccdb3c147L19) but this PR doesn't seem to chagne bit_util.rs -- maybe I am missing something. Or perhaps you meant to delete `bit_util.rs`? ########## File path: rust/arrow/src/util/bit_ops.rs ########## @@ -0,0 +1,407 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +use crate::buffer::Buffer; + +use bitvec::prelude::*; +use bitvec::slice::ChunksExact; + +use std::fmt::Debug; + +/// +/// Immutable bit slice representation of buffer data +#[derive(Debug)] +pub struct BufferBitSlice<'a> { + buffer_data: &'a [u8], + bit_slice: &'a BitSlice<LocalBits, u8>, +} + +impl<'a> BufferBitSlice<'a> { + /// + /// Creates a immutable bit slice over the given data + #[inline] + pub fn new(buffer_data: &'a [u8]) -> Self { + let bit_slice = BitSlice::<LocalBits, _>::from_slice(buffer_data).unwrap(); + + BufferBitSlice { + buffer_data, + bit_slice: &bit_slice, + } + } + + /// + /// Returns immutable view with the given offset in bits and length in bits. + /// This view have zero-copy representation over the actual data. + #[inline] + pub fn view(&self, offset_in_bits: usize, len_in_bits: usize) -> Self { + Self { + buffer_data: self.buffer_data, + bit_slice: &self.bit_slice[offset_in_bits..offset_in_bits + len_in_bits], + } + } + + /// + /// Returns bit chunks in native 64-bit allocation size. + /// Native representations in Arrow follows 64-bit convention. + /// Chunks can still be reinterpreted in any primitive type lower than u64. + #[inline] + pub fn chunks<T>(&self) -> BufferBitChunksExact<T> + where + T: BitMemory, + { + let offset_size_in_bits = 8 * std::mem::size_of::<T>(); + let chunks_exact = self.bit_slice.chunks_exact(offset_size_in_bits); + let remainder_bits = chunks_exact.remainder(); + let remainder: T = if remainder_bits.len() == 0 { + T::default() + } else { + remainder_bits.load::<T>() + }; + BufferBitChunksExact { + chunks_exact, + remainder, + remainder_len_in_bits: remainder_bits.len(), + } + } + + /// + /// Converts the bit view into the Buffer. + /// Buffer is always byte-aligned and well-aligned. Review comment: I am a little confused about this comment. What is the difference between `byte-aligned` and `well-aligned`? ########## File path: rust/arrow/src/util/bit_ops.rs ########## @@ -0,0 +1,407 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +use crate::buffer::Buffer; + +use bitvec::prelude::*; +use bitvec::slice::ChunksExact; + +use std::fmt::Debug; + +/// +/// Immutable bit slice representation of buffer data +#[derive(Debug)] +pub struct BufferBitSlice<'a> { + buffer_data: &'a [u8], + bit_slice: &'a BitSlice<LocalBits, u8>, +} + +impl<'a> BufferBitSlice<'a> { + /// + /// Creates a immutable bit slice over the given data + #[inline] + pub fn new(buffer_data: &'a [u8]) -> Self { + let bit_slice = BitSlice::<LocalBits, _>::from_slice(buffer_data).unwrap(); + + BufferBitSlice { + buffer_data, + bit_slice: &bit_slice, + } + } + + /// + /// Returns immutable view with the given offset in bits and length in bits. + /// This view have zero-copy representation over the actual data. + #[inline] + pub fn view(&self, offset_in_bits: usize, len_in_bits: usize) -> Self { + Self { + buffer_data: self.buffer_data, + bit_slice: &self.bit_slice[offset_in_bits..offset_in_bits + len_in_bits], + } + } + + /// + /// Returns bit chunks in native 64-bit allocation size. + /// Native representations in Arrow follows 64-bit convention. + /// Chunks can still be reinterpreted in any primitive type lower than u64. + #[inline] + pub fn chunks<T>(&self) -> BufferBitChunksExact<T> + where + T: BitMemory, + { + let offset_size_in_bits = 8 * std::mem::size_of::<T>(); + let chunks_exact = self.bit_slice.chunks_exact(offset_size_in_bits); + let remainder_bits = chunks_exact.remainder(); + let remainder: T = if remainder_bits.len() == 0 { + T::default() + } else { + remainder_bits.load::<T>() + }; + BufferBitChunksExact { + chunks_exact, + remainder, + remainder_len_in_bits: remainder_bits.len(), + } + } + + /// + /// Converts the bit view into the Buffer. + /// Buffer is always byte-aligned and well-aligned. + #[inline] + pub fn as_buffer(&self) -> Buffer { + Buffer::from(self.bit_slice.as_slice()) + } + + /// + /// Count ones in the given bit view + #[inline] + pub fn count_ones(&self) -> usize { + self.bit_slice.count_ones() + } + + /// + /// Count zeros in the given bit view + #[inline] + pub fn count_zeros(&self) -> usize { + self.bit_slice.count_zeros() + } + + /// + /// Get bit value at the given index in this bit view + #[inline] + pub fn get_bit(&self, index: usize) -> bool { + *unsafe { self.bit_slice.get_unchecked(index) } + } + + /// + /// Get bits in this view as vector of booleans + #[inline] + pub fn typed_bits(&self) -> Vec<bool> { + self.bit_slice.iter().map(|e| *e).collect() + } + + /// + /// Get manipulated data as byte slice + #[inline] + pub fn to_slice(&self) -> &[u8] { + self.bit_slice.as_slice() + } +} + +impl<'a> PartialEq for BufferBitSlice<'a> { + fn eq(&self, other: &Self) -> bool { + self.bit_slice == other.bit_slice + } +} + +/// +/// Conversion from mutable slice to immutable bit slice +impl<'a> From<&'a [u8]> for BufferBitSlice<'a> { + fn from(data: &'a [u8]) -> Self { + BufferBitSlice::new(data) + } +} + +/// +/// Mutable bit slice representation of buffer data +#[derive(Debug)] +pub struct BufferBitSliceMut<'a> { + bit_slice: &'a mut BitSlice<LocalBits, u8>, +} + +impl<'a> BufferBitSliceMut<'a> { + /// + /// Creates a mutable bit slice over the given data + #[inline] + pub fn new(buffer_data: &'a mut [u8]) -> Self { + let bit_slice = BitSlice::<LocalBits, _>::from_slice_mut(buffer_data).unwrap(); + + BufferBitSliceMut { bit_slice } + } + + /// + /// Returns mutable view with the given offset in bits and length in bits. + /// This view have zero-copy representation over the actual data. + #[inline] + pub fn view(&'a mut self, offset_in_bits: usize, len_in_bits: usize) -> Self { + Self { + bit_slice: &mut self.bit_slice[offset_in_bits..offset_in_bits + len_in_bits], + } + } + + /// + /// Set given bit at the position to a given value + #[inline] + pub fn set_bit_all(&mut self, value: bool) { + self.bit_slice.set_all(value) + } + + /// + /// Count zeros in the given bit view Review comment: ```suggestion /// Set given bit at the position to a given value ``` ########## File path: rust/arrow/src/util/bit_ops.rs ########## @@ -0,0 +1,407 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +use crate::buffer::Buffer; + +use bitvec::prelude::*; +use bitvec::slice::ChunksExact; + +use std::fmt::Debug; + +/// +/// Immutable bit slice representation of buffer data Review comment: ```suggestion /// /// Immutable bit slice view of `Buffer` data. /// /// `BufferBitSlice` does not own any underlying data, but rather wraps references /// to the underlying data in a `Buffer` and has methods for addressing and interacting with /// individual bits ``` ########## File path: rust/arrow/src/util/bit_ops.rs ########## @@ -0,0 +1,407 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +use crate::buffer::Buffer; + +use bitvec::prelude::*; +use bitvec::slice::ChunksExact; + +use std::fmt::Debug; + +/// +/// Immutable bit slice representation of buffer data +#[derive(Debug)] +pub struct BufferBitSlice<'a> { + buffer_data: &'a [u8], + bit_slice: &'a BitSlice<LocalBits, u8>, +} + +impl<'a> BufferBitSlice<'a> { + /// + /// Creates a immutable bit slice over the given data + #[inline] + pub fn new(buffer_data: &'a [u8]) -> Self { + let bit_slice = BitSlice::<LocalBits, _>::from_slice(buffer_data).unwrap(); + + BufferBitSlice { + buffer_data, + bit_slice: &bit_slice, + } + } + + /// + /// Returns immutable view with the given offset in bits and length in bits. + /// This view have zero-copy representation over the actual data. + #[inline] + pub fn view(&self, offset_in_bits: usize, len_in_bits: usize) -> Self { + Self { + buffer_data: self.buffer_data, + bit_slice: &self.bit_slice[offset_in_bits..offset_in_bits + len_in_bits], + } + } + + /// + /// Returns bit chunks in native 64-bit allocation size. + /// Native representations in Arrow follows 64-bit convention. + /// Chunks can still be reinterpreted in any primitive type lower than u64. + #[inline] + pub fn chunks<T>(&self) -> BufferBitChunksExact<T> + where + T: BitMemory, + { + let offset_size_in_bits = 8 * std::mem::size_of::<T>(); + let chunks_exact = self.bit_slice.chunks_exact(offset_size_in_bits); + let remainder_bits = chunks_exact.remainder(); + let remainder: T = if remainder_bits.len() == 0 { + T::default() + } else { + remainder_bits.load::<T>() + }; + BufferBitChunksExact { + chunks_exact, + remainder, + remainder_len_in_bits: remainder_bits.len(), + } + } + + /// + /// Converts the bit view into the Buffer. + /// Buffer is always byte-aligned and well-aligned. + #[inline] + pub fn as_buffer(&self) -> Buffer { + Buffer::from(self.bit_slice.as_slice()) + } + + /// + /// Count ones in the given bit view + #[inline] + pub fn count_ones(&self) -> usize { + self.bit_slice.count_ones() + } + + /// + /// Count zeros in the given bit view + #[inline] + pub fn count_zeros(&self) -> usize { + self.bit_slice.count_zeros() + } + + /// + /// Get bit value at the given index in this bit view + #[inline] + pub fn get_bit(&self, index: usize) -> bool { + *unsafe { self.bit_slice.get_unchecked(index) } + } + + /// + /// Get bits in this view as vector of booleans + #[inline] + pub fn typed_bits(&self) -> Vec<bool> { + self.bit_slice.iter().map(|e| *e).collect() + } + + /// + /// Get manipulated data as byte slice + #[inline] + pub fn to_slice(&self) -> &[u8] { + self.bit_slice.as_slice() + } +} + +impl<'a> PartialEq for BufferBitSlice<'a> { + fn eq(&self, other: &Self) -> bool { + self.bit_slice == other.bit_slice + } +} + +/// +/// Conversion from mutable slice to immutable bit slice +impl<'a> From<&'a [u8]> for BufferBitSlice<'a> { + fn from(data: &'a [u8]) -> Self { + BufferBitSlice::new(data) + } +} + +/// +/// Mutable bit slice representation of buffer data +#[derive(Debug)] +pub struct BufferBitSliceMut<'a> { + bit_slice: &'a mut BitSlice<LocalBits, u8>, +} + +impl<'a> BufferBitSliceMut<'a> { + /// + /// Creates a mutable bit slice over the given data + #[inline] + pub fn new(buffer_data: &'a mut [u8]) -> Self { + let bit_slice = BitSlice::<LocalBits, _>::from_slice_mut(buffer_data).unwrap(); + + BufferBitSliceMut { bit_slice } + } + + /// + /// Returns mutable view with the given offset in bits and length in bits. + /// This view have zero-copy representation over the actual data. + #[inline] + pub fn view(&'a mut self, offset_in_bits: usize, len_in_bits: usize) -> Self { + Self { + bit_slice: &mut self.bit_slice[offset_in_bits..offset_in_bits + len_in_bits], + } + } + + /// + /// Set given bit at the position to a given value + #[inline] + pub fn set_bit_all(&mut self, value: bool) { + self.bit_slice.set_all(value) + } + + /// + /// Count zeros in the given bit view + #[inline] + pub fn set_bit(&mut self, index: usize, value: bool) { + unsafe { self.bit_slice.set_unchecked(index, value) } + } + + /// + /// Converts the bit view into the Buffer. + /// Buffer is always byte-aligned and well-aligned. Review comment: same question as above about "is there a difference between `byte-aligned` and `well-aligned`"? ########## File path: rust/arrow/src/util/bit_ops.rs ########## @@ -0,0 +1,407 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +use crate::buffer::Buffer; + +use bitvec::prelude::*; +use bitvec::slice::ChunksExact; + +use std::fmt::Debug; + +/// +/// Immutable bit slice representation of buffer data +#[derive(Debug)] +pub struct BufferBitSlice<'a> { + buffer_data: &'a [u8], + bit_slice: &'a BitSlice<LocalBits, u8>, +} + +impl<'a> BufferBitSlice<'a> { + /// + /// Creates a immutable bit slice over the given data + #[inline] + pub fn new(buffer_data: &'a [u8]) -> Self { + let bit_slice = BitSlice::<LocalBits, _>::from_slice(buffer_data).unwrap(); + + BufferBitSlice { + buffer_data, + bit_slice: &bit_slice, + } + } + + /// + /// Returns immutable view with the given offset in bits and length in bits. + /// This view have zero-copy representation over the actual data. + #[inline] + pub fn view(&self, offset_in_bits: usize, len_in_bits: usize) -> Self { + Self { + buffer_data: self.buffer_data, + bit_slice: &self.bit_slice[offset_in_bits..offset_in_bits + len_in_bits], + } + } + + /// + /// Returns bit chunks in native 64-bit allocation size. + /// Native representations in Arrow follows 64-bit convention. + /// Chunks can still be reinterpreted in any primitive type lower than u64. + #[inline] + pub fn chunks<T>(&self) -> BufferBitChunksExact<T> + where + T: BitMemory, + { + let offset_size_in_bits = 8 * std::mem::size_of::<T>(); + let chunks_exact = self.bit_slice.chunks_exact(offset_size_in_bits); + let remainder_bits = chunks_exact.remainder(); + let remainder: T = if remainder_bits.len() == 0 { + T::default() + } else { + remainder_bits.load::<T>() + }; + BufferBitChunksExact { + chunks_exact, + remainder, + remainder_len_in_bits: remainder_bits.len(), + } + } + + /// + /// Converts the bit view into the Buffer. Review comment: ```suggestion /// Converts the bit view into a Buffer. ``` ########## File path: rust/arrow/src/util/bit_ops.rs ########## @@ -0,0 +1,407 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +use crate::buffer::Buffer; + +use bitvec::prelude::*; +use bitvec::slice::ChunksExact; + +use std::fmt::Debug; + +/// +/// Immutable bit slice representation of buffer data +#[derive(Debug)] +pub struct BufferBitSlice<'a> { + buffer_data: &'a [u8], + bit_slice: &'a BitSlice<LocalBits, u8>, +} + +impl<'a> BufferBitSlice<'a> { + /// + /// Creates a immutable bit slice over the given data + #[inline] + pub fn new(buffer_data: &'a [u8]) -> Self { + let bit_slice = BitSlice::<LocalBits, _>::from_slice(buffer_data).unwrap(); + + BufferBitSlice { + buffer_data, + bit_slice: &bit_slice, + } + } + + /// + /// Returns immutable view with the given offset in bits and length in bits. + /// This view have zero-copy representation over the actual data. + #[inline] + pub fn view(&self, offset_in_bits: usize, len_in_bits: usize) -> Self { + Self { + buffer_data: self.buffer_data, + bit_slice: &self.bit_slice[offset_in_bits..offset_in_bits + len_in_bits], + } + } + + /// + /// Returns bit chunks in native 64-bit allocation size. + /// Native representations in Arrow follows 64-bit convention. + /// Chunks can still be reinterpreted in any primitive type lower than u64. + #[inline] + pub fn chunks<T>(&self) -> BufferBitChunksExact<T> + where + T: BitMemory, + { + let offset_size_in_bits = 8 * std::mem::size_of::<T>(); + let chunks_exact = self.bit_slice.chunks_exact(offset_size_in_bits); + let remainder_bits = chunks_exact.remainder(); + let remainder: T = if remainder_bits.len() == 0 { + T::default() + } else { + remainder_bits.load::<T>() + }; + BufferBitChunksExact { + chunks_exact, + remainder, + remainder_len_in_bits: remainder_bits.len(), + } + } + + /// + /// Converts the bit view into the Buffer. + /// Buffer is always byte-aligned and well-aligned. + #[inline] + pub fn as_buffer(&self) -> Buffer { + Buffer::from(self.bit_slice.as_slice()) + } + + /// + /// Count ones in the given bit view + #[inline] + pub fn count_ones(&self) -> usize { + self.bit_slice.count_ones() + } + + /// + /// Count zeros in the given bit view + #[inline] + pub fn count_zeros(&self) -> usize { + self.bit_slice.count_zeros() + } + + /// + /// Get bit value at the given index in this bit view + #[inline] + pub fn get_bit(&self, index: usize) -> bool { + *unsafe { self.bit_slice.get_unchecked(index) } + } + + /// + /// Get bits in this view as vector of booleans + #[inline] + pub fn typed_bits(&self) -> Vec<bool> { + self.bit_slice.iter().map(|e| *e).collect() + } + + /// + /// Get manipulated data as byte slice + #[inline] + pub fn to_slice(&self) -> &[u8] { + self.bit_slice.as_slice() + } +} + +impl<'a> PartialEq for BufferBitSlice<'a> { + fn eq(&self, other: &Self) -> bool { + self.bit_slice == other.bit_slice + } +} + +/// +/// Conversion from mutable slice to immutable bit slice +impl<'a> From<&'a [u8]> for BufferBitSlice<'a> { + fn from(data: &'a [u8]) -> Self { + BufferBitSlice::new(data) + } +} + +/// +/// Mutable bit slice representation of buffer data +#[derive(Debug)] +pub struct BufferBitSliceMut<'a> { + bit_slice: &'a mut BitSlice<LocalBits, u8>, +} + +impl<'a> BufferBitSliceMut<'a> { + /// + /// Creates a mutable bit slice over the given data + #[inline] + pub fn new(buffer_data: &'a mut [u8]) -> Self { + let bit_slice = BitSlice::<LocalBits, _>::from_slice_mut(buffer_data).unwrap(); + + BufferBitSliceMut { bit_slice } + } + + /// + /// Returns mutable view with the given offset in bits and length in bits. + /// This view have zero-copy representation over the actual data. + #[inline] + pub fn view(&'a mut self, offset_in_bits: usize, len_in_bits: usize) -> Self { + Self { + bit_slice: &mut self.bit_slice[offset_in_bits..offset_in_bits + len_in_bits], + } + } + + /// + /// Set given bit at the position to a given value + #[inline] + pub fn set_bit_all(&mut self, value: bool) { + self.bit_slice.set_all(value) + } + + /// + /// Count zeros in the given bit view + #[inline] + pub fn set_bit(&mut self, index: usize, value: bool) { + unsafe { self.bit_slice.set_unchecked(index, value) } + } + + /// + /// Converts the bit view into the Buffer. + /// Buffer is always byte-aligned and well-aligned. + #[inline] + pub fn as_buffer(&self) -> Buffer { + Buffer::from(self.bit_slice.as_slice()) + } + + /// + /// Count ones in the given bit view + #[inline] + pub fn count_ones(&self) -> usize { + self.bit_slice.count_ones() + } + + /// + /// Count zeros in the given bit view + #[inline] + pub fn count_zeros(&self) -> usize { + self.bit_slice.count_zeros() + } + + /// + /// Get bit value at the given index in this bit view + #[inline] + pub fn get_bit(&self, index: usize) -> bool { + *unsafe { self.bit_slice.get_unchecked(index) } + } + + /// + /// Get bits in this view as vector of booleans + #[inline] + pub fn typed_bits(&self) -> Vec<bool> { + self.bit_slice.iter().map(|e| *e).collect() + } + + /// + /// Get manipulated data as byte slice + #[inline] + pub fn to_slice(&self) -> &[u8] { + self.bit_slice.as_slice() + } +} + +impl<'a> PartialEq for BufferBitSliceMut<'a> { + fn eq(&self, other: &Self) -> bool { + self.bit_slice == other.bit_slice + } +} + +/// +/// Conversion from mutable slice to mutable bit slice +impl<'a> From<&'a mut [u8]> for BufferBitSliceMut<'a> { + fn from(data: &'a mut [u8]) -> Self { + BufferBitSliceMut::new(data) + } +} + +/// +/// Exact chunk view over the bit slice +#[derive(Clone, Debug)] +pub struct BufferBitChunksExact<'a, T> +where + T: BitMemory, Review comment: In general my questions about keeping this generic over `T` vs hard coding `u64` remains here too ########## File path: rust/arrow/src/compute/kernels/comparison.rs ########## @@ -570,27 +570,26 @@ where )); } - let num_bytes = bit_util::ceil(left_len, 8); + let num_bytes = utils::ceil(left_len, 8); let not_both_null_bit_buffer = match combine_option_bitmap(left.data_ref(), right.data_ref(), left_len)? { Some(buff) => buff, None => new_all_set_buffer(num_bytes), }; - let not_both_null_bitmap = not_both_null_bit_buffer.data(); + let _not_both_null_bitmap = not_both_null_bit_buffer.data(); Review comment: I wonder if there is some reason to keep this statement? It seems unused ########## File path: rust/arrow/src/buffer.rs ########## @@ -258,39 +259,52 @@ impl Buffer { /// Returns a slice of this buffer starting at a certain bit offset. /// If the offset is byte-aligned the returned buffer is a shallow clone, /// otherwise a new buffer is allocated and filled with a copy of the bits in the range. - pub fn bit_slice(&self, offset: usize, len: usize) -> Self { - if offset % 8 == 0 && len % 8 == 0 { - return self.slice(offset / 8); + #[inline] + pub fn bit_view(&self, offset_in_bits: usize, len_in_bits: usize) -> Self { Review comment: the fact that it can *copy* the underlying data even though it is called `bit_view` is confusing to me Maybe we could call it `as_aligned()` or something ########## File path: rust/arrow/src/array/array_list.rs ########## @@ -711,8 +722,9 @@ mod tests { assert_eq!(1, sliced_array.offset()); assert_eq!(2, sliced_array.null_count()); + let null_bit_slice = BufferBitSliceMut::new(&mut null_bits); Review comment: this might be able to be `BitBufferSlice` as it doesn't need to be mutable ########## File path: rust/arrow/src/util/bit_ops.rs ########## @@ -0,0 +1,407 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +use crate::buffer::Buffer; + +use bitvec::prelude::*; +use bitvec::slice::ChunksExact; + +use std::fmt::Debug; + +/// +/// Immutable bit slice representation of buffer data +#[derive(Debug)] +pub struct BufferBitSlice<'a> { + buffer_data: &'a [u8], + bit_slice: &'a BitSlice<LocalBits, u8>, +} + +impl<'a> BufferBitSlice<'a> { + /// + /// Creates a immutable bit slice over the given data + #[inline] + pub fn new(buffer_data: &'a [u8]) -> Self { + let bit_slice = BitSlice::<LocalBits, _>::from_slice(buffer_data).unwrap(); + + BufferBitSlice { + buffer_data, + bit_slice: &bit_slice, + } + } + + /// + /// Returns immutable view with the given offset in bits and length in bits. + /// This view have zero-copy representation over the actual data. + #[inline] + pub fn view(&self, offset_in_bits: usize, len_in_bits: usize) -> Self { + Self { + buffer_data: self.buffer_data, + bit_slice: &self.bit_slice[offset_in_bits..offset_in_bits + len_in_bits], + } + } + + /// + /// Returns bit chunks in native 64-bit allocation size. + /// Native representations in Arrow follows 64-bit convention. + /// Chunks can still be reinterpreted in any primitive type lower than u64. + #[inline] + pub fn chunks<T>(&self) -> BufferBitChunksExact<T> + where + T: BitMemory, + { + let offset_size_in_bits = 8 * std::mem::size_of::<T>(); + let chunks_exact = self.bit_slice.chunks_exact(offset_size_in_bits); + let remainder_bits = chunks_exact.remainder(); + let remainder: T = if remainder_bits.len() == 0 { + T::default() + } else { + remainder_bits.load::<T>() + }; + BufferBitChunksExact { + chunks_exact, + remainder, + remainder_len_in_bits: remainder_bits.len(), + } + } + + /// + /// Converts the bit view into the Buffer. + /// Buffer is always byte-aligned and well-aligned. + #[inline] + pub fn as_buffer(&self) -> Buffer { + Buffer::from(self.bit_slice.as_slice()) + } + + /// + /// Count ones in the given bit view + #[inline] + pub fn count_ones(&self) -> usize { + self.bit_slice.count_ones() + } + + /// + /// Count zeros in the given bit view + #[inline] + pub fn count_zeros(&self) -> usize { + self.bit_slice.count_zeros() + } + + /// + /// Get bit value at the given index in this bit view + #[inline] + pub fn get_bit(&self, index: usize) -> bool { + *unsafe { self.bit_slice.get_unchecked(index) } + } + + /// + /// Get bits in this view as vector of booleans + #[inline] + pub fn typed_bits(&self) -> Vec<bool> { + self.bit_slice.iter().map(|e| *e).collect() + } + + /// + /// Get manipulated data as byte slice + #[inline] + pub fn to_slice(&self) -> &[u8] { + self.bit_slice.as_slice() + } +} + +impl<'a> PartialEq for BufferBitSlice<'a> { + fn eq(&self, other: &Self) -> bool { + self.bit_slice == other.bit_slice + } +} + +/// +/// Conversion from mutable slice to immutable bit slice +impl<'a> From<&'a [u8]> for BufferBitSlice<'a> { + fn from(data: &'a [u8]) -> Self { + BufferBitSlice::new(data) + } +} + +/// +/// Mutable bit slice representation of buffer data +#[derive(Debug)] +pub struct BufferBitSliceMut<'a> { + bit_slice: &'a mut BitSlice<LocalBits, u8>, +} + +impl<'a> BufferBitSliceMut<'a> { + /// + /// Creates a mutable bit slice over the given data + #[inline] + pub fn new(buffer_data: &'a mut [u8]) -> Self { + let bit_slice = BitSlice::<LocalBits, _>::from_slice_mut(buffer_data).unwrap(); + + BufferBitSliceMut { bit_slice } + } + + /// + /// Returns mutable view with the given offset in bits and length in bits. + /// This view have zero-copy representation over the actual data. + #[inline] + pub fn view(&'a mut self, offset_in_bits: usize, len_in_bits: usize) -> Self { + Self { + bit_slice: &mut self.bit_slice[offset_in_bits..offset_in_bits + len_in_bits], + } + } + + /// + /// Set given bit at the position to a given value + #[inline] + pub fn set_bit_all(&mut self, value: bool) { + self.bit_slice.set_all(value) + } + + /// + /// Count zeros in the given bit view + #[inline] + pub fn set_bit(&mut self, index: usize, value: bool) { + unsafe { self.bit_slice.set_unchecked(index, value) } + } + + /// + /// Converts the bit view into the Buffer. + /// Buffer is always byte-aligned and well-aligned. + #[inline] + pub fn as_buffer(&self) -> Buffer { + Buffer::from(self.bit_slice.as_slice()) + } + + /// + /// Count ones in the given bit view + #[inline] + pub fn count_ones(&self) -> usize { + self.bit_slice.count_ones() + } + + /// + /// Count zeros in the given bit view + #[inline] + pub fn count_zeros(&self) -> usize { + self.bit_slice.count_zeros() + } + + /// + /// Get bit value at the given index in this bit view + #[inline] + pub fn get_bit(&self, index: usize) -> bool { + *unsafe { self.bit_slice.get_unchecked(index) } + } + + /// + /// Get bits in this view as vector of booleans + #[inline] + pub fn typed_bits(&self) -> Vec<bool> { + self.bit_slice.iter().map(|e| *e).collect() + } + + /// + /// Get manipulated data as byte slice + #[inline] + pub fn to_slice(&self) -> &[u8] { + self.bit_slice.as_slice() + } +} + +impl<'a> PartialEq for BufferBitSliceMut<'a> { + fn eq(&self, other: &Self) -> bool { + self.bit_slice == other.bit_slice + } +} + +/// +/// Conversion from mutable slice to mutable bit slice +impl<'a> From<&'a mut [u8]> for BufferBitSliceMut<'a> { + fn from(data: &'a mut [u8]) -> Self { + BufferBitSliceMut::new(data) + } +} + +/// +/// Exact chunk view over the bit slice +#[derive(Clone, Debug)] +pub struct BufferBitChunksExact<'a, T> +where + T: BitMemory, +{ + chunks_exact: ChunksExact<'a, LocalBits, u8>, + remainder: T, + remainder_len_in_bits: usize, +} + +impl<'a, T> BufferBitChunksExact<'a, T> +where + T: BitMemory, +{ + /// + /// Returns remainder bit length from the exact chunk iterator + #[inline(always)] + pub fn remainder_bit_len(&self) -> usize { + self.remainder_len_in_bits + } + + /// + /// Returns the remainder bits interpreted as given type. + #[inline(always)] + pub fn remainder_bits(&self) -> T { + self.remainder + } + + /// + /// Interprets underlying chunk's view's bits as a given type. + #[inline(always)] + pub fn interpret(self) -> impl Iterator<Item = T> + 'a + where + T: BitMemory, + { + self.chunks_exact.map(|e| e.load::<T>()) + } + + /// + /// Returns underlying iterator as it is + #[inline(always)] + pub fn iter(&self) -> &ChunksExact<'a, LocalBits, u8> { + &self.chunks_exact + } +} + +/// +/// Implements consuming iterator for exact chunk iterator +impl<'a, T> IntoIterator for BufferBitChunksExact<'a, T> +where + T: BitMemory, +{ + type Item = &'a BitSlice<LocalBits, u8>; + type IntoIter = ChunksExact<'a, LocalBits, u8>; + + fn into_iter(self) -> Self::IntoIter { + self.chunks_exact + } +} + +#[cfg(all(test, target_endian = "little"))] +mod tests_bit_slices_little_endian { + use super::*; + use crate::datatypes::ToByteSlice; + + #[test] + fn test_bit_slice_iter_aligned() { + let input: &[u8] = &[0, 1, 2, 3, 4, 5, 6, 7]; + let buffer: Buffer = Buffer::from(input); + + let bit_slice = buffer.bit_slice(); + let result = bit_slice.chunks().interpret().collect::<Vec<u64>>(); + + assert_eq!(vec![0x0706050403020100], result); + } + + #[test] + fn test_bit_slice_iter_unaligned() { + let input: &[u8] = &[ + 0b00000000, 0b00000001, 0b00000010, 0b00000100, 0b00001000, 0b00010000, + 0b00100000, 0b01000000, 0b11111111, + ]; + let buffer: Buffer = Buffer::from(input); + + let bit_slice = buffer.bit_slice().view(4, 64); + let chunks = bit_slice.chunks::<u64>(); + + assert_eq!(0, chunks.remainder_bit_len()); + assert_eq!(0, chunks.remainder_bits()); + + let result = chunks.interpret().collect::<Vec<u64>>(); + + assert_eq!( + vec![0b1111_01000000_00100000_00010000_00001000_00000100_00000010_00000001_0000], + result + ); + } + + #[test] + fn test_bit_slice_iter_unaligned_remainder_1_byte() { + let input: &[u8] = &[ + 0b00000000, 0b00000001, 0b00000010, 0b00000100, 0b00001000, 0b00010000, + 0b00100000, 0b01000000, 0b11111111, + ]; + let buffer: Buffer = Buffer::from(input); + + let bit_slice = buffer.bit_slice().view(4, 66); + let chunks = bit_slice.chunks::<u64>(); + + assert_eq!(2, chunks.remainder_bit_len()); + assert_eq!(0b00000011, chunks.remainder_bits()); + + let result = chunks.interpret().collect::<Vec<u64>>(); + + assert_eq!( + vec![0b1111_01000000_00100000_00010000_00001000_00000100_00000010_00000001_0000], Review comment: I don't know if it is intended, but it is strange to me that the resoult can you explain why the expected answer here is the same as when the view is `view(4, 64): https://github.com/apache/arrow/pull/8664/files#diff-715ddfbc534281523a73117d3bf4986d69d8a375dd320bc19f83298d3ba7ebd6R333 Maybe you can change the bit pattern so there the extra two bits result in an additional `11` in the high place ########## File path: rust/arrow/src/compute/kernels/aggregate.rs ########## @@ -219,24 +223,27 @@ where let data_chunks = data.chunks_exact(64); let remainder = data_chunks.remainder(); - let bit_chunks = buffer.bit_chunks(array.offset(), array.len()); + let bit_slice = buffer.bit_slice().view(array.offset(), array.len()); + let bit_chunks = bit_slice.chunks::<u64>(); let remainder_bits = bit_chunks.remainder_bits(); - data_chunks.zip(bit_chunks).for_each(|(chunk, mut mask)| { - // split chunks further into slices corresponding to the vector length - // the compiler is able to unroll this inner loop and remove bounds checks - // since the outer chunk size (64) is always a multiple of the number of lanes - chunk.chunks_exact(T::lanes()).for_each(|chunk| { - let zero = T::init(T::default_value()); - let vecmask = T::mask_from_u64(mask); - let chunk = T::load(&chunk); - let blended = T::mask_select(vecmask, chunk, zero); - - vector_sum = vector_sum + blended; - - mask = mask >> T::lanes(); + data_chunks + .zip(bit_chunks.interpret()) Review comment: `interpret` was confusing to me - it is making an `iter` over the underlying type `T` (`u64` in this case) -- maybe calling `interpret` like `to_native_iter` or something would be clearer. ---------------------------------------------------------------- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: [email protected]
