541 lines
21 KiB
Rust
541 lines
21 KiB
Rust
use crate::bit_reverse::reverse_bits;
|
|
use crate::lzvalue::StoredLength;
|
|
use std::fmt;
|
|
|
|
/// The number of length codes in the Huffman table
|
|
pub const NUM_LENGTH_CODES: usize = 29;
|
|
|
|
/// The number of distance codes in the distance Huffman table
|
|
// NOTE: two mode codes are actually used when constructing codes
|
|
pub const NUM_DISTANCE_CODES: usize = 30;
|
|
|
|
/// Combined number of literal and length codes
|
|
// NOTE: two mode codes are actually used when constructing codes
|
|
pub const NUM_LITERALS_AND_LENGTHS: usize = 286;
|
|
|
|
/// The maximum length of a Huffman code
|
|
pub const MAX_CODE_LENGTH: usize = 15;
|
|
|
|
/// The minimum and maximum lengths for a match according to the DEFLATE specification
|
|
pub const MIN_MATCH: u16 = 3;
|
|
pub const MAX_MATCH: u16 = 258;
|
|
|
|
#[cfg(test)]
|
|
pub const MIN_DISTANCE: u16 = 1;
|
|
pub const MAX_DISTANCE: u16 = 32768;
|
|
|
|
/// The position in the literal/length table of the end of block symbol
|
|
pub const END_OF_BLOCK_POSITION: usize = 256;
|
|
|
|
/// Bit lengths for literal and length codes in the fixed Huffman table
|
|
/// The Huffman codes are generated from this and the distance bit length table
|
|
pub static FIXED_CODE_LENGTHS: [u8; NUM_LITERALS_AND_LENGTHS + 2] = [
|
|
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
|
|
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
|
|
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
|
|
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
|
|
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
|
|
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
|
|
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
|
|
9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
|
|
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8,
|
|
];
|
|
|
|
/// The number of extra bits for the length codes
|
|
const LENGTH_EXTRA_BITS_LENGTH: [u8; NUM_LENGTH_CODES] = [
|
|
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,
|
|
];
|
|
|
|
/// Table used to get a code from a length value (see get_distance_code_and_extra_bits)
|
|
const LENGTH_CODE: [u8; 256] = [
|
|
0, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 12, 12, 13, 13, 13, 13, 14, 14, 14,
|
|
14, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18,
|
|
18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
|
|
20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 22, 22, 22,
|
|
22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
|
|
23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
|
|
24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
|
|
25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26,
|
|
26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
|
|
26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
|
|
27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28,
|
|
];
|
|
|
|
/// Base values to calculate the value of the bits in length codes
|
|
const BASE_LENGTH: [u8; NUM_LENGTH_CODES] = [
|
|
0, 1, 2, 3, 4, 5, 6, 7, 8, 10, 12, 14, 16, 20, 24, 28, 32, 40, 48, 56, 64, 80, 96, 112, 128,
|
|
160, 192, 224, 255,
|
|
]; // 258 - MIN_MATCh
|
|
|
|
/// What number in the literal/length table the lengths start at
|
|
pub const LENGTH_BITS_START: u16 = 257;
|
|
|
|
/// Lengths for the distance codes in the pre-defined/fixed Huffman table
|
|
/// (All distance codes are 5 bits long)
|
|
pub const FIXED_CODE_LENGTHS_DISTANCE: [u8; NUM_DISTANCE_CODES + 2] = [5; NUM_DISTANCE_CODES + 2];
|
|
|
|
const DISTANCE_CODES: [u8; 512] = [
|
|
0, 1, 2, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9,
|
|
10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11,
|
|
11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
|
|
12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13,
|
|
13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
|
|
14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
|
|
14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
|
|
14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15,
|
|
15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
|
|
15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
|
|
15, 15, 15, 15, 15, 15, 15, 15, 0, 0, 16, 17, 18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21,
|
|
22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24,
|
|
24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
|
|
26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
|
|
26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
|
|
27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28,
|
|
28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
|
|
28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
|
|
28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
|
|
29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
|
|
29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
|
|
];
|
|
|
|
/// Number of extra bits following the distance codes
|
|
#[cfg(test)]
|
|
const DISTANCE_EXTRA_BITS: [u8; NUM_DISTANCE_CODES] = [
|
|
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,
|
|
];
|
|
|
|
const DISTANCE_BASE: [u16; NUM_DISTANCE_CODES] = [
|
|
0, 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 512, 768, 1024, 1536,
|
|
2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576,
|
|
];
|
|
|
|
pub const fn num_extra_bits_for_length_code(code: u8) -> u8 {
|
|
LENGTH_EXTRA_BITS_LENGTH[code as usize]
|
|
}
|
|
|
|
/// Get the number of extra bits used for a distance code.
|
|
/// (Code numbers above `NUM_DISTANCE_CODES` will give some garbage
|
|
/// value.)
|
|
pub fn num_extra_bits_for_distance_code(code: u8) -> u8 {
|
|
// This can be easily calculated without a lookup.
|
|
//
|
|
let mut c = code >> 1;
|
|
c -= (c != 0) as u8;
|
|
c
|
|
}
|
|
|
|
/// A struct representing the data needed to generate the bit codes for
|
|
/// a given value and Huffman table.
|
|
#[derive(Copy, Clone)]
|
|
struct ExtraBits {
|
|
/// The position of the length in the Huffman table.
|
|
pub code_number: u16,
|
|
/// Number of extra bits following the code.
|
|
pub num_bits: u8,
|
|
/// The value of the extra bits, which together with the length/distance code
|
|
/// allow us to calculate the exact length/distance.
|
|
pub value: u16,
|
|
}
|
|
|
|
/// Get the length code that corresponds to the length value
|
|
/// Panics if length is out of range.
|
|
pub fn get_length_code(length: u16) -> usize {
|
|
// Going via an u8 here helps the compiler evade bounds checking.
|
|
usize::from(LENGTH_CODE[(length.wrapping_sub(MIN_MATCH)) as u8 as usize])
|
|
+ LENGTH_BITS_START as usize
|
|
}
|
|
|
|
/// Get the code for the Huffman table and the extra bits for the requested length.
|
|
fn get_length_code_and_extra_bits(length: StoredLength) -> ExtraBits {
|
|
// Length values are stored as unsigned bytes, where the actual length is the value - 3
|
|
// The `StoredLength` struct takes care of this conversion for us.
|
|
let n = LENGTH_CODE[length.stored_length() as usize];
|
|
|
|
// We can then get the base length from the base length table,
|
|
// which we use to calculate the value of the extra bits.
|
|
let base = BASE_LENGTH[n as usize];
|
|
let num_bits = num_extra_bits_for_length_code(n);
|
|
ExtraBits {
|
|
code_number: n as u16 + LENGTH_BITS_START,
|
|
num_bits,
|
|
value: (length.stored_length() - base) as u16,
|
|
}
|
|
}
|
|
|
|
/// Get the spot in the Huffman table for distances `distance` corresponds to
|
|
/// Returns 255 if the distance is invalid.
|
|
/// Avoiding option here for simplicity and performance) as this being called with an invalid
|
|
/// value would be a bug.
|
|
pub fn get_distance_code(distance: u16) -> u8 {
|
|
let distance = distance as usize;
|
|
|
|
match distance {
|
|
// Since the array starts at 0, we need to subtract 1 to get the correct code number.
|
|
1..=256 => DISTANCE_CODES[distance - 1],
|
|
// Due to the distrubution of the distance codes above 256, we can get away with only
|
|
// using the top bits to determine the code, rather than having a 32k long table of
|
|
// distance codes.
|
|
257..=32768 => DISTANCE_CODES[256 + ((distance - 1) >> 7)],
|
|
_ => 0,
|
|
}
|
|
}
|
|
|
|
fn get_distance_code_and_extra_bits(distance: u16) -> ExtraBits {
|
|
let distance_code = get_distance_code(distance);
|
|
let extra = num_extra_bits_for_distance_code(distance_code);
|
|
// FIXME: We should add 1 to the values in distance_base to avoid having to add one here
|
|
let base = DISTANCE_BASE[distance_code as usize] + 1;
|
|
ExtraBits {
|
|
code_number: distance_code.into(),
|
|
num_bits: extra,
|
|
value: distance - base,
|
|
}
|
|
}
|
|
|
|
#[derive(Copy, Clone, Default)]
|
|
pub struct HuffmanCode {
|
|
pub code: u16,
|
|
pub length: u8,
|
|
}
|
|
|
|
impl fmt::Debug for HuffmanCode {
|
|
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
|
|
write!(
|
|
f,
|
|
"HuffmanCode {{ code: {:b}, length: {}}}",
|
|
self.code, self.length
|
|
)
|
|
}
|
|
}
|
|
|
|
impl HuffmanCode {
|
|
#[inline]
|
|
/// Create a Huffman code value from a code and length.
|
|
const fn new(code: u16, length: u8) -> HuffmanCode {
|
|
HuffmanCode { code, length }
|
|
}
|
|
}
|
|
|
|
#[cfg(test)]
|
|
pub struct LengthAndDistanceBits {
|
|
pub length_code: HuffmanCode,
|
|
pub length_extra_bits: HuffmanCode,
|
|
pub distance_code: HuffmanCode,
|
|
pub distance_extra_bits: HuffmanCode,
|
|
}
|
|
|
|
/// Counts the number of values of each length.
|
|
/// Returns a tuple containing the longest length value in the table, it's position,
|
|
/// and fills in lengths in the `len_counts` slice.
|
|
/// Returns an error if `table` is empty, or if any of the lengths exceed 15.
|
|
fn build_length_count_table(table: &[u8], len_counts: &mut [u16; 16]) -> (usize, usize) {
|
|
// TODO: Validate the length table properly in debug mode.
|
|
let max_length = (*table.iter().max().expect("BUG! Empty lengths!")).into();
|
|
|
|
assert!(max_length <= MAX_CODE_LENGTH);
|
|
|
|
let mut max_length_pos = 0;
|
|
|
|
for (n, &length) in table.iter().enumerate() {
|
|
// TODO: Make sure we don't have more of one length than we can make
|
|
// codes for
|
|
if length > 0 {
|
|
len_counts[usize::from(length)] += 1;
|
|
max_length_pos = n;
|
|
}
|
|
}
|
|
(max_length, max_length_pos)
|
|
}
|
|
|
|
/// Generates a vector of Huffman codes given a table of bit lengths
|
|
/// Returns an error if any of the lengths are > 15
|
|
pub fn create_codes_in_place(code_table: &mut [u16], length_table: &[u8]) {
|
|
let mut len_counts = [0; 16];
|
|
let (max_length, max_length_pos) = build_length_count_table(length_table, &mut len_counts);
|
|
let lengths = len_counts;
|
|
|
|
let mut code = 0u16;
|
|
let mut next_code = Vec::with_capacity(length_table.len());
|
|
next_code.push(code);
|
|
|
|
for bits in 1..=max_length {
|
|
code = (code + lengths[bits - 1]) << 1;
|
|
next_code.push(code);
|
|
}
|
|
|
|
for n in 0..=max_length_pos {
|
|
let length = usize::from(length_table[n]);
|
|
if length != 0 {
|
|
// The algorithm generates the code in the reverse bit order, so we need to reverse them
|
|
// to get the correct codes.
|
|
code_table[n] = reverse_bits(next_code[length], length as u8);
|
|
// We use wrapping here as we would otherwise overflow on the last code
|
|
// This should be okay as we exit the loop after this so the value is ignored
|
|
next_code[length] = next_code[length].wrapping_add(1);
|
|
}
|
|
}
|
|
}
|
|
|
|
/// A structure containing the tables of Huffman codes for lengths, literals and distances
|
|
pub struct HuffmanTable {
|
|
// Literal, end of block and length codes
|
|
codes: [u16; 288],
|
|
code_lengths: [u8; 288],
|
|
// Distance codes
|
|
distance_codes: [u16; 32],
|
|
distance_code_lengths: [u8; 32],
|
|
}
|
|
|
|
impl HuffmanTable {
|
|
pub const fn empty() -> HuffmanTable {
|
|
HuffmanTable {
|
|
codes: [0; 288],
|
|
code_lengths: [0; 288],
|
|
distance_codes: [0; 32],
|
|
distance_code_lengths: [0; 32],
|
|
}
|
|
}
|
|
|
|
#[cfg(test)]
|
|
pub fn from_length_tables(
|
|
literals_and_lengths: &[u8; 288],
|
|
distances: &[u8; 32],
|
|
) -> HuffmanTable {
|
|
let mut table = HuffmanTable {
|
|
codes: [0; 288],
|
|
code_lengths: *literals_and_lengths,
|
|
distance_codes: [0; 32],
|
|
distance_code_lengths: *distances,
|
|
};
|
|
|
|
table.update_from_lengths();
|
|
table
|
|
}
|
|
|
|
/// Get references to the lengths of the current Huffman codes.
|
|
#[inline]
|
|
pub const fn get_lengths(&self) -> (&[u8; 288], &[u8; 32]) {
|
|
(&self.code_lengths, &self.distance_code_lengths)
|
|
}
|
|
|
|
/// Get mutable references to the lengths of the current Huffman codes.
|
|
///
|
|
/// Used for updating the lengths in place.
|
|
#[inline]
|
|
pub fn get_lengths_mut(&mut self) -> (&mut [u8; 288], &mut [u8; 32]) {
|
|
(&mut self.code_lengths, &mut self.distance_code_lengths)
|
|
}
|
|
|
|
/// Update the Huffman codes using the existing length values in the Huffman table.
|
|
pub fn update_from_lengths(&mut self) {
|
|
create_codes_in_place(self.codes.as_mut(), &self.code_lengths[..]);
|
|
create_codes_in_place(
|
|
self.distance_codes.as_mut(),
|
|
&self.distance_code_lengths[..],
|
|
);
|
|
}
|
|
|
|
pub fn set_to_fixed(&mut self) {
|
|
self.code_lengths = FIXED_CODE_LENGTHS;
|
|
self.distance_code_lengths = FIXED_CODE_LENGTHS_DISTANCE;
|
|
self.update_from_lengths();
|
|
}
|
|
|
|
/// Create a `HuffmanTable` using the fixed tables specified in the DEFLATE format specification.
|
|
#[cfg(test)]
|
|
pub fn fixed_table() -> HuffmanTable {
|
|
// This should be safe to unwrap, if it were to panic the code is wrong,
|
|
// tests should catch it.
|
|
HuffmanTable::from_length_tables(&FIXED_CODE_LENGTHS, &FIXED_CODE_LENGTHS_DISTANCE)
|
|
}
|
|
|
|
#[inline]
|
|
const fn get_ll_huff(&self, value: usize) -> HuffmanCode {
|
|
HuffmanCode::new(self.codes[value], self.code_lengths[value])
|
|
}
|
|
|
|
/// Get the Huffman code from the corresponding literal value
|
|
#[inline]
|
|
pub fn get_literal(&self, value: u8) -> HuffmanCode {
|
|
let index = usize::from(value);
|
|
HuffmanCode::new(self.codes[index], self.code_lengths[index])
|
|
}
|
|
|
|
/// Get the Huffman code for the end of block value
|
|
#[inline]
|
|
pub const fn get_end_of_block(&self) -> HuffmanCode {
|
|
self.get_ll_huff(END_OF_BLOCK_POSITION)
|
|
}
|
|
|
|
/// Get the Huffman code and extra bits for the specified length
|
|
#[inline]
|
|
pub fn get_length_huffman(&self, length: StoredLength) -> (HuffmanCode, HuffmanCode) {
|
|
let length_data = get_length_code_and_extra_bits(length);
|
|
|
|
let length_huffman_code = self.get_ll_huff(length_data.code_number as usize);
|
|
|
|
(
|
|
length_huffman_code,
|
|
HuffmanCode {
|
|
code: length_data.value,
|
|
length: length_data.num_bits,
|
|
},
|
|
)
|
|
}
|
|
|
|
/// Get the Huffman code and extra bits for the specified distance
|
|
///
|
|
/// Returns None if distance is 0 or above 32768
|
|
#[inline]
|
|
pub fn get_distance_huffman(&self, distance: u16) -> (HuffmanCode, HuffmanCode) {
|
|
//debug_assert!(distance >= MIN_DISTANCE && distance <= MAX_DISTANCE);
|
|
|
|
let distance_data = get_distance_code_and_extra_bits(distance);
|
|
|
|
let distance_huffman_code = self.distance_codes[distance_data.code_number as usize];
|
|
let distance_huffman_length =
|
|
self.distance_code_lengths[distance_data.code_number as usize];
|
|
|
|
(
|
|
HuffmanCode {
|
|
code: distance_huffman_code,
|
|
length: distance_huffman_length,
|
|
},
|
|
HuffmanCode {
|
|
code: distance_data.value,
|
|
length: distance_data.num_bits,
|
|
},
|
|
)
|
|
}
|
|
|
|
#[cfg(test)]
|
|
pub fn get_length_distance_code(&self, length: u16, distance: u16) -> LengthAndDistanceBits {
|
|
assert!(length >= MIN_MATCH && length < MAX_DISTANCE);
|
|
let l_codes = self.get_length_huffman(StoredLength::from_actual_length(length));
|
|
let d_codes = self.get_distance_huffman(distance);
|
|
LengthAndDistanceBits {
|
|
length_code: l_codes.0,
|
|
length_extra_bits: l_codes.1,
|
|
distance_code: d_codes.0,
|
|
distance_extra_bits: d_codes.1,
|
|
}
|
|
}
|
|
}
|
|
|
|
#[cfg(test)]
|
|
mod test {
|
|
use super::*;
|
|
use super::{
|
|
build_length_count_table, get_distance_code_and_extra_bits, get_length_code_and_extra_bits,
|
|
};
|
|
|
|
use crate::lzvalue::StoredLength;
|
|
|
|
fn l(length: u16) -> StoredLength {
|
|
StoredLength::from_actual_length(length)
|
|
}
|
|
|
|
#[test]
|
|
fn test_get_length_code() {
|
|
let extra_bits = get_length_code_and_extra_bits(l(4));
|
|
assert_eq!(extra_bits.code_number, 258);
|
|
assert_eq!(extra_bits.num_bits, 0);
|
|
assert_eq!(extra_bits.value, 0);
|
|
|
|
let extra_bits = get_length_code_and_extra_bits(l(165));
|
|
assert_eq!(extra_bits.code_number, 282);
|
|
assert_eq!(extra_bits.num_bits, 5);
|
|
assert_eq!(extra_bits.value, 2);
|
|
|
|
let extra_bits = get_length_code_and_extra_bits(l(257));
|
|
assert_eq!(extra_bits.code_number, 284);
|
|
assert_eq!(extra_bits.num_bits, 5);
|
|
assert_eq!(extra_bits.value, 30);
|
|
|
|
let extra_bits = get_length_code_and_extra_bits(l(258));
|
|
assert_eq!(extra_bits.code_number, 285);
|
|
assert_eq!(extra_bits.num_bits, 0);
|
|
}
|
|
|
|
#[test]
|
|
fn test_distance_code() {
|
|
assert_eq!(get_distance_code(1), 0);
|
|
// Using 0 for None at the moment
|
|
assert_eq!(get_distance_code(0), 0);
|
|
assert_eq!(get_distance_code(50000), 0);
|
|
assert_eq!(get_distance_code(6146), 25);
|
|
assert_eq!(get_distance_code(256), 15);
|
|
assert_eq!(get_distance_code(4733), 24);
|
|
assert_eq!(get_distance_code(257), 16);
|
|
}
|
|
|
|
#[test]
|
|
fn test_distance_extra_bits() {
|
|
let extra = get_distance_code_and_extra_bits(527);
|
|
assert_eq!(extra.value, 0b1110);
|
|
assert_eq!(extra.code_number, 18);
|
|
assert_eq!(extra.num_bits, 8);
|
|
let extra = get_distance_code_and_extra_bits(256);
|
|
assert_eq!(extra.code_number, 15);
|
|
assert_eq!(extra.num_bits, 6);
|
|
let extra = get_distance_code_and_extra_bits(4733);
|
|
assert_eq!(extra.code_number, 24);
|
|
assert_eq!(extra.num_bits, 11);
|
|
}
|
|
|
|
#[test]
|
|
fn test_length_table_fixed() {
|
|
let _ = build_length_count_table(&FIXED_CODE_LENGTHS, &mut [0; 16]);
|
|
}
|
|
|
|
#[test]
|
|
#[should_panic]
|
|
fn test_length_table_max_length() {
|
|
let table = [16u8; 288];
|
|
build_length_count_table(&table, &mut [0; 16]);
|
|
}
|
|
|
|
#[test]
|
|
#[should_panic]
|
|
fn test_empty_table() {
|
|
let table = [];
|
|
build_length_count_table(&table, &mut [0; 16]);
|
|
}
|
|
|
|
#[test]
|
|
fn make_table_fixed() {
|
|
let table = HuffmanTable::fixed_table();
|
|
assert_eq!(table.codes[0], 0b00001100);
|
|
assert_eq!(table.codes[143], 0b11111101);
|
|
assert_eq!(table.codes[144], 0b000010011);
|
|
assert_eq!(table.codes[255], 0b111111111);
|
|
assert_eq!(table.codes[256], 0b0000000);
|
|
assert_eq!(table.codes[279], 0b1110100);
|
|
assert_eq!(table.codes[280], 0b00000011);
|
|
assert_eq!(table.codes[287], 0b11100011);
|
|
|
|
assert_eq!(table.distance_codes[0], 0);
|
|
assert_eq!(table.distance_codes[5], 20);
|
|
|
|
let ld = table.get_length_distance_code(4, 5);
|
|
|
|
assert_eq!(ld.length_code.code, 0b00100000);
|
|
assert_eq!(ld.distance_code.code, 0b00100);
|
|
assert_eq!(ld.distance_extra_bits.length, 1);
|
|
assert_eq!(ld.distance_extra_bits.code, 0);
|
|
}
|
|
|
|
#[test]
|
|
fn extra_bits_distance() {
|
|
use std::mem::size_of;
|
|
for i in 0..NUM_DISTANCE_CODES {
|
|
assert_eq!(
|
|
num_extra_bits_for_distance_code(i as u8),
|
|
DISTANCE_EXTRA_BITS[i]
|
|
);
|
|
}
|
|
println!("Size of huffmanCode struct: {}", size_of::<HuffmanCode>());
|
|
}
|
|
}
|