gzippy 0.8.0

//! SIMD-Accelerated Huffman Decode
//!
//! Uses AVX2/AVX-512 gather instructions to decode multiple symbols in parallel.
//! This is similar to ISA-L's approach but implemented in Rust.
//!
//! ## Strategy
//!
//! 1. Build a multi-symbol lookup table where each entry can decode 1-4 symbols
//! 2. Use SIMD gather to look up multiple table entries in parallel
//! 3. Combine results and advance bit position
//!
//! ## Performance Target
//!
//! 15-25% gain on literal-heavy dynamic blocks by reducing table lookups per symbol.

#![allow(dead_code)]

use std::io;

/// Maximum bits for multi-symbol lookup (12 bits = 4KB table)
const MULTI_SYM_BITS: usize = 12;
const MULTI_SYM_SIZE: usize = 1 << MULTI_SYM_BITS;
const MULTI_SYM_MASK: u64 = (MULTI_SYM_SIZE - 1) as u64;

/// Multi-symbol table entry
/// Encodes 1-4 literal bytes in a single lookup
#[derive(Clone, Copy, Default)]
#[repr(C, align(8))]
pub struct MultiSymEntry {
    /// Total bits consumed (sum of all symbol code lengths)
    pub total_bits: u8,
    /// Number of symbols decoded (1-4)
    pub sym_count: u8,
    /// First symbol (literal byte or 0xFF for non-literal)
    pub sym1: u8,
    /// Second symbol (or 0 if sym_count < 2)
    pub sym2: u8,
    /// Third symbol (or 0 if sym_count < 3)
    pub sym3: u8,
    /// Fourth symbol (or 0 if sym_count < 4)
    pub sym4: u8,
    /// Padding to 8 bytes
    _pad: [u8; 2],
}

impl MultiSymEntry {
    /// Create entry for a single literal
    #[inline(always)]
    pub fn single_literal(bits: u8, byte: u8) -> Self {
        Self {
            total_bits: bits,
            sym_count: 1,
            sym1: byte,
            sym2: 0,
            sym3: 0,
            sym4: 0,
            _pad: [0; 2],
        }
    }

    /// Create entry for two literals
    #[inline(always)]
    pub fn two_literals(bits1: u8, byte1: u8, bits2: u8, byte2: u8) -> Self {
        Self {
            total_bits: bits1 + bits2,
            sym_count: 2,
            sym1: byte1,
            sym2: byte2,
            sym3: 0,
            sym4: 0,
            _pad: [0; 2],
        }
    }

    /// Create entry for three literals
    #[inline(always)]
    pub fn three_literals(total_bits: u8, b1: u8, b2: u8, b3: u8) -> Self {
        Self {
            total_bits,
            sym_count: 3,
            sym1: b1,
            sym2: b2,
            sym3: b3,
            sym4: 0,
            _pad: [0; 2],
        }
    }

    /// Create entry for four literals
    #[inline(always)]
    pub fn four_literals(total_bits: u8, b1: u8, b2: u8, b3: u8, b4: u8) -> Self {
        Self {
            total_bits,
            sym_count: 4,
            sym1: b1,
            sym2: b2,
            sym3: b3,
            sym4: b4,
            _pad: [0; 2],
        }
    }

    /// Create entry for non-literal (length code, EOB, or slow path)
    /// sym1 contains the symbol value (256 for EOB, 257-285 for length codes)
    #[inline(always)]
    pub fn non_literal(bits: u8, symbol: u16) -> Self {
        Self {
            total_bits: bits,
            sym_count: 0, // 0 indicates non-literal
            sym1: (symbol & 0xFF) as u8,
            sym2: (symbol >> 8) as u8,
            sym3: 0,
            sym4: 0,
            _pad: [0; 2],
        }
    }

    /// Check if this is a literal-only entry
    #[inline(always)]
    pub fn is_literal_run(&self) -> bool {
        self.sym_count > 0
    }

