xz.hpp

Go to the documentation of this file.

#ifndef RPNX_COMPRESSION_IMPLEMENTATION_XZ_HPP
#define RPNX_COMPRESSION_IMPLEMENTATION_XZ_HPP
 
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <limits>
#include <optional>
#include <span>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>
 
#include <rpnx/compression/implementation/io.hpp>
 
/**
 * @file
 * @brief Native xz container, LZMA2, and range-coding implementation.
 */
 
/** @brief Internal implementation of xz and its LZMA2 payload format. */
namespace rpnx::compression::xz_codec
{
 
    /** @brief LZMA probability-model total. */
    inline constexpr std::uint32_t probability_total = 1U << 11U;
    /** @brief Adaptation shift applied after every probability decision. */
    inline constexpr std::uint32_t probability_move_bits = 5U;
    /** @brief Range threshold below which the arithmetic coder normalizes. */
    inline constexpr std::uint32_t range_top = 1U << 24U;
    /** @brief Number of LZMA state-machine states. */
    inline constexpr std::size_t state_count = 12U;
    /** @brief Maximum number of position states. */
    inline constexpr std::size_t position_state_count = 16U;
    /** @brief Number of literal contexts retained by the supported properties. */
    inline constexpr std::size_t literal_coder_count = 16U;
    /** @brief Probability count in one LZMA literal coder. */
    inline constexpr std::size_t literal_coder_size = 0x300U;
 
    /** Size metadata collected while decoding one xz block. */
    struct block_record
    {
        std::uint64_t unpadded_size;     ///< Header, payload, and check size before four-byte padding.
        std::uint64_t uncompressed_size; ///< Number of bytes produced by the block.
    };
 
    /** Adaptive probability tables and state used by LZMA. */
    struct lzma_model
    {
        /** Probability tables for the three LZMA match-length ranges. */
        struct length_model
        {
            std::uint16_t choice = probability_total / 2U;  ///< Selects the low range.
            std::uint16_t choice2 = probability_total / 2U; ///< Selects the middle or high range.
            std::array< std::array< std::uint16_t, 8U >, position_state_count > low{}; ///< Low-range trees by position state.
            std::array< std::array< std::uint16_t, 8U >, position_state_count > mid{}; ///< Middle-range trees by position state.
            std::array< std::uint16_t, 256U > high{}; ///< High-range probability tree.
        };
 
        std::uint32_t rep0 = 0U; ///< Most recent repeated match distance minus one.
        std::uint32_t rep1 = 0U; ///< Second most recent repeated distance minus one.
        std::uint32_t rep2 = 0U; ///< Third most recent repeated distance minus one.
        std::uint32_t rep3 = 0U; ///< Fourth most recent repeated distance minus one.
        std::uint8_t state = 0U; ///< Current LZMA literal/match state.
        std::uint8_t literal_context_bits = 3U; ///< Number of high previous-byte bits in a literal context.
        std::uint8_t literal_position_bits = 0U; ///< Number of low position bits in a literal context.
        std::uint8_t position_bits = 2U; ///< Number of low position bits selecting a position state.
        std::array< std::array< std::uint16_t, position_state_count >, state_count > is_match{}; ///< Literal-versus-match probabilities.
        std::array< std::uint16_t, state_count > is_rep{}; ///< New-versus-repeated match probabilities.
        std::array< std::uint16_t, state_count > is_rep0{}; ///< Most-recent-distance probabilities.
        std::array< std::uint16_t, state_count > is_rep1{}; ///< Second-distance probabilities.
        std::array< std::uint16_t, state_count > is_rep2{}; ///< Third-versus-fourth distance probabilities.
        std::array< std::array< std::uint16_t, position_state_count >, state_count > is_rep0_long{}; ///< Short repeated-match probabilities.
        std::array< std::array< std::uint16_t, 64U >, 4U > distance_slot{}; ///< Distance-slot trees by match-length state.
        std::array< std::uint16_t, 114U > distance_special{}; ///< Probability trees for middle distance bits.
        std::array< std::uint16_t, 16U > distance_align{}; ///< Reversed tree for low aligned distance bits.
        length_model match_length; ///< Length model for new matches.
        length_model repeated_length; ///< Length model for repeated matches.
        std::array< std::array< std::uint16_t, literal_coder_size >, literal_coder_count > literal{}; ///< Literal probability trees by context.
 
        /** Reset the probability model and recent-match state. */
        void reset()
        {
            rep0 = 0U;
            rep1 = 0U;
            rep2 = 0U;
            rep3 = 0U;
            state = 0U;
            fill_probabilities();
        }
 
        /**
         * @brief Configures lc, lp, and pb from one LZMA properties byte.
         * @param properties Encoded LZMA lc/lp/pb value.
         * @throws compression_error If the value or supported context sum is invalid.
         */
        void set_properties(std::uint8_t properties)
        {
            if (properties > 224U)
            {
                throw compression_error(error_code::invalid_data, format::xz, "invalid LZMA properties byte");
            }
            position_bits = static_cast< std::uint8_t >(properties / 45U);
            std::uint8_t const remainder = static_cast< std::uint8_t >(properties % 45U);
            literal_position_bits = static_cast< std::uint8_t >(remainder / 9U);
            literal_context_bits = static_cast< std::uint8_t >(remainder % 9U);
            if (literal_context_bits + literal_position_bits > 4U)
            {
                throw compression_error(error_code::invalid_data, format::xz, "invalid LZMA literal context properties");
            }
            reset();
        }
 
      private:
        /** Initialize every adaptive probability to one half. */
        void fill_probabilities()
        {
            constexpr std::uint16_t initial = probability_total / 2U;
            for (std::array< std::uint16_t, position_state_count >& probabilities : is_match)
            {
                probabilities.fill(initial);
            }
            is_rep.fill(initial);
            is_rep0.fill(initial);
            is_rep1.fill(initial);
            is_rep2.fill(initial);
            for (std::array< std::uint16_t, position_state_count >& probabilities : is_rep0_long)
            {
                probabilities.fill(initial);
            }
            for (std::array< std::uint16_t, 64U >& probabilities : distance_slot)
            {
                probabilities.fill(initial);
            }
            distance_special.fill(initial);
            distance_align.fill(initial);
            initialize_length(match_length);
            initialize_length(repeated_length);
            for (std::array< std::uint16_t, literal_coder_size >& probabilities : literal)
            {
                probabilities.fill(initial);
            }
        }
 
