deflate/
huffman_table.rs

Help
1use crate::bit_reverse::reverse_bits;
2use crate::lzvalue::StoredLength;
3use std::fmt;
4
5/// The number of length codes in the Huffman table
6pub const NUM_LENGTH_CODES: usize = 29;
7
8/// The number of distance codes in the distance Huffman table
9// NOTE: two mode codes are actually used when constructing codes
10pub const NUM_DISTANCE_CODES: usize = 30;
11
12/// Combined number of literal and length codes
13// NOTE: two mode codes are actually used when constructing codes
14pub const NUM_LITERALS_AND_LENGTHS: usize = 286;
15
16/// The maximum length of a Huffman code
17pub const MAX_CODE_LENGTH: usize = 15;
18
19/// The minimum and maximum lengths for a match according to the DEFLATE specification
20pub const MIN_MATCH: u16 = 3;
21pub const MAX_MATCH: u16 = 258;
22
23#[cfg(test)]
24pub const MIN_DISTANCE: u16 = 1;
25pub const MAX_DISTANCE: u16 = 32768;
26
27/// The position in the literal/length table of the end of block symbol
28pub const END_OF_BLOCK_POSITION: usize = 256;
29
30/// Bit lengths for literal and length codes in the fixed Huffman table
31/// The Huffman codes are generated from this and the distance bit length table
32pub static FIXED_CODE_LENGTHS: [u8; NUM_LITERALS_AND_LENGTHS + 2] = [
33    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,
34    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,
35    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,
36    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,
37    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,
38    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,
39    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,
40    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,
41    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,
42];
43
44/// The number of extra bits for the length codes
45const LENGTH_EXTRA_BITS_LENGTH: [u8; NUM_LENGTH_CODES] = [
46    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,
47];
48
49/// Table used to get a code from a length value (see get_distance_code_and_extra_bits)
50const LENGTH_CODE: [u8; 256] = [
51    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,
52    14, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18,
53    18, 18, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
54    20, 20, 20, 20, 20, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 22, 22, 22,
55    22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
56    23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
57    24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
58    25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 26, 26, 26,
59    26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
60    26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
61    27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28,
62];
63
64/// Base values to calculate the value of the bits in length codes
65const BASE_LENGTH: [u8; NUM_LENGTH_CODES] = [
66    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,
67    160, 192, 224, 255,
68]; // 258 - MIN_MATCh
69
70/// What number in the literal/length table the lengths start at
71pub const LENGTH_BITS_START: u16 = 257;
72
73/// Lengths for the distance codes in the pre-defined/fixed Huffman table
74/// (All distance codes are 5 bits long)
75pub const FIXED_CODE_LENGTHS_DISTANCE: [u8; NUM_DISTANCE_CODES + 2] = [5; NUM_DISTANCE_CODES + 2];
76
77const DISTANCE_CODES: [u8; 512] = [
78    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,
79    10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11,
80    11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
81    12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13,
82    13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
83    14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
84    14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
85    14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15,
86    15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
87    15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
88    15, 15, 15, 15, 15, 15, 15, 15, 0, 0, 16, 17, 18, 18, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21,
89    22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24,
90    24, 24, 24, 24, 24, 24, 24, 24, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
91    26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
92    26, 26, 26, 26, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
93    27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28,
94    28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
95    28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
96    28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
97    29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
98    29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
99];
100
101/// Number of extra bits following the distance codes
102#[cfg(test)]
103const DISTANCE_EXTRA_BITS: [u8; NUM_DISTANCE_CODES] = [
104    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,
105    13,
106];
107
108const DISTANCE_BASE: [u16; NUM_DISTANCE_CODES] = [
109    0, 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 512, 768, 1024, 1536,
110    2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576,
111];
112
113pub const fn num_extra_bits_for_length_code(code: u8) -> u8 {
114    LENGTH_EXTRA_BITS_LENGTH[code as usize]
115}
116
117/// Get the number of extra bits used for a distance code.
118/// (Code numbers above `NUM_DISTANCE_CODES` will give some garbage
119/// value.)
120pub fn num_extra_bits_for_distance_code(code: u8) -> u8 {
121    // This can be easily calculated without a lookup.
122    //
123    let mut c = code >> 1;
124    c -= (c != 0) as u8;
125    c
126}
127
128/// A struct representing the data needed to generate the bit codes for
129/// a given value and Huffman table.
130#[derive(Copy, Clone)]
131struct ExtraBits {
132    /// The position of the length in the Huffman table.
133    pub code_number: u16,
134    /// Number of extra bits following the code.
135    pub num_bits: u8,
136    /// The value of the extra bits, which together with the length/distance code
137    /// allow us to calculate the exact length/distance.
138    pub value: u16,
139}
140
141/// Get the length code that corresponds to the length value
142/// Panics if length is out of range.
143pub fn get_length_code(length: u16) -> usize {
144    // Going via an u8 here helps the compiler evade bounds checking.
145    usize::from(LENGTH_CODE[(length.wrapping_sub(MIN_MATCH)) as u8 as usize])
146        + LENGTH_BITS_START as usize
147}
148
149/// Get the code for the Huffman table and the extra bits for the requested length.
150fn get_length_code_and_extra_bits(length: StoredLength) -> ExtraBits {
151    // Length values are stored as unsigned bytes, where the actual length is the value - 3
152    // The `StoredLength` struct takes care of this conversion for us.
153    let n = LENGTH_CODE[length.stored_length() as usize];
154
155    // We can then get the base length from the base length table,
156    // which we use to calculate the value of the extra bits.
157    let base = BASE_LENGTH[n as usize];
158    let num_bits = num_extra_bits_for_length_code(n);
159    ExtraBits {
160        code_number: n as u16 + LENGTH_BITS_START,
161        num_bits,
162        value: (length.stored_length() - base) as u16,
163    }
164}
165
166/// Get the spot in the Huffman table for distances `distance` corresponds to
167/// Returns 255 if the distance is invalid.
168/// Avoiding option here for simplicity and performance) as this being called with an invalid
169/// value would be a bug.
170pub fn get_distance_code(distance: u16) -> u8 {
171    let distance = distance as usize;
172
173    match distance {
174        // Since the array starts at 0, we need to subtract 1 to get the correct code number.
175        1..=256 => DISTANCE_CODES[distance - 1],
176        // Due to the distrubution of the distance codes above 256, we can get away with only
177        // using the top bits to determine the code, rather than having a 32k long table of
178        // distance codes.
179        257..=32768 => DISTANCE_CODES[256 + ((distance - 1) >> 7)],
180        _ => 0,
181    }
182}
183
184fn get_distance_code_and_extra_bits(distance: u16) -> ExtraBits {
185    let distance_code = get_distance_code(distance);
186    let extra = num_extra_bits_for_distance_code(distance_code);
187    // FIXME: We should add 1 to the values in distance_base to avoid having to add one here
188    let base = DISTANCE_BASE[distance_code as usize] + 1;
189    ExtraBits {
190        code_number: distance_code.into(),
191        num_bits: extra,
192        value: distance - base,
193    }
194}
195
196#[derive(Copy, Clone, Default)]
197pub struct HuffmanCode {
198    pub code: u16,
199    pub length: u8,
200}
201
202impl fmt::Debug for HuffmanCode {
203    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
204        write!(
205            f,
206            "HuffmanCode {{ code: {:b}, length: {}}}",
207            self.code, self.length
208        )
209    }
210}
211
212impl HuffmanCode {
213    #[inline]
214    /// Create a Huffman code value from a code and length.
215    const fn new(code: u16, length: u8) -> HuffmanCode {
216        HuffmanCode { code, length }
217    }
218}
219
220#[cfg(test)]
221pub struct LengthAndDistanceBits {
222    pub length_code: HuffmanCode,
223    pub length_extra_bits: HuffmanCode,
224    pub distance_code: HuffmanCode,
225    pub distance_extra_bits: HuffmanCode,
226}
227
228/// Counts the number of values of each length.
229/// Returns a tuple containing the longest length value in the table, it's position,
230/// and fills in lengths in the `len_counts` slice.
231/// Returns an error if `table` is empty, or if any of the lengths exceed 15.
232fn build_length_count_table(table: &[u8], len_counts: &mut [u16; 16]) -> (usize, usize) {
233    // TODO: Validate the length table properly in debug mode.
234    let max_length = (*table.iter().max().expect("BUG! Empty lengths!")).into();
235
236    assert!(max_length <= MAX_CODE_LENGTH);
237
238    let mut max_length_pos = 0;
239
240    for (n, &length) in table.iter().enumerate() {
241        // TODO: Make sure we don't have more of one length than we can make
242        // codes for
243        if length > 0 {
244            len_counts[usize::from(length)] += 1;
245            max_length_pos = n;
246        }
247    }
248    (max_length, max_length_pos)
249}
250
251/// Generates a vector of Huffman codes given a table of bit lengths
252/// Returns an error if any of the lengths are > 15
253pub fn create_codes_in_place(code_table: &mut [u16], length_table: &[u8]) {
254    let mut len_counts = [0; 16];
255    let (max_length, max_length_pos) = build_length_count_table(length_table, &mut len_counts);
256    let lengths = len_counts;
257
258    let mut code = 0u16;
259    let mut next_code = Vec::with_capacity(length_table.len());
260    next_code.push(code);
261
262    for bits in 1..=max_length {
263        code = (code + lengths[bits - 1]) << 1;
264        next_code.push(code);
265    }
266
267    for n in 0..=max_length_pos {
268        let length = usize::from(length_table[n]);
269        if length != 0 {
270            // The algorithm generates the code in the reverse bit order, so we need to reverse them
271            // to get the correct codes.
272            code_table[n] = reverse_bits(next_code[length], length as u8);
273            // We use wrapping here as we would otherwise overflow on the last code
274            // This should be okay as we exit the loop after this so the value is ignored
275            next_code[length] = next_code[length].wrapping_add(1);
276        }
277    }
278}
279
280/// A structure containing the tables of Huffman codes for lengths, literals and distances
281pub struct HuffmanTable {
282    // Literal, end of block and length codes
283    codes: [u16; 288],
284    code_lengths: [u8; 288],
285    // Distance codes
286    distance_codes: [u16; 32],
287    distance_code_lengths: [u8; 32],
288}
289
290impl HuffmanTable {
291    pub const fn empty() -> HuffmanTable {
292        HuffmanTable {
293            codes: [0; 288],
294            code_lengths: [0; 288],
295            distance_codes: [0; 32],
296            distance_code_lengths: [0; 32],
297        }
298    }
299
300    #[cfg(test)]
301    pub fn from_length_tables(
302        literals_and_lengths: &[u8; 288],
303        distances: &[u8; 32],
304    ) -> HuffmanTable {
305        let mut table = HuffmanTable {
306            codes: [0; 288],
307            code_lengths: *literals_and_lengths,
308            distance_codes: [0; 32],
309            distance_code_lengths: *distances,
310        };
311
312        table.update_from_lengths();
313        table
314    }
315
316    /// Get references to the lengths of the current Huffman codes.
317    #[inline]
318    pub const fn get_lengths(&self) -> (&[u8; 288], &[u8; 32]) {
319        (&self.code_lengths, &self.distance_code_lengths)
320    }
321
322    /// Get mutable references to the lengths of the current Huffman codes.
323    ///
324    /// Used for updating the lengths in place.
325    #[inline]
326    pub fn get_lengths_mut(&mut self) -> (&mut [u8; 288], &mut [u8; 32]) {
327        (&mut self.code_lengths, &mut self.distance_code_lengths)
328    }
329
330    /// Update the Huffman codes using the existing length values in the Huffman table.
331    pub fn update_from_lengths(&mut self) {
332        create_codes_in_place(self.codes.as_mut(), &self.code_lengths[..]);
333        create_codes_in_place(
334            self.distance_codes.as_mut(),
335            &self.distance_code_lengths[..],
336        );
337    }
338
339    pub fn set_to_fixed(&mut self) {
340        self.code_lengths = FIXED_CODE_LENGTHS;
341        self.distance_code_lengths = FIXED_CODE_LENGTHS_DISTANCE;
342        self.update_from_lengths();
343    }
344
345    /// Create a `HuffmanTable` using the fixed tables specified in the DEFLATE format specification.
346    #[cfg(test)]
347    pub fn fixed_table() -> HuffmanTable {
348        // This should be safe to unwrap, if it were to panic the code is wrong,
349        // tests should catch it.
350        HuffmanTable::from_length_tables(&FIXED_CODE_LENGTHS, &FIXED_CODE_LENGTHS_DISTANCE)
351    }
352
353    #[inline]
354    const fn get_ll_huff(&self, value: usize) -> HuffmanCode {
355        HuffmanCode::new(self.codes[value], self.code_lengths[value])
356    }
357
358    /// Get the Huffman code from the corresponding literal value
359    #[inline]
360    pub fn get_literal(&self, value: u8) -> HuffmanCode {
361        let index = usize::from(value);
362        HuffmanCode::new(self.codes[index], self.code_lengths[index])
363    }
364
365    /// Get the Huffman code for the end of block value
366    #[inline]
367    pub const fn get_end_of_block(&self) -> HuffmanCode {
368        self.get_ll_huff(END_OF_BLOCK_POSITION)
369    }
370
371    /// Get the Huffman code and extra bits for the specified length
372    #[inline]
373    pub fn get_length_huffman(&self, length: StoredLength) -> (HuffmanCode, HuffmanCode) {
374        let length_data = get_length_code_and_extra_bits(length);
375
376        let length_huffman_code = self.get_ll_huff(length_data.code_number as usize);
377
378        (
379            length_huffman_code,
380            HuffmanCode {
381                code: length_data.value,
382                length: length_data.num_bits,
383            },
384        )
385    }
386
387    /// Get the Huffman code and extra bits for the specified distance
388    ///
389    /// Returns None if distance is 0 or above 32768
390    #[inline]
391    pub fn get_distance_huffman(&self, distance: u16) -> (HuffmanCode, HuffmanCode) {
392        //debug_assert!(distance >= MIN_DISTANCE && distance <= MAX_DISTANCE);
393
394        let distance_data = get_distance_code_and_extra_bits(distance);
395
396        let distance_huffman_code = self.distance_codes[distance_data.code_number as usize];
397        let distance_huffman_length =
398            self.distance_code_lengths[distance_data.code_number as usize];
399
400        (
401            HuffmanCode {
402                code: distance_huffman_code,
403                length: distance_huffman_length,
404            },
405            HuffmanCode {
406                code: distance_data.value,
407                length: distance_data.num_bits,
408            },
409        )
410    }
411
412    #[cfg(test)]
413    pub fn get_length_distance_code(&self, length: u16, distance: u16) -> LengthAndDistanceBits {
414        assert!(length >= MIN_MATCH && length < MAX_DISTANCE);
415        let l_codes = self.get_length_huffman(StoredLength::from_actual_length(length));
416        let d_codes = self.get_distance_huffman(distance);
417        LengthAndDistanceBits {
418            length_code: l_codes.0,
419            length_extra_bits: l_codes.1,
420            distance_code: d_codes.0,
421            distance_extra_bits: d_codes.1,
422        }
423    }
424}
425
426#[cfg(test)]
427mod test {
428    use super::*;
429    use super::{
430        build_length_count_table, get_distance_code_and_extra_bits, get_length_code_and_extra_bits,
431    };
432
433    use crate::lzvalue::StoredLength;
434
435    fn l(length: u16) -> StoredLength {
436        StoredLength::from_actual_length(length)
437    }
438
439    #[test]
440    fn test_get_length_code() {
441        let extra_bits = get_length_code_and_extra_bits(l(4));
442        assert_eq!(extra_bits.code_number, 258);
443        assert_eq!(extra_bits.num_bits, 0);
444        assert_eq!(extra_bits.value, 0);
445
446        let extra_bits = get_length_code_and_extra_bits(l(165));
447        assert_eq!(extra_bits.code_number, 282);
448        assert_eq!(extra_bits.num_bits, 5);
449        assert_eq!(extra_bits.value, 2);
450
451        let extra_bits = get_length_code_and_extra_bits(l(257));
452        assert_eq!(extra_bits.code_number, 284);
453        assert_eq!(extra_bits.num_bits, 5);
454        assert_eq!(extra_bits.value, 30);
455
456        let extra_bits = get_length_code_and_extra_bits(l(258));
457        assert_eq!(extra_bits.code_number, 285);
458        assert_eq!(extra_bits.num_bits, 0);
459    }
460
461    #[test]
462    fn test_distance_code() {
463        assert_eq!(get_distance_code(1), 0);
464        // Using 0 for None at the moment
465        assert_eq!(get_distance_code(0), 0);
466        assert_eq!(get_distance_code(50000), 0);
467        assert_eq!(get_distance_code(6146), 25);
468        assert_eq!(get_distance_code(256), 15);
469        assert_eq!(get_distance_code(4733), 24);
470        assert_eq!(get_distance_code(257), 16);
471    }
472
473    #[test]
474    fn test_distance_extra_bits() {
475        let extra = get_distance_code_and_extra_bits(527);
476        assert_eq!(extra.value, 0b1110);
477        assert_eq!(extra.code_number, 18);
478        assert_eq!(extra.num_bits, 8);
479        let extra = get_distance_code_and_extra_bits(256);
480        assert_eq!(extra.code_number, 15);
481        assert_eq!(extra.num_bits, 6);
482        let extra = get_distance_code_and_extra_bits(4733);
483        assert_eq!(extra.code_number, 24);
484        assert_eq!(extra.num_bits, 11);
485    }
486
487    #[test]
488    fn test_length_table_fixed() {
489        let _ = build_length_count_table(&FIXED_CODE_LENGTHS, &mut [0; 16]);
490    }
491
492    #[test]
493    #[should_panic]
494    fn test_length_table_max_length() {
495        let table = [16u8; 288];
496        build_length_count_table(&table, &mut [0; 16]);
497    }
498
499    #[test]
500    #[should_panic]
501    fn test_empty_table() {
502        let table = [];
503        build_length_count_table(&table, &mut [0; 16]);
504    }
505
506    #[test]
507    fn make_table_fixed() {
508        let table = HuffmanTable::fixed_table();
509        assert_eq!(table.codes[0], 0b00001100);
510        assert_eq!(table.codes[143], 0b11111101);
511        assert_eq!(table.codes[144], 0b000010011);
512        assert_eq!(table.codes[255], 0b111111111);
513        assert_eq!(table.codes[256], 0b0000000);
514        assert_eq!(table.codes[279], 0b1110100);
515        assert_eq!(table.codes[280], 0b00000011);
516        assert_eq!(table.codes[287], 0b11100011);
517
518        assert_eq!(table.distance_codes[0], 0);
519        assert_eq!(table.distance_codes[5], 20);
520
521        let ld = table.get_length_distance_code(4, 5);
522
523        assert_eq!(ld.length_code.code, 0b00100000);
524        assert_eq!(ld.distance_code.code, 0b00100);
525        assert_eq!(ld.distance_extra_bits.length, 1);
526        assert_eq!(ld.distance_extra_bits.code, 0);
527    }
528
529    #[test]
530    fn extra_bits_distance() {
531        use std::mem::size_of;
532        for i in 0..NUM_DISTANCE_CODES {
533            assert_eq!(
534                num_extra_bits_for_distance_code(i as u8),
535                DISTANCE_EXTRA_BITS[i]
536            );
537        }
538        println!("Size of huffmanCode struct: {}", size_of::<HuffmanCode>());
539    }
540}
deflate/huffman_table.rs

deflate/
huffman_table.rs
