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

Classes
struct	burrows_wheeler_result
	Burrows-Wheeler last column and its original rotation index. More...

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

struct	huffman_table
	Canonical bzip2 Huffman decoding tree. More...

class	iterator_bit_reader
	MSB-first bit reader backed by a single-pass byte reader. More...

class	iterator_bit_writer
	MSB-first bit writer backed by an STL output iterator. More...

Functions
std::uint32_t	crc32 (std::span< std::byte const > input) noexcept
	Computes the non-reflected CRC-32 variant used by bzip2 blocks.

huffman_table	build_huffman_table (std::span< std::uint8_t const > lengths)
	Builds a canonical Huffman tree from bzip2 code lengths.

template<typename reader_type>
std::uint16_t	decode_huffman_symbol (reader_type &reader, huffman_table const &table)
	Decodes one symbol with a canonical bzip2 Huffman tree.

std::vector< std::byte >	encode_first_run_length (std::span< std::byte const > input)
	Applies bzip2's first run-length transform to one source block.

burrows_wheeler_result	burrows_wheeler_transform (std::span< std::byte const > input)
	Sorts cyclic rotations and produces the Burrows-Wheeler last column.

template<typename writer_type>
void	compress_block (writer_type &writer, std::span< std::byte const > input, std::uint32_t &combined_crc)
	Encode one bzip2 block with deterministic canonical Huffman tables.

template<typename reader_type>
std::vector< std::byte >	decompress_block (reader_type &reader, std::size_t block_size_limit, std::size_t maximum_output_size, std::uint32_t &combined_crc)
	Decode one bzip2 block after its block magic.

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 native bzip2 stream.

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 native bzip2 streams.

Detailed Description

Internal implementation of bzip2 compression and decompression.

Function Documentation

◆ build_huffman_table()

huffman_table rpnx::compression::bzip2_codec::build_huffman_table ( std::span< std::uint8_t const > lengths )

inlinenodiscard

Builds a canonical Huffman tree from bzip2 code lengths.

Parameters

lengths Code length for each symbol in symbol order.

Returns: Validated decoding tree.

Exceptions

compression_error If a length is invalid or the tree is oversubscribed.

Definition at line 80 of file bzip2.hpp.

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

Referenced by decompress_block().

◆ burrows_wheeler_transform()

burrows_wheeler_result rpnx::compression::bzip2_codec::burrows_wheeler_transform ( std::span< std::byte const > input )

inlinenodiscard

Sorts cyclic rotations and produces the Burrows-Wheeler last column.

Parameters

input Run-length transformed block.

Returns: Last-column bytes and the original row index.

Exceptions

compression_error If the rotation table loses the original row.

Definition at line 216 of file bzip2.hpp.

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

Referenced by compress_block().

◆ compress()

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

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

Compresses an iterator range as a native bzip2 stream.

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 1 through 9.

Returns: Destination advanced past the stream trailer.

Definition at line 834 of file bzip2.hpp.

References rpnx::compression::bzip2, compress_block(), rpnx::compression::bzip2_codec::iterator_bit_writer< output_iterator >::finish(), rpnx::compression::invalid_option, rpnx::compression::compression_options::level, rpnx::compression::implementation::to_byte(), and rpnx::compression::bzip2_codec::iterator_bit_writer< output_iterator >::write_bits().

◆ compress_block()

template<typename writer_type>

void rpnx::compression::bzip2_codec::compress_block	(	writer_type &	writer,
		std::span< std::byte const >	input,
		std::uint32_t &	combined_crc )

Encode one bzip2 block with deterministic canonical Huffman tables.

Encodes one bzip2 block and updates the stream checksum.

Template Parameters

writer_type MSB-first writer providing write_bits().

Parameters

writer	Destination bit writer.
input	Uncompressed source block.
combined_crc	Rolling stream checksum updated in place.

Definition at line 323 of file bzip2.hpp.

