1 //! Deflate format (RFC 1951) support.
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`].
5 //! [`Deflate`]: ./struct.Deflate.html
6 //! [`Inflate`]: ./struct.Inflate.html
7 //! [`gzip_decode`]: ./fn.gzip_decode.html
11 //! Decompressing full input buffer into sufficiently large output buffer:
13 //! # use nihav_core::compr::DecompressError;
14 //! use nihav_core::compr::deflate::Inflate;
16 //! # fn decompress(input: &[u8]) -> Result<(), DecompressError> {
17 //! # let mut output_buffer = [0u8; 16];
18 //! let output_length = Inflate::uncompress(input, &mut output_buffer)?;
23 //! Decompressing input chunks into portions of output:
25 //! use nihav_core::compr::DecompressError;
26 //! use nihav_core::compr::deflate::Inflate;
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;
35 //! let ret = inflate.decompress_data(src, &mut output_chunk, repeat);
37 //! Ok(len) => { // we got a buffer decoded successfully to the end
38 //! dst_buf.extend_from_slice(&output_chunk[..len]);
41 //! Err(DecompressError::ShortData) => { // this block of data was fully read
44 //! Err(DecompressError::OutputFull) => {
45 //! // the output buffer is full, flush it and continue decoding the same block
47 //! dst_buf.extend_from_slice(&output_chunk);
59 //! Compressing input buffer into zlib stream:
61 //! use nihav_core::compr::deflate::{Deflate, DeflateMode, DeflateWriter};
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();
74 use crate::options::NAOptionDefinitionType;
75 use crate::io::byteio::*;
76 use crate::io::bitreader::*;
77 use crate::io::codebook::*;
80 const NUM_LITERALS: usize = 287;
81 const NUM_DISTS: usize = 32;
83 struct FixedLenCodeReader {}
85 impl CodebookDescReader<u16> for FixedLenCodeReader {
86 fn bits(&mut self, idx: usize) -> u8 {
88 else if idx < 256 { 9 }
89 else if idx < 280 { 7 }
92 #[allow(clippy::identity_op)]
93 fn code(&mut self, idx: usize) -> u32 {
94 let base = idx as u32;
95 let bits = self.bits(idx);
96 if idx < 144 { reverse_bits(base + 0x30, bits) }
97 else if idx < 256 { reverse_bits(base + 0x190 - 144, bits) }
98 else if idx < 280 { reverse_bits(base + 0x000 - 256, bits) }
99 else { reverse_bits(base + 0xC0 - 280, bits) }
101 fn sym (&mut self, idx: usize) -> u16 { idx as u16 }
102 fn len(&mut self) -> usize { NUM_LITERALS + 1 }
105 #[derive(Clone,Copy,Default)]
106 struct BitReaderState {
112 struct CurrentSource<'a> {
117 impl<'a> CurrentSource<'a> {
118 fn new(src: &'a [u8], br: BitReaderState) -> Self {
119 let mut newsrc = Self { src, br };
124 fn reinit(src: &'a [u8], br: BitReaderState) -> Self {
125 let mut newsrc = Self { src, br };
129 fn refill(&mut self) {
130 while (self.br.bits <= 24) && (self.br.pos < self.src.len()) {
131 self.br.bitbuf |= u32::from(self.src[self.br.pos]) << self.br.bits;
136 fn skip_cache(&mut self, nbits: u8) {
137 self.br.bitbuf >>= nbits;
138 self.br.bits -= nbits;
140 fn read(&mut self, nbits: u8) -> BitReaderResult<u32> {
141 if nbits == 0 { return Ok(0); }
142 if nbits > 16 { return Err(BitReaderError::TooManyBitsRequested); }
143 if self.br.bits < nbits {
145 if self.br.bits < nbits { return Err(BitReaderError::BitstreamEnd); }
147 let ret = self.br.bitbuf & ((1 << nbits) - 1);
148 self.skip_cache(nbits);
151 fn read_bool(&mut self) -> BitReaderResult<bool> {
152 if self.br.bits == 0 {
154 if self.br.bits == 0 { return Err(BitReaderError::BitstreamEnd); }
156 let ret = (self.br.bitbuf & 1) != 0;
160 fn peek(&mut self, nbits: u8) -> u32 {
161 if nbits == 0 || nbits > 16 { return 0; }
162 if self.br.bits < nbits {
165 self.br.bitbuf & ((1 << nbits) - 1)
167 fn skip(&mut self, nbits: u32) -> BitReaderResult<()> {
168 if u32::from(self.br.bits) >= nbits {
169 self.skip_cache(nbits as u8);
175 fn align(&mut self) {
176 let b = self.br.bits & 7;
181 fn left(&self) -> isize {
182 ((self.src.len() as isize) - (self.br.pos as isize)) * 8 + (self.br.bits as isize)
186 impl<'a, S: Copy> CodebookReader<S> for CurrentSource<'a> {
187 fn read_cb(&mut self, cb: &Codebook<S>) -> CodebookResult<S> {
190 let mut lut_bits = cb.lut_bits;
191 let orig_br = self.br;
193 let lut_idx = (self.peek(lut_bits) as usize) + (idx as usize);
194 if cb.table[lut_idx] == TABLE_FILL_VALUE { return Err(CodebookError::InvalidCode); }
195 let bits = cb.table[lut_idx] & 0x7F;
196 esc = (cb.table[lut_idx] & 0x80) != 0;
197 idx = (cb.table[lut_idx] >> 8) as usize;
198 let skip_bits = if esc { u32::from(lut_bits) } else { bits };
199 if (skip_bits as isize) > self.left() {
202 return Err(CodebookError::MemoryError);
204 self.skip(skip_bits as u32).unwrap();
205 lut_bits = bits as u8;
216 StaticBlockInvLen(u32),
217 StaticBlockCopy(usize),
219 FixedBlockLengthExt(usize, u8),
220 FixedBlockDist(usize),
221 FixedBlockDistExt(usize, usize, u8),
222 FixedBlockCopy(usize, usize),
223 FixedBlockLiteral(u8),
229 DynCodeLengthsAdd(usize),
231 DynBlockLengthExt(usize, u8),
233 DynBlockDistExt(usize, usize, u8),
234 DynCopy(usize, usize),
239 ///! The decompressor for deflated streams (RFC 1951).
242 fix_len_cb: Codebook<u16>,
253 dyn_len_cb: Option<Codebook<u32>>,
254 dyn_lit_cb: Option<Codebook<u32>>,
255 dyn_dist_cb: Option<Codebook<u32>>,
256 len_lengths: [u8; 19],
257 all_lengths: [u8; NUM_LITERALS + NUM_DISTS],
261 const LENGTH_ADD_BITS: [u8; 29] = [
262 0, 0, 0, 0, 0, 0, 0, 0, 1, 1,
263 1, 1, 2, 2, 2, 2, 3, 3, 3, 3,
264 4, 4, 4, 4, 5, 5, 5, 5, 0
266 const LENGTH_BASE: [u16; 29] = [
267 3, 4, 5, 6, 7, 8, 9, 10, 11, 13,
268 15, 17, 19, 23, 27, 31, 35, 43, 51, 59,
269 67, 83, 99, 115, 131, 163, 195, 227, 258
271 const DIST_ADD_BITS: [u8; 30] = [
272 0, 0, 0, 0, 1, 1, 2, 2, 3, 3,
273 4, 4, 5, 5, 6, 6, 7, 7, 8, 8,
274 9, 9, 10, 10, 11, 11, 12, 12, 13, 13
276 const DIST_BASE: [u16; 30] = [
277 1, 2, 3, 4, 5, 7, 9, 13, 17, 25,
278 33, 49, 65, 97, 129, 193, 257, 385, 513, 769,
279 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577
281 const LEN_RECODE: [usize; 19] = [
282 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
284 const REPEAT_BITS: [u8; 3] = [ 2, 3, 7 ];
285 const REPEAT_BASE: [u8; 3] = [ 3, 3, 11 ];
287 macro_rules! read_bits {
288 ($self: expr, $csrc: expr, $bits: expr) => ({
289 if $csrc.left() < $bits as isize {
291 return Err(DecompressError::ShortData);
293 $csrc.read($bits).unwrap()
297 macro_rules! read_cb {
298 ($self: expr, $csrc: expr, $cb: expr) => ({
299 let ret = $csrc.read_cb($cb);
300 if let Err(CodebookError::MemoryError) = ret {
302 return Err(DecompressError::ShortData);
307 $self.state = InflateState::End;
308 return Err(DecompressError::InvalidData);
315 ///! Creates a new instance of `Inflate` struct.
316 pub fn new() -> Self {
317 let mut cr = FixedLenCodeReader {};
318 let fix_len_cb = Codebook::new(&mut cr, CodebookMode::LSB).unwrap();
320 br: BitReaderState::default(),
328 state: InflateState::Start,
335 len_lengths: [0; 19],
336 all_lengths: [0; NUM_LITERALS + NUM_DISTS],
340 fn put_literal(&mut self, val: u8) {
341 self.buf[self.bpos] = val;
342 self.bpos = (self.bpos + 1) & (self.buf.len() - 1);
345 fn lz_copy(&mut self, offset: usize, len: usize, dst: &mut [u8]) -> DecompressResult<()> {
346 let mask = self.buf.len() - 1;
347 if offset > self.full_pos {
348 return Err(DecompressError::InvalidData);
350 let cstart = (self.bpos.wrapping_sub(offset)) & mask;
352 self.buf[(self.bpos + i) & mask] = self.buf[(cstart + i) & mask];
353 dst[i] = self.buf[(cstart + i) & mask];
355 self.bpos = (self.bpos + len) & mask;
356 self.full_pos += len;
359 ///! Reports whether decoder has finished decoding the input.
360 pub fn is_finished(&self) -> bool {
362 InflateState::End => true,
366 ///! Reports the current amount of bytes output into the destination buffer after the last run.
367 pub fn get_current_output_size(&self) -> usize { self.output_idx }
368 ///! Reports the total amount of bytes decoded so far.
369 pub fn get_total_output_size(&self) -> usize { self.bpos }
370 ///! Tries to decompress input data and write it to the output buffer.
372 ///! Since the decompressor can work with arbitrary input and output chunks its return value may have several meanings:
373 ///! * `Ok(len)` means the stream has been fully decoded and then number of bytes output into the destination buffer is returned.
374 ///! * [`DecompressError::ShortData`] means the input stream has been fully read but more data is needed.
375 ///! * [`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`.
377 ///! [`DecompressError::ShortData`]: ../enum.DecompressError.html#variant.ShortData
378 ///! [`DecompressError::OutputFull`]: ../enum.DecompressError.html#variant.OutputFull
379 pub fn decompress_data(&mut self, src: &[u8], dst: &mut [u8], continue_block: bool) -> DecompressResult<usize> {
380 self.decompress_data_internal(src, dst, continue_block, false)
382 ///! Tries to decompress whole input chunk to the output buffer.
383 pub fn decompress_block(&mut self, src: &[u8], dst: &mut [u8]) -> DecompressResult<usize> {
384 self.decompress_data_internal(src, dst, false, true)
386 #[allow(clippy::comparison_chain)]
387 fn decompress_data_internal(&mut self, src: &[u8], dst: &mut [u8], continue_block: bool, do_one_block: bool) -> DecompressResult<usize> {
388 if src.is_empty() || dst.is_empty() {
389 return Err(DecompressError::InvalidArgument);
391 let mut csrc = if !continue_block {
392 CurrentSource::new(src, self.br)
395 CurrentSource::reinit(src, self.br)
400 // check for zlib stream header
401 if let (&InflateState::Start, true) = (&self.state, src.len() > 2) {
402 let cm = src[0] & 0xF;
403 let cinfo = src[0] >> 4;
404 let hdr = (u16::from(src[0]) << 8) | u16::from(src[1]);
405 if cm == 8 && cinfo <= 7 && (hdr % 31) == 0 {
406 csrc.skip(16).unwrap();
411 InflateState::Start | InflateState::BlockStart => {
412 if csrc.left() == 0 {
414 return Ok(self.output_idx);
417 return Err(DecompressError::ShortData);
419 self.final_block = csrc.read_bool().unwrap();
420 self.state = InflateState::BlockMode;
422 InflateState::BlockMode => {
423 let bmode = read_bits!(self, csrc, 2);
427 self.state = InflateState::StaticBlockLen;
429 1 => { self.state = InflateState::FixedBlock; },
430 2 => { self.state = InflateState::DynBlockHlit; },
432 self.state = InflateState::End;
433 return Err(DecompressError::InvalidHeader);
437 InflateState::StaticBlockLen => {
438 let len = read_bits!(self, csrc, 16);
439 self.state = InflateState::StaticBlockInvLen(len);
441 InflateState::StaticBlockInvLen(len) => {
442 let inv_len = read_bits!(self, csrc, 16);
443 if (len ^ inv_len) != 0xFFFF {
444 self.state = InflateState::End;
445 return Err(DecompressError::InvalidHeader);
447 self.state = InflateState::StaticBlockCopy(len as usize);
449 InflateState::StaticBlockCopy(len) => {
453 self.state = InflateState::StaticBlockCopy(len - i);
454 return Err(DecompressError::ShortData);
456 let val = csrc.read(8).unwrap() as u8;
457 self.put_literal(val);
459 self.state = InflateState::BlockStart;
461 InflateState::FixedBlock => {
462 let val = read_cb!(self, csrc, &self.fix_len_cb);
464 if self.output_idx >= dst.len() {
466 self.state = InflateState::FixedBlockLiteral(val as u8);
467 return Err(DecompressError::OutputFull);
469 self.put_literal(val as u8);
470 dst[self.output_idx] = val as u8;
471 self.output_idx += 1;
472 } else if val == 256 {
473 if self.final_block {
474 self.state = InflateState::End;
475 return Ok(self.output_idx);
477 self.state = InflateState::BlockStart;
480 let len_idx = (val - 257) as usize;
481 if len_idx >= LENGTH_BASE.len() {
482 self.state = InflateState::End;
483 return Err(DecompressError::InvalidData);
485 let len_bits = LENGTH_ADD_BITS[len_idx];
486 let add_base = LENGTH_BASE[len_idx] as usize;
488 self.state = InflateState::FixedBlockLengthExt(add_base, len_bits);
490 self.state = InflateState::FixedBlockDist(add_base);
494 InflateState::FixedBlockLiteral(sym) => {
495 if self.output_idx >= dst.len() {
497 return Err(DecompressError::OutputFull);
499 self.put_literal(sym);
500 dst[self.output_idx] = sym;
501 self.output_idx += 1;
502 self.state = InflateState::FixedBlock;
504 InflateState::FixedBlockLengthExt(base, bits) => {
505 let add = read_bits!(self, csrc, bits) as usize;
506 self.state = InflateState::FixedBlockDist(base + add);
508 InflateState::FixedBlockDist(length) => {
509 let dist_idx = reverse_bits(read_bits!(self, csrc, 5), 5) as usize;
510 if dist_idx >= DIST_BASE.len() {
511 self.state = InflateState::End;
512 return Err(DecompressError::InvalidData);
514 let dist_bits = DIST_ADD_BITS[dist_idx];
515 let dist_base = DIST_BASE[dist_idx] as usize;
517 self.state = InflateState::FixedBlockCopy(length, dist_base);
519 self.state = InflateState::FixedBlockDistExt(length, dist_base, dist_bits);
522 InflateState::FixedBlockDistExt(length, base, bits) => {
523 let add = read_bits!(self, csrc, bits) as usize;
524 self.state = InflateState::FixedBlockCopy(length, base + add);
526 InflateState::FixedBlockCopy(length, dist) => {
527 if self.output_idx + length > dst.len() {
528 let copy_size = dst.len() - self.output_idx;
529 let ret = self.lz_copy(dist, copy_size, &mut dst[self.output_idx..]);
531 self.state = InflateState::End;
532 return Err(DecompressError::InvalidData);
534 self.output_idx += copy_size;
536 self.state = InflateState::FixedBlockCopy(length - copy_size, dist);
537 return Err(DecompressError::OutputFull);
539 let ret = self.lz_copy(dist, length, &mut dst[self.output_idx..]);
541 self.state = InflateState::End;
542 return Err(DecompressError::InvalidData);
544 self.output_idx += length;
545 self.state = InflateState::FixedBlock;
547 InflateState::DynBlockHlit => {
548 self.hlit = (read_bits!(self, csrc, 5) as usize) + 257;
549 if self.hlit >= 287 {
550 self.state = InflateState::End;
551 return Err(DecompressError::InvalidHeader);
553 self.state = InflateState::DynBlockHdist;
555 InflateState::DynBlockHdist => {
556 self.hdist = (read_bits!(self, csrc, 5) as usize) + 1;
557 self.state = InflateState::DynBlockHclen;
559 InflateState::DynBlockHclen => {
560 let hclen = (read_bits!(self, csrc, 4) as usize) + 4;
561 self.cur_len_idx = 0;
562 self.len_lengths = [0; 19];
563 self.all_lengths = [0; NUM_LITERALS + NUM_DISTS];
564 self.state = InflateState::DynLengths(hclen);
566 InflateState::DynLengths(len) => {
570 self.state = InflateState::DynLengths(len - i);
571 return Err(DecompressError::ShortData);
573 self.len_lengths[LEN_RECODE[self.cur_len_idx]] = csrc.read(3).unwrap() as u8;
574 self.cur_len_idx += 1;
576 let mut len_codes = [ShortCodebookDesc { code: 0, bits: 0 }; 19];
577 lengths_to_codes(&self.len_lengths, &mut len_codes)?;
578 let mut cr = ShortCodebookDescReader::new(len_codes.to_vec());
579 let ret = Codebook::new(&mut cr, CodebookMode::LSB);
581 self.state = InflateState::End;
582 return Err(DecompressError::InvalidHeader);
584 self.dyn_len_cb = Some(ret.unwrap());
585 self.cur_len_idx = 0;
586 self.state = InflateState::DynCodeLengths;
588 InflateState::DynCodeLengths => {
589 if let Some(ref len_cb) = self.dyn_len_cb {
590 while self.cur_len_idx < self.hlit + self.hdist {
591 let ret = csrc.read_cb(len_cb);
592 let val = match ret {
594 Err(CodebookError::MemoryError) => {
596 return Err(DecompressError::ShortData);
599 self.state = InflateState::End;
600 return Err(DecompressError::InvalidHeader);
604 self.all_lengths[self.cur_len_idx] = val as u8;
605 self.cur_len_idx += 1;
607 let idx = (val as usize) - 16;
609 self.state = InflateState::End;
610 return Err(DecompressError::InvalidHeader);
612 self.state = InflateState::DynCodeLengthsAdd(idx);
616 let (lit_lengths, dist_lengths) = self.all_lengths.split_at(self.hlit);
618 let mut lit_codes = [ShortCodebookDesc { code: 0, bits: 0 }; NUM_LITERALS];
619 lengths_to_codes(&lit_lengths, &mut lit_codes)?;
620 let mut cr = ShortCodebookDescReader::new(lit_codes.to_vec());
621 let ret = Codebook::new(&mut cr, CodebookMode::LSB);
622 if ret.is_err() { return Err(DecompressError::InvalidHeader); }
623 self.dyn_lit_cb = Some(ret.unwrap());
625 let mut dist_codes = [ShortCodebookDesc { code: 0, bits: 0 }; NUM_DISTS];
626 lengths_to_codes(&dist_lengths[..self.hdist], &mut dist_codes)?;
627 let mut cr = ShortCodebookDescReader::new(dist_codes.to_vec());
628 let ret = Codebook::new(&mut cr, CodebookMode::LSB);
629 if ret.is_err() { return Err(DecompressError::InvalidHeader); }
630 self.dyn_dist_cb = Some(ret.unwrap());
632 self.state = InflateState::DynBlock;
637 InflateState::DynCodeLengthsAdd(mode) => {
638 let base = REPEAT_BASE[mode] as usize;
639 let bits = REPEAT_BITS[mode];
640 let len = base + read_bits!(self, csrc, bits) as usize;
641 if self.cur_len_idx + len > self.hlit + self.hdist {
642 self.state = InflateState::End;
643 return Err(DecompressError::InvalidHeader);
645 let rpt = if mode == 0 {
646 if self.cur_len_idx == 0 {
647 self.state = InflateState::End;
648 return Err(DecompressError::InvalidHeader);
650 self.all_lengths[self.cur_len_idx - 1]
655 self.all_lengths[self.cur_len_idx] = rpt;
656 self.cur_len_idx += 1;
658 self.state = InflateState::DynCodeLengths;
660 InflateState::DynBlock => {
661 if let Some(ref lit_cb) = self.dyn_lit_cb {
662 let val = read_cb!(self, csrc, lit_cb);
664 if self.output_idx >= dst.len() {
666 self.state = InflateState::DynBlockLiteral(val as u8);
667 return Err(DecompressError::OutputFull);
669 self.put_literal(val as u8);
670 dst[self.output_idx] = val as u8;
671 self.output_idx += 1;
672 } else if val == 256 {
673 if self.final_block {
674 self.state = InflateState::End;
675 return Ok(self.output_idx);
677 self.state = InflateState::BlockStart;
680 let len_idx = (val - 257) as usize;
681 if len_idx >= LENGTH_BASE.len() {
682 self.state = InflateState::End;
683 return Err(DecompressError::InvalidData);
685 let len_bits = LENGTH_ADD_BITS[len_idx];
686 let add_base = LENGTH_BASE[len_idx] as usize;
688 self.state = InflateState::DynBlockLengthExt(add_base, len_bits);
690 self.state = InflateState::DynBlockDist(add_base);
697 InflateState::DynBlockLiteral(sym) => {
698 if self.output_idx >= dst.len() {
700 return Err(DecompressError::OutputFull);
702 self.put_literal(sym);
703 dst[self.output_idx] = sym;
704 self.output_idx += 1;
705 self.state = InflateState::DynBlock;
707 InflateState::DynBlockLengthExt(base, bits) => {
708 let add = read_bits!(self, csrc, bits) as usize;
709 self.state = InflateState::DynBlockDist(base + add);
711 InflateState::DynBlockDist(length) => {
712 if let Some(ref dist_cb) = self.dyn_dist_cb {
713 let dist_idx = read_cb!(self, csrc, dist_cb) as usize;
714 if dist_idx >= DIST_BASE.len() {
715 self.state = InflateState::End;
716 return Err(DecompressError::InvalidData);
718 let dist_bits = DIST_ADD_BITS[dist_idx];
719 let dist_base = DIST_BASE[dist_idx] as usize;
721 self.state = InflateState::DynCopy(length, dist_base);
723 self.state = InflateState::DynBlockDistExt(length, dist_base, dist_bits);
729 InflateState::DynBlockDistExt(length, base, bits) => {
730 let add = read_bits!(self, csrc, bits) as usize;
731 self.state = InflateState::DynCopy(length, base + add);
733 InflateState::DynCopy(length, dist) => {
734 if self.output_idx + length > dst.len() {
735 let copy_size = dst.len() - self.output_idx;
736 let ret = self.lz_copy(dist, copy_size, &mut dst[self.output_idx..]);
738 self.state = InflateState::End;
739 return Err(DecompressError::InvalidData);
741 self.output_idx += copy_size;
743 self.state = InflateState::DynCopy(length - copy_size, dist);
744 return Err(DecompressError::OutputFull);
746 let ret = self.lz_copy(dist, length, &mut dst[self.output_idx..]);
748 self.state = InflateState::End;
749 return Err(DecompressError::InvalidData);
751 self.output_idx += length;
752 self.state = InflateState::DynBlock;
754 InflateState::End => {
760 ///! Resets decoder state.
761 pub fn reset(&mut self) {
765 self.state = InflateState::Start;
768 ///! Decompresses input data into output returning the uncompressed data length.
769 pub fn uncompress(src: &[u8], dst: &mut [u8]) -> DecompressResult<usize> {
770 let mut inflate = Self::new();
771 inflate.decompress_data(src, dst, false)
775 impl Default for Inflate {
776 fn default() -> Self {
781 fn lengths_to_codes(lens: &[u8], codes: &mut [ShortCodebookDesc]) -> DecompressResult<()> {
782 let mut bits = [0u32; 32];
783 let mut pfx = [0u32; 33];
784 for len in lens.iter() {
785 let len = *len as usize;
786 if len >= bits.len() {
787 return Err(DecompressError::InvalidHeader);
793 for i in 0..bits.len() {
794 code = (code + bits[i]) << 1;
798 for (len, codes) in lens.iter().zip(codes.iter_mut()) {
799 let len = *len as usize;
801 let bits = len as u8;
802 *codes = ShortCodebookDesc { code: reverse_bits(pfx[len], bits), bits };
805 *codes = ShortCodebookDesc { code: 0, bits: 0 };
818 #[allow(clippy::unreadable_literal)]
820 let mut tab = [0u32; 256];
822 let mut c = i as u32;
825 c = 0xEDB88320 ^ (c >> 1);
834 fn update_crc(&mut self, src: &[u8]) {
835 let mut c = !self.crc;
836 for el in src.iter() {
837 c = self.tab[((c ^ u32::from(*el)) & 0xFF) as usize] ^ (c >> 8);
843 ///! Decodes input data in gzip file format (RFC 1952) returning a vector containing decoded data.
844 pub fn gzip_decode(br: &mut ByteReader, skip_crc: bool) -> DecompressResult<Vec<u8>> {
845 const FLAG_HCRC: u8 = 0x02;
846 const FLAG_EXTRA: u8 = 0x04;
847 const FLAG_NAME: u8 = 0x08;
848 const FLAG_COMMENT: u8 = 0x10;
850 let id1 = br.read_byte()?;
851 let id2 = br.read_byte()?;
852 let cm = br.read_byte()?;
853 let flg = br.read_byte()?;
854 let _mtime = br.read_u32le()?;
855 let _xfl = br.read_byte()?;
856 let _os = br.read_byte()?;
857 if id1 != 0x1F || id2 != 0x8B || cm != 8 {
858 return Err(DecompressError::InvalidHeader);
861 if (flg & FLAG_EXTRA) != 0 {
862 let xlen = br.read_u16le()? as usize;
865 if (flg & FLAG_NAME) != 0 {
867 let b = br.read_byte()?;
873 if (flg & FLAG_COMMENT) != 0 {
875 let b = br.read_byte()?;
881 let _hcrc = if (flg & FLAG_HCRC) != 0 {
886 if (flg & 0xE0) != 0 {
887 return Err(DecompressError::Unsupported);
890 let mut output: Vec<u8> = Vec::new();
891 let mut tail = [0u8; 8];
892 let mut inblk = [0u8; 1024];
893 let mut oblk = [0u8; 4096];
894 let mut inflate = Inflate::new();
895 let mut checker = GzipCRC32::new();
898 let ret = br.read_buf_some(&mut inblk);
899 if let Err(ByteIOError::EOF) = ret {
902 let inlen = match ret {
904 Err(_) => return Err(DecompressError::IOError),
906 let mut repeat = false;
908 let ret = inflate.decompress_data(&inblk[..inlen], &mut oblk, repeat);
911 checker.update_crc(&oblk[..outlen]);
912 output.extend_from_slice(&oblk[..outlen]);
915 Err(DecompressError::ShortData) => {
918 Err(DecompressError::OutputFull) => {
920 checker.update_crc(&oblk);
921 output.extend_from_slice(&oblk);
928 // Save last 8 bytes for CRC and size.
930 tail.copy_from_slice(&inblk[inlen - 8..][..8]);
932 let shift_len = 8 - inlen;
933 for i in 0..shift_len {
934 tail[i] = tail[i + inlen];
936 for i in shift_len..8 {
937 tail[i] = inblk[i - shift_len];
942 if !inflate.is_finished() { println!("???"); }
943 let crc = read_u32le(&tail[0..4])?;
944 let size = read_u32le(&tail[4..8])?;
945 if size != (output.len() as u32) {
946 return Err(DecompressError::CRCError);
948 if crc != checker.crc {
949 return Err(DecompressError::CRCError);
956 #[derive(Clone,Copy,Default)]
964 const TOKEN_EOB: Token = Token { sym: 256, distsym: 0, len: 0, dist: 0 };
967 fn from_literal(sym: u8) -> Self {
975 fn from_match(dist: u16, len: u16) -> Self {
976 let sym = match len {
977 3..= 10 => 257 + len - 3,
978 11..= 18 => 265 + (len - 11) / 2,
979 19..= 34 => 269 + (len - 19) / 4,
980 35..= 66 => 273 + (len - 35) / 8,
981 67..=130 => 277 + (len - 67) / 16,
982 131..=257 => 281 + (len - 131) / 32,
985 let distsym = if dist <= 4 {
988 let bits = 16 - (dist - 1).leading_zeros();
989 (bits as u8) * 2 - 2 + if ((dist - 1) & (1 << (bits - 2))) != 0 { 1 } else { 0 }
992 sym, distsym, len, dist
997 fn add_codes(lens: &[u8], stats: &mut [u32], toks: &mut Vec<(u8, u8)>) {
1001 for &len in lens.iter() {
1007 let run = lcount.min(138);
1009 toks.push((18, run - 11));
1014 toks.push((17, lcount - 3));
1017 for _ in 0..lcount {
1023 let run = lcount.min(6);
1025 toks.push((16, run - 3));
1028 for _ in 0..lcount {
1029 stats[last as usize] += 1;
1030 toks.push((last, 0));
1033 stats[len as usize] += 1;
1034 toks.push((len, 0));
1042 let run = lcount.min(138);
1044 toks.push((18, run - 11));
1049 toks.push((17, lcount - 3));
1052 for _ in 0..lcount {
1058 let run = lcount.min(6);
1060 toks.push((16, run - 3));
1063 for _ in 0..lcount {
1064 stats[last as usize] += 1;
1065 toks.push((last, 0));
1071 ///! Deflate stream writer.
1072 pub struct DeflateWriter {
1078 impl DeflateWriter {
1079 ///! Creates a new instance of `DeflateWriter` for a provided output.
1080 pub fn new(dst: Vec<u8>) -> Self {
1087 fn align(&mut self) {
1088 if (self.bits & 7) != 0 {
1089 self.bits += 8 - (self.bits & 7);
1092 fn flush(&mut self) {
1093 while self.bits >= 8 {
1094 self.dst.push(self.bbuf as u8);
1099 fn write(&mut self, val: u16, len: u8) {
1101 self.bbuf |= u32::from(val) << self.bits;
1104 ///! Finishes writing the stream and returns the output vector.
1105 pub fn end(mut self) -> Vec<u8> {
1108 self.dst.push(self.bbuf as u8);
1113 fn write_codes(&mut self, codes: &CodeHuff, dists: &DistHuff) {
1114 let mut stats = [0u32; 19];
1115 let mut toks = Vec::with_capacity(NUM_LITERALS + NUM_DISTS);
1116 let mut cw = [0u16; 19];
1117 let mut cl = [0u8; 19];
1120 add_codes(&codes.lens[..codes.num_codes], &mut stats, &mut toks);
1121 add_codes(&dists.lens[..dists.num_codes], &mut stats, &mut toks);
1123 gen_tree(&mut cw, &mut cl, &mut nc, &mut stats, 7);
1126 for &idx in LEN_RECODE.iter().rev() {
1136 self.write((nc - 4) as u16, 4);
1137 for &idx in LEN_RECODE.iter().take(nc) {
1138 self.write(u16::from(cl[idx]), 3);
1140 for &(sym, add) in toks.iter() {
1141 self.write(cw[sym as usize], cl[sym as usize]);
1143 16 => self.write(u16::from(add), 2),
1144 17 => self.write(u16::from(add), 3),
1145 18 => self.write(u16::from(add), 7),
1150 fn write_tokens(&mut self, src: &[Token], codes: &CodeHuff, dists: &DistHuff) {
1151 for &tok in src.iter() {
1152 self.write(codes.codes[tok.sym as usize], codes.lens[tok.sym as usize]);
1154 self.write_len_bits(tok.len);
1155 self.write(dists.codes[tok.distsym as usize], dists.lens[tok.distsym as usize]);
1156 self.write_dist_bits(tok.dist);
1160 fn write_len_bits(&mut self, len: u16) {
1162 if llen >= 8 && llen < 255 {
1163 let bits = (16 - llen.leading_zeros() - 3) as u8;
1164 self.write(llen & ((1 << bits) - 1), bits);
1167 fn write_dist_bits(&mut self, dist: u16) {
1168 let ddist = dist - 1;
1170 let bits = (16 - ddist.leading_zeros() - 2) as u8;
1171 self.write(ddist & ((1 << bits) - 1), bits);
1178 stats: [u32; NUM_LITERALS],
1179 codes: [u16; NUM_LITERALS],
1180 lens: [u8; NUM_LITERALS],
1185 fn new(is_fixed: bool) -> Self {
1188 stats: [0; NUM_LITERALS],
1189 codes: [0; NUM_LITERALS],
1190 lens: [0; NUM_LITERALS],
1191 num_codes: NUM_LITERALS,
1194 fn make_codes(&mut self, src: &[Token]) {
1197 self.codes[i] = reverse_bits((i + 0x30) as u32, 8) as u16;
1200 for i in 144..=255 {
1201 self.codes[i] = reverse_bits((i + 0x100) as u32, 9) as u16;
1204 for i in 256..=279 {
1205 self.codes[i] = reverse_bits((i & 0x1F) as u32, 7) as u16;
1208 for i in 280..NUM_LITERALS {
1209 self.codes[i] = reverse_bits((i - 280 + 0xC0) as u32, 8) as u16;
1213 for &tok in src.iter() {
1214 self.stats[tok.sym as usize] += 1;
1216 gen_tree(&mut self.codes, &mut self.lens, &mut self.num_codes, &mut self.stats, 15);
1217 if self.num_codes < 257 {
1218 self.num_codes = 257;
1226 stats: [u32; NUM_DISTS],
1227 codes: [u16; NUM_DISTS],
1228 lens: [u8; NUM_DISTS],
1233 fn new(is_fixed: bool) -> Self {
1236 stats: [0; NUM_DISTS],
1237 codes: [0; NUM_DISTS],
1238 lens: [0; NUM_DISTS],
1239 num_codes: NUM_DISTS,
1242 fn make_codes(&mut self, src: &[Token]) {
1244 for i in 0..NUM_DISTS {
1245 self.codes[i] = reverse_bits(i as u32, 5) as u16;
1249 for &tok in src.iter() {
1251 self.stats[tok.distsym as usize] += 1;
1254 gen_tree(&mut self.codes, &mut self.lens, &mut self.num_codes, &mut self.stats, 15);
1255 if self.num_codes < 1 {
1262 #[derive(Clone,Copy,Default)]
1270 const NODE_SYM: u16 = 65500;
1273 nodes: [Node; NUM_LITERALS * 2],
1280 nodes: [Node::default(); NUM_LITERALS * 2],
1284 fn insert(&mut self, val: Node) {
1285 let mut idx = self.nnodes;
1286 for (i, nn) in self.nodes[..self.nnodes].iter().enumerate() {
1292 if idx < self.nnodes {
1293 for i in (idx..self.nnodes).rev() {
1294 self.nodes[i + 1] = self.nodes[i];
1297 self.nodes[idx] = val;
1300 fn trim(&mut self) {
1301 let mut start = self.nnodes;
1302 for (i, n) in self.nodes[..self.nnodes].iter().enumerate() {
1309 for i in 0..self.nnodes - start {
1310 self.nodes[i] = self.nodes[i + start];
1312 self.nnodes -= start;
1315 fn build(&mut self) {
1316 if self.nnodes == 1 {
1317 self.nodes[0].w = 1;
1321 while start + 1 < self.nnodes {
1322 let nn1 = self.nodes[start];
1323 let nn2 = self.nodes[start + 1];
1328 idx1: (start + 1) as u16,
1330 self.nodes[start].w = 0;
1331 self.nodes[start + 1].w = 0;
1335 if self.nnodes > 1 {
1336 self.assign_len(self.nnodes - 1, 0);
1339 fn assign_len(&mut self, idx: usize, len: u16) {
1340 if self.nodes[idx].sym == NODE_SYM {
1341 self.assign_len(self.nodes[idx].idx0 as usize, len + 1);
1342 self.assign_len(self.nodes[idx].idx1 as usize, len + 1);
1344 self.nodes[idx].w = len;
1349 fn gen_tree(codes: &mut [u16], lens: &mut [u8], num_codes: &mut usize, stats: &mut [u32], max_bits: u8) {
1351 for &w in stats.iter() {
1360 while tot_w > (1 << max_bits) {
1361 for w in stats.iter_mut() {
1365 for &w in stats.iter() {
1369 let mut tree = Tree::new();
1370 for (sym, &w) in stats.iter().enumerate() {
1371 tree.insert(Node{ sym: sym as u16, w: w as u16, idx0: 64000, idx1: 64000 });
1376 for n in tree.nodes[..tree.nnodes].iter() {
1377 if n.sym != NODE_SYM {
1378 lens[n.sym as usize] = n.w as u8;
1381 lengths_to_codes16(lens, codes);
1382 let mut sz = codes.len();
1383 for &len in lens.iter().rev() {
1392 fn lengths_to_codes16(lens: &[u8], codes: &mut [u16]) {
1393 let mut bits = [0u32; 32];
1394 let mut pfx = [0u32; 33];
1395 for len in lens.iter() {
1396 let len = *len as usize;
1401 for i in 0..bits.len() {
1402 code = (code + bits[i]) << 1;
1406 for (len, codes) in lens.iter().zip(codes.iter_mut()) {
1407 let len = *len as usize;
1409 let bits = len as u8;
1410 *codes = reverse_bits(pfx[len], bits) as u16;
1419 fn parse(&mut self, src: &[u8], dst: &mut Vec<Token>);
1423 impl LZParse for NoParser {
1424 fn parse(&mut self, src: &[u8], dst: &mut Vec<Token>) {
1425 dst.reserve(src.len());
1426 for &b in src.iter() {
1427 dst.push(Token::from_literal(b));
1429 dst.push(TOKEN_EOB);
1433 fn check_match(src1: &[u8], src2: &[u8]) -> u16 {
1435 for (&a, &b) in src1.iter().zip(src2.iter()) {
1444 const HASH_SIZE: usize = 4096;
1445 const MAX_MATCH_LEN: usize = 258;
1446 const WINDOW_SIZE: usize = 32768 - MAX_MATCH_LEN;
1447 const NONEXT: usize = WINDOW_SIZE * 2;
1449 struct MatchFinder<'a> {
1452 hstart: [usize; HASH_SIZE],
1453 hend: [usize; HASH_SIZE],
1454 hnext: [usize; WINDOW_SIZE * 3],
1457 impl<'a> MatchFinder<'a> {
1458 fn new(src: &'a [u8]) -> Self {
1459 let mut obj = Self {
1462 hstart: [0; HASH_SIZE],
1463 hend: [0; HASH_SIZE],
1464 hnext: [0; WINDOW_SIZE * 3],
1469 fn hash(src: &[u8]) -> usize {
1471 (((u16::from(src[0]) << 10) ^ (u16::from(src[1]) << 5) ^ u16::from(src[2])) & ((HASH_SIZE as u16) - 1)) as usize
1473 fn build_hash(&mut self) {
1474 for el in self.hstart.iter_mut() { *el = NONEXT; }
1475 for el in self.hend.iter_mut() { *el = NONEXT; }
1476 for el in self.hnext.iter_mut() { *el = NONEXT; }
1477 if self.pos + 3 >= self.src.len() {
1480 let end = (self.src.len() - 3).min(self.pos + NONEXT);
1481 for i in (self.pos .. end).rev() {
1482 let key = Self::hash(&self.src[i..]);
1483 if self.hstart[key] == NONEXT {
1484 self.hstart[key] = i;
1486 self.hnext[key] = NONEXT;
1488 self.hnext[self.hend[key]] = i;
1493 fn find_match(&mut self) -> (u16, u16) {
1494 if self.pos == 0 || self.pos + 3 > self.src.len() {
1497 let key = Self::hash(&self.src[self.pos..]) as usize;
1499 let mut best_pos = 0;
1500 let mut best_len = 0;
1501 let mut idx = self.hstart[key];
1502 while idx != NONEXT && idx + WINDOW_SIZE > self.pos {
1504 let cur_len = check_match(&self.src[self.pos..], &self.src[idx..]);
1505 if cur_len > best_len {
1507 best_pos = self.pos - idx;
1508 if best_len >= (MAX_MATCH_LEN as u16) {
1509 return (best_pos as u16, MAX_MATCH_LEN as u16);
1513 idx = self.hnext[idx];
1515 (best_pos as u16, best_len)
1517 fn find_all_matches(&mut self, dists: &mut [u16; MAX_MATCH_LEN + 1]) {
1518 if self.pos == 0 || self.pos + 3 > self.src.len() {
1521 let key = Self::hash(&self.src[self.pos..]) as usize;
1522 let mut idx = self.hstart[key];
1523 while idx != NONEXT && idx + WINDOW_SIZE > self.pos {
1525 let cur_len = (check_match(&self.src[self.pos..], &self.src[idx..]) as usize).min(MAX_MATCH_LEN);
1526 if cur_len > 0 && dists[cur_len] == 0 {
1527 dists[cur_len] = (self.pos - idx) as u16;
1530 idx = self.hnext[idx];
1533 fn advance(&mut self, num: usize) {
1536 if self.pos >= NONEXT {
1537 let (_, tail) = self.src.split_at(self.pos - WINDOW_SIZE);
1539 self.pos = WINDOW_SIZE;
1542 for (start, end) in self.hstart.iter_mut().zip(self.hend.iter_mut()) {
1543 let mut idx = *start;
1544 while idx != NONEXT && idx + WINDOW_SIZE < self.pos {
1545 idx = self.hnext[idx];
1554 fn get_sym(&self) -> u8 { self.src[self.pos] }
1555 fn is_end(&self) -> bool { self.pos >= self.src.len() }
1558 struct GreedyParser {}
1559 impl LZParse for GreedyParser {
1560 fn parse(&mut self, src: &[u8], dst: &mut Vec<Token>) {
1561 dst.reserve(src.len());
1563 let mut matcher = MatchFinder::new(src);
1564 while !matcher.is_end() {
1565 let (best_pos, best_len) = matcher.find_match();
1568 dst.push(Token::from_match(best_pos, best_len));
1569 matcher.advance(best_len as usize);
1571 dst.push(Token::from_literal(matcher.get_sym()));
1575 dst.push(TOKEN_EOB);
1579 struct LazyParser {}
1580 impl LZParse for LazyParser {
1581 fn parse(&mut self, src: &[u8], dst: &mut Vec<Token>) {
1582 dst.reserve(src.len());
1584 let mut matcher = MatchFinder::new(src);
1585 while !matcher.is_end() {
1586 let (best_pos, best_len) = matcher.find_match();
1588 let last_sym = matcher.get_sym();
1590 if !matcher.is_end() {
1591 let (best_pos1, best_len1) = matcher.find_match();
1592 if best_len1 > best_len + 1 {
1593 dst.push(Token::from_literal(last_sym));
1594 dst.push(Token::from_match(best_pos1, best_len1));
1595 matcher.advance(best_len1 as usize);
1599 dst.push(Token::from_match(best_pos, best_len));
1600 matcher.advance((best_len - 1) as usize);
1602 dst.push(Token::from_literal(matcher.get_sym()));
1606 dst.push(TOKEN_EOB);
1610 #[derive(Clone,Copy)]
1617 impl Default for TNode {
1618 fn default() -> Self {
1620 price: std::u32::MAX,
1627 struct OptimalParser {
1628 trellis: Vec<TNode>,
1630 impl OptimalParser {
1631 fn new() -> Self { Self::default() }
1632 fn sym_price(_sym: u8) -> u32 { 9 }
1633 fn match_price(dist: u16, _len: u16) -> u32 {
1637 let bits = 16 - (dist - 1).leading_zeros();
1642 impl Default for OptimalParser {
1643 fn default() -> Self {
1645 trellis: Vec::with_capacity(WINDOW_SIZE),
1649 impl LZParse for OptimalParser {
1650 fn parse(&mut self, src: &[u8], dst: &mut Vec<Token>) {
1652 dst.push(TOKEN_EOB);
1655 dst.reserve(src.len());
1657 self.trellis.truncate(0);
1658 self.trellis.reserve(src.len() + 1);
1659 for _ in 0..=src.len() {
1660 self.trellis.push(TNode::default());
1662 self.trellis[0].price = 0;
1664 let mut matcher = MatchFinder::new(src);
1665 for i in 0..self.trellis.len() - 1 {
1666 let mut dists = [0; MAX_MATCH_LEN + 1];
1667 matcher.find_all_matches(&mut dists);
1669 let sym = matcher.get_sym();
1670 let lprice = Self::sym_price(sym) + self.trellis[i].price;
1671 if self.trellis[i + 1].price > lprice {
1672 self.trellis[i + 1].price = lprice;
1673 self.trellis[i + 1].link = i;
1675 for (len, &dist) in dists.iter().enumerate() {
1677 let mprice = Self::match_price(dist, len as u16) + self.trellis[i].price;
1678 if self.trellis[i + len].price > mprice {
1679 self.trellis[i + len].price = mprice;
1680 self.trellis[i + len].link = i;
1681 self.trellis[i].dist = dist;
1688 let mut idx = self.trellis.len() - 1;
1689 let mut nidx = self.trellis[idx].link;
1693 nidx = self.trellis[idx].link;
1694 self.trellis[idx].link = oidx;
1698 while idx < self.trellis.len() - 1 {
1699 let len = self.trellis[idx].link - idx;
1701 dst.push(Token::from_literal(src[idx]));
1703 dst.push(Token::from_match(self.trellis[idx].dist, len as u16));
1705 idx = self.trellis[idx].link;
1708 dst.push(TOKEN_EOB);
1712 ///! Deflate compression mode.
1713 #[derive(Clone,Copy,Debug,PartialEq)]
1714 pub enum DeflateMode {
1715 ///! No compression.
1717 ///! Fast compression.
1719 ///! Still fast but better compression.
1721 ///! Slow but the best compression.
1725 impl Default for DeflateMode {
1726 fn default() -> Self { DeflateMode::Better }
1729 pub const DEFLATE_MODE_DESCRIPTION: &str = "Deflate compression level.";
1730 ///! Deflate option for no compression.
1731 pub const DEFLATE_MODE_NONE: &str = "none";
1732 ///! Deflate option for fast compression.
1733 pub const DEFLATE_MODE_FAST: &str = "fast";
1734 ///! Deflate option for better compression.
1735 pub const DEFLATE_MODE_BETTER: &str = "better";
1736 ///! Deflate option for best compression.
1737 pub const DEFLATE_MODE_BEST: &str = "best";
1739 ///! All possible option values for deflate compression.
1740 pub const DEFLATE_OPTION_VALUES: NAOptionDefinitionType = NAOptionDefinitionType::String(Some(&[DEFLATE_MODE_NONE, DEFLATE_MODE_FAST, DEFLATE_MODE_BETTER, DEFLATE_MODE_BEST]));
1742 impl std::str::FromStr for DeflateMode {
1745 fn from_str(s: &str) -> Result<Self, Self::Err> {
1747 DEFLATE_MODE_NONE => Ok(DeflateMode::NoCompr),
1748 DEFLATE_MODE_FAST => Ok(DeflateMode::Fast),
1749 DEFLATE_MODE_BETTER => Ok(DeflateMode::Better),
1750 DEFLATE_MODE_BEST => Ok(DeflateMode::Best),
1756 impl ToString for DeflateMode {
1757 fn to_string(&self) -> String {
1759 DeflateMode::NoCompr => DEFLATE_MODE_NONE.to_string(),
1760 DeflateMode::Fast => DEFLATE_MODE_FAST.to_string(),
1761 DeflateMode::Better => DEFLATE_MODE_BETTER.to_string(),
1762 DeflateMode::Best => DEFLATE_MODE_BEST.to_string(),
1767 #[derive(Clone,Copy,Debug,PartialEq)]
1774 const MAX_BLOCK_SIZE: usize = 65535;
1776 ///! Deflate stream compressor.
1777 pub struct Deflate {
1780 srcbuf: [u8; MAX_BLOCK_SIZE],
1785 parser: Box<dyn LZParse + Send>,
1789 ///! Creates a new instance of `Deflate`.
1790 pub fn new(mode: DeflateMode) -> Self {
1791 let (mode, parser) = match mode {
1792 DeflateMode::NoCompr => (Mode::Copy, Box::new(NoParser{}) as Box<dyn LZParse + Send>),
1793 DeflateMode::Fast => (Mode::Fixed, Box::new(GreedyParser{}) as Box<dyn LZParse + Send>),
1794 DeflateMode::Better => (Mode::Dynamic, Box::new(LazyParser{}) as Box<dyn LZParse + Send>),
1795 DeflateMode::Best => (Mode::Dynamic, Box::new(OptimalParser::new()) as Box<dyn LZParse + Send>),
1799 tokens: Vec::with_capacity(MAX_BLOCK_SIZE),
1800 srcbuf: [0; MAX_BLOCK_SIZE],
1807 ///! Writes zlib stream header.
1808 pub fn write_zlib_header(&mut self, wr: &mut DeflateWriter) {
1811 let level = match self.mode {
1813 Mode::Fixed => 0x5E,
1814 Mode::Dynamic => 0x9C,
1815 // 0xDA for the strongest one
1818 self.zlib_mode = true;
1820 fn write_zlib_footer(&self, wr: &mut DeflateWriter) {
1822 wr.write((self.sum2 >> 8) as u16, 8);
1823 wr.write((self.sum2 & 0xFF) as u16, 8);
1824 wr.write((self.sum1 >> 8) as u16, 8);
1825 wr.write((self.sum1 & 0xFF) as u16, 8);
1827 ///! Queues data for compression.
1829 ///! The data might be not actually compressed until [`compress_end`] is called.
1831 ///! [`compress_end`]: ./struct.Deflate.html#method.compress_end
1832 pub fn compress(&mut self, src: &[u8], wr: &mut DeflateWriter) {
1834 while !src.is_empty() {
1835 let clen = src.len().min(MAX_BLOCK_SIZE - self.ssize);
1836 let (head, tail) = src.split_at(clen);
1838 self.srcbuf[self.ssize..][..clen].copy_from_slice(head);
1840 if self.ssize == MAX_BLOCK_SIZE {
1841 self.do_block(wr, false);
1845 ///! Tells the encoder to finish data compression.
1847 ///! Complete data will be output after this call.
1848 pub fn compress_end(&mut self, wr: &mut DeflateWriter) {
1850 self.do_block(wr, true);
1854 wr.write(0, 7); //static EOF sym
1857 self.write_zlib_footer(wr);
1860 ///! Tells the encoder to compress the data it received and flush it.
1861 pub fn compress_flush(&mut self, wr: &mut DeflateWriter) {
1863 self.do_block(wr, false);
1865 if (wr.bits & 7) != 0 {
1866 // write zero-length copy block for byte-alignment
1871 wr.write(0xFFFF, 16);
1874 fn do_block(&mut self, wr: &mut DeflateWriter, final_block: bool) {
1875 const CRC_BASE: u32 = 65521;
1876 for &b in self.srcbuf[..self.ssize].iter() {
1877 self.sum1 += u32::from(b);
1878 if self.sum1 >= CRC_BASE {
1879 self.sum1 -= CRC_BASE;
1881 self.sum2 += self.sum1;
1882 if self.sum2 >= CRC_BASE {
1883 self.sum2 -= CRC_BASE;
1888 wr.write(final_block as u16, 1);
1891 wr.write(self.ssize as u16, 16);
1892 wr.write(!self.ssize as u16, 16);
1893 for &b in self.srcbuf[..self.ssize].iter() {
1894 wr.write(u16::from(b), 8);
1898 wr.write(final_block as u16, 1);
1900 self.tokens.truncate(0);
1901 self.parser.parse(&self.srcbuf[..self.ssize], &mut self.tokens);
1902 let mut codes = CodeHuff::new(true);
1903 codes.make_codes(&self.tokens);
1904 let mut dists = DistHuff::new(true);
1905 dists.make_codes(&self.tokens);
1906 wr.write_tokens(&self.tokens, &codes, &dists);
1909 wr.write(final_block as u16, 1);
1911 self.tokens.truncate(0);
1912 self.parser.parse(&self.srcbuf[..self.ssize], &mut self.tokens);
1913 let mut codes = CodeHuff::new(false);
1914 codes.make_codes(&self.tokens);
1915 let mut dists = DistHuff::new(false);
1916 dists.make_codes(&self.tokens);
1917 wr.write((codes.num_codes - 257) as u16, 5);
1918 wr.write((dists.num_codes - 1) as u16, 5);
1919 wr.write_codes(&codes, &dists);
1920 wr.write_tokens(&self.tokens, &codes, &dists);
1932 fn test_inflate1() {
1933 const TEST_DATA: &[u8] = &[
1934 0xF3, 0x48, 0xCD, 0xC9, 0xC9, 0xD7, 0x51, 0x28,
1935 0xCF, 0x2F, 0xCA, 0x49, 0x51, 0x04, 0x00 ];
1936 const TEST_REF: &[u8] = b"Hello, world!";
1937 let mut dst_buf = [0u8; 13];
1938 let len = Inflate::uncompress(TEST_DATA, &mut dst_buf).unwrap();
1939 assert_eq!(len, 13);
1941 assert_eq!(dst_buf[i], TEST_REF[i]);
1945 fn test_inflate2() {
1946 const TEST_DATA3: &[u8] = &[ 0x4B, 0x4C, 0x44, 0x80, 0x24, 0x54, 0x80, 0x2C, 0x06, 0x00 ];
1947 const TEST_REF3: &[u8] = b"aaaaaaaaaaaabbbbbbbbbbbbbbbaaaaabbbbbbb";
1948 let mut dst_buf = [0u8; 39];
1950 let mut inflate = Inflate::new();
1951 let mut output_chunk = [0u8; 7];
1952 let mut output_pos = 0;
1953 for input in TEST_DATA3.chunks(3) {
1954 let mut repeat = false;
1956 let ret = inflate.decompress_data(input, &mut output_chunk, repeat);
1960 dst_buf[output_pos + i] = output_chunk[i];
1965 Err(DecompressError::ShortData) => {
1968 Err(DecompressError::OutputFull) => {
1970 for i in 0..output_chunk.len() {
1971 dst_buf[output_pos + i] = output_chunk[i];
1973 output_pos += output_chunk.len();
1976 panic!("decompress error {:?}", ret.err().unwrap());
1982 assert_eq!(output_pos, dst_buf.len());
1983 for i in 0..output_pos {
1984 assert_eq!(dst_buf[i], TEST_REF3[i]);
1988 fn test_inflate3() {
1989 const TEST_DATA: &[u8] = &[
1990 0x1F, 0x8B, 0x08, 0x08, 0xF6, 0x7B, 0x90, 0x5E, 0x02, 0x03, 0x31, 0x2E, 0x74, 0x78, 0x74, 0x00,
1991 0xE5, 0x95, 0x4B, 0x4E, 0xC3, 0x30, 0x10, 0x40, 0xF7, 0x39, 0xC5, 0x1C, 0x00, 0x16, 0x70, 0x83,
1992 0x0A, 0xB5, 0x3B, 0xE8, 0x82, 0x5E, 0x60, 0x1A, 0x4F, 0xE2, 0x11, 0xFE, 0x44, 0x1E, 0xA7, 0x69,
1993 0x6E, 0xCF, 0x38, 0xDD, 0xB0, 0x40, 0xA2, 0x46, 0x2D, 0x20, 0x2A, 0xE5, 0xAB, 0xCC, 0xE7, 0xBD,
1994 0x49, 0xAC, 0x6C, 0x03, 0x64, 0x4B, 0xD0, 0x71, 0x92, 0x0C, 0x06, 0x67, 0x88, 0x1D, 0x3C, 0xD9,
1995 0xC4, 0x92, 0x3D, 0x4A, 0xF3, 0x3C, 0x43, 0x4E, 0x23, 0x81, 0x8B, 0x07, 0x82, 0x1E, 0xF5, 0x90,
1996 0x23, 0x78, 0x6A, 0x56, 0x30, 0x60, 0xCA, 0x89, 0x4D, 0x4F, 0xC0, 0x01, 0x10, 0x06, 0xC2, 0xA4,
1997 0xA1, 0x44, 0xCD, 0xF6, 0x54, 0x50, 0xA8, 0x8D, 0xC1, 0x9C, 0x5F, 0x71, 0x37, 0x45, 0xC8, 0x63,
1998 0xCA, 0x8E, 0xC0, 0xE8, 0x23, 0x69, 0x56, 0x9A, 0x8D, 0x5F, 0xB6, 0xC9, 0x96, 0x53, 0x4D, 0x17,
1999 0xAB, 0xB9, 0xB0, 0x49, 0x14, 0x5A, 0x0B, 0x96, 0x82, 0x7C, 0xB7, 0x6F, 0x17, 0x35, 0xC7, 0x9E,
2000 0xDF, 0x78, 0xA3, 0xF1, 0xD0, 0xA2, 0x73, 0x1C, 0x7A, 0xD8, 0x2B, 0xB3, 0x5C, 0x90, 0x85, 0xBB,
2001 0x2A, 0x14, 0x2E, 0xF7, 0xD1, 0x19, 0x48, 0x0A, 0x23, 0x57, 0x45, 0x13, 0x3E, 0xD6, 0xA0, 0xBD,
2002 0xF2, 0x11, 0x7A, 0x22, 0x21, 0xAD, 0xE5, 0x70, 0x56, 0xA0, 0x9F, 0xA5, 0xA5, 0x03, 0x85, 0x2A,
2003 0xDE, 0x92, 0x00, 0x32, 0x61, 0x10, 0xAD, 0x27, 0x13, 0x7B, 0x5F, 0x98, 0x7F, 0x59, 0x83, 0xB8,
2004 0xB7, 0x35, 0x16, 0xEB, 0x12, 0x0F, 0x1E, 0xD9, 0x14, 0x0B, 0xCF, 0xEE, 0x6D, 0x91, 0xF8, 0x93,
2005 0x6E, 0x81, 0x3F, 0x7F, 0x41, 0xA4, 0x22, 0x1F, 0xB7, 0xE6, 0x85, 0x83, 0x9A, 0xA2, 0x61, 0x12,
2006 0x0D, 0x0F, 0x6D, 0x01, 0xBD, 0xB0, 0xE8, 0x1D, 0xEC, 0xD1, 0xA0, 0xBF, 0x1F, 0x4E, 0xFB, 0x55,
2007 0xBD, 0x73, 0xDD, 0x87, 0xB9, 0x53, 0x23, 0x17, 0xD3, 0xE2, 0xE9, 0x08, 0x87, 0x42, 0xFF, 0xCF,
2008 0x26, 0x42, 0xAE, 0x76, 0xB5, 0xAE, 0x97, 0x0C, 0x18, 0x78, 0xA0, 0x24, 0xE5, 0x54, 0x0C, 0x6E,
2009 0x60, 0x52, 0x79, 0x22, 0x57, 0xF5, 0x87, 0x78, 0x78, 0x04, 0x93, 0x46, 0xEF, 0xCB, 0x98, 0x96,
2010 0x8B, 0x65, 0x00, 0xB7, 0x36, 0xBD, 0x77, 0xA8, 0xBD, 0x5A, 0xAA, 0x1A, 0x09, 0x00, 0x00
2013 let mut mr = MemoryReader::new_read(TEST_DATA);
2014 let mut br = ByteReader::new(&mut mr);
2015 let _dst_buf = gzip_decode(&mut br, false).unwrap();
2017 // println!("{}", String::from_utf8_lossy(_dst_buf.as_slice()));
2020 fn test_deflate_crc() {
2021 let output = Vec::with_capacity(20);
2022 let mut writer = DeflateWriter::new(output);
2023 let mut compr = Deflate::new(DeflateMode::NoCompr);
2024 compr.write_zlib_header(&mut writer);
2025 compr.compress(b"Hello, world!", &mut writer);
2026 compr.compress_end(&mut writer);
2027 let output = writer.end();
2028 assert_eq!(output.as_slice(), b"\x78\x01\x01\x0D\x00\xF2\xFFHello, world!\x20\x5E\x04\x8A");
2030 fn deflate_test(mode: DeflateMode) {
2032 b"The first day of Christmas,
2033 My true love sent to me
2034 A partridge in a pear tree.
2036 The second day of Christmas,
2037 My true love sent to me
2038 Two turtle doves, and
2039 A partridge in a pear tree.
2041 The third day of Christmas,
2042 My true love sent to me
2044 Two turtle doves, and
2045 A partridge in a pear tree.
2047 The fourth day of Christmas,
2048 My true love sent to me
2051 Two turtle doves, and
2052 A partridge in a pear tree.
2054 The fifth day of Christmas,
2055 My true love sent to me
2059 Two turtle doves, and
2060 A partridge in a pear tree.";
2061 let output = Vec::with_capacity(SRC.len() + 16);
2062 let mut writer = DeflateWriter::new(output);
2063 let mut compr = Deflate::new(mode);
2064 compr.write_zlib_header(&mut writer);
2065 compr.compress(SRC, &mut writer);
2066 compr.compress_end(&mut writer);
2067 let output = writer.end();
2068 let mut uncompr = vec![0u8; SRC.len()];
2069 Inflate::uncompress(&output, &mut uncompr).unwrap();
2070 assert_eq!(SRC, uncompr.as_slice());
2073 fn test_deflate_fast() {
2074 deflate_test(DeflateMode::Fast);
2077 fn test_deflate_better() {
2078 deflate_test(DeflateMode::Better);
2081 fn test_deflate_best() {
2082 deflate_test(DeflateMode::Best);