        /** Initialize one match-length probability table. */
        static void initialize_length(length_model& model)
        {
            constexpr std::uint16_t initial = probability_total / 2U;
            model.choice = initial;
            model.choice2 = initial;
            for (std::array< std::uint16_t, 8U >& probabilities : model.low)
            {
                probabilities.fill(initial);
            }
            for (std::array< std::uint16_t, 8U >& probabilities : model.mid)
            {
                probabilities.fill(initial);
            }
            model.high.fill(initial);
        }
    };
 
    /** One-shot LZMA range decoder. */
    class range_decoder
    {
      public:
        /**
         * @brief Initializes a decoder from one complete LZMA chunk.
         * @param input Complete range-coded chunk retained for this object's lifetime.
         */
        explicit range_decoder(std::span< std::byte const > input) : m_input(input)
        {
            if (input.size() < 5U)
            {
                throw compression_error(error_code::invalid_data, format::xz, "truncated LZMA range-coded chunk");
            }
            for (std::size_t index = 0U; index < 5U; ++index)
            {
                m_code = (m_code << 8U) | read_byte();
            }
        }
 
        /**
         * @brief Decodes one adaptive binary symbol.
         * @param probability Probability updated in place after the decision.
         * @return Zero or one.
         */
        [[nodiscard]] std::uint8_t decode_bit(std::uint16_t& probability)
        {
            normalize();
            std::uint32_t const bound = (m_range >> 11U) * probability;
            if (m_code < bound)
            {
                m_range = bound;
                probability = static_cast< std::uint16_t >(probability + ((probability_total - probability) >> probability_move_bits));
                return 0U;
            }
            m_range -= bound;
            m_code -= bound;
            probability = static_cast< std::uint16_t >(probability - (probability >> probability_move_bits));
            return 1U;
        }
 
        /**
         * @brief Decodes a most-significant-bit-first probability tree.
         * @param probabilities Tree probabilities updated in place.
         * @param leaf_base First leaf index, which must be a power of two.
         * @return Tree leaf index including @p leaf_base.
         */
        [[nodiscard]] std::uint32_t decode_tree(std::span< std::uint16_t > probabilities, std::uint32_t leaf_base)
        {
            std::uint32_t symbol = 1U;
            while (symbol < leaf_base)
            {
                if (symbol >= probabilities.size())
                {
                    throw compression_error(error_code::invalid_data, format::xz, "invalid LZMA probability tree");
                }
                symbol = (symbol << 1U) | decode_bit(probabilities[symbol]);
            }
            return symbol;
        }
 
        /**
         * @brief Decodes a least-significant-bit-first probability tree.
         * @param probabilities Backing probability table updated in place.
         * @param base Offset immediately before the tree's root.
         * @param bit_count Tree depth.
         * @return Reversed decoded value.
         */
        [[nodiscard]] std::uint32_t decode_reverse_tree(std::span< std::uint16_t > probabilities, std::ptrdiff_t base, std::uint8_t bit_count)
        {
            std::uint32_t symbol = 1U;
            std::uint32_t value = 0U;
            for (std::uint8_t bit_index = 0U; bit_index < bit_count; ++bit_index)
            {
                std::ptrdiff_t const probability_index = base + static_cast< std::ptrdiff_t >(symbol);
                if (probability_index < 0 || static_cast< std::size_t >(probability_index) >= probabilities.size())
                {
                    throw compression_error(error_code::invalid_data, format::xz, "invalid reversed LZMA probability tree");
                }
                std::uint8_t const bit = decode_bit(probabilities[static_cast< std::size_t >(probability_index)]);
                symbol = (symbol << 1U) | bit;
                value |= static_cast< std::uint32_t >(bit) << bit_index;
            }
            return value;
        }
 
        /**
         * @brief Decodes equiprobable direct bits.
         * @param bit_count Number of bits to decode.
         * @return Decoded most-significant-bit-first value.
         */
        [[nodiscard]] std::uint32_t decode_direct(std::uint8_t bit_count)
        {
            std::uint32_t value = 0U;
            for (std::uint8_t bit_index = 0U; bit_index < bit_count; ++bit_index)
            {
                normalize();
                m_range >>= 1U;
                std::uint8_t bit = 0U;
                if (m_code >= m_range)
                {
                    m_code -= m_range;
                    bit = 1U;
                }
                value = (value << 1U) | bit;
            }
            return value;
        }
 
        /** Validate exact consumption and the LZMA terminal range state. */
        void finish()
        {
            normalize();
            if (m_position != m_input.size() || m_code != 0U)
            {
                throw compression_error(error_code::invalid_data, format::xz, "invalid LZMA chunk termination");
            }
        }
 
      private:
        [[nodiscard]] std::uint8_t read_byte()
        {
            if (m_position >= m_input.size())
            {
                throw compression_error(error_code::invalid_data, format::xz, "truncated LZMA range-coded chunk");
            }
            return std::to_integer< std::uint8_t >(m_input[m_position++]);
        }
 
        void normalize()
        {
            if (m_range < range_top)
            {
                m_range <<= 8U;
                m_code = (m_code << 8U) | read_byte();
            }
        }
 
        std::span< std::byte const > m_input;
        std::size_t m_position = 0U;
        std::uint32_t m_range = std::numeric_limits< std::uint32_t >::max();
        std::uint32_t m_code = 0U;
    };
 
