Internal implementation of Zstandard compression and decompression. More...

Classes
struct	decoder_state
	Persistent entropy tables and repeat offsets shared by compressed blocks. More...

struct	encoded_length
	Encoded sequence length code and its additional-bit payload. More...

class	forward_bit_reader
	Read a byte-aligned, forward, least-significant-bit-first bitstream. More...

struct	fse_entry
	One state transition in an FSE decoding table. More...

struct	fse_table
	Native FSE decoding table indexed by the current decoder state. More...

struct	huffman_description_result
	A parsed Huffman tree description and its encoded byte length. More...

struct	huffman_node
	One node in a native canonical Huffman decoding tree. More...

struct	huffman_table
	Canonical Huffman decoding tree retained for treeless literal blocks. More...

struct	length_code_entry
	Baseline and additional-bit count selected by a sequence length code. More...

struct	literals_result
	Decoded literals and the number of compressed-block bytes they occupy. More...

struct	normalized_probability_result
	Parsed normalized FSE probabilities and their encoded byte length. More...

class	reverse_bit_reader
	Read a Zstandard entropy bitstream from its end toward its beginning. More...

class	xxhash64_accumulator
	Incremental XXH64 accumulator for streamed Zstandard checksums. More...

Functions
std::uint64_t	rotate_left (std::uint64_t value, std::uint8_t count) noexcept
	Rotates a 64-bit value left without compiler-specific intrinsics.

std::uint32_t	read_word32 (std::span< std::byte const > input, std::size_t offset) noexcept
	Reads an unchecked little-endian 32-bit word.

std::uint64_t	read_word64 (std::span< std::byte const > input, std::size_t offset) noexcept
	Reads an unchecked little-endian 64-bit word.

std::uint64_t	xxhash64 (std::span< std::byte const > input, std::uint64_t seed=0U) noexcept
	Computes XXH64 as required by the Zstandard frame checksum.

void	append_integer (std::vector< std::byte > &output, std::uint64_t value, std::uint8_t byte_count)
	Appends a little-endian integer with a selected byte count.

std::uint64_t	read_integer (std::span< std::byte const > input, std::size_t offset, std::uint8_t byte_count)
	Reads a checked little-endian integer with a selected byte count.

normalized_probability_result	parse_normalized_probabilities (std::span< std::byte const > input, std::uint8_t maximum_symbol, std::uint8_t maximum_accuracy_log)
	Parses one forward-coded normalized FSE probability description.

fse_table	build_fse_table (std::span< std::int16_t const > probabilities, std::uint8_t accuracy_log)
	Constructs the FSE decoding table for normalized probabilities.

fse_table	build_rle_fse_table (std::uint8_t symbol)
	Constructs a one-symbol FSE table for RLE sequence mode.

fse_table	build_predefined_literal_length_table ()
	Builds the format-defined predefined literal-length FSE table.

fse_table	build_predefined_match_length_table ()
	Builds the format-defined predefined match-length FSE table.

fse_table	build_predefined_offset_table ()
	Builds the format-defined predefined offset-code FSE table.

std::vector< std::uint8_t >	decode_fse_weights (std::span< std::byte const > input)
	Decodes the two-state FSE stream used for Huffman weights.

huffman_table	build_huffman_table (std::span< std::uint8_t const > explicit_weights)
	Builds the canonical Huffman tree implied by transmitted weights.

huffman_description_result	parse_huffman_description (std::span< std::byte const > input)
	Parses a direct or FSE-compressed Huffman tree description.

std::vector< std::byte >	decode_huffman_stream (std::span< std::byte const > input, std::size_t regenerated_size, huffman_table const &table)
	Decodes one backward Huffman literal stream to an exact byte count.

literals_result	decode_literals (std::span< std::byte const > block, decoder_state &state)
	Decodes the literals section at the front of a compressed block.

void	decompress_compressed_block (std::span< std::byte const > block, std::size_t window_size, std::size_t maximum_output_size, decoder_state &state, std::vector< std::byte > &output)
	Decodes one compressed block into frame output.

template<std::size_t code_count>
encoded_length	encode_length (std::size_t length, std::array< length_code_entry, code_count > const &codes)
	Selects the sequence length code covering one exact length.

