bitpacking/
lib.rs

1// We could auto-include the README here to avoid duplicating documentation,
2//   #![doc = include_str!("../README.md")]
3// but at the moment that seems a bit too long(?),
4// so for now only do it during testing to validate README's examples.
5#![cfg_attr(doctest, doc = include_str!("../README.md"))]
6
7/*!  # Fast Bitpacking algorithms
8
9This crate is a **Rust port of [Daniel Lemire's simdcomp C library](https://github.com/lemire/simdcomp)**.
10It contains different flavor of integers compression via bitpacking :  `BitPacker1x`, `BitPacker4x`, and `BitPacker8x`.
11
12Each produces different formats, and are incompatible one with another,
13and requires integers to be encoded in block of different size..
14
15`BitPacker4x` and `BitPacker8x` are designed specifically to leverage `SSE3`
16and `AVX2` instructions respectively.
17
18The library will fall back to a scalar implementation if these instruction
19sets are not available. For instance :
20- because your compilation target architecture is not `x86_64`
21- because the CPU you use is from an older generation
22
23I recommend using `BitPacker4x` if you are in doubt.
24
25See the [`BitPacker` trait](./trait.BitPacker.html) for example usage.
26
27*/
28
29#![allow(unused_unsafe)]
30#![warn(missing_docs)]
31
32use std::marker::Sized;
33
34#[cfg(test)]
35#[macro_use]
36pub(crate) mod tests;
37
38#[macro_use]
39mod macros;
40#[macro_use]
41mod macros_simple;
42
43trait Available {
44    fn available() -> bool;
45}
46
47trait UnsafeBitPacker {
48    const BLOCK_LEN: usize;
49    unsafe fn compress(decompressed: &[u32], compressed: &mut [u8], num_bits: u8) -> usize;
50    unsafe fn compress_sorted(
51        initial: u32,
52        decompressed: &[u32],
53        compressed: &mut [u8],
54        num_bits: u8,
55    ) -> usize;
56    unsafe fn compress_strictly_sorted(
57        initial: Option<u32>,
58        decompressed: &[u32],
59        compressed: &mut [u8],
60        num_bits: u8,
61    ) -> usize;
62    unsafe fn decompress(compressed: &[u8], decompressed: &mut [u32], num_bits: u8) -> usize;
63    unsafe fn decompress_sorted(
64        initial: u32,
65        compressed: &[u8],
66        decompressed: &mut [u32],
67        num_bits: u8,
68    ) -> usize;
69    unsafe fn decompress_strictly_sorted(
70        initial: Option<u32>,
71        compressed: &[u8],
72        decompressed: &mut [u32],
73        num_bits: u8,
74    ) -> usize;
75    unsafe fn num_bits(decompressed: &[u32]) -> u8;
76    unsafe fn num_bits_sorted(initial: u32, decompressed: &[u32]) -> u8;
77    unsafe fn num_bits_strictly_sorted(initial: Option<u32>, decompressed: &[u32]) -> u8;
78}
79
80/// # Examples without delta-encoding
81/// ```
82/// use bitpacking::{BitPacker4x, BitPacker};
83///
84/// # fn main() {
85/// # let my_data: Vec<u32> = vec![7, 7, 7, 7, 11, 10, 15, 13, 6, 5, 3, 14, 5, 7,
86/// #    15, 12, 1, 10, 8, 10, 12, 14, 13, 1, 10, 1, 1, 10, 4, 15, 12,
87/// #    1, 2, 0, 8, 5, 14, 5, 2, 4, 1, 6, 14, 13, 5, 10, 10, 1, 6, 4,
88/// #    1, 12, 1, 1, 5, 15, 15, 2, 8, 6, 4, 3, 10, 8, 8, 9, 2, 6, 10,
89/// #    5, 7, 9, 0, 13, 15, 5, 13, 10, 0, 2, 10, 14, 5, 9, 12, 8, 5, 10,
90/// #    8, 8, 10, 5, 13, 8, 11, 14, 7, 14, 4, 2, 9, 12, 14, 5, 15, 12, 0,
91/// #    12, 13, 3, 13, 5, 4, 15, 9, 8, 9, 3, 3, 3, 1, 12, 0, 6, 11, 11, 12, 4];
92///
93/// // Detects if `SSE3` is available on the current computed
94/// // and uses the best available implementation accordingly.
95/// let bitpacker = BitPacker4x::new();
96///
97/// // Computes the number of bits used for each integer in the blocks.
98/// // my_data is assumed to have a len of 128 for `BitPacker4x`.
99/// let num_bits: u8 = bitpacker.num_bits(&my_data);
100/// # assert_eq!(num_bits, 4);
101///
102/// // The compressed array will take exactly `num_bits * BitPacker4x::BLOCK_LEN / 8`.
103/// // But it is ok to have an output with a different len as long as it is larger
104/// // than this.
105/// let mut compressed = vec![0u8; 4 * BitPacker4x::BLOCK_LEN];
106///
107/// // Compress returns the len.
108/// let compressed_len = bitpacker.compress(&my_data, &mut compressed[..], num_bits);
109///
110/// assert_eq!((num_bits as usize) *  BitPacker4x::BLOCK_LEN / 8, compressed_len);
111///
112/// // Decompressing
113/// let mut decompressed = vec![0u32; BitPacker4x::BLOCK_LEN];
114/// bitpacker.decompress(&compressed[..compressed_len], &mut decompressed[..], num_bits);
115///
116/// assert_eq!(&my_data, &decompressed);
117/// # }
118/// ```
119///
120///
121///
122/// # Examples with delta-encoding
123///
124/// Delta-encoding makes it possible to store sorted integers in an efficient manner.
125/// Rather than encoding the integers directly, the interval (or deltas) between each of them
126/// are computed and then encoded.
127///
128/// Decoding then requires to first decode the deltas and then operate a cumulative sum (also called
129/// integration or prefix sum) on them.
130///
131/// ```
132/// use bitpacking::{BitPacker4x, BitPacker};
133///
134/// # fn main() {
135/// # let my_data: Vec<u32> = vec![0, 5, 6, 8, 12, 21, 30, 38,
136/// # 46, 52, 59, 61, 62, 62, 71, 71, 73, 74, 76,
137/// # 77, 80, 87, 96, 99, 105, 114, 119, 121, 128,
138/// # 133, 138, 145, 152, 161, 161, 166, 175, 176,
139/// # 180, 186, 189, 193, 202, 211, 220, 224, 229,
140/// # 238, 247, 255, 261, 267, 267, 268, 269, 269,
141/// # 270, 271, 279, 283, 285, 291, 297, 303, 305,
142/// # 309, 310, 315, 316, 316, 321, 324, 329, 337,
143/// # 339, 342, 350, 355, 364, 373, 382, 386, 392,
144/// # 400, 408, 414, 423, 431, 433, 436, 441, 444,
145/// # 445, 454, 463, 463, 465, 472, 474, 477, 480,
146/// # 488, 493, 496, 501, 503, 509, 515, 519, 526,
147/// # 526, 532, 539, 542, 542, 542, 549, 557, 565,
148/// # 566, 573, 578, 580, 581, 585, 588, 588, 591];
149///
150///
151/// // The initial value is used to compute the first delta.
152/// // In most use cases, you will be compressing long increasing
153/// // integer sequences.
154/// //
155/// // You should probably pass an initial value of `0u32` to the
156/// // first block if you do not have any information.
157/// //
158/// // When encoding the second block however, you will want to pass the last
159/// // value of the first block.
160/// let initial_value = 0u32;
161///
162/// let bitpacker = BitPacker4x::new();
163///
164/// let num_bits: u8 = bitpacker.num_bits_sorted(initial_value, &my_data);
165///
166/// // A block will take at most 4 bytes per-integers.
167/// let mut compressed = vec![0u8; 4 * BitPacker4x::BLOCK_LEN];
168///
169/// # assert_eq!(num_bits, 4);
170///
171/// let compressed_len = bitpacker.compress_sorted(initial_value, &my_data, &mut compressed[..], num_bits);
172///
173/// assert_eq!((num_bits as usize) *  BitPacker4x::BLOCK_LEN / 8, compressed_len);
174///
175/// // Decompressing
176/// let mut decompressed = vec![0u32; BitPacker4x::BLOCK_LEN];
177///
178/// // The initial value must be the same as the one passed
179/// // when compressing the block.
180/// bitpacker.decompress_sorted(initial_value, &compressed[..compressed_len], &mut decompressed[..], num_bits);
181///
182/// assert_eq!(&my_data, &decompressed);
183/// # }
184pub trait BitPacker: Sized + Clone + Copy {
185    /// Number of `u32` per compressed block
186    const BLOCK_LEN: usize;
187
188    /// Checks the available instructions set on the current
189    /// CPU and returns the best available implementation.
190    ///
191    /// Calling `.new()` is extremely cheap, and does not
192    /// require any heap allocation. It is *not* required to cache
193    /// its result too aggressively.
194    fn new() -> Self;
195
196    /// Compress a block of `u32`.
197    ///
198    /// Assumes that the integers are all lower than `2^num_bits`.
199    /// The result is undefined if they are larger.
200    ///
201    /// Returns the amount of bytes of the compressed block.
202    ///
203    /// # Panics
204    ///
205    /// - Panics if the compressed destination array is too small
206    /// - Panics if `decompressed` length is not exactly the `BLOCK_LEN`.
207    fn compress(&self, decompressed: &[u32], compressed: &mut [u8], num_bits: u8) -> usize;
208
209    /// Delta encode and compressed the `decompressed` array.
210    ///
211    /// Assumes that the elements in the `decompressed` array are sorted.
212    /// `initial` will be used to compute the first `delta`.
213    ///
214    /// # Panics
215    ///
216    /// - Panics if `initial` is greater than `decompressed[0]`
217    /// - Panics if `decompressed` is not sorted
218    /// - Panics if `decompressed`'s length is not exactly `BLOCK_LEN`
219    /// - Panics if `compressed` is not large enough to receive the compressed data
220    /// - Panics if the compressed destination array is too small.
221    ///
222    /// Returns the amount of bytes of the compressed block.
223    ///
224    /// # Panics
225    ///
226    /// - Panics if the compressed array is too short.
227    /// - Panics if the decompressed array is not exactly the `BLOCK_LEN`.
228    fn compress_sorted(
229        &self,
230        initial: u32,
231        decompressed: &[u32],
232        compressed: &mut [u8],
233        num_bits: u8,
234    ) -> usize;
235
236    /// Delta encode and compress the `decompressed` array.
237    ///
238    /// Assumes that the elements in the `decompressed` array are strictly
239    /// monotonous, that is, each element is strictly greater than the previous.
240    ///
241    /// This codec can be more efficient that the simply sorted compressor by up to one bit per
242    /// integer. This has an important impact on saturated or nearly saturated datasets (almost
243    /// every number appears in sequence), but isn't very different from the sorted compressor
244    /// on more sparse datasets.
245    ///
246    /// # Panics
247    ///
248    /// - Panics if `initial` is greater or equal to `decompressed[0]`
249    /// - Panics if `decompressed` isn't strictly monotonic
250    /// - Panics if `decompressed`'s length is not exactly `BLOCK_LEN`
251    /// - Panics if `compressed` is not large enough to receive the compressed data
252    ///
253    /// Returns the amount of bytes in the compressed block.
254    fn compress_strictly_sorted(
255        &self,
256        initial: Option<u32>,
257        decompressed: &[u32],
258        compressed: &mut [u8],
259        num_bits: u8,
260    ) -> usize;
261
262    /// Decompress the `compress` array to the `decompressed` array.
263    ///
264    /// Returns the amount of bytes that were consumed.
265    ///
266    /// # Panics
267    ///
268    /// Panics if the compressed array is too short, or the decompressed array is too short.
269    fn decompress(&self, compressed: &[u8], decompressed: &mut [u32], num_bits: u8) -> usize;
270
271    /// Decompress the`compress`array to the `decompressed` array.
272    /// The `compressed` array is assumed to have been delta-encoded and compressed.
273    ///
274    /// `initial` must be the value that was passed as the `initial` argument compressing
275    /// the block.
276    ///
277    /// Returns the amount of bytes that have been read.
278    ///
279    /// # Panics
280    ///
281    /// - Panics if the compressed array is too short to contain `BLOCK_LEN` elements
282    /// - Panics if the decompressed array is too short.
283    fn decompress_sorted(
284        &self,
285        initial: u32,
286        compressed: &[u8],
287        decompressed: &mut [u32],
288        num_bits: u8,
289    ) -> usize;
290
291    /// Decompress the`compress`array to the `decompressed` array.
292    /// The `compressed` array is assumed to have been strict-delta-encoded and compressed.
293    ///
294    /// `initial` must be the value that was passed as the `initial` argument compressing
295    /// the block.
296    ///
297    /// Returns the amount of bytes that have been read.
298    ///
299    /// # Panics
300    ///
301    /// - Panics if the compressed array is too short to contain `BLOCK_LEN` elements
302    /// - Panics if the decompressed array is too short.
303
304    fn decompress_strictly_sorted(
305        &self,
306        initial: Option<u32>,
307        compressed: &[u8],
308        decompressed: &mut [u32],
309        num_bits: u8,
310    ) -> usize;
311
312    /// Returns the minimum number of bits used to represent the largest integer in the
313    /// `decompressed` block.
314    ///
315    /// # Panics
316    ///
317    /// Panics if `decompressed`'s len is not exactly `BLOCK_LEN`.
318    fn num_bits(&self, decompressed: &[u32]) -> u8;
319
320    /// Returns the minimum number of bits used to represent the largest `delta` in the deltas in the
321    /// `decompressed` block.
322    ///
323    /// # Panics
324    ///
325    /// Panics if `decompressed`'s len is not exactly `BLOCK_LEN`.
326    fn num_bits_sorted(&self, initial: u32, decompressed: &[u32]) -> u8;
327
328    /// Returns the minimum number of bits used to represent the largest `delta-1` in the deltas in the
329    /// `decompressed` block.
330    ///
331    /// # Panics
332    ///
333    /// Panics if `decompressed`'s len is not exactly `BLOCK_LEN`.
334    fn num_bits_strictly_sorted(&self, initial: Option<u32>, decompressed: &[u32]) -> u8;
335
336    /// Returns the size of a compressed block.
337    #[must_use]
338    fn compressed_block_size(num_bits: u8) -> usize {
339        Self::BLOCK_LEN * (num_bits as usize) / 8
340    }
341}
342
343/// Returns the most significant bit.&self,
344fn most_significant_bit(v: u32) -> u8 {
345    if v == 0 {
346        0
347    } else {
348        32u8 - (v.leading_zeros() as u8)
349    }
350}
351
352#[cfg(all(feature = "bitpacker1x", any(test, not(debug_assertions))))]
353mod bitpacker1x;
354#[cfg(all(feature = "bitpacker4x", any(test, not(debug_assertions))))]
355mod bitpacker4x;
356
357#[cfg(all(feature = "bitpacker1x", debug_assertions))]
358mod bitpacker1x_simple;
359#[cfg(all(feature = "bitpacker4x", debug_assertions))]
360mod bitpacker4x_simple;
361
362#[cfg(feature = "bitpacker8x")]
363mod bitpacker8x;
364
365#[cfg(all(feature = "bitpacker1x", not(debug_assertions)))]
366pub use bitpacker1x::BitPacker1x;
367#[cfg(all(feature = "bitpacker1x", debug_assertions))]
368pub use bitpacker1x_simple::BitPacker1x;
369
370#[cfg(all(feature = "bitpacker4x", not(debug_assertions)))]
371pub use bitpacker4x::BitPacker4x;
372#[cfg(all(feature = "bitpacker4x", debug_assertions))]
373pub use bitpacker4x_simple::BitPacker4x;
374
375#[cfg(feature = "bitpacker8x")]
376pub use bitpacker8x::BitPacker8x;
377
378#[cfg(test)]
379mod tests_unit {
380    use super::*;
381
382    #[test]
383    #[should_panic(expected = "`decompressed`'s len is not `BLOCK_LEN=128`")]
384    fn test_num_bits_block_too_long() {
385        let bit_packer = BitPacker4x::new();
386        let v = vec![0u32; BitPacker4x::BLOCK_LEN + 1];
387        bit_packer.num_bits(&v[..]);
388    }
389
390    #[test]
391    #[should_panic(expected = "`decompressed`'s len is not `BLOCK_LEN=128`")]
392    fn test_num_bits_block_too_short() {
393        let bit_packer = BitPacker4x::new();
394        let v = vec![0u32; BitPacker4x::BLOCK_LEN - 1];
395        bit_packer.num_bits(&v[..]);
396    }
397}
398
399#[cfg(test)]
400mod functional_tests {
401    use crate::{BitPacker, BitPacker4x};
402    use proptest::prelude::*;
403
404    proptest! {
405        #[test]
406        #[ignore]
407        fn check_block(
408            values in prop::collection::vec(u32::arbitrary(), BitPacker4x::BLOCK_LEN),
409        ) {
410            let bit_packer = BitPacker4x::new();
411            let bit_width = bit_packer.num_bits(&*values);
412
413            let mut block = vec![0u8; BitPacker4x::compressed_block_size(bit_width)];
414            bit_packer.compress(&values, &mut block, bit_width);
415
416            let mut decoded_values = vec![0x10101010; BitPacker4x::BLOCK_LEN];
417            bit_packer.decompress(&block, &mut decoded_values, bit_width);
418
419            prop_assert_eq!(values, decoded_values);
420        }
421
422        #[ignore]
423        #[test]
424        fn check_sorted_block(
425            (values, init_value) in prop::collection::vec(u32::arbitrary(), BitPacker4x::BLOCK_LEN).prop_flat_map(|mut values| {
426                values.sort_unstable();
427                let min_value = values[0];
428                (Just(values), 0..=min_value)
429            }),
430        ) {
431            let bit_packer = BitPacker4x::new();
432            let bit_width = bit_packer.num_bits_sorted(init_value, &*values);
433
434            let mut block = vec![0u8; BitPacker4x::compressed_block_size(bit_width)];
435            bit_packer.compress_sorted(init_value, &values, &mut block, bit_width);
436
437            let mut decoded_values = vec![0x10101010; BitPacker4x::BLOCK_LEN];
438            bit_packer.decompress_sorted(init_value, &block, &mut decoded_values, bit_width);
439
440            prop_assert_eq!(values, decoded_values);
441        }
442    }
443}
bitpacking/lib.rs

bitpacking/
lib.rs
