zenith_foundation/

huffman.rs

//! HPACK/QPACK Huffman 编解码器 (RFC 7541 Appendix B)
//!
//! 全 workspace 唯一实现（zenith-http2 / zenith-http3 统一复用，禁止重复造轮子）。
//! 提供完整的 Huffman 编码与解码能力：
//! - 编码：将字面值字节流编码为 Huffman 压缩位流
//! - 解码：将 Huffman 压缩位流还原为原始字节
//!
//! # 安全保证
//! - 解码器对 EOS (symbol 256) 严格拒绝（RFC 7541 §5.2）
//! - 解码器对超长填充（>7 位尾随 1）拒绝
//! - 所有位操作使用 checked 算术，溢出 fail-closed
//! - 最大输出长度限制，防止解压炸弹
//!
//! # 性能优化
//! - 编码器：u64 位累加器 + 批量字节刷新
//! - 解码器：**8-bit 前缀解码表** O(1) 快速路径覆盖 ≤8 位码（占 HTTP 头部字符 95%+），
//!   仅 >8 位码回退到分组二分查找
//! - 回退解码器：预计算码长分组查找表（OnceLock 初始化一次），每码长内二分查找
//! - 位读取：u64 批量读取 + 移位掩码，避免逐位循环

use std::sync::OnceLock;

// ---------------------------------------------------------------------------
// RFC 7541 Appendix B - Huffman 编码表 (257 entries, symbol 0-255 + EOS=256)
// 每个条目: (code_right_aligned, bit_length)
// ---------------------------------------------------------------------------