    /** One-shot LZMA range encoder used by the deterministic literal encoder. */
    class range_encoder
    {
      public:
        /**
         * @brief Encodes one adaptive binary symbol.
         * @param probability Probability updated in place after encoding.
         * @param bit Symbol value, either zero or one.
         */
        void encode_bit(std::uint16_t& probability, std::uint8_t bit)
        {
            std::uint32_t const bound = (m_range >> 11U) * probability;
            if (bit == 0U)
            {
                m_range = bound;
                probability = static_cast< std::uint16_t >(probability + ((probability_total - probability) >> probability_move_bits));
            }
            else
            {
                m_low += bound;
                m_range -= bound;
                probability = static_cast< std::uint16_t >(probability - (probability >> probability_move_bits));
            }
            if (m_range < range_top)
            {
                m_range <<= 8U;
                shift_low();
            }
        }
 
        /**
         * @brief Finishes the range stream.
         * @return Five-byte-terminated encoded representation.
         */
        [[nodiscard]] std::vector< std::byte > finish()
        {
            for (std::size_t index = 0U; index < 5U; ++index)
            {
                shift_low();
            }
            return std::move(m_output);
        }
 
      private:
        void shift_low()
        {
            std::uint32_t const low = static_cast< std::uint32_t >(m_low);
            std::uint32_t const high = static_cast< std::uint32_t >(m_low >> 32U);
            if (low < 0xff000000U || high != 0U)
            {
                std::uint8_t cached = m_cache;
                do
                {
                    m_output.push_back(static_cast< std::byte >(cached + high));
                    cached = 0xffU;
                } while (--m_cache_size != 0U);
                m_cache = static_cast< std::uint8_t >(low >> 24U);
            }
            ++m_cache_size;
            m_low = static_cast< std::uint64_t >(low & 0x00ffffffU) << 8U;
        }
 
        std::vector< std::byte > m_output;
        std::uint64_t m_low = 0U;
        std::uint32_t m_range = std::numeric_limits< std::uint32_t >::max();
        std::uint8_t m_cache = 0U;
        std::size_t m_cache_size = 1U;
    };
 
    /**
     * @brief Computes the reflected CRC-32 used by xz metadata and checks.
     * @param input Bytes to checksum.
     * @return Finalized 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 ^= std::to_integer< std::uint8_t >(value);
            for (std::uint8_t bit = 0U; bit < 8U; ++bit)
            {
                crc = (crc & 1U) != 0U ? (crc >> 1U) ^ 0xedb88320U : crc >> 1U;
            }
        }
        return ~crc;
    }
 
    /** Incremental CRC-64/XZ accumulator for streamed block data. */
    class crc64_accumulator
    {
      public:
        /**
         * @brief Includes one byte in the checksum.
         * @param value Next byte in stream order.
         */
        void update(std::byte value) noexcept
        {
            m_crc ^= std::to_integer< std::uint8_t >(value);
            for (std::uint8_t bit = 0U; bit < 8U; ++bit)
            {
                m_crc = (m_crc & 1U) != 0U ? (m_crc >> 1U) ^ 0xc96c5795d7870f42ULL : m_crc >> 1U;
            }
        }
 
        /**
         * @brief Returns the checksum for all supplied bytes.
         * @return Finalized CRC-64/XZ value.
         */
        [[nodiscard]] std::uint64_t value() const noexcept
        {
            return ~m_crc;
        }
 
      private:
        std::uint64_t m_crc = std::numeric_limits< std::uint64_t >::max();
    };
 
    /**
     * @brief Reads a fixed-width little-endian integer.
     * @param input Source bytes.
     * @param position Current position, advanced by @p byte_count.
     * @param byte_count Width from zero through eight bytes.
     * @return Decoded value.
     */
    [[nodiscard]] inline std::uint64_t read_little_endian(std::span< std::byte const > input, std::size_t& position, std::uint8_t byte_count)
    {
        if (position > input.size() || byte_count > input.size() - position)
        {
            throw compression_error(error_code::invalid_data, format::xz, "truncated xz integer");
        }
        std::uint64_t value = 0U;
        for (std::uint8_t byte_index = 0U; byte_index < byte_count; ++byte_index)
        {
            value |= static_cast< std::uint64_t >(std::to_integer< std::uint8_t >(input[position++])) << (byte_index * 8U);
        }
        return value;
    }
 
    /**
     * @brief Decodes one minimal xz variable-length integer.
     * @param input Source bytes.
     * @param position Current position, advanced past the encoded integer.
     * @return Decoded unsigned value.
     * @throws compression_error If the integer is truncated, non-minimal, or oversized.
     */
    [[nodiscard]] inline std::uint64_t read_variable_integer(std::span< std::byte const > input, std::size_t& position)
    {
        std::uint64_t value = 0U;
        for (std::uint8_t byte_index = 0U; byte_index < 9U; ++byte_index)
        {
            if (position >= input.size())
            {
                throw compression_error(error_code::invalid_data, format::xz, "truncated xz variable-length integer");
            }
            std::uint8_t const byte = std::to_integer< std::uint8_t >(input[position++]);
            if (byte_index != 0U && byte == 0U)
            {
                throw compression_error(error_code::invalid_data, format::xz, "non-minimal xz variable-length integer");
            }
            value |= static_cast< std::uint64_t >(byte & 0x7fU) << (byte_index * 7U);
            if ((byte & 0x80U) == 0U)
            {
                return value;
            }
        }
        throw compression_error(error_code::invalid_data, format::xz, "oversized xz variable-length integer");
    }
 
    /**
     * @brief Returns the number of bytes in an xz integrity check.
     * @param check_identifier Four-bit xz check identifier.
     * @return Encoded check size.
     */
    [[nodiscard]] inline std::size_t check_size(std::uint8_t check_identifier)
    {
        constexpr std::array< std::size_t, 16U > sizes{0U, 4U, 4U, 4U, 8U, 8U, 8U, 16U, 16U, 16U, 32U, 32U, 32U, 64U, 64U, 64U};
        return sizes[check_identifier];
    }
 
    /**
     * @brief Updates an LZMA state after decoding a literal.
     * @param state State-machine value updated in place.
     */
    inline void update_literal_state(std::uint8_t& state) noexcept
    {
        if (state <= 3U)
        {
            state = 0U;
        }
        else if (state <= 9U)
        {
            state = static_cast< std::uint8_t >(state - 3U);
        }
        else
        {
            state = static_cast< std::uint8_t >(state - 6U);
        }
    }
 
