--- /dev/null
+//! Deflate format (RFC 1951) support.
+//!
+//! This module provides functionality for decompressing raw deflated streams via [`Inflate`] and gzip files (RFC 1952) via [`gzip_decode`].
+//!
+//! [`Inflate`]: ./struct.Inflate.html
+//! [`gzip_decode`]: ./fn.gzip_decode.html
+//!
+//! # Examples
+//!
+//! Decompressing full input buffer into sufficiently large output buffer:
+//! ```
+//! # use nihav_core::compr::DecompressError;
+//! use nihav_core::compr::deflate::Inflate;
+//!
+//! # fn decompress(input: &[u8]) -> Result<(), DecompressError> {
+//! # let mut output_buffer = [0u8; 16];
+//! let output_length = Inflate::uncompress(input, &mut output_buffer)?;
+//! # Ok(())
+//! # }
+//! ```
+//!
+//! Decompressing input chunks into portions of output:
+//! ```
+//! use nihav_core::compr::DecompressError;
+//! use nihav_core::compr::deflate::Inflate;
+//!
+//! # fn decompress(input_data: &[u8]) -> Result<(), DecompressError> {
+//! let mut inflate = Inflate::new();
+//! let mut dst_buf: Vec<u8> = Vec::new();
+//! let mut output_chunk = [0u8; 1024];
+//! for src in input_data.chunks(512) {
+//! let mut repeat = false;
+//! loop {
+//! let ret = inflate.decompress_data(src, &mut output_chunk, repeat);
+//! match ret {
+//! Ok(len) => { // we got a buffer decoded successfully to the end
+//! dst_buf.extend_from_slice(&output_chunk[..len]);
+//! break;
+//! },
+//! Err(DecompressError::ShortData) => { // this block of data was fully read
+//! break;
+//! },
+//! Err(DecompressError::OutputFull) => {
+//! // the output buffer is full, flush it and continue decoding the same block
+//! repeat = true;
+//! dst_buf.extend_from_slice(&output_chunk);
+//! },
+//! Err(err) => {
+//! return Err(err);
+//! },
+//! }
+//! }
+//! }
+//! # Ok(())
+//! # }
+//! ```
+
+use crate::io::byteio::*;
+use crate::io::bitreader::*;
+use crate::io::codebook::*;
+use super::*;
+
+const NUM_LITERALS: usize = 287;
+const NUM_DISTS: usize = 32;
+
+struct FixedLenCodeReader {}
+
+impl CodebookDescReader<u16> for FixedLenCodeReader {
+ fn bits(&mut self, idx: usize) -> u8 {
+ if idx < 144 { 8 }
+ else if idx < 256 { 9 }
+ else if idx < 280 { 7 }
+ else { 8 }
+ }
+ fn code(&mut self, idx: usize) -> u32 {
+ let base = idx as u32;
+ let bits = self.bits(idx);
+ if idx < 144 { reverse_bits(base + 0x30, bits) }
+ else if idx < 256 { reverse_bits(base + 0x190 - 144, bits) }
+ else if idx < 280 { reverse_bits(base + 0x000 - 256, bits) }
+ else { reverse_bits(base + 0xC0 - 280, bits) }
+ }
+ fn sym (&mut self, idx: usize) -> u16 { idx as u16 }
+ fn len(&mut self) -> usize { NUM_LITERALS + 1 }
+}
+
+#[derive(Clone,Copy,Default)]
+struct BitReaderState {
+ pos: usize,
+ bitbuf: u32,
+ bits: u8,
+}
+
+struct CurrentSource<'a> {
+ src: &'a [u8],
+ br: BitReaderState,
+}
+
+impl<'a> CurrentSource<'a> {
+ fn new(src: &'a [u8], br: BitReaderState) -> Self {
+ let mut newsrc = Self { src, br };
+ newsrc.br.pos = 0;
+ newsrc.refill();
+ newsrc
+ }
+ fn reinit(src: &'a [u8], br: BitReaderState) -> Self {
+ let mut newsrc = Self { src, br };
+ newsrc.refill();
+ newsrc
+ }
+ fn refill(&mut self) {
+ while (self.br.bits <= 24) && (self.br.pos < self.src.len()) {
+ self.br.bitbuf |= u32::from(self.src[self.br.pos]) << self.br.bits;
+ self.br.bits += 8;
+ self.br.pos += 1;
+ }
+ }
+ fn skip_cache(&mut self, nbits: u8) {
+ self.br.bitbuf >>= nbits;
+ self.br.bits -= nbits;
+ }
+ fn read(&mut self, nbits: u8) -> BitReaderResult<u32> {
+ if nbits == 0 { return Ok(0); }
+ if nbits > 16 { return Err(BitReaderError::TooManyBitsRequested); }
+ if self.br.bits < nbits {
+ self.refill();
+ if self.br.bits < nbits { return Err(BitReaderError::BitstreamEnd); }
+ }
+ let ret = self.br.bitbuf & ((1 << nbits) - 1);
+ self.skip_cache(nbits);
+ Ok(ret)
+ }
+ fn read_bool(&mut self) -> BitReaderResult<bool> {
+ if self.br.bits == 0 {
+ self.refill();
+ if self.br.bits == 0 { return Err(BitReaderError::BitstreamEnd); }
+ }
+ let ret = (self.br.bitbuf & 1) != 0;
+ self.skip_cache(1);
+ Ok(ret)
+ }
+ fn peek(&mut self, nbits: u8) -> u32 {
+ if nbits == 0 || nbits > 16 { return 0; }
+ if self.br.bits < nbits {
+ self.refill();
+ }
+ self.br.bitbuf & ((1 << nbits) - 1)
+ }
+ fn skip(&mut self, nbits: u32) -> BitReaderResult<()> {
+ if u32::from(self.br.bits) >= nbits {
+ self.skip_cache(nbits as u8);
+ } else {
+ unreachable!();
+ }
+ Ok(())
+ }
+ fn align(&mut self) {
+ let b = self.br.bits & 7;
+ if b != 0 {
+ self.skip_cache(8 - (b as u8));
+ }
+ }
+ fn left(&self) -> isize {
+ ((self.src.len() as isize) - (self.br.pos as isize)) * 8 + (self.br.bits as isize)
+ }
+}
+
+impl<'a, S: Copy> CodebookReader<S> for CurrentSource<'a> {
+ fn read_cb(&mut self, cb: &Codebook<S>) -> CodebookResult<S> {
+ let mut esc = true;
+ let mut idx = 0;
+ let mut lut_bits = cb.lut_bits;
+ let orig_br = self.br;
+ while esc {
+ let lut_idx = (self.peek(lut_bits) as usize) + (idx as usize);
+ if cb.table[lut_idx] == TABLE_FILL_VALUE { return Err(CodebookError::InvalidCode); }
+ let bits = cb.table[lut_idx] & 0x7F;
+ esc = (cb.table[lut_idx] & 0x80) != 0;
+ idx = (cb.table[lut_idx] >> 8) as usize;
+ let skip_bits = if esc { u32::from(lut_bits) } else { bits };
+ if (skip_bits as isize) > self.left() {
+ self.br = orig_br;
+ self.refill();
+ return Err(CodebookError::MemoryError);
+ }
+ self.skip(skip_bits as u32).unwrap();
+ lut_bits = bits as u8;
+ }
+ Ok(cb.syms[idx])
+ }
+}
+
+enum InflateState {
+ Start,
+ BlockStart,
+ BlockMode,
+ StaticBlockLen,
+ StaticBlockInvLen(u32),
+ StaticBlockCopy(usize),
+ FixedBlock,
+ FixedBlockLengthExt(usize, u8),
+ FixedBlockDist(usize),
+ FixedBlockDistExt(usize, usize, u8),
+ FixedBlockCopy(usize, usize),
+ FixedBlockLiteral(u8),
+ DynBlockHlit,
+ DynBlockHdist,
+ DynBlockHclen,
+ DynLengths(usize),
+ DynCodeLengths,
+ DynCodeLengthsAdd(usize),
+ DynBlock,
+ DynBlockLengthExt(usize, u8),
+ DynBlockDist(usize),
+ DynBlockDistExt(usize, usize, u8),
+ DynCopy(usize, usize),
+ DynBlockLiteral(u8),
+ End,
+}
+
+///! The decompressor for deflated streams (RFC 1951).
+pub struct Inflate {
+ br: BitReaderState,
+ fix_len_cb: Codebook<u16>,
+
+ buf: [u8; 65536],
+ bpos: usize,
+ output_idx: usize,
+
+ state: InflateState,
+ final_block: bool,
+ hlit: usize,
+ hdist: usize,
+ dyn_len_cb: Option<Codebook<u32>>,
+ dyn_lit_cb: Option<Codebook<u32>>,
+ dyn_dist_cb: Option<Codebook<u32>>,
+ len_lengths: [u8; 19],
+ all_lengths: [u8; NUM_LITERALS + NUM_DISTS],
+ cur_len_idx: usize,
+}
+
+const LENGTH_ADD_BITS: [u8; 29] = [
+ 0, 0, 0, 0, 0, 0, 0, 0, 1, 1,
+ 1, 1, 2, 2, 2, 2, 3, 3, 3, 3,
+ 4, 4, 4, 4, 5, 5, 5, 5, 0
+];
+const LENGTH_BASE: [u16; 29] = [
+ 3, 4, 5, 6, 7, 8, 9, 10, 11, 13,
+ 15, 17, 19, 23, 27, 31, 35, 43, 51, 59,
+ 67, 83, 99, 115, 131, 163, 195, 227, 258
+];
+const DIST_ADD_BITS: [u8; 30] = [
+ 0, 0, 0, 0, 1, 1, 2, 2, 3, 3,
+ 4, 4, 5, 5, 6, 6, 7, 7, 8, 8,
+ 9, 9, 10, 10, 11, 11, 12, 12, 13, 13
+];
+const DIST_BASE: [u16; 30] = [
+ 1, 2, 3, 4, 5, 7, 9, 13, 17, 25,
+ 33, 49, 65, 97, 129, 193, 257, 385, 513, 769,
+ 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577
+];
+const LEN_RECODE: [usize; 19] = [
+ 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
+];
+const REPEAT_BITS: [u8; 3] = [ 2, 3, 7 ];
+const REPEAT_BASE: [u8; 3] = [ 3, 3, 11 ];
+
+macro_rules! read_bits {
+ ($self: expr, $csrc: expr, $bits: expr) => ({
+ if $csrc.left() < $bits as isize {
+ $self.br = $csrc.br;
+ return Err(DecompressError::ShortData);
+ }
+ $csrc.read($bits).unwrap()
+ })
+}
+
+macro_rules! read_cb {
+ ($self: expr, $csrc: expr, $cb: expr) => ({
+ let ret = $csrc.read_cb($cb);
+ if let Err(CodebookError::MemoryError) = ret {
+ $self.br = $csrc.br;
+ return Err(DecompressError::ShortData);
+ }
+ match ret {
+ Ok(val) => val,
+ Err(_) => {
+ $self.state = InflateState::End;
+ return Err(DecompressError::InvalidData);
+ },
+ }
+ })
+}
+
+impl Inflate {
+ ///! Creates a new instance of `Inflate` struct.
+ pub fn new() -> Self {
+ let mut cr = FixedLenCodeReader {};
+ let fix_len_cb = Codebook::new(&mut cr, CodebookMode::LSB).unwrap();
+ Self {
+ br: BitReaderState::default(),
+ fix_len_cb,
+
+ buf: [0; 65536],
+ bpos: 0,
+ output_idx: 0,
+
+ state: InflateState::Start,
+ final_block: false,
+ dyn_len_cb: None,
+ dyn_lit_cb: None,
+ dyn_dist_cb: None,
+ hlit: 0,
+ hdist: 0,
+ len_lengths: [0; 19],
+ all_lengths: [0; NUM_LITERALS + NUM_DISTS],
+ cur_len_idx: 0,
+ }
+ }
+ fn put_literal(&mut self, val: u8) {
+ self.buf[self.bpos] = val;
+ self.bpos += 1;
+ }
+ fn lz_copy(&mut self, offset: usize, len: usize, dst: &mut [u8]) -> DecompressResult<()> {
+ let mask = self.buf.len() - 1;
+ if self.bpos < offset {
+ return Err(DecompressError::InvalidData);
+ }
+ let cstart = (self.bpos - offset) & mask;
+ for i in 0..len {
+ self.buf[(self.bpos + i) & mask] = self.buf[(cstart + i) & mask];
+ dst[i] = self.buf[(cstart + i) & mask];
+ }
+ self.bpos += len;
+ Ok(())
+ }
+ ///! Reports whether decoder has finished decoding the input.
+ pub fn is_finished(&self) -> bool {
+ match self.state {
+ InflateState::End => true,
+ _ => false,
+ }
+ }
+ ///! Reports the current amount of bytes output into the destination buffer after the last run.
+ pub fn get_current_output_size(&self) -> usize { self.output_idx }
+ ///! Reports the total amount of bytes decoded so far.
+ pub fn get_total_output_size(&self) -> usize { self.bpos }
+ ///! Tries to decompress input data and write it to the output buffer.
+ ///!
+ ///! Since the decompressor can work with arbitrary input and output chunks its return value may have several meanings:
+ ///! * `Ok(len)` means the stream has been fully decoded and then number of bytes output into the destination buffer is returned.
+ ///! * [`DecompressError::ShortData`] means the input stream has been fully read but more data is needed.
+ ///! * [`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`.
+ ///!
+ ///! [`DecompressError::ShortData`]: ../enum.DecompressError.html#variant.ShortData
+ ///! [`DecompressError::OutputFull`]: ../enum.DecompressError.html#variant.OutputFull
+ pub fn decompress_data(&mut self, src: &[u8], dst: &mut [u8], continue_block: bool) -> DecompressResult<usize> {
+ if src.len() == 0 || dst.len() == 0 {
+ return Err(DecompressError::InvalidArgument);
+ }
+ let mut csrc = if !continue_block {
+ CurrentSource::new(src, self.br)
+ } else {
+ self.output_idx = 0;
+ CurrentSource::reinit(src, self.br)
+ };
+ 'main: loop {
+ match self.state {
+ InflateState::Start | InflateState::BlockStart => {
+ if csrc.left() == 0 {
+ self.br = csrc.br;
+ return Err(DecompressError::ShortData);
+ }
+ self.final_block = csrc.read_bool().unwrap();
+ self.state = InflateState::BlockMode;
+ },
+ InflateState::BlockMode => {
+ let bmode = read_bits!(self, csrc, 2);
+ match bmode {
+ 0 => {
+ csrc.align();
+ self.state = InflateState::StaticBlockLen;
+ },
+ 1 => { self.state = InflateState::FixedBlock; },
+ 2 => { self.state = InflateState::DynBlockHlit; },
+ _ => {
+ self.state = InflateState::End;
+ return Err(DecompressError::InvalidHeader);
+ },
+ };
+ },
+ InflateState::StaticBlockLen => {
+ let len = read_bits!(self, csrc, 16);
+ self.state = InflateState::StaticBlockInvLen(len);
+ },
+ InflateState::StaticBlockInvLen(len) => {
+ let inv_len = read_bits!(self, csrc, 16);
+ if len != !inv_len {
+ self.state = InflateState::End;
+ return Err(DecompressError::InvalidHeader);
+ }
+ self.state = InflateState::StaticBlockCopy(len as usize);
+ },
+ InflateState::StaticBlockCopy(len) => {
+ for i in 0..len {
+ if csrc.left() < 8 {
+ self.br = csrc.br;
+ self.state = InflateState::StaticBlockCopy(len - i);
+ return Err(DecompressError::ShortData);
+ }
+ let val = csrc.read(8).unwrap() as u8;
+ self.put_literal(val);
+ }
+ self.state = InflateState::BlockStart;
+ }
+ InflateState::FixedBlock => {
+ let val = read_cb!(self, csrc, &self.fix_len_cb);
+ if val < 256 {
+ if self.output_idx >= dst.len() {
+ self.br = csrc.br;
+ self.state = InflateState::FixedBlockLiteral(val as u8);
+ return Err(DecompressError::OutputFull);
+ }
+ self.put_literal(val as u8);
+ dst[self.output_idx] = val as u8;
+ self.output_idx += 1;
+ } else if val == 256 {
+ if self.final_block {
+ self.state = InflateState::End;
+ return Ok(self.output_idx);
+ } else {
+ self.state = InflateState::BlockStart;
+ }
+ } else {
+ let len_idx = (val - 257) as usize;
+ if len_idx >= LENGTH_BASE.len() {
+ self.state = InflateState::End;
+ return Err(DecompressError::InvalidData);
+ }
+ let len_bits = LENGTH_ADD_BITS[len_idx];
+ let add_base = LENGTH_BASE[len_idx] as usize;
+ if len_bits > 0 {
+ self.state = InflateState::FixedBlockLengthExt(add_base, len_bits);
+ } else {
+ self.state = InflateState::FixedBlockDist(add_base);
+ }
+ }
+ },
+ InflateState::FixedBlockLiteral(sym) => {
+ if self.output_idx >= dst.len() {
+ self.br = csrc.br;
+ return Err(DecompressError::OutputFull);
+ }
+ self.put_literal(sym);
+ dst[self.output_idx] = sym;
+ self.output_idx += 1;
+ self.state = InflateState::FixedBlock;
+ },
+ InflateState::FixedBlockLengthExt(base, bits) => {
+ let add = read_bits!(self, csrc, bits) as usize;
+ self.state = InflateState::FixedBlockDist(base + add);
+ },
+ InflateState::FixedBlockDist(length) => {
+ let dist_idx = reverse_bits(read_bits!(self, csrc, 5), 5) as usize;
+ if dist_idx >= DIST_BASE.len() {
+ self.state = InflateState::End;
+ return Err(DecompressError::InvalidData);
+ }
+ let dist_bits = DIST_ADD_BITS[dist_idx];
+ let dist_base = DIST_BASE[dist_idx] as usize;
+ if dist_bits == 0 {
+ self.state = InflateState::FixedBlockCopy(length, dist_base);
+ } else {
+ self.state = InflateState::FixedBlockDistExt(length, dist_base, dist_bits);
+ }
+ },
+ InflateState::FixedBlockDistExt(length, base, bits) => {
+ let add = read_bits!(self, csrc, bits) as usize;
+ self.state = InflateState::FixedBlockCopy(length, base + add);
+ },
+ InflateState::FixedBlockCopy(length, dist) => {
+ if self.output_idx + length > dst.len() {
+ let copy_size = dst.len() - self.output_idx;
+ let ret = self.lz_copy(dist, copy_size, &mut dst[self.output_idx..]);
+ if ret.is_err() {
+ self.state = InflateState::End;
+ return Err(DecompressError::InvalidData);
+ }
+ self.output_idx += copy_size;
+ self.br = csrc.br;
+ self.state = InflateState::FixedBlockCopy(length - copy_size, dist);
+ return Err(DecompressError::OutputFull);
+ }
+ let ret = self.lz_copy(dist, length, &mut dst[self.output_idx..]);
+ if ret.is_err() {
+ self.state = InflateState::End;
+ return Err(DecompressError::InvalidData);
+ }
+ self.output_idx += length;
+ self.state = InflateState::FixedBlock;
+ }
+ InflateState::DynBlockHlit => {
+ self.hlit = (read_bits!(self, csrc, 5) as usize) + 257;
+ if self.hlit >= 287 {
+ self.state = InflateState::End;
+ return Err(DecompressError::InvalidHeader);
+ }
+ self.state = InflateState::DynBlockHdist;
+ }
+ InflateState::DynBlockHdist => {
+ self.hdist = (read_bits!(self, csrc, 5) as usize) + 1;
+ self.state = InflateState::DynBlockHclen;
+ },
+ InflateState::DynBlockHclen => {
+ let hclen = (read_bits!(self, csrc, 4) as usize) + 4;
+ self.cur_len_idx = 0;
+ self.len_lengths = [0; 19];
+ self.all_lengths = [0; NUM_LITERALS + NUM_DISTS];
+ self.state = InflateState::DynLengths(hclen);
+ },
+ InflateState::DynLengths(len) => {
+ for i in 0..len {
+ if csrc.left() < 3 {
+ self.br = csrc.br;
+ self.state = InflateState::DynLengths(len - i);
+ return Err(DecompressError::ShortData);
+ }
+ self.len_lengths[LEN_RECODE[self.cur_len_idx]] = csrc.read(3).unwrap() as u8;
+ self.cur_len_idx += 1;
+ }
+ let mut len_codes = [ShortCodebookDesc { code: 0, bits: 0 }; 19];
+ lengths_to_codes(&self.len_lengths, &mut len_codes)?;
+ let mut cr = ShortCodebookDescReader::new(len_codes.to_vec());
+ let ret = Codebook::new(&mut cr, CodebookMode::LSB);
+ if ret.is_err() {
+ self.state = InflateState::End;
+ return Err(DecompressError::InvalidHeader);
+ }
+ self.dyn_len_cb = Some(ret.unwrap());
+ self.cur_len_idx = 0;
+ self.state = InflateState::DynCodeLengths;
+ },
+ InflateState::DynCodeLengths => {
+ if let Some(ref len_cb) = self.dyn_len_cb {
+ while self.cur_len_idx < self.hlit + self.hdist {
+ let ret = csrc.read_cb(len_cb);
+ let val = match ret {
+ Ok(val) => val,
+ Err(CodebookError::MemoryError) => {
+ self.br = csrc.br;
+ return Err(DecompressError::ShortData);
+ },
+ Err(_) => {
+ self.state = InflateState::End;
+ return Err(DecompressError::InvalidHeader);
+ },
+ };
+ if val < 16 {
+ self.all_lengths[self.cur_len_idx] = val as u8;
+ self.cur_len_idx += 1;
+ } else {
+ let idx = (val as usize) - 16;
+ if idx > 2 {
+ self.state = InflateState::End;
+ return Err(DecompressError::InvalidHeader);
+ }
+ self.state = InflateState::DynCodeLengthsAdd(idx);
+ continue 'main;
+ }
+ }
+ let (lit_lengths, dist_lengths) = self.all_lengths.split_at(self.hlit);
+
+ let mut lit_codes = [ShortCodebookDesc { code: 0, bits: 0 }; NUM_LITERALS];
+ lengths_to_codes(&lit_lengths, &mut lit_codes)?;
+ let mut cr = ShortCodebookDescReader::new(lit_codes.to_vec());
+ let ret = Codebook::new(&mut cr, CodebookMode::LSB);
+ if ret.is_err() { return Err(DecompressError::InvalidHeader); }
+ self.dyn_lit_cb = Some(ret.unwrap());
+
+ let mut dist_codes = [ShortCodebookDesc { code: 0, bits: 0 }; NUM_DISTS];
+ lengths_to_codes(&dist_lengths[..self.hdist], &mut dist_codes)?;
+ let mut cr = ShortCodebookDescReader::new(dist_codes.to_vec());
+ let ret = Codebook::new(&mut cr, CodebookMode::LSB);
+ if ret.is_err() { return Err(DecompressError::InvalidHeader); }
+ self.dyn_dist_cb = Some(ret.unwrap());
+
+ self.state = InflateState::DynBlock;
+ } else {
+ unreachable!();
+ }
+ },
+ InflateState::DynCodeLengthsAdd(mode) => {
+ let base = REPEAT_BASE[mode] as usize;
+ let bits = REPEAT_BITS[mode];
+ let len = base + read_bits!(self, csrc, bits) as usize;
+ if self.cur_len_idx + len > self.hlit + self.hdist {
+ self.state = InflateState::End;
+ return Err(DecompressError::InvalidHeader);
+ }
+ let rpt;
+ if mode == 0 {
+ if self.cur_len_idx == 0 {
+ self.state = InflateState::End;
+ return Err(DecompressError::InvalidHeader);
+ }
+ rpt = self.all_lengths[self.cur_len_idx - 1];
+ } else {
+ rpt = 0;
+ }
+ for _ in 0..len {
+ self.all_lengths[self.cur_len_idx] = rpt;
+ self.cur_len_idx += 1;
+ }
+ self.state = InflateState::DynCodeLengths;
+ },
+ InflateState::DynBlock => {
+ if let Some(ref lit_cb) = self.dyn_lit_cb {
+ let val = read_cb!(self, csrc, lit_cb);
+ if val < 256 {
+ if self.output_idx >= dst.len() {
+ self.br = csrc.br;
+ self.state = InflateState::DynBlockLiteral(val as u8);
+ return Err(DecompressError::OutputFull);
+ }
+ self.put_literal(val as u8);
+ dst[self.output_idx] = val as u8;
+ self.output_idx += 1;
+ } else if val == 256 {
+ if self.final_block {
+ self.state = InflateState::End;
+ return Ok(self.output_idx);
+ } else {
+ self.state = InflateState::BlockStart;
+ }
+ } else {
+ let len_idx = (val - 257) as usize;
+ if len_idx >= LENGTH_BASE.len() {
+ self.state = InflateState::End;
+ return Err(DecompressError::InvalidData);
+ }
+ let len_bits = LENGTH_ADD_BITS[len_idx];
+ let add_base = LENGTH_BASE[len_idx] as usize;
+ if len_bits > 0 {
+ self.state = InflateState::DynBlockLengthExt(add_base, len_bits);
+ } else {
+ self.state = InflateState::DynBlockDist(add_base);
+ }
+ }
+ } else {
+ unreachable!();
+ }
+ },
+ InflateState::DynBlockLiteral(sym) => {
+ if self.output_idx >= dst.len() {
+ self.br = csrc.br;
+ return Err(DecompressError::OutputFull);
+ }
+ self.put_literal(sym);
+ dst[self.output_idx] = sym;
+ self.output_idx += 1;
+ self.state = InflateState::DynBlock;
+ },
+ InflateState::DynBlockLengthExt(base, bits) => {
+ let add = read_bits!(self, csrc, bits) as usize;
+ self.state = InflateState::DynBlockDist(base + add);
+ },
+ InflateState::DynBlockDist(length) => {
+ if let Some(ref dist_cb) = self.dyn_dist_cb {
+ let dist_idx = read_cb!(self, csrc, dist_cb) as usize;
+ if dist_idx >= DIST_BASE.len() {
+ self.state = InflateState::End;
+ return Err(DecompressError::InvalidData);
+ }
+ let dist_bits = DIST_ADD_BITS[dist_idx];
+ let dist_base = DIST_BASE[dist_idx] as usize;
+ if dist_bits == 0 {
+ self.state = InflateState::DynCopy(length, dist_base);
+ } else {
+ self.state = InflateState::DynBlockDistExt(length, dist_base, dist_bits);
+ }
+ } else {
+ unreachable!();
+ }
+ },
+ InflateState::DynBlockDistExt(length, base, bits) => {
+ let add = read_bits!(self, csrc, bits) as usize;
+ self.state = InflateState::DynCopy(length, base + add);
+ },
+ InflateState::DynCopy(length, dist) => {
+ if self.output_idx + length > dst.len() {
+ let copy_size = dst.len() - self.output_idx;
+ let ret = self.lz_copy(dist, copy_size, &mut dst[self.output_idx..]);
+ if ret.is_err() {
+ self.state = InflateState::End;
+ return Err(DecompressError::InvalidData);
+ }
+ self.output_idx += copy_size;
+ self.br = csrc.br;
+ self.state = InflateState::DynCopy(length - copy_size, dist);
+ return Err(DecompressError::OutputFull);
+ }
+ let ret = self.lz_copy(dist, length, &mut dst[self.output_idx..]);
+ if ret.is_err() {
+ self.state = InflateState::End;
+ return Err(DecompressError::InvalidData);
+ }
+ self.output_idx += length;
+ self.state = InflateState::DynBlock;
+ }
+ InflateState::End => {
+ return Ok(0);
+ },
+ }
+ }
+ }
+ ///! Decompresses input data into output returning the uncompressed data length.
+ pub fn uncompress(src: &[u8], dst: &mut [u8]) -> DecompressResult<usize> {
+ let mut inflate = Self::new();
+ inflate.decompress_data(src, dst, false)
+ }
+}
+
+fn lengths_to_codes(lens: &[u8], codes: &mut [ShortCodebookDesc]) -> DecompressResult<()> {
+ let mut bits = [0u32; 32];
+ let mut pfx = [0u32; 33];
+ for len in lens.iter() {
+ let len = *len as usize;
+ if len >= bits.len() {
+ return Err(DecompressError::InvalidHeader);
+ }
+ bits[len] += 1;
+ }
+ bits[0] = 0;
+ let mut code = 0;
+ for i in 0..bits.len() {
+ code = (code + bits[i]) << 1;
+ pfx[i + 1] = code;
+ }
+
+ for (len, codes) in lens.iter().zip(codes.iter_mut()) {
+ let len = *len as usize;
+ if len != 0 {
+ let bits = len as u8;
+ *codes = ShortCodebookDesc { code: reverse_bits(pfx[len], bits), bits };
+ pfx[len] += 1;
+ } else {
+ *codes = ShortCodebookDesc { code: 0, bits: 0 };
+ }
+ }
+
+ Ok(())
+}
+
+struct GzipCRC32 {
+ tab: [u32; 256],
+ crc: u32,
+}
+
+impl GzipCRC32 {
+ fn new() -> Self {
+ let mut tab = [0u32; 256];
+ for i in 0..256 {
+ let mut c = i as u32;
+ for _ in 0..8 {
+ if (c & 1) != 0 {
+ c = 0xEDB88320 ^ (c >> 1);
+ } else {
+ c >>= 1;
+ }
+ }
+ tab[i] = c;
+ }
+ Self { tab, crc: 0 }
+ }
+ fn update_crc(&mut self, src: &[u8]) {
+ let mut c = !self.crc;
+ for el in src.iter() {
+ c = self.tab[((c ^ u32::from(*el)) & 0xFF) as usize] ^ (c >> 8);
+ }
+ self.crc = !c;
+ }
+}
+
+///! Decodes input data in gzip file format (RFC 1952) returning a vector containing decoded data.
+pub fn gzip_decode(br: &mut ByteReader, skip_crc: bool) -> DecompressResult<Vec<u8>> {
+ const FLAG_HCRC: u8 = 0x02;
+ const FLAG_EXTRA: u8 = 0x04;
+ const FLAG_NAME: u8 = 0x08;
+ const FLAG_COMMENT: u8 = 0x10;
+
+ let id1 = br.read_byte()?;
+ let id2 = br.read_byte()?;
+ let cm = br.read_byte()?;
+ let flg = br.read_byte()?;
+ let _mtime = br.read_u32le()?;
+ let _xfl = br.read_byte()?;
+ let _os = br.read_byte()?;
+ if id1 != 0x1F || id2 != 0x8B || cm != 8 {
+ return Err(DecompressError::InvalidHeader);
+ }
+
+ if (flg & FLAG_EXTRA) != 0 {
+ let xlen = br.read_u16le()? as usize;
+ br.read_skip(xlen)?;
+ }
+ if (flg & FLAG_NAME) != 0 {
+ loop {
+ let b = br.read_byte()?;
+ if b == 0 {
+ break;
+ }
+ }
+ }
+ if (flg & FLAG_COMMENT) != 0 {
+ loop {
+ let b = br.read_byte()?;
+ if b == 0 {
+ break;
+ }
+ }
+ }
+ let _hcrc = if (flg & FLAG_HCRC) != 0 {
+ br.read_u16le()?
+ } else {
+ 0
+ };
+ if (flg & 0xE0) != 0 {
+ return Err(DecompressError::Unsupported);
+ }
+
+ let mut output: Vec<u8> = Vec::new();
+ let mut tail = [0u8; 8];
+ let mut inblk = [0u8; 1024];
+ let mut oblk = [0u8; 4096];
+ let mut inflate = Inflate::new();
+ let mut checker = GzipCRC32::new();
+
+ loop {
+ let ret = br.read_buf_some(&mut inblk);
+ if let Err(ByteIOError::EOF) = ret {
+ break;
+ }
+ let inlen = match ret {
+ Ok(val) => val,
+ Err(_) => return Err(DecompressError::IOError),
+ };
+ let mut repeat = false;
+ loop {
+ let ret = inflate.decompress_data(&inblk[..inlen], &mut oblk, repeat);
+ match ret {
+ Ok(outlen) => {
+ checker.update_crc(&oblk[..outlen]);
+ output.extend_from_slice(&oblk[..outlen]);
+ break;
+ },
+ Err(DecompressError::ShortData) => {
+ break;
+ },
+ Err(DecompressError::OutputFull) => {
+ repeat = true;
+ checker.update_crc(&oblk);
+ output.extend_from_slice(&oblk);
+ },
+ Err(err) => {
+ return Err(err);
+ },
+ }
+ }
+ // Save last 8 bytes for CRC and size.
+ if inlen >= 8 {
+ tail.copy_from_slice(&inblk[inlen - 8..][..8]);
+ } else {
+ let shift_len = 8 - inlen;
+ for i in 0..shift_len {
+ tail[i] = tail[i + inlen];
+ }
+ for i in shift_len..8 {
+ tail[i] = inblk[i - shift_len];
+ }
+ }
+ }
+ if !skip_crc {
+ if !inflate.is_finished() { println!("???"); }
+ let crc = read_u32le(&tail[0..4])?;
+ let size = read_u32le(&tail[4..8])?;
+ if size != (output.len() as u32) {
+ return Err(DecompressError::CRCError);
+ }
+ if crc != checker.crc {
+ return Err(DecompressError::CRCError);
+ }
+ }
+
+ Ok(output)
+}
+
+#[cfg(test)]
+mod test {
+ use super::*;
+
+ #[test]
+ fn test_inflate1() {
+ const TEST_DATA: &[u8] = &[
+ 0xF3, 0x48, 0xCD, 0xC9, 0xC9, 0xD7, 0x51, 0x28,
+ 0xCF, 0x2F, 0xCA, 0x49, 0x51, 0x04, 0x00 ];
+ const TEST_REF: &[u8] = b"Hello, world!";
+ let mut dst_buf = [0u8; 13];
+ let len = Inflate::uncompress(TEST_DATA, &mut dst_buf).unwrap();
+ assert_eq!(len, 13);
+ for i in 0..len {
+ assert_eq!(dst_buf[i], TEST_REF[i]);
+ }
+ }
+ #[test]
+ fn test_inflate2() {
+ const TEST_DATA3: &[u8] = &[ 0x4B, 0x4C, 0x44, 0x80, 0x24, 0x54, 0x80, 0x2C, 0x06, 0x00 ];
+ const TEST_REF3: &[u8] = b"aaaaaaaaaaaabbbbbbbbbbbbbbbaaaaabbbbbbb";
+ let mut dst_buf = [0u8; 39];
+
+ let mut inflate = Inflate::new();
+ let mut output_chunk = [0u8; 7];
+ let mut output_pos = 0;
+ for input in TEST_DATA3.chunks(3) {
+ let mut repeat = false;
+ loop {
+ let ret = inflate.decompress_data(input, &mut output_chunk, repeat);
+ match ret {
+ Ok(len) => {
+ for i in 0..len {
+ dst_buf[output_pos + i] = output_chunk[i];
+ }
+ output_pos += len;
+ break;
+ },
+ Err(DecompressError::ShortData) => {
+ break;
+ },
+ Err(DecompressError::OutputFull) => {
+ repeat = true;
+ for i in 0..output_chunk.len() {
+ dst_buf[output_pos + i] = output_chunk[i];
+ }
+ output_pos += output_chunk.len();
+ },
+ _ => {
+ panic!("decompress error {:?}", ret.err().unwrap());
+ },
+ }
+ }
+ }
+
+ assert_eq!(output_pos, dst_buf.len());
+ for i in 0..output_pos {
+ assert_eq!(dst_buf[i], TEST_REF3[i]);
+ }
+ }
+ #[test]
+ fn test_inflate3() {
+ const TEST_DATA: &[u8] = &[
+ 0x1F, 0x8B, 0x08, 0x08, 0xF6, 0x7B, 0x90, 0x5E, 0x02, 0x03, 0x31, 0x2E, 0x74, 0x78, 0x74, 0x00,
+ 0xE5, 0x95, 0x4B, 0x4E, 0xC3, 0x30, 0x10, 0x40, 0xF7, 0x39, 0xC5, 0x1C, 0x00, 0x16, 0x70, 0x83,
+ 0x0A, 0xB5, 0x3B, 0xE8, 0x82, 0x5E, 0x60, 0x1A, 0x4F, 0xE2, 0x11, 0xFE, 0x44, 0x1E, 0xA7, 0x69,
+ 0x6E, 0xCF, 0x38, 0xDD, 0xB0, 0x40, 0xA2, 0x46, 0x2D, 0x20, 0x2A, 0xE5, 0xAB, 0xCC, 0xE7, 0xBD,
+ 0x49, 0xAC, 0x6C, 0x03, 0x64, 0x4B, 0xD0, 0x71, 0x92, 0x0C, 0x06, 0x67, 0x88, 0x1D, 0x3C, 0xD9,
+ 0xC4, 0x92, 0x3D, 0x4A, 0xF3, 0x3C, 0x43, 0x4E, 0x23, 0x81, 0x8B, 0x07, 0x82, 0x1E, 0xF5, 0x90,
+ 0x23, 0x78, 0x6A, 0x56, 0x30, 0x60, 0xCA, 0x89, 0x4D, 0x4F, 0xC0, 0x01, 0x10, 0x06, 0xC2, 0xA4,
+ 0xA1, 0x44, 0xCD, 0xF6, 0x54, 0x50, 0xA8, 0x8D, 0xC1, 0x9C, 0x5F, 0x71, 0x37, 0x45, 0xC8, 0x63,
+ 0xCA, 0x8E, 0xC0, 0xE8, 0x23, 0x69, 0x56, 0x9A, 0x8D, 0x5F, 0xB6, 0xC9, 0x96, 0x53, 0x4D, 0x17,
+ 0xAB, 0xB9, 0xB0, 0x49, 0x14, 0x5A, 0x0B, 0x96, 0x82, 0x7C, 0xB7, 0x6F, 0x17, 0x35, 0xC7, 0x9E,
+ 0xDF, 0x78, 0xA3, 0xF1, 0xD0, 0xA2, 0x73, 0x1C, 0x7A, 0xD8, 0x2B, 0xB3, 0x5C, 0x90, 0x85, 0xBB,
+ 0x2A, 0x14, 0x2E, 0xF7, 0xD1, 0x19, 0x48, 0x0A, 0x23, 0x57, 0x45, 0x13, 0x3E, 0xD6, 0xA0, 0xBD,
+ 0xF2, 0x11, 0x7A, 0x22, 0x21, 0xAD, 0xE5, 0x70, 0x56, 0xA0, 0x9F, 0xA5, 0xA5, 0x03, 0x85, 0x2A,
+ 0xDE, 0x92, 0x00, 0x32, 0x61, 0x10, 0xAD, 0x27, 0x13, 0x7B, 0x5F, 0x98, 0x7F, 0x59, 0x83, 0xB8,
+ 0xB7, 0x35, 0x16, 0xEB, 0x12, 0x0F, 0x1E, 0xD9, 0x14, 0x0B, 0xCF, 0xEE, 0x6D, 0x91, 0xF8, 0x93,
+ 0x6E, 0x81, 0x3F, 0x7F, 0x41, 0xA4, 0x22, 0x1F, 0xB7, 0xE6, 0x85, 0x83, 0x9A, 0xA2, 0x61, 0x12,
+ 0x0D, 0x0F, 0x6D, 0x01, 0xBD, 0xB0, 0xE8, 0x1D, 0xEC, 0xD1, 0xA0, 0xBF, 0x1F, 0x4E, 0xFB, 0x55,
+ 0xBD, 0x73, 0xDD, 0x87, 0xB9, 0x53, 0x23, 0x17, 0xD3, 0xE2, 0xE9, 0x08, 0x87, 0x42, 0xFF, 0xCF,
+ 0x26, 0x42, 0xAE, 0x76, 0xB5, 0xAE, 0x97, 0x0C, 0x18, 0x78, 0xA0, 0x24, 0xE5, 0x54, 0x0C, 0x6E,
+ 0x60, 0x52, 0x79, 0x22, 0x57, 0xF5, 0x87, 0x78, 0x78, 0x04, 0x93, 0x46, 0xEF, 0xCB, 0x98, 0x96,
+ 0x8B, 0x65, 0x00, 0xB7, 0x36, 0xBD, 0x77, 0xA8, 0xBD, 0x5A, 0xAA, 0x1A, 0x09, 0x00, 0x00
+ ];
+
+ let mut mr = MemoryReader::new_read(TEST_DATA);
+ let mut br = ByteReader::new(&mut mr);
+ let _dst_buf = gzip_decode(&mut br, false).unwrap();
+
+// println!("{}", String::from_utf8_lossy(_dst_buf.as_slice()));
+ }
+}
projects / nihav.git / commitdiff