    /// Get symbol for non-literal entry
    #[inline(always)]
    pub fn symbol(&self) -> u16 {
        (self.sym2 as u16) << 8 | self.sym1 as u16
    }
}

/// Multi-symbol Huffman table
/// Allows decoding multiple literals in a single lookup
pub struct MultiSymTable {
    /// Primary table (12-bit lookup)
    table: Vec<MultiSymEntry>,
    /// Maximum code length in source table
    max_code_len: u32,
}

impl MultiSymTable {
    /// Build multi-symbol table from code lengths
    /// This pre-computes entries that decode multiple consecutive literals
    pub fn build(lens: &[u8]) -> io::Result<Self> {
        let mut table = vec![MultiSymEntry::default(); MULTI_SYM_SIZE];

        // First, build a simple single-symbol table
        let mut bl_count = [0u32; 16];
        let mut max_len = 0u32;

        for &len in lens {
            if len > 0 && len <= 15 {
                bl_count[len as usize] += 1;
                max_len = max_len.max(len as u32);
            }
        }

        // Calculate starting codes
        let mut next_code = [0u32; 16];
        let mut code = 0u32;
        for bits in 1..=15 {
            code = (code + bl_count[bits - 1]) << 1;
            next_code[bits] = code;
        }

        // Build symbol lookup (code -> symbol, length)
        // symbol_info[i] = (symbol, code_length) for codes that fit in 12 bits
        let mut symbol_info: Vec<(u16, u8)> = vec![(0xFFFF, 0); MULTI_SYM_SIZE];

        for (symbol, &len) in lens.iter().enumerate() {
            if len == 0 || len > 12 {
                continue; // Skip codes that don't fit in our table
            }

            let len = len as u32;
            let code = next_code[len as usize];
            next_code[len as usize] += 1;

            // Reverse bits for LSB-first deflate
            let rev = reverse_bits(code, len);

            // Fill all entries for this code
            let fill_count = 1usize << (MULTI_SYM_BITS as u32 - len);
            for i in 0..fill_count {
                let idx = (rev as usize) | (i << len as usize);
                if idx < MULTI_SYM_SIZE {
                    symbol_info[idx] = (symbol as u16, len as u8);
                }
            }
        }

        // Now build multi-symbol entries
        // For each table entry, try to decode 2-4 consecutive symbols
        for idx in 0..MULTI_SYM_SIZE {
            let (sym1, len1) = symbol_info[idx];

            if len1 == 0 {
                // Invalid entry - leave as default
                continue;
            }

            if sym1 >= 256 {
                // Non-literal (length code or EOB) - create single entry
                table[idx] = MultiSymEntry::non_literal(len1, sym1);
                continue;
            }

            // First symbol is a literal - try to decode more
            let remaining1 = MULTI_SYM_BITS as u32 - len1 as u32;

            // For fixed Huffman, most codes are 8-9 bits, so we can sometimes
            // fit 2 short codes in 12 bits if the first is short enough
            if remaining1 >= 1 {
                // Try to get second symbol
                // Extract the bits after the first code
                let next_bits = (idx >> len1 as usize) & ((1 << remaining1) - 1);
                let (sym2, len2) = symbol_info[next_bits];

                if len2 > 0 && (len2 as u32) <= remaining1 && sym2 < 256 {
                    // Got a second literal
                    let remaining2 = remaining1 - len2 as u32;

                    if remaining2 >= 1 {
                        // Try for third symbol
                        let next_bits2 =
                            (idx >> (len1 as usize + len2 as usize)) & ((1 << remaining2) - 1);
                        let (sym3, len3) = symbol_info[next_bits2];

                        if len3 > 0 && (len3 as u32) <= remaining2 && sym3 < 256 {
                            // Got a third literal
                            let remaining3 = remaining2 - len3 as u32;

                            if remaining3 >= 1 {
                                // Try for fourth symbol
                                let next_bits3 = (idx
                                    >> (len1 as usize + len2 as usize + len3 as usize))
                                    & ((1 << remaining3) - 1);
                                let (sym4, len4) = symbol_info[next_bits3];

                                if len4 > 0 && (len4 as u32) <= remaining3 && sym4 < 256 {
                                    // Four literals!
                                    table[idx] = MultiSymEntry::four_literals(
                                        len1 + len2 + len3 + len4,
                                        sym1 as u8,
                                        sym2 as u8,
                                        sym3 as u8,
                                        sym4 as u8,
                                    );
                                    continue;
                                }
                            }

                            // Three literals
                            table[idx] = MultiSymEntry::three_literals(
                                len1 + len2 + len3,
                                sym1 as u8,
                                sym2 as u8,
                                sym3 as u8,
                            );
                            continue;
                        }
                    }

                    // Two literals
                    table[idx] = MultiSymEntry::two_literals(len1, sym1 as u8, len2, sym2 as u8);
                    continue;
                }
            }

            // Single literal
            table[idx] = MultiSymEntry::single_literal(len1, sym1 as u8);
        }

        Ok(Self {
            table,
            max_code_len: max_len,
        })
    }