    /**
     * @brief Decodes one LZMA match length.
     * @param decoder Range decoder.
     * @param model Match or repeated-match length model updated in place.
     * @param position_state Current low dictionary-position state.
     * @return Match length of at least two bytes.
     */
    [[nodiscard]] inline std::uint32_t decode_length(range_decoder& decoder, lzma_model::length_model& model, std::size_t position_state)
    {
        if (decoder.decode_bit(model.choice) == 0U)
        {
            return 2U + decoder.decode_tree(model.low[position_state], 8U) - 8U;
        }
        if (decoder.decode_bit(model.choice2) == 0U)
        {
            return 10U + decoder.decode_tree(model.mid[position_state], 8U) - 8U;
        }
        return 18U + decoder.decode_tree(model.high, 256U) - 256U;
    }
 
    /**
     * @brief Copies one validated LZMA match into the output dictionary.
     * @param output Stream output and dictionary storage.
     * @param history_begin Start of the current LZMA2 dictionary history.
     * @param dictionary_size Declared maximum dictionary size.
     * @param distance Zero-based match distance.
     * @param length Number of bytes to reproduce.
     * @param output_limit Absolute output-size limit.
     */
    inline void copy_match(std::vector< std::byte >& output, std::size_t history_begin, std::uint32_t dictionary_size, std::uint32_t distance, std::uint32_t length, std::size_t output_limit)
    {
        std::size_t const history_size = output.size() - history_begin;
        if (distance >= history_size || distance >= dictionary_size)
        {
            throw compression_error(error_code::invalid_data, format::xz, "LZMA match distance " + std::to_string(distance) + " exceeds history " + std::to_string(history_size));
        }
        if (output.size() > output_limit || length > output_limit - output.size())
        {
            throw compression_error(error_code::output_limit_exceeded, format::xz, "decompressed xz output exceeds its limit");
        }
        for (std::uint32_t index = 0U; index < length; ++index)
        {
            output.push_back(output[output.size() - distance - 1U]);
        }
    }
 
    /**
     * @brief Decodes one LZMA range-coded chunk into an LZMA2 dictionary.
     * @param encoded Complete range-coded chunk.
     * @param uncompressed_size Exact number of bytes the chunk must produce.
     * @param model Adaptive model retained across eligible chunks.
     * @param output Stream output and dictionary storage.
     * @param history_begin Start of the current LZMA2 dictionary history.
     * @param dictionary_size Declared maximum dictionary size.
     * @param output_limit Absolute output-size limit.
     * @param dictionary_position_offset Position adjustment for chunk-local buffers.
     */
    inline void decode_lzma_chunk(std::span< std::byte const > encoded, std::size_t uncompressed_size, lzma_model& model, std::vector< std::byte >& output, std::size_t history_begin, std::uint32_t dictionary_size, std::size_t output_limit, std::size_t dictionary_position_offset = 0U)
    {
        if (output.size() > output_limit || uncompressed_size > output_limit - output.size())
        {
            throw compression_error(error_code::output_limit_exceeded, format::xz, "decompressed xz output exceeds its limit");
        }
        std::size_t const target_size = output.size() + uncompressed_size;
        range_decoder decoder(encoded);
        while (output.size() < target_size)
        {
            std::size_t const dictionary_position = dictionary_position_offset + output.size() - history_begin;
            std::size_t const position_state = dictionary_position & ((std::size_t{1U} << model.position_bits) - 1U);
            if (decoder.decode_bit(model.is_match[model.state][position_state]) == 0U)
            {
                std::uint8_t const previous = dictionary_position == 0U ? 0U : std::to_integer< std::uint8_t >(output.back());
                std::size_t const literal_context = ((dictionary_position & ((std::size_t{1U} << model.literal_position_bits) - 1U)) << model.literal_context_bits) | (previous >> (8U - model.literal_context_bits));
                std::array< std::uint16_t, literal_coder_size >& probabilities = model.literal[literal_context];
                std::uint32_t symbol = 1U;
                if (model.state < 7U)
                {
                    symbol = decoder.decode_tree(probabilities, 0x100U);
                }
                else
                {
                    if (model.rep0 >= dictionary_position || model.rep0 >= dictionary_size)
                    {
                        throw compression_error(error_code::invalid_data, format::xz, "LZMA literal match byte exceeds history");
                    }
                    std::uint32_t match_byte = static_cast< std::uint32_t >(std::to_integer< std::uint8_t >(output[output.size() - model.rep0 - 1U])) << 1U;
                    std::uint32_t offset = 0x100U;
                    while (symbol < 0x100U)
                    {
                        std::uint32_t const match_bit = match_byte & offset;
                        match_byte <<= 1U;
                        std::size_t const probability_index = offset + match_bit + symbol;
                        std::uint8_t const bit = decoder.decode_bit(probabilities[probability_index]);
                        symbol = (symbol << 1U) | bit;
                        offset &= bit != 0U ? match_bit : ~match_bit;
                    }
                }
                output.push_back(static_cast< std::byte >(symbol));
                update_literal_state(model.state);
                continue;
            }
 
            std::uint32_t length = 0U;
            if (decoder.decode_bit(model.is_rep[model.state]) == 0U)
            {
                model.state = model.state < 7U ? 7U : 10U;
                model.rep3 = model.rep2;
                model.rep2 = model.rep1;
                model.rep1 = model.rep0;
                length = decode_length(decoder, model.match_length, position_state);
                std::size_t const distance_state = std::min< std::size_t >(length - 2U, 3U);
                std::uint32_t const slot = decoder.decode_tree(model.distance_slot[distance_state], 64U) - 64U;
                if (slot < 4U)
                {
                    model.rep0 = slot;
                }
                else
                {
                    std::uint8_t const additional_bits = static_cast< std::uint8_t >((slot >> 1U) - 1U);
                    model.rep0 = 2U + (slot & 1U);
                    if (slot < 14U)
                    {
                        model.rep0 <<= additional_bits;
                        std::ptrdiff_t const base = static_cast< std::ptrdiff_t >(model.rep0) - static_cast< std::ptrdiff_t >(slot) - 1;
                        model.rep0 += decoder.decode_reverse_tree(model.distance_special, base, additional_bits);
                    }
                    else
                    {
                        std::uint8_t const direct_bits = static_cast< std::uint8_t >(additional_bits - 4U);
                        model.rep0 = (model.rep0 << direct_bits) | decoder.decode_direct(direct_bits);
                        model.rep0 <<= 4U;
                        model.rep0 += decoder.decode_reverse_tree(model.distance_align, 0, 4U);
                    }
                }
            }
            else
            {
                if (decoder.decode_bit(model.is_rep0[model.state]) == 0U)
                {
                    if (decoder.decode_bit(model.is_rep0_long[model.state][position_state]) == 0U)
                    {
                        model.state = model.state < 7U ? 9U : 11U;
                        length = 1U;
                    }
                }
                else
                {
                    std::uint32_t distance = 0U;
                    if (decoder.decode_bit(model.is_rep1[model.state]) == 0U)
                    {
                        distance = model.rep1;
                    }
                    else
                    {
                        if (decoder.decode_bit(model.is_rep2[model.state]) == 0U)
                        {
                            distance = model.rep2;
                        }
                        else
                        {
                            distance = model.rep3;
                            model.rep3 = model.rep2;
                        }
                        model.rep2 = model.rep1;
                    }
                    model.rep1 = model.rep0;
                    model.rep0 = distance;
                }
                if (length == 0U)
                {
                    model.state = model.state < 7U ? 8U : 11U;
                    length = decode_length(decoder, model.repeated_length, position_state);
                }
            }
            if (length > target_size - output.size())
            {
                throw compression_error(error_code::invalid_data, format::xz, "LZMA match exceeds its chunk output size");
            }
            copy_match(output, history_begin, dictionary_size, model.rep0, length, output_limit);
        }
        decoder.finish();
    }
 