std::optional< std::size_t >	find_repeating_period (std::span< std::byte const > block)
	Finds a block prefix whose repetition regenerates the suffix.

std::optional< std::vector< std::byte > >	compress_periodic_block (std::span< std::byte const > block)
	Encodes a periodic block as raw literals plus one match sequence.

template<std::input_iterator input_iterator, std::sentinel_for< input_iterator > sentinel, typename output_iterator>
output_iterator	compress (input_iterator first, sentinel last, output_iterator output, compression_options const &options)
	Compresses an iterator range as a Zstandard frame.

template<std::input_iterator input_iterator, std::sentinel_for< input_iterator > sentinel, typename output_iterator>
output_iterator	decompress (input_iterator first, sentinel last, output_iterator output, decompression_options const &options)
	Decompresses one or more Zstandard or skippable frames.

Variables
constexpr std::array< length_code_entry, 36U >	literal_length_codes {length_code_entry{0U, 0U}, {1U, 0U}, {2U, 0U}, {3U, 0U}, {4U, 0U}, {5U, 0U}, {6U, 0U}, {7U, 0U}, {8U, 0U}, {9U, 0U}, {10U, 0U}, {11U, 0U}, {12U, 0U}, {13U, 0U}, {14U, 0U}, {15U, 0U}, {16U, 1U}, {18U, 1U}, {20U, 1U}, {22U, 1U}, {24U, 2U}, {28U, 2U}, {32U, 3U}, {40U, 3U}, {48U, 4U}, {64U, 6U}, {128U, 7U}, {256U, 8U}, {512U, 9U}, {1024U, 10U}, {2048U, 11U}, {4096U, 12U}, {8192U, 13U}, {16384U, 14U}, {32768U, 15U}, {65536U, 16U}}
	Literal-length code definitions from the Zstandard format.

constexpr std::array< length_code_entry, 53U >	match_length_codes {length_code_entry{3U, 0U}, {4U, 0U}, {5U, 0U}, {6U, 0U}, {7U, 0U}, {8U, 0U}, {9U, 0U}, {10U, 0U}, {11U, 0U}, {12U, 0U}, {13U, 0U}, {14U, 0U}, {15U, 0U}, {16U, 0U}, {17U, 0U}, {18U, 0U}, {19U, 0U}, {20U, 0U}, {21U, 0U}, {22U, 0U}, {23U, 0U}, {24U, 0U}, {25U, 0U}, {26U, 0U}, {27U, 0U}, {28U, 0U}, {29U, 0U}, {30U, 0U}, {31U, 0U}, {32U, 0U}, {33U, 0U}, {34U, 0U}, {35U, 1U}, {37U, 1U}, {39U, 1U}, {41U, 1U}, {43U, 2U}, {47U, 2U}, {51U, 3U}, {59U, 3U}, {67U, 4U}, {83U, 4U}, {99U, 5U}, {131U, 7U}, {259U, 8U}, {515U, 9U}, {1027U, 10U}, {2051U, 11U}, {4099U, 12U}, {8195U, 13U}, {16387U, 14U}, {32771U, 15U}, {65539U, 16U}}
	Match-length code definitions from the Zstandard format.

Detailed Description

Internal implementation of Zstandard compression and decompression.

Function Documentation

◆ append_integer()

void rpnx::compression::zstandard_codec::append_integer	(	std::vector< std::byte > &	output,
		std::uint64_t	value,
		std::uint8_t	byte_count )

inline

Appends a little-endian integer with a selected byte count.

Parameters

output	Buffer receiving encoded bytes.
value	Value to encode.
byte_count	Number of low-order bytes to append.

Definition at line 492 of file zstandard.hpp.

Referenced by compress_periodic_block().

◆ build_fse_table()

fse_table rpnx::compression::zstandard_codec::build_fse_table	(	std::span< std::int16_t const >	probabilities,
		std::uint8_t	accuracy_log )

inlinenodiscard

Constructs the FSE decoding table for normalized probabilities.

Parameters

probabilities	Normalized counts; negative one represents a low-probability symbol.
accuracy_log	Base-two logarithm of the table size.

Returns: Validated state-transition table.

