bitpacking

bitpacking is a Rust port of Daniel Lemire’s simdcomp C library, providing fast integer compression and decompression through bit-packing. It groups u32 integers into fixed-size blocks and encodes each one using only the minimum number of bits needed to represent the block’s largest value, producing a compact byte representation with no entropy coding overhead.

The crate ships three interchangeable codecs — BitPacker1x, BitPacker4x, and BitPacker8x — trading block size for SIMD throughput via SSE3 and AVX2 instructions, with automatic runtime detection and a safe scalar fallback on unsupported CPUs. Dedicated sorted and strictly-sorted delta-encoding modes make it especially well suited to compressing postings lists, timestamps, and other monotonically increasing ID sequences common in search engines and databases.

What You Get

• Three codec widths — BitPacker1x (32-int blocks, scalar), BitPacker4x (128-int blocks, SSE3), and BitPacker8x (256-int blocks, AVX2) — so callers can trade block granularity for raw throughput.
• Automatic CPU feature detection via the Available trait, transparently falling back to a scalar implementation when SSE3/AVX2/NEON instructions aren’t present, so the same code runs correctly on any target.
• Sorted and strictly-sorted delta-encoding variants (compress_sorted, compress_strictly_sorted) that shave up to a full bit per integer off already-increasing sequences like IDs and timestamps.
• A fast debug-build path (macros_simple.rs) that swaps in a naive scalar codec during cargo build without optimizations, keeping local development compile times low despite the fully unrolled SIMD macro expansion used in release builds.
• A minimal, panic-documented public API (BitPacker trait) with compress/decompress/num_bits methods and explicit # Panics contracts instead of Result-based error handling, appropriate for a low-level codec.

Common Use Cases

• Compressing inverted-index postings lists in search engines, where sorted document IDs benefit from delta + bit-packing encoding.
• Shrinking timestamp or monotonic-ID columns in time-series and log-storage engines before writing to disk.
• Reducing memory footprint of large in-memory integer arrays (e.g. row IDs, offsets) in analytical or database engines.
• Any high-throughput pipeline needing to serialize bounded-range integers compactly without the overhead of general-purpose compression like LZ4.

Under The Hood

Architecture The crate exposes a single public trait, BitPacker (in lib.rs), implemented by three concrete types — BitPacker1x, BitPacker4x, BitPacker8x — each gated behind its own Cargo feature flag and split into a “simple” scalar implementation (bitpacker1x_simple.rs/bitpacker4x_simple.rs, used in debug builds) and an optimized SIMD implementation (bitpacker1x.rs/bitpacker4x.rs/bitpacker8x.rs, used in release builds), selected purely via cfg(debug_assertions). The actual encode/decode logic is generated by two parallel macro systems (macros.rs for SIMD, macros_simple.rs for scalar) that expand a pack_unpack_with_bits! macro across the full 0-32 bit-width range per block size, producing fully unrolled per-width functions hidden behind a private UnsafeBitPacker trait and dispatched at runtime through an Available::available() capability check. Because every SIMD backend implements the same UnsafeBitPacker contract that the public BitPacker trait wraps, changing that low-level interface would require touching every architecture-specific module (SSE3, AVX2, and their scalar counterparts) simultaneously.

Tech Stack Pure Rust (edition 2021) with a single required dependency, crunchy, used purely for compile-time loop unrolling; dev-dependencies are rand for generating test data, criterion for a custom harness = false benchmark target, and proptest for property-based round-trip testing. There’s no application runtime, database, or framework involved — this is a library crate distributed via crates.io/docs.rs, with feature flags (bitpacker1x, bitpacker4x, bitpacker8x, all enabled by default) controlling which SIMD-width codecs get compiled, and target_arch cfg gates selecting between x86_64 (SSE3/AVX2) and little-endian aarch64 (NEON) intrinsics.

Code Quality Tests live inline in lib.rs (tests_unit, functional_tests) plus a shared tests.rs helper providing generate_array and cross-implementation compatibility checks, combining conventional #[test]/#[should_panic] assertions with proptest!-driven property tests that verify compress/decompress round-trips across random bit widths — though the two heaviest property tests are marked #[ignore] and skipped by default cargo test runs. CI (GitHub Actions) runs cargo test on both x86_64 and arm64 runners, giving real cross-architecture coverage of the SIMD paths, though there’s no clippy or rustfmt enforcement visible in the workflow. Public methods document explicit # Panics contracts (invalid block length, undersized output buffer) rather than returning Result, a defensible choice for a low-level codec where misuse is a programmer error; the extensive unsafe blocks needed for SIMD intrinsics are not additionally checked with tools like Miri in CI.

What Makes It Unique This is a faithful, well-executed Rust port of Daniel Lemire’s simdcomp C library rather than a novel compression algorithm — its value is in the engineering: three interchangeable codec widths giving callers a granularity/throughput tradeoff, delta and strictly-sorted delta modes tuned specifically for the common case of compressing already-sorted integer sequences at up to one fewer bit per value than plain delta coding, and a debug/release macro split that keeps local compile times fast without sacrificing the fully unrolled SIMD codegen used in production builds. It’s a proven, standard technique executed with real multi-architecture SIMD coverage and safe scalar fallback that many hand-rolled bit-packing implementations skip.