    /**
     * @brief Encodes a literal-only LZMA range-coded chunk.
     * @param input Source literals.
     * @param model Adaptive model updated in place.
     * @param dictionary_position Absolute dictionary position of the first literal.
     * @param previous_byte Byte preceding the chunk, or zero at dictionary start.
     * @return Range-coded chunk payload.
     */
    [[nodiscard]] inline std::vector< std::byte > compress_lzma_literals(std::span< std::byte const > input, lzma_model& model, std::size_t dictionary_position, std::uint8_t previous_byte)
    {
        range_encoder encoder;
        for (std::byte value : input)
        {
            std::size_t const position_state = dictionary_position & ((std::size_t{1U} << model.position_bits) - 1U);
            encoder.encode_bit(model.is_match[model.state][position_state], 0U);
            std::size_t const literal_context = ((dictionary_position & ((std::size_t{1U} << model.literal_position_bits) - 1U)) << model.literal_context_bits) | (previous_byte >> (8U - model.literal_context_bits));
            std::array< std::uint16_t, literal_coder_size >& probabilities = model.literal[literal_context];
            std::uint32_t symbol = 1U;
            std::uint8_t const byte = std::to_integer< std::uint8_t >(value);
            for (std::uint8_t bit_index = 0U; bit_index < 8U; ++bit_index)
            {
                std::uint8_t const bit = static_cast< std::uint8_t >((byte >> (7U - bit_index)) & 1U);
                encoder.encode_bit(probabilities[symbol], bit);
                symbol = (symbol << 1U) | bit;
            }
            update_literal_state(model.state);
            previous_byte = byte;
            ++dictionary_position;
        }
        return encoder.finish();
    }
 
    /**
     * @brief Decodes the one-byte LZMA2 dictionary-size property.
     * @param properties Encoded property from the xz block filter flags.
     * @return Dictionary size in bytes.
     */
    [[nodiscard]] inline std::uint32_t decode_dictionary_size(std::uint8_t properties)
    {
        if (properties > 40U)
        {
            throw compression_error(error_code::unsupported_feature, format::xz, "xz LZMA2 dictionary exceeds 4 GiB");
        }
        if (properties == 40U)
        {
            return std::numeric_limits< std::uint32_t >::max();
        }
        std::uint32_t size = 2U | (properties & 1U);
        size <<= static_cast< std::uint8_t >(properties / 2U + 11U);
        return size;
    }
 
    /**
     * @brief Compresses an iterator range as an xz stream containing LZMA2.
     * @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 0 through 9.
     * @return Destination advanced past the xz footer.
     */
    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(6);
        if (level < 0 || level > 9)
        {
            throw compression_error(error_code::invalid_option, format::xz, "xz compression level must be between 0 and 9");
        }
        auto write_bytes = [&](std::span< std::byte const > bytes)
        {
            for (std::byte value : bytes)
            {
                implementation::write_byte(output, value);
            }
        };
        auto write_little_endian = [&](std::uint64_t value, std::uint8_t count)
        {
            for (std::uint8_t index = 0U; index < count; ++index)
            {
                implementation::write_byte(output, static_cast< std::byte >(value >> (index * 8U)));
            }
        };
 
        constexpr std::array< std::byte, 6U > magic{std::byte{0xfd}, std::byte{'7'}, std::byte{'z'}, std::byte{'X'}, std::byte{'Z'}, std::byte{0}};
        write_bytes(magic);
        constexpr std::array< std::byte, 2U > stream_flags{std::byte{0}, std::byte{4}};
        write_bytes(stream_flags);
        write_little_endian(crc32(stream_flags), 4U);
 
        std::array< std::byte, 12U > header{std::byte{2}, std::byte{0}, std::byte{0x21}, std::byte{1}, std::byte{22}, std::byte{0}, std::byte{0}, std::byte{0}};
        std::uint32_t const header_crc = crc32(std::span< std::byte const >(header).first(8U));
        for (std::uint8_t index = 0U; index < 4U; ++index)
        {
            header[8U + index] = static_cast< std::byte >(header_crc >> (index * 8U));
        }
        write_bytes(header);
 