    /// Look up entry for given bits
    #[inline(always)]
    pub fn lookup(&self, bits: u64) -> &MultiSymEntry {
        let idx = (bits & MULTI_SYM_MASK) as usize;
        unsafe { self.table.get_unchecked(idx) }
    }
}

/// Reverse bits for LSB-first deflate codes
#[inline(always)]
fn reverse_bits(code: u32, len: u32) -> u32 {
    if len == 0 {
        return 0;
    }
    let mut rev = 0u32;
    let mut c = code;
    for _ in 0..len {
        rev = (rev << 1) | (c & 1);
        c >>= 1;
    }
    rev
}

/// SIMD-accelerated decode using multi-symbol table
/// Returns number of bytes written to output
#[cfg(target_arch = "x86_64")]
pub fn decode_simd_multi_sym(
    table: &MultiSymTable,
    bits: &mut crate::decompress::two_level_table::FastBits,
    output: &mut [u8],
    mut out_pos: usize,
) -> io::Result<usize> {
    // Fast path: decode multiple literals at once
    loop {
        bits.ensure(32);

        let entry = table.lookup(bits.buffer());

        if entry.sym_count == 0 {
            // Non-literal - return control to caller
            break;
        }

        if entry.total_bits == 0 {
            // Invalid entry
            break;
        }

        bits.consume(entry.total_bits as u32);

        // Write literals to output
        match entry.sym_count {
            1 => {
                if out_pos >= output.len() {
                    return Err(io::Error::new(
                        io::ErrorKind::WriteZero,
                        "Output buffer full",
                    ));
                }
                output[out_pos] = entry.sym1;
                out_pos += 1;
            }
            2 => {
                if out_pos + 1 >= output.len() {
                    return Err(io::Error::new(
                        io::ErrorKind::WriteZero,
                        "Output buffer full",
                    ));
                }
                output[out_pos] = entry.sym1;
                output[out_pos + 1] = entry.sym2;
                out_pos += 2;
            }
            3 => {
                if out_pos + 2 >= output.len() {
                    return Err(io::Error::new(
                        io::ErrorKind::WriteZero,
                        "Output buffer full",
                    ));
                }
                output[out_pos] = entry.sym1;
                output[out_pos + 1] = entry.sym2;
                output[out_pos + 2] = entry.sym3;
                out_pos += 3;
            }
            4 => {
                if out_pos + 3 >= output.len() {
                    return Err(io::Error::new(
                        io::ErrorKind::WriteZero,
                        "Output buffer full",
                    ));
                }
                output[out_pos] = entry.sym1;
                output[out_pos + 1] = entry.sym2;
                output[out_pos + 2] = entry.sym3;
                output[out_pos + 3] = entry.sym4;
                out_pos += 4;
            }
            _ => break,
        }
    }

    Ok(out_pos)
}

