1 | //! Streaming decompression functionality. |
2 | |
3 | use super::*; |
4 | use crate::shared::{update_adler32, HUFFMAN_LENGTH_ORDER}; |
5 | |
6 | use ::core::convert::TryInto; |
7 | use ::core::{cmp, slice}; |
8 | |
9 | use self::output_buffer::OutputBuffer; |
10 | |
11 | pub const TINFL_LZ_DICT_SIZE: usize = 32_768; |
12 | |
13 | /// A struct containing huffman code lengths and the huffman code tree used by the decompressor. |
14 | struct HuffmanTable { |
15 | /// Length of the code at each index. |
16 | pub code_size: [u8; MAX_HUFF_SYMBOLS_0], |
17 | /// Fast lookup table for shorter huffman codes. |
18 | /// |
19 | /// See `HuffmanTable::fast_lookup`. |
20 | pub look_up: [i16; FAST_LOOKUP_SIZE as usize], |
21 | /// Full huffman tree. |
22 | /// |
23 | /// Positive values are edge nodes/symbols, negative values are |
24 | /// parent nodes/references to other nodes. |
25 | pub tree: [i16; MAX_HUFF_TREE_SIZE], |
26 | } |
27 | |
28 | impl HuffmanTable { |
29 | const fn new() -> HuffmanTable { |
30 | HuffmanTable { |
31 | code_size: [0; MAX_HUFF_SYMBOLS_0], |
32 | look_up: [0; FAST_LOOKUP_SIZE as usize], |
33 | tree: [0; MAX_HUFF_TREE_SIZE], |
34 | } |
35 | } |
36 | |
37 | /// Look for a symbol in the fast lookup table. |
38 | /// The symbol is stored in the lower 9 bits, the length in the next 6. |
39 | /// If the returned value is negative, the code wasn't found in the |
40 | /// fast lookup table and the full tree has to be traversed to find the code. |
41 | #[inline ] |
42 | fn fast_lookup(&self, bit_buf: BitBuffer) -> i16 { |
43 | self.look_up[(bit_buf & BitBuffer::from(FAST_LOOKUP_SIZE - 1)) as usize] |
44 | } |
45 | |
46 | /// Get the symbol and the code length from the huffman tree. |
47 | #[inline ] |
48 | fn tree_lookup(&self, fast_symbol: i32, bit_buf: BitBuffer, mut code_len: u32) -> (i32, u32) { |
49 | let mut symbol = fast_symbol; |
50 | // We step through the tree until we encounter a positive value, which indicates a |
51 | // symbol. |
52 | loop { |
53 | // symbol here indicates the position of the left (0) node, if the next bit is 1 |
54 | // we add 1 to the lookup position to get the right node. |
55 | symbol = i32::from(self.tree[(!symbol + ((bit_buf >> code_len) & 1) as i32) as usize]); |
56 | code_len += 1; |
57 | if symbol >= 0 { |
58 | break; |
59 | } |
60 | } |
61 | (symbol, code_len) |
62 | } |
63 | |
64 | #[inline ] |
65 | /// Look up a symbol and code length from the bits in the provided bit buffer. |
66 | /// |
67 | /// Returns Some(symbol, length) on success, |
68 | /// None if the length is 0. |
69 | /// |
70 | /// It's possible we could avoid checking for 0 if we can guarantee a sane table. |
71 | /// TODO: Check if a smaller type for code_len helps performance. |
72 | fn lookup(&self, bit_buf: BitBuffer) -> Option<(i32, u32)> { |
73 | let symbol = self.fast_lookup(bit_buf).into(); |
74 | if symbol >= 0 { |
75 | if (symbol >> 9) as u32 != 0 { |
76 | Some((symbol, (symbol >> 9) as u32)) |
77 | } else { |
78 | // Zero-length code. |
79 | None |
80 | } |
81 | } else { |
82 | // We didn't get a symbol from the fast lookup table, so check the tree instead. |
83 | Some(self.tree_lookup(symbol, bit_buf, FAST_LOOKUP_BITS.into())) |
84 | } |
85 | } |
86 | } |
87 | |
88 | /// The number of huffman tables used. |
89 | const MAX_HUFF_TABLES: usize = 3; |
90 | /// The length of the first (literal/length) huffman table. |
91 | const MAX_HUFF_SYMBOLS_0: usize = 288; |
92 | /// The length of the second (distance) huffman table. |
93 | const MAX_HUFF_SYMBOLS_1: usize = 32; |
94 | /// The length of the last (huffman code length) huffman table. |
95 | const _MAX_HUFF_SYMBOLS_2: usize = 19; |
96 | /// The maximum length of a code that can be looked up in the fast lookup table. |
97 | const FAST_LOOKUP_BITS: u8 = 10; |
98 | /// The size of the fast lookup table. |
99 | const FAST_LOOKUP_SIZE: u32 = 1 << FAST_LOOKUP_BITS; |
100 | const MAX_HUFF_TREE_SIZE: usize = MAX_HUFF_SYMBOLS_0 * 2; |
101 | const LITLEN_TABLE: usize = 0; |
102 | const DIST_TABLE: usize = 1; |
103 | const HUFFLEN_TABLE: usize = 2; |
104 | |
105 | /// Flags to [`decompress()`] to control how inflation works. |
106 | /// |
107 | /// These define bits for a bitmask argument. |
108 | pub mod inflate_flags { |
109 | /// Should we try to parse a zlib header? |
110 | /// |
111 | /// If unset, the function will expect an RFC1951 deflate stream. If set, it will expect a |
112 | /// RFC1950 zlib wrapper around the deflate stream. |
113 | pub const TINFL_FLAG_PARSE_ZLIB_HEADER: u32 = 1; |
114 | |
115 | /// There will be more input that hasn't been given to the decompressor yet. |
116 | /// |
117 | /// This is useful when you want to decompress what you have so far, |
118 | /// even if you know there is probably more input that hasn't gotten here yet (_e.g._, over a |
119 | /// network connection). When [`decompress()`][super::decompress] reaches the end of the input |
120 | /// without finding the end of the compressed stream, it will return |
121 | /// [`TINFLStatus::NeedsMoreInput`][super::TINFLStatus::NeedsMoreInput] if this is set, |
122 | /// indicating that you should get more data before calling again. If not set, it will return |
123 | /// [`TINFLStatus::FailedCannotMakeProgress`][super::TINFLStatus::FailedCannotMakeProgress] |
124 | /// suggesting the stream is corrupt, since you claimed it was all there. |
125 | pub const TINFL_FLAG_HAS_MORE_INPUT: u32 = 2; |
126 | |
127 | /// The output buffer should not wrap around. |
128 | pub const TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF: u32 = 4; |
129 | |
130 | /// Calculate the adler32 checksum of the output data even if we're not inflating a zlib stream. |
131 | /// |
132 | /// If [`TINFL_FLAG_IGNORE_ADLER32`] is specified, it will override this. |
133 | /// |
134 | /// NOTE: Enabling/disabling this between calls to decompress will result in an incorrect |
135 | /// checksum. |
136 | pub const TINFL_FLAG_COMPUTE_ADLER32: u32 = 8; |
137 | |
138 | /// Ignore adler32 checksum even if we are inflating a zlib stream. |
139 | /// |
140 | /// Overrides [`TINFL_FLAG_COMPUTE_ADLER32`] if both are enabled. |
141 | /// |
142 | /// NOTE: This flag does not exist in miniz as it does not support this and is a |
143 | /// custom addition for miniz_oxide. |
144 | /// |
145 | /// NOTE: Should not be changed from enabled to disabled after decompression has started, |
146 | /// this will result in checksum failure (outside the unlikely event where the checksum happens |
147 | /// to match anyway). |
148 | pub const TINFL_FLAG_IGNORE_ADLER32: u32 = 64; |
149 | } |
150 | |
151 | use self::inflate_flags::*; |
152 | |
153 | const MIN_TABLE_SIZES: [u16; 3] = [257, 1, 4]; |
154 | |
155 | #[cfg (target_pointer_width = "64" )] |
156 | type BitBuffer = u64; |
157 | |
158 | #[cfg (not(target_pointer_width = "64" ))] |
159 | type BitBuffer = u32; |
160 | |
161 | /// Main decompression struct. |
162 | /// |
163 | pub struct DecompressorOxide { |
164 | /// Current state of the decompressor. |
165 | state: core::State, |
166 | /// Number of bits in the bit buffer. |
167 | num_bits: u32, |
168 | /// Zlib CMF |
169 | z_header0: u32, |
170 | /// Zlib FLG |
171 | z_header1: u32, |
172 | /// Adler32 checksum from the zlib header. |
173 | z_adler32: u32, |
174 | /// 1 if the current block is the last block, 0 otherwise. |
175 | finish: u32, |
176 | /// The type of the current block. |
177 | block_type: u32, |
178 | /// 1 if the adler32 value should be checked. |
179 | check_adler32: u32, |
180 | /// Last match distance. |
181 | dist: u32, |
182 | /// Variable used for match length, symbols, and a number of other things. |
183 | counter: u32, |
184 | /// Number of extra bits for the last length or distance code. |
185 | num_extra: u32, |
186 | /// Number of entries in each huffman table. |
187 | table_sizes: [u32; MAX_HUFF_TABLES], |
188 | /// Buffer of input data. |
189 | bit_buf: BitBuffer, |
190 | /// Huffman tables. |
191 | tables: [HuffmanTable; MAX_HUFF_TABLES], |
192 | /// Raw block header. |
193 | raw_header: [u8; 4], |
194 | /// Huffman length codes. |
195 | len_codes: [u8; MAX_HUFF_SYMBOLS_0 + MAX_HUFF_SYMBOLS_1 + 137], |
196 | } |
197 | |
198 | impl DecompressorOxide { |
199 | /// Create a new tinfl_decompressor with all fields set to 0. |
200 | pub fn new() -> DecompressorOxide { |
201 | DecompressorOxide::default() |
202 | } |
203 | |
204 | /// Set the current state to `Start`. |
205 | #[inline ] |
206 | pub fn init(&mut self) { |
207 | // The rest of the data is reset or overwritten when used. |
208 | self.state = core::State::Start; |
209 | } |
210 | |
211 | /// Returns the adler32 checksum of the currently decompressed data. |
212 | /// Note: Will return Some(1) if decompressing zlib but ignoring adler32. |
213 | #[inline ] |
214 | pub fn adler32(&self) -> Option<u32> { |
215 | if self.state != State::Start && !self.state.is_failure() && self.z_header0 != 0 { |
216 | Some(self.check_adler32) |
217 | } else { |
218 | None |
219 | } |
220 | } |
221 | |
222 | /// Returns the adler32 that was read from the zlib header if it exists. |
223 | #[inline ] |
224 | pub fn adler32_header(&self) -> Option<u32> { |
225 | if self.state != State::Start && self.state != State::BadZlibHeader && self.z_header0 != 0 { |
226 | Some(self.z_adler32) |
227 | } else { |
228 | None |
229 | } |
230 | } |
231 | } |
232 | |
233 | impl Default for DecompressorOxide { |
234 | /// Create a new tinfl_decompressor with all fields set to 0. |
235 | #[inline (always)] |
236 | fn default() -> Self { |
237 | DecompressorOxide { |
238 | state: core::State::Start, |
239 | num_bits: 0, |
240 | z_header0: 0, |
241 | z_header1: 0, |
242 | z_adler32: 0, |
243 | finish: 0, |
244 | block_type: 0, |
245 | check_adler32: 0, |
246 | dist: 0, |
247 | counter: 0, |
248 | num_extra: 0, |
249 | table_sizes: [0; MAX_HUFF_TABLES], |
250 | bit_buf: 0, |
251 | // TODO:(oyvindln) Check that copies here are optimized out in release mode. |
252 | tables: [ |
253 | HuffmanTable::new(), |
254 | HuffmanTable::new(), |
255 | HuffmanTable::new(), |
256 | ], |
257 | raw_header: [0; 4], |
258 | len_codes: [0; MAX_HUFF_SYMBOLS_0 + MAX_HUFF_SYMBOLS_1 + 137], |
259 | } |
260 | } |
261 | } |
262 | |
263 | #[derive (Copy, Clone, PartialEq, Eq, Debug)] |
264 | #[non_exhaustive ] |
265 | enum State { |
266 | Start = 0, |
267 | ReadZlibCmf, |
268 | ReadZlibFlg, |
269 | ReadBlockHeader, |
270 | BlockTypeNoCompression, |
271 | RawHeader, |
272 | RawMemcpy1, |
273 | RawMemcpy2, |
274 | ReadTableSizes, |
275 | ReadHufflenTableCodeSize, |
276 | ReadLitlenDistTablesCodeSize, |
277 | ReadExtraBitsCodeSize, |
278 | DecodeLitlen, |
279 | WriteSymbol, |
280 | ReadExtraBitsLitlen, |
281 | DecodeDistance, |
282 | ReadExtraBitsDistance, |
283 | RawReadFirstByte, |
284 | RawStoreFirstByte, |
285 | WriteLenBytesToEnd, |
286 | BlockDone, |
287 | HuffDecodeOuterLoop1, |
288 | HuffDecodeOuterLoop2, |
289 | ReadAdler32, |
290 | |
291 | DoneForever, |
292 | |
293 | // Failure states. |
294 | BlockTypeUnexpected, |
295 | BadCodeSizeSum, |
296 | BadDistOrLiteralTableLength, |
297 | BadTotalSymbols, |
298 | BadZlibHeader, |
299 | DistanceOutOfBounds, |
300 | BadRawLength, |
301 | BadCodeSizeDistPrevLookup, |
302 | InvalidLitlen, |
303 | InvalidDist, |
304 | InvalidCodeLen, |
305 | } |
306 | |
307 | impl State { |
308 | fn is_failure(self) -> bool { |
309 | match self { |
310 | BlockTypeUnexpected => true, |
311 | BadCodeSizeSum => true, |
312 | BadDistOrLiteralTableLength => true, |
313 | BadTotalSymbols => true, |
314 | BadZlibHeader => true, |
315 | DistanceOutOfBounds => true, |
316 | BadRawLength => true, |
317 | BadCodeSizeDistPrevLookup => true, |
318 | InvalidLitlen => true, |
319 | InvalidDist => true, |
320 | _ => false, |
321 | } |
322 | } |
323 | |
324 | #[inline ] |
325 | fn begin(&mut self, new_state: State) { |
326 | *self = new_state; |
327 | } |
328 | } |
329 | |
330 | use self::State::*; |
331 | |
332 | // Not sure why miniz uses 32-bit values for these, maybe alignment/cache again? |
333 | // # Optimization |
334 | // We add a extra value at the end and make the tables 32 elements long |
335 | // so we can use a mask to avoid bounds checks. |
336 | // The invalid values are set to something high enough to avoid underflowing |
337 | // the match length. |
338 | /// Base length for each length code. |
339 | /// |
340 | /// The base is used together with the value of the extra bits to decode the actual |
341 | /// length/distance values in a match. |
342 | #[rustfmt::skip] |
343 | const LENGTH_BASE: [u16; 32] = [ |
344 | 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, |
345 | 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 512, 512, 512 |
346 | ]; |
347 | |
348 | /// Number of extra bits for each length code. |
349 | #[rustfmt::skip] |
350 | const LENGTH_EXTRA: [u8; 32] = [ |
351 | 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, |
352 | 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 0, 0, 0 |
353 | ]; |
354 | |
355 | /// Base length for each distance code. |
356 | #[rustfmt::skip] |
357 | const DIST_BASE: [u16; 32] = [ |
358 | 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, |
359 | 49, 65, 97, 129, 193, 257, 385, 513, 769, 1025, 1537, |
360 | 2049, 3073, 4097, 6145, 8193, 12_289, 16_385, 24_577, 32_768, 32_768 |
361 | ]; |
362 | |
363 | /// Number of extra bits for each distance code. |
364 | #[rustfmt::skip] |
365 | const DIST_EXTRA: [u8; 32] = [ |
366 | 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, |
367 | 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 13, 13 |
368 | ]; |
369 | |
370 | /// The mask used when indexing the base/extra arrays. |
371 | const BASE_EXTRA_MASK: usize = 32 - 1; |
372 | |
373 | /// Sets the value of all the elements of the slice to `val`. |
374 | #[inline ] |
375 | fn memset<T: Copy>(slice: &mut [T], val: T) { |
376 | for x: &mut T in slice { |
377 | *x = val |
378 | } |
379 | } |
380 | |
381 | /// Read an le u16 value from the slice iterator. |
382 | /// |
383 | /// # Panics |
384 | /// Panics if there are less than two bytes left. |
385 | #[inline ] |
386 | fn read_u16_le(iter: &mut slice::Iter<u8>) -> u16 { |
387 | let ret: u16 = { |
388 | let two_bytes: [u8; 2] = iter.as_ref()[..2].try_into().unwrap(); |
389 | u16::from_le_bytes(two_bytes) |
390 | }; |
391 | iter.nth(1); |
392 | ret |
393 | } |
394 | |
395 | /// Read an le u32 value from the slice iterator. |
396 | /// |
397 | /// # Panics |
398 | /// Panics if there are less than four bytes left. |
399 | #[inline (always)] |
400 | #[cfg (target_pointer_width = "64" )] |
401 | fn read_u32_le(iter: &mut slice::Iter<u8>) -> u32 { |
402 | let ret: u32 = { |
403 | let four_bytes: [u8; 4] = iter.as_ref()[..4].try_into().unwrap(); |
404 | u32::from_le_bytes(four_bytes) |
405 | }; |
406 | iter.nth(3); |
407 | ret |
408 | } |
409 | |
410 | /// Ensure that there is data in the bit buffer. |
411 | /// |
412 | /// On 64-bit platform, we use a 64-bit value so this will |
413 | /// result in there being at least 32 bits in the bit buffer. |
414 | /// This function assumes that there is at least 4 bytes left in the input buffer. |
415 | #[inline (always)] |
416 | #[cfg (target_pointer_width = "64" )] |
417 | fn fill_bit_buffer(l: &mut LocalVars, in_iter: &mut slice::Iter<u8>) { |
418 | // Read four bytes into the buffer at once. |
419 | if l.num_bits < 30 { |
420 | l.bit_buf |= BitBuffer::from(read_u32_le(in_iter)) << l.num_bits; |
421 | l.num_bits += 32; |
422 | } |
423 | } |
424 | |
425 | /// Same as previous, but for non-64-bit platforms. |
426 | /// Ensures at least 16 bits are present, requires at least 2 bytes in the in buffer. |
427 | #[inline (always)] |
428 | #[cfg (not(target_pointer_width = "64" ))] |
429 | fn fill_bit_buffer(l: &mut LocalVars, in_iter: &mut slice::Iter<u8>) { |
430 | // If the buffer is 32-bit wide, read 2 bytes instead. |
431 | if l.num_bits < 15 { |
432 | l.bit_buf |= BitBuffer::from(read_u16_le(in_iter)) << l.num_bits; |
433 | l.num_bits += 16; |
434 | } |
435 | } |
436 | |
437 | /// Check that the zlib header is correct and that there is enough space in the buffer |
438 | /// for the window size specified in the header. |
439 | /// |
440 | /// See https://tools.ietf.org/html/rfc1950 |
441 | #[inline ] |
442 | fn validate_zlib_header(cmf: u32, flg: u32, flags: u32, mask: usize) -> Action { |
443 | let mut failed = |
444 | // cmf + flg should be divisible by 31. |
445 | (((cmf * 256) + flg) % 31 != 0) || |
446 | // If this flag is set, a dictionary was used for this zlib compressed data. |
447 | // This is currently not supported by miniz or miniz-oxide |
448 | ((flg & 0b0010_0000) != 0) || |
449 | // Compression method. Only 8(DEFLATE) is defined by the standard. |
450 | ((cmf & 15) != 8); |
451 | |
452 | let window_size = 1 << ((cmf >> 4) + 8); |
453 | if (flags & TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF) == 0 { |
454 | // Bail if the buffer is wrapping and the window size is larger than the buffer. |
455 | failed |= (mask + 1) < window_size; |
456 | } |
457 | |
458 | // Zlib doesn't allow window sizes above 32 * 1024. |
459 | failed |= window_size > 32_768; |
460 | |
461 | if failed { |
462 | Action::Jump(BadZlibHeader) |
463 | } else { |
464 | Action::Jump(ReadBlockHeader) |
465 | } |
466 | } |
467 | |
468 | enum Action { |
469 | None, |
470 | Jump(State), |
471 | End(TINFLStatus), |
472 | } |
473 | |
474 | /// Try to decode the next huffman code, and puts it in the counter field of the decompressor |
475 | /// if successful. |
476 | /// |
477 | /// # Returns |
478 | /// The specified action returned from `f` on success, |
479 | /// `Action::End` if there are not enough data left to decode a symbol. |
480 | fn decode_huffman_code<F>( |
481 | r: &mut DecompressorOxide, |
482 | l: &mut LocalVars, |
483 | table: usize, |
484 | flags: u32, |
485 | in_iter: &mut slice::Iter<u8>, |
486 | f: F, |
487 | ) -> Action |
488 | where |
489 | F: FnOnce(&mut DecompressorOxide, &mut LocalVars, i32) -> Action, |
490 | { |
491 | // As the huffman codes can be up to 15 bits long we need at least 15 bits |
492 | // ready in the bit buffer to start decoding the next huffman code. |
493 | if l.num_bits < 15 { |
494 | // First, make sure there is enough data in the bit buffer to decode a huffman code. |
495 | if in_iter.len() < 2 { |
496 | // If there is less than 2 bytes left in the input buffer, we try to look up |
497 | // the huffman code with what's available, and return if that doesn't succeed. |
498 | // Original explanation in miniz: |
499 | // /* TINFL_HUFF_BITBUF_FILL() is only used rarely, when the number of bytes |
500 | // * remaining in the input buffer falls below 2. */ |
501 | // /* It reads just enough bytes from the input stream that are needed to decode |
502 | // * the next Huffman code (and absolutely no more). It works by trying to fully |
503 | // * decode a */ |
504 | // /* Huffman code by using whatever bits are currently present in the bit buffer. |
505 | // * If this fails, it reads another byte, and tries again until it succeeds or |
506 | // * until the */ |
507 | // /* bit buffer contains >=15 bits (deflate's max. Huffman code size). */ |
508 | loop { |
509 | let mut temp = i32::from(r.tables[table].fast_lookup(l.bit_buf)); |
510 | |
511 | if temp >= 0 { |
512 | let code_len = (temp >> 9) as u32; |
513 | if (code_len != 0) && (l.num_bits >= code_len) { |
514 | break; |
515 | } |
516 | } else if l.num_bits > FAST_LOOKUP_BITS.into() { |
517 | let mut code_len = u32::from(FAST_LOOKUP_BITS); |
518 | loop { |
519 | temp = i32::from( |
520 | r.tables[table].tree |
521 | [(!temp + ((l.bit_buf >> code_len) & 1) as i32) as usize], |
522 | ); |
523 | code_len += 1; |
524 | if temp >= 0 || l.num_bits < code_len + 1 { |
525 | break; |
526 | } |
527 | } |
528 | if temp >= 0 { |
529 | break; |
530 | } |
531 | } |
532 | |
533 | // TODO: miniz jumps straight to here after getting here again after failing to read |
534 | // a byte. |
535 | // Doing that lets miniz avoid re-doing the lookup that that was done in the |
536 | // previous call. |
537 | let mut byte = 0; |
538 | if let a @ Action::End(_) = read_byte(in_iter, flags, |b| { |
539 | byte = b; |
540 | Action::None |
541 | }) { |
542 | return a; |
543 | }; |
544 | |
545 | // Do this outside closure for now to avoid borrowing r. |
546 | l.bit_buf |= BitBuffer::from(byte) << l.num_bits; |
547 | l.num_bits += 8; |
548 | |
549 | if l.num_bits >= 15 { |
550 | break; |
551 | } |
552 | } |
553 | } else { |
554 | // There is enough data in the input buffer, so read the next two bytes |
555 | // and add them to the bit buffer. |
556 | // Unwrapping here is fine since we just checked that there are at least two |
557 | // bytes left. |
558 | l.bit_buf |= BitBuffer::from(read_u16_le(in_iter)) << l.num_bits; |
559 | l.num_bits += 16; |
560 | } |
561 | } |
562 | |
563 | // We now have at least 15 bits in the input buffer. |
564 | let mut symbol = i32::from(r.tables[table].fast_lookup(l.bit_buf)); |
565 | let code_len; |
566 | // If the symbol was found in the fast lookup table. |
567 | if symbol >= 0 { |
568 | // Get the length value from the top bits. |
569 | // As we shift down the sign bit, converting to an unsigned value |
570 | // shouldn't overflow. |
571 | code_len = (symbol >> 9) as u32; |
572 | // Mask out the length value. |
573 | symbol &= 511; |
574 | } else { |
575 | let res = r.tables[table].tree_lookup(symbol, l.bit_buf, u32::from(FAST_LOOKUP_BITS)); |
576 | symbol = res.0; |
577 | code_len = res.1 as u32; |
578 | }; |
579 | |
580 | if code_len == 0 { |
581 | return Action::Jump(InvalidCodeLen); |
582 | } |
583 | |
584 | l.bit_buf >>= code_len as u32; |
585 | l.num_bits -= code_len; |
586 | f(r, l, symbol) |
587 | } |
588 | |
589 | /// Try to read one byte from `in_iter` and call `f` with the read byte as an argument, |
590 | /// returning the result. |
591 | /// If reading fails, `Action::End is returned` |
592 | #[inline ] |
593 | fn read_byte<F>(in_iter: &mut slice::Iter<u8>, flags: u32, f: F) -> Action |
594 | where |
595 | F: FnOnce(u8) -> Action, |
596 | { |
597 | match in_iter.next() { |
598 | None => end_of_input(flags), |
599 | Some(&byte: u8) => f(byte), |
600 | } |
601 | } |
602 | |
603 | // TODO: `l: &mut LocalVars` may be slow similar to decompress_fast (even with inline(always)) |
604 | /// Try to read `amount` number of bits from `in_iter` and call the function `f` with the bits as an |
605 | /// an argument after reading, returning the result of that function, or `Action::End` if there are |
606 | /// not enough bytes left. |
607 | #[inline ] |
608 | #[allow (clippy::while_immutable_condition)] |
609 | fn read_bits<F>( |
610 | l: &mut LocalVars, |
611 | amount: u32, |
612 | in_iter: &mut slice::Iter<u8>, |
613 | flags: u32, |
614 | f: F, |
615 | ) -> Action |
616 | where |
617 | F: FnOnce(&mut LocalVars, BitBuffer) -> Action, |
618 | { |
619 | // Clippy gives a false positive warning here due to the closure. |
620 | // Read enough bytes from the input iterator to cover the number of bits we want. |
621 | while l.num_bits < amount { |
622 | match read_byte(in_iter, flags, |byte: u8| { |
623 | l.bit_buf |= BitBuffer::from(byte) << l.num_bits; |
624 | l.num_bits += 8; |
625 | Action::None |
626 | }) { |
627 | Action::None => (), |
628 | // If there are not enough bytes in the input iterator, return and signal that we need |
629 | // more. |
630 | action: Action => return action, |
631 | } |
632 | } |
633 | |
634 | let bits: u64 = l.bit_buf & ((1 << amount) - 1); |
635 | l.bit_buf >>= amount; |
636 | l.num_bits -= amount; |
637 | f(l, bits) |
638 | } |
639 | |
640 | #[inline ] |
641 | fn pad_to_bytes<F>(l: &mut LocalVars, in_iter: &mut slice::Iter<u8>, flags: u32, f: F) -> Action |
642 | where |
643 | F: FnOnce(&mut LocalVars) -> Action, |
644 | { |
645 | let num_bits: u32 = l.num_bits & 7; |
646 | read_bits(l, amount:num_bits, in_iter, flags, |l: &mut LocalVars, _| f(l)) |
647 | } |
648 | |
649 | #[inline ] |
650 | fn end_of_input(flags: u32) -> Action { |
651 | Action::End(if flags & TINFL_FLAG_HAS_MORE_INPUT != 0 { |
652 | TINFLStatus::NeedsMoreInput |
653 | } else { |
654 | TINFLStatus::FailedCannotMakeProgress |
655 | }) |
656 | } |
657 | |
658 | #[inline ] |
659 | fn undo_bytes(l: &mut LocalVars, max: u32) -> u32 { |
660 | let res: u32 = cmp::min(v1:l.num_bits >> 3, v2:max); |
661 | l.num_bits -= res << 3; |
662 | res |
663 | } |
664 | |
665 | fn start_static_table(r: &mut DecompressorOxide) { |
666 | r.table_sizes[LITLEN_TABLE] = 288; |
667 | r.table_sizes[DIST_TABLE] = 32; |
668 | memset(&mut r.tables[LITLEN_TABLE].code_size[0..144], val:8); |
669 | memset(&mut r.tables[LITLEN_TABLE].code_size[144..256], val:9); |
670 | memset(&mut r.tables[LITLEN_TABLE].code_size[256..280], val:7); |
671 | memset(&mut r.tables[LITLEN_TABLE].code_size[280..288], val:8); |
672 | memset(&mut r.tables[DIST_TABLE].code_size[0..32], val:5); |
673 | } |
674 | |
675 | static REVERSED_BITS_LOOKUP: [u32; 1024] = { |
676 | let mut table: [u32; 1024] = [0; 1024]; |
677 | |
678 | let mut i: usize = 0; |
679 | while i < 1024 { |
680 | table[i] = (i as u32).reverse_bits(); |
681 | i += 1; |
682 | } |
683 | |
684 | table |
685 | }; |
686 | |
687 | fn init_tree(r: &mut DecompressorOxide, l: &mut LocalVars) -> Action { |
688 | loop { |
689 | let table = &mut r.tables[r.block_type as usize]; |
690 | let table_size = r.table_sizes[r.block_type as usize] as usize; |
691 | let mut total_symbols = [0u32; 16]; |
692 | let mut next_code = [0u32; 17]; |
693 | memset(&mut table.look_up[..], 0); |
694 | memset(&mut table.tree[..], 0); |
695 | |
696 | for &code_size in &table.code_size[..table_size] { |
697 | total_symbols[code_size as usize] += 1; |
698 | } |
699 | |
700 | let mut used_symbols = 0; |
701 | let mut total = 0; |
702 | for i in 1..16 { |
703 | used_symbols += total_symbols[i]; |
704 | total += total_symbols[i]; |
705 | total <<= 1; |
706 | next_code[i + 1] = total; |
707 | } |
708 | |
709 | if total != 65_536 && used_symbols > 1 { |
710 | return Action::Jump(BadTotalSymbols); |
711 | } |
712 | |
713 | let mut tree_next = -1; |
714 | for symbol_index in 0..table_size { |
715 | let mut rev_code = 0; |
716 | let code_size = table.code_size[symbol_index]; |
717 | if code_size == 0 { |
718 | continue; |
719 | } |
720 | |
721 | let mut cur_code = next_code[code_size as usize]; |
722 | next_code[code_size as usize] += 1; |
723 | |
724 | let n = cur_code & (u32::MAX >> (32 - code_size)); |
725 | |
726 | let mut rev_code = if n < 1024 { |
727 | REVERSED_BITS_LOOKUP[n as usize] >> (32 - code_size) |
728 | } else { |
729 | for _ in 0..code_size { |
730 | rev_code = (rev_code << 1) | (cur_code & 1); |
731 | cur_code >>= 1; |
732 | } |
733 | rev_code |
734 | }; |
735 | |
736 | if code_size <= FAST_LOOKUP_BITS { |
737 | let k = (i16::from(code_size) << 9) | symbol_index as i16; |
738 | while rev_code < FAST_LOOKUP_SIZE { |
739 | table.look_up[rev_code as usize] = k; |
740 | rev_code += 1 << code_size; |
741 | } |
742 | continue; |
743 | } |
744 | |
745 | let mut tree_cur = table.look_up[(rev_code & (FAST_LOOKUP_SIZE - 1)) as usize]; |
746 | if tree_cur == 0 { |
747 | table.look_up[(rev_code & (FAST_LOOKUP_SIZE - 1)) as usize] = tree_next as i16; |
748 | tree_cur = tree_next; |
749 | tree_next -= 2; |
750 | } |
751 | |
752 | rev_code >>= FAST_LOOKUP_BITS - 1; |
753 | for _ in FAST_LOOKUP_BITS + 1..code_size { |
754 | rev_code >>= 1; |
755 | tree_cur -= (rev_code & 1) as i16; |
756 | if table.tree[(-tree_cur - 1) as usize] == 0 { |
757 | table.tree[(-tree_cur - 1) as usize] = tree_next as i16; |
758 | tree_cur = tree_next; |
759 | tree_next -= 2; |
760 | } else { |
761 | tree_cur = table.tree[(-tree_cur - 1) as usize]; |
762 | } |
763 | } |
764 | |
765 | rev_code >>= 1; |
766 | tree_cur -= (rev_code & 1) as i16; |
767 | table.tree[(-tree_cur - 1) as usize] = symbol_index as i16; |
768 | } |
769 | |
770 | if r.block_type == 2 { |
771 | l.counter = 0; |
772 | return Action::Jump(ReadLitlenDistTablesCodeSize); |
773 | } |
774 | |
775 | if r.block_type == 0 { |
776 | break; |
777 | } |
778 | r.block_type -= 1; |
779 | } |
780 | |
781 | l.counter = 0; |
782 | Action::Jump(DecodeLitlen) |
783 | } |
784 | |
785 | // A helper macro for generating the state machine. |
786 | // |
787 | // As Rust doesn't have fallthrough on matches, we have to return to the match statement |
788 | // and jump for each state change. (Which would ideally be optimized away, but often isn't.) |
789 | macro_rules! generate_state { |
790 | ($state: ident, $state_machine: tt, $f: expr) => { |
791 | loop { |
792 | match $f { |
793 | Action::None => continue, |
794 | Action::Jump(new_state) => { |
795 | $state = new_state; |
796 | continue $state_machine; |
797 | }, |
798 | Action::End(result) => break $state_machine result, |
799 | } |
800 | } |
801 | }; |
802 | } |
803 | |
804 | #[derive (Copy, Clone)] |
805 | struct LocalVars { |
806 | pub bit_buf: BitBuffer, |
807 | pub num_bits: u32, |
808 | pub dist: u32, |
809 | pub counter: u32, |
810 | pub num_extra: u32, |
811 | } |
812 | |
813 | #[inline ] |
814 | fn transfer( |
815 | out_slice: &mut [u8], |
816 | mut source_pos: usize, |
817 | mut out_pos: usize, |
818 | match_len: usize, |
819 | out_buf_size_mask: usize, |
820 | ) { |
821 | // special case that comes up surprisingly often. in the case that `source_pos` |
822 | // is 1 less than `out_pos`, we can say that the entire range will be the same |
823 | // value and optimize this to be a simple `memset` |
824 | let source_diff = if source_pos > out_pos { |
825 | source_pos - out_pos |
826 | } else { |
827 | out_pos - source_pos |
828 | }; |
829 | if out_buf_size_mask == usize::MAX && source_diff == 1 && out_pos > source_pos { |
830 | let init = out_slice[out_pos - 1]; |
831 | let end = (match_len >> 2) * 4 + out_pos; |
832 | |
833 | out_slice[out_pos..end].fill(init); |
834 | out_pos = end; |
835 | source_pos = end - 1; |
836 | // if the difference between `source_pos` and `out_pos` is greater than 3, we |
837 | // can do slightly better than the naive case by copying everything at once |
838 | } else if out_buf_size_mask == usize::MAX && source_diff >= 4 && out_pos > source_pos { |
839 | for _ in 0..match_len >> 2 { |
840 | out_slice.copy_within(source_pos..=source_pos + 3, out_pos); |
841 | source_pos += 4; |
842 | out_pos += 4; |
843 | } |
844 | } else { |
845 | for _ in 0..match_len >> 2 { |
846 | out_slice[out_pos] = out_slice[source_pos & out_buf_size_mask]; |
847 | out_slice[out_pos + 1] = out_slice[(source_pos + 1) & out_buf_size_mask]; |
848 | out_slice[out_pos + 2] = out_slice[(source_pos + 2) & out_buf_size_mask]; |
849 | out_slice[out_pos + 3] = out_slice[(source_pos + 3) & out_buf_size_mask]; |
850 | source_pos += 4; |
851 | out_pos += 4; |
852 | } |
853 | } |
854 | |
855 | match match_len & 3 { |
856 | 0 => (), |
857 | 1 => out_slice[out_pos] = out_slice[source_pos & out_buf_size_mask], |
858 | 2 => { |
859 | out_slice[out_pos] = out_slice[source_pos & out_buf_size_mask]; |
860 | out_slice[out_pos + 1] = out_slice[(source_pos + 1) & out_buf_size_mask]; |
861 | } |
862 | 3 => { |
863 | out_slice[out_pos] = out_slice[source_pos & out_buf_size_mask]; |
864 | out_slice[out_pos + 1] = out_slice[(source_pos + 1) & out_buf_size_mask]; |
865 | out_slice[out_pos + 2] = out_slice[(source_pos + 2) & out_buf_size_mask]; |
866 | } |
867 | _ => unreachable!(), |
868 | } |
869 | } |
870 | |
871 | /// Presumes that there is at least match_len bytes in output left. |
872 | #[inline ] |
873 | fn apply_match( |
874 | out_slice: &mut [u8], |
875 | out_pos: usize, |
876 | dist: usize, |
877 | match_len: usize, |
878 | out_buf_size_mask: usize, |
879 | ) { |
880 | debug_assert!(out_pos + match_len <= out_slice.len()); |
881 | |
882 | let source_pos = out_pos.wrapping_sub(dist) & out_buf_size_mask; |
883 | |
884 | if match_len == 3 { |
885 | // Fast path for match len 3. |
886 | out_slice[out_pos] = out_slice[source_pos]; |
887 | out_slice[out_pos + 1] = out_slice[(source_pos + 1) & out_buf_size_mask]; |
888 | out_slice[out_pos + 2] = out_slice[(source_pos + 2) & out_buf_size_mask]; |
889 | return; |
890 | } |
891 | |
892 | if cfg!(not(any(target_arch = "x86" , target_arch = "x86_64" ))) { |
893 | // We are not on x86 so copy manually. |
894 | transfer(out_slice, source_pos, out_pos, match_len, out_buf_size_mask); |
895 | return; |
896 | } |
897 | |
898 | if source_pos >= out_pos && (source_pos - out_pos) < match_len { |
899 | transfer(out_slice, source_pos, out_pos, match_len, out_buf_size_mask); |
900 | } else if match_len <= dist && source_pos + match_len < out_slice.len() { |
901 | // Destination and source segments does not intersect and source does not wrap. |
902 | if source_pos < out_pos { |
903 | let (from_slice, to_slice) = out_slice.split_at_mut(out_pos); |
904 | to_slice[..match_len].copy_from_slice(&from_slice[source_pos..source_pos + match_len]); |
905 | } else { |
906 | let (to_slice, from_slice) = out_slice.split_at_mut(source_pos); |
907 | to_slice[out_pos..out_pos + match_len].copy_from_slice(&from_slice[..match_len]); |
908 | } |
909 | } else { |
910 | transfer(out_slice, source_pos, out_pos, match_len, out_buf_size_mask); |
911 | } |
912 | } |
913 | |
914 | /// Fast inner decompression loop which is run while there is at least |
915 | /// 259 bytes left in the output buffer, and at least 6 bytes left in the input buffer |
916 | /// (The maximum one match would need + 1). |
917 | /// |
918 | /// This was inspired by a similar optimization in zlib, which uses this info to do |
919 | /// faster unchecked copies of multiple bytes at a time. |
920 | /// Currently we don't do this here, but this function does avoid having to jump through the |
921 | /// big match loop on each state change(as rust does not have fallthrough or gotos at the moment), |
922 | /// and already improves decompression speed a fair bit. |
923 | fn decompress_fast( |
924 | r: &mut DecompressorOxide, |
925 | in_iter: &mut slice::Iter<u8>, |
926 | out_buf: &mut OutputBuffer, |
927 | flags: u32, |
928 | local_vars: &mut LocalVars, |
929 | out_buf_size_mask: usize, |
930 | ) -> (TINFLStatus, State) { |
931 | // Make a local copy of the most used variables, to avoid having to update and read from values |
932 | // in a random memory location and to encourage more register use. |
933 | let mut l = *local_vars; |
934 | let mut state; |
935 | |
936 | let status: TINFLStatus = 'o: loop { |
937 | state = State::DecodeLitlen; |
938 | loop { |
939 | // This function assumes that there is at least 259 bytes left in the output buffer, |
940 | // and that there is at least 14 bytes left in the input buffer. 14 input bytes: |
941 | // 15 (prev lit) + 15 (length) + 5 (length extra) + 15 (dist) |
942 | // + 29 + 32 (left in bit buf, including last 13 dist extra) = 111 bits < 14 bytes |
943 | // We need the one extra byte as we may write one length and one full match |
944 | // before checking again. |
945 | if out_buf.bytes_left() < 259 || in_iter.len() < 14 { |
946 | state = State::DecodeLitlen; |
947 | break 'o TINFLStatus::Done; |
948 | } |
949 | |
950 | fill_bit_buffer(&mut l, in_iter); |
951 | |
952 | if let Some((symbol, code_len)) = r.tables[LITLEN_TABLE].lookup(l.bit_buf) { |
953 | l.counter = symbol as u32; |
954 | l.bit_buf >>= code_len; |
955 | l.num_bits -= code_len; |
956 | |
957 | if (l.counter & 256) != 0 { |
958 | // The symbol is not a literal. |
959 | break; |
960 | } else { |
961 | // If we have a 32-bit buffer we need to read another two bytes now |
962 | // to have enough bits to keep going. |
963 | if cfg!(not(target_pointer_width = "64" )) { |
964 | fill_bit_buffer(&mut l, in_iter); |
965 | } |
966 | |
967 | if let Some((symbol, code_len)) = r.tables[LITLEN_TABLE].lookup(l.bit_buf) { |
968 | l.bit_buf >>= code_len; |
969 | l.num_bits -= code_len; |
970 | // The previous symbol was a literal, so write it directly and check |
971 | // the next one. |
972 | out_buf.write_byte(l.counter as u8); |
973 | if (symbol & 256) != 0 { |
974 | l.counter = symbol as u32; |
975 | // The symbol is a length value. |
976 | break; |
977 | } else { |
978 | // The symbol is a literal, so write it directly and continue. |
979 | out_buf.write_byte(symbol as u8); |
980 | } |
981 | } else { |
982 | state.begin(InvalidCodeLen); |
983 | break 'o TINFLStatus::Failed; |
984 | } |
985 | } |
986 | } else { |
987 | state.begin(InvalidCodeLen); |
988 | break 'o TINFLStatus::Failed; |
989 | } |
990 | } |
991 | |
992 | // Mask the top bits since they may contain length info. |
993 | l.counter &= 511; |
994 | if l.counter == 256 { |
995 | // We hit the end of block symbol. |
996 | state.begin(BlockDone); |
997 | break 'o TINFLStatus::Done; |
998 | } else if l.counter > 285 { |
999 | // Invalid code. |
1000 | // We already verified earlier that the code is > 256. |
1001 | state.begin(InvalidLitlen); |
1002 | break 'o TINFLStatus::Failed; |
1003 | } else { |
1004 | // The symbol was a length code. |
1005 | // # Optimization |
1006 | // Mask the value to avoid bounds checks |
1007 | // We could use get_unchecked later if can statically verify that |
1008 | // this will never go out of bounds. |
1009 | l.num_extra = u32::from(LENGTH_EXTRA[(l.counter - 257) as usize & BASE_EXTRA_MASK]); |
1010 | l.counter = u32::from(LENGTH_BASE[(l.counter - 257) as usize & BASE_EXTRA_MASK]); |
1011 | // Length and distance codes have a number of extra bits depending on |
1012 | // the base, which together with the base gives us the exact value. |
1013 | |
1014 | fill_bit_buffer(&mut l, in_iter); |
1015 | if l.num_extra != 0 { |
1016 | let extra_bits = l.bit_buf & ((1 << l.num_extra) - 1); |
1017 | l.bit_buf >>= l.num_extra; |
1018 | l.num_bits -= l.num_extra; |
1019 | l.counter += extra_bits as u32; |
1020 | } |
1021 | |
1022 | // We found a length code, so a distance code should follow. |
1023 | |
1024 | if cfg!(not(target_pointer_width = "64" )) { |
1025 | fill_bit_buffer(&mut l, in_iter); |
1026 | } |
1027 | |
1028 | if let Some((mut symbol, code_len)) = r.tables[DIST_TABLE].lookup(l.bit_buf) { |
1029 | symbol &= 511; |
1030 | l.bit_buf >>= code_len; |
1031 | l.num_bits -= code_len; |
1032 | if symbol > 29 { |
1033 | state.begin(InvalidDist); |
1034 | break 'o TINFLStatus::Failed; |
1035 | } |
1036 | |
1037 | l.num_extra = u32::from(DIST_EXTRA[symbol as usize]); |
1038 | l.dist = u32::from(DIST_BASE[symbol as usize]); |
1039 | } else { |
1040 | state.begin(InvalidCodeLen); |
1041 | break 'o TINFLStatus::Failed; |
1042 | } |
1043 | |
1044 | if l.num_extra != 0 { |
1045 | fill_bit_buffer(&mut l, in_iter); |
1046 | let extra_bits = l.bit_buf & ((1 << l.num_extra) - 1); |
1047 | l.bit_buf >>= l.num_extra; |
1048 | l.num_bits -= l.num_extra; |
1049 | l.dist += extra_bits as u32; |
1050 | } |
1051 | |
1052 | let position = out_buf.position(); |
1053 | if l.dist as usize > out_buf.position() |
1054 | && (flags & TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF != 0) |
1055 | { |
1056 | // We encountered a distance that refers a position before |
1057 | // the start of the decoded data, so we can't continue. |
1058 | state.begin(DistanceOutOfBounds); |
1059 | break TINFLStatus::Failed; |
1060 | } |
1061 | |
1062 | apply_match( |
1063 | out_buf.get_mut(), |
1064 | position, |
1065 | l.dist as usize, |
1066 | l.counter as usize, |
1067 | out_buf_size_mask, |
1068 | ); |
1069 | |
1070 | out_buf.set_position(position + l.counter as usize); |
1071 | } |
1072 | }; |
1073 | |
1074 | *local_vars = l; |
1075 | (status, state) |
1076 | } |
1077 | |
1078 | /// Main decompression function. Keeps decompressing data from `in_buf` until the `in_buf` is |
1079 | /// empty, `out` is full, the end of the deflate stream is hit, or there is an error in the |
1080 | /// deflate stream. |
1081 | /// |
1082 | /// # Arguments |
1083 | /// |
1084 | /// `r` is a [`DecompressorOxide`] struct with the state of this stream. |
1085 | /// |
1086 | /// `in_buf` is a reference to the compressed data that is to be decompressed. The decompressor will |
1087 | /// start at the first byte of this buffer. |
1088 | /// |
1089 | /// `out` is a reference to the buffer that will store the decompressed data, and that |
1090 | /// stores previously decompressed data if any. |
1091 | /// |
1092 | /// * The offset given by `out_pos` indicates where in the output buffer slice writing should start. |
1093 | /// * If [`TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF`] is not set, the output buffer is used in a |
1094 | /// wrapping manner, and it's size is required to be a power of 2. |
1095 | /// * The decompression function normally needs access to 32KiB of the previously decompressed data |
1096 | ///(or to the beginning of the decompressed data if less than 32KiB has been decompressed.) |
1097 | /// - If this data is not available, decompression may fail. |
1098 | /// - Some deflate compressors allow specifying a window size which limits match distances to |
1099 | /// less than this, or alternatively an RLE mode where matches will only refer to the previous byte |
1100 | /// and thus allows a smaller output buffer. The window size can be specified in the zlib |
1101 | /// header structure, however, the header data should not be relied on to be correct. |
1102 | /// |
1103 | /// `flags` indicates settings and status to the decompression function. |
1104 | /// * The [`TINFL_FLAG_HAS_MORE_INPUT`] has to be specified if more compressed data is to be provided |
1105 | /// in a subsequent call to this function. |
1106 | /// * See the the [`inflate_flags`] module for details on other flags. |
1107 | /// |
1108 | /// # Returns |
1109 | /// |
1110 | /// Returns a tuple containing the status of the compressor, the number of input bytes read, and the |
1111 | /// number of bytes output to `out`. |
1112 | /// |
1113 | /// This function shouldn't panic pending any bugs. |
1114 | pub fn decompress( |
1115 | r: &mut DecompressorOxide, |
1116 | in_buf: &[u8], |
1117 | out: &mut [u8], |
1118 | out_pos: usize, |
1119 | flags: u32, |
1120 | ) -> (TINFLStatus, usize, usize) { |
1121 | let out_buf_size_mask = if flags & TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF != 0 { |
1122 | usize::max_value() |
1123 | } else { |
1124 | // In the case of zero len, any attempt to write would produce HasMoreOutput, |
1125 | // so to gracefully process the case of there really being no output, |
1126 | // set the mask to all zeros. |
1127 | out.len().saturating_sub(1) |
1128 | }; |
1129 | |
1130 | // Ensure the output buffer's size is a power of 2, unless the output buffer |
1131 | // is large enough to hold the entire output file (in which case it doesn't |
1132 | // matter). |
1133 | // Also make sure that the output buffer position is not past the end of the output buffer. |
1134 | if (out_buf_size_mask.wrapping_add(1) & out_buf_size_mask) != 0 || out_pos > out.len() { |
1135 | return (TINFLStatus::BadParam, 0, 0); |
1136 | } |
1137 | |
1138 | let mut in_iter = in_buf.iter(); |
1139 | |
1140 | let mut state = r.state; |
1141 | |
1142 | let mut out_buf = OutputBuffer::from_slice_and_pos(out, out_pos); |
1143 | |
1144 | // Make a local copy of the important variables here so we can work with them on the stack. |
1145 | let mut l = LocalVars { |
1146 | bit_buf: r.bit_buf, |
1147 | num_bits: r.num_bits, |
1148 | dist: r.dist, |
1149 | counter: r.counter, |
1150 | num_extra: r.num_extra, |
1151 | }; |
1152 | |
1153 | let mut status = 'state_machine: loop { |
1154 | match state { |
1155 | Start => generate_state!(state, 'state_machine, { |
1156 | l.bit_buf = 0; |
1157 | l.num_bits = 0; |
1158 | l.dist = 0; |
1159 | l.counter = 0; |
1160 | l.num_extra = 0; |
1161 | r.z_header0 = 0; |
1162 | r.z_header1 = 0; |
1163 | r.z_adler32 = 1; |
1164 | r.check_adler32 = 1; |
1165 | if flags & TINFL_FLAG_PARSE_ZLIB_HEADER != 0 { |
1166 | Action::Jump(State::ReadZlibCmf) |
1167 | } else { |
1168 | Action::Jump(State::ReadBlockHeader) |
1169 | } |
1170 | }), |
1171 | |
1172 | ReadZlibCmf => generate_state!(state, 'state_machine, { |
1173 | read_byte(&mut in_iter, flags, |cmf| { |
1174 | r.z_header0 = u32::from(cmf); |
1175 | Action::Jump(State::ReadZlibFlg) |
1176 | }) |
1177 | }), |
1178 | |
1179 | ReadZlibFlg => generate_state!(state, 'state_machine, { |
1180 | read_byte(&mut in_iter, flags, |flg| { |
1181 | r.z_header1 = u32::from(flg); |
1182 | validate_zlib_header(r.z_header0, r.z_header1, flags, out_buf_size_mask) |
1183 | }) |
1184 | }), |
1185 | |
1186 | // Read the block header and jump to the relevant section depending on the block type. |
1187 | ReadBlockHeader => generate_state!(state, 'state_machine, { |
1188 | read_bits(&mut l, 3, &mut in_iter, flags, |l, bits| { |
1189 | r.finish = (bits & 1) as u32; |
1190 | r.block_type = (bits >> 1) as u32 & 3; |
1191 | match r.block_type { |
1192 | 0 => Action::Jump(BlockTypeNoCompression), |
1193 | 1 => { |
1194 | start_static_table(r); |
1195 | init_tree(r, l) |
1196 | }, |
1197 | 2 => { |
1198 | l.counter = 0; |
1199 | Action::Jump(ReadTableSizes) |
1200 | }, |
1201 | 3 => Action::Jump(BlockTypeUnexpected), |
1202 | _ => unreachable!() |
1203 | } |
1204 | }) |
1205 | }), |
1206 | |
1207 | // Raw/Stored/uncompressed block. |
1208 | BlockTypeNoCompression => generate_state!(state, 'state_machine, { |
1209 | pad_to_bytes(&mut l, &mut in_iter, flags, |l| { |
1210 | l.counter = 0; |
1211 | Action::Jump(RawHeader) |
1212 | }) |
1213 | }), |
1214 | |
1215 | // Check that the raw block header is correct. |
1216 | RawHeader => generate_state!(state, 'state_machine, { |
1217 | if l.counter < 4 { |
1218 | // Read block length and block length check. |
1219 | if l.num_bits != 0 { |
1220 | read_bits(&mut l, 8, &mut in_iter, flags, |l, bits| { |
1221 | r.raw_header[l.counter as usize] = bits as u8; |
1222 | l.counter += 1; |
1223 | Action::None |
1224 | }) |
1225 | } else { |
1226 | read_byte(&mut in_iter, flags, |byte| { |
1227 | r.raw_header[l.counter as usize] = byte; |
1228 | l.counter += 1; |
1229 | Action::None |
1230 | }) |
1231 | } |
1232 | } else { |
1233 | // Check if the length value of a raw block is correct. |
1234 | // The 2 first (2-byte) words in a raw header are the length and the |
1235 | // ones complement of the length. |
1236 | let length = u16::from(r.raw_header[0]) | (u16::from(r.raw_header[1]) << 8); |
1237 | let check = u16::from(r.raw_header[2]) | (u16::from(r.raw_header[3]) << 8); |
1238 | let valid = length == !check; |
1239 | l.counter = length.into(); |
1240 | |
1241 | if !valid { |
1242 | Action::Jump(BadRawLength) |
1243 | } else if l.counter == 0 { |
1244 | // Empty raw block. Sometimes used for synchronization. |
1245 | Action::Jump(BlockDone) |
1246 | } else if l.num_bits != 0 { |
1247 | // There is some data in the bit buffer, so we need to write that first. |
1248 | Action::Jump(RawReadFirstByte) |
1249 | } else { |
1250 | // The bit buffer is empty, so memcpy the rest of the uncompressed data from |
1251 | // the block. |
1252 | Action::Jump(RawMemcpy1) |
1253 | } |
1254 | } |
1255 | }), |
1256 | |
1257 | // Read the byte from the bit buffer. |
1258 | RawReadFirstByte => generate_state!(state, 'state_machine, { |
1259 | read_bits(&mut l, 8, &mut in_iter, flags, |l, bits| { |
1260 | l.dist = bits as u32; |
1261 | Action::Jump(RawStoreFirstByte) |
1262 | }) |
1263 | }), |
1264 | |
1265 | // Write the byte we just read to the output buffer. |
1266 | RawStoreFirstByte => generate_state!(state, 'state_machine, { |
1267 | if out_buf.bytes_left() == 0 { |
1268 | Action::End(TINFLStatus::HasMoreOutput) |
1269 | } else { |
1270 | out_buf.write_byte(l.dist as u8); |
1271 | l.counter -= 1; |
1272 | if l.counter == 0 || l.num_bits == 0 { |
1273 | Action::Jump(RawMemcpy1) |
1274 | } else { |
1275 | // There is still some data left in the bit buffer that needs to be output. |
1276 | // TODO: Changed this to jump to `RawReadfirstbyte` rather than |
1277 | // `RawStoreFirstByte` as that seemed to be the correct path, but this |
1278 | // needs testing. |
1279 | Action::Jump(RawReadFirstByte) |
1280 | } |
1281 | } |
1282 | }), |
1283 | |
1284 | RawMemcpy1 => generate_state!(state, 'state_machine, { |
1285 | if l.counter == 0 { |
1286 | Action::Jump(BlockDone) |
1287 | } else if out_buf.bytes_left() == 0 { |
1288 | Action::End(TINFLStatus::HasMoreOutput) |
1289 | } else { |
1290 | Action::Jump(RawMemcpy2) |
1291 | } |
1292 | }), |
1293 | |
1294 | RawMemcpy2 => generate_state!(state, 'state_machine, { |
1295 | if in_iter.len() > 0 { |
1296 | // Copy as many raw bytes as possible from the input to the output using memcpy. |
1297 | // Raw block lengths are limited to 64 * 1024, so casting through usize and u32 |
1298 | // is not an issue. |
1299 | let space_left = out_buf.bytes_left(); |
1300 | let bytes_to_copy = cmp::min(cmp::min( |
1301 | space_left, |
1302 | in_iter.len()), |
1303 | l.counter as usize |
1304 | ); |
1305 | |
1306 | out_buf.write_slice(&in_iter.as_slice()[..bytes_to_copy]); |
1307 | |
1308 | (&mut in_iter).nth(bytes_to_copy - 1); |
1309 | l.counter -= bytes_to_copy as u32; |
1310 | Action::Jump(RawMemcpy1) |
1311 | } else { |
1312 | end_of_input(flags) |
1313 | } |
1314 | }), |
1315 | |
1316 | // Read how many huffman codes/symbols are used for each table. |
1317 | ReadTableSizes => generate_state!(state, 'state_machine, { |
1318 | if l.counter < 3 { |
1319 | let num_bits = [5, 5, 4][l.counter as usize]; |
1320 | read_bits(&mut l, num_bits, &mut in_iter, flags, |l, bits| { |
1321 | r.table_sizes[l.counter as usize] = |
1322 | bits as u32 + u32::from(MIN_TABLE_SIZES[l.counter as usize]); |
1323 | l.counter += 1; |
1324 | Action::None |
1325 | }) |
1326 | } else { |
1327 | memset(&mut r.tables[HUFFLEN_TABLE].code_size[..], 0); |
1328 | l.counter = 0; |
1329 | // Check that the litlen and distance are within spec. |
1330 | // litlen table should be <=286 acc to the RFC and |
1331 | // additionally zlib rejects dist table sizes larger than 30. |
1332 | // NOTE this the final sizes after adding back predefined values, not |
1333 | // raw value in the data. |
1334 | // See miniz_oxide issue #130 and https://github.com/madler/zlib/issues/82. |
1335 | if r.table_sizes[LITLEN_TABLE] <= 286 && r.table_sizes[DIST_TABLE] <= 30 { |
1336 | Action::Jump(ReadHufflenTableCodeSize) |
1337 | } |
1338 | else { |
1339 | Action::Jump(BadDistOrLiteralTableLength) |
1340 | } |
1341 | } |
1342 | }), |
1343 | |
1344 | // Read the 3-bit lengths of the huffman codes describing the huffman code lengths used |
1345 | // to decode the lengths of the main tables. |
1346 | ReadHufflenTableCodeSize => generate_state!(state, 'state_machine, { |
1347 | if l.counter < r.table_sizes[HUFFLEN_TABLE] { |
1348 | read_bits(&mut l, 3, &mut in_iter, flags, |l, bits| { |
1349 | // These lengths are not stored in a normal ascending order, but rather one |
1350 | // specified by the deflate specification intended to put the most used |
1351 | // values at the front as trailing zero lengths do not have to be stored. |
1352 | r.tables[HUFFLEN_TABLE] |
1353 | .code_size[HUFFMAN_LENGTH_ORDER[l.counter as usize] as usize] = |
1354 | bits as u8; |
1355 | l.counter += 1; |
1356 | Action::None |
1357 | }) |
1358 | } else { |
1359 | r.table_sizes[HUFFLEN_TABLE] = 19; |
1360 | init_tree(r, &mut l) |
1361 | } |
1362 | }), |
1363 | |
1364 | ReadLitlenDistTablesCodeSize => generate_state!(state, 'state_machine, { |
1365 | if l.counter < r.table_sizes[LITLEN_TABLE] + r.table_sizes[DIST_TABLE] { |
1366 | decode_huffman_code( |
1367 | r, &mut l, HUFFLEN_TABLE, |
1368 | flags, &mut in_iter, |r, l, symbol| { |
1369 | l.dist = symbol as u32; |
1370 | if l.dist < 16 { |
1371 | r.len_codes[l.counter as usize] = l.dist as u8; |
1372 | l.counter += 1; |
1373 | Action::None |
1374 | } else if l.dist == 16 && l.counter == 0 { |
1375 | Action::Jump(BadCodeSizeDistPrevLookup) |
1376 | } else { |
1377 | l.num_extra = [2, 3, 7][l.dist as usize - 16]; |
1378 | Action::Jump(ReadExtraBitsCodeSize) |
1379 | } |
1380 | } |
1381 | ) |
1382 | } else if l.counter != r.table_sizes[LITLEN_TABLE] + r.table_sizes[DIST_TABLE] { |
1383 | Action::Jump(BadCodeSizeSum) |
1384 | } else { |
1385 | r.tables[LITLEN_TABLE].code_size[..r.table_sizes[LITLEN_TABLE] as usize] |
1386 | .copy_from_slice(&r.len_codes[..r.table_sizes[LITLEN_TABLE] as usize]); |
1387 | |
1388 | let dist_table_start = r.table_sizes[LITLEN_TABLE] as usize; |
1389 | let dist_table_end = (r.table_sizes[LITLEN_TABLE] + |
1390 | r.table_sizes[DIST_TABLE]) as usize; |
1391 | r.tables[DIST_TABLE].code_size[..r.table_sizes[DIST_TABLE] as usize] |
1392 | .copy_from_slice(&r.len_codes[dist_table_start..dist_table_end]); |
1393 | |
1394 | r.block_type -= 1; |
1395 | init_tree(r, &mut l) |
1396 | } |
1397 | }), |
1398 | |
1399 | ReadExtraBitsCodeSize => generate_state!(state, 'state_machine, { |
1400 | let num_extra = l.num_extra; |
1401 | read_bits(&mut l, num_extra, &mut in_iter, flags, |l, mut extra_bits| { |
1402 | // Mask to avoid a bounds check. |
1403 | extra_bits += [3, 3, 11][(l.dist as usize - 16) & 3]; |
1404 | let val = if l.dist == 16 { |
1405 | r.len_codes[l.counter as usize - 1] |
1406 | } else { |
1407 | 0 |
1408 | }; |
1409 | |
1410 | memset( |
1411 | &mut r.len_codes[ |
1412 | l.counter as usize..l.counter as usize + extra_bits as usize |
1413 | ], |
1414 | val, |
1415 | ); |
1416 | l.counter += extra_bits as u32; |
1417 | Action::Jump(ReadLitlenDistTablesCodeSize) |
1418 | }) |
1419 | }), |
1420 | |
1421 | DecodeLitlen => generate_state!(state, 'state_machine, { |
1422 | if in_iter.len() < 4 || out_buf.bytes_left() < 2 { |
1423 | // See if we can decode a literal with the data we have left. |
1424 | // Jumps to next state (WriteSymbol) if successful. |
1425 | decode_huffman_code( |
1426 | r, |
1427 | &mut l, |
1428 | LITLEN_TABLE, |
1429 | flags, |
1430 | &mut in_iter, |
1431 | |_r, l, symbol| { |
1432 | l.counter = symbol as u32; |
1433 | Action::Jump(WriteSymbol) |
1434 | }, |
1435 | ) |
1436 | } else if |
1437 | // If there is enough space, use the fast inner decompression |
1438 | // function. |
1439 | out_buf.bytes_left() >= 259 && |
1440 | in_iter.len() >= 14 |
1441 | { |
1442 | let (status, new_state) = decompress_fast( |
1443 | r, |
1444 | &mut in_iter, |
1445 | &mut out_buf, |
1446 | flags, |
1447 | &mut l, |
1448 | out_buf_size_mask, |
1449 | ); |
1450 | |
1451 | state = new_state; |
1452 | if status == TINFLStatus::Done { |
1453 | Action::Jump(new_state) |
1454 | } else { |
1455 | Action::End(status) |
1456 | } |
1457 | } else { |
1458 | fill_bit_buffer(&mut l, &mut in_iter); |
1459 | |
1460 | if let Some((symbol, code_len)) = r.tables[LITLEN_TABLE].lookup(l.bit_buf) { |
1461 | |
1462 | l.counter = symbol as u32; |
1463 | l.bit_buf >>= code_len; |
1464 | l.num_bits -= code_len; |
1465 | |
1466 | if (l.counter & 256) != 0 { |
1467 | // The symbol is not a literal. |
1468 | Action::Jump(HuffDecodeOuterLoop1) |
1469 | } else { |
1470 | // If we have a 32-bit buffer we need to read another two bytes now |
1471 | // to have enough bits to keep going. |
1472 | if cfg!(not(target_pointer_width = "64" )) { |
1473 | fill_bit_buffer(&mut l, &mut in_iter); |
1474 | } |
1475 | |
1476 | if let Some((symbol, code_len)) = r.tables[LITLEN_TABLE].lookup(l.bit_buf) { |
1477 | |
1478 | l.bit_buf >>= code_len; |
1479 | l.num_bits -= code_len; |
1480 | // The previous symbol was a literal, so write it directly and check |
1481 | // the next one. |
1482 | out_buf.write_byte(l.counter as u8); |
1483 | if (symbol & 256) != 0 { |
1484 | l.counter = symbol as u32; |
1485 | // The symbol is a length value. |
1486 | Action::Jump(HuffDecodeOuterLoop1) |
1487 | } else { |
1488 | // The symbol is a literal, so write it directly and continue. |
1489 | out_buf.write_byte(symbol as u8); |
1490 | Action::None |
1491 | } |
1492 | } else { |
1493 | Action::Jump(InvalidCodeLen) |
1494 | } |
1495 | } |
1496 | } else { |
1497 | Action::Jump(InvalidCodeLen) |
1498 | } |
1499 | } |
1500 | }), |
1501 | |
1502 | WriteSymbol => generate_state!(state, 'state_machine, { |
1503 | if l.counter >= 256 { |
1504 | Action::Jump(HuffDecodeOuterLoop1) |
1505 | } else if out_buf.bytes_left() > 0 { |
1506 | out_buf.write_byte(l.counter as u8); |
1507 | Action::Jump(DecodeLitlen) |
1508 | } else { |
1509 | Action::End(TINFLStatus::HasMoreOutput) |
1510 | } |
1511 | }), |
1512 | |
1513 | HuffDecodeOuterLoop1 => generate_state!(state, 'state_machine, { |
1514 | // Mask the top bits since they may contain length info. |
1515 | l.counter &= 511; |
1516 | |
1517 | if l.counter |
1518 | == 256 { |
1519 | // We hit the end of block symbol. |
1520 | Action::Jump(BlockDone) |
1521 | } else if l.counter > 285 { |
1522 | // Invalid code. |
1523 | // We already verified earlier that the code is > 256. |
1524 | Action::Jump(InvalidLitlen) |
1525 | } else { |
1526 | // # Optimization |
1527 | // Mask the value to avoid bounds checks |
1528 | // We could use get_unchecked later if can statically verify that |
1529 | // this will never go out of bounds. |
1530 | l.num_extra = |
1531 | u32::from(LENGTH_EXTRA[(l.counter - 257) as usize & BASE_EXTRA_MASK]); |
1532 | l.counter = u32::from(LENGTH_BASE[(l.counter - 257) as usize & BASE_EXTRA_MASK]); |
1533 | // Length and distance codes have a number of extra bits depending on |
1534 | // the base, which together with the base gives us the exact value. |
1535 | if l.num_extra != 0 { |
1536 | Action::Jump(ReadExtraBitsLitlen) |
1537 | } else { |
1538 | Action::Jump(DecodeDistance) |
1539 | } |
1540 | } |
1541 | }), |
1542 | |
1543 | ReadExtraBitsLitlen => generate_state!(state, 'state_machine, { |
1544 | let num_extra = l.num_extra; |
1545 | read_bits(&mut l, num_extra, &mut in_iter, flags, |l, extra_bits| { |
1546 | l.counter += extra_bits as u32; |
1547 | Action::Jump(DecodeDistance) |
1548 | }) |
1549 | }), |
1550 | |
1551 | DecodeDistance => generate_state!(state, 'state_machine, { |
1552 | // Try to read a huffman code from the input buffer and look up what |
1553 | // length code the decoded symbol refers to. |
1554 | decode_huffman_code(r, &mut l, DIST_TABLE, flags, &mut in_iter, |_r, l, symbol| { |
1555 | if symbol > 29 { |
1556 | // Invalid distance code. |
1557 | return Action::Jump(InvalidDist) |
1558 | } |
1559 | // # Optimization |
1560 | // Mask the value to avoid bounds checks |
1561 | // We could use get_unchecked later if can statically verify that |
1562 | // this will never go out of bounds. |
1563 | l.num_extra = u32::from(DIST_EXTRA[symbol as usize & BASE_EXTRA_MASK]); |
1564 | l.dist = u32::from(DIST_BASE[symbol as usize & BASE_EXTRA_MASK]); |
1565 | if l.num_extra != 0 { |
1566 | // ReadEXTRA_BITS_DISTACNE |
1567 | Action::Jump(ReadExtraBitsDistance) |
1568 | } else { |
1569 | Action::Jump(HuffDecodeOuterLoop2) |
1570 | } |
1571 | }) |
1572 | }), |
1573 | |
1574 | ReadExtraBitsDistance => generate_state!(state, 'state_machine, { |
1575 | let num_extra = l.num_extra; |
1576 | read_bits(&mut l, num_extra, &mut in_iter, flags, |l, extra_bits| { |
1577 | l.dist += extra_bits as u32; |
1578 | Action::Jump(HuffDecodeOuterLoop2) |
1579 | }) |
1580 | }), |
1581 | |
1582 | HuffDecodeOuterLoop2 => generate_state!(state, 'state_machine, { |
1583 | if l.dist as usize > out_buf.position() && |
1584 | (flags & TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF != 0) |
1585 | { |
1586 | // We encountered a distance that refers a position before |
1587 | // the start of the decoded data, so we can't continue. |
1588 | Action::Jump(DistanceOutOfBounds) |
1589 | } else { |
1590 | let out_pos = out_buf.position(); |
1591 | let source_pos = out_buf.position() |
1592 | .wrapping_sub(l.dist as usize) & out_buf_size_mask; |
1593 | |
1594 | let out_len = out_buf.get_ref().len() as usize; |
1595 | let match_end_pos = out_buf.position() + l.counter as usize; |
1596 | |
1597 | if match_end_pos > out_len || |
1598 | // miniz doesn't do this check here. Not sure how it makes sure |
1599 | // that this case doesn't happen. |
1600 | (source_pos >= out_pos && (source_pos - out_pos) < l.counter as usize) |
1601 | { |
1602 | // Not enough space for all of the data in the output buffer, |
1603 | // so copy what we have space for. |
1604 | if l.counter == 0 { |
1605 | Action::Jump(DecodeLitlen) |
1606 | } else { |
1607 | Action::Jump(WriteLenBytesToEnd) |
1608 | } |
1609 | } else { |
1610 | apply_match( |
1611 | out_buf.get_mut(), |
1612 | out_pos, |
1613 | l.dist as usize, |
1614 | l.counter as usize, |
1615 | out_buf_size_mask |
1616 | ); |
1617 | out_buf.set_position(out_pos + l.counter as usize); |
1618 | Action::Jump(DecodeLitlen) |
1619 | } |
1620 | } |
1621 | }), |
1622 | |
1623 | WriteLenBytesToEnd => generate_state!(state, 'state_machine, { |
1624 | if out_buf.bytes_left() > 0 { |
1625 | let out_pos = out_buf.position(); |
1626 | let source_pos = out_buf.position() |
1627 | .wrapping_sub(l.dist as usize) & out_buf_size_mask; |
1628 | |
1629 | |
1630 | let len = cmp::min(out_buf.bytes_left(), l.counter as usize); |
1631 | |
1632 | transfer(out_buf.get_mut(), source_pos, out_pos, len, out_buf_size_mask); |
1633 | |
1634 | out_buf.set_position(out_pos + len); |
1635 | l.counter -= len as u32; |
1636 | if l.counter == 0 { |
1637 | Action::Jump(DecodeLitlen) |
1638 | } else { |
1639 | Action::None |
1640 | } |
1641 | } else { |
1642 | Action::End(TINFLStatus::HasMoreOutput) |
1643 | } |
1644 | }), |
1645 | |
1646 | BlockDone => generate_state!(state, 'state_machine, { |
1647 | // End once we've read the last block. |
1648 | if r.finish != 0 { |
1649 | pad_to_bytes(&mut l, &mut in_iter, flags, |_| Action::None); |
1650 | |
1651 | let in_consumed = in_buf.len() - in_iter.len(); |
1652 | let undo = undo_bytes(&mut l, in_consumed as u32) as usize; |
1653 | in_iter = in_buf[in_consumed - undo..].iter(); |
1654 | |
1655 | l.bit_buf &= ((1 as BitBuffer) << l.num_bits) - 1; |
1656 | debug_assert_eq!(l.num_bits, 0); |
1657 | |
1658 | if flags & TINFL_FLAG_PARSE_ZLIB_HEADER != 0 { |
1659 | l.counter = 0; |
1660 | Action::Jump(ReadAdler32) |
1661 | } else { |
1662 | Action::Jump(DoneForever) |
1663 | } |
1664 | } else { |
1665 | Action::Jump(ReadBlockHeader) |
1666 | } |
1667 | }), |
1668 | |
1669 | ReadAdler32 => generate_state!(state, 'state_machine, { |
1670 | if l.counter < 4 { |
1671 | if l.num_bits != 0 { |
1672 | read_bits(&mut l, 8, &mut in_iter, flags, |l, bits| { |
1673 | r.z_adler32 <<= 8; |
1674 | r.z_adler32 |= bits as u32; |
1675 | l.counter += 1; |
1676 | Action::None |
1677 | }) |
1678 | } else { |
1679 | read_byte(&mut in_iter, flags, |byte| { |
1680 | r.z_adler32 <<= 8; |
1681 | r.z_adler32 |= u32::from(byte); |
1682 | l.counter += 1; |
1683 | Action::None |
1684 | }) |
1685 | } |
1686 | } else { |
1687 | Action::Jump(DoneForever) |
1688 | } |
1689 | }), |
1690 | |
1691 | // We are done. |
1692 | DoneForever => break TINFLStatus::Done, |
1693 | |
1694 | // Anything else indicates failure. |
1695 | // BadZlibHeader | BadRawLength | BadDistOrLiteralTableLength | BlockTypeUnexpected | |
1696 | // DistanceOutOfBounds | |
1697 | // BadTotalSymbols | BadCodeSizeDistPrevLookup | BadCodeSizeSum | InvalidLitlen | |
1698 | // InvalidDist | InvalidCodeLen |
1699 | _ => break TINFLStatus::Failed, |
1700 | }; |
1701 | }; |
1702 | |
1703 | let in_undo = if status != TINFLStatus::NeedsMoreInput |
1704 | && status != TINFLStatus::FailedCannotMakeProgress |
1705 | { |
1706 | undo_bytes(&mut l, (in_buf.len() - in_iter.len()) as u32) as usize |
1707 | } else { |
1708 | 0 |
1709 | }; |
1710 | |
1711 | // Make sure HasMoreOutput overrides NeedsMoreInput if the output buffer is full. |
1712 | // (Unless the missing input is the adler32 value in which case we don't need to write anything.) |
1713 | // TODO: May want to see if we can do this in a better way. |
1714 | if status == TINFLStatus::NeedsMoreInput |
1715 | && out_buf.bytes_left() == 0 |
1716 | && state != State::ReadAdler32 |
1717 | { |
1718 | status = TINFLStatus::HasMoreOutput |
1719 | } |
1720 | |
1721 | r.state = state; |
1722 | r.bit_buf = l.bit_buf; |
1723 | r.num_bits = l.num_bits; |
1724 | r.dist = l.dist; |
1725 | r.counter = l.counter; |
1726 | r.num_extra = l.num_extra; |
1727 | |
1728 | r.bit_buf &= ((1 as BitBuffer) << r.num_bits) - 1; |
1729 | |
1730 | // If this is a zlib stream, and update the adler32 checksum with the decompressed bytes if |
1731 | // requested. |
1732 | let need_adler = if (flags & TINFL_FLAG_IGNORE_ADLER32) == 0 { |
1733 | flags & (TINFL_FLAG_PARSE_ZLIB_HEADER | TINFL_FLAG_COMPUTE_ADLER32) != 0 |
1734 | } else { |
1735 | // If TINFL_FLAG_IGNORE_ADLER32 is enabled, ignore the checksum. |
1736 | false |
1737 | }; |
1738 | if need_adler && status as i32 >= 0 { |
1739 | let out_buf_pos = out_buf.position(); |
1740 | r.check_adler32 = update_adler32(r.check_adler32, &out_buf.get_ref()[out_pos..out_buf_pos]); |
1741 | |
1742 | // disabled so that random input from fuzzer would not be rejected early, |
1743 | // before it has a chance to reach interesting parts of code |
1744 | if !cfg!(fuzzing) { |
1745 | // Once we are done, check if the checksum matches with the one provided in the zlib header. |
1746 | if status == TINFLStatus::Done |
1747 | && flags & TINFL_FLAG_PARSE_ZLIB_HEADER != 0 |
1748 | && r.check_adler32 != r.z_adler32 |
1749 | { |
1750 | status = TINFLStatus::Adler32Mismatch; |
1751 | } |
1752 | } |
1753 | } |
1754 | |
1755 | ( |
1756 | status, |
1757 | in_buf.len() - in_iter.len() - in_undo, |
1758 | out_buf.position() - out_pos, |
1759 | ) |
1760 | } |
1761 | |
1762 | #[cfg (test)] |
1763 | mod test { |
1764 | use super::*; |
1765 | |
1766 | //TODO: Fix these. |
1767 | |
1768 | fn tinfl_decompress_oxide<'i>( |
1769 | r: &mut DecompressorOxide, |
1770 | input_buffer: &'i [u8], |
1771 | output_buffer: &mut [u8], |
1772 | flags: u32, |
1773 | ) -> (TINFLStatus, &'i [u8], usize) { |
1774 | let (status, in_pos, out_pos) = decompress(r, input_buffer, output_buffer, 0, flags); |
1775 | (status, &input_buffer[in_pos..], out_pos) |
1776 | } |
1777 | |
1778 | #[test ] |
1779 | fn decompress_zlib() { |
1780 | let encoded = [ |
1781 | 120, 156, 243, 72, 205, 201, 201, 215, 81, 168, 202, 201, 76, 82, 4, 0, 27, 101, 4, 19, |
1782 | ]; |
1783 | let flags = TINFL_FLAG_COMPUTE_ADLER32 | TINFL_FLAG_PARSE_ZLIB_HEADER; |
1784 | |
1785 | let mut b = DecompressorOxide::new(); |
1786 | const LEN: usize = 32; |
1787 | let mut b_buf = vec![0; LEN]; |
1788 | |
1789 | // This should fail with the out buffer being to small. |
1790 | let b_status = tinfl_decompress_oxide(&mut b, &encoded[..], b_buf.as_mut_slice(), flags); |
1791 | |
1792 | assert_eq!(b_status.0, TINFLStatus::Failed); |
1793 | |
1794 | let flags = flags | TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF; |
1795 | |
1796 | b = DecompressorOxide::new(); |
1797 | |
1798 | // With TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF set this should no longer fail. |
1799 | let b_status = tinfl_decompress_oxide(&mut b, &encoded[..], b_buf.as_mut_slice(), flags); |
1800 | |
1801 | assert_eq!(b_buf[..b_status.2], b"Hello, zlib!" [..]); |
1802 | assert_eq!(b_status.0, TINFLStatus::Done); |
1803 | } |
1804 | |
1805 | #[test ] |
1806 | fn raw_block() { |
1807 | const LEN: usize = 64; |
1808 | |
1809 | let text = b"Hello, zlib!" ; |
1810 | let encoded = { |
1811 | let len = text.len(); |
1812 | let notlen = !len; |
1813 | let mut encoded = vec![ |
1814 | 1, |
1815 | len as u8, |
1816 | (len >> 8) as u8, |
1817 | notlen as u8, |
1818 | (notlen >> 8) as u8, |
1819 | ]; |
1820 | encoded.extend_from_slice(&text[..]); |
1821 | encoded |
1822 | }; |
1823 | |
1824 | //let flags = TINFL_FLAG_COMPUTE_ADLER32 | TINFL_FLAG_PARSE_ZLIB_HEADER | |
1825 | let flags = TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF; |
1826 | |
1827 | let mut b = DecompressorOxide::new(); |
1828 | |
1829 | let mut b_buf = vec![0; LEN]; |
1830 | |
1831 | let b_status = tinfl_decompress_oxide(&mut b, &encoded[..], b_buf.as_mut_slice(), flags); |
1832 | assert_eq!(b_buf[..b_status.2], text[..]); |
1833 | assert_eq!(b_status.0, TINFLStatus::Done); |
1834 | } |
1835 | |
1836 | fn masked_lookup(table: &HuffmanTable, bit_buf: BitBuffer) -> (i32, u32) { |
1837 | let ret = table.lookup(bit_buf).unwrap(); |
1838 | (ret.0 & 511, ret.1) |
1839 | } |
1840 | |
1841 | #[test ] |
1842 | fn fixed_table_lookup() { |
1843 | let mut d = DecompressorOxide::new(); |
1844 | d.block_type = 1; |
1845 | start_static_table(&mut d); |
1846 | let mut l = LocalVars { |
1847 | bit_buf: d.bit_buf, |
1848 | num_bits: d.num_bits, |
1849 | dist: d.dist, |
1850 | counter: d.counter, |
1851 | num_extra: d.num_extra, |
1852 | }; |
1853 | init_tree(&mut d, &mut l); |
1854 | let llt = &d.tables[LITLEN_TABLE]; |
1855 | let dt = &d.tables[DIST_TABLE]; |
1856 | assert_eq!(masked_lookup(llt, 0b00001100), (0, 8)); |
1857 | assert_eq!(masked_lookup(llt, 0b00011110), (72, 8)); |
1858 | assert_eq!(masked_lookup(llt, 0b01011110), (74, 8)); |
1859 | assert_eq!(masked_lookup(llt, 0b11111101), (143, 8)); |
1860 | assert_eq!(masked_lookup(llt, 0b000010011), (144, 9)); |
1861 | assert_eq!(masked_lookup(llt, 0b111111111), (255, 9)); |
1862 | assert_eq!(masked_lookup(llt, 0b00000000), (256, 7)); |
1863 | assert_eq!(masked_lookup(llt, 0b1110100), (279, 7)); |
1864 | assert_eq!(masked_lookup(llt, 0b00000011), (280, 8)); |
1865 | assert_eq!(masked_lookup(llt, 0b11100011), (287, 8)); |
1866 | |
1867 | assert_eq!(masked_lookup(dt, 0), (0, 5)); |
1868 | assert_eq!(masked_lookup(dt, 20), (5, 5)); |
1869 | } |
1870 | |
1871 | fn check_result(input: &[u8], expected_status: TINFLStatus, expected_state: State, zlib: bool) { |
1872 | let mut r = DecompressorOxide::default(); |
1873 | let mut output_buf = vec![0; 1024 * 32]; |
1874 | let flags = if zlib { |
1875 | inflate_flags::TINFL_FLAG_PARSE_ZLIB_HEADER |
1876 | } else { |
1877 | 0 |
1878 | } | TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF |
1879 | | TINFL_FLAG_HAS_MORE_INPUT; |
1880 | let (d_status, _in_bytes, _out_bytes) = |
1881 | decompress(&mut r, input, &mut output_buf, 0, flags); |
1882 | assert_eq!(expected_status, d_status); |
1883 | assert_eq!(expected_state, r.state); |
1884 | } |
1885 | |
1886 | #[test ] |
1887 | fn bogus_input() { |
1888 | use self::check_result as cr; |
1889 | const F: TINFLStatus = TINFLStatus::Failed; |
1890 | const OK: TINFLStatus = TINFLStatus::Done; |
1891 | // Bad CM. |
1892 | cr(&[0x77, 0x85], F, State::BadZlibHeader, true); |
1893 | // Bad window size (but check is correct). |
1894 | cr(&[0x88, 0x98], F, State::BadZlibHeader, true); |
1895 | // Bad check bits. |
1896 | cr(&[0x78, 0x98], F, State::BadZlibHeader, true); |
1897 | |
1898 | // Too many code lengths. (From inflate library issues) |
1899 | cr( |
1900 | b"M \xff\xffM* \xad\xad\xad\xad\xad\xad\xad\xcd\xcd\xcdM" , |
1901 | F, |
1902 | State::BadDistOrLiteralTableLength, |
1903 | false, |
1904 | ); |
1905 | |
1906 | // Bad CLEN (also from inflate library issues) |
1907 | cr( |
1908 | b" \xdd\xff\xff*M \x94ffffffffff" , |
1909 | F, |
1910 | State::BadDistOrLiteralTableLength, |
1911 | false, |
1912 | ); |
1913 | |
1914 | // Port of inflate coverage tests from zlib-ng |
1915 | // https://github.com/Dead2/zlib-ng/blob/develop/test/infcover.c |
1916 | let c = |a, b, c| cr(a, b, c, false); |
1917 | |
1918 | // Invalid uncompressed/raw block length. |
1919 | c(&[0, 0, 0, 0, 0], F, State::BadRawLength); |
1920 | // Ok empty uncompressed block. |
1921 | c(&[3, 0], OK, State::DoneForever); |
1922 | // Invalid block type. |
1923 | c(&[6], F, State::BlockTypeUnexpected); |
1924 | // Ok uncompressed block. |
1925 | c(&[1, 1, 0, 0xfe, 0xff, 0], OK, State::DoneForever); |
1926 | // Too many litlens, we handle this later than zlib, so this test won't |
1927 | // give the same result. |
1928 | // c(&[0xfc, 0, 0], F, State::BadTotalSymbols); |
1929 | // Invalid set of code lengths - TODO Check if this is the correct error for this. |
1930 | c(&[4, 0, 0xfe, 0xff], F, State::BadTotalSymbols); |
1931 | // Invalid repeat in list of code lengths. |
1932 | // (Try to repeat a non-existent code.) |
1933 | c(&[4, 0, 0x24, 0x49, 0], F, State::BadCodeSizeDistPrevLookup); |
1934 | // Missing end of block code (should we have a separate error for this?) - fails on further input |
1935 | // c(&[4, 0, 0x24, 0xe9, 0xff, 0x6d], F, State::BadTotalSymbols); |
1936 | // Invalid set of literals/lengths |
1937 | c( |
1938 | &[ |
1939 | 4, 0x80, 0x49, 0x92, 0x24, 0x49, 0x92, 0x24, 0x71, 0xff, 0xff, 0x93, 0x11, 0, |
1940 | ], |
1941 | F, |
1942 | State::BadTotalSymbols, |
1943 | ); |
1944 | // Invalid set of distances _ needsmoreinput |
1945 | // c(&[4, 0x80, 0x49, 0x92, 0x24, 0x49, 0x92, 0x24, 0x0f, 0xb4, 0xff, 0xff, 0xc3, 0x84], F, State::BadTotalSymbols); |
1946 | // Invalid distance code |
1947 | c(&[2, 0x7e, 0xff, 0xff], F, State::InvalidDist); |
1948 | |
1949 | // Distance refers to position before the start |
1950 | c( |
1951 | &[0x0c, 0xc0, 0x81, 0, 0, 0, 0, 0, 0x90, 0xff, 0x6b, 0x4, 0], |
1952 | F, |
1953 | State::DistanceOutOfBounds, |
1954 | ); |
1955 | |
1956 | // Trailer |
1957 | // Bad gzip trailer checksum GZip header not handled by miniz_oxide |
1958 | //cr(&[0x1f, 0x8b, 0x08 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0x03, 0, 0, 0, 0, 0x01], F, State::BadCRC, false) |
1959 | // Bad gzip trailer length |
1960 | //cr(&[0x1f, 0x8b, 0x08 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0x03, 0, 0, 0, 0, 0, 0, 0, 0, 0x01], F, State::BadCRC, false) |
1961 | } |
1962 | |
1963 | #[test ] |
1964 | fn empty_output_buffer_non_wrapping() { |
1965 | let encoded = [ |
1966 | 120, 156, 243, 72, 205, 201, 201, 215, 81, 168, 202, 201, 76, 82, 4, 0, 27, 101, 4, 19, |
1967 | ]; |
1968 | let flags = TINFL_FLAG_COMPUTE_ADLER32 |
1969 | | TINFL_FLAG_PARSE_ZLIB_HEADER |
1970 | | TINFL_FLAG_USING_NON_WRAPPING_OUTPUT_BUF; |
1971 | let mut r = DecompressorOxide::new(); |
1972 | let mut output_buf = vec![]; |
1973 | // Check that we handle an empty buffer properly and not panicking. |
1974 | // https://github.com/Frommi/miniz_oxide/issues/23 |
1975 | let res = decompress(&mut r, &encoded, &mut output_buf, 0, flags); |
1976 | assert_eq!(res, (TINFLStatus::HasMoreOutput, 4, 0)); |
1977 | } |
1978 | |
1979 | #[test ] |
1980 | fn empty_output_buffer_wrapping() { |
1981 | let encoded = [ |
1982 | 0x73, 0x49, 0x4d, 0xcb, 0x49, 0x2c, 0x49, 0x55, 0x00, 0x11, 0x00, |
1983 | ]; |
1984 | let flags = TINFL_FLAG_COMPUTE_ADLER32; |
1985 | let mut r = DecompressorOxide::new(); |
1986 | let mut output_buf = vec![]; |
1987 | // Check that we handle an empty buffer properly and not panicking. |
1988 | // https://github.com/Frommi/miniz_oxide/issues/23 |
1989 | let res = decompress(&mut r, &encoded, &mut output_buf, 0, flags); |
1990 | assert_eq!(res, (TINFLStatus::HasMoreOutput, 2, 0)); |
1991 | } |
1992 | } |
1993 | |