        lzma_model model;
        model.set_properties(0x5dU);
        bool dictionary_reset_needed = true;
        bool properties_needed = true;
        std::size_t dictionary_position = 0U;
        std::uint8_t previous_byte = 0U;
        std::uint64_t uncompressed_size = 0U;
        std::uint64_t compressed_size = 0U;
        crc64_accumulator block_crc;
        std::vector< std::byte > chunk;
        chunk.reserve(60000U);
        while (first != last)
        {
            chunk.clear();
            while (first != last && chunk.size() < 60000U)
            {
                std::byte const value = implementation::to_byte(*first);
                ++first;
                chunk.push_back(value);
                block_crc.update(value);
                ++uncompressed_size;
            }
            lzma_model candidate_model = model;
            if (properties_needed)
            {
                candidate_model.set_properties(0x5dU);
            }
            std::vector< std::byte > compressed;
            if (level != 0)
            {
                compressed = compress_lzma_literals(chunk, candidate_model, dictionary_position, previous_byte);
            }
            std::size_t const compressed_header_size = properties_needed ? 6U : 5U;
            bool const use_compressed = level != 0 && compressed.size() <= 65536U && compressed.size() + compressed_header_size < chunk.size() + 3U;
            if (use_compressed)
            {
                std::uint8_t control = dictionary_reset_needed ? 0xe0U : properties_needed ? 0xc0U : 0x80U;
                control |= static_cast< std::uint8_t >((chunk.size() - 1U) >> 16U);
                implementation::write_byte(output, static_cast< std::byte >(control));
                implementation::write_byte(output, static_cast< std::byte >((chunk.size() - 1U) >> 8U));
                implementation::write_byte(output, static_cast< std::byte >(chunk.size() - 1U));
                implementation::write_byte(output, static_cast< std::byte >((compressed.size() - 1U) >> 8U));
                implementation::write_byte(output, static_cast< std::byte >(compressed.size() - 1U));
                compressed_size += 5U;
                if (properties_needed)
                {
                    implementation::write_byte(output, std::byte{0x5d});
                    ++compressed_size;
                }
                write_bytes(compressed);
                compressed_size += compressed.size();
                model = std::move(candidate_model);
                dictionary_reset_needed = false;
                properties_needed = false;
            }
            else
            {
                implementation::write_byte(output, dictionary_reset_needed ? std::byte{0x01} : std::byte{0x02});
                implementation::write_byte(output, static_cast< std::byte >((chunk.size() - 1U) >> 8U));
                implementation::write_byte(output, static_cast< std::byte >(chunk.size() - 1U));
                write_bytes(chunk);
                compressed_size += chunk.size() + 3U;
                if (dictionary_reset_needed)
                {
                    dictionary_reset_needed = false;
                    properties_needed = true;
                    dictionary_position = 0U;
                }
            }
            dictionary_position += chunk.size();
            previous_byte = std::to_integer< std::uint8_t >(chunk.back());
        }
        implementation::write_byte(output, std::byte{0});
        ++compressed_size;
        for (std::size_t padding = static_cast< std::size_t >((4U - compressed_size % 4U) % 4U); padding > 0U; --padding)
        {
            implementation::write_byte(output, std::byte{0});
        }
        write_little_endian(block_crc.value(), 8U);
 
        std::uint64_t const unpadded_size = header.size() + compressed_size + 8U;
        implementation::crc32_accumulator index_crc;
        std::size_t index_size = 0U;
        auto write_index_byte = [&](std::byte value)
        {
            implementation::write_byte(output, value);
            index_crc.update(value);
            ++index_size;
        };
        auto write_index_integer = [&](std::uint64_t value)
        {
            do
            {
                std::uint8_t byte = static_cast< std::uint8_t >(value & 0x7fU);
                value >>= 7U;
                if (value != 0U)
                {
                    byte |= 0x80U;
                }
                write_index_byte(static_cast< std::byte >(byte));
            } while (value != 0U);
        };
        write_index_byte(std::byte{0});
        write_index_integer(1U);
        write_index_integer(unpadded_size);
        write_index_integer(uncompressed_size);
        while (index_size % 4U != 0U)
        {
            write_index_byte(std::byte{0});
        }
        write_little_endian(index_crc.value(), 4U);
 