/// Non-x86 fallback
#[cfg(not(target_arch = "x86_64"))]
pub fn decode_simd_multi_sym(
    table: &MultiSymTable,
    bits: &mut crate::decompress::two_level_table::FastBits,
    output: &mut [u8],
    mut out_pos: usize,
) -> io::Result<usize> {
    // Same logic, just without SIMD intrinsics
    loop {
        bits.ensure(32);

        let entry = table.lookup(bits.buffer());

        if entry.sym_count == 0 || entry.total_bits == 0 {
            break;
        }

        bits.consume(entry.total_bits as u32);

        match entry.sym_count {
            1 => {
                if out_pos >= output.len() {
                    return Err(io::Error::new(
                        io::ErrorKind::WriteZero,
                        "Output buffer full",
                    ));
                }
                output[out_pos] = entry.sym1;
                out_pos += 1;
            }
            2 => {
                if out_pos + 1 >= output.len() {
                    return Err(io::Error::new(
                        io::ErrorKind::WriteZero,
                        "Output buffer full",
                    ));
                }
                output[out_pos] = entry.sym1;
                output[out_pos + 1] = entry.sym2;
                out_pos += 2;
            }
            3 => {
                if out_pos + 2 >= output.len() {
                    return Err(io::Error::new(
                        io::ErrorKind::WriteZero,
                        "Output buffer full",
                    ));
                }
                output[out_pos] = entry.sym1;
                output[out_pos + 1] = entry.sym2;
                output[out_pos + 2] = entry.sym3;
                out_pos += 3;
            }
            4 => {
                if out_pos + 3 >= output.len() {
                    return Err(io::Error::new(
                        io::ErrorKind::WriteZero,
                        "Output buffer full",
                    ));
                }
                output[out_pos] = entry.sym1;
                output[out_pos + 1] = entry.sym2;
                output[out_pos + 2] = entry.sym3;
                output[out_pos + 3] = entry.sym4;
                out_pos += 4;
            }
            _ => break,
        }
    }

    Ok(out_pos)
}

// =============================================================================
// AVX2 Gather-Based Huffman Decode (Phase 3.2)
// =============================================================================

/// Packed u32 table entry for gather-based decode
/// Format: bits[7:0] = code_length, bits[15:8] = symbol, bits[31] = literal_flag
#[derive(Clone, Copy, Default)]
#[repr(transparent)]
pub struct GatherEntry(pub u32);

impl GatherEntry {
    pub const LITERAL_FLAG: u32 = 1 << 31;
    pub const LENGTH_MASK: u32 = 0xFF;
    pub const SYMBOL_SHIFT: u32 = 8;

    #[inline(always)]
    pub fn literal(bits: u8, byte: u8) -> Self {
        GatherEntry(Self::LITERAL_FLAG | ((byte as u32) << Self::SYMBOL_SHIFT) | bits as u32)
    }

    #[inline(always)]
    pub fn length_code(bits: u8, len_idx: u8) -> Self {
        GatherEntry(((len_idx as u32) << Self::SYMBOL_SHIFT) | bits as u32)
    }

    #[inline(always)]
    pub fn is_literal(self) -> bool {
        self.0 & Self::LITERAL_FLAG != 0
    }

    #[inline(always)]
    pub fn symbol(self) -> u8 {
        ((self.0 >> Self::SYMBOL_SHIFT) & 0xFF) as u8
    }

    #[inline(always)]
    pub fn code_length(self) -> u8 {
        (self.0 & Self::LENGTH_MASK) as u8
    }
}

/// Table for AVX2 gather-based decode (10-bit, 4KB)
pub struct GatherTable {
    pub entries: Box<[GatherEntry; 1024]>,
}

