bzip2.hpp

Go to the documentation of this file.

#ifndef RPNX_COMPRESSION_IMPLEMENTATION_BZIP2_HPP
#define RPNX_COMPRESSION_IMPLEMENTATION_BZIP2_HPP
 
#include <algorithm>
#include <array>
#include <bit>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <limits>
#include <optional>
#include <span>
#include <type_traits>
#include <utility>
#include <vector>
 
#include <rpnx/compression/implementation/io.hpp>
 
/**
 * @file
 * @brief Native bzip2 block transforms, entropy coding, and stream adapters.
 */
 
/** @brief Internal implementation of bzip2 compression and decompression. */
namespace rpnx::compression::bzip2_codec
{
 
    /** One node in a canonical bzip2 Huffman decoding tree. */
    struct huffman_node
    {
        /** @brief Child selected by a zero bit, if present. */
        std::optional< std::uint16_t > zero_child;
        /** @brief Child selected by a one bit, if present. */
        std::optional< std::uint16_t > one_child;
        /** @brief Decoded symbol for a leaf node. */
        std::optional< std::uint16_t > symbol;
    };
 
    /** Canonical bzip2 Huffman decoding tree. */
    struct huffman_table
    {
        /** @brief Tree nodes with the root at index zero. */
        std::vector< huffman_node > nodes;
    };
 
    /** Burrows-Wheeler last column and its original rotation index. */
    struct burrows_wheeler_result
    {
        /** @brief Final byte of each lexicographically sorted cyclic rotation. */
        std::vector< std::byte > last_column;
        /** @brief Row containing the unrotated source block. */
        std::size_t original_pointer;
    };
 
    /**
     * @brief Computes the non-reflected CRC-32 variant used by bzip2 blocks.
     * @param input Uncompressed block bytes.
     * @return Finalized bzip2 CRC-32.
     */
    [[nodiscard]] inline std::uint32_t crc32(std::span< std::byte const > input) noexcept
    {
        std::uint32_t crc = 0xffffffffU;
        for (std::byte value : input)
        {
            crc ^= static_cast< std::uint32_t >(std::to_integer< std::uint8_t >(value)) << 24U;
            for (std::uint8_t bit = 0U; bit < 8U; ++bit)
            {
                crc = (crc & 0x80000000U) != 0U ? (crc << 1U) ^ 0x04c11db7U : crc << 1U;
            }
        }
        return ~crc;
    }
 
    /**
     * @brief Builds a canonical Huffman tree from bzip2 code lengths.
     * @param lengths Code length for each symbol in symbol order.
     * @return Validated decoding tree.
     * @throws compression_error If a length is invalid or the tree is oversubscribed.
     */
    [[nodiscard]] inline huffman_table build_huffman_table(std::span< std::uint8_t const > lengths)
    {
        std::uint8_t minimum_length = 21U;
        std::uint8_t maximum_length = 0U;
        for (std::uint8_t length : lengths)
        {
            if (length == 0U || length > 20U)
            {
                throw compression_error(error_code::invalid_data, format::bzip2, "invalid bzip2 Huffman code length");
            }
            minimum_length = std::min(minimum_length, length);
            maximum_length = std::max(maximum_length, length);
        }
 
        huffman_table table{{huffman_node{}}};
        std::uint32_t code = 0U;
        for (std::uint8_t length = minimum_length; length <= maximum_length; ++length)
        {
            if (length != minimum_length)
            {
                code <<= 1U;
            }
            for (std::size_t symbol = 0U; symbol < lengths.size(); ++symbol)
            {
                if (lengths[symbol] != length)
                {
                    continue;
                }
                if (code >= (std::uint32_t{1U} << length))
                {
                    throw compression_error(error_code::invalid_data, format::bzip2, "oversubscribed bzip2 Huffman tree");
                }
                std::size_t node_index = 0U;
                for (std::uint8_t depth = 0U; depth < length; ++depth)
                {
                    if (table.nodes[node_index].symbol.has_value())
                    {
                        throw compression_error(error_code::invalid_data, format::bzip2, "overlapping bzip2 Huffman prefix codes");
                    }
                    std::uint8_t const bit = static_cast< std::uint8_t >((code >> (length - depth - 1U)) & 1U);
                    std::optional< std::uint16_t >& child = bit == 0U ? table.nodes[node_index].zero_child : table.nodes[node_index].one_child;
                    if (!child.has_value())
                    {
                        if (table.nodes.size() >= std::numeric_limits< std::uint16_t >::max())
                        {
                            throw compression_error(error_code::invalid_data, format::bzip2, "bzip2 Huffman tree is too large");
                        }
                        std::uint16_t const new_node = static_cast< std::uint16_t >(table.nodes.size());
                        child = new_node;
                        node_index = new_node;
                        table.nodes.push_back(huffman_node{});
                    }
                    else
                    {
                        node_index = *child;
                    }
                }
                if (table.nodes[node_index].symbol.has_value() || table.nodes[node_index].zero_child.has_value() || table.nodes[node_index].one_child.has_value())
                {
                    throw compression_error(error_code::invalid_data, format::bzip2, "duplicate bzip2 Huffman prefix code");
                }
                table.nodes[node_index].symbol = static_cast< std::uint16_t >(symbol);
                ++code;
            }
        }
        return table;
    }
 