Definition at line 617 of file zstandard.hpp.

References rpnx::compression::invalid_data, and rpnx::compression::zstandard.

Referenced by build_predefined_literal_length_table(), build_predefined_match_length_table(), build_predefined_offset_table(), decode_fse_weights(), and decompress_compressed_block().

◆ build_huffman_table()

huffman_table rpnx::compression::zstandard_codec::build_huffman_table ( std::span< std::uint8_t const > explicit_weights )

inlinenodiscard

Builds the canonical Huffman tree implied by transmitted weights.

Parameters

explicit_weights Weights for all symbols except the inferred final symbol.

Returns: Validated canonical decoding tree.

Definition at line 822 of file zstandard.hpp.

References rpnx::compression::invalid_data, and rpnx::compression::zstandard.

Referenced by parse_huffman_description().

◆ build_predefined_literal_length_table()

fse_table rpnx::compression::zstandard_codec::build_predefined_literal_length_table ( )

inlinenodiscard

Builds the format-defined predefined literal-length FSE table.

Returns: Predefined literal-length state-transition table.

Definition at line 718 of file zstandard.hpp.

References build_fse_table().

Referenced by decompress_compressed_block().

◆ build_predefined_match_length_table()

fse_table rpnx::compression::zstandard_codec::build_predefined_match_length_table ( )

inlinenodiscard

Builds the format-defined predefined match-length FSE table.

Returns: Predefined match-length state-transition table.

Definition at line 728 of file zstandard.hpp.

References build_fse_table().

Referenced by decompress_compressed_block().

◆ build_predefined_offset_table()

fse_table rpnx::compression::zstandard_codec::build_predefined_offset_table ( )

inlinenodiscard

Builds the format-defined predefined offset-code FSE table.

Returns: Predefined offset-code state-transition table.

Definition at line 738 of file zstandard.hpp.

References build_fse_table().

Referenced by decompress_compressed_block().

◆ build_rle_fse_table()

fse_table rpnx::compression::zstandard_codec::build_rle_fse_table ( std::uint8_t symbol )

inlinenodiscard

Constructs a one-symbol FSE table for RLE sequence mode.

Parameters

symbol Repeated symbol.

Returns: Single-state decoding table.

Definition at line 709 of file zstandard.hpp.

Referenced by decompress_compressed_block().

◆ compress()

template<std::input_iterator input_iterator, std::sentinel_for< input_iterator > sentinel, typename output_iterator>

output_iterator rpnx::compression::zstandard_codec::compress	(	input_iterator	first,
		sentinel	last,
		output_iterator	output,
		compression_options const &	options )

Compresses an iterator range as a Zstandard frame.

Template Parameters

input_iterator	Single-pass byte iterator.
sentinel	Sentinel for `first`.
output_iterator	Destination byte iterator.

Parameters

first	First source byte.
last	Sentinel past the source.
output	Destination iterator.
options	Compression level from 0 through 22.

Returns: Destination advanced past the frame checksum.

Definition at line 1463 of file zstandard.hpp.

References compress_periodic_block(), rpnx::compression::invalid_option, rpnx::compression::compression_options::level, rpnx::compression::implementation::to_byte(), rpnx::compression::implementation::write_byte(), and rpnx::compression::zstandard.

◆ compress_periodic_block()

std::optional< std::vector< std::byte > > rpnx::compression::zstandard_codec::compress_periodic_block ( std::span< std::byte const > block )

inlinenodiscard

Encodes a periodic block as raw literals plus one match sequence.

Parameters

block Candidate block.

Returns: Compressed payload when smaller than the source, otherwise no value.

Definition at line 1391 of file zstandard.hpp.

References rpnx::compression::zstandard_codec::encoded_length::additional_value, append_integer(), rpnx::compression::zstandard_codec::encoded_length::code, encode_length(), find_repeating_period(), literal_length_codes, match_length_codes, and rpnx::compression::zstandard_codec::encoded_length::number_of_bits.

Referenced by compress().

◆ decode_fse_weights()

std::vector< std::uint8_t > rpnx::compression::zstandard_codec::decode_fse_weights ( std::span< std::byte const > input )

inlinenodiscard

