pub(crate) const MIN_MATCH: usize = 3;
pub(crate) const MAX_CODE_BITS: usize = 15;
pub(crate) const END_OF_BLOCK: usize = 256;
pub(crate) const LITLEN_SYMBOLS: usize = 286;
pub(crate) const DIST_SYMBOLS: usize = 30;
pub(crate) const CODE_LENGTH_SYMBOLS: usize = 19;
pub(crate) const FIXED_LITLEN_SYMBOLS: usize = 288;
pub(crate) const FIXED_DIST_SYMBOLS: usize = 32;
pub(crate) const LENGTH_BASE: [u16; 29] = [
3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, 67, 83, 99, 115, 131,
163, 195, 227, 258,
];
pub(crate) const LENGTH_EXTRA: [u8; 29] = [
0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0,
];
pub(crate) const DIST_BASE: [u16; 30] = [
1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537,
2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577,
];
pub(crate) const DIST_EXTRA: [u8; 30] = [
0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13,
13,
];
pub(crate) const CODE_LENGTH_ORDER: [usize; CODE_LENGTH_SYMBOLS] = [
16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15,
];
static LENGTH_INDEX: [u8; 256] = build_length_index();
static DIST_INDEX: [u8; 512] = build_dist_index();
const fn build_length_index() -> [u8; 256] {
let mut table = [0; 256];
let mut code = 0;
while code < LENGTH_BASE.len() {
let base = LENGTH_BASE[code] as usize;
let mut offset = 0;
while offset < 1 << LENGTH_EXTRA[code] {
table[base + offset - MIN_MATCH] = code as u8;
offset += 1;
}
code += 1;
}
table
}
const fn build_dist_index() -> [u8; 512] {
let mut table = [0; 512];
let mut code = 0;
while code < DIST_BASE.len() {
let base = DIST_BASE[code] as usize;
let mut offset = 0;
while offset < 1 << DIST_EXTRA[code] {
let distance = base + offset;
if distance <= 256 {
table[distance - 1] = code as u8;
} else {
table[256 + ((distance - 1) >> 7)] = code as u8;
}
offset += 1;
}
code += 1;
}
table
}
pub(crate) fn length_index(length: usize) -> usize {
usize::from(LENGTH_INDEX[length - MIN_MATCH])
}
pub(crate) fn dist_index(distance: usize) -> usize {
let zero_based = distance - 1;
if zero_based < 256 {
usize::from(DIST_INDEX[zero_based])
} else {
usize::from(DIST_INDEX[256 + (zero_based >> 7)])
}
}
pub(crate) const fn fixed_litlen_lengths() -> [u8; FIXED_LITLEN_SYMBOLS] {
let mut lengths = [8; FIXED_LITLEN_SYMBOLS];
let mut symbol = 144;
while symbol < 256 {
lengths[symbol] = 9;
symbol += 1;
}
while symbol < 280 {
lengths[symbol] = 7;
symbol += 1;
}
lengths
}
pub(crate) const FIXED_DIST_LENGTHS: [u8; FIXED_DIST_SYMBOLS] = [5; FIXED_DIST_SYMBOLS];
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn length_index_brackets_every_length() {
for length in MIN_MATCH..=258 {
let index = length_index(length);
let base = usize::from(LENGTH_BASE[index]);
let span = 1 << LENGTH_EXTRA[index];
assert!(base <= length && length < base + span, "length {length}");
}
assert_eq!(length_index(258), 28);
assert_eq!(length_index(257), 27);
}
#[test]
fn dist_index_brackets_every_distance() {
for distance in 1..=32_768 {
let index = dist_index(distance);
let base = usize::from(DIST_BASE[index]);
let span = 1 << DIST_EXTRA[index];
assert!(
base <= distance && distance < base + span,
"distance {distance}"
);
}
}
#[test]
fn fixed_code_has_rfc_shape() {
let lengths = fixed_litlen_lengths();
let kraft: u32 = lengths.iter().map(|&l| 1 << (9 - l)).sum();
assert_eq!(kraft, 1 << 9, "the fixed code is complete");
assert_eq!(lengths[END_OF_BLOCK], 7);
}
}