    /**
     * @brief Decodes one symbol with a canonical bzip2 Huffman tree.
     * @tparam reader_type MSB-first reader providing read_bits().
     * @param reader Source bit reader.
     * @param table Validated decoding tree.
     * @return Decoded symbol index.
     * @throws compression_error If the bit sequence does not identify a leaf.
     */
    template < typename reader_type >
    [[nodiscard]] std::uint16_t decode_huffman_symbol(reader_type& reader, huffman_table const& table)
    {
        std::size_t node_index = 0U;
        while (!table.nodes[node_index].symbol.has_value())
        {
            std::uint8_t const bit = static_cast< std::uint8_t >(reader.read_bits(1U));
            std::optional< std::uint16_t > const child = bit == 0U ? table.nodes[node_index].zero_child : table.nodes[node_index].one_child;
            if (!child.has_value() || *child >= table.nodes.size())
            {
                throw compression_error(error_code::invalid_data, format::bzip2, "invalid bzip2 Huffman code");
            }
            node_index = *child;
        }
        return *table.nodes[node_index].symbol;
    }
 
    /**
     * @brief Applies bzip2's first run-length transform to one source block.
     * @param input Source block.
     * @return Run-length transformed bytes.
     */
    [[nodiscard]] inline std::vector< std::byte > encode_first_run_length(std::span< std::byte const > input)
    {
        std::vector< std::byte > output;
        output.reserve(input.size());
        std::size_t position = 0U;
        while (position < input.size())
        {
            std::size_t run_end = position + 1U;
            while (run_end < input.size() && input[run_end] == input[position])
            {
                ++run_end;
            }
            std::size_t remaining = run_end - position;
            while (remaining != 0U)
            {
                std::size_t const chunk_size = std::min< std::size_t >(remaining, 259U);
                if (chunk_size < 4U)
                {
                    output.insert(output.end(), chunk_size, input[position]);
                }
                else
                {
                    output.insert(output.end(), 4U, input[position]);
                    output.push_back(static_cast< std::byte >(chunk_size - 4U));
                }
                remaining -= chunk_size;
            }
            position = run_end;
        }
        return output;
    }
 
