kopis/

ser.rs

//! Serialization and deserialization routines for ring elements

/// Fast specialization of `deserialize` for the 13-bit case (matrix expansion), which is
/// by far the hottest width. Processes a whole 13-byte group into 8 coefficients with
/// fixed shifts and no per-element branching, so it vectorizes well.
pub(crate) fn deserialize_13(bytes: &[u8; 13 * 256 / 8]) -> [u16; 256] {
    let mut out = [0u16; 256];
    // 256 coeffs = 32 groups of 8, each group packed into 13 bytes.
    for g in 0..32 {
        let b = &bytes[13 * g..13 * g + 13];
        // Widen once so the shifts below can't lose high bits.
        let w = |k: usize| b[k] as u16;
        let o = 8 * g;
        out[o] = w(0) | ((w(1) & 0x1f) << 8);
        out[o + 1] = (w(1) >> 5) | ((w(2)) << 3) | ((w(3) & 0x03) << 11);
        out[o + 2] = (w(3) >> 2) | ((w(4) & 0x7f) << 6);
        out[o + 3] = (w(4) >> 7) | ((w(5)) << 1) | ((w(6) & 0x0f) << 9);
        out[o + 4] = (w(6) >> 4) | ((w(7)) << 4) | ((w(8) & 0x01) << 12);
        out[o + 5] = (w(8) >> 1) | ((w(9) & 0x3f) << 7);
        out[o + 6] = (w(9) >> 6) | ((w(10)) << 2) | ((w(11) & 0x07) << 10);
        out[o + 7] = (w(11) >> 3) | ((w(12)) << 5);
    }
    out
}

/// Fast specialization of `deserialize_generic` for the 10-bit case
/// (ciphertext/public-key vector unpacking). Processes a 5-byte group into 4 coefficients
/// with fixed shifts.
pub(crate) fn deserialize_10(bytes: &[u8; 10 * 256 / 8]) -> [u16; 256] {
    let mut out = [0u16; 256];
    // 256 coeffs = 64 groups of 4, each group packed into 5 bytes.
    for g in 0..64 {
        let b = &bytes[5 * g..5 * g + 5];
        let w = |k: usize| b[k] as u16;
        let o = 4 * g;
        out[o] = w(0) | ((w(1) & 0x03) << 8);
        out[o + 1] = (w(1) >> 2) | ((w(2) & 0x0f) << 6);
        out[o + 2] = (w(2) >> 4) | ((w(3) & 0x3f) << 4);
        out[o + 3] = (w(3) >> 6) | (w(4) << 2);
    }
    out
}

/// Deserializes the given bitstring into a u16 array. Every element of the array has
/// `bits_per_elem` bits (must be ≤ 13), encoded in the lower bits of the word.
#[allow(clippy::needless_range_loop)]
pub(crate) fn deserialize_generic<const N: usize>(bytes: &[u8], bits_per_elem: usize) -> [u16; N] {
    // Serialized bitlength must be a multiple of 8, and `bytes` must be the correct length
    assert_eq!((bits_per_elem * N) % 8, 0);
    assert_eq!(bytes.len(), bits_per_elem * N / 8);

    let mut out = [0u16; N];
    let bitmask: u32 = (1 << bits_per_elem) - 1;

    // Sliding window: holds pending bits from the byte stream. We refill from bytes
    // one at a time and extract elements from the bottom.
    let mut window: u32 = 0;
    let mut bits_in_window: usize = 0;
    let mut byte_pos: usize = 0;

    for idx in 0..N {
        // Ensure we have enough bits in the window for one element
        while bits_in_window < bits_per_elem {
            window |= (bytes[byte_pos] as u32) << bits_in_window;
            byte_pos += 1;
            bits_in_window += 8;
        }

        // Extract the lowest bits_per_elem bits as one element
        out[idx] = (window & bitmask) as u16;
        window >>= bits_per_elem;
        bits_in_window -= bits_per_elem;
    }

    out
}

/// Fast specialization of `serialize` for the 10-bit case (ciphertext/public-key vector
/// packing), which is by far the hottest serialization width. Packs each 4-coefficient
/// group into 5 bytes with fixed shifts and no per-element branching.
pub(crate) fn serialize_10(data: &[u16; 256], out_buf: &mut [u8; 10 * 256 / 8]) {
    // 256 coeffs = 64 groups of 4, each group packed into 5 bytes.
    for g in 0..64 {
        let o = 4 * g;
        // Mask to 10 bits like the generic path does: coefficients may carry garbage in their
        // high bits, and serialization is where values get reduced mod 2^10
        let d = |k: usize| data[o + k] & 0x3ff;
        let b = 5 * g;
        out_buf[b] = d(0) as u8;
        out_buf[b + 1] = ((d(0) >> 8) | (d(1) << 2)) as u8;
        out_buf[b + 2] = ((d(1) >> 6) | (d(2) << 4)) as u8;
        out_buf[b + 3] = ((d(2) >> 4) | (d(3) << 6)) as u8;
        out_buf[b + 4] = (d(3) >> 2) as u8;
    }
}

// Algorithm 10, POLN2BS
/// Serializes the given u16 array into a bitstring. Every element of the array has `bits_per_elem`
/// bits (must be ≤ 13), encoded in the lower bits of the word.
pub(crate) fn serialize(data: &[u16], out_buf: &mut [u8], bits_per_elem: usize) {
    assert_eq!(out_buf.len(), bits_per_elem * data.len() / 8);

    let bitmask: u32 = (1 << bits_per_elem) - 1;

    // Sliding window: elements are OR'd in at the current position, and complete bytes
    // are flushed out from the bottom.
    let mut window: u32 = 0;
    let mut bits_in_window: usize = 0;
    let mut byte_pos: usize = 0;

    for &elem in data.iter() {
        // Insert this element's bits into the window
        window |= ((elem as u32) & bitmask) << bits_in_window;
        bits_in_window += bits_per_elem;

        // Flush all complete bytes
        while bits_in_window >= 8 {
            out_buf[byte_pos] = window as u8;
            window >>= 8;
            bits_in_window -= 8;
            byte_pos += 1;
        }
    }

    // There should never be any partial bits in the output
    debug_assert_eq!(bits_in_window, 0);
}

// The fast 10- and 13-bit paths must agree with the generic sliding-window deserializer.
#[test]
fn specialized_deser_matches_generic() {
    use rand::Rng;
    let mut rng = rand::rng();

    // Test deserialize_13
    for _ in 0..100 {
        let bytes: [u8; 13 * 256 / 8] = rng.random();
        let generic: [u16; 256] = deserialize_generic(&bytes, 13);
        let fast = deserialize_13(&bytes);
        assert_eq!(generic, fast);
    }

    // Test deserialize_10
    for _ in 0..100 {
        let bytes: [u8; 10 * 256 / 8] = rng.random();
        let generic: [u16; 256] = deserialize_generic(&bytes, 10);
        let fast = deserialize_10(&bytes);
        assert_eq!(generic, fast);
    }
}

// The fast 10-bit serialization path must agree with the generic sliding-window serializer.
#[test]
fn specialized_ser_matches_generic() {
    use rand::Rng;
    let mut rng = rand::rng();

    // Use full-range u16 coefficients so the test also covers the 10-bit masking behavior
    for _ in 0..100 {
        let data: [u16; 256] = rng.random();
        let mut generic = [0u8; 10 * 256 / 8];
        let mut fast = [0u8; 10 * 256 / 8];
        serialize(&data, &mut generic, 10);
        serialize_10(&data, &mut fast);
        assert_eq!(generic, fast);
    }
}