use std::mem;
use std::ops::Range;
use crate::{
DecoderOptions,
block::{BLOCK_SIZE_MAX, BlockHeader, BlockType},
decode::{append_bytes, append_repeated, decode_compressed_block_into},
decode_out::DecodeOut,
dictionary::{DecoderDictionary, Dictionary, EncoderDictionary},
encode::{
CHECKSUM_SIZE, CompressionParameters, EncoderOptions, EntropyEncodeScratch,
FRAME_HEADER_MAX, LiteralsEncodingState, UPSTREAM_SPLIT_CHUNK_SIZE,
compression_parameters_for_options, encode_block_into_contiguous,
encode_block_into_prefixed_contiguous, seed_optimal_prices_from_first_block,
upstream_optimal_block_size, validate_options,
},
error::{Error, Result},
frame::{
FrameHeader, MAX_DECLARABLE_WINDOW_SIZE, ZstandardFrameHeader,
parse_frame_header_with_format, write_single_segment_header_with_dict,
write_windowed_header_with_content_size, write_windowed_header_with_dict,
},
literals::LiteralsState,
outbuf::OutBuf,
sequence::{OutputLimit, RepeatOffsets, SequenceEncodingState, SequenceTablesState},
window::{ContiguousBlockMatchState, LdmFrameState, PrefixMatchMode, PrefixedBlockMatchState},
xxhash::Xxh64State,
};
pub struct StreamingEncoder<'a> {
options: EncoderOptions,
dictionary: Option<EncoderDictionary<'a>>,
params: CompressionParameters,
buffered_input: Vec<u8>,
literals_state: LiteralsEncodingState,
repeat_offsets: RepeatOffsets,
sequence_tables: SequenceEncodingState,
scratch: EntropyEncodeScratch,
checksum: Option<Xxh64State>,
output: Vec<u8>,
output_pos: usize,
frame: Vec<u8>,
match_state: StreamingMatchState,
ldm: Option<LdmFrameState>,
savings: i64,
content_len: u64,
finished: bool,
}
enum StreamingMatchState {
Contiguous(ContiguousBlockMatchState),
Prefixed(PrefixedBlockMatchState),
}
fn new_match_state(
dictionary: Option<&EncoderDictionary<'_>>,
params: CompressionParameters,
frame_capacity: usize,
position_limit: usize,
) -> StreamingMatchState {
let Some(dictionary) = dictionary else {
return StreamingMatchState::Contiguous(
ContiguousBlockMatchState::new_with_position_limit(
frame_capacity,
position_limit,
params.match_finder,
),
);
};
let content = dictionary.as_inner().content();
if content.is_empty() {
return StreamingMatchState::Contiguous(
ContiguousBlockMatchState::new_with_position_limit(
frame_capacity,
position_limit,
params.match_finder,
),
);
}
StreamingMatchState::Prefixed(
PrefixedBlockMatchState::new_with_prepared_match_state_and_position_limit(
content,
frame_capacity,
position_limit,
params.match_finder,
if dictionary.as_inner().is_raw_content() {
PrefixMatchMode::ExtDict
} else {
PrefixMatchMode::DictMatchState
},
dictionary
.prepared_match_state(params.match_finder)
.as_deref(),
),
)
}
fn block_size_for(params: CompressionParameters, options: EncoderOptions) -> usize {
let window = history_limit_for(params)
.min(
options
.pledged_src_size
.unwrap_or(u64::MAX)
.try_into()
.unwrap_or(usize::MAX),
)
.max(1);
options.block_size.max(1 << 10).min(window)
}
fn history_limit_for(params: CompressionParameters) -> usize {
params.max_history_bytes.min(MAX_DECLARABLE_WINDOW_SIZE)
}
fn history_slack_for(params: CompressionParameters, options: EncoderOptions) -> usize {
let history_limit = history_limit_for(params);
let period = params.match_finder.rebase_period();
let unwidened = history_limit
.saturating_mul(2)
.saturating_add(block_size_for(params, options));
if period >= unwidened {
history_limit
} else {
history_limit.max(period)
}
}
fn frame_capacity_for(params: CompressionParameters, options: EncoderOptions) -> usize {
history_limit_for(params)
.saturating_add(history_slack_for(params, options))
.saturating_add(block_size_for(params, options))
}
fn match_position_limit_for(params: CompressionParameters, options: EncoderOptions) -> usize {
frame_capacity_for(params, options).min(
options
.pledged_src_size
.and_then(|size| usize::try_from(size).ok())
.unwrap_or(usize::MAX),
)
}
impl StreamingEncoder<'static> {
pub fn new(options: EncoderOptions) -> Result<Self> {
Self::with_prepared_dictionary(None, options)
}
}
impl<'a> StreamingEncoder<'a> {
pub const RECOMMENDED_INPUT_SIZE: usize = BLOCK_SIZE_MAX;
pub const RECOMMENDED_OUTPUT_SIZE: usize = FRAME_HEADER_MAX
+ (BLOCK_SIZE_MAX / UPSTREAM_SPLIT_CHUNK_SIZE) * BlockHeader::SIZE
+ BLOCK_SIZE_MAX
+ CHECKSUM_SIZE;
pub fn with_dict(dict: &'a [u8], options: EncoderOptions) -> Result<Self> {
let dictionary = EncoderDictionary::new(dict)?;
Self::with_prepared_dict(&dictionary, options)
}
pub fn with_prepared_dict(
dict: &EncoderDictionary<'a>,
options: EncoderOptions,
) -> Result<Self> {
Self::with_prepared_dictionary(Some(dict.clone()), options)
}
fn with_prepared_dictionary(
dictionary: Option<EncoderDictionary<'a>>,
options: EncoderOptions,
) -> Result<Self> {
validate_options(options)?;
let params = compression_parameters_for_options(
options,
None,
dictionary.as_ref().map(EncoderDictionary::as_inner),
);
let match_state = new_match_state(
dictionary.as_ref(),
params,
frame_capacity_for(params, options),
match_position_limit_for(params, options),
);
let mut encoder = Self {
options,
dictionary,
params,
buffered_input: Vec::with_capacity(block_size_for(params, options)),
literals_state: LiteralsEncodingState::default(),
repeat_offsets: RepeatOffsets::default(),
sequence_tables: SequenceEncodingState::default(),
scratch: EntropyEncodeScratch::default(),
checksum: None,
output: Vec::new(),
output_pos: 0,
frame: Vec::with_capacity(block_size_for(params, options)),
match_state,
ldm: None,
savings: 0,
content_len: 0,
finished: false,
};
encoder.reset_frame_state()?;
Ok(encoder)
}
pub fn push(&mut self, mut src: &[u8]) -> Result<()> {
if self.finished {
return Err(Error::InvalidParameter("cannot push after finish"));
}
if let Some(checksum) = self.checksum.as_mut() {
checksum.update(src);
}
self.content_len += src.len() as u64;
let target = self.push_target();
while !src.is_empty() {
debug_assert!(self.buffered_input.len() < target);
let take = (target - self.buffered_input.len()).min(src.len());
self.buffered_input.extend_from_slice(&src[..take]);
src = &src[take..];
if self.buffered_input.len() == target {
self.encode_buffered_chunk()?;
}
}
Ok(())
}
fn push_target(&self) -> usize {
let block_size = self.block_size();
block_size + usize::from(self.options.pledged_src_size == Some(block_size as u64))
}
fn encode_buffered_chunk(&mut self) -> Result<()> {
let n = self.next_block_size();
if std::env::var_os("ZSTANDARD_TRACE_CHUNK").is_some() {
eprintln!(
"chunk: buffered={} split={} savings={}",
self.buffered_input.len(),
n,
self.savings
);
}
self.encode_buffered_block(n, false)?;
if !self.buffered_input.is_empty() {
if std::env::var_os("ZSTANDARD_TRACE_CHUNK").is_some() {
eprintln!(" tail: {}", self.buffered_input.len());
}
self.encode_buffered_block(self.buffered_input.len(), false)?;
}
Ok(())
}
fn next_block_size(&self) -> usize {
let available = self.buffered_input.len();
if self.params.upstream_cparams.strategy.is_optimal() {
return available.min(self.block_size());
}
upstream_optimal_block_size(
&self.buffered_input,
0,
self.block_size(),
self.params.upstream_cparams.strategy,
self.savings,
)
.clamp(1, available)
}
pub fn flush(&mut self) -> Result<()> {
if self.finished {
return Err(Error::InvalidParameter("cannot flush after finish"));
}
if self.buffered_input.is_empty() {
return Ok(());
}
self.encode_buffered_block(self.buffered_input.len(), false)
}
pub fn finish(&mut self) -> Result<()> {
if self.finished {
return Ok(());
}
if let Some(pledged) = self.options.pledged_src_size {
if pledged != self.content_len {
return Err(Error::InvalidParameter(
"stream carried a different number of bytes than pledged_src_size",
));
}
}
self.encode_buffered_block(self.buffered_input.len(), true)?;
if let Some(checksum) = self.checksum.as_ref() {
self.output
.extend_from_slice(&(checksum.digest() as u32).to_le_bytes());
}
self.finished = true;
Ok(())
}
pub fn reset(&mut self) -> Result<()> {
if !self.finished {
return Err(Error::InvalidParameter("cannot reset before finish"));
}
self.reset_frame_state()
}
pub fn take_output(&mut self) -> Vec<u8> {
if self.output_pos == 0 {
return mem::take(&mut self.output);
}
let out = self.output[self.output_pos..].to_vec();
self.output.clear();
self.output_pos = 0;
out
}
pub fn read(&mut self, dst: &mut [u8]) -> usize {
let count = dst.len().min(self.pending_output_len());
if count == 0 {
return 0;
}
dst[..count].copy_from_slice(&self.output[self.output_pos..self.output_pos + count]);
self.output_pos += count;
self.compact_output();
count
}
pub fn pending_output(&self) -> &[u8] {
&self.output[self.output_pos..]
}
pub fn consume_output(&mut self, count: usize) {
assert!(
count <= self.pending_output_len(),
"consumed {count} bytes of pending output but only {} are pending",
self.pending_output_len()
);
self.output_pos += count;
self.compact_output();
}
fn compact_output(&mut self) {
if self.output_pos == 0 {
return;
}
if self.output_pos == self.output.len() {
self.output.clear();
self.output_pos = 0;
return;
}
if self.output_pos * 2 >= self.output.len() {
self.output.drain(..self.output_pos);
self.output_pos = 0;
}
}
pub fn pending_output_len(&self) -> usize {
self.output.len() - self.output_pos
}
pub fn is_finished(&self) -> bool {
self.finished
}
fn encode_buffered_block(&mut self, take: usize, last_block: bool) -> Result<()> {
let history_limit = self.history_limit();
if self.frame.len()
> history_limit.saturating_add(history_slack_for(self.params, self.options))
{
self.compact_frame(history_limit);
}
let block_start = self.frame.len();
self.frame.extend_from_slice(&self.buffered_input[..take]);
self.buffered_input.drain(..take);
let block_end = self.frame.len();
let mut params = self.params;
params.max_history_bytes = history_limit;
if block_start == 0
&& let StreamingMatchState::Contiguous(match_state) = &mut self.match_state
{
seed_optimal_prices_from_first_block(
&mut self.scratch,
&self.frame[..block_end],
self.repeat_offsets,
params,
match_state,
self.ldm.as_mut(),
)?;
}
let output_before = self.output.len();
let result = match &mut self.match_state {
StreamingMatchState::Contiguous(match_state) => encode_block_into_contiguous(
&mut OutBuf::growable(&mut self.output),
&self.frame,
block_start,
block_end,
match_state,
&mut self.literals_state,
last_block,
&mut self.repeat_offsets,
&mut self.sequence_tables,
&mut self.scratch,
params,
self.ldm.as_mut(),
),
StreamingMatchState::Prefixed(match_state) => encode_block_into_prefixed_contiguous(
&mut OutBuf::growable(&mut self.output),
self.dictionary
.as_ref()
.map_or(&[][..], |dictionary| dictionary.as_inner().content()),
&self.frame,
block_start,
block_end,
match_state,
&mut self.literals_state,
last_block,
&mut self.repeat_offsets,
&mut self.sequence_tables,
&mut self.scratch,
params,
self.ldm.as_mut(),
),
};
result?;
self.savings += take as i64 - (self.output.len() - output_before) as i64;
Ok(())
}
fn compact_frame(&mut self, history_limit: usize) {
let live_end = self.frame.len();
let dropped = self.aligned_drop(live_end - history_limit);
self.frame.drain(..dropped);
let retained = self.frame.len();
if let Some(ldm) = self.ldm.as_mut() {
ldm.shift_positions(dropped);
}
self.scratch.shift_frame_positions(dropped);
if let StreamingMatchState::Contiguous(match_state) = &mut self.match_state {
if match_state.shift_positions(dropped, live_end) {
return;
}
}
let reset_in_place = match &mut self.match_state {
StreamingMatchState::Contiguous(match_state) => match_state.reset_if_compatible(
self.params.match_finder,
match_position_limit_for(self.params, self.options),
),
StreamingMatchState::Prefixed(_) => false,
};
if !reset_in_place {
self.match_state = StreamingMatchState::Contiguous(
ContiguousBlockMatchState::new_with_position_limit(
self.frame_capacity(),
match_position_limit_for(self.params, self.options),
self.params.match_finder,
),
);
}
if self.params.match_finder.parser_strategy.is_binary_tree() {
return;
}
if let StreamingMatchState::Contiguous(match_state) = &mut self.match_state {
match_state.insert_range(&self.frame, 0, retained);
}
}
fn aligned_drop(&self, want: usize) -> usize {
let period = self.params.match_finder.rebase_period();
debug_assert!(
match &self.match_state {
StreamingMatchState::Contiguous(state) => state.rebase_period() == period,
StreamingMatchState::Prefixed(_) => true,
},
"the buffer was sized around a cycle the finder does not have"
);
if period > want {
return want;
}
want - want % period
}
fn frame_capacity(&self) -> usize {
frame_capacity_for(self.params, self.options)
}
fn history_limit(&self) -> usize {
history_limit_for(self.params)
}
fn block_size(&self) -> usize {
block_size_for(self.params, self.options)
}
fn frame_window_size(&self) -> usize {
self.history_limit()
}
fn reset_frame_state(&mut self) -> Result<()> {
self.buffered_input.clear();
self.frame.clear();
self.savings = 0;
self.match_state = new_match_state(
self.dictionary.as_ref(),
self.params,
self.frame_capacity(),
match_position_limit_for(self.params, self.options),
);
self.ldm = self.params.ldm.map(|ldm| {
let mut state = LdmFrameState::new(ldm, self.history_limit());
if let Some(dictionary) = self.dictionary.as_ref() {
state.load_dictionary(dictionary.as_inner().content());
}
state
});
self.sequence_tables = self
.dictionary
.as_ref()
.map_or_else(SequenceEncodingState::default, |dictionary| {
dictionary.as_inner().sequence_encoding_state()
});
self.repeat_offsets = self
.dictionary
.as_ref()
.map_or_else(RepeatOffsets::default, |dictionary| {
dictionary.as_inner().repeat_offsets()
});
self.literals_state = LiteralsEncodingState::new(
self.dictionary.as_ref().map(EncoderDictionary::as_inner),
self.params,
);
self.checksum = self.options.checksum.then(|| Xxh64State::new(0));
self.scratch.clear_frame_parser_state();
self.content_len = 0;
self.finished = false;
let frame_window_size = self.frame_window_size() as u64;
let dictionary_id = self
.options
.write_dict_id
.then(|| {
self.dictionary
.as_ref()
.and_then(|dictionary| dictionary.as_inner().frame_dictionary_id())
})
.flatten();
let out = &mut OutBuf::growable(&mut self.output);
match self
.options
.pledged_src_size
.filter(|_| self.options.write_content_size)
{
Some(pledged) if pledged <= frame_window_size => {
write_single_segment_header_with_dict(
out,
pledged,
self.options.checksum,
dictionary_id,
self.options.format,
);
}
Some(pledged) => write_windowed_header_with_content_size(
out,
frame_window_size,
pledged,
self.options.checksum,
dictionary_id,
self.options.format,
)?,
None => write_windowed_header_with_dict(
out,
frame_window_size,
self.options.checksum,
dictionary_id,
self.options.format,
)?,
}
Ok(())
}
}
impl Default for StreamingEncoder<'static> {
fn default() -> Self {
Self::new(EncoderOptions::default()).expect("default encoder options must be valid")
}
}
pub struct StreamingDecoder<'a> {
options: DecoderOptions,
dictionary: Option<Dictionary<'a>>,
input: Vec<u8>,
input_pos: usize,
output: Vec<u8>,
output_pos: usize,
literals_scratch: Vec<u8>,
state: DecoderState,
current_frame: Option<Box<FrameDecodeState>>,
spare_frame: Option<Box<FrameDecodeState>>,
total_output_size: u64,
received_input: bool,
finished_input: bool,
input_dropped: usize,
decoded_a_frame: bool,
}
impl StreamingDecoder<'static> {
pub fn new(options: DecoderOptions) -> Self {
Self::with_parsed_dictionary(None, options)
}
}
impl Default for StreamingDecoder<'static> {
fn default() -> Self {
Self::new(DecoderOptions::default())
}
}
impl<'a> StreamingDecoder<'a> {
pub const RECOMMENDED_INPUT_SIZE: usize = BLOCK_SIZE_MAX + BlockHeader::SIZE;
pub const RECOMMENDED_OUTPUT_SIZE: usize = BLOCK_SIZE_MAX;
pub fn with_dict(dict: &'a [u8], options: DecoderOptions) -> Result<Self> {
let dictionary = DecoderDictionary::new(dict)?;
Ok(Self::with_prepared_dict(&dictionary, options))
}
pub fn with_prepared_dict(dict: &DecoderDictionary<'a>, options: DecoderOptions) -> Self {
Self::with_parsed_dictionary(Some(dict.as_inner().clone()), options)
}
pub fn push(&mut self, src: &[u8]) -> Result<()> {
if self.finished_input {
return Err(Error::InvalidParameter("cannot push after finish"));
}
self.received_input |= !src.is_empty();
self.input.extend_from_slice(src);
self.process()
}
pub fn finish(&mut self) -> Result<()> {
if self.finished_input {
return self.finish_status();
}
self.finished_input = true;
self.process()?;
self.finish_status()
}
pub fn reset(&mut self) -> Result<()> {
self.finish_status()?;
self.reset_state();
Ok(())
}
pub fn read(&mut self, dst: &mut [u8]) -> usize {
let count = dst.len().min(self.pending_output_len());
if count == 0 {
return 0;
}
dst[..count].copy_from_slice(&self.pending_output()[..count]);
self.consume_output(count);
count
}
pub fn take_output(&mut self) -> Vec<u8> {
if self.output_pos == 0 && self.current_frame.is_none() {
return mem::take(&mut self.output);
}
let out = self.output[self.output_pos..].to_vec();
self.output_pos = self.output.len();
self.compact_output();
out
}
pub fn pending_output_len(&self) -> usize {
self.output.len().saturating_sub(self.output_pos)
}
pub(crate) fn pending_output(&self) -> &[u8] {
&self.output[self.output_pos..]
}
pub(crate) fn consume_output(&mut self, count: usize) {
assert!(
count <= self.pending_output_len(),
"consumed {count} bytes of pending output but only {} are pending",
self.pending_output_len()
);
self.output_pos += count;
self.compact_output();
}
pub fn unconsumed_input(&self) -> &[u8] {
&self.input[self.input_pos..]
}
pub fn input_consumed(&self) -> usize {
self.stream_input_pos()
}
#[cfg(any(test, feature = "internal-trace"))]
#[doc(hidden)]
pub fn retained_output_len(&self) -> usize {
self.output.len()
}
pub fn is_finished(&self) -> bool {
self.finished_input
&& matches!(self.state, DecoderState::FrameHeader)
&& self.current_frame.is_none()
&& self.input_pos == self.input.len()
}
fn with_parsed_dictionary(dictionary: Option<Dictionary<'a>>, options: DecoderOptions) -> Self {
let mut decoder = Self {
options,
dictionary,
input: Vec::new(),
input_pos: 0,
output: Vec::new(),
output_pos: 0,
literals_scratch: Vec::new(),
state: DecoderState::FrameHeader,
current_frame: None,
spare_frame: None,
total_output_size: 0,
received_input: false,
finished_input: false,
input_dropped: 0,
decoded_a_frame: false,
};
decoder.reset_state();
decoder
}
fn process(&mut self) -> Result<()> {
loop {
let progress = match self.state {
DecoderState::FrameHeader => self.process_frame_header()?,
DecoderState::Skippable { .. } => self.process_skippable_frame(),
DecoderState::BlockHeader => self.process_block_header()?,
DecoderState::BlockPayload { .. } => self.process_block_payload()?,
DecoderState::FrameChecksum => self.process_frame_checksum()?,
};
if !progress {
break;
}
self.compact_input();
}
Ok(())
}
fn process_frame_header(&mut self) -> Result<bool> {
if self.input_pos == self.input.len() {
return Ok(false);
}
if self.options.single_frame && self.decoded_a_frame {
return Err(Error::TrailingInput {
offset: self.stream_input_pos(),
});
}
match parse_frame_header_with_format(&self.input[self.input_pos..], self.options.format) {
Ok(FrameHeader::Skippable(skippable)) => {
if self.options.single_frame {
return Err(Error::TrailingInput {
offset: self.stream_input_pos(),
});
}
self.input_pos += skippable.header_size;
self.state = DecoderState::Skippable {
remaining: skippable.size as usize,
};
Ok(true)
}
Ok(FrameHeader::Zstandard(header)) => {
self.input_pos += header.header_size;
self.start_frame(header)?;
self.state = DecoderState::BlockHeader;
Ok(true)
}
Err(Error::UnexpectedEof) => Ok(false),
Err(err) => Err(err),
}
}
fn process_skippable_frame(&mut self) -> bool {
let DecoderState::Skippable { remaining } = &mut self.state else {
unreachable!();
};
let available = self.input.len() - self.input_pos;
let consumed = available.min(*remaining);
self.input_pos += consumed;
*remaining -= consumed;
if *remaining == 0 {
self.state = DecoderState::FrameHeader;
}
consumed != 0
}
fn process_block_header(&mut self) -> Result<bool> {
if self.input.len() - self.input_pos < BlockHeader::SIZE {
return Ok(false);
}
let header =
BlockHeader::parse(&self.input[self.input_pos..self.input_pos + BlockHeader::SIZE])?;
self.input_pos += BlockHeader::SIZE;
self.state = DecoderState::BlockPayload { header };
Ok(true)
}
fn process_block_payload(&mut self) -> Result<bool> {
let DecoderState::BlockPayload { header } = self.state else {
unreachable!();
};
let payload_size = header.payload_size();
if self.input.len() - self.input_pos < payload_size {
self.state = DecoderState::BlockPayload { header };
return Ok(false);
}
let payload = self.input_pos..self.input_pos + payload_size;
self.input_pos += payload_size;
self.decode_block(header, payload)?;
let checksum = self
.current_frame
.as_ref()
.expect("compressed block requires an active frame")
.header
.checksum;
self.state = if header.last_block {
if checksum {
DecoderState::FrameChecksum
} else {
self.finish_frame()?;
DecoderState::FrameHeader
}
} else {
DecoderState::BlockHeader
};
Ok(true)
}
fn process_frame_checksum(&mut self) -> Result<bool> {
if self.input.len() - self.input_pos < 4 {
return Ok(false);
}
let expected = u32::from_le_bytes([
self.input[self.input_pos],
self.input[self.input_pos + 1],
self.input[self.input_pos + 2],
self.input[self.input_pos + 3],
]);
self.input_pos += 4;
let frame = self.current_frame.as_ref().ok_or(Error::Generic)?;
if self.options.verify_checksum {
let actual = frame
.checksum
.as_ref()
.ok_or(Error::Corruption("missing frame checksum state"))?
.digest() as u32;
if actual != expected {
return Err(Error::ChecksumMismatch { expected, actual });
}
}
self.finish_frame()?;
self.state = DecoderState::FrameHeader;
Ok(true)
}
fn start_frame(&mut self, header: ZstandardFrameHeader) -> Result<()> {
self.compact_between_frames();
let dictionary = match (self.dictionary.as_ref(), header.dictionary_id) {
(None, Some(dictionary_id)) => {
return Err(Error::DictionaryRequired(Some(dictionary_id)));
}
(Some(dictionary), Some(dictionary_id)) if dictionary.id() != dictionary_id => {
return Err(Error::DictionaryMismatch {
expected: dictionary_id,
actual: dictionary.id(),
});
}
(dictionary, _) => dictionary,
};
if let Some(max_window_size) = self.options.max_window_size {
if header.window_size > max_window_size {
return Err(Error::WindowSizeTooLarge {
window_size: header.window_size,
max_window_size,
});
}
}
if let Some(content_size) = header.content_size {
ensure_total_size_limit(
self.total_output_size,
content_size,
self.options.max_output_size,
)?;
}
let checksum = header.checksum;
let window_size = usize::try_from(header.window_size).unwrap_or(usize::MAX);
let frame = FrameDecodeState {
literals_state: dictionary
.map_or_else(LiteralsState::default, Dictionary::literals_state),
sequence_tables: dictionary
.map_or_else(SequenceTablesState::default, Dictionary::sequence_tables),
repeat_offsets: dictionary
.map_or_else(RepeatOffsets::default, Dictionary::repeat_offsets),
checksum: checksum.then(|| Xxh64State::new(0)),
frame_output_size: 0,
window_size,
frame_start: self.output.len(),
header,
};
self.current_frame = Some(match self.spare_frame.take() {
Some(mut recycled) => {
*recycled = frame;
recycled
}
None => Box::new(frame),
});
Ok(())
}
fn decode_block(
&mut self,
block_header: BlockHeader,
payload_range: Range<usize>,
) -> Result<()> {
let block_start = self.output.len();
let released = self.total_output_size.saturating_sub(block_start as u64);
let limit = OutputLimit::after(released, self.options.max_output_size);
let payload = &self.input[payload_range];
let dictionary_content = self.dictionary.as_ref().map(Dictionary::content);
let frame = self.current_frame.as_mut().ok_or(Error::Generic)?;
let oversized = block_header.block_size > frame.header.block_size_max;
match block_header.block_type {
BlockType::Raw => {
if oversized {
return Err(Error::Corruption(
"block size exceeds frame block size limit",
));
}
append_bytes(&mut DecodeOut::growable(&mut self.output), payload, limit)?
}
BlockType::Rle => {
if oversized {
return Err(Error::Corruption(
"block size exceeds frame block size limit",
));
}
append_repeated(
&mut DecodeOut::growable(&mut self.output),
*payload.first().ok_or(Error::UnexpectedEof)?,
block_header.block_size as usize,
limit,
)?
}
BlockType::Compressed => decode_compressed_block_into(
payload,
frame.header.block_size_max as usize,
frame.frame_start,
frame.window_size,
dictionary_content,
&mut frame.literals_state,
&mut frame.sequence_tables,
&mut frame.repeat_offsets,
&mut self.literals_scratch,
&mut DecodeOut::growable(&mut self.output),
limit,
)?,
}
let produced = self.output.len() - block_start;
frame.absorb_block_output(&self.output[block_start..]);
self.total_output_size += produced as u64;
Ok(())
}
fn finish_frame(&mut self) -> Result<()> {
let frame = self.current_frame.take().ok_or(Error::Generic)?;
if let Some(expected_size) = frame.header.content_size {
if frame.frame_output_size != expected_size {
return Err(Error::ContentSizeMismatch {
expected: expected_size,
actual: frame.frame_output_size,
});
}
}
self.decoded_a_frame = true;
self.spare_frame = Some(frame);
Ok(())
}
fn finish_status(&self) -> Result<()> {
if !self.received_input {
return Err(Error::UnexpectedEof);
}
if self.current_frame.is_some() || !matches!(self.state, DecoderState::FrameHeader) {
return Err(Error::UnexpectedEof);
}
if self.input_pos != self.input.len() {
return Err(Error::UnexpectedEof);
}
Ok(())
}
fn compact_input(&mut self) {
if self.input_pos == 0 {
return;
}
if self.input_pos == self.input.len() {
self.input_dropped += self.input_pos;
self.input.clear();
self.input_pos = 0;
return;
}
if self.input_pos >= 4096 || self.input_pos * 2 >= self.input.len() {
self.input_dropped += self.input_pos;
self.input.drain(..self.input_pos);
self.input_pos = 0;
}
}
fn stream_input_pos(&self) -> usize {
self.input_dropped + self.input_pos
}
fn compact_output(&mut self) {
let retain = self.retain_for_matches();
let droppable = self
.output_pos
.min(self.output.len().saturating_sub(retain));
if droppable == 0 {
return;
}
if droppable == self.output.len() {
self.output.clear();
self.output_pos = 0;
self.release_history(droppable);
return;
}
if self.current_frame.is_none() {
return;
}
if droppable * 2 >= self.output.len() {
self.output.drain(..droppable);
self.output_pos -= droppable;
self.release_history(droppable);
}
}
fn compact_between_frames(&mut self) {
debug_assert!(
self.current_frame.is_none(),
"a frame is opening while another is still current"
);
if self.output_pos != 0 && self.output_pos * 2 >= self.output.len() {
self.output.drain(..self.output_pos);
self.output_pos = 0;
}
}
fn retain_for_matches(&self) -> usize {
self.current_frame
.as_ref()
.map_or(0, |frame| frame.window_size.saturating_add(1))
}
fn release_history(&mut self, dropped: usize) {
let retained = self.output.len();
if let Some(frame) = self.current_frame.as_mut() {
frame.frame_start = frame.frame_start.saturating_sub(dropped);
debug_assert!(
frame.frame_start <= retained,
"compaction left the frame starting past the end of the buffer"
);
let held = (retained - frame.frame_start) as u64;
debug_assert!(
held == frame.frame_output_size || held > frame.window_size as u64,
"compaction left {held} bytes of a {}-byte frame, inside its {}-byte window",
frame.frame_output_size,
frame.window_size
);
}
}
fn reset_state(&mut self) {
self.input.clear();
self.input_pos = 0;
self.state = DecoderState::FrameHeader;
self.spare_frame = self.current_frame.take().or(self.spare_frame.take());
self.total_output_size = 0;
self.received_input = false;
self.finished_input = false;
self.input_dropped = 0;
self.decoded_a_frame = false;
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum DecoderState {
FrameHeader,
Skippable { remaining: usize },
BlockHeader,
BlockPayload { header: BlockHeader },
FrameChecksum,
}
struct FrameDecodeState {
header: ZstandardFrameHeader,
literals_state: LiteralsState,
sequence_tables: SequenceTablesState,
repeat_offsets: RepeatOffsets,
checksum: Option<Xxh64State>,
frame_output_size: u64,
window_size: usize,
frame_start: usize,
}
impl FrameDecodeState {
fn absorb_block_output(&mut self, produced: &[u8]) {
if let Some(checksum) = self.checksum.as_mut() {
checksum.update(produced);
}
self.frame_output_size += produced.len() as u64;
}
}
fn ensure_total_size_limit(
current_output_size: u64,
content_size: u64,
max_output_size: Option<usize>,
) -> Result<()> {
if let Some(limit) = max_output_size {
let total = current_output_size
.checked_add(content_size)
.ok_or(Error::OutputSizeOverflow)?;
if total > limit as u64 {
return Err(Error::OutputSizeTooLarge {
output_size: total,
max_output_size: limit,
});
}
}
Ok(())
}
impl std::fmt::Debug for StreamingEncoder<'_> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("StreamingEncoder")
.field("compression_level", &self.options.compression_level)
.field("block_size", &self.options.block_size)
.field("has_dictionary", &self.dictionary.is_some())
.field("buffered_input_len", &self.buffered_input.len())
.field("pending_output_len", &self.pending_output_len())
.field("finished", &self.finished)
.finish_non_exhaustive()
}
}
impl std::fmt::Debug for StreamingDecoder<'_> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("StreamingDecoder")
.field("pending_output_len", &self.pending_output_len())
.field("finished", &self.is_finished())
.finish_non_exhaustive()
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::CompressionLevel;
fn xorshift(state: &mut u64) -> u64 {
*state ^= *state << 13;
*state ^= *state >> 7;
*state ^= *state << 17;
*state
}
fn repetitive_body(len: usize) -> Vec<u8> {
const LINES: [&str; 5] = [
"the quick brown fox jumps over the lazy dog\n",
"pack my box with five dozen liquor jugs\n",
"how vexingly quick daft zebras jump\n",
"sphinx of black quartz judge my vow\n",
"the five boxing wizards jump quickly\n",
];
let mut out = Vec::with_capacity(len);
let mut state = 0x2545_f491_4f6c_dd1du64;
let mut n = 0usize;
while out.len() < len {
out.extend_from_slice(LINES[n % LINES.len()].as_bytes());
if n.is_multiple_of(11) {
for _ in 0..24 {
out.push((xorshift(&mut state) & 0xff) as u8);
}
}
n += 1;
}
out.truncate(len);
out
}
#[test]
fn streaming_decode_drops_history_but_never_what_a_match_needs() {
let body = repetitive_body(4_000_000);
let options =
EncoderOptions::default().with_compression_level(CompressionLevel::try_new(1).unwrap());
let mut encoder = StreamingEncoder::new(options).unwrap();
let mut compressed = Vec::new();
for piece in body.chunks(7_919) {
encoder.push(piece).unwrap();
compressed.extend_from_slice(&encoder.take_output());
}
encoder.finish().unwrap();
compressed.extend_from_slice(&encoder.take_output());
let FrameHeader::Zstandard(header) =
parse_frame_header_with_format(&compressed, crate::frame::Format::Zstd1).unwrap()
else {
panic!("expected a Zstandard frame");
};
let window = usize::try_from(header.window_size).unwrap();
assert!(
window * 4 <= body.len(),
"the frame declares a {window}-byte window, too wide against a {}-byte body for \
anything to become droppable",
body.len()
);
for drain_every in [1usize, 3, 16] {
let mut decoder = StreamingDecoder::new(DecoderOptions::default());
let mut decoded = Vec::new();
let mut peak_retained = 0usize;
for (index, piece) in compressed.chunks(4_093).enumerate() {
decoder.push(piece).unwrap();
if index % drain_every == 0 {
decoded.extend_from_slice(&decoder.take_output());
}
peak_retained = peak_retained.max(decoder.retained_output_len());
}
decoder.finish().unwrap();
decoded.extend_from_slice(&decoder.take_output());
assert_eq!(decoded, body, "drain_every {drain_every}");
assert!(
peak_retained > window,
"drain_every {drain_every}: held only {peak_retained} bytes, which is inside \
the {window}-byte window a match may still reach into"
);
let undrained =
(drain_every as u64 * 4_093 * body.len() as u64 / compressed.len() as u64) as usize;
let ceiling = 2 * (window + 1) + header.block_size_max as usize + undrained;
assert!(
peak_retained <= ceiling,
"drain_every {drain_every}: held {peak_retained} bytes against a \
{window}-byte window, so history was never dropped"
);
}
}
#[test]
fn streaming_decode_compacts_across_a_frame_boundary() {
let first_body = repetitive_body(2_000_000);
let second_body = repetitive_body(50_000);
let mut stream = Vec::new();
for body in [&first_body, &second_body] {
let options = EncoderOptions::default()
.with_compression_level(CompressionLevel::try_new(1).unwrap());
let mut encoder = StreamingEncoder::new(options).unwrap();
for piece in body.chunks(7_919) {
encoder.push(piece).unwrap();
stream.extend_from_slice(&encoder.take_output());
}
encoder.finish().unwrap();
stream.extend_from_slice(&encoder.take_output());
}
let mut decoder = StreamingDecoder::new(DecoderOptions::default());
let mut decoded = Vec::new();
for piece in stream.chunks(4_093) {
decoder.push(piece).unwrap();
decoded.extend_from_slice(&decoder.take_output());
}
decoder.finish().unwrap();
decoded.extend_from_slice(&decoder.take_output());
let mut expected = first_body;
expected.extend_from_slice(&second_body);
assert_eq!(decoded, expected);
}
#[test]
fn concatenated_frames_do_not_accumulate_drained_output() {
const FRAMES: usize = 200;
const UNREAD: usize = 8;
let body = repetitive_body(4_096);
let frame = crate::encode_all(&body).unwrap();
let mut decoder = StreamingDecoder::new(DecoderOptions::default());
let mut decoded = Vec::new();
let mut sink = vec![0u8; body.len() - UNREAD];
let mut peak_retained = 0usize;
for _ in 0..FRAMES {
decoder.push(&frame).unwrap();
let taken = decoder.read(&mut sink);
decoded.extend_from_slice(&sink[..taken]);
peak_retained = peak_retained.max(decoder.retained_output_len());
}
decoder.finish().unwrap();
decoded.extend_from_slice(&decoder.take_output());
let mut expected = Vec::new();
for _ in 0..FRAMES {
expected.extend_from_slice(&body);
}
assert_eq!(decoded, expected);
let ceiling = 2 * (body.len() + UNREAD);
assert!(
peak_retained <= ceiling,
"held {peak_retained} bytes against a {ceiling}-byte ceiling, over {} decoded: \
the drained prefix is accumulating instead of being reclaimed",
expected.len()
);
}
#[test]
fn streaming_decode_without_draining_retains_everything() {
let body = repetitive_body(300_000);
let options =
EncoderOptions::default().with_compression_level(CompressionLevel::try_new(9).unwrap());
let mut encoder = StreamingEncoder::new(options).unwrap();
encoder.params.max_history_bytes = 16 * 1024;
let mut compressed = Vec::new();
for piece in body.chunks(4_099) {
encoder.push(piece).unwrap();
compressed.extend_from_slice(&encoder.take_output());
}
encoder.finish().unwrap();
compressed.extend_from_slice(&encoder.take_output());
let mut decoder = StreamingDecoder::new(DecoderOptions::default());
for piece in compressed.chunks(1_021) {
decoder.push(piece).unwrap();
}
decoder.finish().unwrap();
assert_eq!(decoder.retained_output_len(), body.len());
assert_eq!(decoder.take_output(), body);
}
#[test]
fn compaction_preserves_history_across_every_parser_strategy() {
let body = repetitive_body(400_000);
for level in [1, 3, 5, 7, 9, 12, 13, 15, 17, 19, 22] {
let options = EncoderOptions::default()
.with_compression_level(CompressionLevel::try_new(level).unwrap());
let mut encoder = StreamingEncoder::new(options).unwrap();
encoder.params.max_history_bytes = 32 * 1024;
let history_limit = encoder.history_limit();
let bound = encoder.frame_capacity();
let mut compressed = Vec::new();
for piece in body.chunks(7_919) {
encoder.push(piece).unwrap();
compressed.extend_from_slice(&encoder.take_output());
assert!(
encoder.frame.len() <= bound,
"L{level}: frame grew to {} against a documented bound of {bound}",
encoder.frame.len(),
);
}
encoder.finish().unwrap();
compressed.extend_from_slice(&encoder.take_output());
assert!(
body.len() > 4 * history_limit,
"L{level}: the body must outrun the window several times over \
or this never compacts at all",
);
assert_eq!(
crate::decode_all(&compressed).unwrap(),
body,
"L{level}: round-trip through a compacted window",
);
assert!(
compressed.len() * 8 < body.len(),
"L{level}: compacting cost the parser its history: {} bytes from {}",
compressed.len(),
body.len(),
);
}
}
#[test]
fn compaction_preserves_history_with_a_dictionary() {
let dictionary = repetitive_body(24_000);
let body = repetitive_body(400_000);
for level in [1, 5, 9, 13, 19] {
let options = EncoderOptions::default()
.with_compression_level(CompressionLevel::try_new(level).unwrap());
let mut encoder = StreamingEncoder::with_dict(&dictionary, options).unwrap();
encoder.params.max_history_bytes = 32 * 1024;
let bound = encoder.frame_capacity();
let mut compressed = Vec::new();
for piece in body.chunks(7_919) {
encoder.push(piece).unwrap();
compressed.extend_from_slice(&encoder.take_output());
assert!(
encoder.frame.len() <= bound,
"L{level}: frame exceeded {bound}"
);
}
encoder.finish().unwrap();
compressed.extend_from_slice(&encoder.take_output());
assert_eq!(
crate::decode_all_with_dict(&compressed, &dictionary).unwrap(),
body,
"L{level}: round-trip through a compacted window with a dictionary",
);
assert!(
compressed.len() * 8 < body.len(),
"L{level}: compacting cost the parser its history: {} bytes from {}",
compressed.len(),
body.len(),
);
}
}
}