lib_q_ring/
encoding.rs

1//! FIPS 204-style bit packing for bounded unsigned coefficient vectors.
2
3use crate::constants::COEFFICIENTS_IN_RING_ELEMENT;
4
5/// Byte length for [`simple_bit_pack`] / [`simple_bit_unpack`] with `w` bits per coefficient.
6#[must_use]
7pub const fn simple_bit_pack_len(w: usize) -> usize {
8    (COEFFICIENTS_IN_RING_ELEMENT * w).div_ceil(8)
9}
10
11/// Pack 256 coefficients, each using `w` bits, least-significant bit first within each coefficient,
12/// coefficients in order `0 … 255`, bit stream little-endian across bytes (FIPS 204 “SimpleBitPack”).
13///
14/// # Panics
15///
16/// If any coefficient is outside `[0, 2^w)`.
17pub fn simple_bit_pack(w: u8, coeffs: &[i32; COEFFICIENTS_IN_RING_ELEMENT], out: &mut [u8]) {
18    let w = usize::from(w);
19    assert_eq!(out.len(), simple_bit_pack_len(w), "output length mismatch");
20    let max = 1i32.checked_shl(w as u32).expect("w too large");
21    out.fill(0);
22    let mut bit_idx = 0usize;
23    for &c in coeffs {
24        assert!(c >= 0 && c < max, "coefficient out of range for w={w}");
25        let u = c as u32;
26        for b in 0..w {
27            let bit = (u >> b) & 1;
28            let byte_i = bit_idx / 8;
29            let bit_in_byte = bit_idx % 8;
30            out[byte_i] |= (bit as u8) << bit_in_byte;
31            bit_idx += 1;
32        }
33    }
34}
35
36/// Inverse of [`simple_bit_pack`].
37///
38/// # Panics
39///
40/// If `data` is shorter than [`simple_bit_pack_len`]`(w)`.
41pub fn simple_bit_unpack(w: u8, data: &[u8], out: &mut [i32; COEFFICIENTS_IN_RING_ELEMENT]) {
42    let w = usize::from(w);
43    let need = simple_bit_pack_len(w);
44    assert!(data.len() >= need, "input too short");
45    // Use a u64 intermediate so that w == 32 produces a mask of all-ones (u32::MAX)
46    // without overflowing a u32 shift.
47    let mask = ((1u64 << w).wrapping_sub(1)) as u32;
48    let mut bit_idx = 0usize;
49    for o in out.iter_mut() {
50        let mut v = 0u32;
51        for b in 0..w {
52            let byte_i = bit_idx / 8;
53            let bit_in_byte = bit_idx % 8;
54            let bit = ((data[byte_i] >> bit_in_byte) & 1) as u32;
55            v |= bit << b;
56            bit_idx += 1;
57        }
58        *o = (v & mask) as i32;
59    }
60}
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65
66    #[test]
67    fn bit_pack_roundtrip_w4_w6_w20() {
68        for w in [4u8, 6, 10, 20] {
69            let mut coeffs = [0i32; COEFFICIENTS_IN_RING_ELEMENT];
70            for (i, c) in coeffs.iter_mut().enumerate() {
71                *c = (i % (1 << (w as usize))) as i32;
72            }
73            let len = simple_bit_pack_len(w as usize);
74            let mut buf = [0u8; 800];
75            simple_bit_pack(w, &coeffs, &mut buf[..len]);
76            let mut back = [0i32; COEFFICIENTS_IN_RING_ELEMENT];
77            simple_bit_unpack(w, &buf[..len], &mut back);
78            assert_eq!(coeffs, back);
79        }
80    }
81}
lib_q_ring/encoding.rs

lib_q_ring/
encoding.rs
