shoco 0.1.0

//! Shoco - A fast compressor for short strings
//!
//! A Rust port of the shoco library. Optimized for short ASCII strings using
//! entropy encoding based on English character frequency and bigram patterns.

const PACK_COUNT: usize = 3;
const MAX_SUCCESSOR_CHAIN_LENGTH: usize = 7;
const MIN_CHR: u8 = 39;

#[rustfmt::skip]
const CHARACTER_BY_ID: [u8; 32] = [
    b'e', b'a', b'i', b'o', b't', b'h', b'n', b'r', b's', b'l', b'u', b'c', b'w', b'm', b'd', b'b',
    b'p', b'f', b'g', b'v', b'y', b'k', b'-', b'H', b'M', b'T', b'\'', b'B', b'x', b'I', b'W', b'L',
];

/// Reverse lookup: ASCII byte -> character_id (-1 if not in common set)
#[rustfmt::skip]
const CHARACTER_ID_BY_BYTE: [i8; 256] = [
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, 26, -1, -1, -1, -1, -1, 22, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, 27, -1, -1, -1, -1, -1, 23, 29, -1, -1, 31, 24, -1, -1,
    -1, -1, -1, -1, 25, -1, -1, 30, -1, -1, -1, -1, -1, -1, -1, -1,
    -1,  1, 15, 11, 14,  0, 17, 18,  5,  2, -1, 21,  9, 13,  6,  3,
    16, -1,  7,  8,  4, 10, 19, 12, 28, 20, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
];