Decodes the two-state FSE stream used for Huffman weights.

Parameters

input Encoded normalized probabilities followed by reverse-coded states.

Returns: Explicit Huffman weights.

Definition at line 749 of file zstandard.hpp.

Referenced by parse_huffman_description().

◆ decode_huffman_stream()

std::vector< std::byte > rpnx::compression::zstandard_codec::decode_huffman_stream	(	std::span< std::byte const >	input,
		std::size_t	regenerated_size,
		huffman_table const &	table )

inlinenodiscard

Decodes one backward Huffman literal stream to an exact byte count.

Parameters

input	Reverse-coded Huffman stream.
regenerated_size	Exact number of literals to produce.
table	Canonical decoding tree.

Returns: Regenerated literal bytes.

Definition at line 957 of file zstandard.hpp.

References rpnx::compression::invalid_data, rpnx::compression::zstandard_codec::huffman_table::nodes, rpnx::compression::zstandard_codec::reverse_bit_reader::read_bits(), rpnx::compression::zstandard_codec::reverse_bit_reader::remaining_bits(), and rpnx::compression::zstandard.

Referenced by decode_literals().

◆ decode_literals()

literals_result rpnx::compression::zstandard_codec::decode_literals	(	std::span< std::byte const >	block,
		decoder_state &	state )

inlinenodiscard

Decodes the literals section at the front of a compressed block.

Parameters

block	Complete compressed block payload.
state	Frame decoder state retaining a reusable Huffman table.

Returns: Literals and the number of block bytes they occupied.

Definition at line 990 of file zstandard.hpp.

References rpnx::compression::zstandard_codec::huffman_description_result::consumed_bytes, decode_huffman_stream(), rpnx::compression::zstandard_codec::decoder_state::huffman_literals_table, rpnx::compression::invalid_data, parse_huffman_description(), read_integer(), rpnx::compression::zstandard_codec::huffman_description_result::table, and rpnx::compression::zstandard.

Referenced by decompress_compressed_block().

◆ decompress()

template<std::input_iterator input_iterator, std::sentinel_for< input_iterator > sentinel, typename output_iterator>

output_iterator rpnx::compression::zstandard_codec::decompress	(	input_iterator	first,
		sentinel	last,
		output_iterator	output,
		decompression_options const &	options )

Decompresses one or more Zstandard or skippable frames.

Template Parameters

input_iterator	Single-pass byte iterator.
sentinel	Sentinel for `first`.
output_iterator	Destination byte iterator.

Parameters

first	First compressed byte.
last	Sentinel past the compressed input.
output	Destination iterator.
options	Output limit and concatenated-frame policy.

Returns: Destination advanced past the uncompressed data.

Definition at line 1549 of file zstandard.hpp.

◆ decompress_compressed_block()

void rpnx::compression::zstandard_codec::decompress_compressed_block	(	std::span< std::byte const >	block,
		std::size_t	window_size,
		std::size_t	maximum_output_size,
		decoder_state &	state,
		std::vector< std::byte > &	output )

inline

Decodes one compressed block into frame output.

Parameters

block	Complete compressed block payload.
window_size	Declared maximum backward-match window.
maximum_output_size	Absolute output-size limit.
state	Entropy tables and repeat offsets retained across blocks.
output	Frame output and match-history storage.

Definition at line 1116 of file zstandard.hpp.

Referenced by decompress().

◆ encode_length()

template<std::size_t code_count>

encoded_length rpnx::compression::zstandard_codec::encode_length	(	std::size_t	length,
		std::array< length_code_entry, code_count > const &	codes )

inlinenodiscard

Selects the sequence length code covering one exact length.

Template Parameters

code_count Number of entries in codes.

Parameters

length	Exact sequence length.
codes	Ordered baseline and additional-bit definitions.

Returns: Wire code and additional value bits.

Definition at line 1339 of file zstandard.hpp.

References rpnx::compression::zstandard_codec::length_code_entry::baseline, rpnx::compression::invalid_data, rpnx::compression::zstandard_codec::length_code_entry::number_of_bits, and rpnx::compression::zstandard.

Referenced by compress_periodic_block().

◆ find_repeating_period()

