lance_bitpacking/bitpacker_internal/
mod.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright The Lance Authors
3
4// Lance-owned u32 SIMD bitpacking kernels.
5//
6// This is adapted from the MIT-licensed `bitpacking` crate so Lance can keep the
7// hot FTS posting-list bitpacking implementation inside lance-bitpacking while
8// preserving byte compatibility with the existing 4x format.
9
10#![allow(dead_code)]
11#![allow(unsafe_op_in_unsafe_fn)]
12#![allow(clippy::redundant_pub_crate)]
13#![allow(clippy::upper_case_acronyms)]
14#![allow(clippy::use_self)]
15
16#[macro_use]
17mod macros;
18
19mod bitpacker4x;
20mod bitpacker8x;
21
22pub use bitpacker4x::BitPacker4x;
23pub use bitpacker8x::BitPacker8x;
24
25pub(crate) trait Available {
26    fn available() -> bool;
27}
28
29pub(crate) trait UnsafeBitPacker {
30    const BLOCK_LEN: usize;
31
32    unsafe fn compress(decompressed: &[u32], compressed: &mut [u8], num_bits: u8) -> usize;
33
34    unsafe fn compress_sorted(
35        initial: u32,
36        decompressed: &[u32],
37        compressed: &mut [u8],
38        num_bits: u8,
39    ) -> usize;
40
41    unsafe fn compress_strictly_sorted(
42        initial: Option<u32>,
43        decompressed: &[u32],
44        compressed: &mut [u8],
45        num_bits: u8,
46    ) -> usize;
47
48    unsafe fn decompress(compressed: &[u8], decompressed: &mut [u32], num_bits: u8) -> usize;
49
50    unsafe fn decompress_sorted(
51        initial: u32,
52        compressed: &[u8],
53        decompressed: &mut [u32],
54        num_bits: u8,
55    ) -> usize;
56
57    unsafe fn decompress_strictly_sorted(
58        initial: Option<u32>,
59        compressed: &[u8],
60        decompressed: &mut [u32],
61        num_bits: u8,
62    ) -> usize;
63
64    unsafe fn num_bits(decompressed: &[u32]) -> u8;
65
66    unsafe fn num_bits_sorted(initial: u32, decompressed: &[u32]) -> u8;
67
68    unsafe fn num_bits_strictly_sorted(initial: Option<u32>, decompressed: &[u32]) -> u8;
69}
70
71/// Block bitpacker for fixed-size `u32` blocks.
72///
73/// Implementations own runtime SIMD dispatch and use caller-provided buffers.
74/// Packed bytes are stable for a given implementation and bit width.
75pub trait BitPacker: Sized + Clone + Copy {
76    /// Number of `u32` values in one physical block.
77    const BLOCK_LEN: usize;
78
79    /// Select the best supported implementation for the current CPU.
80    ///
81    /// Lance uses SIMD backends when available and falls back to a scalar
82    /// backend otherwise, matching the existing allocation-free call shape used
83    /// by the upstream `bitpacking` crate.
84    fn new() -> Self;
85
86    /// Compress one full block of raw values into `compressed`.
87    fn compress(&self, decompressed: &[u32], compressed: &mut [u8], num_bits: u8) -> usize;
88
89    /// Delta-compress one full non-decreasing block into `compressed`.
90    fn compress_sorted(
91        &self,
92        initial: u32,
93        decompressed: &[u32],
94        compressed: &mut [u8],
95        num_bits: u8,
96    ) -> usize;
97
98    /// Delta-compress one full strictly increasing block into `compressed`.
99    fn compress_strictly_sorted(
100        &self,
101        initial: Option<u32>,
102        decompressed: &[u32],
103        compressed: &mut [u8],
104        num_bits: u8,
105    ) -> usize;
106
107    /// Decompress one raw block into `decompressed`.
108    fn decompress(&self, compressed: &[u8], decompressed: &mut [u32], num_bits: u8) -> usize;
109
110    /// Decompress one delta-compressed non-decreasing block.
111    fn decompress_sorted(
112        &self,
113        initial: u32,
114        compressed: &[u8],
115        decompressed: &mut [u32],
116        num_bits: u8,
117    ) -> usize;
118
119    /// Decompress one delta-compressed strictly increasing block.
120    fn decompress_strictly_sorted(
121        &self,
122        initial: Option<u32>,
123        compressed: &[u8],
124        decompressed: &mut [u32],
125        num_bits: u8,
126    ) -> usize;
127
128    /// Return the minimum bit width needed to represent a full raw block.
129    fn num_bits(&self, decompressed: &[u32]) -> u8;
130
131    /// Return the minimum bit width needed to represent deltas in a full block.
132    fn num_bits_sorted(&self, initial: u32, decompressed: &[u32]) -> u8;
133
134    /// Return the minimum bit width needed to represent strict deltas in a full block.
135    fn num_bits_strictly_sorted(&self, initial: Option<u32>, decompressed: &[u32]) -> u8;
136
137    /// Return the byte size of one compressed block at `num_bits`.
138    #[must_use]
139    fn compressed_block_size(num_bits: u8) -> usize {
140        Self::BLOCK_LEN * num_bits as usize / 8
141    }
142}
143
144#[inline]
145fn most_significant_bit(value: u32) -> u8 {
146    (u32::BITS - value.leading_zeros()) as u8
147}
lance_bitpacking/bitpacker_internal/mod.rs

lance_bitpacking/bitpacker_internal/
mod.rs