    /**
     * @brief Sorts cyclic rotations and produces the Burrows-Wheeler last column.
     * @param input Run-length transformed block.
     * @return Last-column bytes and the original row index.
     * @throws compression_error If the rotation table loses the original row.
     */
    [[nodiscard]] inline burrows_wheeler_result burrows_wheeler_transform(std::span< std::byte const > input)
    {
        if (input.empty())
        {
            throw compression_error(error_code::invalid_data, format::bzip2, "cannot transform an empty bzip2 block");
        }
        std::size_t const size = input.size();
        std::vector< std::size_t > order(size, 0U);
        std::vector< std::size_t > classes(size, 0U);
        std::array< std::size_t, 256U > byte_counts{};
        for (std::byte value : input)
        {
            ++byte_counts[std::to_integer< std::uint8_t >(value)];
        }
        std::array< std::size_t, 256U > byte_positions{};
        for (std::size_t byte = 1U; byte < byte_positions.size(); ++byte)
        {
            byte_positions[byte] = byte_positions[byte - 1U] + byte_counts[byte - 1U];
        }
        for (std::size_t index = 0U; index < size; ++index)
        {
            std::uint8_t const value = std::to_integer< std::uint8_t >(input[index]);
            order[byte_positions[value]++] = index;
        }
        std::size_t class_count = 1U;
        classes[order[0U]] = 0U;
        for (std::size_t index = 1U; index < size; ++index)
        {
            if (input[order[index]] != input[order[index - 1U]])
            {
                ++class_count;
            }
            classes[order[index]] = class_count - 1U;
        }
 
        std::vector< std::size_t > shifted(size, 0U);
        std::vector< std::size_t > new_classes(size, 0U);
        for (std::size_t shift = 1U; shift < size; shift <<= 1U)
        {
            for (std::size_t index = 0U; index < size; ++index)
            {
                shifted[index] = order[index] >= shift ? order[index] - shift : order[index] + size - shift;
            }
            std::vector< std::size_t > counts(class_count, 0U);
            for (std::size_t index : shifted)
            {
                ++counts[classes[index]];
            }
            std::vector< std::size_t > positions(class_count, 0U);
            for (std::size_t class_index = 1U; class_index < class_count; ++class_index)
            {
                positions[class_index] = positions[class_index - 1U] + counts[class_index - 1U];
            }
            for (std::size_t index : shifted)
            {
                std::size_t const class_index = classes[index];
                order[positions[class_index]++] = index;
            }
 
            std::size_t new_class_count = 1U;
            new_classes[order[0U]] = 0U;
            for (std::size_t index = 1U; index < size; ++index)
            {
                std::size_t const current = order[index];
                std::size_t const previous = order[index - 1U];
                if (classes[current] != classes[previous] || classes[(current + shift) % size] != classes[(previous + shift) % size])
                {
                    ++new_class_count;
                }
                new_classes[current] = new_class_count - 1U;
            }
            classes.swap(new_classes);
            class_count = new_class_count;
            if (shift > size / 2U)
            {
                break;
            }
        }
 
        std::vector< std::byte > last_column;
        last_column.reserve(size);
        std::optional< std::size_t > original_pointer;
        for (std::size_t row = 0U; row < size; ++row)
        {
            std::size_t const rotation = order[row];
            if (rotation == 0U)
            {
                original_pointer = row;
            }
            last_column.push_back(input[rotation == 0U ? size - 1U : rotation - 1U]);
        }
        if (!original_pointer.has_value())
        {
            throw compression_error(error_code::invalid_data, format::bzip2, "bzip2 rotation sort lost the original row");
        }
        return burrows_wheeler_result{std::move(last_column), *original_pointer};
    }
 
