| 1 |
//! A module for all decoding needs. |
| 2 |
#[cfg(feature = "std")] |
| 3 |
use crate::error::StreamResult; |
| 4 |
use crate::error::{BufferResult, LzwError, LzwStatus, VectorResult}; |
| 5 |
use crate::{BitOrder, Code, StreamBuf, MAX_CODESIZE, MAX_ENTRIES, STREAM_BUF_SIZE}; |
| 6 |
|
| 7 |
use crate::alloc::{boxed::Box, vec, vec::Vec}; |
| 8 |
#[cfg(feature = "std")] |
| 9 |
use 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 |
| 32 |
pub 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))] |
| 46 |
pub 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")] |
| 59 |
pub 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 |
| 71 |
pub struct IntoVec<'d> { |
| 72 |
decoder: &'d mut Decoder, |
| 73 |
vector: &'d mut Vec<u8>, |
| 74 |
} |
| 75 |
|
| 76 |
trait 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)] |
| 86 |
struct Link { |
| 87 |
prev: Code, |
| 88 |
byte: u8, |
| 89 |
first: u8, |
| 90 |
} |
| 91 |
|
| 92 |
#[derive(Clone)] |
| 93 |
struct DerivationBase { |
| 94 |
code: Code, |
| 95 |
first: u8, |
| 96 |
} |
| 97 |
|
| 98 |
#[derive(Default)] |
| 99 |
struct MsbBuffer { |
| 100 |
/// A buffer of individual bits. The oldest code is kept in the high-order bits. |
| 101 |
bit_buffer: u64, |
| 102 |
/// A precomputed mask for this code. |
| 103 |
code_mask: u16, |
| 104 |
/// The current code size. |
| 105 |
code_size: u8, |
| 106 |
/// The number of bits in the buffer. |
| 107 |
bits: u8, |
| 108 |
} |
| 109 |
|
| 110 |
#[derive(Default)] |
| 111 |
struct LsbBuffer { |
| 112 |
/// A buffer of individual bits. The oldest code is kept in the high-order bits. |
| 113 |
bit_buffer: u64, |
| 114 |
/// A precomputed mask for this code. |
| 115 |
code_mask: u16, |
| 116 |
/// The current code size. |
| 117 |
code_size: u8, |
| 118 |
/// The number of bits in the buffer. |
| 119 |
bits: u8, |
| 120 |
} |
| 121 |
|
| 122 |
trait CodeBuffer { |
| 123 |
fn new(min_size: u8) -> Self; |
| 124 |
fn reset(&mut self, min_size: u8); |
| 125 |
fn bump_code_size(&mut self); |
| 126 |
|
| 127 |
/// Retrieve the next symbol, refilling if necessary. |
| 128 |
fn next_symbol(&mut self, inp: &mut &[u8]) -> Option<Code>; |
| 129 |
/// Refill the internal buffer. |
| 130 |
fn refill_bits(&mut self, inp: &mut &[u8]); |
| 131 |
|
| 132 |
fn peek_bits(&self, code: &mut [Code; BURST]) -> usize; |
| 133 |
fn consume_bits(&mut self, code_cnt: u8); |
| 134 |
|
| 135 |
fn max_code(&self) -> Code; |
| 136 |
fn code_size(&self) -> u8; |
| 137 |
} |
| 138 |
|
| 139 |
trait CodegenConstants { |
| 140 |
const YIELD_ON_FULL: bool; |
| 141 |
} |
| 142 |
|
| 143 |
struct DecodeState<CodeBuffer, Constants: CodegenConstants> { |
| 144 |
/// The original minimum code size. |
| 145 |
min_size: u8, |
| 146 |
/// The table of decoded codes. |
| 147 |
table: Table, |
| 148 |
/// The buffer of decoded data. |
| 149 |
buffer: Buffer, |
| 150 |
/// The link which we are still decoding and its original code. |
| 151 |
last: Option<DerivationBase>, |
| 152 |
/// The next code entry. |
| 153 |
next_code: Code, |
| 154 |
/// Code to reset all tables. |
| 155 |
clear_code: Code, |
| 156 |
/// Code to signal the end of the stream. |
| 157 |
end_code: Code, |
| 158 |
/// A stored flag if the end code has already appeared. |
| 159 |
has_ended: bool, |
| 160 |
/// If tiff then bumps are a single code sooner. |
| 161 |
is_tiff: bool, |
| 162 |
/// Do we allow stream to start without an explicit reset code? |
| 163 |
implicit_reset: bool, |
| 164 |
/// The buffer for decoded words. |
| 165 |
code_buffer: CodeBuffer, |
| 166 |
#[allow(dead_code)] |
| 167 |
constants: core::marker::PhantomData<Constants>, |
| 168 |
} |
| 169 |
|
| 170 |
// We have a buffer of 64 bits. So at max size at most 5 units can be read at once without |
| 171 |
// refilling the buffer. At smaller code sizes there are more. We tune for 6 here, by slight |
| 172 |
// experimentation. This may be an architecture dependent constant. |
| 173 |
const BURST: usize = 6; |
| 174 |
|
| 175 |
struct Buffer { |
| 176 |
bytes: Box<[u8]>, |
| 177 |
read_mark: usize, |
| 178 |
write_mark: usize, |
| 179 |
} |
| 180 |
|
| 181 |
struct Table { |
| 182 |
inner: Vec<Link>, |
| 183 |
depths: Vec<u16>, |
| 184 |
} |
| 185 |
|
| 186 |
/// Describes the static parameters for creating a decoder. |
| 187 |
#[derive(Clone, Debug)] |
| 188 |
pub struct Configuration { |
| 189 |
order: BitOrder, |
| 190 |
size: u8, |
| 191 |
tiff: bool, |
| 192 |
yield_on_full: bool, |
| 193 |
} |
| 194 |
|
| 195 |
impl Configuration { |
| 196 |
/// Create a configuration to decode with the specified bit order and symbol size. |
| 197 |
pub fn new(order: BitOrder, size: u8) -> Self { |
| 198 |
super::assert_decode_size(size); |
| 199 |
Configuration { |
| 200 |
order, |
| 201 |
size, |
| 202 |
tiff: false, |
| 203 |
yield_on_full: false, |
| 204 |
} |
| 205 |
} |
| 206 |
|
| 207 |
/// Create a configuration for a TIFF compatible decoder. |
| 208 |
pub fn with_tiff_size_switch(order: BitOrder, size: u8) -> Self { |
| 209 |
super::assert_decode_size(size); |
| 210 |
Configuration { |
| 211 |
order, |
| 212 |
size, |
| 213 |
tiff: true, |
| 214 |
yield_on_full: false, |
| 215 |
} |
| 216 |
} |
| 217 |
|
| 218 |
/// Immediately yield to the caller when the decoder buffer is full. |
| 219 |
/// |
| 220 |
/// This can be used for `libtiff` compatibility. It will use a "relaxed" stream interpretation |
| 221 |
/// that need not contain an explicit EOF. Instead, the decoder is expected to stop fetching |
| 222 |
/// symbols when some out-of-band specified length of the decoded text has been reached. The |
| 223 |
/// caller indicates this maximum length through the available output buffer space. |
| 224 |
/// |
| 225 |
/// Symbols afterwards must not be expected to be valid. On filling the output buffer space |
| 226 |
/// completely, the decoder will return immediately to the caller instead of potentially |
| 227 |
/// interpreting the following bit-stream (and returning an error on doing so). |
| 228 |
/// |
| 229 |
/// Default: `false`. |
| 230 |
pub fn with_yield_on_full_buffer(self, do_yield: bool) -> Self { |
| 231 |
Configuration { |
| 232 |
yield_on_full: do_yield, |
| 233 |
..self |
| 234 |
} |
| 235 |
} |
| 236 |
|
| 237 |
/// Create a new decoder with the define configuration. |
| 238 |
pub fn build(self) -> Decoder { |
| 239 |
Decoder { |
| 240 |
state: Decoder::from_configuration(&self), |
| 241 |
} |
| 242 |
} |
| 243 |
} |
| 244 |
|
| 245 |
impl Decoder { |
| 246 |
/// Create a new decoder with the specified bit order and symbol size. |
| 247 |
/// |
| 248 |
/// The algorithm for dynamically increasing the code symbol bit width is compatible with the |
| 249 |
/// original specification. In particular you will need to specify an `Lsb` bit oder to decode |
| 250 |
/// the data portion of a compressed `gif` image. |
| 251 |
/// |
| 252 |
/// # Panics |
| 253 |
/// |
| 254 |
/// The `size` needs to be in the interval `0..=12`. |
| 255 |
pub fn new(order: BitOrder, size: u8) -> Self { |
| 256 |
Configuration::new(order, size).build() |
| 257 |
} |
| 258 |
|
| 259 |
/// Create a TIFF compatible decoder with the specified bit order and symbol size. |
| 260 |
/// |
| 261 |
/// The algorithm for dynamically increasing the code symbol bit width is compatible with the |
| 262 |
/// TIFF specification, which is a misinterpretation of the original algorithm for increasing |
| 263 |
/// the code size. It switches one symbol sooner. |
| 264 |
/// |
| 265 |
/// # Panics |
| 266 |
/// |
| 267 |
/// The `size` needs to be in the interval `0..=12`. |
| 268 |
pub fn with_tiff_size_switch(order: BitOrder, size: u8) -> Self { |
| 269 |
Configuration::with_tiff_size_switch(order, size).build() |
| 270 |
} |
| 271 |
|
| 272 |
fn from_configuration(configuration: &Configuration) -> Box<dyn Stateful + Send + 'static> { |
| 273 |
struct NoYield; |
| 274 |
struct YieldOnFull; |
| 275 |
|
| 276 |
impl CodegenConstants for NoYield { |
| 277 |
const YIELD_ON_FULL: bool = false; |
| 278 |
} |
| 279 |
|
| 280 |
impl CodegenConstants for YieldOnFull { |
| 281 |
const YIELD_ON_FULL: bool = true; |
| 282 |
} |
| 283 |
|
| 284 |
type Boxed = Box<dyn Stateful + Send + 'static>; |
| 285 |
match (configuration.order, configuration.yield_on_full) { |
| 286 |
(BitOrder::Lsb, false) => { |
| 287 |
let mut state = |
| 288 |
Box::new(DecodeState::<LsbBuffer, NoYield>::new(configuration.size)); |
| 289 |
state.is_tiff = configuration.tiff; |
| 290 |
state as Boxed |
| 291 |
} |
| 292 |
(BitOrder::Lsb, true) => { |
| 293 |
let mut state = Box::new(DecodeState::<LsbBuffer, YieldOnFull>::new( |
| 294 |
configuration.size, |
| 295 |
)); |
| 296 |
state.is_tiff = configuration.tiff; |
| 297 |
state as Boxed |
| 298 |
} |
| 299 |
(BitOrder::Msb, false) => { |
| 300 |
let mut state = |
| 301 |
Box::new(DecodeState::<MsbBuffer, NoYield>::new(configuration.size)); |
| 302 |
state.is_tiff = configuration.tiff; |
| 303 |
state as Boxed |
| 304 |
} |
| 305 |
(BitOrder::Msb, true) => { |
| 306 |
let mut state = Box::new(DecodeState::<MsbBuffer, YieldOnFull>::new( |
| 307 |
configuration.size, |
| 308 |
)); |
| 309 |
state.is_tiff = configuration.tiff; |
| 310 |
state as Boxed |
| 311 |
} |
| 312 |
} |
| 313 |
} |
| 314 |
|
| 315 |
/// Decode some bytes from `inp` and write result to `out`. |
| 316 |
/// |
| 317 |
/// This will consume a prefix of the input buffer and write decoded output into a prefix of |
| 318 |
/// the output buffer. See the respective fields of the return value for the count of consumed |
| 319 |
/// and written bytes. For the next call You should have adjusted the inputs accordingly. |
| 320 |
/// |
| 321 |
/// The call will try to decode and write as many bytes of output as available. It will be |
| 322 |
/// much more optimized (and avoid intermediate buffering) if it is allowed to write a large |
| 323 |
/// contiguous chunk at once. |
| 324 |
/// |
| 325 |
/// See [`into_stream`] for high-level functions (that are only available with the `std` |
| 326 |
/// feature). |
| 327 |
/// |
| 328 |
/// [`into_stream`]: #method.into_stream |
| 329 |
pub fn decode_bytes(&mut self, inp: &[u8], out: &mut [u8]) -> BufferResult { |
| 330 |
self.state.advance(inp, out) |
| 331 |
} |
| 332 |
|
| 333 |
/// Decode a single chunk of lzw encoded data. |
| 334 |
/// |
| 335 |
/// This method requires the data to contain an end marker, and returns an error otherwise. |
| 336 |
/// |
| 337 |
/// This is a convenience wrapper around [`into_vec`]. Use the `into_vec` adapter to customize |
| 338 |
/// buffer size, to supply an existing vector, to control whether an end marker is required, or |
| 339 |
/// to preserve partial data in the case of a decoding error. |
| 340 |
/// |
| 341 |
/// [`into_vec`]: #into_vec |
| 342 |
/// |
| 343 |
/// # Example |
| 344 |
/// |
| 345 |
/// ``` |
| 346 |
/// use weezl::{BitOrder, decode::Decoder}; |
| 347 |
/// |
| 348 |
/// // Encoded that was created with an encoder. |
| 349 |
/// let data = b"\x80\x04\x81\x94l\x1b\x06\xf0\xb0 \x1d\xc6\xf1\xc8l\x19 \x10"; |
| 350 |
/// let decoded = Decoder::new(BitOrder::Msb, 9) |
| 351 |
/// .decode(data) |
| 352 |
/// .unwrap(); |
| 353 |
/// assert_eq!(decoded, b"Hello, world"); |
| 354 |
/// ``` |
| 355 |
pub fn decode(&mut self, data: &[u8]) -> Result<Vec<u8>, LzwError> { |
| 356 |
let mut output = vec![]; |
| 357 |
self.into_vec(&mut output).decode_all(data).status?; |
| 358 |
Ok(output) |
| 359 |
} |
| 360 |
|
| 361 |
/// Construct a decoder into a writer. |
| 362 |
#[cfg(feature = "std")] |
| 363 |
pub fn into_stream<W: Write>(&mut self, writer: W) -> IntoStream<'_, W> { |
| 364 |
IntoStream { |
| 365 |
decoder: self, |
| 366 |
writer, |
| 367 |
buffer: None, |
| 368 |
default_size: STREAM_BUF_SIZE, |
| 369 |
} |
| 370 |
} |
| 371 |
|
| 372 |
/// Construct a decoder into an async writer. |
| 373 |
#[cfg(feature = "async")] |
| 374 |
pub fn into_async<W: futures::io::AsyncWrite>(&mut self, writer: W) -> IntoAsync<'_, W> { |
| 375 |
IntoAsync { |
| 376 |
decoder: self, |
| 377 |
writer, |
| 378 |
buffer: None, |
| 379 |
default_size: STREAM_BUF_SIZE, |
| 380 |
} |
| 381 |
} |
| 382 |
|
| 383 |
/// Construct a decoder into a vector. |
| 384 |
/// |
| 385 |
/// All decoded data is appended and the vector is __not__ cleared. |
| 386 |
/// |
| 387 |
/// Compared to `into_stream` this interface allows a high-level access to decoding without |
| 388 |
/// requires the `std`-feature. Also, it can make full use of the extra buffer control that the |
| 389 |
/// special target exposes. |
| 390 |
pub fn into_vec<'lt>(&'lt mut self, vec: &'lt mut Vec<u8>) -> IntoVec<'lt> { |
| 391 |
IntoVec { |
| 392 |
decoder: self, |
| 393 |
vector: vec, |
| 394 |
} |
| 395 |
} |
| 396 |
|
| 397 |
/// Check if the decoding has finished. |
| 398 |
/// |
| 399 |
/// No more output is produced beyond the end code that marked the finish of the stream. The |
| 400 |
/// decoder may have read additional bytes, including padding bits beyond the last code word |
| 401 |
/// but also excess bytes provided. |
| 402 |
pub fn has_ended(&self) -> bool { |
| 403 |
self.state.has_ended() |
| 404 |
} |
| 405 |
|
| 406 |
/// Ignore an end code and continue. |
| 407 |
/// |
| 408 |
/// This will _not_ reset any of the inner code tables and not have the effect of a clear code. |
| 409 |
/// It will instead continue as if the end code had not been present. If no end code has |
| 410 |
/// occurred then this is a no-op. |
| 411 |
/// |
| 412 |
/// You can test if an end code has occurred with [`has_ended`](#method.has_ended). |
| 413 |
/// FIXME: clarify how this interacts with padding introduced after end code. |
| 414 |
#[allow(dead_code)] |
| 415 |
pub(crate) fn restart(&mut self) { |
| 416 |
self.state.restart(); |
| 417 |
} |
| 418 |
|
| 419 |
/// Reset all internal state. |
| 420 |
/// |
| 421 |
/// This produce a decoder as if just constructed with `new` but taking slightly less work. In |
| 422 |
/// particular it will not deallocate any internal allocations. It will also avoid some |
| 423 |
/// duplicate setup work. |
| 424 |
pub fn reset(&mut self) { |
| 425 |
self.state.reset(); |
| 426 |
} |
| 427 |
} |
| 428 |
|
| 429 |
#[cfg(feature = "std")] |
| 430 |
impl<'d, W: Write> IntoStream<'d, W> { |
| 431 |
/// Decode data from a reader. |
| 432 |
/// |
| 433 |
/// This will read data until the stream is empty or an end marker is reached. |
| 434 |
pub fn decode(&mut self, read: impl BufRead) -> StreamResult { |
| 435 |
self.decode_part(read, false) |
| 436 |
} |
| 437 |
|
| 438 |
/// Decode data from a reader, requiring an end marker. |
| 439 |
pub fn decode_all(mut self, read: impl BufRead) -> StreamResult { |
| 440 |
self.decode_part(read, true) |
| 441 |
} |
| 442 |
|
| 443 |
/// Set the size of the intermediate decode buffer. |
| 444 |
/// |
| 445 |
/// A buffer of this size is allocated to hold one part of the decoded stream when no buffer is |
| 446 |
/// available and any decoding method is called. No buffer is allocated if `set_buffer` has |
| 447 |
/// been called. The buffer is reused. |
| 448 |
/// |
| 449 |
/// # Panics |
| 450 |
/// This method panics if `size` is `0`. |
| 451 |
pub fn set_buffer_size(&mut self, size: usize) { |
| 452 |
assert_ne!(size, 0, "Attempted to set empty buffer"); |
| 453 |
self.default_size = size; |
| 454 |
} |
| 455 |
|
| 456 |
/// Use a particular buffer as an intermediate decode buffer. |
| 457 |
/// |
| 458 |
/// Calling this sets or replaces the buffer. When a buffer has been set then it is used |
| 459 |
/// instead of dynamically allocating a buffer. Note that the size of the buffer is critical |
| 460 |
/// for efficient decoding. Some optimization techniques require the buffer to hold one or more |
| 461 |
/// previous decoded words. There is also additional overhead from `write` calls each time the |
| 462 |
/// buffer has been filled. |
| 463 |
/// |
| 464 |
/// # Panics |
| 465 |
/// This method panics if the `buffer` is empty. |
| 466 |
pub fn set_buffer(&mut self, buffer: &'d mut [u8]) { |
| 467 |
assert_ne!(buffer.len(), 0, "Attempted to set empty buffer"); |
| 468 |
self.buffer = Some(StreamBuf::Borrowed(buffer)); |
| 469 |
} |
| 470 |
|
| 471 |
fn decode_part(&mut self, mut read: impl BufRead, must_finish: bool) -> StreamResult { |
| 472 |
let IntoStream { |
| 473 |
decoder, |
| 474 |
writer, |
| 475 |
buffer, |
| 476 |
default_size, |
| 477 |
} = self; |
| 478 |
|
| 479 |
enum Progress { |
| 480 |
Ok, |
| 481 |
Done, |
| 482 |
} |
| 483 |
|
| 484 |
let mut bytes_read = 0; |
| 485 |
let mut bytes_written = 0; |
| 486 |
|
| 487 |
// Converting to mutable refs to move into the `once` closure. |
| 488 |
let read_bytes = &mut bytes_read; |
| 489 |
let write_bytes = &mut bytes_written; |
| 490 |
|
| 491 |
let outbuf: &mut [u8] = |
| 492 |
match { buffer.get_or_insert_with(|| StreamBuf::Owned(vec![0u8; *default_size])) } { |
| 493 |
StreamBuf::Borrowed(slice) => &mut *slice, |
| 494 |
StreamBuf::Owned(vec) => &mut *vec, |
| 495 |
}; |
| 496 |
assert!(!outbuf.is_empty()); |
| 497 |
|
| 498 |
let once = move || { |
| 499 |
// Try to grab one buffer of input data. |
| 500 |
let data = read.fill_buf()?; |
| 501 |
|
| 502 |
// Decode as much of the buffer as fits. |
| 503 |
let result = decoder.decode_bytes(data, &mut outbuf[..]); |
| 504 |
// Do the bookkeeping and consume the buffer. |
| 505 |
*read_bytes += result.consumed_in; |
| 506 |
*write_bytes += result.consumed_out; |
| 507 |
read.consume(result.consumed_in); |
| 508 |
|
| 509 |
// Handle the status in the result. |
| 510 |
let done = result.status.map_err(|err| { |
| 511 |
io::Error::new(io::ErrorKind::InvalidData, &*format!("{:?}", err)) |
| 512 |
})?; |
| 513 |
|
| 514 |
// Check if we had any new data at all. |
| 515 |
if let LzwStatus::NoProgress = done { |
| 516 |
debug_assert_eq!( |
| 517 |
result.consumed_out, 0, |
| 518 |
"No progress means we have not decoded any data" |
| 519 |
); |
| 520 |
// In particular we did not finish decoding. |
| 521 |
if must_finish { |
| 522 |
return Err(io::Error::new( |
| 523 |
io::ErrorKind::UnexpectedEof, |
| 524 |
"No more data but no end marker detected", |
| 525 |
)); |
| 526 |
} else { |
| 527 |
return Ok(Progress::Done); |
| 528 |
} |
| 529 |
} |
| 530 |
|
| 531 |
// And finish by writing our result. |
| 532 |
// TODO: we may lose data on error (also on status error above) which we might want to |
| 533 |
// deterministically handle so that we don't need to restart everything from scratch as |
| 534 |
// the only recovery strategy. Any changes welcome. |
| 535 |
writer.write_all(&outbuf[..result.consumed_out])?; |
| 536 |
|
| 537 |
Ok(if let LzwStatus::Done = done { |
| 538 |
Progress::Done |
| 539 |
} else { |
| 540 |
Progress::Ok |
| 541 |
}) |
| 542 |
}; |
| 543 |
|
| 544 |
// Decode chunks of input data until we're done. |
| 545 |
let status = core::iter::repeat_with(once) |
| 546 |
// scan+fuse can be replaced with map_while |
| 547 |
.scan((), |(), result| match result { |
| 548 |
Ok(Progress::Ok) => Some(Ok(())), |
| 549 |
Err(err) => Some(Err(err)), |
| 550 |
Ok(Progress::Done) => None, |
| 551 |
}) |
| 552 |
.fuse() |
| 553 |
.collect(); |
| 554 |
|
| 555 |
StreamResult { |
| 556 |
bytes_read, |
| 557 |
bytes_written, |
| 558 |
status, |
| 559 |
} |
| 560 |
} |
| 561 |
} |
| 562 |
|
| 563 |
impl IntoVec<'_> { |
| 564 |
/// Decode data from a slice. |
| 565 |
/// |
| 566 |
/// This will read data until the slice is empty or an end marker is reached. |
| 567 |
pub fn decode(&mut self, read: &[u8]) -> VectorResult { |
| 568 |
self.decode_part(read, false) |
| 569 |
} |
| 570 |
|
| 571 |
/// Decode data from a slice, requiring an end marker. |
| 572 |
pub fn decode_all(mut self, read: &[u8]) -> VectorResult { |
| 573 |
self.decode_part(read, true) |
| 574 |
} |
| 575 |
|
| 576 |
fn grab_buffer(&mut self) -> (&mut [u8], &mut Decoder) { |
| 577 |
const CHUNK_SIZE: usize = 1 << 12; |
| 578 |
let decoder = &mut self.decoder; |
| 579 |
let length = self.vector.len(); |
| 580 |
|
| 581 |
// Use the vector to do overflow checks and w/e. |
| 582 |
self.vector.reserve(CHUNK_SIZE); |
| 583 |
// FIXME: decoding into uninit buffer? |
| 584 |
self.vector.resize(length + CHUNK_SIZE, 0u8); |
| 585 |
|
| 586 |
(&mut self.vector[length..], decoder) |
| 587 |
} |
| 588 |
|
| 589 |
fn decode_part(&mut self, part: &[u8], must_finish: bool) -> VectorResult { |
| 590 |
let mut result = VectorResult { |
| 591 |
consumed_in: 0, |
| 592 |
consumed_out: 0, |
| 593 |
status: Ok(LzwStatus::Ok), |
| 594 |
}; |
| 595 |
|
| 596 |
enum Progress { |
| 597 |
Ok, |
| 598 |
Done, |
| 599 |
} |
| 600 |
|
| 601 |
// Converting to mutable refs to move into the `once` closure. |
| 602 |
let read_bytes = &mut result.consumed_in; |
| 603 |
let write_bytes = &mut result.consumed_out; |
| 604 |
let mut data = part; |
| 605 |
|
| 606 |
// A 64 MB buffer is quite large but should get alloc_zeroed. |
| 607 |
// Note that the decoded size can be up to quadratic in code block. |
| 608 |
let once = move || { |
| 609 |
// Grab a new output buffer. |
| 610 |
let (outbuf, decoder) = self.grab_buffer(); |
| 611 |
|
| 612 |
// Decode as much of the buffer as fits. |
| 613 |
let result = decoder.decode_bytes(data, &mut outbuf[..]); |
| 614 |
// Do the bookkeeping and consume the buffer. |
| 615 |
*read_bytes += result.consumed_in; |
| 616 |
*write_bytes += result.consumed_out; |
| 617 |
data = &data[result.consumed_in..]; |
| 618 |
|
| 619 |
let unfilled = outbuf.len() - result.consumed_out; |
| 620 |
let filled = self.vector.len() - unfilled; |
| 621 |
self.vector.truncate(filled); |
| 622 |
|
| 623 |
// Handle the status in the result. |
| 624 |
match result.status { |
| 625 |
Err(err) => Err(err), |
| 626 |
Ok(LzwStatus::NoProgress) if must_finish => Err(LzwError::InvalidCode), |
| 627 |
Ok(LzwStatus::NoProgress) | Ok(LzwStatus::Done) => Ok(Progress::Done), |
| 628 |
Ok(LzwStatus::Ok) => Ok(Progress::Ok), |
| 629 |
} |
| 630 |
}; |
| 631 |
|
| 632 |
// Decode chunks of input data until we're done. |
| 633 |
let status: Result<(), _> = core::iter::repeat_with(once) |
| 634 |
// scan+fuse can be replaced with map_while |
| 635 |
.scan((), |(), result| match result { |
| 636 |
Ok(Progress::Ok) => Some(Ok(())), |
| 637 |
Err(err) => Some(Err(err)), |
| 638 |
Ok(Progress::Done) => None, |
| 639 |
}) |
| 640 |
.fuse() |
| 641 |
.collect(); |
| 642 |
|
| 643 |
if let Err(err) = status { |
| 644 |
result.status = Err(err); |
| 645 |
} |
| 646 |
|
| 647 |
result |
| 648 |
} |
| 649 |
} |
| 650 |
|
| 651 |
// This is implemented in a separate file, so that 1.34.2 does not parse it. Otherwise, it would |
| 652 |
// trip over the usage of await, which is a reserved keyword in that edition/version. It only |
| 653 |
// contains an impl block. |
| 654 |
#[cfg(feature = "async")] |
| 655 |
#[path = "decode_into_async.rs"] |
| 656 |
mod impl_decode_into_async; |
| 657 |
|
| 658 |
impl<C: CodeBuffer, CgC: CodegenConstants> DecodeState<C, CgC> { |
| 659 |
fn new(min_size: u8) -> Self { |
| 660 |
DecodeState { |
| 661 |
min_size, |
| 662 |
table: Table::new(), |
| 663 |
buffer: Buffer::new(), |
| 664 |
last: None, |
| 665 |
clear_code: 1 << min_size, |
| 666 |
end_code: (1 << min_size) + 1, |
| 667 |
next_code: (1 << min_size) + 2, |
| 668 |
has_ended: false, |
| 669 |
is_tiff: false, |
| 670 |
implicit_reset: true, |
| 671 |
code_buffer: CodeBuffer::new(min_size), |
| 672 |
constants: core::marker::PhantomData, |
| 673 |
} |
| 674 |
} |
| 675 |
|
| 676 |
fn init_tables(&mut self) { |
| 677 |
self.code_buffer.reset(self.min_size); |
| 678 |
self.next_code = (1 << self.min_size) + 2; |
| 679 |
self.table.init(self.min_size); |
| 680 |
} |
| 681 |
|
| 682 |
fn reset_tables(&mut self) { |
| 683 |
self.code_buffer.reset(self.min_size); |
| 684 |
self.next_code = (1 << self.min_size) + 2; |
| 685 |
self.table.clear(self.min_size); |
| 686 |
} |
| 687 |
} |
| 688 |
|
| 689 |
impl<C: CodeBuffer, CgC: CodegenConstants> Stateful for DecodeState<C, CgC> { |
| 690 |
fn has_ended(&self) -> bool { |
| 691 |
self.has_ended |
| 692 |
} |
| 693 |
|
| 694 |
fn restart(&mut self) { |
| 695 |
self.has_ended = false; |
| 696 |
} |
| 697 |
|
| 698 |
fn reset(&mut self) { |
| 699 |
self.table.init(self.min_size); |
| 700 |
self.next_code = (1 << self.min_size) + 2; |
| 701 |
self.buffer.read_mark = 0; |
| 702 |
self.buffer.write_mark = 0; |
| 703 |
self.last = None; |
| 704 |
self.restart(); |
| 705 |
self.code_buffer = CodeBuffer::new(self.min_size); |
| 706 |
} |
| 707 |
|
| 708 |
fn advance(&mut self, mut inp: &[u8], mut out: &mut [u8]) -> BufferResult { |
| 709 |
// Skip everything if there is nothing to do. |
| 710 |
if self.has_ended { |
| 711 |
return BufferResult { |
| 712 |
consumed_in: 0, |
| 713 |
consumed_out: 0, |
| 714 |
status: Ok(LzwStatus::Done), |
| 715 |
}; |
| 716 |
} |
| 717 |
|
| 718 |
// Rough description: |
| 719 |
// We will fill the output slice as much as possible until either there is no more symbols |
| 720 |
// to decode or an end code has been reached. This requires an internal buffer to hold a |
| 721 |
// potential tail of the word corresponding to the last symbol. This tail will then be |
| 722 |
// decoded first before continuing with the regular decoding. The same buffer is required |
| 723 |
// to persist some symbol state across calls. |
| 724 |
// |
| 725 |
// We store the words corresponding to code symbols in an index chain, bytewise, where we |
| 726 |
// push each decoded symbol. (TODO: wuffs shows some success with 8-byte units). This chain |
| 727 |
// is traversed for each symbol when it is decoded and bytes are placed directly into the |
| 728 |
// output slice. In the special case (new_code == next_code) we use an existing decoded |
| 729 |
// version that is present in either the out bytes of this call or in buffer to copy the |
| 730 |
// repeated prefix slice. |
| 731 |
// TODO: I played with a 'decoding cache' to remember the position of long symbols and |
| 732 |
// avoid traversing the chain, doing a copy of memory instead. It did however not lead to |
| 733 |
// a serious improvement. It's just unlikely to both have a long symbol and have that |
| 734 |
// repeated twice in the same output buffer. |
| 735 |
// |
| 736 |
// You will also find the (to my knowledge novel) concept of a _decoding burst_ which |
| 737 |
// gained some >~10% speedup in tests. This is motivated by wanting to use out-of-order |
| 738 |
// execution as much as possible and for this reason have the least possible stress on |
| 739 |
// branch prediction. Our decoding table already gives us a lookahead on symbol lengths but |
| 740 |
// only for re-used codes, not novel ones. This lookahead also makes the loop termination |
| 741 |
// when restoring each byte of the code word perfectly predictable! So a burst is a chunk |
| 742 |
// of code words which are all independent of each other, have known lengths _and_ are |
| 743 |
// guaranteed to fit into the out slice without requiring a buffer. One burst can be |
| 744 |
// decoded in an extremely tight loop. |
| 745 |
// |
| 746 |
// TODO: since words can be at most (1 << MAX_CODESIZE) = 4096 bytes long we could avoid |
| 747 |
// that intermediate buffer at the expense of not always filling the output buffer |
| 748 |
// completely. Alternatively we might follow its chain of precursor states twice. This may |
| 749 |
// be even cheaper if we store more than one byte per link so it really should be |
| 750 |
// evaluated. |
| 751 |
// TODO: if the caller was required to provide the previous last word we could also avoid |
| 752 |
// the buffer for cases where we need it to restore the next code! This could be built |
| 753 |
// backwards compatible by only doing it after an opt-in call that enables the behaviour. |
| 754 |
|
| 755 |
// Record initial lengths for the result that is returned. |
| 756 |
let o_in = inp.len(); |
| 757 |
let o_out = out.len(); |
| 758 |
|
| 759 |
// The code_link is the previously decoded symbol. |
| 760 |
// It's used to link the new code back to its predecessor. |
| 761 |
let mut code_link = None; |
| 762 |
// The status, which is written to on an invalid code. |
| 763 |
let mut status = Ok(LzwStatus::Ok); |
| 764 |
|
| 765 |
match self.last.take() { |
| 766 |
// No last state? This is the first code after a reset? |
| 767 |
None => { |
| 768 |
match self.next_symbol(&mut inp) { |
| 769 |
// Plainly invalid code. |
| 770 |
Some(code) if code > self.next_code => status = Err(LzwError::InvalidCode), |
| 771 |
// next_code would require an actual predecessor. |
| 772 |
Some(code) if code == self.next_code => status = Err(LzwError::InvalidCode), |
| 773 |
// No more symbols available and nothing decoded yet. |
| 774 |
// Assume that we didn't make progress, this may get reset to Done if we read |
| 775 |
// some bytes from the input. |
| 776 |
None => status = Ok(LzwStatus::NoProgress), |
| 777 |
// Handle a valid code. |
| 778 |
Some(init_code) => { |
| 779 |
if init_code == self.clear_code { |
| 780 |
self.init_tables(); |
| 781 |
} else if init_code == self.end_code { |
| 782 |
self.has_ended = true; |
| 783 |
status = Ok(LzwStatus::Done); |
| 784 |
} else if self.table.is_empty() { |
| 785 |
if self.implicit_reset { |
| 786 |
self.init_tables(); |
| 787 |
|
| 788 |
self.buffer.fill_reconstruct(&self.table, init_code); |
| 789 |
let link = self.table.at(init_code).clone(); |
| 790 |
code_link = Some(DerivationBase { |
| 791 |
code: init_code, |
| 792 |
first: link.first, |
| 793 |
}); |
| 794 |
} else { |
| 795 |
// We require an explicit reset. |
| 796 |
status = Err(LzwError::InvalidCode); |
| 797 |
} |
| 798 |
} else { |
| 799 |
// Reconstruct the first code in the buffer. |
| 800 |
self.buffer.fill_reconstruct(&self.table, init_code); |
| 801 |
let link = self.table.at(init_code).clone(); |
| 802 |
code_link = Some(DerivationBase { |
| 803 |
code: init_code, |
| 804 |
first: link.first, |
| 805 |
}); |
| 806 |
} |
| 807 |
} |
| 808 |
} |
| 809 |
} |
| 810 |
// Move the tracking state to the stack. |
| 811 |
Some(tup) => code_link = Some(tup), |
| 812 |
}; |
| 813 |
|
| 814 |
// Track an empty `burst` (see below) means we made no progress. |
| 815 |
let mut have_yet_to_decode_data = false; |
| 816 |
|
| 817 |
// Restore the previous state, if any. |
| 818 |
if code_link.is_some() { |
| 819 |
let remain = self.buffer.buffer(); |
| 820 |
// Check if we can fully finish the buffer. |
| 821 |
if remain.len() > out.len() { |
| 822 |
if out.is_empty() { |
| 823 |
// This also implies the buffer is _not_ empty and we will not enter any |
| 824 |
// decoding loop. |
| 825 |
status = Ok(LzwStatus::NoProgress); |
| 826 |
} else { |
| 827 |
out.copy_from_slice(&remain[..out.len()]); |
| 828 |
self.buffer.consume(out.len()); |
| 829 |
out = &mut []; |
| 830 |
} |
| 831 |
} else if remain.is_empty() { |
| 832 |
status = Ok(LzwStatus::NoProgress); |
| 833 |
have_yet_to_decode_data = true; |
| 834 |
} else { |
| 835 |
let consumed = remain.len(); |
| 836 |
out[..consumed].copy_from_slice(remain); |
| 837 |
self.buffer.consume(consumed); |
| 838 |
out = &mut out[consumed..]; |
| 839 |
have_yet_to_decode_data = false; |
| 840 |
} |
| 841 |
} |
| 842 |
|
| 843 |
// A special reference to out slice which holds the last decoded symbol. |
| 844 |
let mut last_decoded: Option<&[u8]> = None; |
| 845 |
|
| 846 |
if self.buffer.buffer().is_empty() { |
| 847 |
// Hot loop that writes data to the output as long as we can do so directly from the |
| 848 |
// input stream. As an invariant of this block we did not need to use the buffer to |
| 849 |
// store a decoded code word. Testing the condition ahead of time avoids a test in the |
| 850 |
// loop body since every code path where the buffer is filled already breaks. |
| 851 |
// |
| 852 |
// In a previous iteration of the code we trusted compiler optimization to work this |
| 853 |
// out but it seems that it does not. Another edit hidden behind some performance work |
| 854 |
// then edited out the check, inadvertently changing the behavior for callers that |
| 855 |
// relied on being able to provide an empty output buffer and still receiving a useful |
| 856 |
// signal about the state of the stream. |
| 857 |
|
| 858 |
// A burst is a sequence of code words that are independently decoded, i.e. they do not |
| 859 |
// change the state of the decoder in ways that would influence the interpretation of |
| 860 |
// each other. That is: they are not special symbols, they do not make us increase the |
| 861 |
// code size, they are each codes already in the tree before the burst. |
| 862 |
// |
| 863 |
// The tracking state for a burst. These are actually initialized later but compiler |
| 864 |
// wasn't smart enough to fully optimize out the init code so that appears outside the |
| 865 |
// loop. |
| 866 |
let mut burst = [0; BURST]; |
| 867 |
let mut burst_byte_len = [0u16; BURST]; |
| 868 |
let mut burst_byte = [0u8; BURST]; |
| 869 |
let mut target: [&mut [u8]; BURST] = Default::default(); |
| 870 |
|
| 871 |
loop { |
| 872 |
// In particular, we *also* break if the output buffer is still empty. Especially |
| 873 |
// when the output parameter was an empty slice, we must try to fetch at least one |
| 874 |
// code but with YIELD_ON_FULL we do not. |
| 875 |
if CgC::YIELD_ON_FULL && out.is_empty() { |
| 876 |
break; |
| 877 |
} |
| 878 |
|
| 879 |
let mut deriv = match code_link.take() { |
| 880 |
Some(link) => link, |
| 881 |
None => { |
| 882 |
// TODO: we do not need to break here. This does not indicate that the buffer |
| 883 |
// has been filled, rather it indicates we have reset the state. The next code |
| 884 |
// should be part of the initial alphabet. However the first code is special in |
| 885 |
// the sense of not creating a new code itself. This is handled correctly in |
| 886 |
// the initialization prior to the loop; and in particular that handling as |
| 887 |
// written currently relies on putting it into the buffer; so handling it we |
| 888 |
// would need to ensure that either the buffer is fully cleared after its use, |
| 889 |
// or use another implementation of handling that first code. |
| 890 |
break; |
| 891 |
} |
| 892 |
}; |
| 893 |
|
| 894 |
// Ensure the code buffer is full, we're about to request some codes. |
| 895 |
// Note that this also ensures at least one code is in the buffer if any input is left. |
| 896 |
self.refill_bits(&mut inp); |
| 897 |
let cnt = self.code_buffer.peek_bits(&mut burst); |
| 898 |
|
| 899 |
// No code left in the buffer, and no more bytes to refill the buffer. |
| 900 |
if cnt == 0 { |
| 901 |
if have_yet_to_decode_data { |
| 902 |
status = Ok(LzwStatus::NoProgress); |
| 903 |
} |
| 904 |
|
| 905 |
code_link = Some(deriv); |
| 906 |
break; |
| 907 |
} |
| 908 |
|
| 909 |
debug_assert!( |
| 910 |
// When the table is full, we have a max code above the size switch. |
| 911 |
self.table.inner.len() >= MAX_ENTRIES - usize::from(self.is_tiff) |
| 912 |
// When the code size is 2 we have a bit code: (0, 1, CLS, EOF). Then the |
| 913 |
// computed next_code is 4 which already exceeds the bit width from the start. |
| 914 |
// Then we will immediately switch code size after this code. |
| 915 |
// |
| 916 |
// TODO: this is the reason for some saturating and non-sharp comparisons in |
| 917 |
// the code below. Maybe it makes sense to revisit turning this into a compile |
| 918 |
// time choice? |
| 919 |
|| (self.code_buffer.code_size() == 1 && self.next_code < 4) |
| 920 |
|| (self.code_buffer.code_size() == 2 && self.next_code == 4) |
| 921 |
|| self.code_buffer.max_code() - Code::from(self.is_tiff) >= self.next_code, |
| 922 |
"Table: {}, code_size: {}, next_code: {}, table_condition: {}", |
| 923 |
self.table.is_full(), |
| 924 |
self.code_buffer.code_size(), |
| 925 |
self.next_code, |
| 926 |
self.code_buffer.max_code() - Code::from(self.is_tiff), |
| 927 |
); |
| 928 |
|
| 929 |
let mut burst_size = 0; |
| 930 |
let left_before_size_switch = (self.code_buffer.max_code() |
| 931 |
- Code::from(self.is_tiff)) |
| 932 |
.saturating_sub(self.next_code); |
| 933 |
|
| 934 |
// A burst is a sequence of decodes that are completely independent of each other. This |
| 935 |
// is the case if neither is an end code, a clear code, or a next code, i.e. we have |
| 936 |
// all of them in the decoding table and thus known their depths, and additionally if |
| 937 |
// we can decode them directly into the output buffer. |
| 938 |
for b in &burst[..cnt] { |
| 939 |
// We can commit the previous burst code, and will take a slice from the output |
| 940 |
// buffer. This also avoids the bounds check in the tight loop later. |
| 941 |
if burst_size > 0 { |
| 942 |
let len = burst_byte_len[burst_size - 1]; |
| 943 |
let (into, tail) = out.split_at_mut(usize::from(len)); |
| 944 |
target[burst_size - 1] = into; |
| 945 |
out = tail; |
| 946 |
} |
| 947 |
|
| 948 |
// Check that we don't overflow the code size with all codes we burst decode. |
| 949 |
burst_size += 1; |
| 950 |
|
| 951 |
if burst_size > usize::from(left_before_size_switch) { |
| 952 |
break; |
| 953 |
} |
| 954 |
|
| 955 |
let read_code = *b; |
| 956 |
|
| 957 |
// A burst code can't be special. |
| 958 |
if read_code == self.clear_code |
| 959 |
|| read_code == self.end_code |
| 960 |
|| read_code >= self.next_code |
| 961 |
{ |
| 962 |
break; |
| 963 |
} |
| 964 |
|
| 965 |
// Read the code length and check that we can decode directly into the out slice. |
| 966 |
let len = self.table.depths[usize::from(read_code)]; |
| 967 |
|
| 968 |
if out.len() < usize::from(len) { |
| 969 |
break; |
| 970 |
} |
| 971 |
|
| 972 |
// We do exactly one more code (the one being inspected in the current iteration) |
| 973 |
// after the 'burst'. When we want to break decoding precisely on the supplied |
| 974 |
// buffer, we check if this is the last code to be decoded into it. |
| 975 |
if CgC::YIELD_ON_FULL { |
| 976 |
if out.len() == usize::from(len) { |
| 977 |
break; |
| 978 |
} |
| 979 |
} |
| 980 |
|
| 981 |
burst_byte_len[burst_size - 1] = len; |
| 982 |
} |
| 983 |
|
| 984 |
self.code_buffer.consume_bits(burst_size as u8); |
| 985 |
have_yet_to_decode_data = false; |
| 986 |
|
| 987 |
// Note that the very last code in the burst buffer doesn't actually belong to the |
| 988 |
// burst itself. TODO: sometimes it could, we just don't differentiate between the |
| 989 |
// breaks and a loop end condition above. That may be a speed advantage? |
| 990 |
let (&new_code, burst) = burst[..burst_size].split_last().unwrap(); |
| 991 |
|
| 992 |
// The very tight loop for restoring the actual burst. These can be reconstructed in |
| 993 |
// parallel since none of them depend on a prior constructed. Only the derivation of |
| 994 |
// new codes is not parallel. There are no size changes here either. |
| 995 |
let burst_targets = &mut target[..burst_size - 1]; |
| 996 |
|
| 997 |
if !self.table.is_full() { |
| 998 |
self.next_code += burst_targets.len() as u16; |
| 999 |
} |
| 1000 |
|
| 1001 |
for ((&burst, target), byte) in |
| 1002 |
burst.iter().zip(&mut *burst_targets).zip(&mut burst_byte) |
| 1003 |
{ |
| 1004 |
*byte = self.table.reconstruct(burst, target); |
| 1005 |
} |
| 1006 |
|
| 1007 |
self.table.derive_burst(&mut deriv, burst, &burst_byte[..]); |
| 1008 |
|
| 1009 |
// Now handle the special codes. |
| 1010 |
if new_code == self.clear_code { |
| 1011 |
self.reset_tables(); |
| 1012 |
last_decoded = None; |
| 1013 |
// Restarts in the next call to the entry point. |
| 1014 |
break; |
| 1015 |
} |
| 1016 |
|
| 1017 |
if new_code == self.end_code { |
| 1018 |
self.has_ended = true; |
| 1019 |
status = Ok(LzwStatus::Done); |
| 1020 |
last_decoded = None; |
| 1021 |
break; |
| 1022 |
} |
| 1023 |
|
| 1024 |
if new_code > self.next_code { |
| 1025 |
status = Err(LzwError::InvalidCode); |
| 1026 |
last_decoded = None; |
| 1027 |
break; |
| 1028 |
} |
| 1029 |
|
| 1030 |
let required_len = if new_code == self.next_code { |
| 1031 |
self.table.depths[usize::from(deriv.code)] + 1 |
| 1032 |
} else { |
| 1033 |
self.table.depths[usize::from(new_code)] |
| 1034 |
}; |
| 1035 |
|
| 1036 |
// We need the decoded data of the new code if it is the `next_code`. This is the |
| 1037 |
// special case of LZW decoding that is demonstrated by `banana` (or form cScSc). In |
| 1038 |
// all other cases we only need the first character of the decoded data. |
| 1039 |
let have_next_code = new_code == self.next_code; |
| 1040 |
|
| 1041 |
// Update the slice holding the last decoded word. |
| 1042 |
if have_next_code { |
| 1043 |
// If we did not have any burst code, we still hold that slice in the buffer. |
| 1044 |
if let Some(new_last) = target[..burst_size - 1].last_mut() { |
| 1045 |
let slice = core::mem::replace(new_last, &mut []); |
| 1046 |
last_decoded = Some(&*slice); |
| 1047 |
} |
| 1048 |
} |
| 1049 |
|
| 1050 |
let cha; |
| 1051 |
let is_in_buffer = usize::from(required_len) > out.len(); |
| 1052 |
// Check if we will need to store our current state into the buffer. |
| 1053 |
if is_in_buffer { |
| 1054 |
if have_next_code { |
| 1055 |
// last_decoded will be Some if we have restored any code into the out slice. |
| 1056 |
// Otherwise it will still be present in the buffer. |
| 1057 |
if let Some(last) = last_decoded.take() { |
| 1058 |
self.buffer.bytes[..last.len()].copy_from_slice(last); |
| 1059 |
self.buffer.write_mark = last.len(); |
| 1060 |
self.buffer.read_mark = last.len(); |
| 1061 |
} |
| 1062 |
|
| 1063 |
cha = self.buffer.fill_cscsc(); |
| 1064 |
} else { |
| 1065 |
// Restore the decoded word into the buffer. |
| 1066 |
last_decoded = None; |
| 1067 |
cha = self.buffer.fill_reconstruct(&self.table, new_code); |
| 1068 |
} |
| 1069 |
} else { |
| 1070 |
let (target, tail) = out.split_at_mut(usize::from(required_len)); |
| 1071 |
out = tail; |
| 1072 |
|
| 1073 |
if have_next_code { |
| 1074 |
// Reconstruct high. |
| 1075 |
let source = match last_decoded.take() { |
| 1076 |
Some(last) => last, |
| 1077 |
None => &self.buffer.bytes[..self.buffer.write_mark], |
| 1078 |
}; |
| 1079 |
|
| 1080 |
// We don't *actually* expect the unwrap to happen. Each source is at least 1 |
| 1081 |
// byte long. But llvm doesn't know this (too much indirect loads and cases). |
| 1082 |
cha = source.get(0).map(|x| *x).unwrap_or(0); |
| 1083 |
target[..source.len()].copy_from_slice(source); |
| 1084 |
target[source.len()..][0] = cha; |
| 1085 |
} else { |
| 1086 |
cha = self.table.reconstruct(new_code, target); |
| 1087 |
} |
| 1088 |
|
| 1089 |
// A new decoded word. |
| 1090 |
last_decoded = Some(target); |
| 1091 |
} |
| 1092 |
|
| 1093 |
// Each newly read code creates one new code/link based on the preceding code if we |
| 1094 |
// have enough space to put it there. |
| 1095 |
if !self.table.is_full() { |
| 1096 |
self.table.derive(&deriv, cha); |
| 1097 |
|
| 1098 |
if self.next_code >= self.code_buffer.max_code() - Code::from(self.is_tiff) |
| 1099 |
&& self.code_buffer.code_size() < MAX_CODESIZE |
| 1100 |
{ |
| 1101 |
self.bump_code_size(); |
| 1102 |
} |
| 1103 |
|
| 1104 |
self.next_code += 1; |
| 1105 |
} |
| 1106 |
|
| 1107 |
// store the information on the decoded word. |
| 1108 |
code_link = Some(DerivationBase { |
| 1109 |
code: new_code, |
| 1110 |
first: cha, |
| 1111 |
}); |
| 1112 |
|
| 1113 |
// Can't make any more progress with decoding. |
| 1114 |
// |
| 1115 |
// We have more data buffered but not enough space to put it? We want fetch a next |
| 1116 |
// symbol if possible as in the case of it being a new symbol we can refer to the |
| 1117 |
// buffered output as the source for that symbol's meaning and do a memcpy. |
| 1118 |
// |
| 1119 |
// Since this test is after decoding at least one code, we can now check for an |
| 1120 |
// empty buffer and still guarantee progress when one was passed as a parameter. |
| 1121 |
if is_in_buffer || out.is_empty() { |
| 1122 |
break; |
| 1123 |
} |
| 1124 |
} |
| 1125 |
} |
| 1126 |
|
| 1127 |
// We need to store the last word into the buffer in case the first code in the next |
| 1128 |
// iteration is the next_code. |
| 1129 |
if let Some(tail) = last_decoded { |
| 1130 |
self.buffer.bytes[..tail.len()].copy_from_slice(tail); |
| 1131 |
self.buffer.write_mark = tail.len(); |
| 1132 |
// Mark the full buffer as having been consumed. |
| 1133 |
self.buffer.read_mark = tail.len(); |
| 1134 |
} |
| 1135 |
|
| 1136 |
// Ensure we don't indicate that no progress was made if we read some bytes from the input |
| 1137 |
// (which is progress). |
| 1138 |
if o_in > inp.len() { |
| 1139 |
if let Ok(LzwStatus::NoProgress) = status { |
| 1140 |
status = Ok(LzwStatus::Ok); |
| 1141 |
} |
| 1142 |
} |
| 1143 |
|
| 1144 |
// Store the code/link state. |
| 1145 |
self.last = code_link; |
| 1146 |
|
| 1147 |
BufferResult { |
| 1148 |
consumed_in: o_in.wrapping_sub(inp.len()), |
| 1149 |
consumed_out: o_out.wrapping_sub(out.len()), |
| 1150 |
status, |
| 1151 |
} |
| 1152 |
} |
| 1153 |
} |
| 1154 |
|
| 1155 |
impl<C: CodeBuffer, CgC: CodegenConstants> DecodeState<C, CgC> { |
| 1156 |
fn next_symbol(&mut self, inp: &mut &[u8]) -> Option<Code> { |
| 1157 |
self.code_buffer.next_symbol(inp) |
| 1158 |
} |
| 1159 |
|
| 1160 |
fn bump_code_size(&mut self) { |
| 1161 |
self.code_buffer.bump_code_size() |
| 1162 |
} |
| 1163 |
|
| 1164 |
fn refill_bits(&mut self, inp: &mut &[u8]) { |
| 1165 |
self.code_buffer.refill_bits(inp) |
| 1166 |
} |
| 1167 |
} |
| 1168 |
|
| 1169 |
impl CodeBuffer for MsbBuffer { |
| 1170 |
fn new(min_size: u8) -> Self { |
| 1171 |
MsbBuffer { |
| 1172 |
code_size: min_size + 1, |
| 1173 |
code_mask: (1u16 << (min_size + 1)) - 1, |
| 1174 |
bit_buffer: 0, |
| 1175 |
bits: 0, |
| 1176 |
} |
| 1177 |
} |
| 1178 |
|
| 1179 |
fn reset(&mut self, min_size: u8) { |
| 1180 |
self.code_size = min_size + 1; |
| 1181 |
self.code_mask = (1 << self.code_size) - 1; |
| 1182 |
} |
| 1183 |
|
| 1184 |
fn next_symbol(&mut self, inp: &mut &[u8]) -> Option<Code> { |
| 1185 |
if self.bits < self.code_size { |
| 1186 |
self.refill_bits(inp); |
| 1187 |
} |
| 1188 |
|
| 1189 |
if self.bits < self.code_size { |
| 1190 |
return None; |
| 1191 |
} |
| 1192 |
|
| 1193 |
let mask = u64::from(self.code_mask); |
| 1194 |
let rotbuf = self.bit_buffer.rotate_left(self.code_size.into()); |
| 1195 |
self.bit_buffer = rotbuf & !mask; |
| 1196 |
self.bits -= self.code_size; |
| 1197 |
Some((rotbuf & mask) as u16) |
| 1198 |
} |
| 1199 |
|
| 1200 |
fn bump_code_size(&mut self) { |
| 1201 |
self.code_size += 1; |
| 1202 |
self.code_mask = (self.code_mask << 1) | 1; |
| 1203 |
} |
| 1204 |
|
| 1205 |
fn refill_bits(&mut self, inp: &mut &[u8]) { |
| 1206 |
let wish_count = (64 - self.bits) / 8; |
| 1207 |
let mut buffer = [0u8; 8]; |
| 1208 |
let new_bits = match inp.get(..usize::from(wish_count)) { |
| 1209 |
Some(bytes) => { |
| 1210 |
buffer[..usize::from(wish_count)].copy_from_slice(bytes); |
| 1211 |
*inp = &inp[usize::from(wish_count)..]; |
| 1212 |
wish_count * 8 |
| 1213 |
} |
| 1214 |
None => { |
| 1215 |
let new_bits = inp.len() * 8; |
| 1216 |
buffer[..inp.len()].copy_from_slice(inp); |
| 1217 |
*inp = &[]; |
| 1218 |
new_bits as u8 |
| 1219 |
} |
| 1220 |
}; |
| 1221 |
self.bit_buffer |= u64::from_be_bytes(buffer) >> self.bits; |
| 1222 |
self.bits += new_bits; |
| 1223 |
} |
| 1224 |
|
| 1225 |
fn peek_bits(&self, code: &mut [Code; BURST]) -> usize { |
| 1226 |
let mut bit_buffer = self.bit_buffer; |
| 1227 |
let mask = u64::from(self.code_mask); |
| 1228 |
let mut consumed = 0; |
| 1229 |
let mut cnt = 0; |
| 1230 |
|
| 1231 |
for b in code { |
| 1232 |
let consumed_after = consumed + self.code_size; |
| 1233 |
if consumed_after > self.bits { |
| 1234 |
break; |
| 1235 |
} |
| 1236 |
|
| 1237 |
cnt += 1; |
| 1238 |
consumed = consumed_after; |
| 1239 |
|
| 1240 |
let rotbuf = bit_buffer.rotate_left(self.code_size.into()); |
| 1241 |
*b = (rotbuf & mask) as u16; |
| 1242 |
// The read bits are 'appended' but we never interpret those appended bits. |
| 1243 |
bit_buffer = rotbuf; |
| 1244 |
} |
| 1245 |
|
| 1246 |
cnt |
| 1247 |
} |
| 1248 |
|
| 1249 |
fn consume_bits(&mut self, code_cnt: u8) { |
| 1250 |
let bits = self.code_size * code_cnt; |
| 1251 |
debug_assert!(bits <= self.bits); |
| 1252 |
|
| 1253 |
if bits >= self.bits { |
| 1254 |
self.bit_buffer = 0; |
| 1255 |
} else { |
| 1256 |
// bits < self.bits so this must be smaller than the number size. |
| 1257 |
self.bit_buffer = self.bit_buffer << bits; |
| 1258 |
} |
| 1259 |
|
| 1260 |
self.bits = self.bits.wrapping_sub(bits); |
| 1261 |
} |
| 1262 |
|
| 1263 |
fn max_code(&self) -> Code { |
| 1264 |
self.code_mask |
| 1265 |
} |
| 1266 |
|
| 1267 |
fn code_size(&self) -> u8 { |
| 1268 |
self.code_size |
| 1269 |
} |
| 1270 |
} |
| 1271 |
|
| 1272 |
impl CodeBuffer for LsbBuffer { |
| 1273 |
fn new(min_size: u8) -> Self { |
| 1274 |
LsbBuffer { |
| 1275 |
code_size: min_size + 1, |
| 1276 |
code_mask: (1u16 << (min_size + 1)) - 1, |
| 1277 |
bit_buffer: 0, |
| 1278 |
bits: 0, |
| 1279 |
} |
| 1280 |
} |
| 1281 |
|
| 1282 |
fn reset(&mut self, min_size: u8) { |
| 1283 |
self.code_size = min_size + 1; |
| 1284 |
self.code_mask = (1 << self.code_size) - 1; |
| 1285 |
} |
| 1286 |
|
| 1287 |
fn next_symbol(&mut self, inp: &mut &[u8]) -> Option<Code> { |
| 1288 |
if self.bits < self.code_size { |
| 1289 |
self.refill_bits(inp); |
| 1290 |
} |
| 1291 |
|
| 1292 |
if self.bits < self.code_size { |
| 1293 |
return None; |
| 1294 |
} |
| 1295 |
|
| 1296 |
let mask = u64::from(self.code_mask); |
| 1297 |
let code = self.bit_buffer & mask; |
| 1298 |
self.bit_buffer >>= self.code_size; |
| 1299 |
self.bits -= self.code_size; |
| 1300 |
Some(code as u16) |
| 1301 |
} |
| 1302 |
|
| 1303 |
fn bump_code_size(&mut self) { |
| 1304 |
self.code_size += 1; |
| 1305 |
self.code_mask = (self.code_mask << 1) | 1; |
| 1306 |
} |
| 1307 |
|
| 1308 |
fn refill_bits(&mut self, inp: &mut &[u8]) { |
| 1309 |
let wish_count = (64 - self.bits) / 8; |
| 1310 |
let mut buffer = [0u8; 8]; |
| 1311 |
let new_bits = match inp.get(..usize::from(wish_count)) { |
| 1312 |
Some(bytes) => { |
| 1313 |
buffer[..usize::from(wish_count)].copy_from_slice(bytes); |
| 1314 |
*inp = &inp[usize::from(wish_count)..]; |
| 1315 |
wish_count * 8 |
| 1316 |
} |
| 1317 |
None => { |
| 1318 |
let new_bits = inp.len() * 8; |
| 1319 |
buffer[..inp.len()].copy_from_slice(inp); |
| 1320 |
*inp = &[]; |
| 1321 |
new_bits as u8 |
| 1322 |
} |
| 1323 |
}; |
| 1324 |
self.bit_buffer |= u64::from_be_bytes(buffer).swap_bytes() << self.bits; |
| 1325 |
self.bits += new_bits; |
| 1326 |
} |
| 1327 |
|
| 1328 |
fn peek_bits(&self, code: &mut [Code; BURST]) -> usize { |
| 1329 |
let mut bit_buffer = self.bit_buffer; |
| 1330 |
let mask = u64::from(self.code_mask); |
| 1331 |
let mut consumed = 0; |
| 1332 |
let mut cnt = 0; |
| 1333 |
|
| 1334 |
for b in code { |
| 1335 |
let consumed_after = consumed + self.code_size; |
| 1336 |
if consumed_after > self.bits { |
| 1337 |
break; |
| 1338 |
} |
| 1339 |
|
| 1340 |
cnt += 1; |
| 1341 |
consumed = consumed_after; |
| 1342 |
|
| 1343 |
*b = (bit_buffer & mask) as u16; |
| 1344 |
bit_buffer = bit_buffer >> self.code_size; |
| 1345 |
} |
| 1346 |
|
| 1347 |
cnt |
| 1348 |
} |
| 1349 |
|
| 1350 |
fn consume_bits(&mut self, code_cnt: u8) { |
| 1351 |
let bits = self.code_size * code_cnt; |
| 1352 |
debug_assert!(bits <= self.bits); |
| 1353 |
|
| 1354 |
if bits >= self.bits { |
| 1355 |
self.bit_buffer = 0; |
| 1356 |
} else { |
| 1357 |
// bits < self.bits so this must be smaller than the number size. |
| 1358 |
self.bit_buffer = self.bit_buffer >> bits; |
| 1359 |
} |
| 1360 |
|
| 1361 |
self.bits = self.bits.wrapping_sub(bits); |
| 1362 |
} |
| 1363 |
|
| 1364 |
fn max_code(&self) -> Code { |
| 1365 |
self.code_mask |
| 1366 |
} |
| 1367 |
|
| 1368 |
fn code_size(&self) -> u8 { |
| 1369 |
self.code_size |
| 1370 |
} |
| 1371 |
} |
| 1372 |
|
| 1373 |
impl Buffer { |
| 1374 |
fn new() -> Self { |
| 1375 |
Buffer { |
| 1376 |
bytes: vec![0; MAX_ENTRIES].into_boxed_slice(), |
| 1377 |
read_mark: 0, |
| 1378 |
write_mark: 0, |
| 1379 |
} |
| 1380 |
} |
| 1381 |
|
| 1382 |
/// When encoding a sequence `cScSc` where `c` is any character and `S` is any string |
| 1383 |
/// this results in two codes `AB`, `A` encoding `cS` and `B` encoding `cSc`. Supposing |
| 1384 |
/// the buffer is already filled with the reconstruction of `A`, we can easily fill it |
| 1385 |
/// with the reconstruction of `B`. |
| 1386 |
fn fill_cscsc(&mut self) -> u8 { |
| 1387 |
self.bytes[self.write_mark] = self.bytes[0]; |
| 1388 |
self.write_mark += 1; |
| 1389 |
self.read_mark = 0; |
| 1390 |
self.bytes[0] |
| 1391 |
} |
| 1392 |
|
| 1393 |
// Fill the buffer by decoding from the table |
| 1394 |
fn fill_reconstruct(&mut self, table: &Table, code: Code) -> u8 { |
| 1395 |
self.write_mark = 0; |
| 1396 |
self.read_mark = 0; |
| 1397 |
let depth = table.depths[usize::from(code)]; |
| 1398 |
let mut memory = core::mem::replace(&mut self.bytes, Box::default()); |
| 1399 |
|
| 1400 |
let out = &mut memory[..usize::from(depth)]; |
| 1401 |
let last = table.reconstruct(code, out); |
| 1402 |
|
| 1403 |
self.bytes = memory; |
| 1404 |
self.write_mark = usize::from(depth); |
| 1405 |
last |
| 1406 |
} |
| 1407 |
|
| 1408 |
fn buffer(&self) -> &[u8] { |
| 1409 |
&self.bytes[self.read_mark..self.write_mark] |
| 1410 |
} |
| 1411 |
|
| 1412 |
fn consume(&mut self, amt: usize) { |
| 1413 |
self.read_mark += amt; |
| 1414 |
} |
| 1415 |
} |
| 1416 |
|
| 1417 |
impl Table { |
| 1418 |
fn new() -> Self { |
| 1419 |
Table { |
| 1420 |
inner: Vec::with_capacity(MAX_ENTRIES), |
| 1421 |
depths: Vec::with_capacity(MAX_ENTRIES), |
| 1422 |
} |
| 1423 |
} |
| 1424 |
|
| 1425 |
fn clear(&mut self, min_size: u8) { |
| 1426 |
let static_count = usize::from(1u16 << u16::from(min_size)) + 2; |
| 1427 |
self.inner.truncate(static_count); |
| 1428 |
self.depths.truncate(static_count); |
| 1429 |
} |
| 1430 |
|
| 1431 |
fn init(&mut self, min_size: u8) { |
| 1432 |
self.inner.clear(); |
| 1433 |
self.depths.clear(); |
| 1434 |
for i in 0..(1u16 << u16::from(min_size)) { |
| 1435 |
self.inner.push(Link::base(i as u8)); |
| 1436 |
self.depths.push(1); |
| 1437 |
} |
| 1438 |
// Clear code. |
| 1439 |
self.inner.push(Link::base(0)); |
| 1440 |
self.depths.push(0); |
| 1441 |
// End code. |
| 1442 |
self.inner.push(Link::base(0)); |
| 1443 |
self.depths.push(0); |
| 1444 |
} |
| 1445 |
|
| 1446 |
fn at(&self, code: Code) -> &Link { |
| 1447 |
&self.inner[usize::from(code)] |
| 1448 |
} |
| 1449 |
|
| 1450 |
fn is_empty(&self) -> bool { |
| 1451 |
self.inner.is_empty() |
| 1452 |
} |
| 1453 |
|
| 1454 |
fn is_full(&self) -> bool { |
| 1455 |
self.inner.len() >= MAX_ENTRIES |
| 1456 |
} |
| 1457 |
|
| 1458 |
fn derive(&mut self, from: &DerivationBase, byte: u8) { |
| 1459 |
let link = from.derive(byte); |
| 1460 |
let depth = self.depths[usize::from(from.code)] + 1; |
| 1461 |
self.inner.push(link); |
| 1462 |
self.depths.push(depth); |
| 1463 |
} |
| 1464 |
|
| 1465 |
// Derive multiple codes in a row, where each base is guaranteed to already exist. |
| 1466 |
fn derive_burst(&mut self, from: &mut DerivationBase, burst: &[Code], first: &[u8]) { |
| 1467 |
let mut depth_of = from.code; |
| 1468 |
// Note that false data dependency we want to get rid of! |
| 1469 |
// TODO: this pushes into a Vec, maybe we can make this cleaner. |
| 1470 |
for &code in burst { |
| 1471 |
let depth = self.depths[usize::from(depth_of)] + 1; |
| 1472 |
self.depths.push(depth); |
| 1473 |
depth_of = code; |
| 1474 |
} |
| 1475 |
|
| 1476 |
// Llvm tends to be flaky with code layout for the case of requiring an allocation. It's |
| 1477 |
// not clear if that can occur in practice but it relies on iterator size hint.. |
| 1478 |
let extensions = burst.iter().zip(first); |
| 1479 |
self.inner.extend(extensions.map(|(&code, &first)| { |
| 1480 |
let link = from.derive(first); |
| 1481 |
from.code = code; |
| 1482 |
from.first = first; |
| 1483 |
link |
| 1484 |
})); |
| 1485 |
} |
| 1486 |
|
| 1487 |
fn reconstruct(&self, code: Code, out: &mut [u8]) -> u8 { |
| 1488 |
let mut code_iter = code; |
| 1489 |
let table = &self.inner[..=usize::from(code)]; |
| 1490 |
let first = table[usize::from(code)].first; |
| 1491 |
|
| 1492 |
let len = code_iter; |
| 1493 |
for ch in out.iter_mut().rev() { |
| 1494 |
//(code, cha) = self.table[k as usize]; |
| 1495 |
// Note: This could possibly be replaced with an unchecked array access if |
| 1496 |
// - value is asserted to be < self.next_code() in push |
| 1497 |
// - min_size is asserted to be < MAX_CODESIZE |
| 1498 |
let entry = &table[usize::from(code_iter)]; |
| 1499 |
code_iter = core::cmp::min(len, entry.prev); |
| 1500 |
*ch = entry.byte; |
| 1501 |
} |
| 1502 |
|
| 1503 |
first |
| 1504 |
} |
| 1505 |
} |
| 1506 |
|
| 1507 |
impl Link { |
| 1508 |
fn base(byte: u8) -> Self { |
| 1509 |
Link { |
| 1510 |
prev: 0, |
| 1511 |
byte, |
| 1512 |
first: byte, |
| 1513 |
} |
| 1514 |
} |
| 1515 |
} |
| 1516 |
|
| 1517 |
impl DerivationBase { |
| 1518 |
// TODO: this has self type to make it clear we might depend on the old in a future |
| 1519 |
// optimization. However, that has no practical purpose right now. |
| 1520 |
fn derive(&self, byte: u8) -> Link { |
| 1521 |
Link { |
| 1522 |
prev: self.code, |
| 1523 |
byte, |
| 1524 |
first: self.first, |
| 1525 |
} |
| 1526 |
} |
| 1527 |
} |
| 1528 |
|
| 1529 |
#[cfg(test)] |
| 1530 |
mod tests { |
| 1531 |
use crate::alloc::vec::Vec; |
| 1532 |
#[cfg(feature = "std")] |
| 1533 |
use crate::StreamBuf; |
| 1534 |
use crate::{decode::Decoder, BitOrder}; |
| 1535 |
|
| 1536 |
#[test] |
| 1537 |
fn invalid_code_size_low() { |
| 1538 |
let _ = Decoder::new(BitOrder::Msb, 0); |
| 1539 |
let _ = Decoder::new(BitOrder::Msb, 1); |
| 1540 |
} |
| 1541 |
|
| 1542 |
#[test] |
| 1543 |
#[should_panic] |
| 1544 |
fn invalid_code_size_high() { |
| 1545 |
let _ = Decoder::new(BitOrder::Msb, 14); |
| 1546 |
} |
| 1547 |
|
| 1548 |
fn make_encoded() -> Vec<u8> { |
| 1549 |
const FILE: &'static [u8] = include_bytes!(concat!( |
| 1550 |
env!("CARGO_MANIFEST_DIR"), |
| 1551 |
"/benches/binary-8-msb.lzw" |
| 1552 |
)); |
| 1553 |
return Vec::from(FILE); |
| 1554 |
} |
| 1555 |
|
| 1556 |
#[test] |
| 1557 |
#[cfg(feature = "std")] |
| 1558 |
fn into_stream_buffer_no_alloc() { |
| 1559 |
let encoded = make_encoded(); |
| 1560 |
let mut decoder = Decoder::new(BitOrder::Msb, 8); |
| 1561 |
|
| 1562 |
let mut output = vec![]; |
| 1563 |
let mut buffer = [0; 512]; |
| 1564 |
let mut istream = decoder.into_stream(&mut output); |
| 1565 |
istream.set_buffer(&mut buffer[..]); |
| 1566 |
istream.decode(&encoded[..]).status.unwrap(); |
| 1567 |
|
| 1568 |
match istream.buffer { |
| 1569 |
Some(StreamBuf::Borrowed(_)) => {} |
| 1570 |
None => panic!("Decoded without buffer??"), |
| 1571 |
Some(StreamBuf::Owned(_)) => panic!("Unexpected buffer allocation"), |
| 1572 |
} |
| 1573 |
} |
| 1574 |
|
| 1575 |
#[test] |
| 1576 |
#[cfg(feature = "std")] |
| 1577 |
fn into_stream_buffer_small_alloc() { |
| 1578 |
struct WriteTap<W: std::io::Write>(W); |
| 1579 |
const BUF_SIZE: usize = 512; |
| 1580 |
|
| 1581 |
impl<W: std::io::Write> std::io::Write for WriteTap<W> { |
| 1582 |
fn write(&mut self, buf: &[u8]) -> std::io::Result<usize> { |
| 1583 |
assert!(buf.len() <= BUF_SIZE); |
| 1584 |
self.0.write(buf) |
| 1585 |
} |
| 1586 |
fn flush(&mut self) -> std::io::Result<()> { |
| 1587 |
self.0.flush() |
| 1588 |
} |
| 1589 |
} |
| 1590 |
|
| 1591 |
let encoded = make_encoded(); |
| 1592 |
let mut decoder = Decoder::new(BitOrder::Msb, 8); |
| 1593 |
|
| 1594 |
let mut output = vec![]; |
| 1595 |
let mut istream = decoder.into_stream(WriteTap(&mut output)); |
| 1596 |
istream.set_buffer_size(512); |
| 1597 |
istream.decode(&encoded[..]).status.unwrap(); |
| 1598 |
|
| 1599 |
match istream.buffer { |
| 1600 |
Some(StreamBuf::Owned(vec)) => assert!(vec.len() <= BUF_SIZE), |
| 1601 |
Some(StreamBuf::Borrowed(_)) => panic!("Unexpected borrowed buffer, where from?"), |
| 1602 |
None => panic!("Decoded without buffer??"), |
| 1603 |
} |
| 1604 |
} |
| 1605 |
|
| 1606 |
#[test] |
| 1607 |
#[cfg(feature = "std")] |
| 1608 |
fn reset() { |
| 1609 |
let encoded = make_encoded(); |
| 1610 |
let mut decoder = Decoder::new(BitOrder::Msb, 8); |
| 1611 |
let mut reference = None; |
| 1612 |
|
| 1613 |
for _ in 0..2 { |
| 1614 |
let mut output = vec![]; |
| 1615 |
let mut buffer = [0; 512]; |
| 1616 |
let mut istream = decoder.into_stream(&mut output); |
| 1617 |
istream.set_buffer(&mut buffer[..]); |
| 1618 |
istream.decode_all(&encoded[..]).status.unwrap(); |
| 1619 |
|
| 1620 |
decoder.reset(); |
| 1621 |
if let Some(reference) = &reference { |
| 1622 |
assert_eq!(output, *reference); |
| 1623 |
} else { |
| 1624 |
reference = Some(output); |
| 1625 |
} |
| 1626 |
} |
| 1627 |
} |
| 1628 |
} |