impl GatherTable {
    /// Build table from Huffman code lengths
    pub fn build(lit_len_lens: &[u8]) -> Option<Self> {
        let mut entries = Box::new([GatherEntry::default(); 1024]);

        // Build canonical codes (simplified)
        let mut bl_count = [0u32; 16];
        for &len in lit_len_lens.iter().take(286) {
            if len > 0 {
                bl_count[len as usize] += 1;
            }
        }

        let mut next_code = [0u32; 16];
        let mut code = 0u32;
        for bits in 1..16 {
            code = (code + bl_count[bits - 1]) << 1;
            next_code[bits] = code;
        }

        // Fill table
        for (sym, &len) in lit_len_lens.iter().enumerate().take(286) {
            if len == 0 || len > 10 {
                continue;
            }
            let code = next_code[len as usize];
            next_code[len as usize] += 1;

            // Bit-reverse the code for little-endian lookup
            let mut rev = 0u32;
            for i in 0..len {
                if code & (1 << i) != 0 {
                    rev |= 1 << (len - 1 - i);
                }
            }

            // Fill all entries for this code
            let fill_count = 1 << (10 - len);
            for i in 0..fill_count {
                let idx = rev as usize | (i << len);
                if sym < 256 {
                    entries[idx] = GatherEntry::literal(len, sym as u8);
                } else {
                    entries[idx] = GatherEntry::length_code(len, (sym - 256) as u8);
                }
            }
        }

        Some(GatherTable { entries })
    }
}

/// AVX2 gather-based decode of 8 literals in parallel
///
/// This uses vpgatherdd to look up 8 table entries at once,
/// then processes them in a tight scalar loop.
#[cfg(all(target_arch = "x86_64", target_feature = "avx2"))]
#[allow(dead_code)]
pub unsafe fn decode_8_gather(
    table: &GatherTable,
    bit_positions: &[u64; 8],
    bitbuf: u64,
) -> ([u8; 8], [u8; 8]) {
    use std::arch::x86_64::*;

    // Create 8 indices from bit positions
    let mut indices = [0i32; 8];
    for i in 0..8 {
        indices[i] = ((bitbuf >> bit_positions[i]) & 0x3FF) as i32;
    }

    // Load indices into AVX2 register
    let idx_vec = _mm256_loadu_si256(indices.as_ptr() as *const __m256i);

    // Gather 8 entries from table
    let base_ptr = table.entries.as_ptr() as *const i32;
    let entries = _mm256_i32gather_epi32(base_ptr, idx_vec, 4);

    // Extract to array
    let mut entry_arr = [0u32; 8];
    _mm256_storeu_si256(entry_arr.as_mut_ptr() as *mut __m256i, entries);

    // Decode each entry
    let mut literals = [0u8; 8];
    let mut bits_consumed = [0u8; 8];

    for i in 0..8 {
        let e = GatherEntry(entry_arr[i]);
        literals[i] = e.symbol();
        bits_consumed[i] = e.code_length();
    }

    (literals, bits_consumed)
}