/// Bigram encoding: [predecessor_id][successor_id] -> compressed_successor_index
/// -1 means this bigram cannot be encoded (too rare in training data)
#[rustfmt::skip]
const SUCCESSOR_INDEX_BY_CHARACTER_IDS: [[i8; 32]; 32] = [
    [ 7,  4, 12, -1,  6, -1,  1,  0,  3,  5, -1,  9, -1,  8,  2, -1, 15, 14, -1, 10, 11, -1, -1, -1, -1, -1, -1, -1, 13, -1, -1, -1],
    [-1, -1,  6, -1,  1, -1,  0,  3,  2,  4, 15, 11, -1,  9,  5, 10, 13, -1, 12,  8,  7, 14, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 9, 11, -1,  4,  2, -1,  0,  8,  1,  5, -1,  6, -1,  3,  7, 15, -1, 12, 10, 13, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [-1, -1, 14,  7,  5, -1,  1,  2,  8,  9,  0, 15,  6,  4, 11, -1, 12,  3, -1, 10, -1, 13, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 2,  4,  3,  1,  5,  0, -1,  6, 10,  9,  7, 12, 11, -1, -1, -1, -1, 13, -1, -1,  8, -1, 15, -1, -1, -1, 14, -1, -1, -1, -1, -1],
    [ 0,  1,  2,  3,  4, -1, -1,  5,  9, 10,  6, -1, -1,  8, 15, 11, -1, 14, -1, -1,  7, -1, 13, -1, -1, -1, 12, -1, -1, -1, -1, -1],
    [ 2,  8,  7,  4,  3, -1,  9, -1,  6, 11, -1,  5, -1, -1,  0, -1, -1, 14,  1, 15, 10, 12, -1, -1, -1, -1, 13, -1, -1, -1, -1, -1],
    [ 0,  3,  1,  2,  6, -1,  9,  8,  4, 12, 13, 10, -1, 11,  7, -1, -1, 15, 14, -1,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 0,  6,  3,  4,  1,  2, -1, -1,  5, 10,  7,  9, 11, 12, -1, -1,  8, 14, -1, -1, 15, 13, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 0,  6,  2,  5,  9, -1, -1, -1, 10,  1,  8, -1, 12, 14,  4, -1, 15,  7, -1, 13,  3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 8, 10,  9, 15,  1, -1,  4,  0,  3,  2, -1,  6, -1, 12, 11, 13,  7, 14,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 1,  3,  6,  0,  4,  2, -1,  7, 13,  8,  9, 11, -1, -1, 15, -1, -1, -1, -1, -1, 10,  5, 14, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 3,  0,  1,  4, -1,  2,  5,  6,  7,  8, -1, 14, -1, -1,  9, 15, -1, 12, -1, -1, -1, 10, 11, -1, -1, -1, 13, -1, -1, -1, -1, -1],
    [ 0,  1,  3,  2, 15, -1, 12, -1,  7, 14,  4, -1, -1,  9, -1,  8,  5, 10, -1, -1,  6, -1, 13, -1, -1, -1, 11, -1, -1, -1, -1, -1],
    [ 0,  3,  1,  2, -1, -1, 12,  6,  4,  9,  7, -1, -1, 14,  8, -1, -1, 15, 11, 13,  5, -1, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 0,  5,  7,  2, 10, 13, -1,  6,  8,  1,  3, -1, -1, 14, 15, 11, -1, -1, -1, 12,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 0,  2,  6,  3,  7, 10, -1,  1,  9,  4,  8, -1, -1, 15, -1, 12,  5, -1, -1, -1, 11, -1, 13, -1, -1, -1, 14, -1, -1, -1, -1, -1],
    [ 1,  3,  4,  0,  7, -1, 12,  2, 11,  8,  6, 13, -1, -1, -1, -1, -1,  5, -1, -1, 10, 15,  9, -1, -1, -1, 14, -1, -1, -1, -1, -1],
    [ 1,  3,  5,  2, 13,  0,  9,  4,  7,  6,  8, -1, -1, 15, -1, 11, -1, -1, 10, -1, 14, -1, 12, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 0,  2,  1,  3, -1, -1, -1,  6, -1, -1,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 1, 11,  4,  0,  3, -1, 13, 12,  2,  7, -1, -1, 15, 10,  5,  8, 14, -1, -1, -1, -1, -1,  9, -1, -1, -1,  6, -1, -1, -1, -1, -1],
    [ 0,  9,  2, 14, 15,  4,  1, 13,  3,  5, -1, -1, 10, -1, -1, -1, -1,  6, 12, -1,  7, -1,  8, -1, -1, -1, 11, -1, -1, -1, -1, -1],
    [-1,  2, 14, -1,  1,  5,  8,  7,  4, 12, -1,  6,  9, 11, 13,  3, 10, 15, -1, -1, -1, -1,  0, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 0,  1,  3,  2, -1, -1, -1, -1, -1, -1,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 4,  3,  1,  5, -1, -1, -1,  0, -1, -1,  6, -1, -1, -1, -1, -1, -1, -1, -1, -1,  2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [ 2,  8,  4,  1, -1,  0, -1,  6, -1, -1,  5, -1,  7, -1, -1, -1, -1, -1, -1, -1, 10, -1, -1,  9, -1, -1, -1, -1, -1, -1, -1, -1],
    [12,  5, -1, -1,  1, -1, -1,  7,  0,  3, -1,  2, -1,  4,  6, -1, -1, -1, -1,  8, -1, -1, 15, -1, 13,  9, -1, -1, -1, -1, -1, 11],
    [ 1,  3,  2,  4, -1, -1, -1,  5, -1,  7,  0, -1, -1, -1, -1, -1, -1, -1, -1, -1,  6, -1, -1, -1, -1, -1, -1, -1, -1,  8, -1, -1],
    [ 5,  3,  4, 12,  1,  6, -1, -1, -1, -1,  8,  2, -1, -1, -1, -1,  0,  9, -1, -1, 11, -1, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1],
    [-1, -1, -1, -1,  0, -1,  1, 12,  3, -1, -1, -1, -1,  5, -1, -1, -1,  2, -1, -1, -1, -1, -1, -1, -1, -1,  4, -1, -1,  6, -1, 10],
    [ 2,  3,  1,  4, -1,  0, -1,  5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,  7, -1, -1, -1, -1, -1, -1, -1, -1,  6, -1, -1],
    [ 5,  1,  3,  0, -1, -1, -1, -1, -1, -1,  4, -1, -1, -1, -1, -1, -1, -1, -1, -1,  2, -1, -1, -1, -1, -1,  9, -1, -1,  6, -1,  7],
];

/// Decompression lookup: [char - MIN_CHR][successor_index] -> successor_char
/// 0 means invalid entry, NUL values in strings need handling.
#[rustfmt::skip]
const SUCCESSOR_CHARACTER_BY_CHAR_AND_INDEX: [[i8; 16]; 83] = [
    [b's' as i8, b't' as i8, b'c' as i8, b'l' as i8, b'm' as i8, b'a' as i8, b'd' as i8, b'r' as i8, b'v' as i8, b'T' as i8, b'A' as i8, b'L' as i8, b'e' as i8, b'M' as i8, b'Y' as i8, b'-' as i8],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [b'-' as i8, b't' as i8, b'a' as i8, b'b' as i8, b's' as i8, b'h' as i8, b'c' as i8, b'r' as i8, b'n' as i8, b'w' as i8, b'p' as i8, b'm' as i8, b'l' as i8, b'd' as i8, b'i' as i8, b'f' as i8],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [b'u' as i8, b'e' as i8, b'i' as i8, b'a' as i8, b'o' as i8, b'r' as i8, b'y' as i8, b'l' as i8, b'I' as i8, b'E' as i8, b'R' as i8, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [b'e' as i8, b'a' as i8, b'o' as i8, b'i' as i8, b'u' as i8, b'A' as i8, b'y' as i8, b'E' as i8, 0, 0, 0, 0, 0, 0, 0, 0],
    [b't' as i8, b'n' as i8, b'f' as i8, b's' as i8, b'\'' as i8, b'm' as i8, b'I' as i8, b'N' as i8, b'A' as i8, b'E' as i8, b'L' as i8, b'Z' as i8, b'r' as i8, b'V' as i8, b'R' as i8, b'C' as i8],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [b'o' as i8, b'a' as i8, b'y' as i8, b'i' as i8, b'u' as i8, b'e' as i8, b'I' as i8, b'L' as i8, b'D' as i8, b'\'' as i8, b'E' as i8, b'Y' as i8, 0, 0, 0, 0],
    [b'r' as i8, b'i' as i8, b'y' as i8, b'a' as i8, b'e' as i8, b'o' as i8, b'u' as i8, b'Y' as i8, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [b'h' as i8, b'o' as i8, b'e' as i8, b'E' as i8, b'i' as i8, b'u' as i8, b'r' as i8, b'w' as i8, b'a' as i8, b'H' as i8, b'y' as i8, b'R' as i8, b'Z' as i8, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [b'h' as i8, b'i' as i8, b'e' as i8, b'a' as i8, b'o' as i8, b'r' as i8, b'I' as i8, b'y' as i8, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [b'n' as i8, b't' as i8, b's' as i8, b'r' as i8, b'l' as i8, b'd' as i8, b'i' as i8, b'y' as i8, b'v' as i8, b'm' as i8, b'b' as i8, b'c' as i8, b'g' as i8, b'p' as i8, b'k' as i8, b'u' as i8],
    [b'e' as i8, b'l' as i8, b'o' as i8, b'u' as i8, b'y' as i8, b'a' as i8, b'r' as i8, b'i' as i8, b's' as i8, b'j' as i8, b't' as i8, b'b' as i8, b'v' as i8, b'h' as i8, b'm' as i8, b'd' as i8],
    [b'o' as i8, b'e' as i8, b'h' as i8, b'a' as i8, b't' as i8, b'k' as i8, b'i' as i8, b'r' as i8, b'l' as i8, b'u' as i8, b'y' as i8, b'c' as i8, b'q' as i8, b's' as i8, b'-' as i8, b'd' as i8],
    [b'e' as i8, b'i' as i8, b'o' as i8, b'a' as i8, b's' as i8, b'y' as i8, b'r' as i8, b'u' as i8, b'd' as i8, b'l' as i8, b'-' as i8, b'g' as i8, b'n' as i8, b'v' as i8, b'm' as i8, b'f' as i8],
    [b'r' as i8, b'n' as i8, b'd' as i8, b's' as i8, b'a' as i8, b'l' as i8, b't' as i8, b'e' as i8, b'm' as i8, b'c' as i8, b'v' as i8, b'y' as i8, b'i' as i8, b'x' as i8, b'f' as i8, b'p' as i8],
    [b'o' as i8, b'e' as i8, b'r' as i8, b'a' as i8, b'i' as i8, b'f' as i8, b'u' as i8, b't' as i8, b'l' as i8, b'-' as i8, b'y' as i8, b's' as i8, b'n' as i8, b'c' as i8, b'\'' as i8, b'k' as i8],
    [b'h' as i8, b'e' as i8, b'o' as i8, b'a' as i8, b'r' as i8, b'i' as i8, b'l' as i8, b's' as i8, b'u' as i8, b'n' as i8, b'g' as i8, b'b' as i8, b'-' as i8, b't' as i8, b'y' as i8, b'm' as i8],
    [b'e' as i8, b'a' as i8, b'i' as i8, b'o' as i8, b't' as i8, b'r' as i8, b'u' as i8, b'y' as i8, b'm' as i8, b's' as i8, b'l' as i8, b'b' as i8, b'\'' as i8, b'-' as i8, b'f' as i8, b'd' as i8],
    [b'n' as i8, b's' as i8, b't' as i8, b'm' as i8, b'o' as i8, b'l' as i8, b'c' as i8, b'd' as i8, b'r' as i8, b'e' as i8, b'g' as i8, b'a' as i8, b'f' as i8, b'v' as i8, b'z' as i8, b'b' as i8],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [b'e' as i8, b'n' as i8, b'i' as i8, b's' as i8, b'h' as i8, b'l' as i8, b'f' as i8, b'y' as i8, b'-' as i8, b'a' as i8, b'w' as i8, b'\'' as i8, b'g' as i8, b'r' as i8, b'o' as i8, b't' as i8],
    [b'e' as i8, b'l' as i8, b'i' as i8, b'y' as i8, b'd' as i8, b'o' as i8, b'a' as i8, b'f' as i8, b'u' as i8, b't' as i8, b's' as i8, b'k' as i8, b'w' as i8, b'v' as i8, b'm' as i8, b'p' as i8],
    [b'e' as i8, b'a' as i8, b'o' as i8, b'i' as i8, b'u' as i8, b'p' as i8, b'y' as i8, b's' as i8, b'b' as i8, b'm' as i8, b'f' as i8, b'\'' as i8, b'n' as i8, b'-' as i8, b'l' as i8, b't' as i8],
    [b'd' as i8, b'g' as i8, b'e' as i8, b't' as i8, b'o' as i8, b'c' as i8, b's' as i8, b'i' as i8, b'a' as i8, b'n' as i8, b'y' as i8, b'l' as i8, b'k' as i8, b'\'' as i8, b'f' as i8, b'v' as i8],
    [b'u' as i8, b'n' as i8, b'r' as i8, b'f' as i8, b'm' as i8, b't' as i8, b'w' as i8, b'o' as i8, b's' as i8, b'l' as i8, b'v' as i8, b'd' as i8, b'p' as i8, b'k' as i8, b'i' as i8, b'c' as i8],
    [b'e' as i8, b'r' as i8, b'a' as i8, b'o' as i8, b'l' as i8, b'p' as i8, b'i' as i8, b't' as i8, b'u' as i8, b's' as i8, b'h' as i8, b'y' as i8, b'b' as i8, b'-' as i8, b'\'' as i8, b'm' as i8],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [b'e' as i8, b'i' as i8, b'o' as i8, b'a' as i8, b's' as i8, b'y' as i8, b't' as i8, b'd' as i8, b'r' as i8, b'n' as i8, b'c' as i8, b'm' as i8, b'l' as i8, b'u' as i8, b'g' as i8, b'f' as i8],
    [b'e' as i8, b't' as i8, b'h' as i8, b'i' as i8, b'o' as i8, b's' as i8, b'a' as i8, b'u' as i8, b'p' as i8, b'c' as i8, b'l' as i8, b'w' as i8, b'm' as i8, b'k' as i8, b'f' as i8, b'y' as i8],
    [b'h' as i8, b'o' as i8, b'e' as i8, b'i' as i8, b'a' as i8, b't' as i8, b'r' as i8, b'u' as i8, b'y' as i8, b'l' as i8, b's' as i8, b'w' as i8, b'c' as i8, b'f' as i8, b'\'' as i8, b'-' as i8],
    [b'r' as i8, b't' as i8, b'l' as i8, b's' as i8, b'n' as i8, b'g' as i8, b'c' as i8, b'p' as i8, b'e' as i8, b'i' as i8, b'a' as i8, b'd' as i8, b'm' as i8, b'b' as i8, b'f' as i8, b'o' as i8],
    [b'e' as i8, b'i' as i8, b'a' as i8, b'o' as i8, b'y' as i8, b'u' as i8, b'r' as i8, 0, 0, 0, 0, 0, 0, 0, 0, 0],
    [b'a' as i8, b'i' as i8, b'h' as i8, b'e' as i8, b'o' as i8, b'n' as i8, b'r' as i8, b's' as i8, b'l' as i8, b'd' as i8, b'k' as i8, b'-' as i8, b'f' as i8, b'\'' as i8, b'c' as i8, b'b' as i8],
    [b'p' as i8, b't' as i8, b'c' as i8, b'a' as i8, b'i' as i8, b'e' as i8, b'h' as i8, b'q' as i8, b'u' as i8, b'f' as i8, b'-' as i8, b'y' as i8, b'o' as i8, 0, 0, 0],
    [b'o' as i8, b'e' as i8, b's' as i8, b't' as i8, b'i' as i8, b'd' as i8, b'\'' as i8, b'l' as i8, b'b' as i8, b'-' as i8, b'm' as i8, b'a' as i8, b'r' as i8, b'n' as i8, b'p' as i8, b'w' as i8],
];

struct Pack {
    word: u32,
    output_byte_count: usize,
    encoded_character_count: usize,
    bit_offsets: [u8; 8],
    bit_masks: [i32; 8],
    header_mask: u8,
    header: u8,
}

const PACKS: [Pack; PACK_COUNT] = [
    Pack {
        word: 0x80000000,
        output_byte_count: 1,
        encoded_character_count: 2,
        bit_offsets: [26, 24, 24, 24, 24, 24, 24, 24],
        bit_masks: [15, 3, 0, 0, 0, 0, 0, 0],
        header_mask: 0xc0,
        header: 0x80,
    },
    Pack {
        word: 0xc0000000,
        output_byte_count: 2,
        encoded_character_count: 4,
        bit_offsets: [25, 22, 19, 16, 16, 16, 16, 16],
        bit_masks: [15, 7, 7, 7, 0, 0, 0, 0],
        header_mask: 0xe0,
        header: 0xc0,
    },
    Pack {
        word: 0xe0000000,
        output_byte_count: 4,
        encoded_character_count: 8,
        bit_offsets: [23, 19, 15, 11, 8, 5, 2, 0],
        bit_masks: [31, 15, 15, 15, 7, 7, 7, 3],
        header_mask: 0xf0,
        header: 0xe0,
    },
];

#[derive(Clone, Copy)]
struct PackedWord {
    bits: u32,
}

impl PackedWord {
    fn new() -> Self {
        Self { bits: 0 }
    }

    fn from_bits(bits: u32) -> Self {
        Self { bits }
    }

    fn to_bytes(self) -> [u8; 4] {
        self.bits.to_be_bytes()
    }

    fn set_byte(&mut self, index: usize, value: u8) {
        let mut bytes = self.bits.to_be_bytes();
        bytes[index] = value;
        self.bits = u32::from_be_bytes(bytes);
    }
}

fn determine_pack_from_header(header_byte: u8) -> Option<usize> {
    for pack_index in (0..PACK_COUNT).rev() {
        if (header_byte & PACKS[pack_index].header_mask) == PACKS[pack_index].header {
            return Some(pack_index);
        }
    }
    None
}

fn indices_fit_in_pack(indices: &[i8], pack_index: usize) -> bool {
    let pack = &PACKS[pack_index];
    for slot in 0..pack.encoded_character_count {
        let index = indices[slot];
        let mask = pack.bit_masks[slot];
        if index < 0 || (index as i32 & mask) != index as i32 {
            return false;
        }
    }
    true
}

fn find_best_pack(indices: &[i8], chain_length: usize) -> Option<usize> {
    for pack_index in (0..PACK_COUNT).rev() {
        if chain_length >= PACKS[pack_index].encoded_character_count
            && indices_fit_in_pack(indices, pack_index)
        {
            return Some(pack_index);
        }
    }
    None
}

/// Compresses a byte slice.
///
/// Output will never exceed input length for ASCII text.
pub fn compress(input: &[u8]) -> Vec<u8> {
    if input.is_empty() {
        return Vec::new();
    }

    let mut output = Vec::with_capacity(input.len());
    let mut indices: [i8; MAX_SUCCESSOR_CHAIN_LENGTH + 1] = [0; MAX_SUCCESSOR_CHAIN_LENGTH + 1];
    let mut position = 0;

    while position < input.len() {
        let current_byte = input[position];

        if current_byte > 127 || current_byte == 0x00 {
            output.push(0x00); // sentinel for non-ASCII and NUL bytes
            output.push(current_byte);
            position += 1;
            continue;
        }

        let first_character_id = CHARACTER_ID_BY_BYTE[current_byte as usize];
        if first_character_id < 0 {
            output.push(current_byte);
            position += 1;
            continue;
        }

        indices[0] = first_character_id;
        let mut chain_length = 1;
        let mut previous_character_id = first_character_id;

        while chain_length <= MAX_SUCCESSOR_CHAIN_LENGTH && (position + chain_length) < input.len()
        {
            let next_byte = input[position + chain_length];

            if next_byte > 127 {
                break;
            }

            let next_character_id = CHARACTER_ID_BY_BYTE[next_byte as usize];
            if next_character_id < 0 {
                break;
            }

            let successor_index = SUCCESSOR_INDEX_BY_CHARACTER_IDS[previous_character_id as usize]
                [next_character_id as usize];
            if successor_index < 0 {
                break;
            }

            indices[chain_length] = successor_index;
            previous_character_id = next_character_id;
            chain_length += 1;
        }

        if let Some(pack_index) = find_best_pack(&indices, chain_length) {
            let pack = &PACKS[pack_index];
            let mut packed_word = PackedWord::from_bits(pack.word);

            for slot in 0..pack.encoded_character_count {
                packed_word.bits |= (indices[slot] as u32) << pack.bit_offsets[slot];
            }

            let bytes = packed_word.to_bytes();
            for byte_index in 0..pack.output_byte_count {
                output.push(bytes[byte_index]);
            }

            position += pack.encoded_character_count;
        } else {
            output.push(current_byte);
            position += 1;
        }
    }

    output
}

/// Decompresses shoco-compressed data.
///
/// Returns `None` if the input is malformed.
pub fn decompress(input: &[u8]) -> Option<Vec<u8>> {
    if input.is_empty() {
        return Some(Vec::new());
    }

    let mut output = Vec::with_capacity(input.len() * 2);
    let mut position = 0;

    while position < input.len() {
        let current_byte = input[position];

        if (current_byte & 0x80) == 0 {
            if current_byte == 0x00 {
                // sentinel for non-ASCII: skip it and copy next byte literally
                position += 1;
                if position >= input.len() {
                    return None;
                }
                output.push(input[position]);
                position += 1;
                continue;
            }
            output.push(current_byte);
            position += 1;
            continue;
        }

        let pack_index = determine_pack_from_header(current_byte)?;
        let pack = &PACKS[pack_index];

        if position + pack.output_byte_count > input.len() {
            return None;
        }

        let mut packed_word = PackedWord::new();
        for byte_index in 0..pack.output_byte_count {
            packed_word.set_byte(byte_index, input[position + byte_index]);
        }

        let first_character_id =
            ((packed_word.bits >> pack.bit_offsets[0]) & pack.bit_masks[0] as u32) as usize;
        if first_character_id >= CHARACTER_BY_ID.len() {
            return None;
        }
        let first_character = CHARACTER_BY_ID[first_character_id];
        output.push(first_character);

        let mut last_character = first_character;

        for slot in 1..pack.encoded_character_count {
            if pack.bit_masks[slot] == 0 {
                break;
            }

            let successor_index = ((packed_word.bits >> pack.bit_offsets[slot])
                & pack.bit_masks[slot] as u32) as usize;

            let char_offset = last_character.wrapping_sub(MIN_CHR) as usize;
            if char_offset >= SUCCESSOR_CHARACTER_BY_CHAR_AND_INDEX.len() {
                return None;
            }

            let successor_char =
                SUCCESSOR_CHARACTER_BY_CHAR_AND_INDEX[char_offset][successor_index];
            if successor_char == 0 {
                return None;
            }

            output.push(successor_char as u8);
            last_character = successor_char as u8;
        }

        position += pack.output_byte_count;
    }

    Some(output)
}

pub fn compress_str(input: &str) -> Vec<u8> {
    compress(input.as_bytes())
}

pub fn decompress_str(input: &[u8]) -> Option<String> {
    decompress(input).and_then(|bytes| String::from_utf8(bytes).ok())
}

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

    #[test]
    fn empty_input_produces_empty_output() {
        assert_eq!(compress(b""), vec![]);
        assert_eq!(decompress(&[]), Some(vec![]));
    }

    #[test]
    fn single_character_roundtrips() {
        let input = b"a";
        let decompressed = decompress(&compress(input)).unwrap();
        assert_eq!(decompressed, input.to_vec());
    }

    #[test]
    fn hello_world_roundtrips_and_compresses() {
        let input = b"hello world";
        let compressed = compress(input);
        let decompressed = decompress(&compressed).unwrap();
        assert_eq!(decompressed, input.to_vec());
        assert!(compressed.len() <= input.len());
    }

    #[test]
    fn common_english_words_roundtrip() {
        let words = ["the", "and", "that", "have", "for", "not", "with", "you"];
        for word in words {
            let input = word.as_bytes();
            let decompressed = decompress(&compress(input)).unwrap();
            assert_eq!(decompressed, input.to_vec(), "Failed for: {}", word);
        }
    }

    #[test]
    fn longer_text_roundtrips() {
        let input = b"This is a longer piece of text that should compress well.";
        let decompressed = decompress(&compress(input)).unwrap();
        assert_eq!(decompressed, input.to_vec());
    }

    #[test]
    fn control_characters_pass_through() {
        let input = b"\x00\x01\x02abc";
        let decompressed = decompress(&compress(input)).unwrap();
        assert_eq!(decompressed, input.to_vec());
    }

    #[test]
    fn string_api_roundtrips() {
        let input = "Hello, World!";
        let decompressed = decompress_str(&compress_str(input)).unwrap();
        assert_eq!(decompressed, input);
    }

    #[test]
    fn output_never_exceeds_input_for_ascii() {
        let input =
            b"This is a test of the shoco compression algorithm. It should work well for English text.";
        let compressed = compress(input);
        assert!(compressed.len() <= input.len());
    }

    #[test]
    fn incompressible_input_passes_through() {
        let input = b"ZQXJK123!@#$%";
        let compressed = compress(input);
        let decompressed = decompress(&compressed).unwrap();
        assert_eq!(decompressed, input.to_vec());
        assert!(compressed.len() <= input.len());
    }

    #[test]
    fn nul_bytes_roundtrip() {
        // NUL at start
        let input = b"\x00hello";
        assert_eq!(decompress(&compress(input)).unwrap(), input.to_vec());

        // NUL in middle
        let input = b"hel\x00lo";
        assert_eq!(decompress(&compress(input)).unwrap(), input.to_vec());

        // NUL at end
        let input = b"hello\x00";
        assert_eq!(decompress(&compress(input)).unwrap(), input.to_vec());

        // Multiple NULs
        let input = b"\x00\x00\x00";
        assert_eq!(decompress(&compress(input)).unwrap(), input.to_vec());

        // NUL with high bytes
        let input = b"\x00\xff\x00\x80";
        assert_eq!(decompress(&compress(input)).unwrap(), input.to_vec());
    }
}