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