//! 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<dyn Stateful + Send + 'static>,
}
/// 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<StreamBuf<'d>>,
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<StreamBuf<'d>>,
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<u8>,
}
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<Code>;
/// Refill the internal buffer.
fn refill_bits(&mut self, inp: &mut &[u8]);
/// Get the next buffered code word.
fn get_bits(&mut self) -> Option<Code>;
fn max_code(&self) -> Code;
fn code_size(&self) -> u8;
}
struct DecodeState<CodeBuffer> {
/// 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<Link>,
depths: Vec<u16>,
}
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<dyn Stateful + Send + 'static>;
super::assert_decode_size(size);
let state = match order {
BitOrder::Lsb => Box::new(DecodeState::<LsbBuffer>::new(size)) as Boxed,
BitOrder::Msb => Box::new(DecodeState::<MsbBuffer>::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<dyn Stateful + Send + 'static>;
super::assert_decode_size(size);
let state = match order {
BitOrder::Lsb => {
let mut state = Box::new(DecodeState::<LsbBuffer>::new(size));
state.is_tiff = true;
state as Boxed
}
BitOrder::Msb => {
let mut state = Box::new(DecodeState::<MsbBuffer>::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<Vec<u8>, 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<W: Write>(&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<W: futures::io::AsyncWrite>(&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<u8>) -> 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<C: CodeBuffer> DecodeState<C> {
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<C: CodeBuffer> Stateful for DecodeState<C> {
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<C: CodeBuffer> DecodeState<C> {
fn next_symbol(&mut self, inp: &mut &[u8]) -> Option<Code> {
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<Code> {
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<Code> {
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<Code> {
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<Code> {
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<Code> {
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<u8> {
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: std::io::Write>(W);
const BUF_SIZE: usize = 512;
impl<W: std::io::Write> std::io::Write for WriteTap<W> {
fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
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);
}
}
}
}