        std::array< std::byte, 6U > footer{static_cast< std::byte >((index_size + 4U) / 4U - 1U), static_cast< std::byte >(((index_size + 4U) / 4U - 1U) >> 8U), static_cast< std::byte >(((index_size + 4U) / 4U - 1U) >> 16U), static_cast< std::byte >(((index_size + 4U) / 4U - 1U) >> 24U), std::byte{0}, std::byte{4}};
        write_little_endian(crc32(footer), 4U);
        write_bytes(footer);
        implementation::write_byte(output, std::byte{'Y'});
        implementation::write_byte(output, std::byte{'Z'});
        return output;
    }
 
    /**
     * @brief Decompresses one or more xz streams containing LZMA2.
     * @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));
        auto read_byte = [&]() -> std::byte
        {
            std::byte value{};
            if (!source.read(value))
            {
                throw compression_error(error_code::invalid_data, format::xz, "truncated xz stream");
            }
            return value;
        };
        auto read_little_endian_source = [&](std::uint8_t count) -> std::uint64_t
        {
            std::uint64_t value = 0U;
            for (std::uint8_t index = 0U; index < count; ++index)
            {
                value |= static_cast< std::uint64_t >(std::to_integer< std::uint8_t >(read_byte())) << (index * 8U);
            }
            return value;
        };
        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::xz, "xz stream contains trailing data");
            }
            constexpr std::array< std::byte, 6U > magic{std::byte{0xfd}, std::byte{'7'}, std::byte{'z'}, std::byte{'X'}, std::byte{'Z'}, std::byte{0}};
            for (std::byte expected : magic)
            {
                if (read_byte() != expected)
                {
                    throw compression_error(error_code::invalid_data, format::xz, "invalid xz stream header");
                }
            }
            std::array< std::byte, 2U > const stream_flags{read_byte(), read_byte()};
            if (stream_flags[0U] != std::byte{0} || (std::to_integer< std::uint8_t >(stream_flags[1U]) & 0xf0U) != 0U)
            {
                throw compression_error(error_code::unsupported_feature, format::xz, "unsupported xz stream flags");
            }
            if (read_little_endian_source(4U) != crc32(stream_flags))
            {
                throw compression_error(error_code::invalid_data, format::xz, "xz stream header checksum mismatch");
            }
            std::uint8_t const check_identifier = std::to_integer< std::uint8_t >(stream_flags[1U]);
            if (check_identifier != 0U && check_identifier != 1U && check_identifier != 4U)
            {
                throw compression_error(error_code::unsupported_feature, format::xz, "unsupported xz integrity check");
            }
 
            std::vector< block_record > records;
            while (true)
            {
                std::uint8_t const encoded_header_size = std::to_integer< std::uint8_t >(read_byte());
                if (encoded_header_size == 0U)
                {
                    break;
                }
                std::size_t const header_size = (static_cast< std::size_t >(encoded_header_size) + 1U) * 4U;
                if (header_size < 8U)
                {
                    throw compression_error(error_code::invalid_data, format::xz, "invalid xz block header size");
                }
                std::vector< std::byte > header;
                header.reserve(header_size);
                header.push_back(static_cast< std::byte >(encoded_header_size));
                for (std::size_t index = 1U; index < header_size; ++index)
                {
                    header.push_back(read_byte());
                }
                std::size_t header_crc_position = header_size - 4U;
                if (read_little_endian(header, header_crc_position, 4U) != crc32(std::span< std::byte const >(header).first(header_size - 4U)))
                {
                    throw compression_error(error_code::invalid_data, format::xz, "xz block header checksum mismatch");
                }
                std::size_t header_position = 1U;
                std::uint8_t const block_flags = std::to_integer< std::uint8_t >(header[header_position++]);
                if ((block_flags & 0x3cU) != 0U)
                {
                    throw compression_error(error_code::unsupported_feature, format::xz, "unsupported xz block flags");
                }
                std::size_t const filter_count = (block_flags & 0x03U) + 1U;
                std::optional< std::uint64_t > declared_compressed_size;
                std::optional< std::uint64_t > declared_uncompressed_size;
                std::span< std::byte const > const header_fields = std::span< std::byte const >(header).first(header_size - 4U);
                if ((block_flags & 0x40U) != 0U)
                {
                    declared_compressed_size = read_variable_integer(header_fields, header_position);
                }
                if ((block_flags & 0x80U) != 0U)
                {
                    declared_uncompressed_size = read_variable_integer(header_fields, header_position);
                }
                if (filter_count != 1U || read_variable_integer(header_fields, header_position) != 0x21U || read_variable_integer(header_fields, header_position) != 1U || header_position >= header_size - 4U)
                {
                    throw compression_error(error_code::unsupported_feature, format::xz, "xz block does not contain a supported LZMA2 filter");
                }
                std::uint32_t const dictionary_size = decode_dictionary_size(std::to_integer< std::uint8_t >(header[header_position++]));
                while (header_position < header_size - 4U)
                {
                    if (header[header_position++] != std::byte{0})
                    {
                        throw compression_error(error_code::invalid_data, format::xz, "nonzero xz block-header padding");
                    }
                }
 
                std::vector< std::byte > history;
                lzma_model model;
                bool need_dictionary_reset = true;
                bool need_properties = true;
                std::size_t dictionary_position = 0U;
                std::uint64_t compressed_size = 0U;
                std::uint64_t block_output_size = 0U;
                implementation::crc32_accumulator block_crc32;
                crc64_accumulator block_crc64;
                auto emit = [&](std::byte value)
                {
                    if (total_output == options.maximum_output_size)
                    {
                        throw compression_error(error_code::output_limit_exceeded, format::xz, "decompressed xz output exceeds its limit");
                    }
                    block_crc32.update(value);
                    block_crc64.update(value);
                    implementation::write_byte(output, value);
                    ++total_output;
                    ++block_output_size;
                };
 
                while (true)
                {
                    std::uint8_t const control = std::to_integer< std::uint8_t >(read_byte());
                    ++compressed_size;
                    if (control == 0U)
                    {
                        break;
                    }
                    if (control >= 0xe0U || control == 0x01U)
                    {
                        history.clear();
                        dictionary_position = 0U;
                        need_dictionary_reset = false;
                        need_properties = true;
                    }
                    else if (need_dictionary_reset)
                    {
                        throw compression_error(error_code::invalid_data, format::xz, "LZMA2 stream does not begin with a dictionary reset");
                    }
                    if (control < 0x80U)
                    {
                        if (control > 0x02U)
                        {
                            throw compression_error(error_code::invalid_data, format::xz, "invalid LZMA2 uncompressed control byte");
                        }
                        std::size_t const chunk_size = (static_cast< std::size_t >(std::to_integer< std::uint8_t >(read_byte())) << 8U) | std::to_integer< std::uint8_t >(read_byte());
                        compressed_size += 2U;
                        for (std::size_t index = 0U; index <= chunk_size; ++index)
                        {
                            std::byte const value = read_byte();
                            ++compressed_size;
                            history.push_back(value);
                            emit(value);
                        }
                        dictionary_position += chunk_size + 1U;
                        if (history.size() > dictionary_size)
                        {
                            history.erase(history.begin(), history.begin() + static_cast< std::ptrdiff_t >(history.size() - dictionary_size));
                        }
                        continue;
                    }
 
                    std::size_t const uncompressed_size = (static_cast< std::size_t >(control & 0x1fU) << 16U) | (static_cast< std::size_t >(std::to_integer< std::uint8_t >(read_byte())) << 8U) | std::to_integer< std::uint8_t >(read_byte());
                    std::size_t const compressed_chunk_size = (static_cast< std::size_t >(std::to_integer< std::uint8_t >(read_byte())) << 8U) | std::to_integer< std::uint8_t >(read_byte());
                    compressed_size += 4U;
                    if (control >= 0xc0U)
                    {
                        model.set_properties(std::to_integer< std::uint8_t >(read_byte()));
                        ++compressed_size;
                        need_properties = false;
                    }
                    else if (need_properties)
                    {
                        throw compression_error(error_code::invalid_data, format::xz, "LZMA2 compressed chunk omits required properties");
                    }
                    else if (control >= 0xa0U)
                    {
                        model.reset();
                    }
                    std::vector< std::byte > encoded;
                    encoded.reserve(compressed_chunk_size + 1U);
                    for (std::size_t index = 0U; index <= compressed_chunk_size; ++index)
                    {
                        encoded.push_back(read_byte());
                    }
                    compressed_size += compressed_chunk_size + 1U;
                    std::vector< std::byte > working = std::move(history);
                    std::size_t const history_size = working.size();
                    decode_lzma_chunk(encoded, uncompressed_size + 1U, model, working, 0U, dictionary_size, history_size + uncompressed_size + 1U, dictionary_position - history_size);
                    for (std::size_t index = history_size; index < working.size(); ++index)
                    {
                        emit(working[index]);
                    }
                    dictionary_position += uncompressed_size + 1U;
                    std::size_t const retained = std::min< std::size_t >(working.size(), dictionary_size);
                    history.assign(working.end() - static_cast< std::ptrdiff_t >(retained), working.end());
                }
                if (declared_compressed_size.has_value() && *declared_compressed_size != compressed_size)
                {
                    throw compression_error(error_code::invalid_data, format::xz, "xz block compressed-size mismatch");
                }
                if (declared_uncompressed_size.has_value() && *declared_uncompressed_size != block_output_size)
                {
                    throw compression_error(error_code::invalid_data, format::xz, "xz block uncompressed-size mismatch");
                }
                for (std::size_t padding = static_cast< std::size_t >((4U - compressed_size % 4U) % 4U); padding > 0U; --padding)
                {
                    if (read_byte() != std::byte{0})
                    {
                        throw compression_error(error_code::invalid_data, format::xz, "invalid xz block padding");
                    }
                }
                if (check_identifier == 1U && read_little_endian_source(4U) != block_crc32.value())
                {
                    throw compression_error(error_code::invalid_data, format::xz, "xz block CRC-32 mismatch");
                }
                if (check_identifier == 4U && read_little_endian_source(8U) != block_crc64.value())
                {
                    throw compression_error(error_code::invalid_data, format::xz, "xz block CRC-64 mismatch");
                }
                records.push_back(block_record{header_size + compressed_size + check_size(check_identifier), block_output_size});
            }
 
            implementation::crc32_accumulator index_crc;
            index_crc.update(std::byte{0});
            std::size_t index_size = 1U;
            auto read_index_byte = [&]() -> std::byte
            {
                std::byte const value = read_byte();
                index_crc.update(value);
                ++index_size;
                return value;
            };
            auto read_index_integer = [&]() -> std::uint64_t
            {
                std::uint64_t value = 0U;
                for (std::uint8_t byte_index = 0U; byte_index < 9U; ++byte_index)
                {
                    std::uint8_t const byte = std::to_integer< std::uint8_t >(read_index_byte());
                    if (byte_index != 0U && byte == 0U)
                    {
                        throw compression_error(error_code::invalid_data, format::xz, "non-minimal xz variable-length integer");
                    }
                    value |= static_cast< std::uint64_t >(byte & 0x7fU) << (byte_index * 7U);
                    if ((byte & 0x80U) == 0U)
                    {
                        return value;
                    }
                }
                throw compression_error(error_code::invalid_data, format::xz, "oversized xz variable-length integer");
            };
            if (read_index_integer() != records.size())
            {
                throw compression_error(error_code::invalid_data, format::xz, "xz index block count mismatch");
            }
            for (block_record const& record : records)
            {
                if (read_index_integer() != record.unpadded_size || read_index_integer() != record.uncompressed_size)
                {
                    throw compression_error(error_code::invalid_data, format::xz, "xz index record mismatch");
                }
            }
            while (index_size % 4U != 0U)
            {
                if (read_index_byte() != std::byte{0})
                {
                    throw compression_error(error_code::invalid_data, format::xz, "invalid xz index padding");
                }
            }
            if (read_little_endian_source(4U) != index_crc.value())
            {
                throw compression_error(error_code::invalid_data, format::xz, "xz index checksum mismatch");
            }
            index_size += 4U;
            std::array< std::byte, 12U > footer{};
            for (std::byte& value : footer)
            {
                value = read_byte();
            }
            std::size_t footer_position = 0U;
            std::uint32_t const expected_footer_crc = static_cast< std::uint32_t >(read_little_endian(footer, footer_position, 4U));
            if (crc32(std::span< std::byte const >(footer).subspan(4U, 6U)) != expected_footer_crc)
            {
                throw compression_error(error_code::invalid_data, format::xz, "xz footer checksum mismatch");
            }
            std::uint64_t const backward_size = (read_little_endian(footer, footer_position, 4U) + 1U) * 4U;
            if (backward_size != index_size || footer[8U] != stream_flags[0U] || footer[9U] != stream_flags[1U] || footer[10U] != std::byte{'Y'} || footer[11U] != std::byte{'Z'})
            {
                throw compression_error(error_code::invalid_data, format::xz, "invalid xz stream footer");
            }
            decoded_stream = true;
            std::size_t padding_size = 0U;
            std::byte next{};
            while (source.peek(next) && next == std::byte{0})
            {
                static_cast< void >(read_byte());
                ++padding_size;
            }
            if (padding_size % 4U != 0U)
            {
                throw compression_error(error_code::invalid_data, format::xz, "xz stream padding is not a multiple of four bytes");
            }
        } while (!source.empty());
        return output;
    }
 
} // namespace rpnx::compression::xz_codec
 
#endif