    /** Encode one bzip2 block with deterministic canonical Huffman tables. */
    /**
     * @brief Encodes one bzip2 block and updates the stream checksum.
     * @tparam writer_type MSB-first writer providing write_bits().
     * @param writer Destination bit writer.
     * @param input Uncompressed source block.
     * @param combined_crc Rolling stream checksum updated in place.
     */
    template < typename writer_type >
    void compress_block(writer_type& writer, std::span< std::byte const > input, std::uint32_t& combined_crc)
    {
        std::uint32_t const block_crc = crc32(input);
        combined_crc = ((combined_crc << 1U) | (combined_crc >> 31U)) ^ block_crc;
        std::vector< std::byte > run_length_encoded = encode_first_run_length(input);
        burrows_wheeler_result transformed = burrows_wheeler_transform(run_length_encoded);
 
        std::array< bool, 256U > used{};
        for (std::byte value : transformed.last_column)
        {
            used[std::to_integer< std::uint8_t >(value)] = true;
        }
        std::vector< std::uint8_t > alphabet;
        for (std::size_t symbol = 0U; symbol < used.size(); ++symbol)
        {
            if (used[symbol])
            {
                alphabet.push_back(static_cast< std::uint8_t >(symbol));
            }
        }
 
        std::vector< std::uint8_t > move_to_front = alphabet;
        std::vector< std::uint16_t > codes;
        codes.reserve(transformed.last_column.size() + 1U);
        std::size_t zero_run = 0U;
        auto flush_zero_run = [&]
        {
            if (zero_run == 0U)
            {
                return;
            }
            std::size_t value = zero_run - 1U;
            while (true)
            {
                codes.push_back(static_cast< std::uint16_t >((value & 1U) != 0U ? 1U : 0U));
                if (value < 2U)
                {
                    break;
                }
                value = (value - 2U) / 2U;
            }
            zero_run = 0U;
        };
        for (std::byte byte : transformed.last_column)
        {
            std::uint8_t const symbol = std::to_integer< std::uint8_t >(byte);
            std::size_t mtf_index = 0U;
            while (mtf_index < move_to_front.size() && move_to_front[mtf_index] != symbol)
            {
                ++mtf_index;
            }
            if (mtf_index == move_to_front.size())
            {
                throw compression_error(error_code::invalid_data, format::bzip2, "bzip2 MTF encoder lost a block symbol");
            }
            if (mtf_index == 0U)
            {
                ++zero_run;
                continue;
            }
            flush_zero_run();
            codes.push_back(static_cast< std::uint16_t >(mtf_index + 1U));
            for (std::size_t index = mtf_index; index > 0U; --index)
            {
                move_to_front[index] = move_to_front[index - 1U];
            }
            move_to_front[0U] = symbol;
        }
        flush_zero_run();
        std::size_t const alphabet_size = alphabet.size() + 2U;
        codes.push_back(static_cast< std::uint16_t >(alphabet_size - 1U));
 
        writer.write_bits(0x314159265359ULL, 48U);
        writer.write_bits(block_crc, 32U);
        writer.write_bits(0U, 1U);
        writer.write_bits(transformed.original_pointer, 24U);
        std::uint16_t range_mask = 0U;
        std::array< std::uint16_t, 16U > symbol_masks{};
        for (std::size_t symbol = 0U; symbol < used.size(); ++symbol)
        {
            if (used[symbol])
            {
                std::size_t const range = symbol / 16U;
                range_mask |= static_cast< std::uint16_t >(std::uint16_t{1U} << (15U - range));
                symbol_masks[range] |= static_cast< std::uint16_t >(std::uint16_t{1U} << (15U - symbol % 16U));
            }
        }
        writer.write_bits(range_mask, 16U);
        for (std::size_t range = 0U; range < symbol_masks.size(); ++range)
        {
            if (symbol_masks[range] != 0U)
            {
                writer.write_bits(symbol_masks[range], 16U);
            }
        }
 
        writer.write_bits(2U, 3U);
        std::size_t const selector_count = (codes.size() + 49U) / 50U;
        if (selector_count == 0U || selector_count > 18002U)
        {
            throw compression_error(error_code::invalid_data, format::bzip2, "native bzip2 selector count exceeds the format limit");
        }
        writer.write_bits(selector_count, 15U);
        for (std::size_t selector = 0U; selector < selector_count; ++selector)
        {
            writer.write_bits(0U, 1U);
        }
 
        std::uint8_t const code_length = static_cast< std::uint8_t >(std::bit_width(alphabet_size - 1U));
        for (std::size_t group = 0U; group < 2U; ++group)
        {
            writer.write_bits(code_length, 5U);
            for (std::size_t symbol = 0U; symbol < alphabet_size; ++symbol)
            {
                writer.write_bits(0U, 1U);
            }
        }
        for (std::uint16_t code : codes)
        {
            writer.write_bits(code, code_length);
        }
    }
 
