parmesan-par2 0.6.0

Fast, standalone PAR2 (Reed-Solomon) creation, verification and repair tool
Documentation
//! ALTMAP bit-plane layout for GF(2^16) Reed-Solomon data.
//!
//! ## Layout
//!
//! **Normal layout:** N consecutive `u16` words, each stored as 2 little-endian
//! bytes.
//!
//! **ALTMAP layout:** 16 contiguous bit-plane sections, each of `N/8` bytes.
//! Plane `k` (0 ≤ k < 16) stores bit `k` of every word: within the 2-byte
//! chunk at byte offset `g*2` inside plane `k`, bit `i` (LSB-first) equals
//! bit `k` of input word `g*16 + i`.
//!
//! Total ALTMAP size = `16 × (N/8)` = `2N` bytes — identical to the normal
//! layout.
//!
//! ## Alignment requirement
//!
//! `N` must be a multiple of 16 (one SSE2 processing group = 16 words).
//! For 27e's AVX2 XOR kernel `N` should also be a multiple of 256 so that
//! each plane section fills whole 32-byte AVX2 vectors; in practice PAR2
//! slice sizes are large multiples of 256 words.
//!
//! ## Why it speeds up RS encoding
//!
//! With ALTMAP, applying a GF(2^16) coefficient to an input slice is a sequence
//! of `vpxor` operations on 256-bit vectors (one full bit-plane per vector).
//! The XOR bit-dependency matrix (Phase 27a/27b) determines exactly which input
//! planes XOR into which output planes — no nibble extraction, no lookup tables.

/// Returns the number of bytes needed to hold `words` u16 values in ALTMAP
/// format.  Equal to `words * 2` (same as the normal layout).
///
/// # Panics
///
/// Panics if `words` is not a multiple of 16.
pub fn altmap_size(words: usize) -> usize {
    assert!(
        words.is_multiple_of(16),
        "altmap_size: words ({words}) must be a multiple of 16"
    );
    words * 2
}

/// Convert `src` (N u16 words, normal layout) into ALTMAP bit-plane format,
/// writing `2N` bytes into `dst`.
///
/// Uses the SSE2 path on x86_64 when available; falls back to scalar otherwise.
///
/// # Panics
///
/// Panics if `src.len()` is not a multiple of 16 or `dst.len() != src.len() * 2`.
pub fn to_altmap(src: &[u16], dst: &mut [u8]) {
    let n = src.len();
    assert!(
        n.is_multiple_of(16),
        "to_altmap: src length ({n}) must be a multiple of 16"
    );
    assert_eq!(
        dst.len(),
        n * 2,
        "to_altmap: dst must be {} bytes, got {}",
        n * 2,
        dst.len()
    );

    #[cfg(target_arch = "x86_64")]
    if std::is_x86_feature_detected!("sse2") {
        // SAFETY: SSE2 availability checked above; preconditions asserted above.
        unsafe { to_altmap_sse2(src, dst) };
        return;
    }

    to_altmap_scalar(src, dst);
}

/// Convert `src` (ALTMAP format, `2N` bytes) back to normal u16 layout,
/// writing N words into `dst`.
///
/// # Panics
///
/// Panics if `dst.len()` is not a multiple of 16 or `src.len() != dst.len() * 2`.
pub fn from_altmap(src: &[u8], dst: &mut [u16]) {
    let n = dst.len();
    assert!(
        n.is_multiple_of(16),
        "from_altmap: dst length ({n}) must be a multiple of 16"
    );
    assert_eq!(
        src.len(),
        n * 2,
        "from_altmap: src must be {} bytes, got {}",
        n * 2,
        src.len()
    );
    from_altmap_scalar(src, dst);
}

// ---------------------------------------------------------------------------
// Scalar implementations (reference / non-x86 fallback)
// ---------------------------------------------------------------------------