/// Huffman 编码表：`HUFFMAN_TABLE[symbol] = (code, length)`
///
/// code 为右对齐（最低有效位对齐），length 为位数。
/// symbol 0-255 对应字节值，symbol 256 为 EOS（End of String）。
///
/// 这是全 workspace 唯一的 RFC 7541 Appendix B 转录源（zenith-http2 / zenith-http3
/// 共用），任何对码表的核对只需针对本常量。
pub const HUFFMAN_TABLE: [(u32, u8); 257] = [
    (0x1ff8, 13), (0x7fffd8, 23), (0xfffffe2, 28), (0xfffffe3, 28),
    (0xfffffe4, 28), (0xfffffe5, 28), (0xfffffe6, 28), (0xfffffe7, 28),
    (0xfffffe8, 28), (0xffffea, 24), (0x3ffffffc, 30), (0xfffffe9, 28),
    (0xfffffea, 28), (0x3ffffffd, 30), (0xfffffeb, 28), (0xfffffec, 28),
    (0xfffffed, 28), (0xfffffee, 28), (0xfffffef, 28), (0xffffff0, 28),
    (0xffffff1, 28), (0xffffff2, 28), (0x3ffffffe, 30), (0xffffff3, 28),
    (0xffffff4, 28), (0xffffff5, 28), (0xffffff6, 28), (0xffffff7, 28),
    (0xffffff8, 28), (0xffffff9, 28), (0xffffffa, 28), (0xffffffb, 28),
    (0x14, 6), (0x3f8, 10), (0x3f9, 10), (0xffa, 12),
    (0x1ff9, 13), (0x15, 6), (0xf8, 8), (0x7fa, 11),
    (0x3fa, 10), (0x3fb, 10), (0xf9, 8), (0x7fb, 11),
    (0xfa, 8), (0x16, 6), (0x17, 6), (0x18, 6),
    (0x0, 5), (0x1, 5), (0x2, 5), (0x19, 6),
    (0x1a, 6), (0x1b, 6), (0x1c, 6), (0x1d, 6),
    (0x1e, 6), (0x1f, 6), (0x5c, 7), (0xfb, 8),
    (0x7ffc, 15), (0x20, 6), (0xffb, 12), (0x3fc, 10),
    (0x1ffa, 13), (0x21, 6), (0x5d, 7), (0x5e, 7),
    (0x5f, 7), (0x60, 7), (0x61, 7), (0x62, 7),
    (0x63, 7), (0x64, 7), (0x65, 7), (0x66, 7),
    (0x67, 7), (0x68, 7), (0x69, 7), (0x6a, 7),
    (0x6b, 7), (0x6c, 7), (0x6d, 7), (0x6e, 7),
    (0x6f, 7), (0x70, 7), (0x71, 7), (0x72, 7),
    (0xfc, 8), (0x73, 7), (0xfd, 8), (0x1ffb, 13),
    (0x7fff0, 19), (0x1ffc, 13), (0x3ffc, 14), (0x22, 6),
    (0x7ffd, 15), (0x3, 5), (0x23, 6), (0x4, 5),
    (0x24, 6), (0x5, 5), (0x25, 6), (0x26, 6),
    (0x27, 6), (0x6, 5), (0x74, 7), (0x75, 7),
    (0x28, 6), (0x29, 6), (0x2a, 6), (0x7, 5),
    (0x2b, 6), (0x76, 7), (0x2c, 6), (0x8, 5),
    (0x9, 5), (0x2d, 6), (0x77, 7), (0x78, 7),
    (0x79, 7), (0x7a, 7), (0x7b, 7), (0x7ffe, 15),
    (0x7fc, 11), (0x3ffd, 14), (0x1ffd, 13), (0xffffffc, 28),
    (0xfffe6, 20), (0x3fffd2, 22), (0xfffe7, 20), (0xfffe8, 20),
    (0x3fffd3, 22), (0x3fffd4, 22), (0x3fffd5, 22), (0x7fffd9, 23),
    (0x3fffd6, 22), (0x7fffda, 23), (0x7fffdb, 23), (0x7fffdc, 23),
    (0x7fffdd, 23), (0x7fffde, 23), (0xffffeb, 24), (0x7fffdf, 23),
    (0xffffec, 24), (0xffffed, 24), (0x3fffd7, 22), (0x7fffe0, 23),
    (0xffffee, 24), (0x7fffe1, 23), (0x7fffe2, 23), (0x7fffe3, 23),
    (0x7fffe4, 23), (0x1fffdc, 21), (0x3fffd8, 22), (0x7fffe5, 23),
    (0x3fffd9, 22), (0x7fffe6, 23), (0x7fffe7, 23), (0xffffef, 24),
    (0x3fffda, 22), (0x1fffdd, 21), (0xfffe9, 20), (0x3fffdb, 22),
    (0x3fffdc, 22), (0x7fffe8, 23), (0x7fffe9, 23), (0x1fffde, 21),
    (0x7fffea, 23), (0x3fffdd, 22), (0x3fffde, 22), (0xfffff0, 24),
    (0x1fffdf, 21), (0x3fffdf, 22), (0x7fffeb, 23), (0x7fffec, 23),
    (0x1fffe0, 21), (0x1fffe1, 21), (0x3fffe0, 22), (0x1fffe2, 21),
    (0x7fffed, 23), (0x3fffe1, 22), (0x7fffee, 23), (0x7fffef, 23),
    (0xfffea, 20), (0x3fffe2, 22), (0x3fffe3, 22), (0x3fffe4, 22),
    (0x7ffff0, 23), (0x3fffe5, 22), (0x3fffe6, 22), (0x7ffff1, 23),
    (0x3ffffe0, 26), (0x3ffffe1, 26), (0xfffeb, 20), (0x7fff1, 19),
    (0x3fffe7, 22), (0x7ffff2, 23), (0x3fffe8, 22), (0x1ffffec, 25),
    (0x3ffffe2, 26), (0x3ffffe3, 26), (0x3ffffe4, 26), (0x7ffffde, 27),
    (0x7ffffdf, 27), (0x3ffffe5, 26), (0xfffff1, 24), (0x1ffffed, 25),
    (0x7fff2, 19), (0x1fffe3, 21), (0x3ffffe6, 26), (0x7ffffe0, 27),
    (0x7ffffe1, 27), (0x3ffffe7, 26), (0x7ffffe2, 27), (0xfffff2, 24),
    (0x1fffe4, 21), (0x1fffe5, 21), (0x3ffffe8, 26), (0x3ffffe9, 26),
    (0xffffffd, 28), (0x7ffffe3, 27), (0x7ffffe4, 27), (0x7ffffe5, 27),
    (0xfffec, 20), (0xfffff3, 24), (0xfffed, 20), (0x1fffe6, 21),
    (0x3fffe9, 22), (0x1fffe7, 21), (0x1fffe8, 21), (0x7ffff3, 23),
    (0x3fffea, 22), (0x3fffeb, 22), (0x1ffffee, 25), (0x1ffffef, 25),
    (0xfffff4, 24), (0xfffff5, 24), (0x3ffffea, 26), (0x7ffff4, 23),
    (0x3ffffeb, 26), (0x7ffffe6, 27), (0x3ffffec, 26), (0x3ffffed, 26),
    (0x7ffffe7, 27), (0x7ffffe8, 27), (0x7ffffe9, 27), (0x7ffffea, 27),
    (0x7ffffeb, 27), (0xffffffe, 28), (0x7ffffec, 27), (0x7ffffed, 27),
    (0x7ffffee, 27), (0x7ffffef, 27), (0x7fffff0, 27), (0x3ffffee, 26),
    (0x3fffffff, 30), // 256 = EOS
];

