1//! A module for all decoding needs.
2#[cfg(feature = "std")]
3use crate::error::StreamResult;
4use crate::error::{BufferResult, LzwError, LzwStatus, VectorResult};
5use crate::{BitOrder, Code, StreamBuf, MAX_CODESIZE, MAX_ENTRIES, STREAM_BUF_SIZE};
6
7use crate::alloc::{boxed::Box, vec, vec::Vec};
8#[cfg(feature = "std")]
9use std::io::{self, BufRead, Write};
10
11/// The state for decoding data with an LZW algorithm.
12///
13/// The same structure can be utilized with streams as well as your own buffers and driver logic.
14/// It may even be possible to mix them if you are sufficiently careful not to lose or skip any
15/// already decode data in the process.
16///
17/// This is a sans-IO implementation, meaning that it only contains the state of the decoder and
18/// the caller will provide buffers for input and output data when calling the basic
19/// [`decode_bytes`] method. Nevertheless, a number of _adapters_ are provided in the `into_*`
20/// methods for decoding with a particular style of common IO.
21///
22/// * [`decode`] for decoding once without any IO-loop.
23/// * [`into_async`] for decoding with the `futures` traits for asynchronous IO.
24/// * [`into_stream`] for decoding with the standard `io` traits.
25/// * [`into_vec`] for in-memory decoding.
26///
27/// [`decode_bytes`]: #method.decode_bytes
28/// [`decode`]: #method.decode
29/// [`into_async`]: #method.into_async
30/// [`into_stream`]: #method.into_stream
31/// [`into_vec`]: #method.into_vec
32pub struct Decoder {
33 state: Box<dyn Stateful + Send + 'static>,
34}
35
36/// A decoding stream sink.
37///
38/// See [`Decoder::into_stream`] on how to create this type.
39///
40/// [`Decoder::into_stream`]: struct.Decoder.html#method.into_stream
41#[cfg_attr(
42 not(feature = "std"),
43 deprecated = "This type is only useful with the `std` feature."
44)]
45#[cfg_attr(not(feature = "std"), allow(dead_code))]
46pub struct IntoStream<'d, W> {
47 decoder: &'d mut Decoder,
48 writer: W,
49 buffer: Option<StreamBuf<'d>>,
50 default_size: usize,
51}
52
53/// An async decoding sink.
54///
55/// See [`Decoder::into_async`] on how to create this type.
56///
57/// [`Decoder::into_async`]: struct.Decoder.html#method.into_async
58#[cfg(feature = "async")]
59pub struct IntoAsync<'d, W> {
60 decoder: &'d mut Decoder,
61 writer: W,
62 buffer: Option<StreamBuf<'d>>,
63 default_size: usize,
64}
65
66/// A decoding sink into a vector.
67///
68/// See [`Decoder::into_vec`] on how to create this type.
69///
70/// [`Decoder::into_vec`]: struct.Decoder.html#method.into_vec
71pub struct IntoVec<'d> {
72 decoder: &'d mut Decoder,
73 vector: &'d mut Vec<u8>,
74}
75
76trait Stateful {
77 fn advance(&mut self, inp: &[u8], out: &mut [u8]) -> BufferResult;
78 fn has_ended(&self) -> bool;
79 /// Ignore an end code and continue decoding (no implied reset).
80 fn restart(&mut self);
81 /// Reset the decoder to the beginning, dropping all buffers etc.
82 fn reset(&mut self);
83}
84
85#[derive(Clone)]
86struct Link {
87 prev: Code,
88 byte: u8,
89}
90
91#[derive(Default)]
92struct MsbBuffer {
93 /// A buffer of individual bits. The oldest code is kept in the high-order bits.
94 bit_buffer: u64,
95 /// A precomputed mask for this code.
96 code_mask: u16,
97 /// The current code size.
98 code_size: u8,
99 /// The number of bits in the buffer.
100 bits: u8,
101}
102
103#[derive(Default)]
104struct LsbBuffer {
105 /// A buffer of individual bits. The oldest code is kept in the high-order bits.
106 bit_buffer: u64,
107 /// A precomputed mask for this code.
108 code_mask: u16,
109 /// The current code size.
110 code_size: u8,
111 /// The number of bits in the buffer.
112 bits: u8,
113}
114
115trait CodeBuffer {
116 fn new(min_size: u8) -> Self;
117 fn reset(&mut self, min_size: u8);
118 fn bump_code_size(&mut self);
119 /// Retrieve the next symbol, refilling if necessary.
120 fn next_symbol(&mut self, inp: &mut &[u8]) -> Option<Code>;
121 /// Refill the internal buffer.
122 fn refill_bits(&mut self, inp: &mut &[u8]);
123 /// Get the next buffered code word.
124 fn get_bits(&mut self) -> Option<Code>;
125 fn max_code(&self) -> Code;
126 fn code_size(&self) -> u8;
127}
128
129struct DecodeState<CodeBuffer> {
130 /// The original minimum code size.
131 min_size: u8,
132 /// The table of decoded codes.
133 table: Table,
134 /// The buffer of decoded data.
135 buffer: Buffer,
136 /// The link which we are still decoding and its original code.
137 last: Option<(Code, Link)>,
138 /// The next code entry.
139 next_code: Code,
140 /// Code to reset all tables.
141 clear_code: Code,
142 /// Code to signal the end of the stream.
143 end_code: Code,
144 /// A stored flag if the end code has already appeared.
145 has_ended: bool,
146 /// If tiff then bumps are a single code sooner.
147 is_tiff: bool,
148 /// Do we allow stream to start without an explicit reset code?
149 implicit_reset: bool,
150 /// The buffer for decoded words.
151 code_buffer: CodeBuffer,
152}
153
154struct Buffer {
155 bytes: Box<[u8]>,
156 read_mark: usize,
157 write_mark: usize,
158}
159
160struct Table {
161 inner: Vec<Link>,
162 depths: Vec<u16>,
163}
164
165impl Decoder {
166 /// Create a new decoder with the specified bit order and symbol size.
167 ///
168 /// The algorithm for dynamically increasing the code symbol bit width is compatible with the
169 /// original specification. In particular you will need to specify an `Lsb` bit oder to decode
170 /// the data portion of a compressed `gif` image.
171 ///
172 /// # Panics
173 ///
174 /// The `size` needs to be in the interval `0..=12`.
175 pub fn new(order: BitOrder, size: u8) -> Self {
176 type Boxed = Box<dyn Stateful + Send + 'static>;
177 super::assert_decode_size(size);
178 let state = match order {
179 BitOrder::Lsb => Box::new(DecodeState::<LsbBuffer>::new(size)) as Boxed,
180 BitOrder::Msb => Box::new(DecodeState::<MsbBuffer>::new(size)) as Boxed,
181 };
182
183 Decoder { state }
184 }
185
186 /// Create a TIFF compatible decoder with the specified bit order and symbol size.
187 ///
188 /// The algorithm for dynamically increasing the code symbol bit width is compatible with the
189 /// TIFF specification, which is a misinterpretation of the original algorithm for increasing
190 /// the code size. It switches one symbol sooner.
191 ///
192 /// # Panics
193 ///
194 /// The `size` needs to be in the interval `0..=12`.
195 pub fn with_tiff_size_switch(order: BitOrder, size: u8) -> Self {
196 type Boxed = Box<dyn Stateful + Send + 'static>;
197 super::assert_decode_size(size);
198 let state = match order {
199 BitOrder::Lsb => {
200 let mut state = Box::new(DecodeState::<LsbBuffer>::new(size));
201 state.is_tiff = true;
202 state as Boxed
203 }
204 BitOrder::Msb => {
205 let mut state = Box::new(DecodeState::<MsbBuffer>::new(size));
206 state.is_tiff = true;
207 state as Boxed
208 }
209 };
210
211 Decoder { state }
212 }
213
214 /// Decode some bytes from `inp` and write result to `out`.
215 ///
216 /// This will consume a prefix of the input buffer and write decoded output into a prefix of
217 /// the output buffer. See the respective fields of the return value for the count of consumed
218 /// and written bytes. For the next call You should have adjusted the inputs accordingly.
219 ///
220 /// The call will try to decode and write as many bytes of output as available. It will be
221 /// much more optimized (and avoid intermediate buffering) if it is allowed to write a large
222 /// contiguous chunk at once.
223 ///
224 /// See [`into_stream`] for high-level functions (that are only available with the `std`
225 /// feature).
226 ///
227 /// [`into_stream`]: #method.into_stream
228 pub fn decode_bytes(&mut self, inp: &[u8], out: &mut [u8]) -> BufferResult {
229 self.state.advance(inp, out)
230 }
231
232 /// Decode a single chunk of lzw encoded data.
233 ///
234 /// This method requires the data to contain an end marker, and returns an error otherwise.
235 ///
236 /// This is a convenience wrapper around [`into_vec`]. Use the `into_vec` adapter to customize
237 /// buffer size, to supply an existing vector, to control whether an end marker is required, or
238 /// to preserve partial data in the case of a decoding error.
239 ///
240 /// [`into_vec`]: #into_vec
241 ///
242 /// # Example
243 ///
244 /// ```
245 /// use weezl::{BitOrder, decode::Decoder};
246 ///
247 /// // Encoded that was created with an encoder.
248 /// let data = b"\x80\x04\x81\x94l\x1b\x06\xf0\xb0 \x1d\xc6\xf1\xc8l\x19 \x10";
249 /// let decoded = Decoder::new(BitOrder::Msb, 9)
250 /// .decode(data)
251 /// .unwrap();
252 /// assert_eq!(decoded, b"Hello, world");
253 /// ```
254 pub fn decode(&mut self, data: &[u8]) -> Result<Vec<u8>, LzwError> {
255 let mut output = vec![];
256 self.into_vec(&mut output).decode_all(data).status?;
257 Ok(output)
258 }
259
260 /// Construct a decoder into a writer.
261 #[cfg(feature = "std")]
262 pub fn into_stream<W: Write>(&mut self, writer: W) -> IntoStream<'_, W> {
263 IntoStream {
264 decoder: self,
265 writer,
266 buffer: None,
267 default_size: STREAM_BUF_SIZE,
268 }
269 }
270
271 /// Construct a decoder into an async writer.
272 #[cfg(feature = "async")]
273 pub fn into_async<W: futures::io::AsyncWrite>(&mut self, writer: W) -> IntoAsync<'_, W> {
274 IntoAsync {
275 decoder: self,
276 writer,
277 buffer: None,
278 default_size: STREAM_BUF_SIZE,
279 }
280 }
281
282 /// Construct a decoder into a vector.
283 ///
284 /// All decoded data is appended and the vector is __not__ cleared.
285 ///
286 /// Compared to `into_stream` this interface allows a high-level access to decoding without
287 /// requires the `std`-feature. Also, it can make full use of the extra buffer control that the
288 /// special target exposes.
289 pub fn into_vec<'lt>(&'lt mut self, vec: &'lt mut Vec<u8>) -> IntoVec<'lt> {
290 IntoVec {
291 decoder: self,
292 vector: vec,
293 }
294 }
295
296 /// Check if the decoding has finished.
297 ///
298 /// No more output is produced beyond the end code that marked the finish of the stream. The
299 /// decoder may have read additional bytes, including padding bits beyond the last code word
300 /// but also excess bytes provided.
301 pub fn has_ended(&self) -> bool {
302 self.state.has_ended()
303 }
304
305 /// Ignore an end code and continue.
306 ///
307 /// This will _not_ reset any of the inner code tables and not have the effect of a clear code.
308 /// It will instead continue as if the end code had not been present. If no end code has
309 /// occurred then this is a no-op.
310 ///
311 /// You can test if an end code has occurred with [`has_ended`](#method.has_ended).
312 /// FIXME: clarify how this interacts with padding introduced after end code.
313 #[allow(dead_code)]
314 pub(crate) fn restart(&mut self) {
315 self.state.restart();
316 }
317
318 /// Reset all internal state.
319 ///
320 /// This produce a decoder as if just constructed with `new` but taking slightly less work. In
321 /// particular it will not deallocate any internal allocations. It will also avoid some
322 /// duplicate setup work.
323 pub fn reset(&mut self) {
324 self.state.reset();
325 }
326}
327
328#[cfg(feature = "std")]
329impl<'d, W: Write> IntoStream<'d, W> {
330 /// Decode data from a reader.
331 ///
332 /// This will read data until the stream is empty or an end marker is reached.
333 pub fn decode(&mut self, read: impl BufRead) -> StreamResult {
334 self.decode_part(read, false)
335 }
336
337 /// Decode data from a reader, requiring an end marker.
338 pub fn decode_all(mut self, read: impl BufRead) -> StreamResult {
339 self.decode_part(read, true)
340 }
341
342 /// Set the size of the intermediate decode buffer.
343 ///
344 /// A buffer of this size is allocated to hold one part of the decoded stream when no buffer is
345 /// available and any decoding method is called. No buffer is allocated if `set_buffer` has
346 /// been called. The buffer is reused.
347 ///
348 /// # Panics
349 /// This method panics if `size` is `0`.
350 pub fn set_buffer_size(&mut self, size: usize) {
351 assert_ne!(size, 0, "Attempted to set empty buffer");
352 self.default_size = size;
353 }
354
355 /// Use a particular buffer as an intermediate decode buffer.
356 ///
357 /// Calling this sets or replaces the buffer. When a buffer has been set then it is used
358 /// instead of dynamically allocating a buffer. Note that the size of the buffer is critical
359 /// for efficient decoding. Some optimization techniques require the buffer to hold one or more
360 /// previous decoded words. There is also additional overhead from `write` calls each time the
361 /// buffer has been filled.
362 ///
363 /// # Panics
364 /// This method panics if the `buffer` is empty.
365 pub fn set_buffer(&mut self, buffer: &'d mut [u8]) {
366 assert_ne!(buffer.len(), 0, "Attempted to set empty buffer");
367 self.buffer = Some(StreamBuf::Borrowed(buffer));
368 }
369
370 fn decode_part(&mut self, mut read: impl BufRead, must_finish: bool) -> StreamResult {
371 let IntoStream {
372 decoder,
373 writer,
374 buffer,
375 default_size,
376 } = self;
377
378 enum Progress {
379 Ok,
380 Done,
381 }
382
383 let mut bytes_read = 0;
384 let mut bytes_written = 0;
385
386 // Converting to mutable refs to move into the `once` closure.
387 let read_bytes = &mut bytes_read;
388 let write_bytes = &mut bytes_written;
389
390 let outbuf: &mut [u8] =
391 match { buffer.get_or_insert_with(|| StreamBuf::Owned(vec![0u8; *default_size])) } {
392 StreamBuf::Borrowed(slice) => &mut *slice,
393 StreamBuf::Owned(vec) => &mut *vec,
394 };
395 assert!(!outbuf.is_empty());
396
397 let once = move || {
398 // Try to grab one buffer of input data.
399 let data = read.fill_buf()?;
400
401 // Decode as much of the buffer as fits.
402 let result = decoder.decode_bytes(data, &mut outbuf[..]);
403 // Do the bookkeeping and consume the buffer.
404 *read_bytes += result.consumed_in;
405 *write_bytes += result.consumed_out;
406 read.consume(result.consumed_in);
407
408 // Handle the status in the result.
409 let done = result.status.map_err(|err| {
410 io::Error::new(io::ErrorKind::InvalidData, &*format!("{:?}", err))
411 })?;
412
413 // Check if we had any new data at all.
414 if let LzwStatus::NoProgress = done {
415 debug_assert_eq!(
416 result.consumed_out, 0,
417 "No progress means we have not decoded any data"
418 );
419 // In particular we did not finish decoding.
420 if must_finish {
421 return Err(io::Error::new(
422 io::ErrorKind::UnexpectedEof,
423 "No more data but no end marker detected",
424 ));
425 } else {
426 return Ok(Progress::Done);
427 }
428 }
429
430 // And finish by writing our result.
431 // TODO: we may lose data on error (also on status error above) which we might want to
432 // deterministically handle so that we don't need to restart everything from scratch as
433 // the only recovery strategy. Any changes welcome.
434 writer.write_all(&outbuf[..result.consumed_out])?;
435
436 Ok(if let LzwStatus::Done = done {
437 Progress::Done
438 } else {
439 Progress::Ok
440 })
441 };
442
443 // Decode chunks of input data until we're done.
444 let status = core::iter::repeat_with(once)
445 // scan+fuse can be replaced with map_while
446 .scan((), |(), result| match result {
447 Ok(Progress::Ok) => Some(Ok(())),
448 Err(err) => Some(Err(err)),
449 Ok(Progress::Done) => None,
450 })
451 .fuse()
452 .collect();
453
454 StreamResult {
455 bytes_read,
456 bytes_written,
457 status,
458 }
459 }
460}
461
462impl IntoVec<'_> {
463 /// Decode data from a slice.
464 ///
465 /// This will read data until the slice is empty or an end marker is reached.
466 pub fn decode(&mut self, read: &[u8]) -> VectorResult {
467 self.decode_part(read, false)
468 }
469
470 /// Decode data from a slice, requiring an end marker.
471 pub fn decode_all(mut self, read: &[u8]) -> VectorResult {
472 self.decode_part(read, true)
473 }
474
475 fn grab_buffer(&mut self) -> (&mut [u8], &mut Decoder) {
476 const CHUNK_SIZE: usize = 1 << 12;
477 let decoder = &mut self.decoder;
478 let length = self.vector.len();
479
480 // Use the vector to do overflow checks and w/e.
481 self.vector.reserve(CHUNK_SIZE);
482 // FIXME: decoding into uninit buffer?
483 self.vector.resize(length + CHUNK_SIZE, 0u8);
484
485 (&mut self.vector[length..], decoder)
486 }
487
488 fn decode_part(&mut self, part: &[u8], must_finish: bool) -> VectorResult {
489 let mut result = VectorResult {
490 consumed_in: 0,
491 consumed_out: 0,
492 status: Ok(LzwStatus::Ok),
493 };
494
495 enum Progress {
496 Ok,
497 Done,
498 }
499
500 // Converting to mutable refs to move into the `once` closure.
501 let read_bytes = &mut result.consumed_in;
502 let write_bytes = &mut result.consumed_out;
503 let mut data = part;
504
505 // A 64 MB buffer is quite large but should get alloc_zeroed.
506 // Note that the decoded size can be up to quadratic in code block.
507 let once = move || {
508 // Grab a new output buffer.
509 let (outbuf, decoder) = self.grab_buffer();
510
511 // Decode as much of the buffer as fits.
512 let result = decoder.decode_bytes(data, &mut outbuf[..]);
513 // Do the bookkeeping and consume the buffer.
514 *read_bytes += result.consumed_in;
515 *write_bytes += result.consumed_out;
516 data = &data[result.consumed_in..];
517
518 let unfilled = outbuf.len() - result.consumed_out;
519 let filled = self.vector.len() - unfilled;
520 self.vector.truncate(filled);
521
522 // Handle the status in the result.
523 match result.status {
524 Err(err) => Err(err),
525 Ok(LzwStatus::NoProgress) if must_finish => Err(LzwError::InvalidCode),
526 Ok(LzwStatus::NoProgress) | Ok(LzwStatus::Done) => Ok(Progress::Done),
527 Ok(LzwStatus::Ok) => Ok(Progress::Ok),
528 }
529 };
530
531 // Decode chunks of input data until we're done.
532 let status: Result<(), _> = core::iter::repeat_with(once)
533 // scan+fuse can be replaced with map_while
534 .scan((), |(), result| match result {
535 Ok(Progress::Ok) => Some(Ok(())),
536 Err(err) => Some(Err(err)),
537 Ok(Progress::Done) => None,
538 })
539 .fuse()
540 .collect();
541
542 if let Err(err) = status {
543 result.status = Err(err);
544 }
545
546 result
547 }
548}
549
550// This is implemented in a separate file, so that 1.34.2 does not parse it. Otherwise, it would
551// trip over the usage of await, which is a reserved keyword in that edition/version. It only
552// contains an impl block.
553#[cfg(feature = "async")]
554#[path = "decode_into_async.rs"]
555mod impl_decode_into_async;
556
557impl<C: CodeBuffer> DecodeState<C> {
558 fn new(min_size: u8) -> Self {
559 DecodeState {
560 min_size,
561 table: Table::new(),
562 buffer: Buffer::new(),
563 last: None,
564 clear_code: 1 << min_size,
565 end_code: (1 << min_size) + 1,
566 next_code: (1 << min_size) + 2,
567 has_ended: false,
568 is_tiff: false,
569 implicit_reset: true,
570 code_buffer: CodeBuffer::new(min_size),
571 }
572 }
573
574 fn init_tables(&mut self) {
575 self.code_buffer.reset(self.min_size);
576 self.next_code = (1 << self.min_size) + 2;
577 self.table.init(self.min_size);
578 }
579
580 fn reset_tables(&mut self) {
581 self.code_buffer.reset(self.min_size);
582 self.next_code = (1 << self.min_size) + 2;
583 self.table.clear(self.min_size);
584 }
585}
586
587impl<C: CodeBuffer> Stateful for DecodeState<C> {
588 fn has_ended(&self) -> bool {
589 self.has_ended
590 }
591
592 fn restart(&mut self) {
593 self.has_ended = false;
594 }
595
596 fn reset(&mut self) {
597 self.table.init(self.min_size);
598 self.next_code = (1 << self.min_size) + 2;
599 self.buffer.read_mark = 0;
600 self.buffer.write_mark = 0;
601 self.last = None;
602 self.restart();
603 self.code_buffer = CodeBuffer::new(self.min_size);
604 }
605
606 fn advance(&mut self, mut inp: &[u8], mut out: &mut [u8]) -> BufferResult {
607 // Skip everything if there is nothing to do.
608 if self.has_ended {
609 return BufferResult {
610 consumed_in: 0,
611 consumed_out: 0,
612 status: Ok(LzwStatus::Done),
613 };
614 }
615
616 // Rough description:
617 // We will fill the output slice as much as possible until either there is no more symbols
618 // to decode or an end code has been reached. This requires an internal buffer to hold a
619 // potential tail of the word corresponding to the last symbol. This tail will then be
620 // decoded first before continuing with the regular decoding. The same buffer is required
621 // to persist some symbol state across calls.
622 //
623 // We store the words corresponding to code symbols in an index chain, bytewise, where we
624 // push each decoded symbol. (TODO: wuffs shows some success with 8-byte units). This chain
625 // is traversed for each symbol when it is decoded and bytes are placed directly into the
626 // output slice. In the special case (new_code == next_code) we use an existing decoded
627 // version that is present in either the out bytes of this call or in buffer to copy the
628 // repeated prefix slice.
629 // TODO: I played with a 'decoding cache' to remember the position of long symbols and
630 // avoid traversing the chain, doing a copy of memory instead. It did however not lead to
631 // a serious improvement. It's just unlikely to both have a long symbol and have that
632 // repeated twice in the same output buffer.
633 //
634 // You will also find the (to my knowledge novel) concept of a _decoding burst_ which
635 // gained some >~10% speedup in tests. This is motivated by wanting to use out-of-order
636 // execution as much as possible and for this reason have the least possible stress on
637 // branch prediction. Our decoding table already gives us a lookahead on symbol lengths but
638 // only for re-used codes, not novel ones. This lookahead also makes the loop termination
639 // when restoring each byte of the code word perfectly predictable! So a burst is a chunk
640 // of code words which are all independent of each other, have known lengths _and_ are
641 // guaranteed to fit into the out slice without requiring a buffer. One burst can be
642 // decoded in an extremely tight loop.
643 //
644 // TODO: since words can be at most (1 << MAX_CODESIZE) = 4096 bytes long we could avoid
645 // that intermediate buffer at the expense of not always filling the output buffer
646 // completely. Alternatively we might follow its chain of precursor states twice. This may
647 // be even cheaper if we store more than one byte per link so it really should be
648 // evaluated.
649 // TODO: if the caller was required to provide the previous last word we could also avoid
650 // the buffer for cases where we need it to restore the next code! This could be built
651 // backwards compatible by only doing it after an opt-in call that enables the behaviour.
652
653 // Record initial lengths for the result that is returned.
654 let o_in = inp.len();
655 let o_out = out.len();
656
657 // The code_link is the previously decoded symbol.
658 // It's used to link the new code back to its predecessor.
659 let mut code_link = None;
660 // The status, which is written to on an invalid code.
661 let mut status = Ok(LzwStatus::Ok);
662
663 match self.last.take() {
664 // No last state? This is the first code after a reset?
665 None => {
666 match self.next_symbol(&mut inp) {
667 // Plainly invalid code.
668 Some(code) if code > self.next_code => status = Err(LzwError::InvalidCode),
669 // next_code would require an actual predecessor.
670 Some(code) if code == self.next_code => status = Err(LzwError::InvalidCode),
671 // No more symbols available and nothing decoded yet.
672 // Assume that we didn't make progress, this may get reset to Done if we read
673 // some bytes from the input.
674 None => status = Ok(LzwStatus::NoProgress),
675 // Handle a valid code.
676 Some(init_code) => {
677 if init_code == self.clear_code {
678 self.init_tables();
679 } else if init_code == self.end_code {
680 self.has_ended = true;
681 status = Ok(LzwStatus::Done);
682 } else if self.table.is_empty() {
683 if self.implicit_reset {
684 self.init_tables();
685
686 self.buffer.fill_reconstruct(&self.table, init_code);
687 let link = self.table.at(init_code).clone();
688 code_link = Some((init_code, link));
689 } else {
690 // We require an explicit reset.
691 status = Err(LzwError::InvalidCode);
692 }
693 } else {
694 // Reconstruct the first code in the buffer.
695 self.buffer.fill_reconstruct(&self.table, init_code);
696 let link = self.table.at(init_code).clone();
697 code_link = Some((init_code, link));
698 }
699 }
700 }
701 }
702 // Move the tracking state to the stack.
703 Some(tup) => code_link = Some(tup),
704 };
705
706 // Track an empty `burst` (see below) means we made no progress.
707 let mut burst_required_for_progress = false;
708 // Restore the previous state, if any.
709 if let Some((code, link)) = code_link.take() {
710 code_link = Some((code, link));
711 let remain = self.buffer.buffer();
712 // Check if we can fully finish the buffer.
713 if remain.len() > out.len() {
714 if out.is_empty() {
715 status = Ok(LzwStatus::NoProgress);
716 } else {
717 out.copy_from_slice(&remain[..out.len()]);
718 self.buffer.consume(out.len());
719 out = &mut [];
720 }
721 } else if remain.is_empty() {
722 status = Ok(LzwStatus::NoProgress);
723 burst_required_for_progress = true;
724 } else {
725 let consumed = remain.len();
726 out[..consumed].copy_from_slice(remain);
727 self.buffer.consume(consumed);
728 out = &mut out[consumed..];
729 burst_required_for_progress = false;
730 }
731 }
732
733 // The tracking state for a burst.
734 // These are actually initialized later but compiler wasn't smart enough to fully optimize
735 // out the init code so that appears outside th loop.
736 // TODO: maybe we can make it part of the state but it's dubious if that really gives a
737 // benefit over stack usage? Also the slices stored here would need some treatment as we
738 // can't infect the main struct with a lifetime.
739 let mut burst = [0; 6];
740 let mut bytes = [0u16; 6];
741 let mut target: [&mut [u8]; 6] = Default::default();
742 // A special reference to out slice which holds the last decoded symbol.
743 let mut last_decoded: Option<&[u8]> = None;
744
745 while let Some((mut code, mut link)) = code_link.take() {
746 if out.is_empty() && !self.buffer.buffer().is_empty() {
747 code_link = Some((code, link));
748 break;
749 }
750
751 let mut burst_size = 0;
752 // Ensure the code buffer is full, we're about to request some codes.
753 // Note that this also ensures at least one code is in the buffer if any input is left.
754 self.refill_bits(&mut inp);
755 // A burst is a sequence of decodes that are completely independent of each other. This
756 // is the case if neither is an end code, a clear code, or a next code, i.e. we have
757 // all of them in the decoding table and thus known their depths, and additionally if
758 // we can decode them directly into the output buffer.
759 for b in &mut burst {
760 // TODO: does it actually make a perf difference to avoid reading new bits here?
761 *b = match self.get_bits() {
762 None => break,
763 Some(code) => code,
764 };
765
766 // We can commit the previous burst code, and will take a slice from the output
767 // buffer. This also avoids the bounds check in the tight loop later.
768 if burst_size > 0 {
769 let len = bytes[burst_size - 1];
770 let (into, tail) = out.split_at_mut(usize::from(len));
771 target[burst_size - 1] = into;
772 out = tail;
773 }
774
775 // Check that we don't overflow the code size with all codes we burst decode.
776 if let Some(potential_code) = self.next_code.checked_add(burst_size as u16) {
777 burst_size += 1;
778 if potential_code == self.code_buffer.max_code() - Code::from(self.is_tiff) {
779 break;
780 }
781 } else {
782 // next_code overflowed
783 break;
784 }
785
786 // A burst code can't be special.
787 if *b == self.clear_code || *b == self.end_code || *b >= self.next_code {
788 break;
789 }
790
791 // Read the code length and check that we can decode directly into the out slice.
792 let len = self.table.depths[usize::from(*b)];
793 if out.len() < usize::from(len) {
794 break;
795 }
796
797 bytes[burst_size - 1] = len;
798 }
799
800 // No code left, and no more bytes to fill the buffer.
801 if burst_size == 0 {
802 if burst_required_for_progress {
803 status = Ok(LzwStatus::NoProgress);
804 }
805 code_link = Some((code, link));
806 break;
807 }
808
809 burst_required_for_progress = false;
810 // Note that the very last code in the burst buffer doesn't actually belong to the
811 // burst itself. TODO: sometimes it could, we just don't differentiate between the
812 // breaks and a loop end condition above. That may be a speed advantage?
813 let (&new_code, burst) = burst[..burst_size].split_last().unwrap();
814
815 // The very tight loop for restoring the actual burst.
816 for (&burst, target) in burst.iter().zip(&mut target[..burst_size - 1]) {
817 let cha = self.table.reconstruct(burst, target);
818 // TODO: this pushes into a Vec, maybe we can make this cleaner.
819 // Theoretically this has a branch and llvm tends to be flaky with code layout for
820 // the case of requiring an allocation (which can't occur in practice).
821 let new_link = self.table.derive(&link, cha, code);
822 self.next_code += 1;
823 code = burst;
824 link = new_link;
825 }
826
827 // Update the slice holding the last decoded word.
828 if let Some(new_last) = target[..burst_size - 1].last_mut() {
829 let slice = core::mem::replace(new_last, &mut []);
830 last_decoded = Some(&*slice);
831 }
832
833 // Now handle the special codes.
834 if new_code == self.clear_code {
835 self.reset_tables();
836 last_decoded = None;
837 continue;
838 }
839
840 if new_code == self.end_code {
841 self.has_ended = true;
842 status = Ok(LzwStatus::Done);
843 last_decoded = None;
844 break;
845 }
846
847 if new_code > self.next_code {
848 status = Err(LzwError::InvalidCode);
849 last_decoded = None;
850 break;
851 }
852
853 let required_len = if new_code == self.next_code {
854 self.table.depths[usize::from(code)] + 1
855 } else {
856 self.table.depths[usize::from(new_code)]
857 };
858
859 let cha;
860 let is_in_buffer;
861 // Check if we will need to store our current state into the buffer.
862 if usize::from(required_len) > out.len() {
863 is_in_buffer = true;
864 if new_code == self.next_code {
865 // last_decoded will be Some if we have restored any code into the out slice.
866 // Otherwise it will still be present in the buffer.
867 if let Some(last) = last_decoded.take() {
868 self.buffer.bytes[..last.len()].copy_from_slice(last);
869 self.buffer.write_mark = last.len();
870 self.buffer.read_mark = last.len();
871 }
872
873 cha = self.buffer.fill_cscsc();
874 } else {
875 // Restore the decoded word into the buffer.
876 last_decoded = None;
877 cha = self.buffer.fill_reconstruct(&self.table, new_code);
878 }
879 } else {
880 is_in_buffer = false;
881 let (target, tail) = out.split_at_mut(usize::from(required_len));
882 out = tail;
883
884 if new_code == self.next_code {
885 // Reconstruct high.
886 let source = match last_decoded.take() {
887 Some(last) => last,
888 None => &self.buffer.bytes[..self.buffer.write_mark],
889 };
890 cha = source[0];
891 target[..source.len()].copy_from_slice(source);
892 target[source.len()..][0] = source[0];
893 } else {
894 cha = self.table.reconstruct(new_code, target);
895 }
896
897 // A new decoded word.
898 last_decoded = Some(target);
899 }
900
901 let new_link;
902 // Each newly read code creates one new code/link based on the preceding code if we
903 // have enough space to put it there.
904 if !self.table.is_full() {
905 let link = self.table.derive(&link, cha, code);
906
907 if self.next_code == self.code_buffer.max_code() - Code::from(self.is_tiff)
908 && self.code_buffer.code_size() < MAX_CODESIZE
909 {
910 self.bump_code_size();
911 }
912
913 self.next_code += 1;
914 new_link = link;
915 } else {
916 // It's actually quite likely that the next code will be a reset but just in case.
917 // FIXME: this path hasn't been tested very well.
918 new_link = link.clone();
919 }
920
921 // store the information on the decoded word.
922 code_link = Some((new_code, new_link));
923
924 // Can't make any more progress with decoding.
925 if is_in_buffer {
926 break;
927 }
928 }
929
930 // We need to store the last word into the buffer in case the first code in the next
931 // iteration is the next_code.
932 if let Some(tail) = last_decoded {
933 self.buffer.bytes[..tail.len()].copy_from_slice(tail);
934 self.buffer.write_mark = tail.len();
935 self.buffer.read_mark = tail.len();
936 }
937
938 // Ensure we don't indicate that no progress was made if we read some bytes from the input
939 // (which is progress).
940 if o_in > inp.len() {
941 if let Ok(LzwStatus::NoProgress) = status {
942 status = Ok(LzwStatus::Ok);
943 }
944 }
945
946 // Store the code/link state.
947 self.last = code_link;
948
949 BufferResult {
950 consumed_in: o_in.wrapping_sub(inp.len()),
951 consumed_out: o_out.wrapping_sub(out.len()),
952 status,
953 }
954 }
955}
956
957impl<C: CodeBuffer> DecodeState<C> {
958 fn next_symbol(&mut self, inp: &mut &[u8]) -> Option<Code> {
959 self.code_buffer.next_symbol(inp)
960 }
961
962 fn bump_code_size(&mut self) {
963 self.code_buffer.bump_code_size()
964 }
965
966 fn refill_bits(&mut self, inp: &mut &[u8]) {
967 self.code_buffer.refill_bits(inp)
968 }
969
970 fn get_bits(&mut self) -> Option<Code> {
971 self.code_buffer.get_bits()
972 }
973}
974
975impl CodeBuffer for MsbBuffer {
976 fn new(min_size: u8) -> Self {
977 MsbBuffer {
978 code_size: min_size + 1,
979 code_mask: (1u16 << (min_size + 1)) - 1,
980 bit_buffer: 0,
981 bits: 0,
982 }
983 }
984
985 fn reset(&mut self, min_size: u8) {
986 self.code_size = min_size + 1;
987 self.code_mask = (1 << self.code_size) - 1;
988 }
989
990 fn next_symbol(&mut self, inp: &mut &[u8]) -> Option<Code> {
991 if self.bits < self.code_size {
992 self.refill_bits(inp);
993 }
994
995 self.get_bits()
996 }
997
998 fn bump_code_size(&mut self) {
999 self.code_size += 1;
1000 self.code_mask = (self.code_mask << 1) | 1;
1001 }
1002
1003 fn refill_bits(&mut self, inp: &mut &[u8]) {
1004 let wish_count = (64 - self.bits) / 8;
1005 let mut buffer = [0u8; 8];
1006 let new_bits = match inp.get(..usize::from(wish_count)) {
1007 Some(bytes) => {
1008 buffer[..usize::from(wish_count)].copy_from_slice(bytes);
1009 *inp = &inp[usize::from(wish_count)..];
1010 wish_count * 8
1011 }
1012 None => {
1013 let new_bits = inp.len() * 8;
1014 buffer[..inp.len()].copy_from_slice(inp);
1015 *inp = &[];
1016 new_bits as u8
1017 }
1018 };
1019 self.bit_buffer |= u64::from_be_bytes(buffer) >> self.bits;
1020 self.bits += new_bits;
1021 }
1022
1023 fn get_bits(&mut self) -> Option<Code> {
1024 if self.bits < self.code_size {
1025 return None;
1026 }
1027
1028 let mask = u64::from(self.code_mask);
1029 let rotbuf = self.bit_buffer.rotate_left(self.code_size.into());
1030 self.bit_buffer = rotbuf & !mask;
1031 self.bits -= self.code_size;
1032 Some((rotbuf & mask) as u16)
1033 }
1034
1035 fn max_code(&self) -> Code {
1036 self.code_mask
1037 }
1038
1039 fn code_size(&self) -> u8 {
1040 self.code_size
1041 }
1042}
1043
1044impl CodeBuffer for LsbBuffer {
1045 fn new(min_size: u8) -> Self {
1046 LsbBuffer {
1047 code_size: min_size + 1,
1048 code_mask: (1u16 << (min_size + 1)) - 1,
1049 bit_buffer: 0,
1050 bits: 0,
1051 }
1052 }
1053
1054 fn reset(&mut self, min_size: u8) {
1055 self.code_size = min_size + 1;
1056 self.code_mask = (1 << self.code_size) - 1;
1057 }
1058
1059 fn next_symbol(&mut self, inp: &mut &[u8]) -> Option<Code> {
1060 if self.bits < self.code_size {
1061 self.refill_bits(inp);
1062 }
1063
1064 self.get_bits()
1065 }
1066
1067 fn bump_code_size(&mut self) {
1068 self.code_size += 1;
1069 self.code_mask = (self.code_mask << 1) | 1;
1070 }
1071
1072 fn refill_bits(&mut self, inp: &mut &[u8]) {
1073 let wish_count = (64 - self.bits) / 8;
1074 let mut buffer = [0u8; 8];
1075 let new_bits = match inp.get(..usize::from(wish_count)) {
1076 Some(bytes) => {
1077 buffer[..usize::from(wish_count)].copy_from_slice(bytes);
1078 *inp = &inp[usize::from(wish_count)..];
1079 wish_count * 8
1080 }
1081 None => {
1082 let new_bits = inp.len() * 8;
1083 buffer[..inp.len()].copy_from_slice(inp);
1084 *inp = &[];
1085 new_bits as u8
1086 }
1087 };
1088 self.bit_buffer |= u64::from_be_bytes(buffer).swap_bytes() << self.bits;
1089 self.bits += new_bits;
1090 }
1091
1092 fn get_bits(&mut self) -> Option<Code> {
1093 if self.bits < self.code_size {
1094 return None;
1095 }
1096
1097 let mask = u64::from(self.code_mask);
1098 let code = self.bit_buffer & mask;
1099 self.bit_buffer >>= self.code_size;
1100 self.bits -= self.code_size;
1101 Some(code as u16)
1102 }
1103
1104 fn max_code(&self) -> Code {
1105 self.code_mask
1106 }
1107
1108 fn code_size(&self) -> u8 {
1109 self.code_size
1110 }
1111}
1112
1113impl Buffer {
1114 fn new() -> Self {
1115 Buffer {
1116 bytes: vec![0; MAX_ENTRIES].into_boxed_slice(),
1117 read_mark: 0,
1118 write_mark: 0,
1119 }
1120 }
1121
1122 /// When encoding a sequence `cScSc` where `c` is any character and `S` is any string
1123 /// this results in two codes `AB`, `A` encoding `cS` and `B` encoding `cSc`. Supposing
1124 /// the buffer is already filled with the reconstruction of `A`, we can easily fill it
1125 /// with the reconstruction of `B`.
1126 fn fill_cscsc(&mut self) -> u8 {
1127 self.bytes[self.write_mark] = self.bytes[0];
1128 self.write_mark += 1;
1129 self.read_mark = 0;
1130 self.bytes[0]
1131 }
1132
1133 // Fill the buffer by decoding from the table
1134 fn fill_reconstruct(&mut self, table: &Table, code: Code) -> u8 {
1135 self.write_mark = 0;
1136 self.read_mark = 0;
1137 let depth = table.depths[usize::from(code)];
1138 let mut memory = core::mem::replace(&mut self.bytes, Box::default());
1139
1140 let out = &mut memory[..usize::from(depth)];
1141 let last = table.reconstruct(code, out);
1142
1143 self.bytes = memory;
1144 self.write_mark = usize::from(depth);
1145 last
1146 }
1147
1148 fn buffer(&self) -> &[u8] {
1149 &self.bytes[self.read_mark..self.write_mark]
1150 }
1151
1152 fn consume(&mut self, amt: usize) {
1153 self.read_mark += amt;
1154 }
1155}
1156
1157impl Table {
1158 fn new() -> Self {
1159 Table {
1160 inner: Vec::with_capacity(MAX_ENTRIES),
1161 depths: Vec::with_capacity(MAX_ENTRIES),
1162 }
1163 }
1164
1165 fn clear(&mut self, min_size: u8) {
1166 let static_count = usize::from(1u16 << u16::from(min_size)) + 2;
1167 self.inner.truncate(static_count);
1168 self.depths.truncate(static_count);
1169 }
1170
1171 fn init(&mut self, min_size: u8) {
1172 self.inner.clear();
1173 self.depths.clear();
1174 for i in 0..(1u16 << u16::from(min_size)) {
1175 self.inner.push(Link::base(i as u8));
1176 self.depths.push(1);
1177 }
1178 // Clear code.
1179 self.inner.push(Link::base(0));
1180 self.depths.push(0);
1181 // End code.
1182 self.inner.push(Link::base(0));
1183 self.depths.push(0);
1184 }
1185
1186 fn at(&self, code: Code) -> &Link {
1187 &self.inner[usize::from(code)]
1188 }
1189
1190 fn is_empty(&self) -> bool {
1191 self.inner.is_empty()
1192 }
1193
1194 fn is_full(&self) -> bool {
1195 self.inner.len() >= MAX_ENTRIES
1196 }
1197
1198 fn derive(&mut self, from: &Link, byte: u8, prev: Code) -> Link {
1199 let link = from.derive(byte, prev);
1200 let depth = self.depths[usize::from(prev)] + 1;
1201 self.inner.push(link.clone());
1202 self.depths.push(depth);
1203 link
1204 }
1205
1206 fn reconstruct(&self, code: Code, out: &mut [u8]) -> u8 {
1207 let mut code_iter = code;
1208 let table = &self.inner[..=usize::from(code)];
1209 let len = code_iter;
1210 for ch in out.iter_mut().rev() {
1211 //(code, cha) = self.table[k as usize];
1212 // Note: This could possibly be replaced with an unchecked array access if
1213 // - value is asserted to be < self.next_code() in push
1214 // - min_size is asserted to be < MAX_CODESIZE
1215 let entry = &table[usize::from(code_iter)];
1216 code_iter = core::cmp::min(len, entry.prev);
1217 *ch = entry.byte;
1218 }
1219 out[0]
1220 }
1221}
1222
1223impl Link {
1224 fn base(byte: u8) -> Self {
1225 Link { prev: 0, byte }
1226 }
1227
1228 // TODO: this has self type to make it clear we might depend on the old in a future
1229 // optimization. However, that has no practical purpose right now.
1230 fn derive(&self, byte: u8, prev: Code) -> Self {
1231 Link { prev, byte }
1232 }
1233}
1234
1235#[cfg(test)]
1236mod tests {
1237 use crate::alloc::vec::Vec;
1238 #[cfg(feature = "std")]
1239 use crate::StreamBuf;
1240 use crate::{decode::Decoder, BitOrder};
1241
1242 #[test]
1243 fn invalid_code_size_low() {
1244 let _ = Decoder::new(BitOrder::Msb, 0);
1245 let _ = Decoder::new(BitOrder::Msb, 1);
1246 }
1247
1248 #[test]
1249 #[should_panic]
1250 fn invalid_code_size_high() {
1251 let _ = Decoder::new(BitOrder::Msb, 14);
1252 }
1253
1254 fn make_encoded() -> Vec<u8> {
1255 const FILE: &'static [u8] = include_bytes!(concat!(
1256 env!("CARGO_MANIFEST_DIR"),
1257 "/benches/binary-8-msb.lzw"
1258 ));
1259 return Vec::from(FILE);
1260 }
1261
1262 #[test]
1263 #[cfg(feature = "std")]
1264 fn into_stream_buffer_no_alloc() {
1265 let encoded = make_encoded();
1266 let mut decoder = Decoder::new(BitOrder::Msb, 8);
1267
1268 let mut output = vec![];
1269 let mut buffer = [0; 512];
1270 let mut istream = decoder.into_stream(&mut output);
1271 istream.set_buffer(&mut buffer[..]);
1272 istream.decode(&encoded[..]).status.unwrap();
1273
1274 match istream.buffer {
1275 Some(StreamBuf::Borrowed(_)) => {}
1276 None => panic!("Decoded without buffer??"),
1277 Some(StreamBuf::Owned(_)) => panic!("Unexpected buffer allocation"),
1278 }
1279 }
1280
1281 #[test]
1282 #[cfg(feature = "std")]
1283 fn into_stream_buffer_small_alloc() {
1284 struct WriteTap<W: std::io::Write>(W);
1285 const BUF_SIZE: usize = 512;
1286
1287 impl<W: std::io::Write> std::io::Write for WriteTap<W> {
1288 fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> {
1289 assert!(buf.len() <= BUF_SIZE);
1290 self.0.write(buf)
1291 }
1292 fn flush(&mut self) -> std::io::Result<()> {
1293 self.0.flush()
1294 }
1295 }
1296
1297 let encoded = make_encoded();
1298 let mut decoder = Decoder::new(BitOrder::Msb, 8);
1299
1300 let mut output = vec![];
1301 let mut istream = decoder.into_stream(WriteTap(&mut output));
1302 istream.set_buffer_size(512);
1303 istream.decode(&encoded[..]).status.unwrap();
1304
1305 match istream.buffer {
1306 Some(StreamBuf::Owned(vec)) => assert!(vec.len() <= BUF_SIZE),
1307 Some(StreamBuf::Borrowed(_)) => panic!("Unexpected borrowed buffer, where from?"),
1308 None => panic!("Decoded without buffer??"),
1309 }
1310 }
1311
1312 #[test]
1313 #[cfg(feature = "std")]
1314 fn reset() {
1315 let encoded = make_encoded();
1316 let mut decoder = Decoder::new(BitOrder::Msb, 8);
1317 let mut reference = None;
1318
1319 for _ in 0..2 {
1320 let mut output = vec![];
1321 let mut buffer = [0; 512];
1322 let mut istream = decoder.into_stream(&mut output);
1323 istream.set_buffer(&mut buffer[..]);
1324 istream.decode_all(&encoded[..]).status.unwrap();
1325
1326 decoder.reset();
1327 if let Some(reference) = &reference {
1328 assert_eq!(output, *reference);
1329 } else {
1330 reference = Some(output);
1331 }
1332 }
1333 }
1334}
1335