fn to_altmap_scalar(src: &[u16], dst: &mut [u8]) {
    let n = src.len();
    let plane_bytes = n / 8; // bytes per plane section

    for (g, chunk) in src.as_chunks::<16>().0.iter().enumerate() {
        let byte_off = g * 2; // 2-byte position within each plane section
        for k in 0u32..16 {
            let mut bits: u16 = 0;
            for (i, &w) in chunk.iter().enumerate() {
                if (w >> k) & 1 == 1 {
                    bits |= 1 << i;
                }
            }
            let off = k as usize * plane_bytes + byte_off;
            dst[off..off + 2].copy_from_slice(&bits.to_le_bytes());
        }
    }
}

fn from_altmap_scalar(src: &[u8], dst: &mut [u16]) {
    let n = dst.len();
    let plane_bytes = n / 8;

    for g in 0..n / 16 {
        let byte_off = g * 2;
        for i in 0..16usize {
            let mut word: u16 = 0;
            for k in 0..16u32 {
                let off = k as usize * plane_bytes + byte_off;
                let bits = u16::from_le_bytes([src[off], src[off + 1]]);
                if (bits >> i) & 1 == 1 {
                    word |= 1 << k;
                }
            }
            dst[g * 16 + i] = word;
        }
    }
}

// ---------------------------------------------------------------------------
// SSE2 implementation of `to_altmap`
// ---------------------------------------------------------------------------
//
// For each group of 16 u16 words (32 bytes):
//
//   1. Load two 128-bit registers (words 0..7, words 8..15).
//   2. Separate lo bytes (bits 0..7) and hi bytes (bits 8..15) using AND + SRL
//      + PACKUS.
//   3. For each bit k in 0..8:
//        - AND lo with mask (1<<k) in every byte position.
//        - CMPEQ to produce 0xFF where bit k is set, 0x00 otherwise.
//        - MOVEMASK extracts one bit per byte → 16-bit result.
//        - Write 2 bytes into plane k's section.
//   4. Repeat step 3 for k in 0..8 using hi bytes → writes into planes 8..15.
//
// Instructions per group (16 words):
//   2 loads + 2 ANDs + 2 SRLs + 2 PACKs + 16*(AND+CMPEQ+MOVEMASK) ≈ 56 ops.
// Throughput on i5-10400 for 768 KB input: ≈ 50–80 µs (well within 100 µs target).

#[cfg(target_arch = "x86_64")]
#[target_feature(enable = "sse2")]
unsafe fn to_altmap_sse2(src: &[u16], dst: &mut [u8]) {
    #[allow(unused_imports)]
    use std::arch::x86_64::*;

    let n = src.len();
    let plane_bytes = n / 8;

    // Precompute bit-selector masks outside the group loop.
    // masks[k] = _mm_set1_epi8(1 << k): byte vector with bit k set in every position.
    let masks: [__m128i; 8] = std::array::from_fn(|k| _mm_set1_epi8((1u8 << k) as i8));

    let lo_mask = _mm_set1_epi16(0x00FF_u16 as i16);

    for (g, chunk) in src.as_chunks::<16>().0.iter().enumerate() {
        let byte_off = g * 2;
        let ptr = chunk.as_ptr();

        // Load 16 u16 words as two 128-bit vectors (8 words each).
        let v0 = _mm_loadu_si128(ptr as *const __m128i);
        let v1 = _mm_loadu_si128(ptr.add(8) as *const __m128i);

        // Separate lo and hi bytes of each u16 word, then pack into byte vectors.
        //   lo: [w0_lo, w1_lo, ..., w15_lo]
        //   hi: [w0_hi, w1_hi, ..., w15_hi]
        let lo = _mm_packus_epi16(_mm_and_si128(v0, lo_mask), _mm_and_si128(v1, lo_mask));
        let hi = _mm_packus_epi16(_mm_srli_epi16(v0, 8), _mm_srli_epi16(v1, 8));

        // Planes 0..8 come from lo bytes; planes 8..16 come from hi bytes.
        for (k, &m) in masks.iter().enumerate() {
            // lo byte planes (bits 0..8)
            let lo_bits = _mm_movemask_epi8(_mm_cmpeq_epi8(_mm_and_si128(lo, m), m)) as u16;
            let off_lo = k * plane_bytes + byte_off;
            let lo_bytes = lo_bits.to_le_bytes();
            dst[off_lo] = lo_bytes[0];
            dst[off_lo + 1] = lo_bytes[1];

            // hi byte planes (bits 8..16)
            let hi_bits = _mm_movemask_epi8(_mm_cmpeq_epi8(_mm_and_si128(hi, m), m)) as u16;
            let off_hi = (k + 8) * plane_bytes + byte_off;
            let hi_bytes = hi_bits.to_le_bytes();
            dst[off_hi] = hi_bytes[0];
            dst[off_hi + 1] = hi_bytes[1];
        }
    }
}