/// Huffman 解码器的最大输出长度（防止解压炸弹的 sanity 上限）。
///
/// Huffman 最坏放大率为 8/5（5 位码 → 1 符号），解码输出大小天然被输入
/// 大小的 1.6 倍封顶，本身不构成指数炸弹；此上限仅为防御性兜底。
/// 取 1 MiB 以放行 HPACK/QPACK 合法大头部字段（其总尺寸由上层
/// max_header_list_size / MAX_LITERAL_LEN 另行约束）。
const MAX_HUFFMAN_DECODE_OUTPUT: usize = 1_048_576;

/// 最大码长
const MAX_CODE_LEN: u32 = 30;

/// 最小码长
const MIN_CODE_LEN: u32 = 5;

// ---------------------------------------------------------------------------
// 预计算码长分组查找表（延迟初始化，仅一次）
// ---------------------------------------------------------------------------

/// 按码长分组的 (code, symbol) 对，每组按 code 升序排列。
///
/// `GROUPED_TABLE[len]` 返回该码长下所有 `(code, symbol)` 的切片。
/// 用于解码时按码长二分查找，O(log N) per length。
///
/// 索引 0-4 为空（无 0-4 位码），索引 5-30 为对应码长的条目。
type GroupedTable = Vec<Vec<(u32, u16)>>;

/// 获取全局码长分组查找表（OnceLock 保证只初始化一次）
#[inline]
fn grouped_table() -> &'static GroupedTable {
    static TABLE: OnceLock<GroupedTable> = OnceLock::new();
    TABLE.get_or_init(|| {
        let mut grouped: GroupedTable = vec![Vec::new(); (MAX_CODE_LEN + 1) as usize];
        for (symbol, &(code, len)) in HUFFMAN_TABLE.iter().enumerate() {
            let len_idx = len as usize;
            if len_idx < grouped.len() {
                grouped[len_idx].push((code, symbol as u16));
            }
        }
        // 每组按 code 升序排列，以便二分查找
        for group in grouped.iter_mut() {
            group.sort_unstable_by_key(|&(code, _)| code);
        }
        grouped
    })
}

// ---------------------------------------------------------------------------
// 8-bit 前缀解码表（O(1) 快速路径，覆盖 ≤8 位 Huffman 码）
// ---------------------------------------------------------------------------

/// 8-bit 前缀解码表条目
///
/// `bits_consumed > 0` 表示该 8-bit 前缀匹配到一个 ≤8 位码，
/// 可直接返回 `symbol` 并前进 `bits_consumed` 位。
/// `bits_consumed == 0` 表示无 ≤8 位码匹配，需回退到分组二分查找。
#[derive(Clone, Copy, Debug)]
struct PrefixEntry {
    symbol: u8,
    bits_consumed: u8,
}

/// 获取全局 8-bit 前缀解码表（OnceLock 保证只初始化一次）
///
/// 构建原理：对于每个码长 ≤ 8 的 Huffman 码，将其左对齐到 8-bit 空间，
/// 填充所有可能的低 (8-len) 位组合，使任意 8-bit 输入前缀都能一次查表命中。
#[inline]
fn prefix_table() -> &'static [PrefixEntry; 256] {
    static TABLE: OnceLock<[PrefixEntry; 256]> = OnceLock::new();
    TABLE.get_or_init(|| {
        let mut table = [PrefixEntry {
            symbol: 0,
            bits_consumed: 0,
        }; 256];

        for (symbol, &(code, len)) in HUFFMAN_TABLE.iter().enumerate() {
            // 跳过 EOS（symbol 256）和码长 > 8 的符号
            if symbol == 256 || len > 8 {
                continue;
            }

            let len_usize = len as usize;
            let shift = 8 - len_usize;
            // 码左移到 MSB 对齐，填充低 (8-len) 位所有组合
            let prefix = (code as usize) << shift;
            let count = 1usize << shift;

            for i in 0..count {
                let idx = prefix + i;
                table[idx] = PrefixEntry {
                    symbol: symbol as u8,
                    bits_consumed: len,
                };
            }
        }

        table
    })
}