std::optional< std::size_t > rpnx::compression::zstandard_codec::find_repeating_period ( std::span< std::byte const > block )

inlinenodiscard

Finds a block prefix whose repetition regenerates the suffix.

Parameters

block Candidate periodic block.

Returns: Repeating period, or no value if no useful repeated suffix exists.

Definition at line 1358 of file zstandard.hpp.

Referenced by compress_periodic_block().

◆ parse_huffman_description()

huffman_description_result rpnx::compression::zstandard_codec::parse_huffman_description ( std::span< std::byte const > input )

inlinenodiscard

Parses a direct or FSE-compressed Huffman tree description.

Parameters

input Bytes beginning with a Huffman description header.

Returns: Parsed tree and occupied byte count.

Definition at line 916 of file zstandard.hpp.

References build_huffman_table(), decode_fse_weights(), rpnx::compression::invalid_data, read_integer(), and rpnx::compression::zstandard.

Referenced by decode_literals().

◆ parse_normalized_probabilities()

normalized_probability_result rpnx::compression::zstandard_codec::parse_normalized_probabilities	(	std::span< std::byte const >	input,
		std::uint8_t	maximum_symbol,
		std::uint8_t	maximum_accuracy_log )

inlinenodiscard

Parses one forward-coded normalized FSE probability description.

Parameters

input	Encoded probability description.
maximum_symbol	Largest permitted symbol value.
maximum_accuracy_log	Largest permitted FSE accuracy log.

Returns: Parsed probabilities and occupied byte count.

Definition at line 528 of file zstandard.hpp.

References rpnx::compression::zstandard_codec::forward_bit_reader::consumed_bytes(), rpnx::compression::invalid_data, rpnx::compression::zstandard_codec::forward_bit_reader::peek_bits(), rpnx::compression::zstandard_codec::forward_bit_reader::read_bits(), and rpnx::compression::zstandard.

Referenced by decode_fse_weights(), and decompress_compressed_block().

◆ read_integer()

std::uint64_t rpnx::compression::zstandard_codec::read_integer	(	std::span< std::byte const >	input,
		std::size_t	offset,
		std::uint8_t	byte_count )

inlinenodiscard

Reads a checked little-endian integer with a selected byte count.

Parameters

input	Source bytes.
offset	Position of the first byte.
byte_count	Width from zero through eight bytes.

Returns: Decoded value.

Definition at line 507 of file zstandard.hpp.

References rpnx::compression::invalid_data, and rpnx::compression::zstandard.

Referenced by decode_literals(), decompress(), decompress_compressed_block(), and parse_huffman_description().

◆ read_word32()

std::uint32_t rpnx::compression::zstandard_codec::read_word32	(	std::span< std::byte const >	input,
		std::size_t	offset )

inlinenodiscardnoexcept

Reads an unchecked little-endian 32-bit word.

Parameters

input	Range containing at least four bytes at `offset`.
offset	Position of the first byte.

Returns: Decoded word.

Definition at line 275 of file zstandard.hpp.

Referenced by rpnx::compression::zstandard_codec::xxhash64_accumulator::value(), and xxhash64().

◆ read_word64()

std::uint64_t rpnx::compression::zstandard_codec::read_word64	(	std::span< std::byte const >	input,
		std::size_t	offset )

inlinenodiscardnoexcept

Reads an unchecked little-endian 64-bit word.

Parameters

input	Range containing at least eight bytes at `offset`.
offset	Position of the first byte.

Returns: Decoded word.

Definition at line 286 of file zstandard.hpp.

Referenced by rpnx::compression::zstandard_codec::xxhash64_accumulator::update(), rpnx::compression::zstandard_codec::xxhash64_accumulator::value(), and xxhash64().

◆ rotate_left()

std::uint64_t rpnx::compression::zstandard_codec::rotate_left	(	std::uint64_t	value,
		std::uint8_t	count )

inlinenodiscardnoexcept

Rotates a 64-bit value left without compiler-specific intrinsics.

Parameters

value	Value to rotate.
count	Rotation distance in the range 1–63.

Returns: Rotated value.

Definition at line 264 of file zstandard.hpp.

