steel_core/chunk_saver/
bit_pack.rs

1//! Bit packing utilities for chunk persistence.
2//!
3//! Uses only power-of-2 bit widths (1, 2, 4, 8, 16) to avoid entries spanning
4//! u64 boundaries, which simplifies encoding/decoding and improves performance.
5
6/// Calculates the number of bits needed to represent indices into a palette.
7/// Only returns power-of-2 values: 1, 2, 4, 8, or 16.
8///
9/// Returns `None` for homogeneous containers (palette length 0 or 1).
10#[must_use]
11pub const fn bits_for_palette_len(palette_len: usize) -> Option<u8> {
12    match palette_len {
13        0..=1 => None, // Homogeneous, no bit array needed
14        2 => Some(1),
15        3..=4 => Some(2),
16        5..=16 => Some(4),
17        17..=256 => Some(8),
18        _ => Some(16),
19    }
20}
21
22/// Packs indices into a compact bit array using power-of-2 bit widths.
23///
24/// # Arguments
25/// * `indices` - The indices to pack (values must fit in `bits` bits)
26/// * `bits` - Bits per entry (must be 1, 2, 4, 8, or 16)
27///
28/// # Panics
29/// Panics if `bits` is not a power of 2 or is greater than 16.
30#[must_use]
31pub fn pack_indices(indices: &[u32], bits: u8) -> Box<[u64]> {
32    debug_assert!(
33        bits.is_power_of_two() && bits <= 16,
34        "bits must be 1, 2, 4, 8, or 16"
35    );
36    if indices.is_empty() {
37        return Box::new([]);
38    }
39    let bits = bits as usize;
40    let values_per_u64 = 64 / bits;
41    let num_u64s = indices.len().div_ceil(values_per_u64);
42    let mut data = vec![0u64; num_u64s];
43    for (i, chunk) in indices.chunks(values_per_u64).enumerate() {
44        let mut word = 0u64;
45        for (j, &index) in chunk.iter().enumerate() {
46            word |= u64::from(index) << (j * bits);
47        }
48        data[i] = word;
49    }
50    data.into_boxed_slice()
51}
52
53/// Unpacks indices from a compact bit array.
54///
55/// # Arguments
56/// * `data` - The packed bit array
57/// * `bits` - Bits per entry (must be 1, 2, 4, 8, or 16)
58///
59/// # Panics
60/// Panics if `bits` is not a power of 2 or is greater than 16.
61#[inline]
62pub fn unpack_indices(data: &[u64], bits: u8) -> impl Iterator<Item = u32> {
63    let bits = bits as usize;
64    let mask = (1u64 << bits) - 1;
65    let values_per_u64 = 64 / bits;
66    data.iter().flat_map(move |&word| {
67        (0..values_per_u64).map(move |j| ((word >> (j * bits)) & mask) as u32)
68    })
69}
70
71#[cfg(test)]
72mod tests {
73    use super::*;
74
75    #[test]
76    fn test_bits_for_palette_len() {
77        assert_eq!(bits_for_palette_len(0), None);
78        assert_eq!(bits_for_palette_len(1), None);
79        assert_eq!(bits_for_palette_len(2), Some(1));
80        assert_eq!(bits_for_palette_len(3), Some(2));
81        assert_eq!(bits_for_palette_len(4), Some(2));
82        assert_eq!(bits_for_palette_len(5), Some(4));
83        assert_eq!(bits_for_palette_len(16), Some(4));
84        assert_eq!(bits_for_palette_len(17), Some(8));
85        assert_eq!(bits_for_palette_len(256), Some(8));
86        assert_eq!(bits_for_palette_len(257), Some(16));
87    }
88
89    #[test]
90    fn test_pack_unpack_roundtrip() {
91        for bits in [1, 2, 4, 8, 16] {
92            let max_value = (1u32 << bits) - 1;
93            let indices: Vec<u32> = (0..100).map(|i| i % (max_value + 1)).collect();
94
95            let packed = pack_indices(&indices, bits);
96            let unpacked: Vec<u32> = unpack_indices(&packed, bits).take(indices.len()).collect();
97
98            assert_eq!(indices, unpacked, "Failed for bits={bits}");
99        }
100    }
101
102    #[test]
103    fn test_pack_4096_entries() {
104        // Simulate a chunk section with 4096 blocks
105        let indices: Vec<u32> = (0..4096).map(|i| (i % 16) as u32).collect();
106
107        let packed = pack_indices(&indices, 4);
108        assert_eq!(packed.len(), 4096 / 16); // 16 values per u64 with 4 bits
109
110        let unpacked: Vec<u32> = unpack_indices(&packed, 4).take(4096).collect();
111        assert_eq!(indices, unpacked);
112    }
113}
steel_core/chunk_saver/bit_pack.rs

steel_core/chunk_saver/
bit_pack.rs