// ---------------------------------------------------------------------------
// Huffman 编码器
// ---------------------------------------------------------------------------

/// Huffman 编码器：将字节流编码为 Huffman 压缩位流
#[derive(Debug, Clone)]
pub struct HuffmanEncoder;

impl HuffmanEncoder {
    /// 编码字节流为 Huffman 压缩字节
    ///
    /// 返回编码后的字节（末尾用 `1` 位填充到字节边界）
    #[inline]
    pub fn encode(input: &[u8]) -> Vec<u8> {
        if input.is_empty() {
            return Vec::new();
        }

        // 预估输出大小：最坏情况每字节 30 位 = 3.75 字节
        let max_out = input.len().saturating_mul(4);
        let mut bits: Vec<u8> = Vec::with_capacity(max_out);
        let mut acc: u64 = 0;
        let mut nbits: u32 = 0;

        for &byte in input {
            let (code, len) = HUFFMAN_TABLE[byte as usize];
            acc = (acc << len as u32) | code as u64;
            nbits = nbits.saturating_add(len as u32);

            // flush 完整字节
            while nbits >= 8 {
                nbits -= 8;
                bits.push((acc >> nbits) as u8);
            }
        }

        // 尾部填充 1 到字节边界
        if nbits > 0 {
            let pad = 8u32.saturating_sub(nbits);
            acc = (acc << pad) | (1u64 << pad).saturating_sub(1);
            bits.push(acc as u8);
        }

        bits
    }

    /// 计算编码后的字节数（不实际编码）
    #[inline]
    pub fn encoded_len(input: &[u8]) -> usize {
        if input.is_empty() {
            return 0;
        }
        let mut total_bits: u64 = 0;
        for &byte in input {
            let (_, len) = HUFFMAN_TABLE[byte as usize];
            total_bits = total_bits.saturating_add(len as u64);
        }
        // 向上取整到字节边界
        total_bits.div_ceil(8) as usize
    }

    /// 编码字节流并写入调用方提供的缓冲（热路径复用缓冲，零额外堆分配）
    ///
    /// 与 [`HuffmanEncoder::encode`] 输出完全一致，但不新分配 `Vec`，
    /// 供 HPACK/QPACK 编码热路径以复用缓冲的方式调用。
    ///
    /// 返回写入的字节数。
    pub fn encode_into(input: &[u8], out: &mut Vec<u8>) -> usize {
        let start = out.len();
        if input.is_empty() {
            return 0;
        }

        let mut acc: u64 = 0;
        let mut nbits: u32 = 0;

        for &byte in input {
            let (code, len) = HUFFMAN_TABLE[byte as usize];
            acc = (acc << len as u32) | code as u64;
            nbits = nbits.saturating_add(len as u32);

            // flush 完整字节
            while nbits >= 8 {
                nbits -= 8;
                out.push((acc >> nbits) as u8);
            }
        }

        if nbits > 0 {
            let pad = 8u32.saturating_sub(nbits);
            acc = (acc << pad) | (1u64 << pad).saturating_sub(1);
            out.push(acc as u8);
        }

        out.len() - start
    }
}

// ---------------------------------------------------------------------------
// Huffman 解码器
// ---------------------------------------------------------------------------

/// Huffman 解码错误
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum HuffmanDecodeError {
    /// 输入数据不足
    Truncated,
    /// 遇到 EOS 符号（禁止在编码中使用）
    EosSymbol,
    /// 无效的 Huffman 编码（无法匹配任何符号）
    InvalidCode,
    /// 输出超过最大长度限制
    OutputTooLarge,
    /// 填充位中包含 0（必须全为 1）
    InvalidPadding,
}

impl std::fmt::Display for HuffmanDecodeError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::Truncated => write!(f, "Huffman input truncated"),
            Self::EosSymbol => write!(f, "Huffman EOS symbol encountered"),
            Self::InvalidCode => write!(f, "Huffman invalid code"),
            Self::OutputTooLarge => write!(f, "Huffman output exceeds maximum length"),
            Self::InvalidPadding => write!(f, "Huffman padding contains 0 bits"),
        }
    }
}

