//! A module for all decoding needs. #[cfg(feature = "std")] use crate::error::StreamResult; use crate::error::{BufferResult, LzwError, LzwStatus, VectorResult}; use crate::{BitOrder, Code, StreamBuf, MAX_CODESIZE, MAX_ENTRIES, STREAM_BUF_SIZE}; use crate::alloc::{boxed::Box, vec, vec::Vec}; #[cfg(feature = "std")] use std::io::{self, BufRead, Write}; /// The state for decoding data with an LZW algorithm. /// /// The same structure can be utilized with streams as well as your own buffers and driver logic. /// It may even be possible to mix them if you are sufficiently careful not to lose or skip any /// already decode data in the process. /// /// This is a sans-IO implementation, meaning that it only contains the state of the decoder and /// the caller will provide buffers for input and output data when calling the basic /// [`decode_bytes`] method. Nevertheless, a number of _adapters_ are provided in the `into_*` /// methods for decoding with a particular style of common IO. /// /// * [`decode`] for decoding once without any IO-loop. /// * [`into_async`] for decoding with the `futures` traits for asynchronous IO. /// * [`into_stream`] for decoding with the standard `io` traits. /// * [`into_vec`] for in-memory decoding. /// /// [`decode_bytes`]: #method.decode_bytes /// [`decode`]: #method.decode /// [`into_async`]: #method.into_async /// [`into_stream`]: #method.into_stream /// [`into_vec`]: #method.into_vec pub struct Decoder { state: Box, } /// A decoding stream sink. /// /// See [`Decoder::into_stream`] on how to create this type. /// /// [`Decoder::into_stream`]: struct.Decoder.html#method.into_stream #[cfg_attr( not(feature = "std"), deprecated = "This type is only useful with the `std` feature." )] #[cfg_attr(not(feature = "std"), allow(dead_code))] pub struct IntoStream<'d, W> { decoder: &'d mut Decoder, writer: W, buffer: Option>, default_size: usize, } /// An async decoding sink. /// /// See [`Decoder::into_async`] on how to create this type. /// /// [`Decoder::into_async`]: struct.Decoder.html#method.into_async #[cfg(feature = "async")] pub struct IntoAsync<'d, W> { decoder: &'d mut Decoder, writer: W, buffer: Option>, default_size: usize, } /// A decoding sink into a vector. /// /// See [`Decoder::into_vec`] on how to create this type. /// /// [`Decoder::into_vec`]: struct.Decoder.html#method.into_vec pub struct IntoVec<'d> { decoder: &'d mut Decoder, vector: &'d mut Vec, } trait Stateful { fn advance(&mut self, inp: &[u8], out: &mut [u8]) -> BufferResult; fn has_ended(&self) -> bool; /// Ignore an end code and continue decoding (no implied reset). fn restart(&mut self); /// Reset the decoder to the beginning, dropping all buffers etc. fn reset(&mut self); } #[derive(Clone)] struct Link { prev: Code, byte: u8, } #[derive(Default)] struct MsbBuffer { /// A buffer of individual bits. The oldest code is kept in the high-order bits. bit_buffer: u64, /// A precomputed mask for this code. code_mask: u16, /// The current code size. code_size: u8, /// The number of bits in the buffer. bits: u8, } #[derive(Default)] struct LsbBuffer { /// A buffer of individual bits. The oldest code is kept in the high-order bits. bit_buffer: u64, /// A precomputed mask for this code. code_mask: u16, /// The current code size. code_size: u8, /// The number of bits in the buffer. bits: u8, } trait CodeBuffer { fn new(min_size: u8) -> Self; fn reset(&mut self, min_size: u8); fn bump_code_size(&mut self); /// Retrieve the next symbol, refilling if necessary. fn next_symbol(&mut self, inp: &mut &[u8]) -> Option; /// Refill the internal buffer. fn refill_bits(&mut self, inp: &mut &[u8]); /// Get the next buffered code word. fn get_bits(&mut self) -> Option; fn max_code(&self) -> Code; fn code_size(&self) -> u8; } struct DecodeState { /// The original minimum code size. min_size: u8, /// The table of decoded codes. table: Table, /// The buffer of decoded data. buffer: Buffer, /// The link which we are still decoding and its original code. last: Option<(Code, Link)>, /// The next code entry. next_code: Code, /// Code to reset all tables. clear_code: Code, /// Code to signal the end of the stream. end_code: Code, /// A stored flag if the end code has already appeared. has_ended: bool, /// If tiff then bumps are a single code sooner. is_tiff: bool, /// Do we allow stream to start without an explicit reset code? implicit_reset: bool, /// The buffer for decoded words. code_buffer: CodeBuffer, } struct Buffer { bytes: Box<[u8]>, read_mark: usize, write_mark: usize, } struct Table { inner: Vec, depths: Vec, } impl Decoder { /// Create a new decoder with the specified bit order and symbol size. /// /// The algorithm for dynamically increasing the code symbol bit width is compatible with the /// original specification. In particular you will need to specify an `Lsb` bit oder to decode /// the data portion of a compressed `gif` image. /// /// # Panics /// /// The `size` needs to be in the interval `0..=12`. pub fn new(order: BitOrder, size: u8) -> Self { type Boxed = Box; super::assert_decode_size(size); let state = match order { BitOrder::Lsb => Box::new(DecodeState::::new(size)) as Boxed, BitOrder::Msb => Box::new(DecodeState::::new(size)) as Boxed, }; Decoder { state } } /// Create a TIFF compatible decoder with the specified bit order and symbol size. /// /// The algorithm for dynamically increasing the code symbol bit width is compatible with the /// TIFF specification, which is a misinterpretation of the original algorithm for increasing /// the code size. It switches one symbol sooner. /// /// # Panics /// /// The `size` needs to be in the interval `0..=12`. pub fn with_tiff_size_switch(order: BitOrder, size: u8) -> Self { type Boxed = Box; super::assert_decode_size(size); let state = match order { BitOrder::Lsb => { let mut state = Box::new(DecodeState::::new(size)); state.is_tiff = true; state as Boxed } BitOrder::Msb => { let mut state = Box::new(DecodeState::::new(size)); state.is_tiff = true; state as Boxed } }; Decoder { state } } /// Decode some bytes from `inp` and write result to `out`. /// /// This will consume a prefix of the input buffer and write decoded output into a prefix of /// the output buffer. See the respective fields of the return value for the count of consumed /// and written bytes. For the next call You should have adjusted the inputs accordingly. /// /// The call will try to decode and write as many bytes of output as available. It will be /// much more optimized (and avoid intermediate buffering) if it is allowed to write a large /// contiguous chunk at once. /// /// See [`into_stream`] for high-level functions (that are only available with the `std` /// feature). /// /// [`into_stream`]: #method.into_stream pub fn decode_bytes(&mut self, inp: &[u8], out: &mut [u8]) -> BufferResult { self.state.advance(inp, out) } /// Decode a single chunk of lzw encoded data. /// /// This method requires the data to contain an end marker, and returns an error otherwise. /// /// This is a convenience wrapper around [`into_vec`]. Use the `into_vec` adapter to customize /// buffer size, to supply an existing vector, to control whether an end marker is required, or /// to preserve partial data in the case of a decoding error. /// /// [`into_vec`]: #into_vec /// /// # Example /// /// ``` /// use weezl::{BitOrder, decode::Decoder}; /// /// // Encoded that was created with an encoder. /// let data = b"\x80\x04\x81\x94l\x1b\x06\xf0\xb0 \x1d\xc6\xf1\xc8l\x19 \x10"; /// let decoded = Decoder::new(BitOrder::Msb, 9) /// .decode(data) /// .unwrap(); /// assert_eq!(decoded, b"Hello, world"); /// ``` pub fn decode(&mut self, data: &[u8]) -> Result, LzwError> { let mut output = vec![]; self.into_vec(&mut output).decode_all(data).status?; Ok(output) } /// Construct a decoder into a writer. #[cfg(feature = "std")] pub fn into_stream(&mut self, writer: W) -> IntoStream<'_, W> { IntoStream { decoder: self, writer, buffer: None, default_size: STREAM_BUF_SIZE, } } /// Construct a decoder into an async writer. #[cfg(feature = "async")] pub fn into_async(&mut self, writer: W) -> IntoAsync<'_, W> { IntoAsync { decoder: self, writer, buffer: None, default_size: STREAM_BUF_SIZE, } } /// Construct a decoder into a vector. /// /// All decoded data is appended and the vector is __not__ cleared. /// /// Compared to `into_stream` this interface allows a high-level access to decoding without /// requires the `std`-feature. Also, it can make full use of the extra buffer control that the /// special target exposes. pub fn into_vec<'lt>(&'lt mut self, vec: &'lt mut Vec) -> IntoVec<'lt> { IntoVec { decoder: self, vector: vec, } } /// Check if the decoding has finished. /// /// No more output is produced beyond the end code that marked the finish of the stream. The /// decoder may have read additional bytes, including padding bits beyond the last code word /// but also excess bytes provided. pub fn has_ended(&self) -> bool { self.state.has_ended() } /// Ignore an end code and continue. /// /// This will _not_ reset any of the inner code tables and not have the effect of a clear code. /// It will instead continue as if the end code had not been present. If no end code has /// occurred then this is a no-op. /// /// You can test if an end code has occurred with [`has_ended`](#method.has_ended). /// FIXME: clarify how this interacts with padding introduced after end code. #[allow(dead_code)] pub(crate) fn restart(&mut self) { self.state.restart(); } /// Reset all internal state. /// /// This produce a decoder as if just constructed with `new` but taking slightly less work. In /// particular it will not deallocate any internal allocations. It will also avoid some /// duplicate setup work. pub fn reset(&mut self) { self.state.reset(); } } #[cfg(feature = "std")] impl<'d, W: Write> IntoStream<'d, W> { /// Decode data from a reader. /// /// This will read data until the stream is empty or an end marker is reached. pub fn decode(&mut self, read: impl BufRead) -> StreamResult { self.decode_part(read, false) } /// Decode data from a reader, requiring an end marker. pub fn decode_all(mut self, read: impl BufRead) -> StreamResult { self.decode_part(read, true) } /// Set the size of the intermediate decode buffer. /// /// A buffer of this size is allocated to hold one part of the decoded stream when no buffer is /// available and any decoding method is called. No buffer is allocated if `set_buffer` has /// been called. The buffer is reused. /// /// # Panics /// This method panics if `size` is `0`. pub fn set_buffer_size(&mut self, size: usize) { assert_ne!(size, 0, "Attempted to set empty buffer"); self.default_size = size; } /// Use a particular buffer as an intermediate decode buffer. /// /// Calling this sets or replaces the buffer. When a buffer has been set then it is used /// instead of dynamically allocating a buffer. Note that the size of the buffer is critical /// for efficient decoding. Some optimization techniques require the buffer to hold one or more /// previous decoded words. There is also additional overhead from `write` calls each time the /// buffer has been filled. /// /// # Panics /// This method panics if the `buffer` is empty. pub fn set_buffer(&mut self, buffer: &'d mut [u8]) { assert_ne!(buffer.len(), 0, "Attempted to set empty buffer"); self.buffer = Some(StreamBuf::Borrowed(buffer)); } fn decode_part(&mut self, mut read: impl BufRead, must_finish: bool) -> StreamResult { let IntoStream { decoder, writer, buffer, default_size, } = self; enum Progress { Ok, Done, } let mut bytes_read = 0; let mut bytes_written = 0; // Converting to mutable refs to move into the `once` closure. let read_bytes = &mut bytes_read; let write_bytes = &mut bytes_written; let outbuf: &mut [u8] = match { buffer.get_or_insert_with(|| StreamBuf::Owned(vec![0u8; *default_size])) } { StreamBuf::Borrowed(slice) => &mut *slice, StreamBuf::Owned(vec) => &mut *vec, }; assert!(!outbuf.is_empty()); let once = move || { // Try to grab one buffer of input data. let data = read.fill_buf()?; // Decode as much of the buffer as fits. let result = decoder.decode_bytes(data, &mut outbuf[..]); // Do the bookkeeping and consume the buffer. *read_bytes += result.consumed_in; *write_bytes += result.consumed_out; read.consume(result.consumed_in); // Handle the status in the result. let done = result.status.map_err(|err| { io::Error::new(io::ErrorKind::InvalidData, &*format!("{:?}", err)) })?; // Check if we had any new data at all. if let LzwStatus::NoProgress = done { debug_assert_eq!( result.consumed_out, 0, "No progress means we have not decoded any data" ); // In particular we did not finish decoding. if must_finish { return Err(io::Error::new( io::ErrorKind::UnexpectedEof, "No more data but no end marker detected", )); } else { return Ok(Progress::Done); } } // And finish by writing our result. // TODO: we may lose data on error (also on status error above) which we might want to // deterministically handle so that we don't need to restart everything from scratch as // the only recovery strategy. Any changes welcome. writer.write_all(&outbuf[..result.consumed_out])?; Ok(if let LzwStatus::Done = done { Progress::Done } else { Progress::Ok }) }; // Decode chunks of input data until we're done. let status = core::iter::repeat_with(once) // scan+fuse can be replaced with map_while .scan((), |(), result| match result { Ok(Progress::Ok) => Some(Ok(())), Err(err) => Some(Err(err)), Ok(Progress::Done) => None, }) .fuse() .collect(); StreamResult { bytes_read, bytes_written, status, } } } impl IntoVec<'_> { /// Decode data from a slice. /// /// This will read data until the slice is empty or an end marker is reached. pub fn decode(&mut self, read: &[u8]) -> VectorResult { self.decode_part(read, false) } /// Decode data from a slice, requiring an end marker. pub fn decode_all(mut self, read: &[u8]) -> VectorResult { self.decode_part(read, true) } fn grab_buffer(&mut self) -> (&mut [u8], &mut Decoder) { const CHUNK_SIZE: usize = 1 << 12; let decoder = &mut self.decoder; let length = self.vector.len(); // Use the vector to do overflow checks and w/e. self.vector.reserve(CHUNK_SIZE); // FIXME: decoding into uninit buffer? self.vector.resize(length + CHUNK_SIZE, 0u8); (&mut self.vector[length..], decoder) } fn decode_part(&mut self, part: &[u8], must_finish: bool) -> VectorResult { let mut result = VectorResult { consumed_in: 0, consumed_out: 0, status: Ok(LzwStatus::Ok), }; enum Progress { Ok, Done, } // Converting to mutable refs to move into the `once` closure. let read_bytes = &mut result.consumed_in; let write_bytes = &mut result.consumed_out; let mut data = part; // A 64 MB buffer is quite large but should get alloc_zeroed. // Note that the decoded size can be up to quadratic in code block. let once = move || { // Grab a new output buffer. let (outbuf, decoder) = self.grab_buffer(); // Decode as much of the buffer as fits. let result = decoder.decode_bytes(data, &mut outbuf[..]); // Do the bookkeeping and consume the buffer. *read_bytes += result.consumed_in; *write_bytes += result.consumed_out; data = &data[result.consumed_in..]; let unfilled = outbuf.len() - result.consumed_out; let filled = self.vector.len() - unfilled; self.vector.truncate(filled); // Handle the status in the result. match result.status { Err(err) => Err(err), Ok(LzwStatus::NoProgress) if must_finish => Err(LzwError::InvalidCode), Ok(LzwStatus::NoProgress) | Ok(LzwStatus::Done) => Ok(Progress::Done), Ok(LzwStatus::Ok) => Ok(Progress::Ok), } }; // Decode chunks of input data until we're done. let status: Result<(), _> = core::iter::repeat_with(once) // scan+fuse can be replaced with map_while .scan((), |(), result| match result { Ok(Progress::Ok) => Some(Ok(())), Err(err) => Some(Err(err)), Ok(Progress::Done) => None, }) .fuse() .collect(); if let Err(err) = status { result.status = Err(err); } result } } // This is implemented in a separate file, so that 1.34.2 does not parse it. Otherwise, it would // trip over the usage of await, which is a reserved keyword in that edition/version. It only // contains an impl block. #[cfg(feature = "async")] #[path = "decode_into_async.rs"] mod impl_decode_into_async; impl DecodeState { fn new(min_size: u8) -> Self { DecodeState { min_size, table: Table::new(), buffer: Buffer::new(), last: None, clear_code: 1 << min_size, end_code: (1 << min_size) + 1, next_code: (1 << min_size) + 2, has_ended: false, is_tiff: false, implicit_reset: true, code_buffer: CodeBuffer::new(min_size), } } fn init_tables(&mut self) { self.code_buffer.reset(self.min_size); self.next_code = (1 << self.min_size) + 2; self.table.init(self.min_size); } fn reset_tables(&mut self) { self.code_buffer.reset(self.min_size); self.next_code = (1 << self.min_size) + 2; self.table.clear(self.min_size); } } impl Stateful for DecodeState { fn has_ended(&self) -> bool { self.has_ended } fn restart(&mut self) { self.has_ended = false; } fn reset(&mut self) { self.table.init(self.min_size); self.buffer.read_mark = 0; self.buffer.write_mark = 0; self.last = None; self.restart(); self.code_buffer = CodeBuffer::new(self.min_size); } fn advance(&mut self, mut inp: &[u8], mut out: &mut [u8]) -> BufferResult { // Skip everything if there is nothing to do. if self.has_ended { return BufferResult { consumed_in: 0, consumed_out: 0, status: Ok(LzwStatus::Done), }; } // Rough description: // We will fill the output slice as much as possible until either there is no more symbols // to decode or an end code has been reached. This requires an internal buffer to hold a // potential tail of the word corresponding to the last symbol. This tail will then be // decoded first before continuing with the regular decoding. The same buffer is required // to persist some symbol state across calls. // // We store the words corresponding to code symbols in an index chain, bytewise, where we // push each decoded symbol. (TODO: wuffs shows some success with 8-byte units). This chain // is traversed for each symbol when it is decoded and bytes are placed directly into the // output slice. In the special case (new_code == next_code) we use an existing decoded // version that is present in either the out bytes of this call or in buffer to copy the // repeated prefix slice. // TODO: I played with a 'decoding cache' to remember the position of long symbols and // avoid traversing the chain, doing a copy of memory instead. It did however not lead to // a serious improvement. It's just unlikely to both have a long symbol and have that // repeated twice in the same output buffer. // // You will also find the (to my knowledge novel) concept of a _decoding burst_ which // gained some >~10% speedup in tests. This is motivated by wanting to use out-of-order // execution as much as possible and for this reason have the least possible stress on // branch prediction. Our decoding table already gives us a lookahead on symbol lengths but // only for re-used codes, not novel ones. This lookahead also makes the loop termination // when restoring each byte of the code word perfectly predictable! So a burst is a chunk // of code words which are all independent of each other, have known lengths _and_ are // guaranteed to fit into the out slice without requiring a buffer. One burst can be // decoded in an extremely tight loop. // // TODO: since words can be at most (1 << MAX_CODESIZE) = 4096 bytes long we could avoid // that intermediate buffer at the expense of not always filling the output buffer // completely. Alternatively we might follow its chain of precursor states twice. This may // be even cheaper if we store more than one byte per link so it really should be // evaluated. // TODO: if the caller was required to provide the previous last word we could also avoid // the buffer for cases where we need it to restore the next code! This could be built // backwards compatible by only doing it after an opt-in call that enables the behaviour. // Record initial lengths for the result that is returned. let o_in = inp.len(); let o_out = out.len(); // The code_link is the previously decoded symbol. // It's used to link the new code back to its predecessor. let mut code_link = None; // The status, which is written to on an invalid code. let mut status = Ok(LzwStatus::Ok); match self.last.take() { // No last state? This is the first code after a reset? None => { match self.next_symbol(&mut inp) { // Plainly invalid code. Some(code) if code > self.next_code => status = Err(LzwError::InvalidCode), // next_code would require an actual predecessor. Some(code) if code == self.next_code => status = Err(LzwError::InvalidCode), // No more symbols available and nothing decoded yet. // Assume that we didn't make progress, this may get reset to Done if we read // some bytes from the input. None => status = Ok(LzwStatus::NoProgress), // Handle a valid code. Some(init_code) => { if init_code == self.clear_code { self.init_tables(); } else if init_code == self.end_code { self.has_ended = true; status = Ok(LzwStatus::Done); } else if self.table.is_empty() { if self.implicit_reset { self.init_tables(); self.buffer.fill_reconstruct(&self.table, init_code); let link = self.table.at(init_code).clone(); code_link = Some((init_code, link)); } else { // We require an explicit reset. status = Err(LzwError::InvalidCode); } } else { // Reconstruct the first code in the buffer. self.buffer.fill_reconstruct(&self.table, init_code); let link = self.table.at(init_code).clone(); code_link = Some((init_code, link)); } } } } // Move the tracking state to the stack. Some(tup) => code_link = Some(tup), }; // Track an empty `burst` (see below) means we made no progress. let mut burst_required_for_progress = false; // Restore the previous state, if any. if let Some((code, link)) = code_link.take() { code_link = Some((code, link)); let remain = self.buffer.buffer(); // Check if we can fully finish the buffer. if remain.len() > out.len() { if out.is_empty() { status = Ok(LzwStatus::NoProgress); } else { out.copy_from_slice(&remain[..out.len()]); self.buffer.consume(out.len()); out = &mut []; } } else if remain.is_empty() { status = Ok(LzwStatus::NoProgress); burst_required_for_progress = true; } else { let consumed = remain.len(); out[..consumed].copy_from_slice(remain); self.buffer.consume(consumed); out = &mut out[consumed..]; burst_required_for_progress = false; } } // The tracking state for a burst. // These are actually initialized later but compiler wasn't smart enough to fully optimize // out the init code so that appears outside th loop. // TODO: maybe we can make it part of the state but it's dubious if that really gives a // benefit over stack usage? Also the slices stored here would need some treatment as we // can't infect the main struct with a lifetime. let mut burst = [0; 6]; let mut bytes = [0u16; 6]; let mut target: [&mut [u8]; 6] = Default::default(); // A special reference to out slice which holds the last decoded symbol. let mut last_decoded: Option<&[u8]> = None; while let Some((mut code, mut link)) = code_link.take() { if out.is_empty() && !self.buffer.buffer().is_empty() { code_link = Some((code, link)); break; } let mut burst_size = 0; // Ensure the code buffer is full, we're about to request some codes. // Note that this also ensures at least one code is in the buffer if any input is left. self.refill_bits(&mut inp); // A burst is a sequence of decodes that are completely independent of each other. This // is the case if neither is an end code, a clear code, or a next code, i.e. we have // all of them in the decoding table and thus known their depths, and additionally if // we can decode them directly into the output buffer. for b in &mut burst { // TODO: does it actually make a perf difference to avoid reading new bits here? *b = match self.get_bits() { None => break, Some(code) => code, }; // We can commit the previous burst code, and will take a slice from the output // buffer. This also avoids the bounds check in the tight loop later. if burst_size > 0 { let len = bytes[burst_size - 1]; let (into, tail) = out.split_at_mut(usize::from(len)); target[burst_size - 1] = into; out = tail; } // Check that we don't overflow the code size with all codes we burst decode. if let Some(potential_code) = self.next_code.checked_add(burst_size as u16) { burst_size += 1; if potential_code == self.code_buffer.max_code() - Code::from(self.is_tiff) { break; } } else { // next_code overflowed break; } // A burst code can't be special. if *b == self.clear_code || *b == self.end_code || *b >= self.next_code { break; } // Read the code length and check that we can decode directly into the out slice. let len = self.table.depths[usize::from(*b)]; if out.len() < usize::from(len) { break; } bytes[burst_size - 1] = len; } // No code left, and no more bytes to fill the buffer. if burst_size == 0 { if burst_required_for_progress { status = Ok(LzwStatus::NoProgress); } code_link = Some((code, link)); break; } burst_required_for_progress = false; // Note that the very last code in the burst buffer doesn't actually belong to the // burst itself. TODO: sometimes it could, we just don't differentiate between the // breaks and a loop end condition above. That may be a speed advantage? let (&new_code, burst) = burst[..burst_size].split_last().unwrap(); // The very tight loop for restoring the actual burst. for (&burst, target) in burst.iter().zip(&mut target[..burst_size - 1]) { let cha = self.table.reconstruct(burst, target); // TODO: this pushes into a Vec, maybe we can make this cleaner. // Theoretically this has a branch and llvm tends to be flaky with code layout for // the case of requiring an allocation (which can't occur in practice). let new_link = self.table.derive(&link, cha, code); self.next_code += 1; code = burst; link = new_link; } // Update the slice holding the last decoded word. if let Some(new_last) = target[..burst_size - 1].last_mut() { let slice = core::mem::replace(new_last, &mut []); last_decoded = Some(&*slice); } // Now handle the special codes. if new_code == self.clear_code { self.reset_tables(); last_decoded = None; continue; } if new_code == self.end_code { self.has_ended = true; status = Ok(LzwStatus::Done); last_decoded = None; break; } if new_code > self.next_code { status = Err(LzwError::InvalidCode); last_decoded = None; break; } let required_len = if new_code == self.next_code { self.table.depths[usize::from(code)] + 1 } else { self.table.depths[usize::from(new_code)] }; let cha; let is_in_buffer; // Check if we will need to store our current state into the buffer. if usize::from(required_len) > out.len() { is_in_buffer = true; if new_code == self.next_code { // last_decoded will be Some if we have restored any code into the out slice. // Otherwise it will still be present in the buffer. if let Some(last) = last_decoded.take() { self.buffer.bytes[..last.len()].copy_from_slice(last); self.buffer.write_mark = last.len(); self.buffer.read_mark = last.len(); } cha = self.buffer.fill_cscsc(); } else { // Restore the decoded word into the buffer. last_decoded = None; cha = self.buffer.fill_reconstruct(&self.table, new_code); } } else { is_in_buffer = false; let (target, tail) = out.split_at_mut(usize::from(required_len)); out = tail; if new_code == self.next_code { // Reconstruct high. let source = match last_decoded.take() { Some(last) => last, None => &self.buffer.bytes[..self.buffer.write_mark], }; cha = source[0]; target[..source.len()].copy_from_slice(source); target[source.len()..][0] = source[0]; } else { cha = self.table.reconstruct(new_code, target); } // A new decoded word. last_decoded = Some(target); } let new_link; // Each newly read code creates one new code/link based on the preceding code if we // have enough space to put it there. if !self.table.is_full() { let link = self.table.derive(&link, cha, code); if self.next_code == self.code_buffer.max_code() - Code::from(self.is_tiff) && self.code_buffer.code_size() < MAX_CODESIZE { self.bump_code_size(); } self.next_code += 1; new_link = link; } else { // It's actually quite likely that the next code will be a reset but just in case. // FIXME: this path hasn't been tested very well. new_link = link.clone(); } // store the information on the decoded word. code_link = Some((new_code, new_link)); // Can't make any more progress with decoding. if is_in_buffer { break; } } // We need to store the last word into the buffer in case the first code in the next // iteration is the next_code. if let Some(tail) = last_decoded { self.buffer.bytes[..tail.len()].copy_from_slice(tail); self.buffer.write_mark = tail.len(); self.buffer.read_mark = tail.len(); } // Ensure we don't indicate that no progress was made if we read some bytes from the input // (which is progress). if o_in > inp.len() { if let Ok(LzwStatus::NoProgress) = status { status = Ok(LzwStatus::Ok); } } // Store the code/link state. self.last = code_link; BufferResult { consumed_in: o_in.wrapping_sub(inp.len()), consumed_out: o_out.wrapping_sub(out.len()), status, } } } impl DecodeState { fn next_symbol(&mut self, inp: &mut &[u8]) -> Option { self.code_buffer.next_symbol(inp) } fn bump_code_size(&mut self) { self.code_buffer.bump_code_size() } fn refill_bits(&mut self, inp: &mut &[u8]) { self.code_buffer.refill_bits(inp) } fn get_bits(&mut self) -> Option { self.code_buffer.get_bits() } } impl CodeBuffer for MsbBuffer { fn new(min_size: u8) -> Self { MsbBuffer { code_size: min_size + 1, code_mask: (1u16 << (min_size + 1)) - 1, bit_buffer: 0, bits: 0, } } fn reset(&mut self, min_size: u8) { self.code_size = min_size + 1; self.code_mask = (1 << self.code_size) - 1; } fn next_symbol(&mut self, inp: &mut &[u8]) -> Option { if self.bits < self.code_size { self.refill_bits(inp); } self.get_bits() } fn bump_code_size(&mut self) { self.code_size += 1; self.code_mask = (self.code_mask << 1) | 1; } fn refill_bits(&mut self, inp: &mut &[u8]) { let wish_count = (64 - self.bits) / 8; let mut buffer = [0u8; 8]; let new_bits = match inp.get(..usize::from(wish_count)) { Some(bytes) => { buffer[..usize::from(wish_count)].copy_from_slice(bytes); *inp = &inp[usize::from(wish_count)..]; wish_count * 8 } None => { let new_bits = inp.len() * 8; buffer[..inp.len()].copy_from_slice(inp); *inp = &[]; new_bits as u8 } }; self.bit_buffer |= u64::from_be_bytes(buffer) >> self.bits; self.bits += new_bits; } fn get_bits(&mut self) -> Option { if self.bits < self.code_size { return None; } let mask = u64::from(self.code_mask); let rotbuf = self.bit_buffer.rotate_left(self.code_size.into()); self.bit_buffer = rotbuf & !mask; self.bits -= self.code_size; Some((rotbuf & mask) as u16) } fn max_code(&self) -> Code { self.code_mask } fn code_size(&self) -> u8 { self.code_size } } impl CodeBuffer for LsbBuffer { fn new(min_size: u8) -> Self { LsbBuffer { code_size: min_size + 1, code_mask: (1u16 << (min_size + 1)) - 1, bit_buffer: 0, bits: 0, } } fn reset(&mut self, min_size: u8) { self.code_size = min_size + 1; self.code_mask = (1 << self.code_size) - 1; } fn next_symbol(&mut self, inp: &mut &[u8]) -> Option { if self.bits < self.code_size { self.refill_bits(inp); } self.get_bits() } fn bump_code_size(&mut self) { self.code_size += 1; self.code_mask = (self.code_mask << 1) | 1; } fn refill_bits(&mut self, inp: &mut &[u8]) { let wish_count = (64 - self.bits) / 8; let mut buffer = [0u8; 8]; let new_bits = match inp.get(..usize::from(wish_count)) { Some(bytes) => { buffer[..usize::from(wish_count)].copy_from_slice(bytes); *inp = &inp[usize::from(wish_count)..]; wish_count * 8 } None => { let new_bits = inp.len() * 8; buffer[..inp.len()].copy_from_slice(inp); *inp = &[]; new_bits as u8 } }; self.bit_buffer |= u64::from_be_bytes(buffer).swap_bytes() << self.bits; self.bits += new_bits; } fn get_bits(&mut self) -> Option { if self.bits < self.code_size { return None; } let mask = u64::from(self.code_mask); let code = self.bit_buffer & mask; self.bit_buffer >>= self.code_size; self.bits -= self.code_size; Some(code as u16) } fn max_code(&self) -> Code { self.code_mask } fn code_size(&self) -> u8 { self.code_size } } impl Buffer { fn new() -> Self { Buffer { bytes: vec![0; MAX_ENTRIES].into_boxed_slice(), read_mark: 0, write_mark: 0, } } /// When encoding a sequence `cScSc` where `c` is any character and `S` is any string /// this results in two codes `AB`, `A` encoding `cS` and `B` encoding `cSc`. Supposing /// the buffer is already filled with the reconstruction of `A`, we can easily fill it /// with the reconstruction of `B`. fn fill_cscsc(&mut self) -> u8 { self.bytes[self.write_mark] = self.bytes[0]; self.write_mark += 1; self.read_mark = 0; self.bytes[0] } // Fill the buffer by decoding from the table fn fill_reconstruct(&mut self, table: &Table, code: Code) -> u8 { self.write_mark = 0; self.read_mark = 0; let depth = table.depths[usize::from(code)]; let mut memory = core::mem::replace(&mut self.bytes, Box::default()); let out = &mut memory[..usize::from(depth)]; let last = table.reconstruct(code, out); self.bytes = memory; self.write_mark = usize::from(depth); last } fn buffer(&self) -> &[u8] { &self.bytes[self.read_mark..self.write_mark] } fn consume(&mut self, amt: usize) { self.read_mark += amt; } } impl Table { fn new() -> Self { Table { inner: Vec::with_capacity(MAX_ENTRIES), depths: Vec::with_capacity(MAX_ENTRIES), } } fn clear(&mut self, min_size: u8) { let static_count = usize::from(1u16 << u16::from(min_size)) + 2; self.inner.truncate(static_count); self.depths.truncate(static_count); } fn init(&mut self, min_size: u8) { self.inner.clear(); self.depths.clear(); for i in 0..(1u16 << u16::from(min_size)) { self.inner.push(Link::base(i as u8)); self.depths.push(1); } // Clear code. self.inner.push(Link::base(0)); self.depths.push(0); // End code. self.inner.push(Link::base(0)); self.depths.push(0); } fn at(&self, code: Code) -> &Link { &self.inner[usize::from(code)] } fn is_empty(&self) -> bool { self.inner.is_empty() } fn is_full(&self) -> bool { self.inner.len() >= MAX_ENTRIES } fn derive(&mut self, from: &Link, byte: u8, prev: Code) -> Link { let link = from.derive(byte, prev); let depth = self.depths[usize::from(prev)] + 1; self.inner.push(link.clone()); self.depths.push(depth); link } fn reconstruct(&self, code: Code, out: &mut [u8]) -> u8 { let mut code_iter = code; let table = &self.inner[..=usize::from(code)]; let len = code_iter; for ch in out.iter_mut().rev() { //(code, cha) = self.table[k as usize]; // Note: This could possibly be replaced with an unchecked array access if // - value is asserted to be < self.next_code() in push // - min_size is asserted to be < MAX_CODESIZE let entry = &table[usize::from(code_iter)]; code_iter = core::cmp::min(len, entry.prev); *ch = entry.byte; } out[0] } } impl Link { fn base(byte: u8) -> Self { Link { prev: 0, byte } } // TODO: this has self type to make it clear we might depend on the old in a future // optimization. However, that has no practical purpose right now. fn derive(&self, byte: u8, prev: Code) -> Self { Link { prev, byte } } } #[cfg(test)] mod tests { use crate::alloc::vec::Vec; #[cfg(feature = "std")] use crate::StreamBuf; use crate::{decode::Decoder, BitOrder}; #[test] fn invalid_code_size_low() { let _ = Decoder::new(BitOrder::Msb, 0); let _ = Decoder::new(BitOrder::Msb, 1); } #[test] #[should_panic] fn invalid_code_size_high() { let _ = Decoder::new(BitOrder::Msb, 14); } fn make_encoded() -> Vec { const FILE: &'static [u8] = include_bytes!(concat!( env!("CARGO_MANIFEST_DIR"), "/benches/binary-8-msb.lzw" )); return Vec::from(FILE); } #[test] #[cfg(feature = "std")] fn into_stream_buffer_no_alloc() { let encoded = make_encoded(); let mut decoder = Decoder::new(BitOrder::Msb, 8); let mut output = vec![]; let mut buffer = [0; 512]; let mut istream = decoder.into_stream(&mut output); istream.set_buffer(&mut buffer[..]); istream.decode(&encoded[..]).status.unwrap(); match istream.buffer { Some(StreamBuf::Borrowed(_)) => {} None => panic!("Decoded without buffer??"), Some(StreamBuf::Owned(_)) => panic!("Unexpected buffer allocation"), } } #[test] #[cfg(feature = "std")] fn into_stream_buffer_small_alloc() { struct WriteTap(W); const BUF_SIZE: usize = 512; impl std::io::Write for WriteTap { fn write(&mut self, buf: &[u8]) -> std::io::Result { assert!(buf.len() <= BUF_SIZE); self.0.write(buf) } fn flush(&mut self) -> std::io::Result<()> { self.0.flush() } } let encoded = make_encoded(); let mut decoder = Decoder::new(BitOrder::Msb, 8); let mut output = vec![]; let mut istream = decoder.into_stream(WriteTap(&mut output)); istream.set_buffer_size(512); istream.decode(&encoded[..]).status.unwrap(); match istream.buffer { Some(StreamBuf::Owned(vec)) => assert!(vec.len() <= BUF_SIZE), Some(StreamBuf::Borrowed(_)) => panic!("Unexpected borrowed buffer, where from?"), None => panic!("Decoded without buffer??"), } } #[test] #[cfg(feature = "std")] fn reset() { let encoded = make_encoded(); let mut decoder = Decoder::new(BitOrder::Msb, 8); let mut reference = None; for _ in 0..2 { let mut output = vec![]; let mut buffer = [0; 512]; let mut istream = decoder.into_stream(&mut output); istream.set_buffer(&mut buffer[..]); istream.decode_all(&encoded[..]).status.unwrap(); decoder.reset(); if let Some(reference) = &reference { assert_eq!(output, *reference); } else { reference = Some(output); } } } }