Referenced by rpnx::compression::zstandard_codec::xxhash64_accumulator::value(), and xxhash64().

◆ xxhash64()

std::uint64_t rpnx::compression::zstandard_codec::xxhash64	(	std::span< std::byte const >	input,
		std::uint64_t	seed = 0U )

inlinenodiscardnoexcept

Computes XXH64 as required by the Zstandard frame checksum.

Parameters

input	Bytes to hash.
seed	XXH64 seed.

Returns: Finalized 64-bit hash.

Definition at line 302 of file zstandard.hpp.

References read_word32(), read_word64(), and rotate_left().

Variable Documentation

◆ literal_length_codes

std::array< length_code_entry, 36U > rpnx::compression::zstandard_codec::literal_length_codes {length_code_entry{0U, 0U}, {1U, 0U}, {2U, 0U}, {3U, 0U}, {4U, 0U}, {5U, 0U}, {6U, 0U}, {7U, 0U}, {8U, 0U}, {9U, 0U}, {10U, 0U}, {11U, 0U}, {12U, 0U}, {13U, 0U}, {14U, 0U}, {15U, 0U}, {16U, 1U}, {18U, 1U}, {20U, 1U}, {22U, 1U}, {24U, 2U}, {28U, 2U}, {32U, 3U}, {40U, 3U}, {48U, 4U}, {64U, 6U}, {128U, 7U}, {256U, 8U}, {512U, 9U}, {1024U, 10U}, {2048U, 11U}, {4096U, 12U}, {8192U, 13U}, {16384U, 14U}, {32768U, 15U}, {65536U, 16U}}

inlineconstexpr

Literal-length code definitions from the Zstandard format.

Definition at line 131 of file zstandard.hpp.

Referenced by compress_periodic_block(), and decompress_compressed_block().

◆ match_length_codes

std::array< length_code_entry, 53U > rpnx::compression::zstandard_codec::match_length_codes {length_code_entry{3U, 0U}, {4U, 0U}, {5U, 0U}, {6U, 0U}, {7U, 0U}, {8U, 0U}, {9U, 0U}, {10U, 0U}, {11U, 0U}, {12U, 0U}, {13U, 0U}, {14U, 0U}, {15U, 0U}, {16U, 0U}, {17U, 0U}, {18U, 0U}, {19U, 0U}, {20U, 0U}, {21U, 0U}, {22U, 0U}, {23U, 0U}, {24U, 0U}, {25U, 0U}, {26U, 0U}, {27U, 0U}, {28U, 0U}, {29U, 0U}, {30U, 0U}, {31U, 0U}, {32U, 0U}, {33U, 0U}, {34U, 0U}, {35U, 1U}, {37U, 1U}, {39U, 1U}, {41U, 1U}, {43U, 2U}, {47U, 2U}, {51U, 3U}, {59U, 3U}, {67U, 4U}, {83U, 4U}, {99U, 5U}, {131U, 7U}, {259U, 8U}, {515U, 9U}, {1027U, 10U}, {2051U, 11U}, {4099U, 12U}, {8195U, 13U}, {16387U, 14U}, {32771U, 15U}, {65539U, 16U}}

inlineconstexpr

Match-length code definitions from the Zstandard format.

Definition at line 134 of file zstandard.hpp.

Referenced by compress_periodic_block(), and decompress_compressed_block().

RPNX::Compress Self-contained C++20 compression and ZIP library

Classes

Functions

Variables

Detailed Description

Function Documentation

◆ append_integer()

◆ build_fse_table()

◆ build_huffman_table()

◆ build_predefined_literal_length_table()

◆ build_predefined_match_length_table()

◆ build_predefined_offset_table()

◆ build_rle_fse_table()

◆ compress()

◆ compress_periodic_block()

◆ decode_fse_weights()

◆ decode_huffman_stream()

◆ decode_literals()

◆ decompress()

◆ decompress_compressed_block()

◆ encode_length()

◆ find_repeating_period()

◆ parse_huffman_description()

◆ parse_normalized_probabilities()

◆ read_integer()

◆ read_word32()

◆ read_word64()

◆ rotate_left()

◆ xxhash64()

Variable Documentation

◆ literal_length_codes

◆ match_length_codes