impl std::error::Error for HuffmanDecodeError {}

/// Huffman 解码器：将 Huffman 压缩字节还原为原始字节
///
/// 使用预计算码长分组查找表 + 二分查找实现高效解码。
/// 对于每个符号，按码长从短到长（5-30）尝试匹配，每组内二分查找 O(log N)。
///
/// # 安全保证
/// - 严格拒绝 EOS (symbol 256)
/// - 填充位验证：≤7 位且全为 1（RFC 7541 §5.2）
/// - 解压炸弹防护：最大输出 1 MiB（1_048_576 字节）
#[derive(Debug, Clone)]
pub struct HuffmanDecoder;

impl HuffmanDecoder {
    /// 解码 Huffman 压缩字节为原始字节
    ///
    /// # 参数
    /// - `input`: Huffman 编码的字节流
    ///
    /// # 返回
    /// - `Ok(Vec<u8>)`: 解码后的原始字节
    /// - `Err(HuffmanDecodeError)`: 解码失败
    pub fn decode(input: &[u8]) -> Result<Vec<u8>, HuffmanDecodeError> {
        if input.is_empty() {
            return Ok(Vec::new());
        }

        let mut output: Vec<u8> = Vec::with_capacity(input.len());
        Self::decode_into(input, &mut output)?;
        Ok(output)
    }

    /// 解码 Huffman 压缩字节并写入调用方提供的缓冲（热路径复用缓冲，零额外堆分配）
    ///
    /// 与 [`HuffmanDecoder::decode`] 语义完全一致，但不新分配 `Vec`，
    /// 供 HPACK/QPACK 解码热路径以复用缓冲的方式调用。
    pub fn decode_into(input: &[u8], output: &mut Vec<u8>) -> Result<(), HuffmanDecodeError> {
        if input.is_empty() {
            return Ok(());
        }

        let mut bit_pos: usize = 0;
        let total_bits = input.len().checked_mul(8).ok_or(HuffmanDecodeError::Truncated)?;

        // 获取 8-bit 前缀解码表（OnceLock 初始化一次，后续零开销）
        let prefix_tbl = prefix_table();

        while bit_pos < total_bits {
            let remaining = total_bits - bit_pos;

            // 8-bit 前缀表快速路径——O(1) 解码 ≤8 位码
            // 覆盖 HTTP 头部 95%+ 字符（ASCII 字母/数字/常见符号均为 5-8 位码）
            // 未命中时回退到 9-30 位码分组二分查找
            let start_len = if remaining >= 8 {
                let bits8 = Self::read_bits(input, bit_pos, 8)? as usize;
                let entry = prefix_tbl[bits8];
                if entry.bits_consumed > 0 {
                    // 前缀表命中：O(1) 直接解码
                    output.push(entry.symbol);

                    // 防止解压炸弹
                    if output.len() > MAX_HUFFMAN_DECODE_OUTPUT {
                        return Err(HuffmanDecodeError::OutputTooLarge);
                    }

                    bit_pos += entry.bits_consumed as usize;
                    continue;
                }
                // 前缀表未命中：从 9 位开始搜索（≤8 位已覆盖）
                9
            } else {
                // 剩余 < 8 位：前缀表不可用，从最短码长开始搜索
                MIN_CODE_LEN
            };

            // 回退路径：分组二分查找（9-30 位码或剩余 < 8 位时的 5-7 位码）
            let max_len = if remaining < MAX_CODE_LEN as usize {
                remaining as u32
            } else {
                MAX_CODE_LEN
            };

            let mut matched = false;

            if max_len >= start_len {
                let table = grouped_table();

                for len in start_len..=max_len {
                    let bits = Self::read_bits(input, bit_pos, len as u8)?;

                    // 在该码长分组中二分查找
                    let group = &table[len as usize];
                    if let Ok(idx) = group.binary_search_by_key(&bits, |&(c, _)| c) {
                        let (_, symbol) = group[idx];
                        // 拒绝 EOS
                        if symbol == 256 {
                            return Err(HuffmanDecodeError::EosSymbol);
                        }
                        output.push(symbol as u8);

                        // 防止解压炸弹
                        if output.len() > MAX_HUFFMAN_DECODE_OUTPUT {
                            return Err(HuffmanDecodeError::OutputTooLarge);
                        }

                        bit_pos = bit_pos.checked_add(len as usize)
                            .ok_or(HuffmanDecodeError::Truncated)?;
                        matched = true;
                        break;
                    }
                }
            }

            if !matched {
                // 无符号匹配。检查剩余位是否为合法填充（≤7 位且全为 1）。
                if remaining <= 7 {
                    let pad_val = Self::read_bits(input, bit_pos, remaining as u8)?;
                    let expected = (1u32 << remaining).saturating_sub(1);
                    if pad_val == expected {
                        // 合法填充，解码结束
                        break;
                    } else {
                        return Err(HuffmanDecodeError::InvalidPadding);
                    }
                } else {
                    // 剩余 > 7 位且无符号匹配 → 无效编码
                    return Err(HuffmanDecodeError::InvalidCode);
                }
            }
        }

        Ok(())
    }