References burrows_wheeler_transform(), rpnx::compression::bzip2, crc32(), encode_first_run_length(), rpnx::compression::invalid_data, rpnx::compression::bzip2_codec::burrows_wheeler_result::last_column, and rpnx::compression::bzip2_codec::burrows_wheeler_result::original_pointer.

Referenced by compress().

◆ crc32()

std::uint32_t rpnx::compression::bzip2_codec::crc32 ( std::span< std::byte const > input )

inlinenodiscardnoexcept

Computes the non-reflected CRC-32 variant used by bzip2 blocks.

Parameters

input Uncompressed block bytes.

Returns: Finalized bzip2 CRC-32.

Definition at line 60 of file bzip2.hpp.

Referenced by compress_block(), and decompress_block().

◆ decode_huffman_symbol()

template<typename reader_type>

std::uint16_t rpnx::compression::bzip2_codec::decode_huffman_symbol	(	reader_type &	reader,
		huffman_table const &	table )

nodiscard

Decodes one symbol with a canonical bzip2 Huffman tree.

Template Parameters

reader_type MSB-first reader providing read_bits().

Parameters

reader	Source bit reader.
table	Validated decoding tree.

Returns: Decoded symbol index.

Exceptions

compression_error If the bit sequence does not identify a leaf.

Definition at line 157 of file bzip2.hpp.

References rpnx::compression::bzip2, rpnx::compression::invalid_data, and rpnx::compression::bzip2_codec::huffman_table::nodes.

Referenced by decompress_block().

◆ decompress()

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

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

Decompresses one or more native bzip2 streams.

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-stream policy.

Returns: Destination advanced past the uncompressed data.

Definition at line 876 of file bzip2.hpp.

References rpnx::compression::decompression_options::allow_concatenated_streams, rpnx::compression::bzip2, decompress_block(), rpnx::compression::implementation::byte_reader< input_iterator, sentinel >::empty(), rpnx::compression::invalid_data, rpnx::compression::decompression_options::maximum_output_size, rpnx::compression::output_limit_exceeded, rpnx::compression::trailing_data, and rpnx::compression::implementation::write_byte().

◆ decompress_block()

template<typename reader_type>

std::vector< std::byte > rpnx::compression::bzip2_codec::decompress_block	(	reader_type &	reader,
		std::size_t	block_size_limit,
		std::size_t	maximum_output_size,
		std::uint32_t &	combined_crc )

nodiscard

Decode one bzip2 block after its block magic.

Decodes one bzip2 block and updates the stream checksum.

Template Parameters

reader_type MSB-first reader providing read_bits().

Parameters

reader	Source bit reader positioned after the block magic.
block_size_limit	Maximum transformed block size declared by the stream.
maximum_output_size	Maximum uncompressed bytes this block may produce.
combined_crc	Rolling stream checksum updated in place.

Returns: Uncompressed block data.

Exceptions

compression_error If entropy data, transforms, size, or checksum is invalid.

Definition at line 458 of file bzip2.hpp.

References build_huffman_table(), rpnx::compression::bzip2, crc32(), decode_huffman_symbol(), rpnx::compression::invalid_data, rpnx::compression::output_limit_exceeded, and rpnx::compression::unsupported_feature.

Referenced by decompress().

◆ encode_first_run_length()

std::vector< std::byte > rpnx::compression::bzip2_codec::encode_first_run_length ( std::span< std::byte const > input )

inlinenodiscard

Applies bzip2's first run-length transform to one source block.

Parameters

input Source block.

Returns: Run-length transformed bytes.

Definition at line 178 of file bzip2.hpp.

Referenced by compress_block().

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

Classes

Functions

Detailed Description

Function Documentation

◆ build_huffman_table()

◆ burrows_wheeler_transform()

◆ compress()

◆ compress_block()

◆ crc32()

◆ decode_huffman_symbol()

◆ decompress()

◆ decompress_block()

◆ encode_first_run_length()