| use std::fmt; |
| use bit_reverse::reverse_bits; |
| use lzvalue::StoredLength; |
| |
| // 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 minimun and maximum lengths for a match according to the DEFLATE specification |
| pub const MIN_MATCH: u16 = 3; |
| pub const MAX_MATCH: u16 = 258; |
| |
| 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 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: u16::from(n) + LENGTH_BITS_START, |
| num_bits: num_bits, |
| value: (length.stored_length() - base).into(), |
| } |
| |
| } |
| |
| /// 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. |
| fn new(code: u16, length: u8) -> HuffmanCode { |
| HuffmanCode { |
| code: code, |
| length: 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) |
| } |
| |
| /// Generats 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 + 1 { |
| code = (code + lengths[bits - 1]) << 1; |
| next_code.push(code); |
| } |
| |
| for n in 0..max_length_pos + 1 { |
| 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 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 lenghts of the current huffman codes. |
| #[inline] |
| pub fn get_lengths(&self) -> (&[u8; 288], &[u8; 32]) { |
| (&self.code_lengths, &self.distance_code_lengths) |
| } |
| |
| /// Get mutable references to the lenghts 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] |
| 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 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::{get_length_code_and_extra_bits, get_distance_code_and_extra_bits, |
| build_length_count_table}; |
| |
| use 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>()); |
| } |
| |
| } |
