]> git.nihav.org Git - nihav.git/blame - nihav-core/src/compr/deflate.rs
deflate: make Deflate Send-able
[nihav.git] / nihav-core / src / compr / deflate.rs
CommitLineData
0443d0c5
KS
1//! Deflate format (RFC 1951) support.
2//!
f8cdb949 3//! This module provides functionality for decompressing raw deflated streams via [`Inflate`] and gzip files (RFC 1952) via [`gzip_decode`] and compressing raw or zlib streams via [`Deflate`].
0443d0c5 4//!
f8cdb949 5//! [`Deflate`]: ./struct.Deflate.html
0443d0c5
KS
6//! [`Inflate`]: ./struct.Inflate.html
7//! [`gzip_decode`]: ./fn.gzip_decode.html
8//!
9//! # Examples
10//!
11//! Decompressing full input buffer into sufficiently large output buffer:
12//! ```
13//! # use nihav_core::compr::DecompressError;
14//! use nihav_core::compr::deflate::Inflate;
15//!
16//! # fn decompress(input: &[u8]) -> Result<(), DecompressError> {
17//! # let mut output_buffer = [0u8; 16];
18//! let output_length = Inflate::uncompress(input, &mut output_buffer)?;
19//! # Ok(())
20//! # }
21//! ```
22//!
23//! Decompressing input chunks into portions of output:
24//! ```
25//! use nihav_core::compr::DecompressError;
26//! use nihav_core::compr::deflate::Inflate;
27//!
28//! # fn decompress(input_data: &[u8]) -> Result<(), DecompressError> {
29//! let mut inflate = Inflate::new();
30//! let mut dst_buf: Vec<u8> = Vec::new();
31//! let mut output_chunk = [0u8; 1024];
32//! for src in input_data.chunks(512) {
33//! let mut repeat = false;
34//! loop {
35//! let ret = inflate.decompress_data(src, &mut output_chunk, repeat);
36//! match ret {
37//! Ok(len) => { // we got a buffer decoded successfully to the end
38//! dst_buf.extend_from_slice(&output_chunk[..len]);
39//! break;
40//! },
41//! Err(DecompressError::ShortData) => { // this block of data was fully read
42//! break;
43//! },
44//! Err(DecompressError::OutputFull) => {
45//! // the output buffer is full, flush it and continue decoding the same block
46//! repeat = true;
47//! dst_buf.extend_from_slice(&output_chunk);
48//! },
49//! Err(err) => {
50//! return Err(err);
51//! },
52//! }
53//! }
54//! }
55//! # Ok(())
56//! # }
57//! ```
f8cdb949
KS
58//!
59//! Compressing input buffer into zlib stream:
60//! ```
61//! use nihav_core::compr::deflate::{Deflate, DeflateMode, DeflateWriter};
62//!
63//! # fn compress(input: &[u8]) {
64//! let output = Vec::with_capacity(input.len() * 65540 / 65535 + 6);
65//! let mut writer = DeflateWriter::new(output);
66//! let mut compr = Deflate::new(DeflateMode::Fast);
67//! compr.write_zlib_header(&mut writer);
68//! compr.compress(input, &mut writer);
69//! compr.compress_end(&mut writer);
70//! let output = writer.end();
71//! # }
72//! ```
0443d0c5
KS
73
74use crate::io::byteio::*;
75use crate::io::bitreader::*;
76use crate::io::codebook::*;
77use super::*;
78
79const NUM_LITERALS: usize = 287;
80const NUM_DISTS: usize = 32;
81
82struct FixedLenCodeReader {}
83
84impl CodebookDescReader<u16> for FixedLenCodeReader {
85 fn bits(&mut self, idx: usize) -> u8 {
86 if idx < 144 { 8 }
87 else if idx < 256 { 9 }
88 else if idx < 280 { 7 }
89 else { 8 }
90 }
b36f412c 91 #[allow(clippy::identity_op)]
0443d0c5
KS
92 fn code(&mut self, idx: usize) -> u32 {
93 let base = idx as u32;
94 let bits = self.bits(idx);
95 if idx < 144 { reverse_bits(base + 0x30, bits) }
96 else if idx < 256 { reverse_bits(base + 0x190 - 144, bits) }
97 else if idx < 280 { reverse_bits(base + 0x000 - 256, bits) }
98 else { reverse_bits(base + 0xC0 - 280, bits) }
99 }
100 fn sym (&mut self, idx: usize) -> u16 { idx as u16 }
101 fn len(&mut self) -> usize { NUM_LITERALS + 1 }
102}
103
104#[derive(Clone,Copy,Default)]
105struct BitReaderState {
106 pos: usize,
107 bitbuf: u32,
108 bits: u8,
109}
110
111struct CurrentSource<'a> {
112 src: &'a [u8],
113 br: BitReaderState,
114}
115
116impl<'a> CurrentSource<'a> {
117 fn new(src: &'a [u8], br: BitReaderState) -> Self {
118 let mut newsrc = Self { src, br };
119 newsrc.br.pos = 0;
120 newsrc.refill();
121 newsrc
122 }
123 fn reinit(src: &'a [u8], br: BitReaderState) -> Self {
124 let mut newsrc = Self { src, br };
125 newsrc.refill();
126 newsrc
127 }
128 fn refill(&mut self) {
129 while (self.br.bits <= 24) && (self.br.pos < self.src.len()) {
130 self.br.bitbuf |= u32::from(self.src[self.br.pos]) << self.br.bits;
131 self.br.bits += 8;
132 self.br.pos += 1;
133 }
134 }
135 fn skip_cache(&mut self, nbits: u8) {
136 self.br.bitbuf >>= nbits;
137 self.br.bits -= nbits;
138 }
139 fn read(&mut self, nbits: u8) -> BitReaderResult<u32> {
140 if nbits == 0 { return Ok(0); }
141 if nbits > 16 { return Err(BitReaderError::TooManyBitsRequested); }
142 if self.br.bits < nbits {
143 self.refill();
144 if self.br.bits < nbits { return Err(BitReaderError::BitstreamEnd); }
145 }
146 let ret = self.br.bitbuf & ((1 << nbits) - 1);
147 self.skip_cache(nbits);
148 Ok(ret)
149 }
150 fn read_bool(&mut self) -> BitReaderResult<bool> {
151 if self.br.bits == 0 {
152 self.refill();
153 if self.br.bits == 0 { return Err(BitReaderError::BitstreamEnd); }
154 }
155 let ret = (self.br.bitbuf & 1) != 0;
156 self.skip_cache(1);
157 Ok(ret)
158 }
159 fn peek(&mut self, nbits: u8) -> u32 {
160 if nbits == 0 || nbits > 16 { return 0; }
161 if self.br.bits < nbits {
162 self.refill();
163 }
164 self.br.bitbuf & ((1 << nbits) - 1)
165 }
166 fn skip(&mut self, nbits: u32) -> BitReaderResult<()> {
167 if u32::from(self.br.bits) >= nbits {
168 self.skip_cache(nbits as u8);
169 } else {
170 unreachable!();
171 }
172 Ok(())
173 }
174 fn align(&mut self) {
175 let b = self.br.bits & 7;
176 if b != 0 {
11f1d51e 177 self.skip_cache(b);
0443d0c5
KS
178 }
179 }
180 fn left(&self) -> isize {
181 ((self.src.len() as isize) - (self.br.pos as isize)) * 8 + (self.br.bits as isize)
182 }
183}
184
185impl<'a, S: Copy> CodebookReader<S> for CurrentSource<'a> {
186 fn read_cb(&mut self, cb: &Codebook<S>) -> CodebookResult<S> {
187 let mut esc = true;
188 let mut idx = 0;
189 let mut lut_bits = cb.lut_bits;
190 let orig_br = self.br;
191 while esc {
192 let lut_idx = (self.peek(lut_bits) as usize) + (idx as usize);
193 if cb.table[lut_idx] == TABLE_FILL_VALUE { return Err(CodebookError::InvalidCode); }
194 let bits = cb.table[lut_idx] & 0x7F;
195 esc = (cb.table[lut_idx] & 0x80) != 0;
196 idx = (cb.table[lut_idx] >> 8) as usize;
197 let skip_bits = if esc { u32::from(lut_bits) } else { bits };
198 if (skip_bits as isize) > self.left() {
199 self.br = orig_br;
200 self.refill();
201 return Err(CodebookError::MemoryError);
202 }
203 self.skip(skip_bits as u32).unwrap();
204 lut_bits = bits as u8;
205 }
206 Ok(cb.syms[idx])
207 }
208}
209
210enum InflateState {
211 Start,
212 BlockStart,
213 BlockMode,
214 StaticBlockLen,
215 StaticBlockInvLen(u32),
216 StaticBlockCopy(usize),
217 FixedBlock,
218 FixedBlockLengthExt(usize, u8),
219 FixedBlockDist(usize),
220 FixedBlockDistExt(usize, usize, u8),
221 FixedBlockCopy(usize, usize),
222 FixedBlockLiteral(u8),
223 DynBlockHlit,
224 DynBlockHdist,
225 DynBlockHclen,
226 DynLengths(usize),
227 DynCodeLengths,
228 DynCodeLengthsAdd(usize),
229 DynBlock,
230 DynBlockLengthExt(usize, u8),
231 DynBlockDist(usize),
232 DynBlockDistExt(usize, usize, u8),
233 DynCopy(usize, usize),
234 DynBlockLiteral(u8),
235 End,
236}
237
238///! The decompressor for deflated streams (RFC 1951).
239pub struct Inflate {
240 br: BitReaderState,
241 fix_len_cb: Codebook<u16>,
242
243 buf: [u8; 65536],
244 bpos: usize,
245 output_idx: usize,
37d96dbb 246 full_pos: usize,
0443d0c5
KS
247
248 state: InflateState,
249 final_block: bool,
250 hlit: usize,
251 hdist: usize,
252 dyn_len_cb: Option<Codebook<u32>>,
253 dyn_lit_cb: Option<Codebook<u32>>,
254 dyn_dist_cb: Option<Codebook<u32>>,
255 len_lengths: [u8; 19],
256 all_lengths: [u8; NUM_LITERALS + NUM_DISTS],
257 cur_len_idx: usize,
258}
259
260const LENGTH_ADD_BITS: [u8; 29] = [
261 0, 0, 0, 0, 0, 0, 0, 0, 1, 1,
262 1, 1, 2, 2, 2, 2, 3, 3, 3, 3,
263 4, 4, 4, 4, 5, 5, 5, 5, 0
264];
265const LENGTH_BASE: [u16; 29] = [
266 3, 4, 5, 6, 7, 8, 9, 10, 11, 13,
267 15, 17, 19, 23, 27, 31, 35, 43, 51, 59,
268 67, 83, 99, 115, 131, 163, 195, 227, 258
269];
270const DIST_ADD_BITS: [u8; 30] = [
271 0, 0, 0, 0, 1, 1, 2, 2, 3, 3,
272 4, 4, 5, 5, 6, 6, 7, 7, 8, 8,
273 9, 9, 10, 10, 11, 11, 12, 12, 13, 13
274];
275const DIST_BASE: [u16; 30] = [
276 1, 2, 3, 4, 5, 7, 9, 13, 17, 25,
277 33, 49, 65, 97, 129, 193, 257, 385, 513, 769,
278 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577
279];
280const LEN_RECODE: [usize; 19] = [
281 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
282];
283const REPEAT_BITS: [u8; 3] = [ 2, 3, 7 ];
284const REPEAT_BASE: [u8; 3] = [ 3, 3, 11 ];
285
286macro_rules! read_bits {
287 ($self: expr, $csrc: expr, $bits: expr) => ({
288 if $csrc.left() < $bits as isize {
289 $self.br = $csrc.br;
290 return Err(DecompressError::ShortData);
291 }
292 $csrc.read($bits).unwrap()
293 })
294}
295
296macro_rules! read_cb {
297 ($self: expr, $csrc: expr, $cb: expr) => ({
298 let ret = $csrc.read_cb($cb);
299 if let Err(CodebookError::MemoryError) = ret {
300 $self.br = $csrc.br;
301 return Err(DecompressError::ShortData);
302 }
303 match ret {
304 Ok(val) => val,
305 Err(_) => {
306 $self.state = InflateState::End;
307 return Err(DecompressError::InvalidData);
308 },
309 }
310 })
311}
312
313impl Inflate {
314 ///! Creates a new instance of `Inflate` struct.
315 pub fn new() -> Self {
316 let mut cr = FixedLenCodeReader {};
317 let fix_len_cb = Codebook::new(&mut cr, CodebookMode::LSB).unwrap();
318 Self {
319 br: BitReaderState::default(),
320 fix_len_cb,
321
322 buf: [0; 65536],
323 bpos: 0,
324 output_idx: 0,
37d96dbb 325 full_pos: 0,
0443d0c5
KS
326
327 state: InflateState::Start,
328 final_block: false,
329 dyn_len_cb: None,
330 dyn_lit_cb: None,
331 dyn_dist_cb: None,
332 hlit: 0,
333 hdist: 0,
334 len_lengths: [0; 19],
335 all_lengths: [0; NUM_LITERALS + NUM_DISTS],
336 cur_len_idx: 0,
337 }
338 }
339 fn put_literal(&mut self, val: u8) {
340 self.buf[self.bpos] = val;
c96ad969 341 self.bpos = (self.bpos + 1) & (self.buf.len() - 1);
37d96dbb 342 self.full_pos += 1;
0443d0c5
KS
343 }
344 fn lz_copy(&mut self, offset: usize, len: usize, dst: &mut [u8]) -> DecompressResult<()> {
345 let mask = self.buf.len() - 1;
37d96dbb 346 if offset > self.full_pos {
0443d0c5
KS
347 return Err(DecompressError::InvalidData);
348 }
c96ad969 349 let cstart = (self.bpos.wrapping_sub(offset)) & mask;
0443d0c5
KS
350 for i in 0..len {
351 self.buf[(self.bpos + i) & mask] = self.buf[(cstart + i) & mask];
352 dst[i] = self.buf[(cstart + i) & mask];
353 }
c96ad969 354 self.bpos = (self.bpos + len) & mask;
37d96dbb 355 self.full_pos += len;
0443d0c5
KS
356 Ok(())
357 }
358 ///! Reports whether decoder has finished decoding the input.
359 pub fn is_finished(&self) -> bool {
360 match self.state {
361 InflateState::End => true,
362 _ => false,
363 }
364 }
365 ///! Reports the current amount of bytes output into the destination buffer after the last run.
366 pub fn get_current_output_size(&self) -> usize { self.output_idx }
367 ///! Reports the total amount of bytes decoded so far.
368 pub fn get_total_output_size(&self) -> usize { self.bpos }
369 ///! Tries to decompress input data and write it to the output buffer.
370 ///!
371 ///! Since the decompressor can work with arbitrary input and output chunks its return value may have several meanings:
372 ///! * `Ok(len)` means the stream has been fully decoded and then number of bytes output into the destination buffer is returned.
373 ///! * [`DecompressError::ShortData`] means the input stream has been fully read but more data is needed.
374 ///! * [`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`.
375 ///!
376 ///! [`DecompressError::ShortData`]: ../enum.DecompressError.html#variant.ShortData
377 ///! [`DecompressError::OutputFull`]: ../enum.DecompressError.html#variant.OutputFull
378 pub fn decompress_data(&mut self, src: &[u8], dst: &mut [u8], continue_block: bool) -> DecompressResult<usize> {
de161d26
KS
379 self.decompress_data_internal(src, dst, continue_block, false)
380 }
381 ///! Tries to decompress whole input chunk to the output buffer.
382 pub fn decompress_block(&mut self, src: &[u8], dst: &mut [u8]) -> DecompressResult<usize> {
383 self.decompress_data_internal(src, dst, false, true)
384 }
385 #[allow(clippy::comparison_chain)]
386 fn decompress_data_internal(&mut self, src: &[u8], dst: &mut [u8], continue_block: bool, do_one_block: bool) -> DecompressResult<usize> {
b36f412c 387 if src.is_empty() || dst.is_empty() {
0443d0c5
KS
388 return Err(DecompressError::InvalidArgument);
389 }
390 let mut csrc = if !continue_block {
391 CurrentSource::new(src, self.br)
392 } else {
393 self.output_idx = 0;
394 CurrentSource::reinit(src, self.br)
395 };
de161d26
KS
396 if do_one_block {
397 self.output_idx = 0;
398 }
0c9b706a
KS
399 // check for zlib stream header
400 if let (&InflateState::Start, true) = (&self.state, src.len() > 2) {
401 let cm = src[0] & 0xF;
402 let cinfo = src[0] >> 4;
403 let hdr = (u16::from(src[0]) << 8) | u16::from(src[1]);
404 if cm == 8 && cinfo <= 7 && (hdr % 31) == 0 {
405 csrc.skip(16).unwrap();
406 }
407 }
0443d0c5
KS
408 'main: loop {
409 match self.state {
410 InflateState::Start | InflateState::BlockStart => {
411 if csrc.left() == 0 {
de161d26
KS
412 if do_one_block {
413 return Ok(self.output_idx);
414 }
0443d0c5
KS
415 self.br = csrc.br;
416 return Err(DecompressError::ShortData);
417 }
418 self.final_block = csrc.read_bool().unwrap();
419 self.state = InflateState::BlockMode;
420 },
421 InflateState::BlockMode => {
422 let bmode = read_bits!(self, csrc, 2);
423 match bmode {
424 0 => {
425 csrc.align();
426 self.state = InflateState::StaticBlockLen;
427 },
428 1 => { self.state = InflateState::FixedBlock; },
429 2 => { self.state = InflateState::DynBlockHlit; },
430 _ => {
431 self.state = InflateState::End;
432 return Err(DecompressError::InvalidHeader);
433 },
434 };
435 },
436 InflateState::StaticBlockLen => {
437 let len = read_bits!(self, csrc, 16);
438 self.state = InflateState::StaticBlockInvLen(len);
439 },
440 InflateState::StaticBlockInvLen(len) => {
441 let inv_len = read_bits!(self, csrc, 16);
6130c973 442 if (len ^ inv_len) != 0xFFFF {
0443d0c5
KS
443 self.state = InflateState::End;
444 return Err(DecompressError::InvalidHeader);
445 }
446 self.state = InflateState::StaticBlockCopy(len as usize);
447 },
448 InflateState::StaticBlockCopy(len) => {
449 for i in 0..len {
450 if csrc.left() < 8 {
451 self.br = csrc.br;
452 self.state = InflateState::StaticBlockCopy(len - i);
453 return Err(DecompressError::ShortData);
454 }
455 let val = csrc.read(8).unwrap() as u8;
456 self.put_literal(val);
457 }
458 self.state = InflateState::BlockStart;
459 }
460 InflateState::FixedBlock => {
461 let val = read_cb!(self, csrc, &self.fix_len_cb);
462 if val < 256 {
463 if self.output_idx >= dst.len() {
464 self.br = csrc.br;
465 self.state = InflateState::FixedBlockLiteral(val as u8);
466 return Err(DecompressError::OutputFull);
467 }
468 self.put_literal(val as u8);
469 dst[self.output_idx] = val as u8;
470 self.output_idx += 1;
471 } else if val == 256 {
472 if self.final_block {
473 self.state = InflateState::End;
474 return Ok(self.output_idx);
475 } else {
476 self.state = InflateState::BlockStart;
477 }
478 } else {
479 let len_idx = (val - 257) as usize;
480 if len_idx >= LENGTH_BASE.len() {
481 self.state = InflateState::End;
482 return Err(DecompressError::InvalidData);
483 }
484 let len_bits = LENGTH_ADD_BITS[len_idx];
485 let add_base = LENGTH_BASE[len_idx] as usize;
486 if len_bits > 0 {
487 self.state = InflateState::FixedBlockLengthExt(add_base, len_bits);
488 } else {
489 self.state = InflateState::FixedBlockDist(add_base);
490 }
491 }
492 },
493 InflateState::FixedBlockLiteral(sym) => {
494 if self.output_idx >= dst.len() {
495 self.br = csrc.br;
496 return Err(DecompressError::OutputFull);
497 }
498 self.put_literal(sym);
499 dst[self.output_idx] = sym;
500 self.output_idx += 1;
501 self.state = InflateState::FixedBlock;
502 },
503 InflateState::FixedBlockLengthExt(base, bits) => {
504 let add = read_bits!(self, csrc, bits) as usize;
505 self.state = InflateState::FixedBlockDist(base + add);
506 },
507 InflateState::FixedBlockDist(length) => {
508 let dist_idx = reverse_bits(read_bits!(self, csrc, 5), 5) as usize;
509 if dist_idx >= DIST_BASE.len() {
510 self.state = InflateState::End;
511 return Err(DecompressError::InvalidData);
512 }
513 let dist_bits = DIST_ADD_BITS[dist_idx];
514 let dist_base = DIST_BASE[dist_idx] as usize;
515 if dist_bits == 0 {
516 self.state = InflateState::FixedBlockCopy(length, dist_base);
517 } else {
518 self.state = InflateState::FixedBlockDistExt(length, dist_base, dist_bits);
519 }
520 },
521 InflateState::FixedBlockDistExt(length, base, bits) => {
522 let add = read_bits!(self, csrc, bits) as usize;
523 self.state = InflateState::FixedBlockCopy(length, base + add);
524 },
525 InflateState::FixedBlockCopy(length, dist) => {
526 if self.output_idx + length > dst.len() {
527 let copy_size = dst.len() - self.output_idx;
528 let ret = self.lz_copy(dist, copy_size, &mut dst[self.output_idx..]);
529 if ret.is_err() {
530 self.state = InflateState::End;
531 return Err(DecompressError::InvalidData);
532 }
533 self.output_idx += copy_size;
534 self.br = csrc.br;
535 self.state = InflateState::FixedBlockCopy(length - copy_size, dist);
536 return Err(DecompressError::OutputFull);
537 }
538 let ret = self.lz_copy(dist, length, &mut dst[self.output_idx..]);
539 if ret.is_err() {
540 self.state = InflateState::End;
541 return Err(DecompressError::InvalidData);
542 }
543 self.output_idx += length;
544 self.state = InflateState::FixedBlock;
545 }
546 InflateState::DynBlockHlit => {
547 self.hlit = (read_bits!(self, csrc, 5) as usize) + 257;
548 if self.hlit >= 287 {
549 self.state = InflateState::End;
550 return Err(DecompressError::InvalidHeader);
551 }
552 self.state = InflateState::DynBlockHdist;
553 }
554 InflateState::DynBlockHdist => {
555 self.hdist = (read_bits!(self, csrc, 5) as usize) + 1;
556 self.state = InflateState::DynBlockHclen;
557 },
558 InflateState::DynBlockHclen => {
559 let hclen = (read_bits!(self, csrc, 4) as usize) + 4;
560 self.cur_len_idx = 0;
561 self.len_lengths = [0; 19];
562 self.all_lengths = [0; NUM_LITERALS + NUM_DISTS];
563 self.state = InflateState::DynLengths(hclen);
564 },
565 InflateState::DynLengths(len) => {
566 for i in 0..len {
567 if csrc.left() < 3 {
568 self.br = csrc.br;
569 self.state = InflateState::DynLengths(len - i);
570 return Err(DecompressError::ShortData);
571 }
572 self.len_lengths[LEN_RECODE[self.cur_len_idx]] = csrc.read(3).unwrap() as u8;
573 self.cur_len_idx += 1;
574 }
575 let mut len_codes = [ShortCodebookDesc { code: 0, bits: 0 }; 19];
576 lengths_to_codes(&self.len_lengths, &mut len_codes)?;
577 let mut cr = ShortCodebookDescReader::new(len_codes.to_vec());
578 let ret = Codebook::new(&mut cr, CodebookMode::LSB);
579 if ret.is_err() {
580 self.state = InflateState::End;
581 return Err(DecompressError::InvalidHeader);
582 }
583 self.dyn_len_cb = Some(ret.unwrap());
584 self.cur_len_idx = 0;
585 self.state = InflateState::DynCodeLengths;
586 },
587 InflateState::DynCodeLengths => {
588 if let Some(ref len_cb) = self.dyn_len_cb {
589 while self.cur_len_idx < self.hlit + self.hdist {
590 let ret = csrc.read_cb(len_cb);
591 let val = match ret {
592 Ok(val) => val,
593 Err(CodebookError::MemoryError) => {
594 self.br = csrc.br;
595 return Err(DecompressError::ShortData);
596 },
597 Err(_) => {
598 self.state = InflateState::End;
599 return Err(DecompressError::InvalidHeader);
600 },
601 };
602 if val < 16 {
603 self.all_lengths[self.cur_len_idx] = val as u8;
604 self.cur_len_idx += 1;
605 } else {
606 let idx = (val as usize) - 16;
607 if idx > 2 {
608 self.state = InflateState::End;
609 return Err(DecompressError::InvalidHeader);
610 }
611 self.state = InflateState::DynCodeLengthsAdd(idx);
612 continue 'main;
613 }
614 }
615 let (lit_lengths, dist_lengths) = self.all_lengths.split_at(self.hlit);
616
617 let mut lit_codes = [ShortCodebookDesc { code: 0, bits: 0 }; NUM_LITERALS];
618 lengths_to_codes(&lit_lengths, &mut lit_codes)?;
619 let mut cr = ShortCodebookDescReader::new(lit_codes.to_vec());
620 let ret = Codebook::new(&mut cr, CodebookMode::LSB);
621 if ret.is_err() { return Err(DecompressError::InvalidHeader); }
622 self.dyn_lit_cb = Some(ret.unwrap());
623
624 let mut dist_codes = [ShortCodebookDesc { code: 0, bits: 0 }; NUM_DISTS];
625 lengths_to_codes(&dist_lengths[..self.hdist], &mut dist_codes)?;
626 let mut cr = ShortCodebookDescReader::new(dist_codes.to_vec());
627 let ret = Codebook::new(&mut cr, CodebookMode::LSB);
628 if ret.is_err() { return Err(DecompressError::InvalidHeader); }
629 self.dyn_dist_cb = Some(ret.unwrap());
630
631 self.state = InflateState::DynBlock;
632 } else {
633 unreachable!();
634 }
635 },
636 InflateState::DynCodeLengthsAdd(mode) => {
637 let base = REPEAT_BASE[mode] as usize;
638 let bits = REPEAT_BITS[mode];
639 let len = base + read_bits!(self, csrc, bits) as usize;
640 if self.cur_len_idx + len > self.hlit + self.hdist {
641 self.state = InflateState::End;
642 return Err(DecompressError::InvalidHeader);
643 }
b36f412c
KS
644 let rpt = if mode == 0 {
645 if self.cur_len_idx == 0 {
646 self.state = InflateState::End;
647 return Err(DecompressError::InvalidHeader);
648 }
649 self.all_lengths[self.cur_len_idx - 1]
650 } else {
651 0
652 };
0443d0c5
KS
653 for _ in 0..len {
654 self.all_lengths[self.cur_len_idx] = rpt;
655 self.cur_len_idx += 1;
656 }
657 self.state = InflateState::DynCodeLengths;
658 },
659 InflateState::DynBlock => {
660 if let Some(ref lit_cb) = self.dyn_lit_cb {
661 let val = read_cb!(self, csrc, lit_cb);
662 if val < 256 {
663 if self.output_idx >= dst.len() {
664 self.br = csrc.br;
665 self.state = InflateState::DynBlockLiteral(val as u8);
666 return Err(DecompressError::OutputFull);
667 }
668 self.put_literal(val as u8);
669 dst[self.output_idx] = val as u8;
670 self.output_idx += 1;
671 } else if val == 256 {
672 if self.final_block {
673 self.state = InflateState::End;
674 return Ok(self.output_idx);
675 } else {
676 self.state = InflateState::BlockStart;
677 }
678 } else {
679 let len_idx = (val - 257) as usize;
680 if len_idx >= LENGTH_BASE.len() {
681 self.state = InflateState::End;
682 return Err(DecompressError::InvalidData);
683 }
684 let len_bits = LENGTH_ADD_BITS[len_idx];
685 let add_base = LENGTH_BASE[len_idx] as usize;
686 if len_bits > 0 {
687 self.state = InflateState::DynBlockLengthExt(add_base, len_bits);
688 } else {
689 self.state = InflateState::DynBlockDist(add_base);
690 }
691 }
692 } else {
693 unreachable!();
694 }
695 },
696 InflateState::DynBlockLiteral(sym) => {
697 if self.output_idx >= dst.len() {
698 self.br = csrc.br;
699 return Err(DecompressError::OutputFull);
700 }
701 self.put_literal(sym);
702 dst[self.output_idx] = sym;
703 self.output_idx += 1;
704 self.state = InflateState::DynBlock;
705 },
706 InflateState::DynBlockLengthExt(base, bits) => {
707 let add = read_bits!(self, csrc, bits) as usize;
708 self.state = InflateState::DynBlockDist(base + add);
709 },
710 InflateState::DynBlockDist(length) => {
711 if let Some(ref dist_cb) = self.dyn_dist_cb {
712 let dist_idx = read_cb!(self, csrc, dist_cb) as usize;
713 if dist_idx >= DIST_BASE.len() {
714 self.state = InflateState::End;
715 return Err(DecompressError::InvalidData);
716 }
717 let dist_bits = DIST_ADD_BITS[dist_idx];
718 let dist_base = DIST_BASE[dist_idx] as usize;
719 if dist_bits == 0 {
720 self.state = InflateState::DynCopy(length, dist_base);
721 } else {
722 self.state = InflateState::DynBlockDistExt(length, dist_base, dist_bits);
723 }
724 } else {
725 unreachable!();
726 }
727 },
728 InflateState::DynBlockDistExt(length, base, bits) => {
729 let add = read_bits!(self, csrc, bits) as usize;
730 self.state = InflateState::DynCopy(length, base + add);
731 },
732 InflateState::DynCopy(length, dist) => {
733 if self.output_idx + length > dst.len() {
734 let copy_size = dst.len() - self.output_idx;
735 let ret = self.lz_copy(dist, copy_size, &mut dst[self.output_idx..]);
736 if ret.is_err() {
737 self.state = InflateState::End;
738 return Err(DecompressError::InvalidData);
739 }
740 self.output_idx += copy_size;
741 self.br = csrc.br;
742 self.state = InflateState::DynCopy(length - copy_size, dist);
743 return Err(DecompressError::OutputFull);
744 }
745 let ret = self.lz_copy(dist, length, &mut dst[self.output_idx..]);
746 if ret.is_err() {
747 self.state = InflateState::End;
748 return Err(DecompressError::InvalidData);
749 }
750 self.output_idx += length;
751 self.state = InflateState::DynBlock;
752 }
753 InflateState::End => {
754 return Ok(0);
755 },
756 }
757 }
758 }
de161d26
KS
759 ///! Resets decoder state.
760 pub fn reset(&mut self) {
761 self.bpos = 0;
762 self.output_idx = 0;
763 self.full_pos = 0;
764 self.state = InflateState::Start;
765 }
766
0443d0c5
KS
767 ///! Decompresses input data into output returning the uncompressed data length.
768 pub fn uncompress(src: &[u8], dst: &mut [u8]) -> DecompressResult<usize> {
769 let mut inflate = Self::new();
0c9b706a 770 inflate.decompress_data(src, dst, false)
0443d0c5
KS
771 }
772}
773
b36f412c
KS
774impl Default for Inflate {
775 fn default() -> Self {
776 Self::new()
777 }
778}
779
0443d0c5
KS
780fn lengths_to_codes(lens: &[u8], codes: &mut [ShortCodebookDesc]) -> DecompressResult<()> {
781 let mut bits = [0u32; 32];
782 let mut pfx = [0u32; 33];
783 for len in lens.iter() {
784 let len = *len as usize;
785 if len >= bits.len() {
786 return Err(DecompressError::InvalidHeader);
787 }
788 bits[len] += 1;
789 }
790 bits[0] = 0;
791 let mut code = 0;
792 for i in 0..bits.len() {
793 code = (code + bits[i]) << 1;
794 pfx[i + 1] = code;
795 }
796
797 for (len, codes) in lens.iter().zip(codes.iter_mut()) {
798 let len = *len as usize;
799 if len != 0 {
800 let bits = len as u8;
801 *codes = ShortCodebookDesc { code: reverse_bits(pfx[len], bits), bits };
802 pfx[len] += 1;
803 } else {
804 *codes = ShortCodebookDesc { code: 0, bits: 0 };
805 }
806 }
e65c0040 807
0443d0c5
KS
808 Ok(())
809}
810
811struct GzipCRC32 {
812 tab: [u32; 256],
813 crc: u32,
814}
815
816impl GzipCRC32 {
b36f412c 817 #[allow(clippy::unreadable_literal)]
0443d0c5
KS
818 fn new() -> Self {
819 let mut tab = [0u32; 256];
820 for i in 0..256 {
821 let mut c = i as u32;
822 for _ in 0..8 {
823 if (c & 1) != 0 {
824 c = 0xEDB88320 ^ (c >> 1);
825 } else {
826 c >>= 1;
827 }
828 }
829 tab[i] = c;
830 }
831 Self { tab, crc: 0 }
832 }
833 fn update_crc(&mut self, src: &[u8]) {
834 let mut c = !self.crc;
835 for el in src.iter() {
836 c = self.tab[((c ^ u32::from(*el)) & 0xFF) as usize] ^ (c >> 8);
837 }
838 self.crc = !c;
839 }
840}
841
842///! Decodes input data in gzip file format (RFC 1952) returning a vector containing decoded data.
843pub fn gzip_decode(br: &mut ByteReader, skip_crc: bool) -> DecompressResult<Vec<u8>> {
844 const FLAG_HCRC: u8 = 0x02;
845 const FLAG_EXTRA: u8 = 0x04;
846 const FLAG_NAME: u8 = 0x08;
847 const FLAG_COMMENT: u8 = 0x10;
848
849 let id1 = br.read_byte()?;
850 let id2 = br.read_byte()?;
851 let cm = br.read_byte()?;
852 let flg = br.read_byte()?;
853 let _mtime = br.read_u32le()?;
854 let _xfl = br.read_byte()?;
855 let _os = br.read_byte()?;
856 if id1 != 0x1F || id2 != 0x8B || cm != 8 {
857 return Err(DecompressError::InvalidHeader);
858 }
859
860 if (flg & FLAG_EXTRA) != 0 {
861 let xlen = br.read_u16le()? as usize;
862 br.read_skip(xlen)?;
863 }
864 if (flg & FLAG_NAME) != 0 {
865 loop {
866 let b = br.read_byte()?;
867 if b == 0 {
868 break;
869 }
870 }
871 }
872 if (flg & FLAG_COMMENT) != 0 {
873 loop {
874 let b = br.read_byte()?;
875 if b == 0 {
876 break;
877 }
878 }
879 }
880 let _hcrc = if (flg & FLAG_HCRC) != 0 {
881 br.read_u16le()?
882 } else {
883 0
884 };
885 if (flg & 0xE0) != 0 {
886 return Err(DecompressError::Unsupported);
887 }
888
889 let mut output: Vec<u8> = Vec::new();
890 let mut tail = [0u8; 8];
891 let mut inblk = [0u8; 1024];
892 let mut oblk = [0u8; 4096];
893 let mut inflate = Inflate::new();
894 let mut checker = GzipCRC32::new();
895
896 loop {
897 let ret = br.read_buf_some(&mut inblk);
898 if let Err(ByteIOError::EOF) = ret {
899 break;
900 }
901 let inlen = match ret {
902 Ok(val) => val,
903 Err(_) => return Err(DecompressError::IOError),
904 };
905 let mut repeat = false;
906 loop {
907 let ret = inflate.decompress_data(&inblk[..inlen], &mut oblk, repeat);
908 match ret {
909 Ok(outlen) => {
910 checker.update_crc(&oblk[..outlen]);
911 output.extend_from_slice(&oblk[..outlen]);
912 break;
913 },
914 Err(DecompressError::ShortData) => {
915 break;
916 },
917 Err(DecompressError::OutputFull) => {
918 repeat = true;
919 checker.update_crc(&oblk);
920 output.extend_from_slice(&oblk);
921 },
922 Err(err) => {
923 return Err(err);
924 },
925 }
926 }
927 // Save last 8 bytes for CRC and size.
928 if inlen >= 8 {
929 tail.copy_from_slice(&inblk[inlen - 8..][..8]);
930 } else {
931 let shift_len = 8 - inlen;
932 for i in 0..shift_len {
933 tail[i] = tail[i + inlen];
934 }
935 for i in shift_len..8 {
936 tail[i] = inblk[i - shift_len];
937 }
938 }
939 }
940 if !skip_crc {
941 if !inflate.is_finished() { println!("???"); }
942 let crc = read_u32le(&tail[0..4])?;
943 let size = read_u32le(&tail[4..8])?;
944 if size != (output.len() as u32) {
945 return Err(DecompressError::CRCError);
946 }
947 if crc != checker.crc {
948 return Err(DecompressError::CRCError);
949 }
950 }
951
952 Ok(output)
953}
954
f8cdb949
KS
955#[derive(Clone,Copy,Default)]
956struct Token {
957 sym: u16,
958 distsym: u8,
959 len: u16,
960 dist: u16,
961}
962
963const TOKEN_EOB: Token = Token { sym: 256, distsym: 0, len: 0, dist: 0 };
964
965impl Token {
966 fn from_literal(sym: u8) -> Self {
967 Self {
968 sym: u16::from(sym),
969 distsym: 0,
970 dist: 0,
971 len: 0,
972 }
973 }
974 fn from_match(dist: u16, len: u16) -> Self {
975 let sym = match len {
976 3..= 10 => 257 + len - 3,
977 11..= 18 => 265 + (len - 11) / 2,
978 19..= 34 => 269 + (len - 19) / 4,
979 35..= 66 => 273 + (len - 35) / 8,
980 67..=130 => 277 + (len - 67) / 16,
981 131..=257 => 281 + (len - 131) / 32,
982 _ => 285,
983 };
984 let distsym = if dist <= 4 {
985 (dist - 1) as u8
986 } else {
987 let bits = 16 - (dist - 1).leading_zeros();
988 (bits as u8) * 2 - 2 + if ((dist - 1) & (1 << (bits - 2))) != 0 { 1 } else { 0 }
989 };
990 Self {
991 sym, distsym, len, dist
992 }
993 }
994}
995
996fn add_codes(lens: &[u8], stats: &mut [u32], toks: &mut Vec<(u8, u8)>) {
997 let mut last = 42;
998 let mut lcount = 0;
999
1000 for &len in lens.iter() {
1001 if len == last {
1002 lcount += 1;
1003 } else {
1004 if last == 0 {
1005 while lcount > 10 {
1006 let run = lcount.min(138);
1007 stats[18] += 1;
1008 toks.push((18, run - 11));
1009 lcount -= run;
1010 }
1011 if lcount >= 3 {
1012 stats[17] += 1;
1013 toks.push((17, lcount - 3));
1014 lcount = 0;
1015 }
1016 for _ in 0..lcount {
1017 stats[0] += 1;
1018 toks.push((0, 0));
1019 }
1020 } else {
1021 while lcount >= 3 {
1022 let run = lcount.min(6);
1023 stats[16] += 1;
1024 toks.push((16, run - 3));
1025 lcount -= run;
1026 }
1027 for _ in 0..lcount {
1028 stats[last as usize] += 1;
1029 toks.push((last, 0));
1030 }
1031 }
1032 stats[len as usize] += 1;
1033 toks.push((len, 0));
1034 last = len;
1035 lcount = 0;
1036 }
1037 }
1038 if lcount > 0 {
1039 if last == 0 {
1040 while lcount > 10 {
1041 let run = lcount.min(138);
1042 stats[18] += 1;
1043 toks.push((18, run - 11));
1044 lcount -= run;
1045 }
1046 if lcount >= 3 {
1047 stats[17] += 1;
1048 toks.push((17, lcount - 3));
1049 lcount = 0;
1050 }
1051 for _ in 0..lcount {
1052 stats[0] += 1;
1053 toks.push((0, 0));
1054 }
1055 } else {
1056 while lcount >= 3 {
1057 let run = lcount.min(6);
1058 stats[16] += 1;
1059 toks.push((16, run - 3));
1060 lcount -= run;
1061 }
1062 for _ in 0..lcount {
1063 stats[last as usize] += 1;
1064 toks.push((last, 0));
1065 }
1066 }
1067 }
1068}
1069
1070///! Deflate stream writer.
1071pub struct DeflateWriter {
1072 dst: Vec<u8>,
1073 bits: u8,
1074 bbuf: u32,
1075}
1076
1077impl DeflateWriter {
1078 ///! Creates a new instance of `DeflateWriter` for a provided output.
1079 pub fn new(dst: Vec<u8>) -> Self {
1080 Self {
1081 dst,
1082 bits: 0,
1083 bbuf: 0,
1084 }
1085 }
1086 fn align(&mut self) {
1087 if (self.bits & 7) != 0 {
1088 self.bits += 8 - (self.bits & 7);
1089 }
1090 }
1091 fn flush(&mut self) {
1092 while self.bits >= 8 {
1093 self.dst.push(self.bbuf as u8);
1094 self.bbuf >>= 8;
1095 self.bits -= 8;
1096 }
1097 }
1098 fn write(&mut self, val: u16, len: u8) {
1099 self.flush();
1100 self.bbuf |= u32::from(val) << self.bits;
1101 self.bits += len;
1102 }
1103 ///! Finishes writing the stream and returns the output vector.
1104 pub fn end(mut self) -> Vec<u8> {
1105 self.flush();
1106 if self.bits > 0 {
1107 self.dst.push(self.bbuf as u8);
1108 }
1109 self.dst
1110 }
1111
1112 fn write_codes(&mut self, codes: &CodeHuff, dists: &DistHuff) {
1113 let mut stats = [0u32; 19];
1114 let mut toks = Vec::with_capacity(NUM_LITERALS + NUM_DISTS);
1115 let mut cw = [0u16; 19];
1116 let mut cl = [0u8; 19];
1117 let mut nc = 0;
1118
1119 add_codes(&codes.lens[..codes.num_codes], &mut stats, &mut toks);
1120 add_codes(&dists.lens[..dists.num_codes], &mut stats, &mut toks);
1121
1122 gen_tree(&mut cw, &mut cl, &mut nc, &mut stats, 7);
1123
1124 nc = cw.len();
1125 for &idx in LEN_RECODE.iter().rev() {
1126 if cl[idx] == 0 {
1127 nc -= 1;
1128 } else {
1129 break;
1130 }
1131 }
1132 if nc < 4 {
1133 nc = 4;
1134 }
1135 self.write((nc - 4) as u16, 4);
1136 for &idx in LEN_RECODE.iter().take(nc) {
1137 self.write(u16::from(cl[idx]), 3);
1138 }
1139 for &(sym, add) in toks.iter() {
1140 self.write(cw[sym as usize], cl[sym as usize]);
1141 match sym {
1142 16 => self.write(u16::from(add), 2),
1143 17 => self.write(u16::from(add), 3),
1144 18 => self.write(u16::from(add), 7),
1145 _ => {},
1146 };
1147 }
1148 }
1149 fn write_tokens(&mut self, src: &[Token], codes: &CodeHuff, dists: &DistHuff) {
1150 for &tok in src.iter() {
1151 self.write(codes.codes[tok.sym as usize], codes.lens[tok.sym as usize]);
1152 if tok.sym > 256 {
1153 self.write_len_bits(tok.len);
1154 self.write(dists.codes[tok.distsym as usize], dists.lens[tok.distsym as usize]);
1155 self.write_dist_bits(tok.dist);
1156 }
1157 }
1158 }
1159 fn write_len_bits(&mut self, len: u16) {
1160 let llen = len - 3;
1161 if llen >= 8 && llen < 255 {
1162 let bits = (16 - llen.leading_zeros() - 3) as u8;
1163 self.write(llen & ((1 << bits) - 1), bits);
1164 }
1165 }
1166 fn write_dist_bits(&mut self, dist: u16) {
1167 let ddist = dist - 1;
1168 if dist >= 4 {
1169 let bits = (16 - ddist.leading_zeros() - 2) as u8;
1170 self.write(ddist & ((1 << bits) - 1), bits);
1171 }
1172 }
1173}
1174
1175struct CodeHuff {
1176 is_fixed: bool,
1177 stats: [u32; NUM_LITERALS],
1178 codes: [u16; NUM_LITERALS],
1179 lens: [u8; NUM_LITERALS],
1180 num_codes: usize,
1181}
1182
1183impl CodeHuff {
1184 fn new(is_fixed: bool) -> Self {
1185 Self {
1186 is_fixed,
1187 stats: [0; NUM_LITERALS],
1188 codes: [0; NUM_LITERALS],
1189 lens: [0; NUM_LITERALS],
1190 num_codes: NUM_LITERALS,
1191 }
1192 }
1193 fn make_codes(&mut self, src: &[Token]) {
1194 if self.is_fixed {
1195 for i in 0..=143 {
1196 self.codes[i] = reverse_bits((i + 0x30) as u32, 8) as u16;
1197 self.lens[i] = 8;
1198 }
1199 for i in 144..=255 {
1200 self.codes[i] = reverse_bits((i + 0x100) as u32, 9) as u16;
1201 self.lens[i] = 9;
1202 }
1203 for i in 256..=279 {
1204 self.codes[i] = reverse_bits((i & 0x1F) as u32, 7) as u16;
1205 self.lens[i] = 7;
1206 }
1207 for i in 280..NUM_LITERALS {
1208 self.codes[i] = reverse_bits((i - 280 + 0xC0) as u32, 8) as u16;
1209 self.lens[i] = 8;
1210 }
1211 } else {
1212 for &tok in src.iter() {
1213 self.stats[tok.sym as usize] += 1;
1214 }
1215 gen_tree(&mut self.codes, &mut self.lens, &mut self.num_codes, &mut self.stats, 15);
1216 if self.num_codes < 257 {
1217 self.num_codes = 257;
1218 }
1219 }
1220 }
1221}
1222
1223struct DistHuff {
1224 is_fixed: bool,
1225 stats: [u32; NUM_DISTS],
1226 codes: [u16; NUM_DISTS],
1227 lens: [u8; NUM_DISTS],
1228 num_codes: usize,
1229}
1230
1231impl DistHuff {
1232 fn new(is_fixed: bool) -> Self {
1233 Self {
1234 is_fixed,
1235 stats: [0; NUM_DISTS],
1236 codes: [0; NUM_DISTS],
1237 lens: [0; NUM_DISTS],
1238 num_codes: NUM_DISTS,
1239 }
1240 }
1241 fn make_codes(&mut self, src: &[Token]) {
1242 if self.is_fixed {
1243 for i in 0..NUM_DISTS {
1244 self.codes[i] = reverse_bits(i as u32, 5) as u16;
1245 self.lens[i] = 5;
1246 }
1247 } else {
1248 for &tok in src.iter() {
1249 if tok.sym > 256 {
1250 self.stats[tok.distsym as usize] += 1;
1251 }
1252 }
1253 gen_tree(&mut self.codes, &mut self.lens, &mut self.num_codes, &mut self.stats, 15);
1254 if self.num_codes < 1 {
1255 self.num_codes = 1;
1256 }
1257 }
1258 }
1259}
1260
1261#[derive(Clone,Copy,Default)]
1262struct Node {
1263 sym: u16,
1264 w: u16,
1265 idx0: u16,
1266 idx1: u16,
1267}
1268
1269const NODE_SYM: u16 = 65500;
1270
1271struct Tree {
1272 nodes: [Node; NUM_LITERALS * 2],
1273 nnodes: usize,
1274}
1275
1276impl Tree {
1277 fn new() -> Self {
1278 Self {
1279 nodes: [Node::default(); NUM_LITERALS * 2],
1280 nnodes: 0,
1281 }
1282 }
1283 fn insert(&mut self, val: Node) {
1284 let mut idx = self.nnodes;
1285 for (i, nn) in self.nodes[..self.nnodes].iter().enumerate() {
1286 if nn.w > val.w {
1287 idx = i;
1288 break;
1289 }
1290 }
1291 if idx < self.nnodes {
1292 for i in (idx..self.nnodes).rev() {
1293 self.nodes[i + 1] = self.nodes[i];
1294 }
1295 }
1296 self.nodes[idx] = val;
1297 self.nnodes += 1;
1298 }
1299 fn trim(&mut self) {
1300 let mut start = self.nnodes;
1301 for (i, n) in self.nodes[..self.nnodes].iter().enumerate() {
1302 if n.w != 0 {
1303 start = i;
1304 break;
1305 }
1306 }
1307 if start != 0 {
1308 for i in 0..self.nnodes - start {
1309 self.nodes[i] = self.nodes[i + start];
1310 }
1311 self.nnodes -= start;
1312 }
1313 }
1314 fn build(&mut self) {
1315 if self.nnodes == 1 {
1316 self.nodes[0].w = 1;
1317 return;
1318 }
1319 let mut start = 0;
1320 while start + 1 < self.nnodes {
1321 let nn1 = self.nodes[start];
1322 let nn2 = self.nodes[start + 1];
1323 let n = Node {
1324 sym: NODE_SYM,
1325 w: nn1.w + nn2.w,
1326 idx0: start as u16,
1327 idx1: (start + 1) as u16,
1328 };
1329 self.nodes[start].w = 0;
1330 self.nodes[start + 1].w = 0;
1331 start += 2;
1332 self.insert(n);
1333 }
1334 if self.nnodes > 1 {
1335 self.assign_len(self.nnodes - 1, 0);
1336 }
1337 }
1338 fn assign_len(&mut self, idx: usize, len: u16) {
1339 if self.nodes[idx].sym == NODE_SYM {
1340 self.assign_len(self.nodes[idx].idx0 as usize, len + 1);
1341 self.assign_len(self.nodes[idx].idx1 as usize, len + 1);
1342 } else {
1343 self.nodes[idx].w = len;
1344 }
1345 }
1346}
1347
1348fn gen_tree(codes: &mut [u16], lens: &mut [u8], num_codes: &mut usize, stats: &mut [u32], max_bits: u8) {
1349 let mut tot_w = 0;
1350 for &w in stats.iter() {
1351 tot_w += w;
1352 }
1353 if tot_w == 0 {
1354 codes[0] = 0;
1355 lens[0] = 0;
1356 *num_codes = 0;
1357 return;
1358 }
1359 while tot_w > (1 << max_bits) {
1360 for w in stats.iter_mut() {
1361 *w = (*w + 1) >> 1;
1362 }
1363 tot_w = 0;
1364 for &w in stats.iter() {
1365 tot_w += w;
1366 }
1367 }
1368 let mut tree = Tree::new();
1369 for (sym, &w) in stats.iter().enumerate() {
1370 tree.insert(Node{ sym: sym as u16, w: w as u16, idx0: 64000, idx1: 64000 });
1371 }
1372 tree.trim();
1373 tree.build();
1374
1375 for n in tree.nodes[..tree.nnodes].iter() {
1376 if n.sym != NODE_SYM {
1377 lens[n.sym as usize] = n.w as u8;
1378 }
1379 }
1380 lengths_to_codes16(lens, codes);
1381 let mut sz = codes.len();
1382 for &len in lens.iter().rev() {
1383 if len != 0 {
1384 break;
1385 }
1386 sz -= 1;
1387 }
1388 *num_codes = sz;
1389}
1390
1391fn lengths_to_codes16(lens: &[u8], codes: &mut [u16]) {
1392 let mut bits = [0u32; 32];
1393 let mut pfx = [0u32; 33];
1394 for len in lens.iter() {
1395 let len = *len as usize;
1396 bits[len] += 1;
1397 }
1398 bits[0] = 0;
1399 let mut code = 0;
1400 for i in 0..bits.len() {
1401 code = (code + bits[i]) << 1;
1402 pfx[i + 1] = code;
1403 }
1404
1405 for (len, codes) in lens.iter().zip(codes.iter_mut()) {
1406 let len = *len as usize;
1407 if len != 0 {
1408 let bits = len as u8;
1409 *codes = reverse_bits(pfx[len], bits) as u16;
1410 pfx[len] += 1;
1411 } else {
1412 *codes = 0;
1413 }
1414 }
1415}
1416
1417trait LZParse {
1418 fn parse(&mut self, src: &[u8], dst: &mut Vec<Token>);
1419}
1420
1421struct NoParser {}
1422impl LZParse for NoParser {
1423 fn parse(&mut self, src: &[u8], dst: &mut Vec<Token>) {
1424 dst.reserve(src.len());
1425 for &b in src.iter() {
1426 dst.push(Token::from_literal(b));
1427 }
1428 dst.push(TOKEN_EOB);
1429 }
1430}
1431
1432fn check_match(src1: &[u8], src2: &[u8]) -> u16 {
1433 let mut len = 0;
1434 for (&a, &b) in src1.iter().zip(src2.iter()) {
1435 if a != b {
1436 break;
1437 }
1438 len += 1;
1439 }
1440 len
1441}
1442
1443const HASH_SIZE: usize = 4096;
1444const MAX_MATCH_LEN: usize = 258;
1445const WINDOW_SIZE: usize = 32768 - MAX_MATCH_LEN;
1446const NONEXT: usize = WINDOW_SIZE * 2;
1447
1448struct MatchFinder<'a> {
1449 src: &'a [u8],
1450 pos: usize,
1451 hstart: [usize; HASH_SIZE],
1452 hend: [usize; HASH_SIZE],
1453 hnext: [usize; WINDOW_SIZE * 3],
1454}
1455
1456impl<'a> MatchFinder<'a> {
1457 fn new(src: &'a [u8]) -> Self {
1458 let mut obj = Self {
1459 src,
1460 pos: 0,
1461 hstart: [0; HASH_SIZE],
1462 hend: [0; HASH_SIZE],
1463 hnext: [0; WINDOW_SIZE * 3],
1464 };
1465 obj.build_hash();
1466 obj
1467 }
1468 fn hash(src: &[u8]) -> usize {
1469 let _ = src[2];
1470 (((u16::from(src[0]) << 10) ^ (u16::from(src[1]) << 5) ^ u16::from(src[2])) & ((HASH_SIZE as u16) - 1)) as usize
1471 }
1472 fn build_hash(&mut self) {
1473 for el in self.hstart.iter_mut() { *el = NONEXT; }
1474 for el in self.hend.iter_mut() { *el = NONEXT; }
1475 for el in self.hnext.iter_mut() { *el = NONEXT; }
1476 if self.pos + 3 >= self.src.len() {
1477 return;
1478 }
1479 let end = (self.src.len() - 3).min(self.pos + NONEXT);
1480 for i in (self.pos .. end).rev() {
1481 let key = Self::hash(&self.src[i..]);
1482 if self.hstart[key] == NONEXT {
1483 self.hstart[key] = i;
1484 self.hend[key] = i;
1485 self.hnext[key] = NONEXT;
1486 } else {
1487 self.hnext[self.hend[key]] = i;
1488 self.hend[key] = i;
1489 }
1490 }
1491 }
1492 fn find_match(&mut self) -> (u16, u16) {
1493 if self.pos == 0 || self.pos + 3 > self.src.len() {
1494 return (0, 0);
1495 }
1496 let key = Self::hash(&self.src[self.pos..]) as usize;
1497
1498 let mut best_pos = 0;
1499 let mut best_len = 0;
1500 let mut idx = self.hstart[key];
1501 while idx != NONEXT && idx + WINDOW_SIZE > self.pos {
1502 if idx < self.pos {
1503 let cur_len = check_match(&self.src[self.pos..], &self.src[idx..]);
1504 if cur_len > best_len {
1505 best_len = cur_len;
1506 best_pos = self.pos - idx;
1507 if best_len >= (MAX_MATCH_LEN as u16) {
1508 return (best_pos as u16, MAX_MATCH_LEN as u16);
1509 }
1510 }
1511 }
1512 idx = self.hnext[idx];
1513 }
1514 (best_pos as u16, best_len)
1515 }
1516 fn find_all_matches(&mut self, dists: &mut [u16; MAX_MATCH_LEN + 1]) {
1517 if self.pos == 0 || self.pos + 3 > self.src.len() {
1518 return;
1519 }
1520 let key = Self::hash(&self.src[self.pos..]) as usize;
1521 let mut idx = self.hstart[key];
1522 while idx != NONEXT && idx + WINDOW_SIZE > self.pos {
1523 if idx < self.pos {
1524 let cur_len = (check_match(&self.src[self.pos..], &self.src[idx..]) as usize).min(MAX_MATCH_LEN);
1525 if cur_len > 0 && dists[cur_len] == 0 {
1526 dists[cur_len] = (self.pos - idx) as u16;
1527 }
1528 }
1529 idx = self.hnext[idx];
1530 }
1531 }
1532 fn advance(&mut self, num: usize) {
1533 self.pos += num;
1534
1535 if self.pos >= NONEXT {
1536 let (_, tail) = self.src.split_at(self.pos - WINDOW_SIZE);
1537 self.src = tail;
1538 self.pos = WINDOW_SIZE;
1539 self.build_hash();
1540 } else {
1541 for (start, end) in self.hstart.iter_mut().zip(self.hend.iter_mut()) {
1542 let mut idx = *start;
1543 while idx != NONEXT && idx + WINDOW_SIZE < self.pos {
1544 idx = self.hnext[idx];
1545 *start = idx;
1546 }
1547 if idx == NONEXT {
1548 *end = NONEXT;
1549 }
1550 }
1551 }
1552 }
1553 fn get_sym(&self) -> u8 { self.src[self.pos] }
1554 fn is_end(&self) -> bool { self.pos >= self.src.len() }
1555}
1556
1557struct GreedyParser {}
1558impl LZParse for GreedyParser {
1559 fn parse(&mut self, src: &[u8], dst: &mut Vec<Token>) {
1560 dst.reserve(src.len());
1561
1562 let mut matcher = MatchFinder::new(src);
1563 while !matcher.is_end() {
1564 let (best_pos, best_len) = matcher.find_match();
1565
1566 if best_len >= 3 {
1567 dst.push(Token::from_match(best_pos, best_len));
1568 matcher.advance(best_len as usize);
1569 } else {
1570 dst.push(Token::from_literal(matcher.get_sym()));
1571 matcher.advance(1);
1572 }
1573 }
1574 dst.push(TOKEN_EOB);
1575 }
1576}
1577
1578struct LazyParser {}
1579impl LZParse for LazyParser {
1580 fn parse(&mut self, src: &[u8], dst: &mut Vec<Token>) {
1581 dst.reserve(src.len());
1582
1583 let mut matcher = MatchFinder::new(src);
1584 while !matcher.is_end() {
1585 let (best_pos, best_len) = matcher.find_match();
1586 if best_len >= 3 {
1587 let last_sym = matcher.get_sym();
1588 matcher.advance(1);
1589 if !matcher.is_end() {
1590 let (best_pos1, best_len1) = matcher.find_match();
1591 if best_len1 > best_len + 1 {
1592 dst.push(Token::from_literal(last_sym));
1593 dst.push(Token::from_match(best_pos1, best_len1));
1594 matcher.advance(best_len1 as usize);
1595 continue;
1596 }
1597 }
1598 dst.push(Token::from_match(best_pos, best_len));
1599 matcher.advance((best_len - 1) as usize);
1600 } else {
1601 dst.push(Token::from_literal(matcher.get_sym()));
1602 matcher.advance(1);
1603 }
1604 }
1605 dst.push(TOKEN_EOB);
1606 }
1607}
1608
1609#[derive(Clone,Copy)]
1610struct TNode {
1611 price: u32,
1612 dist: u16,
1613 link: usize,
1614}
1615
1616impl Default for TNode {
1617 fn default() -> Self {
1618 Self {
1619 price: std::u32::MAX,
1620 dist: 0,
1621 link: 0,
1622 }
1623 }
1624}
1625
1626struct OptimalParser {
1627 trellis: Vec<TNode>,
1628}
1629impl OptimalParser {
1630 fn new() -> Self { Self::default() }
1631 fn sym_price(_sym: u8) -> u32 { 9 }
1632 fn match_price(dist: u16, _len: u16) -> u32 {
1633 if dist <= 4 {
1634 9 + 5
1635 } else {
1636 let bits = 16 - (dist - 1).leading_zeros();
1637 9 + 3 + bits
1638 }
1639 }
1640}
1641impl Default for OptimalParser {
1642 fn default() -> Self {
1643 Self {
1644 trellis: Vec::with_capacity(WINDOW_SIZE),
1645 }
1646 }
1647}
1648impl LZParse for OptimalParser {
1649 fn parse(&mut self, src: &[u8], dst: &mut Vec<Token>) {
1650 if src.is_empty() {
1651 dst.push(TOKEN_EOB);
1652 return;
1653 }
1654 dst.reserve(src.len());
1655
1656 self.trellis.truncate(0);
1657 self.trellis.reserve(src.len() + 1);
1658 for _ in 0..=src.len() {
1659 self.trellis.push(TNode::default());
1660 }
1661 self.trellis[0].price = 0;
1662
1663 let mut matcher = MatchFinder::new(src);
1664 for i in 0..self.trellis.len() - 1 {
1665 let mut dists = [0; MAX_MATCH_LEN + 1];
1666 matcher.find_all_matches(&mut dists);
1667
1668 let sym = matcher.get_sym();
1669 let lprice = Self::sym_price(sym) + self.trellis[i].price;
1670 if self.trellis[i + 1].price > lprice {
1671 self.trellis[i + 1].price = lprice;
1672 self.trellis[i + 1].link = i;
1673 }
1674 for (len, &dist) in dists.iter().enumerate() {
1675 if dist != 0 {
1676 let mprice = Self::match_price(dist, len as u16) + self.trellis[i].price;
1677 if self.trellis[i + len].price > mprice {
1678 self.trellis[i + len].price = mprice;
1679 self.trellis[i + len].link = i;
1680 self.trellis[i].dist = dist;
1681 }
1682 }
1683 }
1684
1685 matcher.advance(1);
1686 }
1687 let mut idx = self.trellis.len() - 1;
1688 let mut nidx = self.trellis[idx].link;
1689 while idx > 0 {
1690 let oidx = idx;
1691 idx = nidx;
1692 nidx = self.trellis[idx].link;
1693 self.trellis[idx].link = oidx;
1694 }
1695
1696 let mut idx = 0;
1697 while idx < self.trellis.len() - 1 {
1698 let len = self.trellis[idx].link - idx;
1699 if len == 1 {
1700 dst.push(Token::from_literal(src[idx]));
1701 } else {
1702 dst.push(Token::from_match(self.trellis[idx].dist, len as u16));
1703 }
1704 idx = self.trellis[idx].link;
1705 }
1706
1707 dst.push(TOKEN_EOB);
1708 }
1709}
1710
1711///! Deflate compression mode.
1712#[derive(Clone,Copy,Debug,PartialEq)]
1713pub enum DeflateMode {
1714 ///! No compression.
1715 NoCompr,
1716 ///! Fast compression.
1717 Fast,
1718 ///! Still fast but better compression.
1719 Better,
1720 ///! Slow but the best compression.
1721 Best,
1722}
1723
1724#[derive(Clone,Copy,Debug,PartialEq)]
1725enum Mode {
1726 Copy,
1727 Fixed,
1728 Dynamic,
1729}
1730
1731const MAX_BLOCK_SIZE: usize = 65535;
1732
1733///! Deflate stream compressor.
1734pub struct Deflate {
1735 mode: Mode,
1736 tokens: Vec<Token>,
1737 srcbuf: [u8; MAX_BLOCK_SIZE],
1738 ssize: usize,
1739 sum1: u32,
1740 sum2: u32,
1741 zlib_mode: bool,
9f838842 1742 parser: Box<dyn LZParse + Send>,
f8cdb949
KS
1743}
1744
1745impl Deflate {
1746 ///! Creates a new instance of `Deflate`.
1747 pub fn new(mode: DeflateMode) -> Self {
1748 let (mode, parser) = match mode {
9f838842
KS
1749 DeflateMode::NoCompr => (Mode::Copy, Box::new(NoParser{}) as Box<dyn LZParse + Send>),
1750 DeflateMode::Fast => (Mode::Fixed, Box::new(GreedyParser{}) as Box<dyn LZParse + Send>),
1751 DeflateMode::Better => (Mode::Dynamic, Box::new(LazyParser{}) as Box<dyn LZParse + Send>),
1752 DeflateMode::Best => (Mode::Dynamic, Box::new(OptimalParser::new()) as Box<dyn LZParse + Send>),
f8cdb949
KS
1753 };
1754 Self {
1755 mode, parser,
1756 tokens: Vec::with_capacity(MAX_BLOCK_SIZE),
1757 srcbuf: [0; MAX_BLOCK_SIZE],
1758 ssize: 0,
1759 sum1: 1,
1760 sum2: 0,
1761 zlib_mode: false,
1762 }
1763 }
1764 ///! Writes zlib stream header.
1765 pub fn write_zlib_header(&mut self, wr: &mut DeflateWriter) {
1766 wr.write(8, 4);
1767 wr.write(7, 4);
1768 let level = match self.mode {
1769 Mode::Copy => 0x01,
1770 Mode::Fixed => 0x5E,
1771 Mode::Dynamic => 0x9C,
1772 // 0xDA for the strongest one
1773 };
1774 wr.write(level, 8);
1775 self.zlib_mode = true;
1776 }
1777 fn write_zlib_footer(&self, wr: &mut DeflateWriter) {
1778 wr.align();
1779 wr.write((self.sum2 >> 8) as u16, 8);
1780 wr.write((self.sum2 & 0xFF) as u16, 8);
1781 wr.write((self.sum1 >> 8) as u16, 8);
1782 wr.write((self.sum1 & 0xFF) as u16, 8);
1783 }
1784 ///! Queues data for compression.
1785 ///!
1786 ///! The data might be not actually compressed until [`compress_end`] is called.
1787 ///!
1788 ///! [`compress_end`]: ./struct.Deflate.html#method.compress_end
1789 pub fn compress(&mut self, src: &[u8], wr: &mut DeflateWriter) {
1790 let mut src = src;
1791 while !src.is_empty() {
1792 let clen = src.len().min(MAX_BLOCK_SIZE - self.ssize);
1793 let (head, tail) = src.split_at(clen);
1794 src = tail;
1795 self.srcbuf[self.ssize..][..clen].copy_from_slice(head);
1796 self.ssize += clen;
1797 if self.ssize == MAX_BLOCK_SIZE {
1798 self.do_block(wr, false);
1799 }
1800 }
1801 }
1802 ///! Tells the encoder to finish data compression.
1803 ///!
1804 ///! Complete data will be output after this call.
1805 pub fn compress_end(&mut self, wr: &mut DeflateWriter) {
1806 if self.ssize > 0 {
1807 self.do_block(wr, true);
1808 } else {
1809 wr.write(1, 1);
1810 wr.write(1, 2);
1811 wr.write(0, 7); //static EOF sym
1812 }
1813 if self.zlib_mode {
1814 self.write_zlib_footer(wr);
1815 }
1816 }
1817 fn do_block(&mut self, wr: &mut DeflateWriter, final_block: bool) {
1818 const CRC_BASE: u32 = 65521;
1819 for &b in self.srcbuf[..self.ssize].iter() {
1820 self.sum1 += u32::from(b);
1821 if self.sum1 >= CRC_BASE {
1822 self.sum1 -= CRC_BASE;
1823 }
1824 self.sum2 += self.sum1;
1825 if self.sum2 >= CRC_BASE {
1826 self.sum2 -= CRC_BASE;
1827 }
1828 }
1829 match self.mode {
1830 Mode::Copy => {
1831 wr.write(final_block as u16, 1);
1832 wr.write(0, 2);
1833 wr.align();
1834 wr.write(self.ssize as u16, 16);
1835 wr.write(!self.ssize as u16, 16);
1836 for &b in self.srcbuf[..self.ssize].iter() {
1837 wr.write(u16::from(b), 8);
1838 }
1839 },
1840 Mode::Fixed => {
1841 wr.write(final_block as u16, 1);
1842 wr.write(1, 2);
1843 self.tokens.truncate(0);
1844 self.parser.parse(&self.srcbuf[..self.ssize], &mut self.tokens);
1845 let mut codes = CodeHuff::new(true);
1846 codes.make_codes(&self.tokens);
1847 let mut dists = DistHuff::new(true);
1848 dists.make_codes(&self.tokens);
1849 wr.write_tokens(&self.tokens, &codes, &dists);
1850 },
1851 Mode::Dynamic => {
1852 wr.write(final_block as u16, 1);
1853 wr.write(2, 2);
1854 self.tokens.truncate(0);
1855 self.parser.parse(&self.srcbuf[..self.ssize], &mut self.tokens);
1856 let mut codes = CodeHuff::new(false);
1857 codes.make_codes(&self.tokens);
1858 let mut dists = DistHuff::new(false);
1859 dists.make_codes(&self.tokens);
1860 wr.write((codes.num_codes - 257) as u16, 5);
1861 wr.write((dists.num_codes - 1) as u16, 5);
1862 wr.write_codes(&codes, &dists);
1863 wr.write_tokens(&self.tokens, &codes, &dists);
1864 },
1865 }
1866 self.ssize = 0;
1867 }
1868}
1869
0443d0c5
KS
1870#[cfg(test)]
1871mod test {
1872 use super::*;
1873
1874 #[test]
1875 fn test_inflate1() {
1876 const TEST_DATA: &[u8] = &[
1877 0xF3, 0x48, 0xCD, 0xC9, 0xC9, 0xD7, 0x51, 0x28,
1878 0xCF, 0x2F, 0xCA, 0x49, 0x51, 0x04, 0x00 ];
1879 const TEST_REF: &[u8] = b"Hello, world!";
1880 let mut dst_buf = [0u8; 13];
1881 let len = Inflate::uncompress(TEST_DATA, &mut dst_buf).unwrap();
1882 assert_eq!(len, 13);
1883 for i in 0..len {
1884 assert_eq!(dst_buf[i], TEST_REF[i]);
1885 }
1886 }
1887 #[test]
1888 fn test_inflate2() {
1889 const TEST_DATA3: &[u8] = &[ 0x4B, 0x4C, 0x44, 0x80, 0x24, 0x54, 0x80, 0x2C, 0x06, 0x00 ];
1890 const TEST_REF3: &[u8] = b"aaaaaaaaaaaabbbbbbbbbbbbbbbaaaaabbbbbbb";
1891 let mut dst_buf = [0u8; 39];
1892
1893 let mut inflate = Inflate::new();
1894 let mut output_chunk = [0u8; 7];
1895 let mut output_pos = 0;
1896 for input in TEST_DATA3.chunks(3) {
1897 let mut repeat = false;
1898 loop {
1899 let ret = inflate.decompress_data(input, &mut output_chunk, repeat);
1900 match ret {
1901 Ok(len) => {
1902 for i in 0..len {
1903 dst_buf[output_pos + i] = output_chunk[i];
1904 }
1905 output_pos += len;
1906 break;
1907 },
1908 Err(DecompressError::ShortData) => {
1909 break;
1910 },
1911 Err(DecompressError::OutputFull) => {
1912 repeat = true;
1913 for i in 0..output_chunk.len() {
1914 dst_buf[output_pos + i] = output_chunk[i];
1915 }
1916 output_pos += output_chunk.len();
1917 },
1918 _ => {
1919 panic!("decompress error {:?}", ret.err().unwrap());
1920 },
1921 }
1922 }
1923 }
1924
1925 assert_eq!(output_pos, dst_buf.len());
1926 for i in 0..output_pos {
1927 assert_eq!(dst_buf[i], TEST_REF3[i]);
1928 }
1929 }
1930 #[test]
1931 fn test_inflate3() {
1932 const TEST_DATA: &[u8] = &[
1933 0x1F, 0x8B, 0x08, 0x08, 0xF6, 0x7B, 0x90, 0x5E, 0x02, 0x03, 0x31, 0x2E, 0x74, 0x78, 0x74, 0x00,
1934 0xE5, 0x95, 0x4B, 0x4E, 0xC3, 0x30, 0x10, 0x40, 0xF7, 0x39, 0xC5, 0x1C, 0x00, 0x16, 0x70, 0x83,
1935 0x0A, 0xB5, 0x3B, 0xE8, 0x82, 0x5E, 0x60, 0x1A, 0x4F, 0xE2, 0x11, 0xFE, 0x44, 0x1E, 0xA7, 0x69,
1936 0x6E, 0xCF, 0x38, 0xDD, 0xB0, 0x40, 0xA2, 0x46, 0x2D, 0x20, 0x2A, 0xE5, 0xAB, 0xCC, 0xE7, 0xBD,
1937 0x49, 0xAC, 0x6C, 0x03, 0x64, 0x4B, 0xD0, 0x71, 0x92, 0x0C, 0x06, 0x67, 0x88, 0x1D, 0x3C, 0xD9,
1938 0xC4, 0x92, 0x3D, 0x4A, 0xF3, 0x3C, 0x43, 0x4E, 0x23, 0x81, 0x8B, 0x07, 0x82, 0x1E, 0xF5, 0x90,
1939 0x23, 0x78, 0x6A, 0x56, 0x30, 0x60, 0xCA, 0x89, 0x4D, 0x4F, 0xC0, 0x01, 0x10, 0x06, 0xC2, 0xA4,
1940 0xA1, 0x44, 0xCD, 0xF6, 0x54, 0x50, 0xA8, 0x8D, 0xC1, 0x9C, 0x5F, 0x71, 0x37, 0x45, 0xC8, 0x63,
1941 0xCA, 0x8E, 0xC0, 0xE8, 0x23, 0x69, 0x56, 0x9A, 0x8D, 0x5F, 0xB6, 0xC9, 0x96, 0x53, 0x4D, 0x17,
1942 0xAB, 0xB9, 0xB0, 0x49, 0x14, 0x5A, 0x0B, 0x96, 0x82, 0x7C, 0xB7, 0x6F, 0x17, 0x35, 0xC7, 0x9E,
1943 0xDF, 0x78, 0xA3, 0xF1, 0xD0, 0xA2, 0x73, 0x1C, 0x7A, 0xD8, 0x2B, 0xB3, 0x5C, 0x90, 0x85, 0xBB,
1944 0x2A, 0x14, 0x2E, 0xF7, 0xD1, 0x19, 0x48, 0x0A, 0x23, 0x57, 0x45, 0x13, 0x3E, 0xD6, 0xA0, 0xBD,
1945 0xF2, 0x11, 0x7A, 0x22, 0x21, 0xAD, 0xE5, 0x70, 0x56, 0xA0, 0x9F, 0xA5, 0xA5, 0x03, 0x85, 0x2A,
1946 0xDE, 0x92, 0x00, 0x32, 0x61, 0x10, 0xAD, 0x27, 0x13, 0x7B, 0x5F, 0x98, 0x7F, 0x59, 0x83, 0xB8,
1947 0xB7, 0x35, 0x16, 0xEB, 0x12, 0x0F, 0x1E, 0xD9, 0x14, 0x0B, 0xCF, 0xEE, 0x6D, 0x91, 0xF8, 0x93,
1948 0x6E, 0x81, 0x3F, 0x7F, 0x41, 0xA4, 0x22, 0x1F, 0xB7, 0xE6, 0x85, 0x83, 0x9A, 0xA2, 0x61, 0x12,
1949 0x0D, 0x0F, 0x6D, 0x01, 0xBD, 0xB0, 0xE8, 0x1D, 0xEC, 0xD1, 0xA0, 0xBF, 0x1F, 0x4E, 0xFB, 0x55,
1950 0xBD, 0x73, 0xDD, 0x87, 0xB9, 0x53, 0x23, 0x17, 0xD3, 0xE2, 0xE9, 0x08, 0x87, 0x42, 0xFF, 0xCF,
1951 0x26, 0x42, 0xAE, 0x76, 0xB5, 0xAE, 0x97, 0x0C, 0x18, 0x78, 0xA0, 0x24, 0xE5, 0x54, 0x0C, 0x6E,
1952 0x60, 0x52, 0x79, 0x22, 0x57, 0xF5, 0x87, 0x78, 0x78, 0x04, 0x93, 0x46, 0xEF, 0xCB, 0x98, 0x96,
1953 0x8B, 0x65, 0x00, 0xB7, 0x36, 0xBD, 0x77, 0xA8, 0xBD, 0x5A, 0xAA, 0x1A, 0x09, 0x00, 0x00
1954 ];
1955
1956 let mut mr = MemoryReader::new_read(TEST_DATA);
1957 let mut br = ByteReader::new(&mut mr);
1958 let _dst_buf = gzip_decode(&mut br, false).unwrap();
1959
1960// println!("{}", String::from_utf8_lossy(_dst_buf.as_slice()));
1961 }
f8cdb949
KS
1962 #[test]
1963 fn test_deflate_crc() {
1964 let output = Vec::with_capacity(20);
1965 let mut writer = DeflateWriter::new(output);
1966 let mut compr = Deflate::new(DeflateMode::NoCompr);
1967 compr.write_zlib_header(&mut writer);
1968 compr.compress(b"Hello, world!", &mut writer);
1969 compr.compress_end(&mut writer);
1970 let output = writer.end();
1971 assert_eq!(output.as_slice(), b"\x78\x01\x01\x0D\x00\xF2\xFFHello, world!\x20\x5E\x04\x8A");
1972 }
1973 fn deflate_test(mode: DeflateMode) {
1974 const SRC: &[u8] =
1975b"The first day of Christmas,
1976My true love sent to me
1977A partridge in a pear tree.
1978
1979The second day of Christmas,
1980My true love sent to me
1981Two turtle doves, and
1982A partridge in a pear tree.
1983
1984The third day of Christmas,
1985My true love sent to me
1986Three French hens,
1987Two turtle doves, and
1988A partridge in a pear tree.
1989
1990The fourth day of Christmas,
1991My true love sent to me
1992Four colly birds,
1993Three French hens,
1994Two turtle doves, and
1995A partridge in a pear tree.
1996
1997The fifth day of Christmas,
1998My true love sent to me
1999Five gold rings,
2000Four colly birds,
2001Three French hens,
2002Two turtle doves, and
2003A partridge in a pear tree.";
2004 let output = Vec::with_capacity(SRC.len() + 16);
2005 let mut writer = DeflateWriter::new(output);
2006 let mut compr = Deflate::new(mode);
2007 compr.write_zlib_header(&mut writer);
2008 compr.compress(SRC, &mut writer);
2009 compr.compress_end(&mut writer);
2010 let output = writer.end();
2011 let mut uncompr = vec![0u8; SRC.len()];
2012 Inflate::uncompress(&output, &mut uncompr).unwrap();
2013 assert_eq!(SRC, uncompr.as_slice());
2014 }
2015 #[test]
2016 fn test_deflate_fast() {
2017 deflate_test(DeflateMode::Fast);
2018 }
2019 #[test]
2020 fn test_deflate_better() {
2021 deflate_test(DeflateMode::Better);
2022 }
2023 #[test]
2024 fn test_deflate_best() {
2025 deflate_test(DeflateMode::Best);
2026 }
0443d0c5 2027}