#[cfg(not(all(target_arch = "x86_64", target_feature = "avx2")))]
#[allow(dead_code, clippy::missing_safety_doc)]
pub unsafe fn decode_8_gather(
    _table: &GatherTable,
    _bit_positions: &[u64; 8],
    _bitbuf: u64,
) -> ([u8; 8], [u8; 8]) {
    // Fallback - not available
    ([0u8; 8], [0u8; 8])
}

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

    #[test]
    fn test_multi_sym_entry_size() {
        assert_eq!(std::mem::size_of::<MultiSymEntry>(), 8);
    }

    #[test]
    fn test_multi_sym_table_build() {
        // Build table with short codes that can fit multiple symbols
        // Use 4-bit codes so we can fit 3 symbols in 12 bits
        let mut lens = [0u8; 16];
        for (i, len) in lens.iter_mut().enumerate() {
            if i < 16 {
                *len = 4; // 4-bit codes for all 16 symbols
            }
        }

        let table = MultiSymTable::build(&lens).unwrap();

        // Check that we have some multi-symbol entries
        let mut single_count = 0;
        let mut multi_count = 0;
        for entry in &table.table {
            if entry.sym_count == 1 {
                single_count += 1;
            } else if entry.sym_count >= 2 {
                multi_count += 1;
            }
        }

        println!(
            "Single: {}, Multi: {}/{}",
            single_count, multi_count, MULTI_SYM_SIZE
        );

        // With 4-bit codes, we should have many multi-symbol entries
        // 12 bits / 4 bits = 3 symbols per entry on average
        assert!(multi_count > 0, "Should have some multi-symbol entries");
    }

    #[test]
    fn test_fixed_huffman_table() {
        // Fixed Huffman has 7-9 bit codes - may not have multi-symbol opportunities
        let mut lens = [0u8; 288];
        for len in lens.iter_mut().take(144) {
            *len = 8;
        }
        for len in lens.iter_mut().take(256).skip(144) {
            *len = 9;
        }
        for len in lens.iter_mut().take(280).skip(256) {
            *len = 7;
        }
        for len in lens.iter_mut().take(288).skip(280) {
            *len = 8;
        }

        let table = MultiSymTable::build(&lens).unwrap();

        let mut single_count = 0;
        let mut multi_count = 0;
        let mut non_literal_count = 0;
        for entry in &table.table {
            if entry.sym_count == 0 && entry.total_bits > 0 {
                non_literal_count += 1;
            } else if entry.sym_count == 1 {
                single_count += 1;
            } else if entry.sym_count >= 2 {
                multi_count += 1;
            }
        }

        println!(
            "Fixed Huffman: single={}, multi={}, non_literal={}",
            single_count, multi_count, non_literal_count
        );

        // Fixed Huffman might have 0 multi-symbol entries due to long codes
        // That's OK - we just use single-symbol entries
    }

    #[test]
    fn test_decode_multi_sym() {
        // Create simple test data
        let original = b"AAAAAABBBBBB"; // Repetitive data

        use flate2::write::DeflateEncoder;
        use flate2::Compression;
        use std::io::Write;

        let mut encoder = DeflateEncoder::new(Vec::new(), Compression::default());
        encoder.write_all(original).unwrap();
        let compressed = encoder.finish().unwrap();

        // Skip the first block header to get to the Huffman data
        // (This is a simplified test - real integration would parse the block)
        println!(
            "Compressed {} bytes to {} bytes",
            original.len(),
            compressed.len()
        );
    }

    #[test]
    fn benchmark_multi_sym_vs_single() {
        let data = match std::fs::read("benchmark_data/silesia-gzip.tar.gz") {
            Ok(d) => d,
            Err(_) => {
                eprintln!("Skipping - no benchmark file");
                return;
            }
        };

        // Build table for fixed Huffman
        let mut lens = [0u8; 288];
        for len in lens.iter_mut().take(144) {
            *len = 8;
        }
        for len in lens.iter_mut().take(256).skip(144) {
            *len = 9;
        }
        for len in lens.iter_mut().take(280).skip(256) {
            *len = 7;
        }
        for len in lens.iter_mut().take(288).skip(280) {
            *len = 8;
        }

        let table = MultiSymTable::build(&lens).unwrap();

        // Count multi-symbol opportunities
        let mut single_count = 0;
        let mut double_count = 0;
        let mut triple_count = 0;
        let mut quad_count = 0;

        for entry in &table.table {
            match entry.sym_count {
                1 => single_count += 1,
                2 => double_count += 1,
                3 => triple_count += 1,
                4 => quad_count += 1,
                _ => {}
            }
        }

        println!("\n=== Multi-Symbol Table Analysis ===");
        println!("1-symbol entries: {}", single_count);
        println!("2-symbol entries: {}", double_count);
        println!("3-symbol entries: {}", triple_count);
        println!("4-symbol entries: {}", quad_count);
        println!(
            "Multi-symbol ratio: {:.1}%",
            (double_count + triple_count + quad_count) as f64 / MULTI_SYM_SIZE as f64 * 100.0
        );

        // The file size is just for reference
        println!("Benchmark file size: {} bytes", data.len());
    }
}