compressed_intvec/variable/
traits.rs

1//! Core traits for the `variable` module.
2//!
3//! This module defines the [`Storable`] trait, which provides a generic
4//! abstraction over the integer types that can be stored in an [`IntVec`].
5//!
6//! [`IntVec`]: crate::variable::IntVec
7
8use dsi_bitstream::prelude::{ToInt, ToNat};
9
10/// A trait for types that can be stored in a variable-length compressed vector.
11///
12/// This trait provides a bidirectional, lossless conversion between a user-facing
13/// element type (e.g., `i32`, `u16`) and the `u64` representation required by the
14/// underlying compression codecs.
15///
16/// # Zig-Zag Encoding for Signed Integers
17///
18/// For signed integer types, this trait's implementation automatically applies
19/// **Zig-Zag encoding**. This is a transformation that maps signed
20/// integers to unsigned integers in a way that is efficient for variable-length
21/// compression.
22///
23/// It works by mapping small positive and negative numbers to small unsigned
24/// numbers, as shown below:
25///
26/// | Original Signed | Zig-Zag Unsigned |
27/// |-----------------|------------------|
28/// | 0               | 0                |
29/// | -1              | 1                |
30/// | 1               | 2                |
31/// | -2              | 3                |
32/// | 2               | 4                |
33/// | ...             | ...              |
34///
35/// This ensures that values close to zero, whether positive or negative, are
36/// represented by small unsigned integers, which can then be compressed into
37/// very few bits by the variable-length codecs. 
38pub trait Storable: Sized + Copy {
39    /// Converts the element into its `u64` storage representation.
40    ///
41    /// For unsigned types, this is a simple cast. For signed types, this
42    /// applies Zig-Zag encoding.
43    fn to_word(self) -> u64;
44    /// Converts a `u64` storage word back into the element type.
45    ///
46    /// For unsigned types, this is a simple cast. For signed types, this
47    /// decodes the Zig-Zag encoded value.
48    fn from_word(word: u64) -> Self;
49}
50
51macro_rules! impl_storable_for_unsigned {
52    ($($T:ty),*) => {$(
53        impl Storable for $T {
54            #[inline(always)]
55            fn to_word(self) -> u64 {
56                self as u64
57            }
58
59            #[inline(always)]
60            fn from_word(word: u64) -> Self {
61                word as Self
62            }
63        }
64    )*};
65}
66
67macro_rules! impl_storable_for_signed {
68    ($($T:ty),*) => {$(
69        impl Storable for $T {
70            #[inline(always)]
71            fn to_word(self) -> u64 {
72                self.to_nat().into()
73            }
74
75            #[inline(always)]
76            fn from_word(word: u64) -> Self {
77                ToInt::to_int(word)
78                    .try_into()
79                    .unwrap_or_else(|_| panic!("Value out of range for type"))
80            }
81        }
82    )*};
83}
84
85// Implement `Storable` for all primitive integer types.
86impl_storable_for_unsigned!(u8, u16, u32, u64);
87impl_storable_for_signed!(i8, i16, i32, i64);
compressed_intvec/variable/traits.rs

compressed_intvec/variable/
traits.rs
