]>
Commit | Line | Data |
---|---|---|
1 | //! Deflate format (RFC 1951) support. | |
2 | //! | |
3 | //! This module provides functionality for decompressing raw deflated streams via [`Inflate`] and gzip files (RFC 1952) via [`gzip_decode`]. | |
4 | //! | |
5 | //! [`Inflate`]: ./struct.Inflate.html | |
6 | //! [`gzip_decode`]: ./fn.gzip_decode.html | |
7 | //! | |
8 | //! # Examples | |
9 | //! | |
10 | //! Decompressing full input buffer into sufficiently large output buffer: | |
11 | //! ``` | |
12 | //! # use nihav_core::compr::DecompressError; | |
13 | //! use nihav_core::compr::deflate::Inflate; | |
14 | //! | |
15 | //! # fn decompress(input: &[u8]) -> Result<(), DecompressError> { | |
16 | //! # let mut output_buffer = [0u8; 16]; | |
17 | //! let output_length = Inflate::uncompress(input, &mut output_buffer)?; | |
18 | //! # Ok(()) | |
19 | //! # } | |
20 | //! ``` | |
21 | //! | |
22 | //! Decompressing input chunks into portions of output: | |
23 | //! ``` | |
24 | //! use nihav_core::compr::DecompressError; | |
25 | //! use nihav_core::compr::deflate::Inflate; | |
26 | //! | |
27 | //! # fn decompress(input_data: &[u8]) -> Result<(), DecompressError> { | |
28 | //! let mut inflate = Inflate::new(); | |
29 | //! let mut dst_buf: Vec<u8> = Vec::new(); | |
30 | //! let mut output_chunk = [0u8; 1024]; | |
31 | //! for src in input_data.chunks(512) { | |
32 | //! let mut repeat = false; | |
33 | //! loop { | |
34 | //! let ret = inflate.decompress_data(src, &mut output_chunk, repeat); | |
35 | //! match ret { | |
36 | //! Ok(len) => { // we got a buffer decoded successfully to the end | |
37 | //! dst_buf.extend_from_slice(&output_chunk[..len]); | |
38 | //! break; | |
39 | //! }, | |
40 | //! Err(DecompressError::ShortData) => { // this block of data was fully read | |
41 | //! break; | |
42 | //! }, | |
43 | //! Err(DecompressError::OutputFull) => { | |
44 | //! // the output buffer is full, flush it and continue decoding the same block | |
45 | //! repeat = true; | |
46 | //! dst_buf.extend_from_slice(&output_chunk); | |
47 | //! }, | |
48 | //! Err(err) => { | |
49 | //! return Err(err); | |
50 | //! }, | |
51 | //! } | |
52 | //! } | |
53 | //! } | |
54 | //! # Ok(()) | |
55 | //! # } | |
56 | //! ``` | |
57 | ||
58 | use crate::io::byteio::*; | |
59 | use crate::io::bitreader::*; | |
60 | use crate::io::codebook::*; | |
61 | use super::*; | |
62 | ||
63 | const NUM_LITERALS: usize = 287; | |
64 | const NUM_DISTS: usize = 32; | |
65 | ||
66 | struct FixedLenCodeReader {} | |
67 | ||
68 | impl CodebookDescReader<u16> for FixedLenCodeReader { | |
69 | fn bits(&mut self, idx: usize) -> u8 { | |
70 | if idx < 144 { 8 } | |
71 | else if idx < 256 { 9 } | |
72 | else if idx < 280 { 7 } | |
73 | else { 8 } | |
74 | } | |
75 | #[allow(clippy::identity_op)] | |
76 | fn code(&mut self, idx: usize) -> u32 { | |
77 | let base = idx as u32; | |
78 | let bits = self.bits(idx); | |
79 | if idx < 144 { reverse_bits(base + 0x30, bits) } | |
80 | else if idx < 256 { reverse_bits(base + 0x190 - 144, bits) } | |
81 | else if idx < 280 { reverse_bits(base + 0x000 - 256, bits) } | |
82 | else { reverse_bits(base + 0xC0 - 280, bits) } | |
83 | } | |
84 | fn sym (&mut self, idx: usize) -> u16 { idx as u16 } | |
85 | fn len(&mut self) -> usize { NUM_LITERALS + 1 } | |
86 | } | |
87 | ||
88 | #[derive(Clone,Copy,Default)] | |
89 | struct BitReaderState { | |
90 | pos: usize, | |
91 | bitbuf: u32, | |
92 | bits: u8, | |
93 | } | |
94 | ||
95 | struct CurrentSource<'a> { | |
96 | src: &'a [u8], | |
97 | br: BitReaderState, | |
98 | } | |
99 | ||
100 | impl<'a> CurrentSource<'a> { | |
101 | fn new(src: &'a [u8], br: BitReaderState) -> Self { | |
102 | let mut newsrc = Self { src, br }; | |
103 | newsrc.br.pos = 0; | |
104 | newsrc.refill(); | |
105 | newsrc | |
106 | } | |
107 | fn reinit(src: &'a [u8], br: BitReaderState) -> Self { | |
108 | let mut newsrc = Self { src, br }; | |
109 | newsrc.refill(); | |
110 | newsrc | |
111 | } | |
112 | fn refill(&mut self) { | |
113 | while (self.br.bits <= 24) && (self.br.pos < self.src.len()) { | |
114 | self.br.bitbuf |= u32::from(self.src[self.br.pos]) << self.br.bits; | |
115 | self.br.bits += 8; | |
116 | self.br.pos += 1; | |
117 | } | |
118 | } | |
119 | fn skip_cache(&mut self, nbits: u8) { | |
120 | self.br.bitbuf >>= nbits; | |
121 | self.br.bits -= nbits; | |
122 | } | |
123 | fn read(&mut self, nbits: u8) -> BitReaderResult<u32> { | |
124 | if nbits == 0 { return Ok(0); } | |
125 | if nbits > 16 { return Err(BitReaderError::TooManyBitsRequested); } | |
126 | if self.br.bits < nbits { | |
127 | self.refill(); | |
128 | if self.br.bits < nbits { return Err(BitReaderError::BitstreamEnd); } | |
129 | } | |
130 | let ret = self.br.bitbuf & ((1 << nbits) - 1); | |
131 | self.skip_cache(nbits); | |
132 | Ok(ret) | |
133 | } | |
134 | fn read_bool(&mut self) -> BitReaderResult<bool> { | |
135 | if self.br.bits == 0 { | |
136 | self.refill(); | |
137 | if self.br.bits == 0 { return Err(BitReaderError::BitstreamEnd); } | |
138 | } | |
139 | let ret = (self.br.bitbuf & 1) != 0; | |
140 | self.skip_cache(1); | |
141 | Ok(ret) | |
142 | } | |
143 | fn peek(&mut self, nbits: u8) -> u32 { | |
144 | if nbits == 0 || nbits > 16 { return 0; } | |
145 | if self.br.bits < nbits { | |
146 | self.refill(); | |
147 | } | |
148 | self.br.bitbuf & ((1 << nbits) - 1) | |
149 | } | |
150 | fn skip(&mut self, nbits: u32) -> BitReaderResult<()> { | |
151 | if u32::from(self.br.bits) >= nbits { | |
152 | self.skip_cache(nbits as u8); | |
153 | } else { | |
154 | unreachable!(); | |
155 | } | |
156 | Ok(()) | |
157 | } | |
158 | fn align(&mut self) { | |
159 | let b = self.br.bits & 7; | |
160 | if b != 0 { | |
161 | self.skip_cache(8 - (b as u8)); | |
162 | } | |
163 | } | |
164 | fn left(&self) -> isize { | |
165 | ((self.src.len() as isize) - (self.br.pos as isize)) * 8 + (self.br.bits as isize) | |
166 | } | |
167 | } | |
168 | ||
169 | impl<'a, S: Copy> CodebookReader<S> for CurrentSource<'a> { | |
170 | fn read_cb(&mut self, cb: &Codebook<S>) -> CodebookResult<S> { | |
171 | let mut esc = true; | |
172 | let mut idx = 0; | |
173 | let mut lut_bits = cb.lut_bits; | |
174 | let orig_br = self.br; | |
175 | while esc { | |
176 | let lut_idx = (self.peek(lut_bits) as usize) + (idx as usize); | |
177 | if cb.table[lut_idx] == TABLE_FILL_VALUE { return Err(CodebookError::InvalidCode); } | |
178 | let bits = cb.table[lut_idx] & 0x7F; | |
179 | esc = (cb.table[lut_idx] & 0x80) != 0; | |
180 | idx = (cb.table[lut_idx] >> 8) as usize; | |
181 | let skip_bits = if esc { u32::from(lut_bits) } else { bits }; | |
182 | if (skip_bits as isize) > self.left() { | |
183 | self.br = orig_br; | |
184 | self.refill(); | |
185 | return Err(CodebookError::MemoryError); | |
186 | } | |
187 | self.skip(skip_bits as u32).unwrap(); | |
188 | lut_bits = bits as u8; | |
189 | } | |
190 | Ok(cb.syms[idx]) | |
191 | } | |
192 | } | |
193 | ||
194 | enum InflateState { | |
195 | Start, | |
196 | BlockStart, | |
197 | BlockMode, | |
198 | StaticBlockLen, | |
199 | StaticBlockInvLen(u32), | |
200 | StaticBlockCopy(usize), | |
201 | FixedBlock, | |
202 | FixedBlockLengthExt(usize, u8), | |
203 | FixedBlockDist(usize), | |
204 | FixedBlockDistExt(usize, usize, u8), | |
205 | FixedBlockCopy(usize, usize), | |
206 | FixedBlockLiteral(u8), | |
207 | DynBlockHlit, | |
208 | DynBlockHdist, | |
209 | DynBlockHclen, | |
210 | DynLengths(usize), | |
211 | DynCodeLengths, | |
212 | DynCodeLengthsAdd(usize), | |
213 | DynBlock, | |
214 | DynBlockLengthExt(usize, u8), | |
215 | DynBlockDist(usize), | |
216 | DynBlockDistExt(usize, usize, u8), | |
217 | DynCopy(usize, usize), | |
218 | DynBlockLiteral(u8), | |
219 | End, | |
220 | } | |
221 | ||
222 | ///! The decompressor for deflated streams (RFC 1951). | |
223 | pub struct Inflate { | |
224 | br: BitReaderState, | |
225 | fix_len_cb: Codebook<u16>, | |
226 | ||
227 | buf: [u8; 65536], | |
228 | bpos: usize, | |
229 | output_idx: usize, | |
230 | ||
231 | state: InflateState, | |
232 | final_block: bool, | |
233 | hlit: usize, | |
234 | hdist: usize, | |
235 | dyn_len_cb: Option<Codebook<u32>>, | |
236 | dyn_lit_cb: Option<Codebook<u32>>, | |
237 | dyn_dist_cb: Option<Codebook<u32>>, | |
238 | len_lengths: [u8; 19], | |
239 | all_lengths: [u8; NUM_LITERALS + NUM_DISTS], | |
240 | cur_len_idx: usize, | |
241 | } | |
242 | ||
243 | const LENGTH_ADD_BITS: [u8; 29] = [ | |
244 | 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, | |
245 | 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, | |
246 | 4, 4, 4, 4, 5, 5, 5, 5, 0 | |
247 | ]; | |
248 | const LENGTH_BASE: [u16; 29] = [ | |
249 | 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, | |
250 | 15, 17, 19, 23, 27, 31, 35, 43, 51, 59, | |
251 | 67, 83, 99, 115, 131, 163, 195, 227, 258 | |
252 | ]; | |
253 | const DIST_ADD_BITS: [u8; 30] = [ | |
254 | 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, | |
255 | 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, | |
256 | 9, 9, 10, 10, 11, 11, 12, 12, 13, 13 | |
257 | ]; | |
258 | const DIST_BASE: [u16; 30] = [ | |
259 | 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, | |
260 | 33, 49, 65, 97, 129, 193, 257, 385, 513, 769, | |
261 | 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577 | |
262 | ]; | |
263 | const LEN_RECODE: [usize; 19] = [ | |
264 | 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 | |
265 | ]; | |
266 | const REPEAT_BITS: [u8; 3] = [ 2, 3, 7 ]; | |
267 | const REPEAT_BASE: [u8; 3] = [ 3, 3, 11 ]; | |
268 | ||
269 | macro_rules! read_bits { | |
270 | ($self: expr, $csrc: expr, $bits: expr) => ({ | |
271 | if $csrc.left() < $bits as isize { | |
272 | $self.br = $csrc.br; | |
273 | return Err(DecompressError::ShortData); | |
274 | } | |
275 | $csrc.read($bits).unwrap() | |
276 | }) | |
277 | } | |
278 | ||
279 | macro_rules! read_cb { | |
280 | ($self: expr, $csrc: expr, $cb: expr) => ({ | |
281 | let ret = $csrc.read_cb($cb); | |
282 | if let Err(CodebookError::MemoryError) = ret { | |
283 | $self.br = $csrc.br; | |
284 | return Err(DecompressError::ShortData); | |
285 | } | |
286 | match ret { | |
287 | Ok(val) => val, | |
288 | Err(_) => { | |
289 | $self.state = InflateState::End; | |
290 | return Err(DecompressError::InvalidData); | |
291 | }, | |
292 | } | |
293 | }) | |
294 | } | |
295 | ||
296 | impl Inflate { | |
297 | ///! Creates a new instance of `Inflate` struct. | |
298 | pub fn new() -> Self { | |
299 | let mut cr = FixedLenCodeReader {}; | |
300 | let fix_len_cb = Codebook::new(&mut cr, CodebookMode::LSB).unwrap(); | |
301 | Self { | |
302 | br: BitReaderState::default(), | |
303 | fix_len_cb, | |
304 | ||
305 | buf: [0; 65536], | |
306 | bpos: 0, | |
307 | output_idx: 0, | |
308 | ||
309 | state: InflateState::Start, | |
310 | final_block: false, | |
311 | dyn_len_cb: None, | |
312 | dyn_lit_cb: None, | |
313 | dyn_dist_cb: None, | |
314 | hlit: 0, | |
315 | hdist: 0, | |
316 | len_lengths: [0; 19], | |
317 | all_lengths: [0; NUM_LITERALS + NUM_DISTS], | |
318 | cur_len_idx: 0, | |
319 | } | |
320 | } | |
321 | fn put_literal(&mut self, val: u8) { | |
322 | self.buf[self.bpos] = val; | |
323 | self.bpos += 1; | |
324 | } | |
325 | fn lz_copy(&mut self, offset: usize, len: usize, dst: &mut [u8]) -> DecompressResult<()> { | |
326 | let mask = self.buf.len() - 1; | |
327 | if self.bpos < offset { | |
328 | return Err(DecompressError::InvalidData); | |
329 | } | |
330 | let cstart = (self.bpos - offset) & mask; | |
331 | for i in 0..len { | |
332 | self.buf[(self.bpos + i) & mask] = self.buf[(cstart + i) & mask]; | |
333 | dst[i] = self.buf[(cstart + i) & mask]; | |
334 | } | |
335 | self.bpos += len; | |
336 | Ok(()) | |
337 | } | |
338 | ///! Reports whether decoder has finished decoding the input. | |
339 | pub fn is_finished(&self) -> bool { | |
340 | match self.state { | |
341 | InflateState::End => true, | |
342 | _ => false, | |
343 | } | |
344 | } | |
345 | ///! Reports the current amount of bytes output into the destination buffer after the last run. | |
346 | pub fn get_current_output_size(&self) -> usize { self.output_idx } | |
347 | ///! Reports the total amount of bytes decoded so far. | |
348 | pub fn get_total_output_size(&self) -> usize { self.bpos } | |
349 | ///! Tries to decompress input data and write it to the output buffer. | |
350 | ///! | |
351 | ///! Since the decompressor can work with arbitrary input and output chunks its return value may have several meanings: | |
352 | ///! * `Ok(len)` means the stream has been fully decoded and then number of bytes output into the destination buffer is returned. | |
353 | ///! * [`DecompressError::ShortData`] means the input stream has been fully read but more data is needed. | |
354 | ///! * [`DecompressError::OutputFull`] means the output buffer is full and should be flushed. Then decoding should continue on the same input block with `continue_block` parameter set to `true`. | |
355 | ///! | |
356 | ///! [`DecompressError::ShortData`]: ../enum.DecompressError.html#variant.ShortData | |
357 | ///! [`DecompressError::OutputFull`]: ../enum.DecompressError.html#variant.OutputFull | |
358 | pub fn decompress_data(&mut self, src: &[u8], dst: &mut [u8], continue_block: bool) -> DecompressResult<usize> { | |
359 | if src.is_empty() || dst.is_empty() { | |
360 | return Err(DecompressError::InvalidArgument); | |
361 | } | |
362 | let mut csrc = if !continue_block { | |
363 | CurrentSource::new(src, self.br) | |
364 | } else { | |
365 | self.output_idx = 0; | |
366 | CurrentSource::reinit(src, self.br) | |
367 | }; | |
368 | 'main: loop { | |
369 | match self.state { | |
370 | InflateState::Start | InflateState::BlockStart => { | |
371 | if csrc.left() == 0 { | |
372 | self.br = csrc.br; | |
373 | return Err(DecompressError::ShortData); | |
374 | } | |
375 | self.final_block = csrc.read_bool().unwrap(); | |
376 | self.state = InflateState::BlockMode; | |
377 | }, | |
378 | InflateState::BlockMode => { | |
379 | let bmode = read_bits!(self, csrc, 2); | |
380 | match bmode { | |
381 | 0 => { | |
382 | csrc.align(); | |
383 | self.state = InflateState::StaticBlockLen; | |
384 | }, | |
385 | 1 => { self.state = InflateState::FixedBlock; }, | |
386 | 2 => { self.state = InflateState::DynBlockHlit; }, | |
387 | _ => { | |
388 | self.state = InflateState::End; | |
389 | return Err(DecompressError::InvalidHeader); | |
390 | }, | |
391 | }; | |
392 | }, | |
393 | InflateState::StaticBlockLen => { | |
394 | let len = read_bits!(self, csrc, 16); | |
395 | self.state = InflateState::StaticBlockInvLen(len); | |
396 | }, | |
397 | InflateState::StaticBlockInvLen(len) => { | |
398 | let inv_len = read_bits!(self, csrc, 16); | |
399 | if len != !inv_len { | |
400 | self.state = InflateState::End; | |
401 | return Err(DecompressError::InvalidHeader); | |
402 | } | |
403 | self.state = InflateState::StaticBlockCopy(len as usize); | |
404 | }, | |
405 | InflateState::StaticBlockCopy(len) => { | |
406 | for i in 0..len { | |
407 | if csrc.left() < 8 { | |
408 | self.br = csrc.br; | |
409 | self.state = InflateState::StaticBlockCopy(len - i); | |
410 | return Err(DecompressError::ShortData); | |
411 | } | |
412 | let val = csrc.read(8).unwrap() as u8; | |
413 | self.put_literal(val); | |
414 | } | |
415 | self.state = InflateState::BlockStart; | |
416 | } | |
417 | InflateState::FixedBlock => { | |
418 | let val = read_cb!(self, csrc, &self.fix_len_cb); | |
419 | if val < 256 { | |
420 | if self.output_idx >= dst.len() { | |
421 | self.br = csrc.br; | |
422 | self.state = InflateState::FixedBlockLiteral(val as u8); | |
423 | return Err(DecompressError::OutputFull); | |
424 | } | |
425 | self.put_literal(val as u8); | |
426 | dst[self.output_idx] = val as u8; | |
427 | self.output_idx += 1; | |
428 | } else if val == 256 { | |
429 | if self.final_block { | |
430 | self.state = InflateState::End; | |
431 | return Ok(self.output_idx); | |
432 | } else { | |
433 | self.state = InflateState::BlockStart; | |
434 | } | |
435 | } else { | |
436 | let len_idx = (val - 257) as usize; | |
437 | if len_idx >= LENGTH_BASE.len() { | |
438 | self.state = InflateState::End; | |
439 | return Err(DecompressError::InvalidData); | |
440 | } | |
441 | let len_bits = LENGTH_ADD_BITS[len_idx]; | |
442 | let add_base = LENGTH_BASE[len_idx] as usize; | |
443 | if len_bits > 0 { | |
444 | self.state = InflateState::FixedBlockLengthExt(add_base, len_bits); | |
445 | } else { | |
446 | self.state = InflateState::FixedBlockDist(add_base); | |
447 | } | |
448 | } | |
449 | }, | |
450 | InflateState::FixedBlockLiteral(sym) => { | |
451 | if self.output_idx >= dst.len() { | |
452 | self.br = csrc.br; | |
453 | return Err(DecompressError::OutputFull); | |
454 | } | |
455 | self.put_literal(sym); | |
456 | dst[self.output_idx] = sym; | |
457 | self.output_idx += 1; | |
458 | self.state = InflateState::FixedBlock; | |
459 | }, | |
460 | InflateState::FixedBlockLengthExt(base, bits) => { | |
461 | let add = read_bits!(self, csrc, bits) as usize; | |
462 | self.state = InflateState::FixedBlockDist(base + add); | |
463 | }, | |
464 | InflateState::FixedBlockDist(length) => { | |
465 | let dist_idx = reverse_bits(read_bits!(self, csrc, 5), 5) as usize; | |
466 | if dist_idx >= DIST_BASE.len() { | |
467 | self.state = InflateState::End; | |
468 | return Err(DecompressError::InvalidData); | |
469 | } | |
470 | let dist_bits = DIST_ADD_BITS[dist_idx]; | |
471 | let dist_base = DIST_BASE[dist_idx] as usize; | |
472 | if dist_bits == 0 { | |
473 | self.state = InflateState::FixedBlockCopy(length, dist_base); | |
474 | } else { | |
475 | self.state = InflateState::FixedBlockDistExt(length, dist_base, dist_bits); | |
476 | } | |
477 | }, | |
478 | InflateState::FixedBlockDistExt(length, base, bits) => { | |
479 | let add = read_bits!(self, csrc, bits) as usize; | |
480 | self.state = InflateState::FixedBlockCopy(length, base + add); | |
481 | }, | |
482 | InflateState::FixedBlockCopy(length, dist) => { | |
483 | if self.output_idx + length > dst.len() { | |
484 | let copy_size = dst.len() - self.output_idx; | |
485 | let ret = self.lz_copy(dist, copy_size, &mut dst[self.output_idx..]); | |
486 | if ret.is_err() { | |
487 | self.state = InflateState::End; | |
488 | return Err(DecompressError::InvalidData); | |
489 | } | |
490 | self.output_idx += copy_size; | |
491 | self.br = csrc.br; | |
492 | self.state = InflateState::FixedBlockCopy(length - copy_size, dist); | |
493 | return Err(DecompressError::OutputFull); | |
494 | } | |
495 | let ret = self.lz_copy(dist, length, &mut dst[self.output_idx..]); | |
496 | if ret.is_err() { | |
497 | self.state = InflateState::End; | |
498 | return Err(DecompressError::InvalidData); | |
499 | } | |
500 | self.output_idx += length; | |
501 | self.state = InflateState::FixedBlock; | |
502 | } | |
503 | InflateState::DynBlockHlit => { | |
504 | self.hlit = (read_bits!(self, csrc, 5) as usize) + 257; | |
505 | if self.hlit >= 287 { | |
506 | self.state = InflateState::End; | |
507 | return Err(DecompressError::InvalidHeader); | |
508 | } | |
509 | self.state = InflateState::DynBlockHdist; | |
510 | } | |
511 | InflateState::DynBlockHdist => { | |
512 | self.hdist = (read_bits!(self, csrc, 5) as usize) + 1; | |
513 | self.state = InflateState::DynBlockHclen; | |
514 | }, | |
515 | InflateState::DynBlockHclen => { | |
516 | let hclen = (read_bits!(self, csrc, 4) as usize) + 4; | |
517 | self.cur_len_idx = 0; | |
518 | self.len_lengths = [0; 19]; | |
519 | self.all_lengths = [0; NUM_LITERALS + NUM_DISTS]; | |
520 | self.state = InflateState::DynLengths(hclen); | |
521 | }, | |
522 | InflateState::DynLengths(len) => { | |
523 | for i in 0..len { | |
524 | if csrc.left() < 3 { | |
525 | self.br = csrc.br; | |
526 | self.state = InflateState::DynLengths(len - i); | |
527 | return Err(DecompressError::ShortData); | |
528 | } | |
529 | self.len_lengths[LEN_RECODE[self.cur_len_idx]] = csrc.read(3).unwrap() as u8; | |
530 | self.cur_len_idx += 1; | |
531 | } | |
532 | let mut len_codes = [ShortCodebookDesc { code: 0, bits: 0 }; 19]; | |
533 | lengths_to_codes(&self.len_lengths, &mut len_codes)?; | |
534 | let mut cr = ShortCodebookDescReader::new(len_codes.to_vec()); | |
535 | let ret = Codebook::new(&mut cr, CodebookMode::LSB); | |
536 | if ret.is_err() { | |
537 | self.state = InflateState::End; | |
538 | return Err(DecompressError::InvalidHeader); | |
539 | } | |
540 | self.dyn_len_cb = Some(ret.unwrap()); | |
541 | self.cur_len_idx = 0; | |
542 | self.state = InflateState::DynCodeLengths; | |
543 | }, | |
544 | InflateState::DynCodeLengths => { | |
545 | if let Some(ref len_cb) = self.dyn_len_cb { | |
546 | while self.cur_len_idx < self.hlit + self.hdist { | |
547 | let ret = csrc.read_cb(len_cb); | |
548 | let val = match ret { | |
549 | Ok(val) => val, | |
550 | Err(CodebookError::MemoryError) => { | |
551 | self.br = csrc.br; | |
552 | return Err(DecompressError::ShortData); | |
553 | }, | |
554 | Err(_) => { | |
555 | self.state = InflateState::End; | |
556 | return Err(DecompressError::InvalidHeader); | |
557 | }, | |
558 | }; | |
559 | if val < 16 { | |
560 | self.all_lengths[self.cur_len_idx] = val as u8; | |
561 | self.cur_len_idx += 1; | |
562 | } else { | |
563 | let idx = (val as usize) - 16; | |
564 | if idx > 2 { | |
565 | self.state = InflateState::End; | |
566 | return Err(DecompressError::InvalidHeader); | |
567 | } | |
568 | self.state = InflateState::DynCodeLengthsAdd(idx); | |
569 | continue 'main; | |
570 | } | |
571 | } | |
572 | let (lit_lengths, dist_lengths) = self.all_lengths.split_at(self.hlit); | |
573 | ||
574 | let mut lit_codes = [ShortCodebookDesc { code: 0, bits: 0 }; NUM_LITERALS]; | |
575 | lengths_to_codes(&lit_lengths, &mut lit_codes)?; | |
576 | let mut cr = ShortCodebookDescReader::new(lit_codes.to_vec()); | |
577 | let ret = Codebook::new(&mut cr, CodebookMode::LSB); | |
578 | if ret.is_err() { return Err(DecompressError::InvalidHeader); } | |
579 | self.dyn_lit_cb = Some(ret.unwrap()); | |
580 | ||
581 | let mut dist_codes = [ShortCodebookDesc { code: 0, bits: 0 }; NUM_DISTS]; | |
582 | lengths_to_codes(&dist_lengths[..self.hdist], &mut dist_codes)?; | |
583 | let mut cr = ShortCodebookDescReader::new(dist_codes.to_vec()); | |
584 | let ret = Codebook::new(&mut cr, CodebookMode::LSB); | |
585 | if ret.is_err() { return Err(DecompressError::InvalidHeader); } | |
586 | self.dyn_dist_cb = Some(ret.unwrap()); | |
587 | ||
588 | self.state = InflateState::DynBlock; | |
589 | } else { | |
590 | unreachable!(); | |
591 | } | |
592 | }, | |
593 | InflateState::DynCodeLengthsAdd(mode) => { | |
594 | let base = REPEAT_BASE[mode] as usize; | |
595 | let bits = REPEAT_BITS[mode]; | |
596 | let len = base + read_bits!(self, csrc, bits) as usize; | |
597 | if self.cur_len_idx + len > self.hlit + self.hdist { | |
598 | self.state = InflateState::End; | |
599 | return Err(DecompressError::InvalidHeader); | |
600 | } | |
601 | let rpt = if mode == 0 { | |
602 | if self.cur_len_idx == 0 { | |
603 | self.state = InflateState::End; | |
604 | return Err(DecompressError::InvalidHeader); | |
605 | } | |
606 | self.all_lengths[self.cur_len_idx - 1] | |
607 | } else { | |
608 | 0 | |
609 | }; | |
610 | for _ in 0..len { | |
611 | self.all_lengths[self.cur_len_idx] = rpt; | |
612 | self.cur_len_idx += 1; | |
613 | } | |
614 | self.state = InflateState::DynCodeLengths; | |
615 | }, | |
616 | InflateState::DynBlock => { | |
617 | if let Some(ref lit_cb) = self.dyn_lit_cb { | |
618 | let val = read_cb!(self, csrc, lit_cb); | |
619 | if val < 256 { | |
620 | if self.output_idx >= dst.len() { | |
621 | self.br = csrc.br; | |
622 | self.state = InflateState::DynBlockLiteral(val as u8); | |
623 | return Err(DecompressError::OutputFull); | |
624 | } | |
625 | self.put_literal(val as u8); | |
626 | dst[self.output_idx] = val as u8; | |
627 | self.output_idx += 1; | |
628 | } else if val == 256 { | |
629 | if self.final_block { | |
630 | self.state = InflateState::End; | |
631 | return Ok(self.output_idx); | |
632 | } else { | |
633 | self.state = InflateState::BlockStart; | |
634 | } | |
635 | } else { | |
636 | let len_idx = (val - 257) as usize; | |
637 | if len_idx >= LENGTH_BASE.len() { | |
638 | self.state = InflateState::End; | |
639 | return Err(DecompressError::InvalidData); | |
640 | } | |
641 | let len_bits = LENGTH_ADD_BITS[len_idx]; | |
642 | let add_base = LENGTH_BASE[len_idx] as usize; | |
643 | if len_bits > 0 { | |
644 | self.state = InflateState::DynBlockLengthExt(add_base, len_bits); | |
645 | } else { | |
646 | self.state = InflateState::DynBlockDist(add_base); | |
647 | } | |
648 | } | |
649 | } else { | |
650 | unreachable!(); | |
651 | } | |
652 | }, | |
653 | InflateState::DynBlockLiteral(sym) => { | |
654 | if self.output_idx >= dst.len() { | |
655 | self.br = csrc.br; | |
656 | return Err(DecompressError::OutputFull); | |
657 | } | |
658 | self.put_literal(sym); | |
659 | dst[self.output_idx] = sym; | |
660 | self.output_idx += 1; | |
661 | self.state = InflateState::DynBlock; | |
662 | }, | |
663 | InflateState::DynBlockLengthExt(base, bits) => { | |
664 | let add = read_bits!(self, csrc, bits) as usize; | |
665 | self.state = InflateState::DynBlockDist(base + add); | |
666 | }, | |
667 | InflateState::DynBlockDist(length) => { | |
668 | if let Some(ref dist_cb) = self.dyn_dist_cb { | |
669 | let dist_idx = read_cb!(self, csrc, dist_cb) as usize; | |
670 | if dist_idx >= DIST_BASE.len() { | |
671 | self.state = InflateState::End; | |
672 | return Err(DecompressError::InvalidData); | |
673 | } | |
674 | let dist_bits = DIST_ADD_BITS[dist_idx]; | |
675 | let dist_base = DIST_BASE[dist_idx] as usize; | |
676 | if dist_bits == 0 { | |
677 | self.state = InflateState::DynCopy(length, dist_base); | |
678 | } else { | |
679 | self.state = InflateState::DynBlockDistExt(length, dist_base, dist_bits); | |
680 | } | |
681 | } else { | |
682 | unreachable!(); | |
683 | } | |
684 | }, | |
685 | InflateState::DynBlockDistExt(length, base, bits) => { | |
686 | let add = read_bits!(self, csrc, bits) as usize; | |
687 | self.state = InflateState::DynCopy(length, base + add); | |
688 | }, | |
689 | InflateState::DynCopy(length, dist) => { | |
690 | if self.output_idx + length > dst.len() { | |
691 | let copy_size = dst.len() - self.output_idx; | |
692 | let ret = self.lz_copy(dist, copy_size, &mut dst[self.output_idx..]); | |
693 | if ret.is_err() { | |
694 | self.state = InflateState::End; | |
695 | return Err(DecompressError::InvalidData); | |
696 | } | |
697 | self.output_idx += copy_size; | |
698 | self.br = csrc.br; | |
699 | self.state = InflateState::DynCopy(length - copy_size, dist); | |
700 | return Err(DecompressError::OutputFull); | |
701 | } | |
702 | let ret = self.lz_copy(dist, length, &mut dst[self.output_idx..]); | |
703 | if ret.is_err() { | |
704 | self.state = InflateState::End; | |
705 | return Err(DecompressError::InvalidData); | |
706 | } | |
707 | self.output_idx += length; | |
708 | self.state = InflateState::DynBlock; | |
709 | } | |
710 | InflateState::End => { | |
711 | return Ok(0); | |
712 | }, | |
713 | } | |
714 | } | |
715 | } | |
716 | ///! Decompresses input data into output returning the uncompressed data length. | |
717 | pub fn uncompress(src: &[u8], dst: &mut [u8]) -> DecompressResult<usize> { | |
718 | let mut inflate = Self::new(); | |
719 | inflate.decompress_data(src, dst, false) | |
720 | } | |
721 | } | |
722 | ||
723 | impl Default for Inflate { | |
724 | fn default() -> Self { | |
725 | Self::new() | |
726 | } | |
727 | } | |
728 | ||
729 | fn lengths_to_codes(lens: &[u8], codes: &mut [ShortCodebookDesc]) -> DecompressResult<()> { | |
730 | let mut bits = [0u32; 32]; | |
731 | let mut pfx = [0u32; 33]; | |
732 | for len in lens.iter() { | |
733 | let len = *len as usize; | |
734 | if len >= bits.len() { | |
735 | return Err(DecompressError::InvalidHeader); | |
736 | } | |
737 | bits[len] += 1; | |
738 | } | |
739 | bits[0] = 0; | |
740 | let mut code = 0; | |
741 | for i in 0..bits.len() { | |
742 | code = (code + bits[i]) << 1; | |
743 | pfx[i + 1] = code; | |
744 | } | |
745 | ||
746 | for (len, codes) in lens.iter().zip(codes.iter_mut()) { | |
747 | let len = *len as usize; | |
748 | if len != 0 { | |
749 | let bits = len as u8; | |
750 | *codes = ShortCodebookDesc { code: reverse_bits(pfx[len], bits), bits }; | |
751 | pfx[len] += 1; | |
752 | } else { | |
753 | *codes = ShortCodebookDesc { code: 0, bits: 0 }; | |
754 | } | |
755 | } | |
756 | ||
757 | Ok(()) | |
758 | } | |
759 | ||
760 | struct GzipCRC32 { | |
761 | tab: [u32; 256], | |
762 | crc: u32, | |
763 | } | |
764 | ||
765 | impl GzipCRC32 { | |
766 | #[allow(clippy::unreadable_literal)] | |
767 | fn new() -> Self { | |
768 | let mut tab = [0u32; 256]; | |
769 | for i in 0..256 { | |
770 | let mut c = i as u32; | |
771 | for _ in 0..8 { | |
772 | if (c & 1) != 0 { | |
773 | c = 0xEDB88320 ^ (c >> 1); | |
774 | } else { | |
775 | c >>= 1; | |
776 | } | |
777 | } | |
778 | tab[i] = c; | |
779 | } | |
780 | Self { tab, crc: 0 } | |
781 | } | |
782 | fn update_crc(&mut self, src: &[u8]) { | |
783 | let mut c = !self.crc; | |
784 | for el in src.iter() { | |
785 | c = self.tab[((c ^ u32::from(*el)) & 0xFF) as usize] ^ (c >> 8); | |
786 | } | |
787 | self.crc = !c; | |
788 | } | |
789 | } | |
790 | ||
791 | ///! Decodes input data in gzip file format (RFC 1952) returning a vector containing decoded data. | |
792 | pub fn gzip_decode(br: &mut ByteReader, skip_crc: bool) -> DecompressResult<Vec<u8>> { | |
793 | const FLAG_HCRC: u8 = 0x02; | |
794 | const FLAG_EXTRA: u8 = 0x04; | |
795 | const FLAG_NAME: u8 = 0x08; | |
796 | const FLAG_COMMENT: u8 = 0x10; | |
797 | ||
798 | let id1 = br.read_byte()?; | |
799 | let id2 = br.read_byte()?; | |
800 | let cm = br.read_byte()?; | |
801 | let flg = br.read_byte()?; | |
802 | let _mtime = br.read_u32le()?; | |
803 | let _xfl = br.read_byte()?; | |
804 | let _os = br.read_byte()?; | |
805 | if id1 != 0x1F || id2 != 0x8B || cm != 8 { | |
806 | return Err(DecompressError::InvalidHeader); | |
807 | } | |
808 | ||
809 | if (flg & FLAG_EXTRA) != 0 { | |
810 | let xlen = br.read_u16le()? as usize; | |
811 | br.read_skip(xlen)?; | |
812 | } | |
813 | if (flg & FLAG_NAME) != 0 { | |
814 | loop { | |
815 | let b = br.read_byte()?; | |
816 | if b == 0 { | |
817 | break; | |
818 | } | |
819 | } | |
820 | } | |
821 | if (flg & FLAG_COMMENT) != 0 { | |
822 | loop { | |
823 | let b = br.read_byte()?; | |
824 | if b == 0 { | |
825 | break; | |
826 | } | |
827 | } | |
828 | } | |
829 | let _hcrc = if (flg & FLAG_HCRC) != 0 { | |
830 | br.read_u16le()? | |
831 | } else { | |
832 | 0 | |
833 | }; | |
834 | if (flg & 0xE0) != 0 { | |
835 | return Err(DecompressError::Unsupported); | |
836 | } | |
837 | ||
838 | let mut output: Vec<u8> = Vec::new(); | |
839 | let mut tail = [0u8; 8]; | |
840 | let mut inblk = [0u8; 1024]; | |
841 | let mut oblk = [0u8; 4096]; | |
842 | let mut inflate = Inflate::new(); | |
843 | let mut checker = GzipCRC32::new(); | |
844 | ||
845 | loop { | |
846 | let ret = br.read_buf_some(&mut inblk); | |
847 | if let Err(ByteIOError::EOF) = ret { | |
848 | break; | |
849 | } | |
850 | let inlen = match ret { | |
851 | Ok(val) => val, | |
852 | Err(_) => return Err(DecompressError::IOError), | |
853 | }; | |
854 | let mut repeat = false; | |
855 | loop { | |
856 | let ret = inflate.decompress_data(&inblk[..inlen], &mut oblk, repeat); | |
857 | match ret { | |
858 | Ok(outlen) => { | |
859 | checker.update_crc(&oblk[..outlen]); | |
860 | output.extend_from_slice(&oblk[..outlen]); | |
861 | break; | |
862 | }, | |
863 | Err(DecompressError::ShortData) => { | |
864 | break; | |
865 | }, | |
866 | Err(DecompressError::OutputFull) => { | |
867 | repeat = true; | |
868 | checker.update_crc(&oblk); | |
869 | output.extend_from_slice(&oblk); | |
870 | }, | |
871 | Err(err) => { | |
872 | return Err(err); | |
873 | }, | |
874 | } | |
875 | } | |
876 | // Save last 8 bytes for CRC and size. | |
877 | if inlen >= 8 { | |
878 | tail.copy_from_slice(&inblk[inlen - 8..][..8]); | |
879 | } else { | |
880 | let shift_len = 8 - inlen; | |
881 | for i in 0..shift_len { | |
882 | tail[i] = tail[i + inlen]; | |
883 | } | |
884 | for i in shift_len..8 { | |
885 | tail[i] = inblk[i - shift_len]; | |
886 | } | |
887 | } | |
888 | } | |
889 | if !skip_crc { | |
890 | if !inflate.is_finished() { println!("???"); } | |
891 | let crc = read_u32le(&tail[0..4])?; | |
892 | let size = read_u32le(&tail[4..8])?; | |
893 | if size != (output.len() as u32) { | |
894 | return Err(DecompressError::CRCError); | |
895 | } | |
896 | if crc != checker.crc { | |
897 | return Err(DecompressError::CRCError); | |
898 | } | |
899 | } | |
900 | ||
901 | Ok(output) | |
902 | } | |
903 | ||
904 | #[cfg(test)] | |
905 | mod test { | |
906 | use super::*; | |
907 | ||
908 | #[test] | |
909 | fn test_inflate1() { | |
910 | const TEST_DATA: &[u8] = &[ | |
911 | 0xF3, 0x48, 0xCD, 0xC9, 0xC9, 0xD7, 0x51, 0x28, | |
912 | 0xCF, 0x2F, 0xCA, 0x49, 0x51, 0x04, 0x00 ]; | |
913 | const TEST_REF: &[u8] = b"Hello, world!"; | |
914 | let mut dst_buf = [0u8; 13]; | |
915 | let len = Inflate::uncompress(TEST_DATA, &mut dst_buf).unwrap(); | |
916 | assert_eq!(len, 13); | |
917 | for i in 0..len { | |
918 | assert_eq!(dst_buf[i], TEST_REF[i]); | |
919 | } | |
920 | } | |
921 | #[test] | |
922 | fn test_inflate2() { | |
923 | const TEST_DATA3: &[u8] = &[ 0x4B, 0x4C, 0x44, 0x80, 0x24, 0x54, 0x80, 0x2C, 0x06, 0x00 ]; | |
924 | const TEST_REF3: &[u8] = b"aaaaaaaaaaaabbbbbbbbbbbbbbbaaaaabbbbbbb"; | |
925 | let mut dst_buf = [0u8; 39]; | |
926 | ||
927 | let mut inflate = Inflate::new(); | |
928 | let mut output_chunk = [0u8; 7]; | |
929 | let mut output_pos = 0; | |
930 | for input in TEST_DATA3.chunks(3) { | |
931 | let mut repeat = false; | |
932 | loop { | |
933 | let ret = inflate.decompress_data(input, &mut output_chunk, repeat); | |
934 | match ret { | |
935 | Ok(len) => { | |
936 | for i in 0..len { | |
937 | dst_buf[output_pos + i] = output_chunk[i]; | |
938 | } | |
939 | output_pos += len; | |
940 | break; | |
941 | }, | |
942 | Err(DecompressError::ShortData) => { | |
943 | break; | |
944 | }, | |
945 | Err(DecompressError::OutputFull) => { | |
946 | repeat = true; | |
947 | for i in 0..output_chunk.len() { | |
948 | dst_buf[output_pos + i] = output_chunk[i]; | |
949 | } | |
950 | output_pos += output_chunk.len(); | |
951 | }, | |
952 | _ => { | |
953 | panic!("decompress error {:?}", ret.err().unwrap()); | |
954 | }, | |
955 | } | |
956 | } | |
957 | } | |
958 | ||
959 | assert_eq!(output_pos, dst_buf.len()); | |
960 | for i in 0..output_pos { | |
961 | assert_eq!(dst_buf[i], TEST_REF3[i]); | |
962 | } | |
963 | } | |
964 | #[test] | |
965 | fn test_inflate3() { | |
966 | const TEST_DATA: &[u8] = &[ | |
967 | 0x1F, 0x8B, 0x08, 0x08, 0xF6, 0x7B, 0x90, 0x5E, 0x02, 0x03, 0x31, 0x2E, 0x74, 0x78, 0x74, 0x00, | |
968 | 0xE5, 0x95, 0x4B, 0x4E, 0xC3, 0x30, 0x10, 0x40, 0xF7, 0x39, 0xC5, 0x1C, 0x00, 0x16, 0x70, 0x83, | |
969 | 0x0A, 0xB5, 0x3B, 0xE8, 0x82, 0x5E, 0x60, 0x1A, 0x4F, 0xE2, 0x11, 0xFE, 0x44, 0x1E, 0xA7, 0x69, | |
970 | 0x6E, 0xCF, 0x38, 0xDD, 0xB0, 0x40, 0xA2, 0x46, 0x2D, 0x20, 0x2A, 0xE5, 0xAB, 0xCC, 0xE7, 0xBD, | |
971 | 0x49, 0xAC, 0x6C, 0x03, 0x64, 0x4B, 0xD0, 0x71, 0x92, 0x0C, 0x06, 0x67, 0x88, 0x1D, 0x3C, 0xD9, | |
972 | 0xC4, 0x92, 0x3D, 0x4A, 0xF3, 0x3C, 0x43, 0x4E, 0x23, 0x81, 0x8B, 0x07, 0x82, 0x1E, 0xF5, 0x90, | |
973 | 0x23, 0x78, 0x6A, 0x56, 0x30, 0x60, 0xCA, 0x89, 0x4D, 0x4F, 0xC0, 0x01, 0x10, 0x06, 0xC2, 0xA4, | |
974 | 0xA1, 0x44, 0xCD, 0xF6, 0x54, 0x50, 0xA8, 0x8D, 0xC1, 0x9C, 0x5F, 0x71, 0x37, 0x45, 0xC8, 0x63, | |
975 | 0xCA, 0x8E, 0xC0, 0xE8, 0x23, 0x69, 0x56, 0x9A, 0x8D, 0x5F, 0xB6, 0xC9, 0x96, 0x53, 0x4D, 0x17, | |
976 | 0xAB, 0xB9, 0xB0, 0x49, 0x14, 0x5A, 0x0B, 0x96, 0x82, 0x7C, 0xB7, 0x6F, 0x17, 0x35, 0xC7, 0x9E, | |
977 | 0xDF, 0x78, 0xA3, 0xF1, 0xD0, 0xA2, 0x73, 0x1C, 0x7A, 0xD8, 0x2B, 0xB3, 0x5C, 0x90, 0x85, 0xBB, | |
978 | 0x2A, 0x14, 0x2E, 0xF7, 0xD1, 0x19, 0x48, 0x0A, 0x23, 0x57, 0x45, 0x13, 0x3E, 0xD6, 0xA0, 0xBD, | |
979 | 0xF2, 0x11, 0x7A, 0x22, 0x21, 0xAD, 0xE5, 0x70, 0x56, 0xA0, 0x9F, 0xA5, 0xA5, 0x03, 0x85, 0x2A, | |
980 | 0xDE, 0x92, 0x00, 0x32, 0x61, 0x10, 0xAD, 0x27, 0x13, 0x7B, 0x5F, 0x98, 0x7F, 0x59, 0x83, 0xB8, | |
981 | 0xB7, 0x35, 0x16, 0xEB, 0x12, 0x0F, 0x1E, 0xD9, 0x14, 0x0B, 0xCF, 0xEE, 0x6D, 0x91, 0xF8, 0x93, | |
982 | 0x6E, 0x81, 0x3F, 0x7F, 0x41, 0xA4, 0x22, 0x1F, 0xB7, 0xE6, 0x85, 0x83, 0x9A, 0xA2, 0x61, 0x12, | |
983 | 0x0D, 0x0F, 0x6D, 0x01, 0xBD, 0xB0, 0xE8, 0x1D, 0xEC, 0xD1, 0xA0, 0xBF, 0x1F, 0x4E, 0xFB, 0x55, | |
984 | 0xBD, 0x73, 0xDD, 0x87, 0xB9, 0x53, 0x23, 0x17, 0xD3, 0xE2, 0xE9, 0x08, 0x87, 0x42, 0xFF, 0xCF, | |
985 | 0x26, 0x42, 0xAE, 0x76, 0xB5, 0xAE, 0x97, 0x0C, 0x18, 0x78, 0xA0, 0x24, 0xE5, 0x54, 0x0C, 0x6E, | |
986 | 0x60, 0x52, 0x79, 0x22, 0x57, 0xF5, 0x87, 0x78, 0x78, 0x04, 0x93, 0x46, 0xEF, 0xCB, 0x98, 0x96, | |
987 | 0x8B, 0x65, 0x00, 0xB7, 0x36, 0xBD, 0x77, 0xA8, 0xBD, 0x5A, 0xAA, 0x1A, 0x09, 0x00, 0x00 | |
988 | ]; | |
989 | ||
990 | let mut mr = MemoryReader::new_read(TEST_DATA); | |
991 | let mut br = ByteReader::new(&mut mr); | |
992 | let _dst_buf = gzip_decode(&mut br, false).unwrap(); | |
993 | ||
994 | // println!("{}", String::from_utf8_lossy(_dst_buf.as_slice())); | |
995 | } | |
996 | } |