    /** Decode one bzip2 block after its block magic. */
    /**
     * @brief Decodes one bzip2 block and updates the stream checksum.
     * @tparam reader_type MSB-first reader providing read_bits().
     * @param reader Source bit reader positioned after the block magic.
     * @param block_size_limit Maximum transformed block size declared by the stream.
     * @param maximum_output_size Maximum uncompressed bytes this block may produce.
     * @param combined_crc Rolling stream checksum updated in place.
     * @return Uncompressed block data.
     * @throws compression_error If entropy data, transforms, size, or checksum is invalid.
     */
    template < typename reader_type >
    [[nodiscard]] 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)
    {
        std::uint32_t const expected_block_crc = static_cast< std::uint32_t >(reader.read_bits(32U));
        if (reader.read_bits(1U) != 0U)
        {
            throw compression_error(error_code::unsupported_feature, format::bzip2, "deprecated randomized bzip2 blocks are not supported");
        }
        std::size_t const original_pointer = static_cast< std::size_t >(reader.read_bits(24U));
 
        std::uint16_t const used_ranges = static_cast< std::uint16_t >(reader.read_bits(16U));
        std::vector< std::uint8_t > symbols;
        symbols.reserve(256U);
        for (std::uint8_t range = 0U; range < 16U; ++range)
        {
            if ((used_ranges & (std::uint16_t{1U} << (15U - range))) == 0U)
            {
                continue;
            }
            std::uint16_t const used_symbols = static_cast< std::uint16_t >(reader.read_bits(16U));
            for (std::uint8_t symbol = 0U; symbol < 16U; ++symbol)
            {
                if ((used_symbols & (std::uint16_t{1U} << (15U - symbol))) != 0U)
                {
                    symbols.push_back(static_cast< std::uint8_t >(range * 16U + symbol));
                }
            }
        }
        if (symbols.empty())
        {
            throw compression_error(error_code::invalid_data, format::bzip2, "bzip2 block has no symbol alphabet");
        }
 
        std::size_t const group_count = static_cast< std::size_t >(reader.read_bits(3U));
        if (group_count < 2U || group_count > 6U)
        {
            throw compression_error(error_code::invalid_data, format::bzip2, "invalid number of bzip2 Huffman groups");
        }
        std::size_t const selector_count = static_cast< std::size_t >(reader.read_bits(15U));
        if (selector_count == 0U || selector_count > 18002U)
        {
            throw compression_error(error_code::invalid_data, format::bzip2, "invalid number of bzip2 Huffman selectors");
        }
        std::vector< std::uint8_t > selector_mtf(group_count);
        for (std::size_t index = 0U; index < group_count; ++index)
        {
            selector_mtf[index] = static_cast< std::uint8_t >(index);
        }
        std::vector< std::uint8_t > selectors;
        selectors.reserve(selector_count);
        for (std::size_t selector = 0U; selector < selector_count; ++selector)
        {
            std::size_t mtf_index = 0U;
            while (reader.read_bits(1U) != 0U)
            {
                ++mtf_index;
                if (mtf_index >= group_count)
                {
                    throw compression_error(error_code::invalid_data, format::bzip2, "bzip2 selector exceeds the Huffman group count");
                }
            }
            std::uint8_t const group = selector_mtf[mtf_index];
            for (std::size_t index = mtf_index; index > 0U; --index)
            {
                selector_mtf[index] = selector_mtf[index - 1U];
            }
            selector_mtf[0U] = group;
            selectors.push_back(group);
        }
 
        std::size_t const alphabet_size = symbols.size() + 2U;
        std::vector< huffman_table > tables;
        tables.reserve(group_count);
        for (std::size_t group = 0U; group < group_count; ++group)
        {
            std::int16_t length = static_cast< std::int16_t >(reader.read_bits(5U));
            std::vector< std::uint8_t > lengths;
            lengths.reserve(alphabet_size);
            for (std::size_t symbol = 0U; symbol < alphabet_size; ++symbol)
            {
                while (reader.read_bits(1U) != 0U)
                {
                    if (reader.read_bits(1U) != 0U)
                    {
                        --length;
                    }
                    else
                    {
                        ++length;
                    }
                    if (length < 1 || length > 20)
                    {
                        throw compression_error(error_code::invalid_data, format::bzip2, "bzip2 Huffman length exceeds its format limit");
                    }
                }
                lengths.push_back(static_cast< std::uint8_t >(length));
            }
            tables.push_back(build_huffman_table(lengths));
        }
 
        std::vector< std::uint8_t > move_to_front = symbols;
        std::vector< std::byte > transformed;
        transformed.reserve(block_size_limit);
        std::size_t selector_position = 0U;
        std::size_t symbols_in_group = 0U;
        std::size_t repeat_count = 0U;
        std::size_t repeat_power = 0U;
        while (true)
        {
            if (symbols_in_group == 0U)
            {
                if (selector_position >= selectors.size())
                {
                    throw compression_error(error_code::invalid_data, format::bzip2, "insufficient bzip2 Huffman selectors");
                }
                symbols_in_group = 50U;
            }
            std::uint8_t const group = selectors[selector_position];
            std::uint16_t const value = decode_huffman_symbol(reader, tables[group]);
            --symbols_in_group;
            if (symbols_in_group == 0U)
            {
                ++selector_position;
            }
 
            if (value < 2U)
            {
                if (repeat_count == 0U)
                {
                    repeat_power = 1U;
                }
                if (repeat_power > block_size_limit || (value != 0U && repeat_power > (block_size_limit - repeat_count) / 2U))
                {
                    throw compression_error(error_code::invalid_data, format::bzip2, "bzip2 RUNA/RUNB count exceeds the block size");
                }
                repeat_count += repeat_power << value;
                repeat_power <<= 1U;
                if (repeat_count > block_size_limit)
                {
                    throw compression_error(error_code::invalid_data, format::bzip2, "bzip2 RUNA/RUNB count exceeds the block size");
                }
                continue;
            }
 
            if (repeat_count != 0U)
            {
                if (repeat_count > block_size_limit - transformed.size())
                {
                    throw compression_error(error_code::invalid_data, format::bzip2, "bzip2 run exceeds the block size");
                }
                transformed.insert(transformed.end(), repeat_count, static_cast< std::byte >(move_to_front[0U]));
                repeat_count = 0U;
            }
            if (value == alphabet_size - 1U)
            {
                break;
            }
            std::size_t const mtf_index = value - 1U;
            if (mtf_index >= move_to_front.size())
            {
                throw compression_error(error_code::invalid_data, format::bzip2, "bzip2 MTF index exceeds its alphabet");
            }
            std::uint8_t const symbol = move_to_front[mtf_index];
            for (std::size_t index = mtf_index; index > 0U; --index)
            {
                move_to_front[index] = move_to_front[index - 1U];
            }
            move_to_front[0U] = symbol;
            if (transformed.size() == block_size_limit)
            {
                throw compression_error(error_code::invalid_data, format::bzip2, "bzip2 transformed data exceeds the block size");
            }
            transformed.push_back(static_cast< std::byte >(symbol));
        }
 
        if (transformed.empty() || original_pointer >= transformed.size())
        {
            throw compression_error(error_code::invalid_data, format::bzip2, "bzip2 original pointer exceeds the transformed block");
        }
        std::array< std::size_t, 256U > counts{};
        for (std::byte value : transformed)
        {
            ++counts[std::to_integer< std::uint8_t >(value)];
        }
        std::array< std::size_t, 256U > positions{};
        std::size_t cumulative = 0U;
        for (std::size_t symbol = 0U; symbol < counts.size(); ++symbol)
        {
            positions[symbol] = cumulative;
            cumulative += counts[symbol];
        }
        std::vector< std::size_t > next(transformed.size(), 0U);
        for (std::size_t index = 0U; index < transformed.size(); ++index)
        {
            std::uint8_t const symbol = std::to_integer< std::uint8_t >(transformed[index]);
            next[positions[symbol]++] = index;
        }
 
        std::vector< std::byte > output;
        output.reserve(std::min(block_size_limit, maximum_output_size));
        std::size_t row = original_pointer;
        std::optional< std::byte > previous_byte;
        std::uint8_t repeated_bytes = 0U;
        for (std::size_t index = 0U; index < transformed.size(); ++index)
        {
            row = next[row];
            std::byte const value = transformed[row];
            if (repeated_bytes == 3U)
            {
                std::size_t const additional_count = std::to_integer< std::uint8_t >(value);
                if (!previous_byte.has_value() || output.size() > maximum_output_size || additional_count > maximum_output_size - output.size())
                {
                    throw compression_error(error_code::output_limit_exceeded, format::bzip2, "decompressed bzip2 block exceeds its limit");
                }
                output.insert(output.end(), additional_count, *previous_byte);
                previous_byte.reset();
                repeated_bytes = 0U;
                continue;
            }
            if (output.size() >= maximum_output_size)
            {
                throw compression_error(error_code::output_limit_exceeded, format::bzip2, "decompressed bzip2 block exceeds its limit");
            }
            output.push_back(value);
            if (previous_byte.has_value() && *previous_byte == value)
            {
                ++repeated_bytes;
            }
            else
            {
                previous_byte = value;
                repeated_bytes = 0U;
            }
        }
 
        std::uint32_t const actual_block_crc = crc32(output);
        if (actual_block_crc != expected_block_crc)
        {
            throw compression_error(error_code::invalid_data, format::bzip2, "bzip2 block checksum mismatch");
        }
        combined_crc = ((combined_crc << 1U) | (combined_crc >> 31U)) ^ actual_block_crc;
        return output;
    }
 
    /**
     * @brief MSB-first bit writer backed by an STL output iterator.
     * @tparam output_iterator Destination accepting byte assignments.
     */
    template < typename output_iterator >
    class iterator_bit_writer
    {
      public:
        /**
         * @brief Constructs a writer owning an output iterator.
         * @param output Destination iterator.
         */
        explicit iterator_bit_writer(output_iterator output) : m_output(std::move(output))
        {
        }
 
        /**
         * @brief Appends a big-endian bit field.
         * @param value Value whose low @p count bits are emitted most significant first.
         * @param count Number of bits to emit, from zero through 64.
         * @throws compression_error If @p count exceeds 64.
         */
        void write_bits(std::uint64_t value, std::uint8_t count)
        {
            if (count > 64U)
            {
                throw compression_error(error_code::invalid_data, format::bzip2, "oversized bzip2 output bit field");
            }
            for (std::uint8_t remaining = count; remaining > 0U; --remaining)
            {
                m_pending = static_cast< std::uint8_t >(m_pending | static_cast< std::uint8_t >(((value >> (remaining - 1U)) & 1U) << (7U - m_bit_count)));
                ++m_bit_count;
                if (m_bit_count == 8U)
                {
                    implementation::write_byte(m_output, static_cast< std::byte >(m_pending));
                    m_pending = 0U;
                    m_bit_count = 0U;
                }
            }
        }
 
        /**
         * @brief Pads the final byte with zeros and releases the output iterator.
         * @return Destination iterator advanced past all emitted bytes.
         */
        [[nodiscard]] output_iterator finish()
        {
            if (m_bit_count != 0U)
            {
                implementation::write_byte(m_output, static_cast< std::byte >(m_pending));
                m_pending = 0U;
                m_bit_count = 0U;
            }
            return std::move(m_output);
        }
 
      private:
        output_iterator m_output;
        std::uint8_t m_pending = 0U;
        std::uint8_t m_bit_count = 0U;
    };
 
    /**
     * @brief MSB-first bit reader backed by a single-pass byte reader.
     * @tparam byte_reader_type Source reader providing read().
     */
    template < typename byte_reader_type >
    class iterator_bit_reader
    {
      public:
        /**
         * @brief Constructs a bit reader over a byte reader.
         * @param input Borrowed reader that must outlive this object.
         */
        explicit iterator_bit_reader(byte_reader_type& input) noexcept : m_input(input)
        {
        }
 
        /**
         * @brief Consumes a big-endian bit field containing at most 64 bits.
         * @param count Number of bits to consume.
         * @return Field value with the earliest bit as the most significant bit.
         * @throws compression_error If the count exceeds 64 or input is truncated.
         */
        [[nodiscard]] std::uint64_t read_bits(std::uint8_t count)
        {
            if (count > 64U)
            {
                throw compression_error(error_code::invalid_data, format::bzip2, "oversized bzip2 input bit field");
            }
            std::uint64_t result = 0U;
            for (std::uint8_t index = 0U; index < count; ++index)
            {
                if (m_bits_remaining == 0U)
                {
                    std::byte value{};
                    if (!m_input.read(value))
                    {
                        throw compression_error(error_code::invalid_data, format::bzip2, "truncated bzip2 bitstream");
                    }
                    m_current = std::to_integer< std::uint8_t >(value);
                    m_bits_remaining = 8U;
                }
                result = (result << 1U) | ((m_current >> (m_bits_remaining - 1U)) & 1U);
                --m_bits_remaining;
            }
            return result;
        }
 
        /** Discard padding through the next byte boundary. */
        void align_to_byte() noexcept
        {
            m_bits_remaining = 0U;
        }
 
      private:
        byte_reader_type& m_input;
        std::uint8_t m_current = 0U;
        std::uint8_t m_bits_remaining = 0U;
    };
 
    /**
     * @brief Compresses an iterator range as a native bzip2 stream.
     * @tparam input_iterator Single-pass byte iterator.
     * @tparam sentinel Sentinel for @p first.
     * @tparam output_iterator Destination byte iterator.
     * @param first First source byte.
     * @param last Sentinel past the source.
     * @param output Destination iterator.
     * @param options Compression level from 1 through 9.
     * @return Destination advanced past the stream trailer.
     */
    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)
    {
        std::int32_t const level = options.level.value_or(9);
        if (level < 1 || level > 9)
        {
            throw compression_error(error_code::invalid_option, format::bzip2, "bzip2 compression level must be between 1 and 9");
        }
        iterator_bit_writer< output_iterator > writer(std::move(output));
        writer.write_bits(0x425a68U, 24U);
        writer.write_bits(static_cast< std::uint8_t >('0' + level), 8U);
        std::size_t const transformed_limit = static_cast< std::size_t >(level) * 100000U - 20U;
        std::size_t const source_block_limit = transformed_limit * 4U / 5U;
        std::vector< std::byte > block;
        block.reserve(source_block_limit);
        std::uint32_t combined_crc = 0U;
        while (first != last)
        {
            block.clear();
            while (first != last && block.size() < source_block_limit)
            {
                block.push_back(implementation::to_byte(*first));
                ++first;
            }
            compress_block(writer, block, combined_crc);
        }
        writer.write_bits(0x177245385090ULL, 48U);
        writer.write_bits(combined_crc, 32U);
        return writer.finish();
    }
 
    /**
     * @brief Decompresses one or more native bzip2 streams.
     * @tparam input_iterator Single-pass byte iterator.
     * @tparam sentinel Sentinel for @p first.
     * @tparam output_iterator Destination byte iterator.
     * @param first First compressed byte.
     * @param last Sentinel past the compressed input.
     * @param output Destination iterator.
     * @param options Output limit and concatenated-stream policy.
     * @return Destination advanced past the uncompressed data.
     */
    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)
    {
        implementation::byte_reader< input_iterator, sentinel > source(std::move(first), std::move(last));
        std::size_t total_output = 0U;
        bool decoded_stream = false;
        do
        {
            if (decoded_stream && !options.allow_concatenated_streams)
            {
                throw compression_error(error_code::trailing_data, format::bzip2, "bzip2 stream contains trailing data");
            }
            iterator_bit_reader< decltype(source) > reader(source);
            if (reader.read_bits(16U) != 0x425aU || reader.read_bits(8U) != 0x68U)
            {
                throw compression_error(error_code::invalid_data, format::bzip2, "invalid bzip2 stream header");
            }
            std::uint8_t const level_byte = static_cast< std::uint8_t >(reader.read_bits(8U));
            if (level_byte < static_cast< std::uint8_t >('1') || level_byte > static_cast< std::uint8_t >('9'))
            {
                throw compression_error(error_code::invalid_data, format::bzip2, "invalid bzip2 block-size level");
            }
            std::size_t const block_size_limit = static_cast< std::size_t >(level_byte - static_cast< std::uint8_t >('0')) * 100000U;
            std::uint32_t combined_crc = 0U;
            while (true)
            {
                std::uint64_t const magic = reader.read_bits(48U);
                if (magic == 0x177245385090ULL)
                {
                    if (combined_crc != static_cast< std::uint32_t >(reader.read_bits(32U)))
                    {
                        throw compression_error(error_code::invalid_data, format::bzip2, "bzip2 stream checksum mismatch");
                    }
                    reader.align_to_byte();
                    break;
                }
                if (magic != 0x314159265359ULL)
                {
                    throw compression_error(error_code::invalid_data, format::bzip2, "invalid bzip2 block magic");
                }
                std::vector< std::byte > block = decompress_block(reader, block_size_limit, options.maximum_output_size - std::min(total_output, options.maximum_output_size), combined_crc);
                for (std::byte value : block)
                {
                    if (total_output == options.maximum_output_size)
                    {
                        throw compression_error(error_code::output_limit_exceeded, format::bzip2, "decompressed bzip2 output exceeds its limit");
                    }
                    implementation::write_byte(output, value);
                    ++total_output;
                }
            }
            decoded_stream = true;
        } while (!source.empty());
        return output;
    }
 
} // namespace rpnx::compression::bzip2_codec
 
#endif