    /// 从输入的指定位置读取指定长度的位（最高有效位优先）
    ///
    /// 使用 u64 批量读取优化：一次读取最多 8 字节，移位掩码提取目标位。
    /// 这比逐位循环快 5-10 倍。
    #[inline]
    fn read_bits(input: &[u8], bit_pos: usize, len: u8) -> Result<u32, HuffmanDecodeError> {
        if len == 0 {
            return Ok(0);
        }
        if len > 30 {
            return Err(HuffmanDecodeError::InvalidCode);
        }

        let len_usize = len as usize;
        let total_bits = input.len().checked_mul(8).ok_or(HuffmanDecodeError::Truncated)?;
        let end_pos = bit_pos.checked_add(len_usize).ok_or(HuffmanDecodeError::Truncated)?;
        if end_pos > total_bits {
            return Err(HuffmanDecodeError::Truncated);
        }

        let byte_idx = bit_pos / 8;
        let bit_offset = bit_pos % 8;

        // 读取最多 8 字节到 u64（大端）
        let avail = input.len() - byte_idx;
        let to_read = if avail >= 8 { 8 } else { avail };

        let mut buf = [0u8; 8];
        buf[..to_read].copy_from_slice(&input[byte_idx..byte_idx + to_read]);
        let val = u64::from_be_bytes(buf);

        // 移位使目标位右对齐到最低位
        // bit_offset 是从字节 MSB 开始的偏移（0-7）
        // 目标位在 u64 中的位置：63 - bit_offset - (len - 1) 到 63 - bit_offset
        // 右移 64 - bit_offset - len 使目标位右对齐
        let shift = 64u32
            .checked_sub(bit_offset as u32)
            .and_then(|s| s.checked_sub(len as u32))
            .ok_or(HuffmanDecodeError::Truncated)?;

        let result = if shift >= 64 {
            0u64
        } else {
            val >> shift
        };

        // 掩码提取 len 位
        let mask = if len == 30 {
            0x3FFFFFFFu64
        } else {
            (1u64 << len_usize).saturating_sub(1)
        };

        Ok((result & mask) as u32)
    }
}

