#![allow(unused_imports)] use alloc::vec::Vec; use alloc::{format, vec}; use crate::bitstream::BitStreamReader; use crate::constants::{ DEFLATE_BLOCKTYPE_DYNAMIC_HUFFMAN, DEFLATE_BLOCKTYPE_RESERVED, DEFLATE_BLOCKTYPE_STATIC, DEFLATE_BLOCKTYPE_UNCOMPRESSED, DEFLATE_MAX_CODEWORD_LENGTH, DEFLATE_MAX_LITLEN_CODEWORD_LENGTH, DEFLATE_MAX_NUM_SYMS, DEFLATE_MAX_OFFSET_CODEWORD_LENGTH, DEFLATE_MAX_PRE_CODEWORD_LEN, DEFLATE_NUM_LITLEN_SYMS, DEFLATE_NUM_OFFSET_SYMS, DEFLATE_NUM_PRECODE_SYMS, DEFLATE_PRECODE_LENS_PERMUTATION, DELFATE_MAX_LENS_OVERRUN, FASTCOPY_BYTES, FASTLOOP_MAX_BYTES_WRITTEN, HUFFDEC_END_OF_BLOCK, HUFFDEC_EXCEPTIONAL, HUFFDEC_LITERAL, HUFFDEC_SUITABLE_POINTER, LITLEN_DECODE_BITS, LITLEN_DECODE_RESULTS, LITLEN_ENOUGH, LITLEN_TABLE_BITS, OFFSET_DECODE_RESULTS, OFFSET_ENOUGH, OFFSET_TABLEBITS, PRECODE_DECODE_RESULTS, PRECODE_ENOUGH, PRECODE_TABLE_BITS }; use crate::errors::{DecodeErrorStatus, InflateDecodeErrors}; #[cfg(feature = "gzip")] use crate::gzip_constants::{ GZIP_CM_DEFLATE, GZIP_FCOMMENT, GZIP_FEXTRA, GZIP_FHCRC, GZIP_FNAME, GZIP_FOOTER_SIZE, GZIP_FRESERVED, GZIP_ID1, GZIP_ID2 }; use crate::utils::{copy_rep_matches, fixed_copy_within, make_decode_table_entry}; struct DeflateHeaderTables { litlen_decode_table: [u32; LITLEN_ENOUGH], offset_decode_table: [u32; OFFSET_ENOUGH] } impl Default for DeflateHeaderTables { fn default() -> Self { DeflateHeaderTables { litlen_decode_table: [0; LITLEN_ENOUGH], offset_decode_table: [0; OFFSET_ENOUGH] } } } /// Options that can influence decompression /// in Deflate/Zlib/Gzip /// /// To use them, pass a customized options to /// the deflate decoder. #[derive(Copy, Clone)] pub struct DeflateOptions { limit: usize, confirm_checksum: bool, size_hint: usize } impl Default for DeflateOptions { fn default() -> Self { DeflateOptions { limit: 1 << 30, confirm_checksum: true, size_hint: 37000 } } } impl DeflateOptions { /// Get deflate/zlib limit option /// /// The decoder won't extend the inbuilt limit and will /// return an error if the limit is exceeded /// /// # Returns /// The currently set limit of the instance /// # Note /// This is provided as a best effort, correctly quiting /// is detrimental to speed and hence this should not be relied too much. pub const fn get_limit(&self) -> usize { self.limit } /// Set a limit to the internal vector /// used to store decoded zlib/deflate output. /// /// # Arguments /// limit: The new decompressor limit /// # Returns /// A modified version of DeflateDecoder /// /// # Note /// This is provided as a best effort, correctly quiting /// is detrimental to speed and hence this should not be relied too much #[must_use] pub fn set_limit(mut self, limit: usize) -> Self { self.limit = limit; self } /// Get whether the decoder will confirm a checksum /// after decoding pub const fn get_confirm_checksum(&self) -> bool { self.confirm_checksum } /// Set whether the decoder should confirm a checksum /// after decoding /// /// Note, you should definitely confirm your checksum, use /// this with caution, otherwise data returned may be corrupt /// /// # Arguments /// - yes: When true, the decoder will confirm checksum /// when false, the decoder will skip checksum verification /// # Notes /// This does not have an influence for deflate decoding as /// it does not have a checksum pub fn set_confirm_checksum(mut self, yes: bool) -> Self { self.confirm_checksum = yes; self } /// Get the default set size hint for the decompressor /// /// The decompressor initializes the internal storage for decompressed bytes /// with this size and will reallocate the vec if the decompressed size becomes bigger /// than this, but when the user currently knows how big the output will be, can be used /// to prevent unnecessary re-allocations pub const fn get_size_hint(&self) -> usize { self.size_hint } /// Set the size hint for the decompressor /// /// This can be used to prevent multiple re-allocations #[must_use] pub const fn set_size_hint(mut self, hint: usize) -> Self { self.size_hint = hint; self } } /// A deflate decoder instance. /// /// The decoder manages output buffer as opposed to requiring the caller to provide a pre-allocated buffer /// it tracks number of bytes written and on successfully reaching the /// end of the block, will return a vector with exactly /// the number of decompressed bytes. /// /// This means that it may use up huge amounts of memory if not checked, but /// there are [options] that can prevent that /// /// [options]: DeflateOptions pub struct DeflateDecoder<'a> { data: &'a [u8], position: usize, stream: BitStreamReader<'a>, is_last_block: bool, static_codes_loaded: bool, deflate_header_tables: DeflateHeaderTables, options: DeflateOptions } impl<'a> DeflateDecoder<'a> { /// Create a new decompressor that will read compressed /// data from `data` and return a new vector containing new data /// /// # Arguments /// - `data`: The compressed data. Data can be of any type /// gzip,zlib or raw deflate. /// /// # Returns /// A decoder instance which will pull compressed data from `data` to inflate the output output /// /// # Note /// /// The default output size limit is **1 GiB.** /// this is to protect the end user against ddos attacks as deflate does not specify it's /// output size upfront /// /// The checksum will be verified depending on the called function. /// this only works for zlib and gzip since deflate does not have a checksum /// /// These defaults can be overridden via [new_with_options()](Self::new_with_options). pub fn new(data: &'a [u8]) -> DeflateDecoder<'a> { let options = DeflateOptions::default(); Self::new_with_options(data, options) } /// Create new decoder with specified options /// /// This can be used to fine tune the decoder to the user's /// needs. /// /// /// # Arguments /// - `data`: The compressed data. Data can be of any format i.e /// gzip, zlib or raw deflate. /// - `options` : A set of user defined options which tune how the decompressor /// /// # Returns /// A decoder instance which will pull compressed data from `data` to inflate output /// /// # Example /// ```no_run /// use zune_inflate::{DeflateDecoder, DeflateOptions}; /// let data = [37]; /// let options = DeflateOptions::default() /// .set_confirm_checksum(true) // confirm the checksum for zlib and gzip /// .set_limit(1000); // how big I think the input will be /// let mut decoder = DeflateDecoder::new_with_options(&data,options); /// // do some stuff and then call decode /// let data = decoder.decode_zlib(); /// /// ``` pub fn new_with_options(data: &'a [u8], options: DeflateOptions) -> DeflateDecoder<'a> { // create stream DeflateDecoder { data, position: 0, stream: BitStreamReader::new(data), is_last_block: false, static_codes_loaded: false, deflate_header_tables: DeflateHeaderTables::default(), options } } /// Decode zlib-encoded data returning the uncompressed in a `Vec` /// or an error if something went wrong. /// /// Bytes consumed will be from the data passed when the /// `new` method was called. /// /// # Arguments /// - None /// # Returns /// Result type containing the decoded data. /// /// - `Ok(Vec)`: Decoded vector containing the uncompressed bytes /// - `Err(InflateDecodeErrors)`: Error that occurred during decoding /// /// It's possible to recover bytes even after an error occurred, bytes up /// to when error was encountered are stored in [InflateDecodeErrors] /// /// /// # Note /// This needs the `zlib` feature enabled to be available otherwise it's a /// compile time error /// /// [InflateDecodeErrors]:crate::errors::InflateDecodeErrors /// #[cfg(feature = "zlib")] pub fn decode_zlib(&mut self) -> Result, InflateDecodeErrors> { use crate::utils::calc_adler_hash; if self.data.len() < 2 /* zlib header */ + 4 /* Deflate */ { return Err(InflateDecodeErrors::new_with_error( DecodeErrorStatus::InsufficientData )); } // Zlib flags // See https://www.ietf.org/rfc/rfc1950.txt for // the RFC let cmf = self.data[0]; let flg = self.data[1]; let cm = cmf & 0xF; let cinfo = cmf >> 4; // let fcheck = flg & 0xF; // let fdict = (flg >> 4) & 1; // let flevel = flg >> 5; // confirm we have the right deflate methods if cm != 8 { if cm == 15 { return Err(InflateDecodeErrors::new_with_error(DecodeErrorStatus::Generic( "CM of 15 is preserved by the standard,currently don't know how to handle it" ))); } return Err(InflateDecodeErrors::new_with_error( DecodeErrorStatus::GenericStr(format!("Unknown zlib compression method {cm}")) )); } if cinfo > 7 { return Err(InflateDecodeErrors::new_with_error( DecodeErrorStatus::GenericStr(format!( "Unknown cinfo `{cinfo}` greater than 7, not allowed" )) )); } let flag_checks = (u16::from(cmf) * 256) + u16::from(flg); if flag_checks % 31 != 0 { return Err(InflateDecodeErrors::new_with_error( DecodeErrorStatus::Generic("FCHECK integrity not preserved") )); } self.position = 2; let data = self.decode_deflate()?; if self.options.confirm_checksum { // Get number of consumed bytes from the input let out_pos = self.stream.get_position() + self.position + self.stream.over_read; // read adler if let Some(adler) = self.data.get(out_pos..out_pos + 4) { let adler_bits: [u8; 4] = adler.try_into().unwrap(); let adler32_expected = u32::from_be_bytes(adler_bits); let adler32_found = calc_adler_hash(&data); if adler32_expected != adler32_found { let err_msg = DecodeErrorStatus::MismatchedAdler(adler32_expected, adler32_found); let err = InflateDecodeErrors::new(err_msg, data); return Err(err); } } else { let err = InflateDecodeErrors::new(DecodeErrorStatus::InsufficientData, data); return Err(err); } } Ok(data) } /// Decode a gzip encoded data and return the uncompressed data in a /// `Vec` or an error if something went wrong /// /// Bytes consumed will be from the data passed when the /// `new` method was called. /// /// # Arguments /// - None /// # Returns /// Result type containing the decoded data. /// /// - `Ok(Vec)`: Decoded vector containing the uncompressed bytes /// - `Err(InflateDecodeErrors)`: Error that occurred during decoding /// /// It's possible to recover bytes even after an error occurred, bytes up /// to when error was encountered are stored in [InflateDecodeErrors] /// /// # Note /// This needs the `gzip` feature enabled to be available, otherwise it's a /// compile time error /// /// [InflateDecodeErrors]:crate::errors::InflateDecodeErrors /// #[cfg(feature = "gzip")] pub fn decode_gzip(&mut self) -> Result, InflateDecodeErrors> { if self.data.len() < 18 { return Err(InflateDecodeErrors::new_with_error( DecodeErrorStatus::InsufficientData )); } if self.data[self.position] != GZIP_ID1 { return Err(InflateDecodeErrors::new_with_error( DecodeErrorStatus::CorruptData )); } self.position += 1; if self.data[self.position] != GZIP_ID2 { return Err(InflateDecodeErrors::new_with_error( DecodeErrorStatus::CorruptData )); } self.position += 1; if self.data[self.position] != GZIP_CM_DEFLATE { return Err(InflateDecodeErrors::new_with_error( DecodeErrorStatus::CorruptData )); } self.position += 1; let flg = self.data[self.position]; self.position += 1; // skip mtime self.position += 4; // skip xfl self.position += 1; // skip os self.position += 1; if (flg & GZIP_FRESERVED) != 0 { return Err(InflateDecodeErrors::new_with_error( DecodeErrorStatus::CorruptData )); } // extra field if (flg & GZIP_FEXTRA) != 0 { let len_bytes = self.data[self.position..self.position + 2] .try_into() .unwrap(); let xlen = usize::from(u16::from_le_bytes(len_bytes)); self.position += 2; if self.data.len().saturating_sub(self.position) < xlen + GZIP_FOOTER_SIZE { return Err(InflateDecodeErrors::new_with_error( DecodeErrorStatus::CorruptData )); } self.position += xlen; } // original file name zero terminated if (flg & GZIP_FNAME) != 0 { loop { if let Some(byte) = self.data.get(self.position) { self.position += 1; if *byte == 0 { break; } } else { return Err(InflateDecodeErrors::new_with_error( DecodeErrorStatus::InsufficientData )); } } } // File comment zero terminated if (flg & GZIP_FCOMMENT) != 0 { loop { if let Some(byte) = self.data.get(self.position) { self.position += 1; if *byte == 0 { break; } } else { return Err(InflateDecodeErrors::new_with_error( DecodeErrorStatus::InsufficientData )); } } } // crc16 for gzip header if (flg & GZIP_FHCRC) != 0 { self.position += 2; } if self.position + GZIP_FOOTER_SIZE > self.data.len() { return Err(InflateDecodeErrors::new_with_error( DecodeErrorStatus::InsufficientData )); } let data = self.decode_deflate()?; let mut out_pos = self.stream.get_position() + self.position + self.stream.over_read; if self.options.confirm_checksum { // Get number of consumed bytes from the input if let Some(crc) = self.data.get(out_pos..out_pos + 4) { let crc_bits: [u8; 4] = crc.try_into().unwrap(); let crc32_expected = u32::from_le_bytes(crc_bits); let crc32_found = !crate::crc::crc32(&data, !0); if crc32_expected != crc32_found { let err_msg = DecodeErrorStatus::MismatchedCRC(crc32_expected, crc32_found); let err = InflateDecodeErrors::new(err_msg, data); return Err(err); } } else { let err = InflateDecodeErrors::new(DecodeErrorStatus::InsufficientData, data); return Err(err); } } //checksum out_pos += 4; if let Some(val) = self.data.get(out_pos..out_pos + 4) { let actual_bytes: [u8; 4] = val.try_into().unwrap(); let ac = u32::from_le_bytes(actual_bytes) as usize; if data.len() != ac { let err = DecodeErrorStatus::Generic("ISIZE does not match actual bytes"); let err = InflateDecodeErrors::new(err, data); return Err(err); } } else { let err = InflateDecodeErrors::new(DecodeErrorStatus::InsufficientData, data); return Err(err); } Ok(data) } /// Decode a deflate stream returning the data as `Vec` or an error /// indicating what went wrong. /// # Arguments /// - None /// # Returns /// Result type containing the decoded data. /// /// - `Ok(Vec)`: Decoded vector containing the uncompressed bytes /// - `Err(InflateDecodeErrors)`: Error that occurred during decoding /// /// It's possible to recover bytes even after an error occurred, bytes up /// to when error was encountered are stored in [InflateDecodeErrors] /// /// /// # Example /// ```no_run /// let data = [42]; // answer to life, the universe and everything /// /// let mut decoder = zune_inflate::DeflateDecoder::new(&data); /// let bytes = decoder.decode_deflate().unwrap(); /// ``` /// /// [InflateDecodeErrors]:crate::errors::InflateDecodeErrors pub fn decode_deflate(&mut self) -> Result, InflateDecodeErrors> { self.start_deflate_block() } /// Main inner loop for decompressing deflate data #[allow(unused_assignments)] fn start_deflate_block(&mut self) -> Result, InflateDecodeErrors> { // start deflate decode // re-read the stream so that we can remove code read by zlib self.stream = BitStreamReader::new(&self.data[self.position..]); self.stream.refill(); // Output space for our decoded bytes. let mut out_block = vec![0; self.options.size_hint]; // bits used let mut src_offset = 0; let mut dest_offset = 0; loop { self.stream.refill(); self.is_last_block = self.stream.get_bits(1) == 1; let block_type = self.stream.get_bits(2); if block_type == DEFLATE_BLOCKTYPE_UNCOMPRESSED { /* * Uncompressed block: copy 'len' bytes literally from the input * buffer to the output buffer. */ /* * The RFC says that * skip any remaining bits in current partially * processed byte * read LEN and NLEN (see next section) * copy LEN bytes of data to output */ if self.stream.over_read > usize::from(self.stream.get_bits_left() >> 3) { out_block.truncate(dest_offset); let err_msg = DecodeErrorStatus::Generic("over-read stream"); let error = InflateDecodeErrors::new(err_msg, out_block); return Err(error); } let partial_bits = self.stream.get_bits_left() & 7; self.stream.drop_bits(partial_bits); let len = self.stream.get_bits(16) as u16; let nlen = self.stream.get_bits(16) as u16; // copy to deflate if len != !nlen { out_block.truncate(dest_offset); let err_msg = DecodeErrorStatus::Generic("Len and nlen do not match"); let error = InflateDecodeErrors::new(err_msg, out_block); return Err(error); } let len = len as usize; let start = self.stream.get_position() + self.position + self.stream.over_read; // ensure there is enough space for a fast copy if dest_offset + len + FASTCOPY_BYTES > out_block.len() { // and if there is not, resize let new_len = out_block.len() + RESIZE_BY + len; out_block.resize(new_len, 0); } if self.data.get((start + len).saturating_sub(1)).is_none() { out_block.truncate(dest_offset); let err_msg = DecodeErrorStatus::CorruptData; let error = InflateDecodeErrors::new(err_msg, out_block); return Err(error); } if dest_offset > self.options.limit { out_block.truncate(dest_offset); let err_msg = DecodeErrorStatus::OutputLimitExceeded(self.options.limit, out_block.len()); let error = InflateDecodeErrors::new(err_msg, out_block); return Err(error); } out_block[dest_offset..dest_offset + len] .copy_from_slice(&self.data[start..start + len]); dest_offset += len; // get the new position to write. self.stream.position = len + (self.stream.position - usize::from(self.stream.bits_left >> 3)); self.stream.reset(); if self.is_last_block { break; } continue; } else if block_type == DEFLATE_BLOCKTYPE_RESERVED { out_block.truncate(dest_offset); let err_msg = DecodeErrorStatus::Generic("Reserved block type 0b11 encountered"); let error = InflateDecodeErrors::new(err_msg, out_block); return Err(error); } // build decode tables for static and dynamic tables match self.build_decode_table(block_type) { Ok(_) => (), Err(value) => { out_block.truncate(dest_offset); let err_msg = value; let error = InflateDecodeErrors::new(err_msg, out_block); return Err(error); } }; // Tables are mutated into the struct, so at this point we know the tables // are loaded, take a reference to them let litlen_decode_table = &self.deflate_header_tables.litlen_decode_table; let offset_decode_table = &self.deflate_header_tables.offset_decode_table; /* * This is the "fast loop" for decoding literals and matches. It does * bounds checks on in_next and out_next in the loop conditions so that * additional bounds checks aren't needed inside the loop body. * * To reduce latency, the bit-buffer is refilled and the next litlen * decode table entry is preloaded before each loop iteration. */ let (mut literal, mut length, mut offset, mut entry) = (0, 0, 0, 0); let mut saved_bitbuf; 'decode: loop { let close_src = 3 * FASTCOPY_BYTES < self.stream.remaining_bytes(); if close_src { self.stream.refill_inner_loop(); let lit_mask = self.stream.peek_bits::(); entry = litlen_decode_table[lit_mask]; 'sequence: loop { // Resize the output vector here to ensure we can always have // enough space for sloppy copies if dest_offset + FASTLOOP_MAX_BYTES_WRITTEN > out_block.len() { let curr_len = out_block.len(); out_block.resize(curr_len + FASTLOOP_MAX_BYTES_WRITTEN + RESIZE_BY, 0) } // At this point entry contains the next value of the litlen // This will always be the case so meaning all our exit paths need // to load in the next entry. // recheck after every sequence // when we hit continue, we need to recheck this // as we are trying to emulate a do while let new_check = self.stream.src.len() < self.stream.position + 8; if new_check { break 'sequence; } self.stream.refill_inner_loop(); /* * Consume the bits for the litlen decode table entry. Save the * original bit-buf for later, in case the extra match length * bits need to be extracted from it. */ saved_bitbuf = self.stream.buffer; self.stream.drop_bits((entry & 0xFF) as u8); /* * Begin by checking for a "fast" literal, i.e. a literal that * doesn't need a subtable. */ if (entry & HUFFDEC_LITERAL) != 0 { /* * On 64-bit platforms, we decode up to 2 extra fast * literals in addition to the primary item, as this * increases performance and still leaves enough bits * remaining for what follows. We could actually do 3, * assuming LITLEN_TABLEBITS=11, but that actually * decreases performance slightly (perhaps by messing * with the branch prediction of the conditional refill * that happens later while decoding the match offset). */ literal = entry >> 16; let new_pos = self.stream.peek_bits::(); entry = litlen_decode_table[new_pos]; saved_bitbuf = self.stream.buffer; self.stream.drop_bits(entry as u8); let out: &mut [u8; 2] = out_block .get_mut(dest_offset..dest_offset + 2) .unwrap() .try_into() .unwrap(); out[0] = literal as u8; dest_offset += 1; if (entry & HUFFDEC_LITERAL) != 0 { /* * Another fast literal, but this one is in lieu of the * primary item, so it doesn't count as one of the extras. */ // load in the next entry. literal = entry >> 16; let new_pos = self.stream.peek_bits::(); entry = litlen_decode_table[new_pos]; out[1] = literal as u8; dest_offset += 1; continue; } } /* * It's not a literal entry, so it can be a length entry, a * subtable pointer entry, or an end-of-block entry. Detect the * two unlikely cases by testing the HUFFDEC_EXCEPTIONAL flag. */ if (entry & HUFFDEC_EXCEPTIONAL) != 0 { // Subtable pointer or end of block entry if (entry & HUFFDEC_END_OF_BLOCK) != 0 { // block done break 'decode; } /* * A subtable is required. Load and consume the * subtable entry. The subtable entry can be of any * type: literal, length, or end-of-block. */ let entry_position = ((entry >> 8) & 0x3F) as usize; let mut pos = (entry >> 16) as usize; saved_bitbuf = self.stream.buffer; pos += self.stream.peek_var_bits(entry_position); entry = litlen_decode_table[pos.min(LITLEN_ENOUGH - 1)]; self.stream.drop_bits(entry as u8); if (entry & HUFFDEC_LITERAL) != 0 { // decode a literal that required a sub table let new_pos = self.stream.peek_bits::(); literal = entry >> 16; entry = litlen_decode_table[new_pos]; *out_block.get_mut(dest_offset).unwrap_or(&mut 0) = (literal & 0xFF) as u8; dest_offset += 1; continue; } if (entry & HUFFDEC_END_OF_BLOCK) != 0 { break 'decode; } } // At this point,we dropped at most 22 bits(LITLEN_DECODE is 11 and we // can do it twice), we now just have 34 bits min remaining. /* * Decode the match length: the length base value associated * with the litlen symbol (which we extract from the decode * table entry), plus the extra length bits. We don't need to * consume the extra length bits here, as they were included in * the bits consumed by the entry earlier. We also don't need * to check for too-long matches here, as this is inside the * fast loop where it's already been verified that the output * buffer has enough space remaining to copy a max-length match. */ let entry_dup = entry; entry = offset_decode_table[self.stream.peek_bits::()]; length = (entry_dup >> 16) as usize; let mask = (1 << entry_dup as u8) - 1; length += (saved_bitbuf & mask) as usize >> ((entry_dup >> 8) as u8); // offset requires a subtable if (entry & HUFFDEC_EXCEPTIONAL) != 0 { self.stream.drop_bits(OFFSET_TABLEBITS as u8); let extra = self.stream.peek_var_bits(((entry >> 8) & 0x3F) as usize); entry = offset_decode_table[((entry >> 16) as usize + extra) & 511]; // refill to handle some weird edge case where we have // less bits than needed for reading the lit-len } saved_bitbuf = self.stream.buffer; self.stream.drop_bits((entry & 0xFF) as u8); let mask = (1 << entry as u8) - 1; offset = (entry >> 16) as usize; offset += (saved_bitbuf & mask) as usize >> (((entry >> 8) & 0xFF) as u8); if offset > dest_offset { out_block.truncate(dest_offset); let err_msg = DecodeErrorStatus::CorruptData; let error = InflateDecodeErrors::new(err_msg, out_block); return Err(error); } src_offset = dest_offset - offset; if self.stream.bits_left < 11 { self.stream.refill_inner_loop(); } // Copy some bytes unconditionally // This makes us copy smaller match lengths quicker because we don't need // a loop + don't send too much pressure to the Memory unit. fixed_copy_within::( &mut out_block, src_offset, dest_offset ); entry = litlen_decode_table[self.stream.peek_bits::()]; let mut current_position = dest_offset; dest_offset += length; if offset == 1 { // RLE fill with a single byte let byte_to_repeat = out_block[src_offset]; out_block[current_position..dest_offset].fill(byte_to_repeat); } else if offset <= FASTCOPY_BYTES && current_position + offset < dest_offset { // The second conditional ensures we only come // here if the first copy didn't succeed to copy just enough bytes for a rep // match to be valid, i.e we want this path to be taken the least amount // of times possible // the unconditional copy above copied some bytes // don't let it go into waste // Increment the position we are in by the number of correct bytes // currently copied let mut src_position = src_offset + offset; let mut dest_position = current_position + offset; // loop copying offset bytes in place // notice this loop does fixed copies but increments in offset bytes :) // that is intentional. loop { fixed_copy_within::( &mut out_block, src_position, dest_position ); src_position += offset; dest_position += offset; if dest_position > dest_offset { break; } } } else if length > FASTCOPY_BYTES { current_position += FASTCOPY_BYTES; // fast non-overlapping copy // // We have enough space to write the ML+FAST_COPY bytes ahead // so we know this won't come to shoot us in the foot. // // An optimization is to copy FAST_COPY_BITS per invocation // Currently FASTCOPY_BYTES is 16, this fits in nicely as we // it's a single SIMD instruction on a lot of things, i.e x86,Arm and even // wasm. // current position of the match let mut dest_src_offset = src_offset + FASTCOPY_BYTES; // Number of bytes we are to copy // copy in batches of FAST_BYTES 'match_lengths: loop { // Safety: We resized out_block hence we know it can handle // sloppy copies without it being out of bounds // // Reason: This is a latency critical loop, even branches start // to matter fixed_copy_within::( &mut out_block, dest_src_offset, current_position ); dest_src_offset += FASTCOPY_BYTES; current_position += FASTCOPY_BYTES; if current_position > dest_offset { break 'match_lengths; } } } if dest_offset > self.options.limit { out_block.truncate(dest_offset); let err_msg = DecodeErrorStatus::OutputLimitExceeded( self.options.limit, dest_offset ); let error = InflateDecodeErrors::new(err_msg, out_block); return Err(error); } if self.stream.src.len() < self.stream.position + 8 { // close to input end, move to the slower one break 'sequence; } } } // generic loop that does things a bit slower but it's okay since it doesn't // deal with a lot of things // We can afford to be more careful here, checking that we do // not drop non-existent bits etc etc as we do not have the // assurances of the fast loop bits above. loop { self.stream.refill(); if self.stream.over_read > usize::from(self.stream.bits_left >> 3) { out_block.truncate(dest_offset); let err_msg = DecodeErrorStatus::CorruptData; let error = InflateDecodeErrors::new(err_msg, out_block); return Err(error); } let literal_mask = self.stream.peek_bits::(); entry = litlen_decode_table[literal_mask]; saved_bitbuf = self.stream.buffer; self.stream.drop_bits((entry & 0xFF) as u8); if (entry & HUFFDEC_SUITABLE_POINTER) != 0 { let extra = self.stream.peek_var_bits(((entry >> 8) & 0x3F) as usize); entry = litlen_decode_table[(entry >> 16) as usize + extra]; saved_bitbuf = self.stream.buffer; self.stream.drop_bits((entry & 0xFF) as u8); } length = (entry >> 16) as usize; if (entry & HUFFDEC_LITERAL) != 0 { resize_and_push(&mut out_block, dest_offset, length as u8); dest_offset += 1; continue; } if (entry & HUFFDEC_END_OF_BLOCK) != 0 { break 'decode; } let mask = (1 << entry as u8) - 1; length += (saved_bitbuf & mask) as usize >> ((entry >> 8) as u8); self.stream.refill(); entry = offset_decode_table[self.stream.peek_bits::()]; if (entry & HUFFDEC_EXCEPTIONAL) != 0 { // offset requires a subtable self.stream.drop_bits(OFFSET_TABLEBITS as u8); let extra = self.stream.peek_var_bits(((entry >> 8) & 0x3F) as usize); entry = offset_decode_table[((entry >> 16) as usize + extra) & 511]; } // ensure there is enough space for a fast copy if dest_offset + length + FASTCOPY_BYTES > out_block.len() { let new_len = out_block.len() + RESIZE_BY + length; out_block.resize(new_len, 0); } saved_bitbuf = self.stream.buffer; let mask = (1 << (entry & 0xFF) as u8) - 1; offset = (entry >> 16) as usize; offset += (saved_bitbuf & mask) as usize >> ((entry >> 8) as u8); if offset > dest_offset { out_block.truncate(dest_offset); let err_msg = DecodeErrorStatus::CorruptData; let error = InflateDecodeErrors::new(err_msg, out_block); return Err(error); } src_offset = dest_offset - offset; self.stream.drop_bits(entry as u8); let (dest_src, dest_ptr) = out_block.split_at_mut(dest_offset); if src_offset + length + FASTCOPY_BYTES > dest_offset { // overlapping copy // do a simple rep match copy_rep_matches(&mut out_block, src_offset, dest_offset, length); } else { dest_ptr[0..length] .copy_from_slice(&dest_src[src_offset..src_offset + length]); } dest_offset += length; if dest_offset > self.options.limit { out_block.truncate(dest_offset); let err_msg = DecodeErrorStatus::OutputLimitExceeded(self.options.limit, dest_offset); let error = InflateDecodeErrors::new(err_msg, out_block); return Err(error); } } } /* * If any of the implicit appended zero bytes were consumed (not just * refilled) before hitting end of stream, then the data is bad. */ if self.stream.over_read > usize::from(self.stream.bits_left >> 3) { out_block.truncate(dest_offset); let err_msg = DecodeErrorStatus::CorruptData; let error = InflateDecodeErrors::new(err_msg, out_block); return Err(error); } if self.is_last_block { break; } } // decompression. DONE // Truncate data to match the number of actual // bytes written. out_block.truncate(dest_offset); Ok(out_block) } /// Build decode tables for static and dynamic /// huffman blocks. fn build_decode_table(&mut self, block_type: u64) -> Result<(), DecodeErrorStatus> { const COUNT: usize = DEFLATE_NUM_LITLEN_SYMS + DEFLATE_NUM_OFFSET_SYMS + DELFATE_MAX_LENS_OVERRUN; let mut lens = [0_u8; COUNT]; let mut precode_lens = [0; DEFLATE_NUM_PRECODE_SYMS]; let mut precode_decode_table = [0_u32; PRECODE_ENOUGH]; let mut litlen_decode_table = [0_u32; LITLEN_ENOUGH]; let mut offset_decode_table = [0; OFFSET_ENOUGH]; let mut num_litlen_syms = 0; let mut num_offset_syms = 0; if block_type == DEFLATE_BLOCKTYPE_DYNAMIC_HUFFMAN { const SINGLE_PRECODE: usize = 3; self.static_codes_loaded = false; // Dynamic Huffman block // Read codeword lengths if !self.stream.has(5 + 5 + 4) { return Err(DecodeErrorStatus::InsufficientData); } num_litlen_syms = 257 + (self.stream.get_bits(5)) as usize; num_offset_syms = 1 + (self.stream.get_bits(5)) as usize; let num_explicit_precode_lens = 4 + (self.stream.get_bits(4)) as usize; self.stream.refill(); if !self.stream.has(3) { return Err(DecodeErrorStatus::InsufficientData); } let first_precode = self.stream.get_bits(3) as u8; let expected = (SINGLE_PRECODE * num_explicit_precode_lens.saturating_sub(1)) as u8; precode_lens[usize::from(DEFLATE_PRECODE_LENS_PERMUTATION[0])] = first_precode; self.stream.refill(); if !self.stream.has(expected) { return Err(DecodeErrorStatus::InsufficientData); } for i in DEFLATE_PRECODE_LENS_PERMUTATION[1..] .iter() .take(num_explicit_precode_lens - 1) { let bits = self.stream.get_bits(3) as u8; precode_lens[usize::from(*i)] = bits; } self.build_decode_table_inner( &precode_lens, &PRECODE_DECODE_RESULTS, &mut precode_decode_table, PRECODE_TABLE_BITS, DEFLATE_NUM_PRECODE_SYMS, DEFLATE_MAX_CODEWORD_LENGTH )?; /* Decode the litlen and offset codeword lengths. */ let mut i = 0; loop { if i >= num_litlen_syms + num_offset_syms { // confirm here since with a continue loop stuff // breaks break; } let rep_val: u8; let rep_count: u64; if !self.stream.has(DEFLATE_MAX_PRE_CODEWORD_LEN + 7) { self.stream.refill(); } // decode next pre-code symbol let entry_pos = self .stream .peek_bits::<{ DEFLATE_MAX_PRE_CODEWORD_LEN as usize }>(); let entry = precode_decode_table[entry_pos]; let presym = entry >> 16; if !self.stream.has(entry as u8) { return Err(DecodeErrorStatus::InsufficientData); } self.stream.drop_bits(entry as u8); if presym < 16 { // explicit codeword length lens[i] = presym as u8; i += 1; continue; } /* Run-length encoded codeword lengths */ /* * Note: we don't need verify that the repeat count * doesn't overflow the number of elements, since we've * sized the lens array to have enough extra space to * allow for the worst-case overrun (138 zeroes when * only 1 length was remaining). * * In the case of the small repeat counts (presyms 16 * and 17), it is fastest to always write the maximum * number of entries. That gets rid of branches that * would otherwise be required. * * It is not just because of the numerical order that * our checks go in the order 'presym < 16', 'presym == * 16', and 'presym == 17'. For typical data this is * ordered from most frequent to least frequent case. */ if presym == 16 { if i == 0 { return Err(DecodeErrorStatus::CorruptData); } if !self.stream.has(2) { return Err(DecodeErrorStatus::InsufficientData); } // repeat previous length three to 6 times rep_val = lens[i - 1]; rep_count = 3 + self.stream.get_bits(2); lens[i..i + 6].fill(rep_val); i += rep_count as usize; } else if presym == 17 { if !self.stream.has(3) { return Err(DecodeErrorStatus::InsufficientData); } /* Repeat zero 3 - 10 times. */ rep_count = 3 + self.stream.get_bits(3); lens[i..i + 10].fill(0); i += rep_count as usize; } else { if !self.stream.has(7) { return Err(DecodeErrorStatus::InsufficientData); } // repeat zero 11-138 times. rep_count = 11 + self.stream.get_bits(7); lens[i..i + rep_count as usize].fill(0); i += rep_count as usize; } if i >= num_litlen_syms + num_offset_syms { break; } } } else if block_type == DEFLATE_BLOCKTYPE_STATIC { if self.static_codes_loaded { return Ok(()); } self.static_codes_loaded = true; lens[000..144].fill(8); lens[144..256].fill(9); lens[256..280].fill(7); lens[280..288].fill(8); lens[288..].fill(5); num_litlen_syms = 288; num_offset_syms = 32; } // build offset decode table self.build_decode_table_inner( &lens[num_litlen_syms..], &OFFSET_DECODE_RESULTS, &mut offset_decode_table, OFFSET_TABLEBITS, num_offset_syms, DEFLATE_MAX_OFFSET_CODEWORD_LENGTH )?; self.build_decode_table_inner( &lens, &LITLEN_DECODE_RESULTS, &mut litlen_decode_table, LITLEN_TABLE_BITS, num_litlen_syms, DEFLATE_MAX_LITLEN_CODEWORD_LENGTH )?; self.deflate_header_tables.offset_decode_table = offset_decode_table; self.deflate_header_tables.litlen_decode_table = litlen_decode_table; Ok(()) } /// Build the decode table for the precode #[allow(clippy::needless_range_loop)] fn build_decode_table_inner( &mut self, lens: &[u8], decode_results: &[u32], decode_table: &mut [u32], table_bits: usize, num_syms: usize, mut max_codeword_len: usize ) -> Result<(), DecodeErrorStatus> { const BITS: u32 = usize::BITS - 1; let mut len_counts: [u32; DEFLATE_MAX_CODEWORD_LENGTH + 1] = [0; DEFLATE_MAX_CODEWORD_LENGTH + 1]; let mut offsets: [u32; DEFLATE_MAX_CODEWORD_LENGTH + 1] = [0; DEFLATE_MAX_CODEWORD_LENGTH + 1]; let mut sorted_syms: [u16; DEFLATE_MAX_NUM_SYMS] = [0; DEFLATE_MAX_NUM_SYMS]; let mut i; // count how many codewords have each length, including 0. for sym in 0..num_syms { len_counts[usize::from(lens[sym])] += 1; } /* * Determine the actual maximum codeword length that was used, and * decrease table_bits to it if allowed. */ while max_codeword_len > 1 && len_counts[max_codeword_len] == 0 { max_codeword_len -= 1; } /* * Sort the symbols primarily by increasing codeword length and * A temporary array of length @num_syms. * secondarily by increasing symbol value; or equivalently by their * codewords in lexicographic order, since a canonical code is assumed. * * For efficiency, also compute 'codespace_used' in the same pass over * 'len_counts[]' used to build 'offsets[]' for sorting. */ offsets[0] = 0; offsets[1] = len_counts[0]; let mut codespace_used = 0_u32; for len in 1..max_codeword_len { offsets[len + 1] = offsets[len] + len_counts[len]; codespace_used = (codespace_used << 1) + len_counts[len]; } codespace_used = (codespace_used << 1) + len_counts[max_codeword_len]; for sym in 0..num_syms { let pos = usize::from(lens[sym]); sorted_syms[offsets[pos] as usize] = sym as u16; offsets[pos] += 1; } i = (offsets[0]) as usize; /* * Check whether the lengths form a complete code (exactly fills the * codespace), an incomplete code (doesn't fill the codespace), or an * overfull code (overflows the codespace). A codeword of length 'n' * uses proportion '1/(2^n)' of the codespace. An overfull code is * nonsensical, so is considered invalid. An incomplete code is * considered valid only in two specific cases; see below. */ // Overfull code if codespace_used > 1 << max_codeword_len { return Err(DecodeErrorStatus::Generic("Overflown code")); } // incomplete code if codespace_used < 1 << max_codeword_len { let entry = if codespace_used == 0 { /* * An empty code is allowed. This can happen for the * offset code in DEFLATE, since a dynamic Huffman block * need not contain any matches. */ /* sym=0, len=1 (arbitrary) */ make_decode_table_entry(decode_results, 0, 1) } else { /* * Allow codes with a single used symbol, with codeword * length 1. The DEFLATE RFC is unclear regarding this * case. What zlib's decompressor does is permit this * for the litlen and offset codes and assume the * codeword is '0' rather than '1'. We do the same * except we allow this for precodes too, since there's * no convincing reason to treat the codes differently. * We also assign both codewords '0' and '1' to the * symbol to avoid having to handle '1' specially. */ if codespace_used != 1 << (max_codeword_len - 1) || len_counts[1] != 1 { return Err(DecodeErrorStatus::Generic( "Cannot work with empty pre-code table" )); } make_decode_table_entry(decode_results, usize::from(sorted_syms[i]), 1) }; /* * Note: the decode table still must be fully initialized, in * case the stream is malformed and contains bits from the part * of the codespace the incomplete code doesn't use. */ decode_table.fill(entry); return Ok(()); } /* * The lengths form a complete code. Now, enumerate the codewords in * lexicographic order and fill the decode table entries for each one. * * First, process all codewords with len <= table_bits. Each one gets * '2^(table_bits-len)' direct entries in the table. * * Since DEFLATE uses bit-reversed codewords, these entries aren't * consecutive but rather are spaced '2^len' entries apart. This makes * filling them naively somewhat awkward and inefficient, since strided * stores are less cache-friendly and preclude the use of word or * vector-at-a-time stores to fill multiple entries per instruction. * * To optimize this, we incrementally double the table size. When * processing codewords with length 'len', the table is treated as * having only '2^len' entries, so each codeword uses just one entry. * Then, each time 'len' is incremented, the table size is doubled and * the first half is copied to the second half. This significantly * improves performance over naively doing strided stores. * * Note that some entries copied for each table doubling may not have * been initialized yet, but it doesn't matter since they're guaranteed * to be initialized later (because the Huffman code is complete). */ let mut codeword = 0; let mut len = 1; let mut count = len_counts[1]; while count == 0 { len += 1; if len >= len_counts.len() { break; } count = len_counts[len]; } let mut curr_table_end = 1 << len; while len <= table_bits { // Process all count codewords with length len loop { let entry = make_decode_table_entry( decode_results, usize::from(sorted_syms[i]), len as u32 ); i += 1; // fill first entry for current codeword decode_table[codeword] = entry; if codeword == curr_table_end - 1 { // last codeword (all 1's) for _ in len..table_bits { decode_table.copy_within(0..curr_table_end, curr_table_end); curr_table_end <<= 1; } return Ok(()); } /* * To advance to the lexicographically next codeword in * the canonical code, the codeword must be incremented, * then 0's must be appended to the codeword as needed * to match the next codeword's length. * * Since the codeword is bit-reversed, appending 0's is * a no-op. However, incrementing it is nontrivial. To * do so efficiently, use the 'bsr' instruction to find * the last (highest order) 0 bit in the codeword, set * it, and clear any later (higher order) 1 bits. But * 'bsr' actually finds the highest order 1 bit, so to * use it first flip all bits in the codeword by XOR' ing * it with (1U << len) - 1 == cur_table_end - 1. */ let adv = BITS - (codeword ^ (curr_table_end - 1)).leading_zeros(); let bit = 1 << adv; codeword &= bit - 1; codeword |= bit; count -= 1; if count == 0 { break; } } // advance to the next codeword length loop { len += 1; if len <= table_bits { // dest is decode_table[curr_table_end] // source is decode_table(start of table); // size is curr_table; decode_table.copy_within(0..curr_table_end, curr_table_end); //decode_table.copy_within(range, curr_table_end); curr_table_end <<= 1; } count = len_counts[len]; if count != 0 { break; } } } // process codewords with len > table_bits. // Require sub-tables curr_table_end = 1 << table_bits; let mut subtable_prefix = usize::MAX; let mut subtable_start = 0; let mut subtable_bits; loop { /* * Start a new sub-table if the first 'table_bits' bits of the * codeword don't match the prefix of the current subtable. */ if codeword & ((1_usize << table_bits) - 1) != subtable_prefix { subtable_prefix = codeword & ((1 << table_bits) - 1); subtable_start = curr_table_end; /* * Calculate the subtable length. If the codeword has * length 'table_bits + n', then the subtable needs * '2^n' entries. But it may need more; if fewer than * '2^n' codewords of length 'table_bits + n' remain, * then the length will need to be incremented to bring * in longer codewords until the subtable can be * completely filled. Note that because the Huffman * code is complete, it will always be possible to fill * the sub-table eventually. */ subtable_bits = len - table_bits; codespace_used = count; while codespace_used < (1 << subtable_bits) { subtable_bits += 1; if subtable_bits + table_bits > 15 { return Err(DecodeErrorStatus::CorruptData); } codespace_used = (codespace_used << 1) + len_counts[table_bits + subtable_bits]; } /* * Create the entry that points from the main table to * the subtable. */ decode_table[subtable_prefix] = (subtable_start as u32) << 16 | HUFFDEC_EXCEPTIONAL | HUFFDEC_SUITABLE_POINTER | (subtable_bits as u32) << 8 | table_bits as u32; curr_table_end = subtable_start + (1 << subtable_bits); } /* Fill the sub-table entries for the current codeword. */ let stride = 1 << (len - table_bits); let mut j = subtable_start + (codeword >> table_bits); let entry = make_decode_table_entry( decode_results, sorted_syms[i] as usize, (len - table_bits) as u32 ); i += 1; while j < curr_table_end { decode_table[j] = entry; j += stride; } //advance to the next codeword if codeword == (1 << len) - 1 { // last codeword return Ok(()); } let adv = BITS - (codeword ^ ((1 << len) - 1)).leading_zeros(); let bit = 1 << adv; codeword &= bit - 1; codeword |= bit; count -= 1; while count == 0 { len += 1; count = len_counts[len]; } } } } const RESIZE_BY: usize = 1024 * 4; // 4 kb /// Resize vector if its current space wont /// be able to store a new byte and then push an element to that new space #[inline(always)] fn resize_and_push(buf: &mut Vec, position: usize, elm: u8) { if buf.len() <= position { let new_len = buf.len() + RESIZE_BY; buf.resize(new_len, 0); } buf[position] = elm; }