// ---------------------------------------------------------------------------
// Tests
// ---------------------------------------------------------------------------

#[cfg(test)]
mod tests {
    use super::*;

    fn round_trip(words: &[u16]) {
        let n = words.len();
        let mut altmap = vec![0u8; altmap_size(n)];
        let mut recovered = vec![0u16; n];
        to_altmap(words, &mut altmap);
        from_altmap(&altmap, &mut recovered);
        assert_eq!(recovered, words, "round-trip failed for {} words", n);
    }

    #[test]
    fn round_trip_all_zeros() {
        round_trip(&[0u16; 16]);
        round_trip(&[0u16; 64]);
    }

    #[test]
    fn round_trip_all_ones() {
        round_trip(&[0xFFFF_u16; 16]);
        round_trip(&[0xFFFF_u16; 256]);
    }

    #[test]
    fn round_trip_single_bit_words() {
        // Each word is a single set bit at position i (mod 16).
        let words: Vec<u16> = (0..64).map(|i| 1u16 << (i % 16)).collect();
        round_trip(&words);
    }

    #[test]
    fn round_trip_incrementing() {
        // words[i] = i as u16
        let words: Vec<u16> = (0..256).map(|i| i as u16).collect();
        round_trip(&words);
    }

    #[test]
    fn round_trip_random_512_words() {
        // Use a simple LCG to avoid pulling in `rand`.
        let mut lcg: u64 = 0xDEAD_BEEF_1234_5678;
        let words: Vec<u16> = (0..512)
            .map(|_| {
                lcg = lcg
                    .wrapping_mul(6364136223846793005)
                    .wrapping_add(1442695040888963407);
                (lcg >> 48) as u16
            })
            .collect();
        round_trip(&words);
    }

    #[test]
    #[allow(unreachable_code)]
    fn scalar_and_simd_produce_identical_output() {
        #[cfg(not(target_arch = "x86_64"))]
        return; // Nothing to compare on non-x86.

        let mut lcg: u64 = 0xCAFEBABE_DEADBEEF;
        let words: Vec<u16> = (0..256)
            .map(|_| {
                lcg = lcg
                    .wrapping_mul(6364136223846793005)
                    .wrapping_add(1442695040888963407);
                (lcg >> 48) as u16
            })
            .collect();

        let mut out_scalar = vec![0u8; altmap_size(words.len())];
        let mut out_simd = vec![0u8; altmap_size(words.len())];

        to_altmap_scalar(&words, &mut out_scalar);
        to_altmap(&words, &mut out_simd); // uses SIMD on x86_64

        assert_eq!(out_scalar, out_simd, "scalar and SIMD outputs differ");
    }

    #[test]
    fn plane_layout_is_correct() {
        // 16 words where word i has only bit i set (i < 16).
        // In plane k, only word k has bit k set, so the 16-bit value for group 0
        // should be (1 << k).
        let words: Vec<u16> = (0..16).map(|i| 1u16 << i).collect();
        let mut altmap = vec![0u8; altmap_size(words.len())];
        to_altmap(&words, &mut altmap);

        let plane_bytes = words.len() / 8; // = 2 for 16 words
        for k in 0..16usize {
            let off = k * plane_bytes;
            let bits = u16::from_le_bytes([altmap[off], altmap[off + 1]]);
            assert_eq!(
                bits,
                1 << k,
                "plane {k}: expected {:#06x}, got {:#06x}",
                1u16 << k,
                bits
            );
        }
    }
}