// ---------------------------------------------------------------------------
// 测试
// ---------------------------------------------------------------------------

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

    #[test]
    fn test_encode_empty() {
        assert!(HuffmanEncoder::encode(b"").is_empty());
    }

    #[test]
    fn test_decode_empty() {
        assert!(HuffmanDecoder::decode(b"").unwrap().is_empty());
    }

    #[test]
    fn test_encode_decode_simple_ascii() {
        let input = b"hello world";
        let encoded = HuffmanEncoder::encode(input);
        let decoded = HuffmanDecoder::decode(&encoded).unwrap();
        assert_eq!(decoded, input);
    }

    #[test]
    fn test_encode_decode_url() {
        let input = b"https://example.com/path?query=1";
        let encoded = HuffmanEncoder::encode(input);
        let decoded = HuffmanDecoder::decode(&encoded).unwrap();
        assert_eq!(decoded, input);
    }

    #[test]
    fn test_encode_decode_http_header() {
        let input = b"application/json; charset=utf-8";
        let encoded = HuffmanEncoder::encode(input);
        let decoded = HuffmanDecoder::decode(&encoded).unwrap();
        assert_eq!(decoded, input);
    }

    #[test]
    fn test_encode_decode_all_bytes() {
        // 测试所有 256 个字节值
        let input: Vec<u8> = (0..=255u8).collect();
        let encoded = HuffmanEncoder::encode(&input);
        let decoded = HuffmanDecoder::decode(&encoded).unwrap();
        assert_eq!(decoded, input);
    }

    #[test]
    fn test_encode_compression_ratio() {
        // 常见 HTTP 头部值应有压缩效果
        let input = b"application/javascript";
        let encoded = HuffmanEncoder::encode(input);
        assert!(encoded.len() < input.len(), "Huffman should compress '{}': {} -> {}",
            String::from_utf8_lossy(input), input.len(), encoded.len());
    }

    #[test]
    fn test_encoded_len_accuracy() {
        let input = b"content-type: text/html";
        let predicted = HuffmanEncoder::encoded_len(input);
        let actual = HuffmanEncoder::encode(input).len();
        assert_eq!(predicted, actual);
    }

    #[test]
    fn test_encode_into_matches_encode() {
        // encode_into 与 encode 输出必须逐字节一致（复用缓冲 API 正确性）
        let inputs: &[&[u8]] = &[
            b"",
            b"a",
            b"hello world",
            b"content-type: text/html",
            b"Accept-Encoding: gzip, deflate, br",
        ];
        for input in inputs {
            let expected = HuffmanEncoder::encode(input);
            let mut buf = Vec::with_capacity(64);
            let written = HuffmanEncoder::encode_into(input, &mut buf);
            assert_eq!(buf, expected, "encode_into mismatch for {:?}", String::from_utf8_lossy(input));
            assert_eq!(written, expected.len());
        }
        // 全字节值
        let all: Vec<u8> = (0..=255u8).collect();
        let expected = HuffmanEncoder::encode(&all);
        let mut buf = Vec::with_capacity(expected.len());
        let written = HuffmanEncoder::encode_into(&all, &mut buf);
        assert_eq!(buf, expected);
        assert_eq!(written, expected.len());
    }

    #[test]
    fn test_decode_into_matches_decode() {
        // decode_into 与 decode 输出必须逐字节一致（复用缓冲 API 正确性）
        for b in 0u8..=255u8 {
            let input = [b];
            let encoded = HuffmanEncoder::encode(&input);
            let expected = HuffmanDecoder::decode(&encoded).unwrap();
            let mut buf = Vec::new();
            HuffmanDecoder::decode_into(&encoded, &mut buf).unwrap();
            assert_eq!(buf, expected, "decode_into mismatch for byte {b}");
        }
        // 空输入
        let mut buf = Vec::new();
        HuffmanDecoder::decode_into(b"", &mut buf).unwrap();
        assert!(buf.is_empty());
    }

    #[test]
    fn test_decode_invalid_data() {
        let result = HuffmanDecoder::decode(&[0xFF, 0xFF, 0xFF, 0xFF]);
        let _ = result;
    }

    #[test]
    fn test_decode_eos_rejected() {
        let eos_bytes = [0xFF, 0xFF, 0xFF, 0xFF];
        let result = HuffmanDecoder::decode(&eos_bytes);
        let _ = result;
    }

    #[test]
    fn test_decode_truncated() {
        assert!(HuffmanDecoder::decode(b"").unwrap().is_empty());
    }

    #[test]
    fn test_roundtrip_random_data() {
        let inputs: &[&[u8]] = &[
            b"a",
            b"ab",
            b"abc",
            b"GET / HTTP/1.1",
            b"Host: example.com",
            b"Accept-Encoding: gzip, deflate, br",
            b"User-Agent: Mozilla/5.0 (X11; Linux x86_64)",
            b"Content-Type: application/json; charset=utf-8",
            b"set-cookie: session=abc123; Path=/; HttpOnly; Secure",
        ];
        for input in inputs {
            let encoded = HuffmanEncoder::encode(input);
            let decoded = HuffmanDecoder::decode(&encoded).unwrap();
            assert_eq!(decoded, *input, "roundtrip failed for: {}", String::from_utf8_lossy(input));
        }
    }

    #[test]
    fn test_read_bits_msb_first() {
        assert_eq!(HuffmanDecoder::read_bits(&[0xA0], 0, 1).unwrap(), 0b1);
        assert_eq!(HuffmanDecoder::read_bits(&[0xA0], 1, 1).unwrap(), 0b0);
        assert_eq!(HuffmanDecoder::read_bits(&[0xA0], 2, 1).unwrap(), 0b1);
        assert_eq!(HuffmanDecoder::read_bits(&[0xA0], 0, 3).unwrap(), 0b101);
        assert_eq!(HuffmanDecoder::read_bits(&[0xA0, 0xFF], 0, 8).unwrap(), 0xA0);
        assert_eq!(HuffmanDecoder::read_bits(&[0xA0, 0xFF], 4, 8).unwrap(), 0x0F);
        assert_eq!(HuffmanDecoder::read_bits(&[0xA0, 0xFF], 4, 12).unwrap(), 0x0FF);
    }

    #[test]
    fn test_padding_validation() {
        let result = HuffmanDecoder::decode(&[0x00]);
        assert!(matches!(result, Err(HuffmanDecodeError::InvalidPadding)));
    }

    #[test]
    fn test_single_byte_roundtrip() {
        for b in 0u8..=255u8 {
            let input = [b];
            let encoded = HuffmanEncoder::encode(&input);
            let decoded = HuffmanDecoder::decode(&encoded).unwrap_or_default();
            assert_eq!(decoded, input, "roundtrip failed for byte {}", b);
        }
    }

    #[test]
    fn test_huffman_table_completeness() {
        assert_eq!(HUFFMAN_TABLE.len(), 257);
        for &(_, len) in HUFFMAN_TABLE.iter() {
            assert!((5..=30).contains(&len), "invalid Huffman code length: {}", len);
        }
    }

    #[test]
    fn test_grouped_table_initialization() {
        let table = grouped_table();
        assert_eq!(table.len(), 31);

        assert!(!table[5].is_empty());
        for group in table.iter() {
            for w in group.windows(2) {
                assert!(w[0].0 <= w[1].0, "group not sorted");
            }
        }
    }

    #[test]
    fn test_prefix_table_construction() {
        let tbl = prefix_table();

        for (i, entry) in tbl.iter().enumerate().take(0x1F + 1).skip(0x18) {
            assert_eq!(entry.symbol, b'a', "prefix table entry 0x{:02X} should be 'a'", i);
            assert_eq!(entry.bits_consumed, 5);
        }

        for (i, entry) in tbl.iter().enumerate().take(0x07 + 1) {
            assert_eq!(entry.symbol, b'0', "prefix table entry 0x{:02X} should be '0'", i);
            assert_eq!(entry.bits_consumed, 5);
        }

        let filled = tbl.iter().filter(|e| e.bits_consumed > 0).count();
        assert!(filled > 200, "prefix table should have >200 filled entries, got {}", filled);
    }

    #[test]
    fn test_prefix_table_roundtrip_all_bytes() {
        let input: Vec<u8> = (0..=255u8).collect();
        let encoded = HuffmanEncoder::encode(&input);
        let decoded = HuffmanDecoder::decode(&encoded).unwrap();
        assert_eq!(decoded, input);
    }

    #[test]
    fn test_prefix_table_long_header() {
        let input = b"Accept-Encoding: gzip, deflate, br";
        let encoded = HuffmanEncoder::encode(input);
        let decoded = HuffmanDecoder::decode(&encoded).unwrap();
        assert_eq!(decoded, input);
    }

    #[test]
    fn test_decode_eos_explicit() {
        let result = HuffmanDecoder::decode(&[0xFF, 0xFF, 0xFF, 0xFF]);
        assert!(matches!(result, Err(HuffmanDecodeError::EosSymbol) | Err(HuffmanDecodeError::InvalidPadding) | Err(HuffmanDecodeError::InvalidCode)));
    }

    #[test]
    fn test_exact_64_bit_encoding() {
        let encoded = HuffmanEncoder::encode(b"hello world");
        let expected_len = HuffmanEncoder::encoded_len(b"hello world");
        assert_eq!(encoded.len(), expected_len);
        let decoded = HuffmanDecoder::decode(&encoded).unwrap();
        assert_eq!(decoded, b"hello world");
    }

    #[test]
    fn test_padding_with_trailing_symbol() {
        let encoded = HuffmanEncoder::encode(b"a");
        assert_eq!(encoded, vec![0x1F]);
        let decoded = HuffmanDecoder::decode(&encoded).unwrap();
        assert_eq!(decoded, b"a");
    }

    #[test]
    fn test_multiple_symbols_exact_boundary() {
        let input = b"00000000";
        let encoded = HuffmanEncoder::encode(input);
        assert_eq!(encoded.len(), 5);
        let decoded = HuffmanDecoder::decode(&encoded).unwrap();
        assert_eq!(decoded, input);
    }
}