Skip to main content

wasm_bitpack/
scalar.rs

1//! [`Scalar`] — the pure safe-Rust reference bit-packing implementation, always available.
2
3use crate::traits::BitPacker;
4
5/// Portable, safe-Rust reference implementation of [`BitPacker`].
6///
7/// Correct on every target, including under miri. Every other implementation in this
8/// crate is checked for byte-for-byte equivalence against `Scalar`'s output.
9///
10/// # Examples
11///
12/// ```
13/// use wasm_bitpack::{BitPacker, Scalar};
14///
15/// let values = vec![7u32; Scalar::BLOCK_LEN];
16/// let num_bits = Scalar::num_bits(&values);
17///
18/// let mut compressed = vec![0u8; (Scalar::BLOCK_LEN * num_bits as usize + 7) / 8];
19/// let written = Scalar::compress(&values, &mut compressed, num_bits);
20///
21/// let mut decompressed = vec![0u32; Scalar::BLOCK_LEN];
22/// Scalar::decompress(&compressed[..written], &mut decompressed, num_bits);
23/// assert_eq!(decompressed, values);
24/// ```
25pub struct Scalar;
26
27impl BitPacker for Scalar {
28    const BLOCK_LEN: usize = 128;
29
30    fn num_bits(decompressed: &[u32]) -> u8 {
31        let max = decompressed.iter().copied().max().unwrap_or(0);
32        bits_for_max_value(max)
33    }
34
35    fn compress(decompressed: &[u32], compressed: &mut [u8], num_bits: u8) -> usize {
36        assert_eq!(
37            decompressed.len(),
38            Self::BLOCK_LEN,
39            "decompressed.len() must be exactly BLOCK_LEN ({}), got {}",
40            Self::BLOCK_LEN,
41            decompressed.len()
42        );
43        check_num_bits(num_bits);
44        let needed = packed_len_bytes(Self::BLOCK_LEN, num_bits);
45        assert!(
46            compressed.len() >= needed,
47            "compressed buffer too small: need at least {needed} bytes, got {}",
48            compressed.len()
49        );
50
51        bitpack_interleaved_into(decompressed, compressed, num_bits)
52    }
53
54    fn decompress(compressed: &[u8], decompressed: &mut [u32], num_bits: u8) -> usize {
55        assert_eq!(
56            decompressed.len(),
57            Self::BLOCK_LEN,
58            "decompressed.len() must be exactly BLOCK_LEN ({}), got {}",
59            Self::BLOCK_LEN,
60            decompressed.len()
61        );
62        check_num_bits(num_bits);
63        let needed = packed_len_bytes(Self::BLOCK_LEN, num_bits);
64        assert!(
65            compressed.len() >= needed,
66            "compressed buffer too small: need at least {needed} bytes, got {}",
67            compressed.len()
68        );
69
70        bitunpack_interleaved_into(compressed, decompressed, num_bits)
71    }
72}
73
74/// The minimum number of bits needed to represent `max` (`0` for `max == 0`).
75///
76/// `pub(crate)` (not private) so [`crate::sorted`]'s `num_bits_sorted`/
77/// `num_bits_strictly_sorted` can reuse it for their own max-delta-to-bit-width conversion,
78/// instead of a second copy of the same `leading_zeros` trick.
79#[allow(clippy::cast_possible_truncation)] // `32 - leading_zeros()` is always in 0..=32
80pub(crate) fn bits_for_max_value(max: u32) -> u8 {
81    (32 - max.leading_zeros()) as u8
82}
83
84/// Panics unless `num_bits` is in the valid `1..=32` range.
85///
86/// Shared between [`Scalar`], and the [`pack`](crate::pack)/[`unpack`](crate::unpack)
87/// wrapper, so every entry point rejects an out-of-range bit width with the same message.
88pub(crate) fn check_num_bits(num_bits: u8) {
89    assert!(
90        (1..=32).contains(&num_bits),
91        "num_bits must be in 1..=32, got {num_bits}"
92    );
93}
94
95/// The number of bytes needed to tightly bit-pack `len` values at `num_bits` bits each.
96pub(crate) fn packed_len_bytes(len: usize, num_bits: u8) -> usize {
97    let total_bits = len as u64 * u64::from(num_bits);
98    ((total_bits + 7) / 8) as usize
99}
100
101/// Tightly bit-packs `values` into `out` at `num_bits` bits per value (LSB-first: value
102/// `i`'s bit `0` is the `(i * num_bits)`-th bit of the output stream, counting from the
103/// least-significant bit of `out[0]`), returning the number of bytes written.
104///
105/// No length restriction — this is the primitive both [`Scalar::compress`] (exact
106/// `BLOCK_LEN` blocks) and the [`pack`](crate::pack) wrapper's partial-block tail build on.
107///
108/// Trusts its caller: `out` must already be verified to be at least
109/// `packed_len_bytes(values.len(), num_bits)` bytes, and `num_bits` must already be
110/// verified to be in `1..=32`.
111#[allow(clippy::cast_possible_truncation)] // `acc & 0xff` always fits in a u8
112pub(crate) fn bitpack_into(values: &[u32], out: &mut [u8], num_bits: u8) -> usize {
113    let mask = (1u64 << num_bits) - 1;
114    let mut acc: u64 = 0;
115    let mut acc_bits: u32 = 0;
116    let mut out_pos = 0usize;
117
118    for &v in values {
119        acc |= (u64::from(v) & mask) << acc_bits;
120        acc_bits += u32::from(num_bits);
121        while acc_bits >= 8 {
122            out[out_pos] = (acc & 0xff) as u8;
123            out_pos += 1;
124            acc >>= 8;
125            acc_bits -= 8;
126        }
127    }
128    if acc_bits > 0 {
129        out[out_pos] = (acc & 0xff) as u8;
130        out_pos += 1;
131    }
132
133    out_pos
134}
135
136/// Unpacks `out.len()` values from `bytes`, the inverse of [`bitpack_into`], returning the
137/// number of bytes read.
138///
139/// Trusts its caller in the same way [`bitpack_into`] does.
140#[allow(clippy::cast_possible_truncation)] // `acc & mask` fits in a u32 for num_bits <= 32
141pub(crate) fn bitunpack_into(bytes: &[u8], out: &mut [u32], num_bits: u8) -> usize {
142    let mask = (1u64 << num_bits) - 1;
143    let mut acc: u64 = 0;
144    let mut acc_bits: u32 = 0;
145    let mut in_pos = 0usize;
146
147    for slot in out.iter_mut() {
148        while acc_bits < u32::from(num_bits) {
149            acc |= u64::from(bytes[in_pos]) << acc_bits;
150            in_pos += 1;
151            acc_bits += 8;
152        }
153        *slot = (acc & mask) as u32;
154        acc >>= u32::from(num_bits);
155        acc_bits -= u32::from(num_bits);
156    }
157
158    in_pos
159}
160
161/// Number of interleaved lanes the block-exact packed format below splits a block into — one
162/// lane per `u32` position in the WASM SIMD128 register [`Wasm128`](crate::Wasm128)'s decode
163/// kernel loads. See `plans/decisions/0010-bp128-style-packed-format.md` for the full
164/// rationale.
165const LANES: usize = 4;
166
167/// Tightly bit-packs a `BLOCK_LEN`-exact (128-value) block into `out` using the 4-way
168/// interleaved layout [`Wasm128`](crate::Wasm128)'s decode kernel expects, returning the
169/// number of bytes written: split `values` into 4 stride-4 sub-streams (lane `j` holds values
170/// `j, j+4, ..., j+124`), bit-pack each lane independently via [`bitpack_into`], then
171/// interleave the 4 lanes' packed 32-bit words round-robin (`out`'s first 4 bytes are lane 0's
172/// first word, the next 4 are lane 1's first word, and so on). See
173/// `plans/decisions/0010-bp128-style-packed-format.md`.
174///
175/// Because `values.len() / LANES` is always `32` (the only block length this crate supports),
176/// each lane's packed length is always an exact multiple of 4 bytes for every `num_bits` in
177/// `1..=32` (`32 * num_bits` bits is always a whole number of 32-bit words) — no padding, no
178/// partial words, ever, and the total output size always equals
179/// `packed_len_bytes(values.len(), num_bits)`, unchanged from the flat format.
180///
181/// Trusts its caller the same way [`bitpack_into`] does: `values.len()` must already be
182/// exactly `BLOCK_LEN` (128), `out` at least `packed_len_bytes(values.len(), num_bits)` bytes,
183/// and `num_bits` already verified to be in `1..=32`.
184pub(crate) fn bitpack_interleaved_into(values: &[u32], out: &mut [u8], num_bits: u8) -> usize {
185    let lane_len = values.len() / LANES;
186    let lane_bytes = packed_len_bytes(lane_len, num_bits);
187
188    let mut lane_values = [0u32; 32];
189    let mut lane_packed = [0u8; 128];
190
191    for lane in 0..LANES {
192        for (i, slot) in lane_values[..lane_len].iter_mut().enumerate() {
193            *slot = values[lane + i * LANES];
194        }
195        bitpack_into(
196            &lane_values[..lane_len],
197            &mut lane_packed[..lane_bytes],
198            num_bits,
199        );
200
201        for (word, chunk) in lane_packed[..lane_bytes].chunks_exact(4).enumerate() {
202            let dst = word * LANES * 4 + lane * 4;
203            out[dst..dst + 4].copy_from_slice(chunk);
204        }
205    }
206
207    lane_bytes * LANES
208}
209
210/// Unpacks `out.len()` values from `bytes`, the inverse of [`bitpack_interleaved_into`],
211/// returning the number of bytes read.
212///
213/// Trusts its caller in the same way [`bitpack_interleaved_into`] does.
214pub(crate) fn bitunpack_interleaved_into(bytes: &[u8], out: &mut [u32], num_bits: u8) -> usize {
215    let lane_len = out.len() / LANES;
216    let lane_bytes = packed_len_bytes(lane_len, num_bits);
217
218    let mut lane_values = [0u32; 32];
219    let mut lane_packed = [0u8; 128];
220
221    for lane in 0..LANES {
222        for (word, chunk) in lane_packed[..lane_bytes].chunks_exact_mut(4).enumerate() {
223            let src = word * LANES * 4 + lane * 4;
224            chunk.copy_from_slice(&bytes[src..src + 4]);
225        }
226        bitunpack_into(
227            &lane_packed[..lane_bytes],
228            &mut lane_values[..lane_len],
229            num_bits,
230        );
231
232        for (i, &value) in lane_values[..lane_len].iter().enumerate() {
233            out[lane + i * LANES] = value;
234        }
235    }
236
237    lane_bytes * LANES
238}
239
240#[cfg(test)]
241#[allow(clippy::cast_possible_truncation)] // test data lengths/values are always small
242mod tests {
243    use super::*;
244    use crate::testing::{gen, oracle};
245    use proptest::prelude::*;
246
247    fn block(value: u32) -> Vec<u32> {
248        vec![value; Scalar::BLOCK_LEN]
249    }
250
251    #[test]
252    fn num_bits_all_zero_is_zero() {
253        assert_eq!(Scalar::num_bits(&[0, 0, 0]), 0);
254    }
255
256    #[test]
257    fn num_bits_matches_expected_widths() {
258        assert_eq!(Scalar::num_bits(&[1]), 1);
259        assert_eq!(Scalar::num_bits(&[2]), 2);
260        assert_eq!(Scalar::num_bits(&[3]), 2);
261        assert_eq!(Scalar::num_bits(&[u32::MAX]), 32);
262    }
263
264    #[test]
265    fn round_trip_num_bits_1() {
266        let values: Vec<u32> = (0..Scalar::BLOCK_LEN as u32).map(|i| i % 2).collect();
267        let mut compressed = vec![0u8; packed_len_bytes(Scalar::BLOCK_LEN, 1)];
268        let written = Scalar::compress(&values, &mut compressed, 1);
269        assert_eq!(written, compressed.len());
270
271        let mut decompressed = vec![0u32; Scalar::BLOCK_LEN];
272        let read = Scalar::decompress(&compressed, &mut decompressed, 1);
273        assert_eq!(read, compressed.len());
274        assert_eq!(decompressed, values);
275    }
276
277    #[test]
278    fn round_trip_num_bits_32() {
279        let values: Vec<u32> = (0..Scalar::BLOCK_LEN as u32)
280            .map(|i| u32::MAX - i)
281            .collect();
282        let mut compressed = vec![0u8; packed_len_bytes(Scalar::BLOCK_LEN, 32)];
283        let written = Scalar::compress(&values, &mut compressed, 32);
284        assert_eq!(written, compressed.len());
285
286        let mut decompressed = vec![0u32; Scalar::BLOCK_LEN];
287        Scalar::decompress(&compressed, &mut decompressed, 32);
288        assert_eq!(decompressed, values);
289    }
290
291    #[test]
292    fn compress_matches_oracle() {
293        for num_bits in [1u8, 3, 7, 8, 11, 16, 17, 24, 32] {
294            let modulus = 1u64 << num_bits;
295            let values: Vec<u32> = (0..Scalar::BLOCK_LEN as u64)
296                .map(|i| (i % modulus) as u32)
297                .collect();
298
299            let mut compressed = vec![0u8; packed_len_bytes(Scalar::BLOCK_LEN, num_bits)];
300            Scalar::compress(&values, &mut compressed, num_bits);
301
302            let expected = oracle::oracle_encode_interleaved(&values, num_bits);
303            assert_eq!(compressed, expected, "mismatch at num_bits={num_bits}");
304        }
305    }
306
307    #[test]
308    fn interleaved_round_trip() {
309        for num_bits in [1u8, 3, 7, 8, 11, 16, 17, 24, 32] {
310            let modulus = 1u64 << num_bits;
311            let values: Vec<u32> = (0..Scalar::BLOCK_LEN as u64)
312                .map(|i| (i * 7 % modulus) as u32)
313                .collect();
314
315            let mut packed = vec![0u8; packed_len_bytes(Scalar::BLOCK_LEN, num_bits)];
316            let written = bitpack_interleaved_into(&values, &mut packed, num_bits);
317            assert_eq!(written, packed.len());
318
319            let mut decoded = vec![0u32; Scalar::BLOCK_LEN];
320            let read = bitunpack_interleaved_into(&packed, &mut decoded, num_bits);
321            assert_eq!(read, packed.len());
322            assert_eq!(
323                decoded, values,
324                "round-trip mismatch at num_bits={num_bits}"
325            );
326        }
327    }
328
329    /// Hand-verifiable layout check: at `num_bits == 32` each lane's `w`-th packed word is
330    /// simply that lane's `w`-th value's raw little-endian bytes (no bit-level packing
331    /// overlap), so the interleaved output at word `w`, lane `j` must be the raw bytes of
332    /// `values[j + w * 4]` — e.g. word 0 holds values `0, 1, 2, 3` (one per lane) and word 1
333    /// holds values `4, 5, 6, 7`.
334    #[test]
335    fn interleaved_known_layout_num_bits_32() {
336        let values: Vec<u32> = (0..Scalar::BLOCK_LEN as u32).collect();
337        let mut packed = vec![0u8; packed_len_bytes(Scalar::BLOCK_LEN, 32)];
338        bitpack_interleaved_into(&values, &mut packed, 32);
339
340        for word in 0..32usize {
341            for lane in 0..4usize {
342                let expected = (lane as u32 + word as u32 * 4).to_le_bytes();
343                let offset = word * 16 + lane * 4;
344                assert_eq!(
345                    &packed[offset..offset + 4],
346                    &expected,
347                    "mismatch at word={word}, lane={lane}"
348                );
349            }
350        }
351    }
352
353    #[test]
354    #[should_panic(expected = "decompressed.len() must be exactly BLOCK_LEN")]
355    fn compress_panics_on_wrong_length() {
356        let values = vec![0u32; Scalar::BLOCK_LEN - 1];
357        let mut compressed = vec![0u8; 1024];
358        Scalar::compress(&values, &mut compressed, 4);
359    }
360
361    #[test]
362    #[should_panic(expected = "decompressed.len() must be exactly BLOCK_LEN")]
363    fn decompress_panics_on_wrong_length() {
364        let compressed = vec![0u8; 1024];
365        let mut decompressed = vec![0u32; Scalar::BLOCK_LEN + 1];
366        Scalar::decompress(&compressed, &mut decompressed, 4);
367    }
368
369    #[test]
370    #[should_panic(expected = "num_bits must be in 1..=32")]
371    fn compress_panics_on_num_bits_zero() {
372        let values = block(0);
373        let mut compressed = vec![0u8; 1024];
374        Scalar::compress(&values, &mut compressed, 0);
375    }
376
377    #[test]
378    #[should_panic(expected = "num_bits must be in 1..=32")]
379    fn compress_panics_on_num_bits_33() {
380        let values = block(0);
381        let mut compressed = vec![0u8; 1024];
382        Scalar::compress(&values, &mut compressed, 33);
383    }
384
385    #[test]
386    #[should_panic(expected = "compressed buffer too small")]
387    fn compress_panics_on_undersized_output() {
388        let values = block(u32::MAX);
389        let mut compressed = vec![0u8; 1];
390        Scalar::compress(&values, &mut compressed, 32);
391    }
392
393    #[test]
394    #[should_panic(expected = "compressed buffer too small")]
395    fn decompress_panics_on_undersized_input() {
396        let compressed = vec![0u8; 1];
397        let mut decompressed = vec![0u32; Scalar::BLOCK_LEN];
398        Scalar::decompress(&compressed, &mut decompressed, 32);
399    }
400
401    proptest! {
402        #![proptest_config(gen::proptest_config(1000))]
403
404        #[test]
405        fn prop_compress_matches_oracle(
406            (num_bits, values) in gen::num_bits_and_block_values(Scalar::BLOCK_LEN)
407        ) {
408            let mut compressed = vec![0u8; packed_len_bytes(Scalar::BLOCK_LEN, num_bits)];
409            Scalar::compress(&values, &mut compressed, num_bits);
410
411            let expected = oracle::oracle_encode_interleaved(&values, num_bits);
412            prop_assert_eq!(compressed, expected);
413        }
414
415        #[test]
416        fn prop_round_trip(
417            (num_bits, values) in gen::num_bits_and_block_values(Scalar::BLOCK_LEN)
418        ) {
419            let mut compressed = vec![0u8; packed_len_bytes(Scalar::BLOCK_LEN, num_bits)];
420            Scalar::compress(&values, &mut compressed, num_bits);
421
422            let mut decompressed = vec![0u32; Scalar::BLOCK_LEN];
423            Scalar::decompress(&compressed, &mut decompressed, num_bits);
424            prop_assert_eq!(decompressed, values);
425        }
426
427        #[test]
428        fn prop_decompress_matches_oracle(
429            (num_bits, values) in gen::num_bits_and_block_values(Scalar::BLOCK_LEN)
430        ) {
431            let compressed = oracle::oracle_encode_interleaved(&values, num_bits);
432
433            let mut decompressed = vec![0u32; Scalar::BLOCK_LEN];
434            Scalar::decompress(&compressed, &mut decompressed, num_bits);
435            prop_assert_eq!(decompressed, values);
436        }
437    }
438}