diff options
Diffstat (limited to 'vendor/zune-inflate/src/decoder.rs')
| -rw-r--r-- | vendor/zune-inflate/src/decoder.rs | 1791 |
1 files changed, 1791 insertions, 0 deletions
diff --git a/vendor/zune-inflate/src/decoder.rs b/vendor/zune-inflate/src/decoder.rs new file mode 100644 index 0000000..105c882 --- /dev/null +++ b/vendor/zune-inflate/src/decoder.rs @@ -0,0 +1,1791 @@ +#![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<u8>` + /// 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<u8>)`: 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<Vec<u8>, 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<u8>` 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<u8>)`: 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<Vec<u8>, 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<u8>` or an error + /// indicating what went wrong. + /// # Arguments + /// - None + /// # Returns + /// Result type containing the decoded data. + /// + /// - `Ok(Vec<u8>)`: 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<Vec<u8>, InflateDecodeErrors> + { + self.start_deflate_block() + } + /// Main inner loop for decompressing deflate data + #[allow(unused_assignments)] + fn start_deflate_block(&mut self) -> Result<Vec<u8>, 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::<LITLEN_DECODE_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::<LITLEN_DECODE_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::<LITLEN_DECODE_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::<LITLEN_DECODE_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::<OFFSET_TABLEBITS>()]; + 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::<FASTCOPY_BYTES>( + &mut out_block, + src_offset, + dest_offset + ); + + entry = litlen_decode_table[self.stream.peek_bits::<LITLEN_DECODE_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::<FASTCOPY_BYTES>( + &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::<FASTCOPY_BYTES>( + &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::<LITLEN_DECODE_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::<OFFSET_TABLEBITS>()]; + + 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<u8>, position: usize, elm: u8) +{ + if buf.len() <= position + { + let new_len = buf.len() + RESIZE_BY; + buf.resize(new_len, 0); + } + buf[position] = elm; +} |