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::io::byteio::*;
75 use crate::io::bitreader::*;
76 use crate::io::codebook::*;
79 const NUM_LITERALS: usize = 287;
80 const NUM_DISTS: usize = 32;
82 struct FixedLenCodeReader {}
84 impl CodebookDescReader<u16> for FixedLenCodeReader {
85 fn bits(&mut self, idx: usize) -> u8 {
87 else if idx < 256 { 9 }
88 else if idx < 280 { 7 }
91 #[allow(clippy::identity_op)]
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) }
100 fn sym (&mut self, idx: usize) -> u16 { idx as u16 }
101 fn len(&mut self) -> usize { NUM_LITERALS + 1 }
104 #[derive(Clone,Copy,Default)]
105 struct BitReaderState {
111 struct CurrentSource<'a> {
116 impl<'a> CurrentSource<'a> {
117 fn new(src: &'a [u8], br: BitReaderState) -> Self {
118 let mut newsrc = Self { src, br };
123 fn reinit(src: &'a [u8], br: BitReaderState) -> Self {
124 let mut newsrc = Self { src, br };
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;
135 fn skip_cache(&mut self, nbits: u8) {
136 self.br.bitbuf >>= nbits;
137 self.br.bits -= nbits;
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 {
144 if self.br.bits < nbits { return Err(BitReaderError::BitstreamEnd); }
146 let ret = self.br.bitbuf & ((1 << nbits) - 1);
147 self.skip_cache(nbits);
150 fn read_bool(&mut self) -> BitReaderResult<bool> {
151 if self.br.bits == 0 {
153 if self.br.bits == 0 { return Err(BitReaderError::BitstreamEnd); }
155 let ret = (self.br.bitbuf & 1) != 0;
159 fn peek(&mut self, nbits: u8) -> u32 {
160 if nbits == 0 || nbits > 16 { return 0; }
161 if self.br.bits < nbits {
164 self.br.bitbuf & ((1 << nbits) - 1)
166 fn skip(&mut self, nbits: u32) -> BitReaderResult<()> {
167 if u32::from(self.br.bits) >= nbits {
168 self.skip_cache(nbits as u8);
174 fn align(&mut self) {
175 let b = self.br.bits & 7;
180 fn left(&self) -> isize {
181 ((self.src.len() as isize) - (self.br.pos as isize)) * 8 + (self.br.bits as isize)
185 impl<'a, S: Copy> CodebookReader<S> for CurrentSource<'a> {
186 fn read_cb(&mut self, cb: &Codebook<S>) -> CodebookResult<S> {
189 let mut lut_bits = cb.lut_bits;
190 let orig_br = self.br;
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() {
201 return Err(CodebookError::MemoryError);
203 self.skip(skip_bits as u32).unwrap();
204 lut_bits = bits as u8;
215 StaticBlockInvLen(u32),
216 StaticBlockCopy(usize),
218 FixedBlockLengthExt(usize, u8),
219 FixedBlockDist(usize),
220 FixedBlockDistExt(usize, usize, u8),
221 FixedBlockCopy(usize, usize),
222 FixedBlockLiteral(u8),
228 DynCodeLengthsAdd(usize),
230 DynBlockLengthExt(usize, u8),
232 DynBlockDistExt(usize, usize, u8),
233 DynCopy(usize, usize),
238 ///! The decompressor for deflated streams (RFC 1951).
241 fix_len_cb: Codebook<u16>,
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],
260 const 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
265 const 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
270 const 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
275 const 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
280 const LEN_RECODE: [usize; 19] = [
281 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
283 const REPEAT_BITS: [u8; 3] = [ 2, 3, 7 ];
284 const REPEAT_BASE: [u8; 3] = [ 3, 3, 11 ];
286 macro_rules! read_bits {
287 ($self: expr, $csrc: expr, $bits: expr) => ({
288 if $csrc.left() < $bits as isize {
290 return Err(DecompressError::ShortData);
292 $csrc.read($bits).unwrap()
296 macro_rules! read_cb {
297 ($self: expr, $csrc: expr, $cb: expr) => ({
298 let ret = $csrc.read_cb($cb);
299 if let Err(CodebookError::MemoryError) = ret {
301 return Err(DecompressError::ShortData);
306 $self.state = InflateState::End;
307 return Err(DecompressError::InvalidData);
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();
319 br: BitReaderState::default(),
327 state: InflateState::Start,
334 len_lengths: [0; 19],
335 all_lengths: [0; NUM_LITERALS + NUM_DISTS],
339 fn put_literal(&mut self, val: u8) {
340 self.buf[self.bpos] = val;
341 self.bpos = (self.bpos + 1) & (self.buf.len() - 1);
344 fn lz_copy(&mut self, offset: usize, len: usize, dst: &mut [u8]) -> DecompressResult<()> {
345 let mask = self.buf.len() - 1;
346 if offset > self.full_pos {
347 return Err(DecompressError::InvalidData);
349 let cstart = (self.bpos.wrapping_sub(offset)) & mask;
351 self.buf[(self.bpos + i) & mask] = self.buf[(cstart + i) & mask];
352 dst[i] = self.buf[(cstart + i) & mask];
354 self.bpos = (self.bpos + len) & mask;
355 self.full_pos += len;
358 ///! Reports whether decoder has finished decoding the input.
359 pub fn is_finished(&self) -> bool {
361 InflateState::End => true,
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.
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`.
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> {
379 self.decompress_data_internal(src, dst, continue_block, false)
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)
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> {
387 if src.is_empty() || dst.is_empty() {
388 return Err(DecompressError::InvalidArgument);
390 let mut csrc = if !continue_block {
391 CurrentSource::new(src, self.br)
394 CurrentSource::reinit(src, self.br)
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();
410 InflateState::Start | InflateState::BlockStart => {
411 if csrc.left() == 0 {
413 return Ok(self.output_idx);
416 return Err(DecompressError::ShortData);
418 self.final_block = csrc.read_bool().unwrap();
419 self.state = InflateState::BlockMode;
421 InflateState::BlockMode => {
422 let bmode = read_bits!(self, csrc, 2);
426 self.state = InflateState::StaticBlockLen;
428 1 => { self.state = InflateState::FixedBlock; },
429 2 => { self.state = InflateState::DynBlockHlit; },
431 self.state = InflateState::End;
432 return Err(DecompressError::InvalidHeader);
436 InflateState::StaticBlockLen => {
437 let len = read_bits!(self, csrc, 16);
438 self.state = InflateState::StaticBlockInvLen(len);
440 InflateState::StaticBlockInvLen(len) => {
441 let inv_len = read_bits!(self, csrc, 16);
442 if (len ^ inv_len) != 0xFFFF {
443 self.state = InflateState::End;
444 return Err(DecompressError::InvalidHeader);
446 self.state = InflateState::StaticBlockCopy(len as usize);
448 InflateState::StaticBlockCopy(len) => {
452 self.state = InflateState::StaticBlockCopy(len - i);
453 return Err(DecompressError::ShortData);
455 let val = csrc.read(8).unwrap() as u8;
456 self.put_literal(val);
458 self.state = InflateState::BlockStart;
460 InflateState::FixedBlock => {
461 let val = read_cb!(self, csrc, &self.fix_len_cb);
463 if self.output_idx >= dst.len() {
465 self.state = InflateState::FixedBlockLiteral(val as u8);
466 return Err(DecompressError::OutputFull);
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);
476 self.state = InflateState::BlockStart;
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);
484 let len_bits = LENGTH_ADD_BITS[len_idx];
485 let add_base = LENGTH_BASE[len_idx] as usize;
487 self.state = InflateState::FixedBlockLengthExt(add_base, len_bits);
489 self.state = InflateState::FixedBlockDist(add_base);
493 InflateState::FixedBlockLiteral(sym) => {
494 if self.output_idx >= dst.len() {
496 return Err(DecompressError::OutputFull);
498 self.put_literal(sym);
499 dst[self.output_idx] = sym;
500 self.output_idx += 1;
501 self.state = InflateState::FixedBlock;
503 InflateState::FixedBlockLengthExt(base, bits) => {
504 let add = read_bits!(self, csrc, bits) as usize;
505 self.state = InflateState::FixedBlockDist(base + add);
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);
513 let dist_bits = DIST_ADD_BITS[dist_idx];
514 let dist_base = DIST_BASE[dist_idx] as usize;
516 self.state = InflateState::FixedBlockCopy(length, dist_base);
518 self.state = InflateState::FixedBlockDistExt(length, dist_base, dist_bits);
521 InflateState::FixedBlockDistExt(length, base, bits) => {
522 let add = read_bits!(self, csrc, bits) as usize;
523 self.state = InflateState::FixedBlockCopy(length, base + add);
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..]);
530 self.state = InflateState::End;
531 return Err(DecompressError::InvalidData);
533 self.output_idx += copy_size;
535 self.state = InflateState::FixedBlockCopy(length - copy_size, dist);
536 return Err(DecompressError::OutputFull);
538 let ret = self.lz_copy(dist, length, &mut dst[self.output_idx..]);
540 self.state = InflateState::End;
541 return Err(DecompressError::InvalidData);
543 self.output_idx += length;
544 self.state = InflateState::FixedBlock;
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);
552 self.state = InflateState::DynBlockHdist;
554 InflateState::DynBlockHdist => {
555 self.hdist = (read_bits!(self, csrc, 5) as usize) + 1;
556 self.state = InflateState::DynBlockHclen;
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);
565 InflateState::DynLengths(len) => {
569 self.state = InflateState::DynLengths(len - i);
570 return Err(DecompressError::ShortData);
572 self.len_lengths[LEN_RECODE[self.cur_len_idx]] = csrc.read(3).unwrap() as u8;
573 self.cur_len_idx += 1;
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);
580 self.state = InflateState::End;
581 return Err(DecompressError::InvalidHeader);
583 self.dyn_len_cb = Some(ret.unwrap());
584 self.cur_len_idx = 0;
585 self.state = InflateState::DynCodeLengths;
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 {
593 Err(CodebookError::MemoryError) => {
595 return Err(DecompressError::ShortData);
598 self.state = InflateState::End;
599 return Err(DecompressError::InvalidHeader);
603 self.all_lengths[self.cur_len_idx] = val as u8;
604 self.cur_len_idx += 1;
606 let idx = (val as usize) - 16;
608 self.state = InflateState::End;
609 return Err(DecompressError::InvalidHeader);
611 self.state = InflateState::DynCodeLengthsAdd(idx);
615 let (lit_lengths, dist_lengths) = self.all_lengths.split_at(self.hlit);
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());
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());
631 self.state = InflateState::DynBlock;
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);
644 let rpt = if mode == 0 {
645 if self.cur_len_idx == 0 {
646 self.state = InflateState::End;
647 return Err(DecompressError::InvalidHeader);
649 self.all_lengths[self.cur_len_idx - 1]
654 self.all_lengths[self.cur_len_idx] = rpt;
655 self.cur_len_idx += 1;
657 self.state = InflateState::DynCodeLengths;
659 InflateState::DynBlock => {
660 if let Some(ref lit_cb) = self.dyn_lit_cb {
661 let val = read_cb!(self, csrc, lit_cb);
663 if self.output_idx >= dst.len() {
665 self.state = InflateState::DynBlockLiteral(val as u8);
666 return Err(DecompressError::OutputFull);
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);
676 self.state = InflateState::BlockStart;
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);
684 let len_bits = LENGTH_ADD_BITS[len_idx];
685 let add_base = LENGTH_BASE[len_idx] as usize;
687 self.state = InflateState::DynBlockLengthExt(add_base, len_bits);
689 self.state = InflateState::DynBlockDist(add_base);
696 InflateState::DynBlockLiteral(sym) => {
697 if self.output_idx >= dst.len() {
699 return Err(DecompressError::OutputFull);
701 self.put_literal(sym);
702 dst[self.output_idx] = sym;
703 self.output_idx += 1;
704 self.state = InflateState::DynBlock;
706 InflateState::DynBlockLengthExt(base, bits) => {
707 let add = read_bits!(self, csrc, bits) as usize;
708 self.state = InflateState::DynBlockDist(base + add);
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);
717 let dist_bits = DIST_ADD_BITS[dist_idx];
718 let dist_base = DIST_BASE[dist_idx] as usize;
720 self.state = InflateState::DynCopy(length, dist_base);
722 self.state = InflateState::DynBlockDistExt(length, dist_base, dist_bits);
728 InflateState::DynBlockDistExt(length, base, bits) => {
729 let add = read_bits!(self, csrc, bits) as usize;
730 self.state = InflateState::DynCopy(length, base + add);
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..]);
737 self.state = InflateState::End;
738 return Err(DecompressError::InvalidData);
740 self.output_idx += copy_size;
742 self.state = InflateState::DynCopy(length - copy_size, dist);
743 return Err(DecompressError::OutputFull);
745 let ret = self.lz_copy(dist, length, &mut dst[self.output_idx..]);
747 self.state = InflateState::End;
748 return Err(DecompressError::InvalidData);
750 self.output_idx += length;
751 self.state = InflateState::DynBlock;
753 InflateState::End => {
759 ///! Resets decoder state.
760 pub fn reset(&mut self) {
764 self.state = InflateState::Start;
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();
770 inflate.decompress_data(src, dst, false)
774 impl Default for Inflate {
775 fn default() -> Self {
780 fn 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);
792 for i in 0..bits.len() {
793 code = (code + bits[i]) << 1;
797 for (len, codes) in lens.iter().zip(codes.iter_mut()) {
798 let len = *len as usize;
800 let bits = len as u8;
801 *codes = ShortCodebookDesc { code: reverse_bits(pfx[len], bits), bits };
804 *codes = ShortCodebookDesc { code: 0, bits: 0 };
817 #[allow(clippy::unreadable_literal)]
819 let mut tab = [0u32; 256];
821 let mut c = i as u32;
824 c = 0xEDB88320 ^ (c >> 1);
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);
842 ///! Decodes input data in gzip file format (RFC 1952) returning a vector containing decoded data.
843 pub 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;
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);
860 if (flg & FLAG_EXTRA) != 0 {
861 let xlen = br.read_u16le()? as usize;
864 if (flg & FLAG_NAME) != 0 {
866 let b = br.read_byte()?;
872 if (flg & FLAG_COMMENT) != 0 {
874 let b = br.read_byte()?;
880 let _hcrc = if (flg & FLAG_HCRC) != 0 {
885 if (flg & 0xE0) != 0 {
886 return Err(DecompressError::Unsupported);
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();
897 let ret = br.read_buf_some(&mut inblk);
898 if let Err(ByteIOError::EOF) = ret {
901 let inlen = match ret {
903 Err(_) => return Err(DecompressError::IOError),
905 let mut repeat = false;
907 let ret = inflate.decompress_data(&inblk[..inlen], &mut oblk, repeat);
910 checker.update_crc(&oblk[..outlen]);
911 output.extend_from_slice(&oblk[..outlen]);
914 Err(DecompressError::ShortData) => {
917 Err(DecompressError::OutputFull) => {
919 checker.update_crc(&oblk);
920 output.extend_from_slice(&oblk);
927 // Save last 8 bytes for CRC and size.
929 tail.copy_from_slice(&inblk[inlen - 8..][..8]);
931 let shift_len = 8 - inlen;
932 for i in 0..shift_len {
933 tail[i] = tail[i + inlen];
935 for i in shift_len..8 {
936 tail[i] = inblk[i - shift_len];
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);
947 if crc != checker.crc {
948 return Err(DecompressError::CRCError);
955 #[derive(Clone,Copy,Default)]
963 const TOKEN_EOB: Token = Token { sym: 256, distsym: 0, len: 0, dist: 0 };
966 fn from_literal(sym: u8) -> Self {
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,
984 let distsym = if dist <= 4 {
987 let bits = 16 - (dist - 1).leading_zeros();
988 (bits as u8) * 2 - 2 + if ((dist - 1) & (1 << (bits - 2))) != 0 { 1 } else { 0 }
991 sym, distsym, len, dist
996 fn add_codes(lens: &[u8], stats: &mut [u32], toks: &mut Vec<(u8, u8)>) {
1000 for &len in lens.iter() {
1006 let run = lcount.min(138);
1008 toks.push((18, run - 11));
1013 toks.push((17, lcount - 3));
1016 for _ in 0..lcount {
1022 let run = lcount.min(6);
1024 toks.push((16, run - 3));
1027 for _ in 0..lcount {
1028 stats[last as usize] += 1;
1029 toks.push((last, 0));
1032 stats[len as usize] += 1;
1033 toks.push((len, 0));
1041 let run = lcount.min(138);
1043 toks.push((18, run - 11));
1048 toks.push((17, lcount - 3));
1051 for _ in 0..lcount {
1057 let run = lcount.min(6);
1059 toks.push((16, run - 3));
1062 for _ in 0..lcount {
1063 stats[last as usize] += 1;
1064 toks.push((last, 0));
1070 ///! Deflate stream writer.
1071 pub struct DeflateWriter {
1077 impl DeflateWriter {
1078 ///! Creates a new instance of `DeflateWriter` for a provided output.
1079 pub fn new(dst: Vec<u8>) -> Self {
1086 fn align(&mut self) {
1087 if (self.bits & 7) != 0 {
1088 self.bits += 8 - (self.bits & 7);
1091 fn flush(&mut self) {
1092 while self.bits >= 8 {
1093 self.dst.push(self.bbuf as u8);
1098 fn write(&mut self, val: u16, len: u8) {
1100 self.bbuf |= u32::from(val) << self.bits;
1103 ///! Finishes writing the stream and returns the output vector.
1104 pub fn end(mut self) -> Vec<u8> {
1107 self.dst.push(self.bbuf as u8);
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];
1119 add_codes(&codes.lens[..codes.num_codes], &mut stats, &mut toks);
1120 add_codes(&dists.lens[..dists.num_codes], &mut stats, &mut toks);
1122 gen_tree(&mut cw, &mut cl, &mut nc, &mut stats, 7);
1125 for &idx in LEN_RECODE.iter().rev() {
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);
1139 for &(sym, add) in toks.iter() {
1140 self.write(cw[sym as usize], cl[sym as usize]);
1142 16 => self.write(u16::from(add), 2),
1143 17 => self.write(u16::from(add), 3),
1144 18 => self.write(u16::from(add), 7),
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]);
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);
1159 fn write_len_bits(&mut self, len: u16) {
1161 if llen >= 8 && llen < 255 {
1162 let bits = (16 - llen.leading_zeros() - 3) as u8;
1163 self.write(llen & ((1 << bits) - 1), bits);
1166 fn write_dist_bits(&mut self, dist: u16) {
1167 let ddist = dist - 1;
1169 let bits = (16 - ddist.leading_zeros() - 2) as u8;
1170 self.write(ddist & ((1 << bits) - 1), bits);
1177 stats: [u32; NUM_LITERALS],
1178 codes: [u16; NUM_LITERALS],
1179 lens: [u8; NUM_LITERALS],
1184 fn new(is_fixed: bool) -> Self {
1187 stats: [0; NUM_LITERALS],
1188 codes: [0; NUM_LITERALS],
1189 lens: [0; NUM_LITERALS],
1190 num_codes: NUM_LITERALS,
1193 fn make_codes(&mut self, src: &[Token]) {
1196 self.codes[i] = reverse_bits((i + 0x30) as u32, 8) as u16;
1199 for i in 144..=255 {
1200 self.codes[i] = reverse_bits((i + 0x100) as u32, 9) as u16;
1203 for i in 256..=279 {
1204 self.codes[i] = reverse_bits((i & 0x1F) as u32, 7) as u16;
1207 for i in 280..NUM_LITERALS {
1208 self.codes[i] = reverse_bits((i - 280 + 0xC0) as u32, 8) as u16;
1212 for &tok in src.iter() {
1213 self.stats[tok.sym as usize] += 1;
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;
1225 stats: [u32; NUM_DISTS],
1226 codes: [u16; NUM_DISTS],
1227 lens: [u8; NUM_DISTS],
1232 fn new(is_fixed: bool) -> Self {
1235 stats: [0; NUM_DISTS],
1236 codes: [0; NUM_DISTS],
1237 lens: [0; NUM_DISTS],
1238 num_codes: NUM_DISTS,
1241 fn make_codes(&mut self, src: &[Token]) {
1243 for i in 0..NUM_DISTS {
1244 self.codes[i] = reverse_bits(i as u32, 5) as u16;
1248 for &tok in src.iter() {
1250 self.stats[tok.distsym as usize] += 1;
1253 gen_tree(&mut self.codes, &mut self.lens, &mut self.num_codes, &mut self.stats, 15);
1254 if self.num_codes < 1 {
1261 #[derive(Clone,Copy,Default)]
1269 const NODE_SYM: u16 = 65500;
1272 nodes: [Node; NUM_LITERALS * 2],
1279 nodes: [Node::default(); NUM_LITERALS * 2],
1283 fn insert(&mut self, val: Node) {
1284 let mut idx = self.nnodes;
1285 for (i, nn) in self.nodes[..self.nnodes].iter().enumerate() {
1291 if idx < self.nnodes {
1292 for i in (idx..self.nnodes).rev() {
1293 self.nodes[i + 1] = self.nodes[i];
1296 self.nodes[idx] = val;
1299 fn trim(&mut self) {
1300 let mut start = self.nnodes;
1301 for (i, n) in self.nodes[..self.nnodes].iter().enumerate() {
1308 for i in 0..self.nnodes - start {
1309 self.nodes[i] = self.nodes[i + start];
1311 self.nnodes -= start;
1314 fn build(&mut self) {
1315 if self.nnodes == 1 {
1316 self.nodes[0].w = 1;
1320 while start + 1 < self.nnodes {
1321 let nn1 = self.nodes[start];
1322 let nn2 = self.nodes[start + 1];
1327 idx1: (start + 1) as u16,
1329 self.nodes[start].w = 0;
1330 self.nodes[start + 1].w = 0;
1334 if self.nnodes > 1 {
1335 self.assign_len(self.nnodes - 1, 0);
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);
1343 self.nodes[idx].w = len;
1348 fn gen_tree(codes: &mut [u16], lens: &mut [u8], num_codes: &mut usize, stats: &mut [u32], max_bits: u8) {
1350 for &w in stats.iter() {
1359 while tot_w > (1 << max_bits) {
1360 for w in stats.iter_mut() {
1364 for &w in stats.iter() {
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 });
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;
1380 lengths_to_codes16(lens, codes);
1381 let mut sz = codes.len();
1382 for &len in lens.iter().rev() {
1391 fn 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;
1400 for i in 0..bits.len() {
1401 code = (code + bits[i]) << 1;
1405 for (len, codes) in lens.iter().zip(codes.iter_mut()) {
1406 let len = *len as usize;
1408 let bits = len as u8;
1409 *codes = reverse_bits(pfx[len], bits) as u16;
1418 fn parse(&mut self, src: &[u8], dst: &mut Vec<Token>);
1422 impl 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));
1428 dst.push(TOKEN_EOB);
1432 fn check_match(src1: &[u8], src2: &[u8]) -> u16 {
1434 for (&a, &b) in src1.iter().zip(src2.iter()) {
1443 const HASH_SIZE: usize = 4096;
1444 const MAX_MATCH_LEN: usize = 258;
1445 const WINDOW_SIZE: usize = 32768 - MAX_MATCH_LEN;
1446 const NONEXT: usize = WINDOW_SIZE * 2;
1448 struct MatchFinder<'a> {
1451 hstart: [usize; HASH_SIZE],
1452 hend: [usize; HASH_SIZE],
1453 hnext: [usize; WINDOW_SIZE * 3],
1456 impl<'a> MatchFinder<'a> {
1457 fn new(src: &'a [u8]) -> Self {
1458 let mut obj = Self {
1461 hstart: [0; HASH_SIZE],
1462 hend: [0; HASH_SIZE],
1463 hnext: [0; WINDOW_SIZE * 3],
1468 fn hash(src: &[u8]) -> usize {
1470 (((u16::from(src[0]) << 10) ^ (u16::from(src[1]) << 5) ^ u16::from(src[2])) & ((HASH_SIZE as u16) - 1)) as usize
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() {
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;
1485 self.hnext[key] = NONEXT;
1487 self.hnext[self.hend[key]] = i;
1492 fn find_match(&mut self) -> (u16, u16) {
1493 if self.pos == 0 || self.pos + 3 > self.src.len() {
1496 let key = Self::hash(&self.src[self.pos..]) as usize;
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 {
1503 let cur_len = check_match(&self.src[self.pos..], &self.src[idx..]);
1504 if cur_len > best_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);
1512 idx = self.hnext[idx];
1514 (best_pos as u16, best_len)
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() {
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 {
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;
1529 idx = self.hnext[idx];
1532 fn advance(&mut self, num: usize) {
1535 if self.pos >= NONEXT {
1536 let (_, tail) = self.src.split_at(self.pos - WINDOW_SIZE);
1538 self.pos = WINDOW_SIZE;
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];
1553 fn get_sym(&self) -> u8 { self.src[self.pos] }
1554 fn is_end(&self) -> bool { self.pos >= self.src.len() }
1557 struct GreedyParser {}
1558 impl LZParse for GreedyParser {
1559 fn parse(&mut self, src: &[u8], dst: &mut Vec<Token>) {
1560 dst.reserve(src.len());
1562 let mut matcher = MatchFinder::new(src);
1563 while !matcher.is_end() {
1564 let (best_pos, best_len) = matcher.find_match();
1567 dst.push(Token::from_match(best_pos, best_len));
1568 matcher.advance(best_len as usize);
1570 dst.push(Token::from_literal(matcher.get_sym()));
1574 dst.push(TOKEN_EOB);
1578 struct LazyParser {}
1579 impl LZParse for LazyParser {
1580 fn parse(&mut self, src: &[u8], dst: &mut Vec<Token>) {
1581 dst.reserve(src.len());
1583 let mut matcher = MatchFinder::new(src);
1584 while !matcher.is_end() {
1585 let (best_pos, best_len) = matcher.find_match();
1587 let last_sym = matcher.get_sym();
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);
1598 dst.push(Token::from_match(best_pos, best_len));
1599 matcher.advance((best_len - 1) as usize);
1601 dst.push(Token::from_literal(matcher.get_sym()));
1605 dst.push(TOKEN_EOB);
1609 #[derive(Clone,Copy)]
1616 impl Default for TNode {
1617 fn default() -> Self {
1619 price: std::u32::MAX,
1626 struct OptimalParser {
1627 trellis: Vec<TNode>,
1629 impl OptimalParser {
1630 fn new() -> Self { Self::default() }
1631 fn sym_price(_sym: u8) -> u32 { 9 }
1632 fn match_price(dist: u16, _len: u16) -> u32 {
1636 let bits = 16 - (dist - 1).leading_zeros();
1641 impl Default for OptimalParser {
1642 fn default() -> Self {
1644 trellis: Vec::with_capacity(WINDOW_SIZE),
1648 impl LZParse for OptimalParser {
1649 fn parse(&mut self, src: &[u8], dst: &mut Vec<Token>) {
1651 dst.push(TOKEN_EOB);
1654 dst.reserve(src.len());
1656 self.trellis.truncate(0);
1657 self.trellis.reserve(src.len() + 1);
1658 for _ in 0..=src.len() {
1659 self.trellis.push(TNode::default());
1661 self.trellis[0].price = 0;
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);
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;
1674 for (len, &dist) in dists.iter().enumerate() {
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;
1687 let mut idx = self.trellis.len() - 1;
1688 let mut nidx = self.trellis[idx].link;
1692 nidx = self.trellis[idx].link;
1693 self.trellis[idx].link = oidx;
1697 while idx < self.trellis.len() - 1 {
1698 let len = self.trellis[idx].link - idx;
1700 dst.push(Token::from_literal(src[idx]));
1702 dst.push(Token::from_match(self.trellis[idx].dist, len as u16));
1704 idx = self.trellis[idx].link;
1707 dst.push(TOKEN_EOB);
1711 ///! Deflate compression mode.
1712 #[derive(Clone,Copy,Debug,PartialEq)]
1713 pub enum DeflateMode {
1714 ///! No compression.
1716 ///! Fast compression.
1718 ///! Still fast but better compression.
1720 ///! Slow but the best compression.
1724 #[derive(Clone,Copy,Debug,PartialEq)]
1731 const MAX_BLOCK_SIZE: usize = 65535;
1733 ///! Deflate stream compressor.
1734 pub struct Deflate {
1737 srcbuf: [u8; MAX_BLOCK_SIZE],
1742 parser: Box<dyn LZParse + Send>,
1746 ///! Creates a new instance of `Deflate`.
1747 pub fn new(mode: DeflateMode) -> Self {
1748 let (mode, parser) = match mode {
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>),
1756 tokens: Vec::with_capacity(MAX_BLOCK_SIZE),
1757 srcbuf: [0; MAX_BLOCK_SIZE],
1764 ///! Writes zlib stream header.
1765 pub fn write_zlib_header(&mut self, wr: &mut DeflateWriter) {
1768 let level = match self.mode {
1770 Mode::Fixed => 0x5E,
1771 Mode::Dynamic => 0x9C,
1772 // 0xDA for the strongest one
1775 self.zlib_mode = true;
1777 fn write_zlib_footer(&self, wr: &mut DeflateWriter) {
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);
1784 ///! Queues data for compression.
1786 ///! The data might be not actually compressed until [`compress_end`] is called.
1788 ///! [`compress_end`]: ./struct.Deflate.html#method.compress_end
1789 pub fn compress(&mut self, src: &[u8], wr: &mut DeflateWriter) {
1791 while !src.is_empty() {
1792 let clen = src.len().min(MAX_BLOCK_SIZE - self.ssize);
1793 let (head, tail) = src.split_at(clen);
1795 self.srcbuf[self.ssize..][..clen].copy_from_slice(head);
1797 if self.ssize == MAX_BLOCK_SIZE {
1798 self.do_block(wr, false);
1802 ///! Tells the encoder to finish data compression.
1804 ///! Complete data will be output after this call.
1805 pub fn compress_end(&mut self, wr: &mut DeflateWriter) {
1807 self.do_block(wr, true);
1811 wr.write(0, 7); //static EOF sym
1814 self.write_zlib_footer(wr);
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;
1824 self.sum2 += self.sum1;
1825 if self.sum2 >= CRC_BASE {
1826 self.sum2 -= CRC_BASE;
1831 wr.write(final_block as u16, 1);
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);
1841 wr.write(final_block as u16, 1);
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);
1852 wr.write(final_block as u16, 1);
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);
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);
1884 assert_eq!(dst_buf[i], TEST_REF[i]);
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];
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;
1899 let ret = inflate.decompress_data(input, &mut output_chunk, repeat);
1903 dst_buf[output_pos + i] = output_chunk[i];
1908 Err(DecompressError::ShortData) => {
1911 Err(DecompressError::OutputFull) => {
1913 for i in 0..output_chunk.len() {
1914 dst_buf[output_pos + i] = output_chunk[i];
1916 output_pos += output_chunk.len();
1919 panic!("decompress error {:?}", ret.err().unwrap());
1925 assert_eq!(output_pos, dst_buf.len());
1926 for i in 0..output_pos {
1927 assert_eq!(dst_buf[i], TEST_REF3[i]);
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
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();
1960 // println!("{}", String::from_utf8_lossy(_dst_buf.as_slice()));
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");
1973 fn deflate_test(mode: DeflateMode) {
1975 b"The first day of Christmas,
1976 My true love sent to me
1977 A partridge in a pear tree.
1979 The second day of Christmas,
1980 My true love sent to me
1981 Two turtle doves, and
1982 A partridge in a pear tree.
1984 The third day of Christmas,
1985 My true love sent to me
1987 Two turtle doves, and
1988 A partridge in a pear tree.
1990 The fourth day of Christmas,
1991 My true love sent to me
1994 Two turtle doves, and
1995 A partridge in a pear tree.
1997 The fifth day of Christmas,
1998 My true love sent to me
2002 Two turtle doves, and
2003 A 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());
2016 fn test_deflate_fast() {
2017 deflate_test(DeflateMode::Fast);
2020 fn test_deflate_better() {
2021 deflate_test(DeflateMode::Better);
2024 fn test_deflate_best() {
2025 deflate_test(DeflateMode::Best);