1use crate::traits::BitPacker;
4
5pub 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#[allow(clippy::cast_possible_truncation)] pub(crate) fn bits_for_max_value(max: u32) -> u8 {
81 (32 - max.leading_zeros()) as u8
82}
83
84pub(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
95pub(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#[allow(clippy::cast_possible_truncation)] pub(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#[allow(clippy::cast_possible_truncation)] pub(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
161const LANES: usize = 4;
166
167pub(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
210pub(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)] mod 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 #[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}