zstandard.hpp

Go to the documentation of this file.

#ifndef RPNX_COMPRESSION_IMPLEMENTATION_ZSTANDARD_HPP
#define RPNX_COMPRESSION_IMPLEMENTATION_ZSTANDARD_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 Zstandard frame, entropy-table, and sequence implementation.
 */
 
/** @brief Internal implementation of Zstandard compression and decompression. */
namespace rpnx::compression::zstandard_codec
{
 
    /** One state transition in an FSE decoding table. */
    struct fse_entry
    {
        /** @brief Symbol emitted when this state is decoded. */
        std::uint8_t symbol;
        /** @brief Number of bits used to select the next state. */
        std::uint8_t number_of_bits;
        /** @brief Baseline added to the decoded transition bits. */
        std::uint16_t baseline;
    };
 
    /** Native FSE decoding table indexed by the current decoder state. */
    struct fse_table
    {
        /** @brief Base-two logarithm of the state count. */
        std::uint8_t accuracy_log;
        /** @brief State transitions indexed by current state. */
        std::vector< fse_entry > entries;
    };
 
    /** Parsed normalized FSE probabilities and their encoded byte length. */
    struct normalized_probability_result
    {
        /** @brief Accuracy log encoded by the description. */
        std::uint8_t accuracy_log;
        /** @brief Normalized probability for every symbol through the last encoded symbol. */
        std::vector< std::int16_t > probabilities;
        /** @brief Whole number of source bytes occupied by the description. */
        std::size_t consumed_bytes;
    };
 
    /** Decoded literals and the number of compressed-block bytes they occupy. */
    struct literals_result
    {
        /** @brief Regenerated literal bytes. */
        std::vector< std::byte > literals;
        /** @brief Bytes occupied by the literals section in its compressed block. */
        std::size_t consumed_bytes;
    };
 
    /** One node in a native canonical 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 Literal value for a leaf node. */
        std::optional< std::uint8_t > symbol;
    };
 
    /** Canonical Huffman decoding tree retained for treeless literal blocks. */
    struct huffman_table
    {
        /** @brief Tree nodes with the root at index zero. */
        std::vector< huffman_node > nodes;
    };
 
    /** A parsed Huffman tree description and its encoded byte length. */
    struct huffman_description_result
    {
        /** @brief Parsed canonical decoding tree. */
        huffman_table table;
        /** @brief Bytes occupied by the encoded tree description. */
        std::size_t consumed_bytes;
    };
 
    /** Persistent entropy tables and repeat offsets shared by compressed blocks. */
    struct decoder_state
    {
        /** @brief Huffman table retained for treeless literal blocks. */
        std::optional< huffman_table > huffman_literals_table;
        /** @brief Most recent literal-length FSE table. */
        std::optional< fse_table > literal_length_table;
        /** @brief Most recent offset-code FSE table. */
        std::optional< fse_table > offset_table;
        /** @brief Most recent match-length FSE table. */
        std::optional< fse_table > match_length_table;
        /** @brief Three repeat offsets in most-recent-first order. */
        std::array< std::size_t, 3U > repeated_offsets{1U, 4U, 8U};
    };
 
    /** Baseline and additional-bit count selected by a sequence length code. */
    struct length_code_entry
    {
        /** @brief Smallest length represented by this code. */
        std::uint32_t baseline;
        /** @brief Number of additional value bits following the code. */
        std::uint8_t number_of_bits;
    };
 
    /** Encoded sequence length code and its additional-bit payload. */
    struct encoded_length
    {
        /** @brief Sequence length code. */
        std::uint8_t code;
        /** @brief Additional value stored after the code. */
        std::uint32_t additional_value;
        /** @brief Number of significant bits in additional_value. */
        std::uint8_t number_of_bits;
    };
 
    /** Literal-length code definitions from the Zstandard format. */
    inline constexpr std::array< length_code_entry, 36U > literal_length_codes{length_code_entry{0U, 0U}, {1U, 0U}, {2U, 0U}, {3U, 0U}, {4U, 0U}, {5U, 0U}, {6U, 0U}, {7U, 0U}, {8U, 0U}, {9U, 0U}, {10U, 0U}, {11U, 0U}, {12U, 0U}, {13U, 0U}, {14U, 0U}, {15U, 0U}, {16U, 1U}, {18U, 1U}, {20U, 1U}, {22U, 1U}, {24U, 2U}, {28U, 2U}, {32U, 3U}, {40U, 3U}, {48U, 4U}, {64U, 6U}, {128U, 7U}, {256U, 8U}, {512U, 9U}, {1024U, 10U}, {2048U, 11U}, {4096U, 12U}, {8192U, 13U}, {16384U, 14U}, {32768U, 15U}, {65536U, 16U}};
 
    /** Match-length code definitions from the Zstandard format. */
    inline constexpr std::array< length_code_entry, 53U > match_length_codes{length_code_entry{3U, 0U}, {4U, 0U}, {5U, 0U}, {6U, 0U}, {7U, 0U}, {8U, 0U}, {9U, 0U}, {10U, 0U}, {11U, 0U}, {12U, 0U}, {13U, 0U}, {14U, 0U}, {15U, 0U}, {16U, 0U}, {17U, 0U}, {18U, 0U}, {19U, 0U}, {20U, 0U}, {21U, 0U}, {22U, 0U}, {23U, 0U}, {24U, 0U}, {25U, 0U}, {26U, 0U}, {27U, 0U}, {28U, 0U}, {29U, 0U}, {30U, 0U}, {31U, 0U}, {32U, 0U}, {33U, 0U}, {34U, 0U}, {35U, 1U}, {37U, 1U}, {39U, 1U}, {41U, 1U}, {43U, 2U}, {47U, 2U}, {51U, 3U}, {59U, 3U}, {67U, 4U}, {83U, 4U}, {99U, 5U}, {131U, 7U}, {259U, 8U}, {515U, 9U}, {1027U, 10U}, {2051U, 11U}, {4099U, 12U}, {8195U, 13U}, {16387U, 14U}, {32771U, 15U}, {65539U, 16U}};
 
    /** Read a byte-aligned, forward, least-significant-bit-first bitstream. */
    class forward_bit_reader
    {
      public:
        /**
         * @brief Constructs a reader over a non-owning byte span.
         * @param input Complete forward bitstream retained for this object's lifetime.
         */
        explicit forward_bit_reader(std::span< std::byte const > input) noexcept : m_input(input)
        {
        }
 
        /**
         * @brief Returns the next bits without consuming them.
         * @param count Number of bits, at most 32.
         * @return Field value with the earliest bit in the least significant position.
         */
        [[nodiscard]] std::uint32_t peek_bits(std::uint8_t count) const
        {
            if (count > 32U || m_bit_position > m_input.size() * 8U || count > m_input.size() * 8U - m_bit_position)
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "truncated forward Zstandard bitstream");
            }
            std::uint32_t value = 0U;
            for (std::uint8_t bit_index = 0U; bit_index < count; ++bit_index)
            {
                std::size_t const absolute_bit = m_bit_position + bit_index;
                std::uint8_t const byte = std::to_integer< std::uint8_t >(m_input[absolute_bit / 8U]);
                value |= static_cast< std::uint32_t >((byte >> (absolute_bit % 8U)) & 1U) << bit_index;
            }
            return value;
        }
 
        /**
         * @brief Consumes and returns the next bits.
         * @param count Number of bits, at most 32.
         * @return Field value with the earliest bit in the least significant position.
         */
        [[nodiscard]] std::uint32_t read_bits(std::uint8_t count)
        {
            std::uint32_t const value = peek_bits(count);
            m_bit_position += count;
            return value;
        }
 
        /**
         * @brief Returns the whole number of bytes occupied by consumed bits.
         * @return Consumed bit count rounded up to bytes.
         */
        [[nodiscard]] std::size_t consumed_bytes() const noexcept
        {
            return (m_bit_position + 7U) / 8U;
        }
 
      private:
        std::span< std::byte const > m_input;
        std::size_t m_bit_position = 0U;
    };
 
    /** Read a Zstandard entropy bitstream from its end toward its beginning. */
    class reverse_bit_reader
    {
      public:
        /**
         * @brief Constructs a reader and removes the mandatory final-bit marker.
         * @param input Complete reverse bitstream retained for this object's lifetime.
         */
        explicit reverse_bit_reader(std::span< std::byte const > input) : m_input(input)
        {
            if (input.empty() || input.back() == std::byte{0})
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "invalid Zstandard reverse bitstream marker");
            }
            std::uint8_t const last_byte = std::to_integer< std::uint8_t >(input.back());
            std::uint8_t marker_position = 0U;
            for (std::uint8_t bit_index = 1U; bit_index < 8U; ++bit_index)
            {
                if ((last_byte >> bit_index) != 0U)
                {
                    marker_position = bit_index;
                }
            }
            m_bit_position = (input.size() - 1U) * 8U + marker_position;
        }
 
        /**
         * @brief Consumes bits preceding the current reverse-stream position.
         * @param count Number of bits, at most 32.
         * @return Field value in least-significant-bit-first wire order.
         */
        [[nodiscard]] std::uint32_t read_bits(std::uint8_t count)
        {
            if (count > 32U || count > m_bit_position)
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "truncated reverse Zstandard bitstream");
            }
            std::size_t const first_bit = m_bit_position - count;
            std::uint32_t value = 0U;
            for (std::uint8_t bit_index = 0U; bit_index < count; ++bit_index)
            {
                std::size_t const absolute_bit = first_bit + bit_index;
                std::uint8_t const byte = std::to_integer< std::uint8_t >(m_input[absolute_bit / 8U]);
                value |= static_cast< std::uint32_t >((byte >> (absolute_bit % 8U)) & 1U) << bit_index;
            }
            m_bit_position = first_bit;
            return value;
        }
 
        /**
         * @brief Returns the number of useful bits not yet consumed.
         * @return Remaining bit count before the end marker.
         */
        [[nodiscard]] std::size_t remaining_bits() const noexcept
        {
            return m_bit_position;
        }
 
      private:
        std::span< std::byte const > m_input;
        std::size_t m_bit_position = 0U;
    };
 
    /**
     * @brief Rotates a 64-bit value left without compiler-specific intrinsics.
     * @param value Value to rotate.
     * @param count Rotation distance in the range 1--63.
     * @return Rotated value.
     */
    [[nodiscard]] inline std::uint64_t rotate_left(std::uint64_t value, std::uint8_t count) noexcept
    {
        return (value << count) | (value >> (64U - count));
    }
 
    /**
     * @brief Reads an unchecked little-endian 32-bit word.
     * @param input Range containing at least four bytes at @p offset.
     * @param offset Position of the first byte.
     * @return Decoded word.
     */
    [[nodiscard]] inline std::uint32_t read_word32(std::span< std::byte const > input, std::size_t offset) noexcept
    {
        return static_cast< std::uint32_t >(std::to_integer< std::uint8_t >(input[offset])) | (static_cast< std::uint32_t >(std::to_integer< std::uint8_t >(input[offset + 1U])) << 8U) | (static_cast< std::uint32_t >(std::to_integer< std::uint8_t >(input[offset + 2U])) << 16U) | (static_cast< std::uint32_t >(std::to_integer< std::uint8_t >(input[offset + 3U])) << 24U);
    }
 
    /**
     * @brief Reads an unchecked little-endian 64-bit word.
     * @param input Range containing at least eight bytes at @p offset.
     * @param offset Position of the first byte.
     * @return Decoded word.
     */
    [[nodiscard]] inline std::uint64_t read_word64(std::span< std::byte const > input, std::size_t offset) noexcept
    {
        std::uint64_t value = 0U;
        for (std::uint8_t byte_index = 0U; byte_index < 8U; ++byte_index)
        {
            value |= static_cast< std::uint64_t >(std::to_integer< std::uint8_t >(input[offset + byte_index])) << (byte_index * 8U);
        }
        return value;
    }
 
    /**
     * @brief Computes XXH64 as required by the Zstandard frame checksum.
     * @param input Bytes to hash.
     * @param seed XXH64 seed.
     * @return Finalized 64-bit hash.
     */
    [[nodiscard]] inline std::uint64_t xxhash64(std::span< std::byte const > input, std::uint64_t seed = 0U) noexcept
    {
        constexpr std::uint64_t prime1 = 0x9e3779b185ebca87ULL;
        constexpr std::uint64_t prime2 = 0xc2b2ae3d27d4eb4fULL;
        constexpr std::uint64_t prime3 = 0x165667b19e3779f9ULL;
        constexpr std::uint64_t prime4 = 0x85ebca77c2b2ae63ULL;
        constexpr std::uint64_t prime5 = 0x27d4eb2f165667c5ULL;
        auto round = [](std::uint64_t accumulator, std::uint64_t value)
        {
            accumulator += value * prime2;
            accumulator = rotate_left(accumulator, 31U);
            return accumulator * prime1;
        };
        auto merge = [&](std::uint64_t accumulator, std::uint64_t lane)
        {
            accumulator ^= round(0U, lane);
            return accumulator * prime1 + prime4;
        };
 
        std::size_t position = 0U;
        std::uint64_t hash = 0U;
        if (input.size() >= 32U)
        {
            std::uint64_t lane1 = seed + prime1 + prime2;
            std::uint64_t lane2 = seed + prime2;
            std::uint64_t lane3 = seed;
            std::uint64_t lane4 = seed - prime1;
            while (position + 32U <= input.size())
            {
                lane1 = round(lane1, read_word64(input, position));
                lane2 = round(lane2, read_word64(input, position + 8U));
                lane3 = round(lane3, read_word64(input, position + 16U));
                lane4 = round(lane4, read_word64(input, position + 24U));
                position += 32U;
            }
            hash = rotate_left(lane1, 1U) + rotate_left(lane2, 7U) + rotate_left(lane3, 12U) + rotate_left(lane4, 18U);
            hash = merge(hash, lane1);
            hash = merge(hash, lane2);
            hash = merge(hash, lane3);
            hash = merge(hash, lane4);
        }
        else
        {
            hash = seed + prime5;
        }
        hash += input.size();
        while (position + 8U <= input.size())
        {
            hash ^= round(0U, read_word64(input, position));
            hash = rotate_left(hash, 27U) * prime1 + prime4;
            position += 8U;
        }
        if (position + 4U <= input.size())
        {
            hash ^= static_cast< std::uint64_t >(read_word32(input, position)) * prime1;
            hash = rotate_left(hash, 23U) * prime2 + prime3;
            position += 4U;
        }
        while (position < input.size())
        {
            hash ^= std::to_integer< std::uint8_t >(input[position]) * prime5;
            hash = rotate_left(hash, 11U) * prime1;
            ++position;
        }
        hash ^= hash >> 33U;
        hash *= prime2;
        hash ^= hash >> 29U;
        hash *= prime3;
        hash ^= hash >> 32U;
        return hash;
    }
 
    /** Incremental XXH64 accumulator for streamed Zstandard checksums. */
    class xxhash64_accumulator
    {
      public:
        /**
         * @brief Includes one byte in the hash.
         * @param value Next byte in stream order.
         */
        void update(std::byte value) noexcept
        {
            m_buffer[m_buffer_size++] = value;
            ++m_total_size;
            if (m_buffer_size == m_buffer.size())
            {
                m_lane1 = round(m_lane1, read_word64(m_buffer, 0U));
                m_lane2 = round(m_lane2, read_word64(m_buffer, 8U));
                m_lane3 = round(m_lane3, read_word64(m_buffer, 16U));
                m_lane4 = round(m_lane4, read_word64(m_buffer, 24U));
                m_buffer_size = 0U;
            }
        }
 
        /**
         * @brief Returns the hash for all supplied bytes.
         * @return Finalized XXH64 value without changing accumulator state.
         */
        [[nodiscard]] std::uint64_t value() const noexcept
        {
            constexpr std::uint64_t prime1 = 0x9e3779b185ebca87ULL;
            constexpr std::uint64_t prime2 = 0xc2b2ae3d27d4eb4fULL;
            constexpr std::uint64_t prime3 = 0x165667b19e3779f9ULL;
            constexpr std::uint64_t prime4 = 0x85ebca77c2b2ae63ULL;
            constexpr std::uint64_t prime5 = 0x27d4eb2f165667c5ULL;
            std::uint64_t hash = 0U;
            if (m_total_size >= 32U)
            {
                hash = rotate_left(m_lane1, 1U) + rotate_left(m_lane2, 7U) + rotate_left(m_lane3, 12U) + rotate_left(m_lane4, 18U);
                hash = merge(hash, m_lane1);
                hash = merge(hash, m_lane2);
                hash = merge(hash, m_lane3);
                hash = merge(hash, m_lane4);
            }
            else
            {
                hash = prime5;
            }
            hash += m_total_size;
            std::size_t position = 0U;
            std::span< std::byte const > const remaining(m_buffer.data(), m_buffer_size);
            while (position + 8U <= remaining.size())
            {
                hash ^= round(0U, read_word64(remaining, position));
                hash = rotate_left(hash, 27U) * prime1 + prime4;
                position += 8U;
            }
            if (position + 4U <= remaining.size())
            {
                hash ^= static_cast< std::uint64_t >(read_word32(remaining, position)) * prime1;
                hash = rotate_left(hash, 23U) * prime2 + prime3;
                position += 4U;
            }
            while (position < remaining.size())
            {
                hash ^= std::to_integer< std::uint8_t >(remaining[position]) * prime5;
                hash = rotate_left(hash, 11U) * prime1;
                ++position;
            }
            hash ^= hash >> 33U;
            hash *= prime2;
            hash ^= hash >> 29U;
            hash *= prime3;
            hash ^= hash >> 32U;
            return hash;
        }
 
      private:
        /**
         * @brief Applies one XXH64 lane round.
         * @param lane Current lane accumulator.
         * @param value Next little-endian input word.
         * @return Updated lane accumulator.
         */
        [[nodiscard]] static std::uint64_t round(std::uint64_t lane, std::uint64_t value) noexcept
        {
            constexpr std::uint64_t prime1 = 0x9e3779b185ebca87ULL;
            constexpr std::uint64_t prime2 = 0xc2b2ae3d27d4eb4fULL;
            return rotate_left(lane + value * prime2, 31U) * prime1;
        }
 
        /**
         * @brief Merges one accumulated lane into the final hash.
         * @param hash Current combined hash.
         * @param lane Lane to merge.
         * @return Updated combined hash.
         */
        [[nodiscard]] static std::uint64_t merge(std::uint64_t hash, std::uint64_t lane) noexcept
        {
            constexpr std::uint64_t prime1 = 0x9e3779b185ebca87ULL;
            constexpr std::uint64_t prime4 = 0x85ebca77c2b2ae63ULL;
            hash ^= round(0U, lane);
            return hash * prime1 + prime4;
        }
 
        std::array< std::byte, 32U > m_buffer{};
        std::size_t m_buffer_size = 0U;
        std::uint64_t m_total_size = 0U;
        std::uint64_t m_lane1 = 0x9e3779b185ebca87ULL + 0xc2b2ae3d27d4eb4fULL;
        std::uint64_t m_lane2 = 0xc2b2ae3d27d4eb4fULL;
        std::uint64_t m_lane3 = 0U;
        std::uint64_t m_lane4 = 0U - 0x9e3779b185ebca87ULL;
    };
 
    /**
     * @brief Appends a little-endian integer with a selected byte count.
     * @param output Buffer receiving encoded bytes.
     * @param value Value to encode.
     * @param byte_count Number of low-order bytes to append.
     */
    inline void append_integer(std::vector< std::byte >& output, std::uint64_t value, std::uint8_t byte_count)
    {
        for (std::uint8_t byte_index = 0U; byte_index < byte_count; ++byte_index)
        {
            output.push_back(static_cast< std::byte >((value >> (byte_index * 8U)) & 0xffU));
        }
    }
 
    /**
     * @brief Reads a checked little-endian integer with a selected byte count.
     * @param input Source bytes.
     * @param offset Position of the first byte.
     * @param byte_count Width from zero through eight bytes.
     * @return Decoded value.
     */
    [[nodiscard]] inline std::uint64_t read_integer(std::span< std::byte const > input, std::size_t offset, std::uint8_t byte_count)
    {
        if (offset > input.size() || byte_count > input.size() - offset)
        {
            throw compression_error(error_code::invalid_data, format::zstandard, "truncated Zstandard frame field");
        }
        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[offset + byte_index])) << (byte_index * 8U);
        }
        return value;
    }
 
    /**
     * @brief Parses one forward-coded normalized FSE probability description.
     * @param input Encoded probability description.
     * @param maximum_symbol Largest permitted symbol value.
     * @param maximum_accuracy_log Largest permitted FSE accuracy log.
     * @return Parsed probabilities and occupied byte count.
     */
    [[nodiscard]] inline normalized_probability_result parse_normalized_probabilities(std::span< std::byte const > input, std::uint8_t maximum_symbol, std::uint8_t maximum_accuracy_log)
    {
        forward_bit_reader reader(input);
        std::uint8_t const accuracy_log = static_cast< std::uint8_t >(reader.read_bits(4U) + 5U);
        if (accuracy_log > maximum_accuracy_log)
        {
            throw compression_error(error_code::invalid_data, format::zstandard, "Zstandard FSE accuracy log exceeds its format limit");
        }
 
        std::vector< std::int16_t > probabilities(static_cast< std::size_t >(maximum_symbol) + 1U, 0);
        std::uint32_t remaining = (1U << accuracy_log) + 1U;
        std::uint32_t threshold = 1U << accuracy_log;
        std::uint8_t number_of_bits = static_cast< std::uint8_t >(accuracy_log + 1U);
        std::size_t symbol = 0U;
        std::size_t symbols_with_probability = 0U;
 
        while (remaining > 1U)
        {
            if (symbol >= probabilities.size())
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "Zstandard FSE description has too many symbols");
            }
 
            std::uint32_t const low_value = reader.peek_bits(static_cast< std::uint8_t >(number_of_bits - 1U));
            std::uint32_t const threshold_offset = (2U * threshold - 1U) - remaining;
            std::uint32_t encoded_probability = 0U;
            if (low_value < threshold_offset)
            {
                encoded_probability = reader.read_bits(static_cast< std::uint8_t >(number_of_bits - 1U));
            }
            else
            {
                encoded_probability = reader.read_bits(number_of_bits);
                if (encoded_probability >= threshold)
                {
                    encoded_probability -= threshold_offset;
                }
            }
 
            std::int16_t const probability = static_cast< std::int16_t >(encoded_probability) - 1;
            probabilities[symbol] = probability;
            ++symbol;
            if (probability != 0)
            {
                ++symbols_with_probability;
            }
            std::uint32_t const magnitude = probability < 0 ? static_cast< std::uint32_t >(-probability) : static_cast< std::uint32_t >(probability);
            if (magnitude >= remaining)
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "Zstandard FSE probabilities exceed the table size");
            }
            remaining -= magnitude;
 
            if (probability == 0)
            {
                std::size_t repeated_zero_count = 0U;
                std::uint32_t repeat_count = 0U;
                do
                {
                    repeat_count = reader.read_bits(2U);
                    repeated_zero_count += repeat_count;
                } while (repeat_count == 3U);
                if (repeated_zero_count > probabilities.size() - symbol)
                {
                    throw compression_error(error_code::invalid_data, format::zstandard, "Zstandard FSE zero run exceeds the symbol alphabet");
                }
                symbol += repeated_zero_count;
            }
 
            while (remaining < threshold)
            {
                --number_of_bits;
                threshold >>= 1U;
            }
        }
 
        if (symbols_with_probability < 2U)
        {
            throw compression_error(error_code::invalid_data, format::zstandard, "Zstandard FSE table requires at least two symbols");
        }
        return normalized_probability_result{accuracy_log, std::move(probabilities), reader.consumed_bytes()};
    }
 
    /**
     * @brief Constructs the FSE decoding table for normalized probabilities.
     * @param probabilities Normalized counts; negative one represents a low-probability symbol.
     * @param accuracy_log Base-two logarithm of the table size.
     * @return Validated state-transition table.
     */
    [[nodiscard]] inline fse_table build_fse_table(std::span< std::int16_t const > probabilities, std::uint8_t accuracy_log)
    {
        if (accuracy_log > 9U)
        {
            throw compression_error(error_code::invalid_data, format::zstandard, "unsupported Zstandard FSE table size");
        }
        std::size_t const table_size = static_cast< std::size_t >(1U) << accuracy_log;
        std::size_t probability_total = 0U;
        for (std::int16_t probability : probabilities)
        {
            if (probability < -1)
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "invalid negative Zstandard FSE probability");
            }
            probability_total += probability < 0 ? 1U : static_cast< std::size_t >(probability);
        }
        if (probability_total != table_size)
        {
            throw compression_error(error_code::invalid_data, format::zstandard, "Zstandard FSE probabilities do not fill the table");
        }
 
        std::vector< fse_entry > entries(table_size, fse_entry{0U, 0U, 0U});
        std::vector< bool > assigned(table_size, false);
        std::vector< std::uint16_t > next_state(probabilities.size(), 0U);
        std::size_t high_position = table_size;
        for (std::size_t symbol = 0U; symbol < probabilities.size(); ++symbol)
        {
            std::int16_t const probability = probabilities[symbol];
            if (probability == -1)
            {
                if (high_position == 0U)
                {
                    throw compression_error(error_code::invalid_data, format::zstandard, "invalid low-probability Zstandard FSE states");
                }
                --high_position;
                entries[high_position].symbol = static_cast< std::uint8_t >(symbol);
                assigned[high_position] = true;
                next_state[symbol] = 1U;
            }
            else
            {
                next_state[symbol] = static_cast< std::uint16_t >(probability);
            }
        }
 
        std::size_t const table_mask = table_size - 1U;
        std::size_t const spread_step = (table_size >> 1U) + (table_size >> 3U) + 3U;
        std::size_t position = 0U;
        for (std::size_t symbol = 0U; symbol < probabilities.size(); ++symbol)
        {
            std::int16_t const probability = probabilities[symbol];
            for (std::int16_t occurrence = 0; occurrence < probability; ++occurrence)
            {
                if (assigned[position])
                {
                    throw compression_error(error_code::invalid_data, format::zstandard, "overlapping Zstandard FSE state spread");
                }
                entries[position].symbol = static_cast< std::uint8_t >(symbol);
                assigned[position] = true;
                position = (position + spread_step) & table_mask;
                while (position >= high_position)
                {
                    position = (position + spread_step) & table_mask;
                }
            }
        }
        if (position != 0U || std::find(assigned.begin(), assigned.end(), false) != assigned.end())
        {
            throw compression_error(error_code::invalid_data, format::zstandard, "invalid Zstandard FSE state spread");
        }
 
        for (std::size_t state = 0U; state < table_size; ++state)
        {
            std::uint8_t const symbol = entries[state].symbol;
            std::uint16_t const symbol_state = next_state[symbol]++;
            if (symbol_state == 0U)
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "zero-width Zstandard FSE symbol state");
            }
            std::uint8_t const state_log = static_cast< std::uint8_t >(std::bit_width(symbol_state) - 1);
            std::uint8_t const number_of_bits = static_cast< std::uint8_t >(accuracy_log - state_log);
            entries[state].number_of_bits = number_of_bits;
            entries[state].baseline = static_cast< std::uint16_t >((static_cast< std::uint32_t >(symbol_state) << number_of_bits) - table_size);
        }
        return fse_table{accuracy_log, std::move(entries)};
    }
 
    /**
     * @brief Constructs a one-symbol FSE table for RLE sequence mode.
     * @param symbol Repeated symbol.
     * @return Single-state decoding table.
     */
    [[nodiscard]] inline fse_table build_rle_fse_table(std::uint8_t symbol)
    {
        return fse_table{0U, {fse_entry{symbol, 0U, 0U}}};
    }
 
    /**
     * @brief Builds the format-defined predefined literal-length FSE table.
     * @return Predefined literal-length state-transition table.
     */
    [[nodiscard]] inline fse_table build_predefined_literal_length_table()
    {
        constexpr std::array< std::int16_t, 36U > probabilities{4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1, -1, -1, -1, -1};
        return build_fse_table(probabilities, 6U);
    }
 
    /**
     * @brief Builds the format-defined predefined match-length FSE table.
     * @return Predefined match-length state-transition table.
     */
    [[nodiscard]] inline fse_table build_predefined_match_length_table()
    {
        constexpr std::array< std::int16_t, 53U > probabilities{1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, -1};
        return build_fse_table(probabilities, 6U);
    }
 
    /**
     * @brief Builds the format-defined predefined offset-code FSE table.
     * @return Predefined offset-code state-transition table.
     */
    [[nodiscard]] inline fse_table build_predefined_offset_table()
    {
        constexpr std::array< std::int16_t, 29U > probabilities{1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1};
        return build_fse_table(probabilities, 5U);
    }
 
    /**
     * @brief Decodes the two-state FSE stream used for Huffman weights.
     * @param input Encoded normalized probabilities followed by reverse-coded states.
     * @return Explicit Huffman weights.
     */
    [[nodiscard]] inline std::vector< std::uint8_t > decode_fse_weights(std::span< std::byte const > input)
    {
        normalized_probability_result probabilities = parse_normalized_probabilities(input, 12U, 6U);
        if (probabilities.consumed_bytes >= input.size())
        {
            throw compression_error(error_code::invalid_data, format::zstandard, "missing FSE-compressed Zstandard Huffman weights");
        }
        fse_table const table = build_fse_table(probabilities.probabilities, probabilities.accuracy_log);
        reverse_bit_reader reader(input.subspan(probabilities.consumed_bytes));
        std::size_t state1 = reader.read_bits(table.accuracy_log);
        std::size_t state2 = reader.read_bits(table.accuracy_log);
        if (state1 >= table.entries.size() || state2 >= table.entries.size())
        {
            throw compression_error(error_code::invalid_data, format::zstandard, "invalid initial Huffman-weight FSE state");
        }
 
        std::vector< std::uint8_t > weights;
        weights.reserve(255U);
        bool finished = false;
        while (!finished)
        {
            if (weights.size() >= 255U)
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "too many Zstandard Huffman weights");
            }
            fse_entry const transition1 = table.entries[state1];
            weights.push_back(transition1.symbol);
            if (transition1.number_of_bits > reader.remaining_bits())
            {
                if (weights.size() >= 255U)
                {
                    throw compression_error(error_code::invalid_data, format::zstandard, "too many Zstandard Huffman weights");
                }
                weights.push_back(table.entries[state2].symbol);
                finished = true;
                continue;
            }
            state1 = transition1.baseline + reader.read_bits(transition1.number_of_bits);
            if (state1 >= table.entries.size())
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "updated Huffman-weight FSE state exceeds its table");
            }
 
            if (weights.size() >= 255U)
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "too many Zstandard Huffman weights");
            }
            fse_entry const transition2 = table.entries[state2];
            weights.push_back(transition2.symbol);
            if (transition2.number_of_bits > reader.remaining_bits())
            {
                if (weights.size() >= 255U)
                {
                    throw compression_error(error_code::invalid_data, format::zstandard, "too many Zstandard Huffman weights");
                }
                weights.push_back(table.entries[state1].symbol);
                finished = true;
                continue;
            }
            state2 = transition2.baseline + reader.read_bits(transition2.number_of_bits);
            if (state2 >= table.entries.size())
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "updated Huffman-weight FSE state exceeds its table");
            }
        }
        return weights;
    }
 
    /**
     * @brief Builds the canonical Huffman tree implied by transmitted weights.
     * @param explicit_weights Weights for all symbols except the inferred final symbol.
     * @return Validated canonical decoding tree.
     */
    [[nodiscard]] inline huffman_table build_huffman_table(std::span< std::uint8_t const > explicit_weights)
    {
        if (explicit_weights.empty() || explicit_weights.size() >= 256U)
        {
            throw compression_error(error_code::invalid_data, format::zstandard, "invalid number of Zstandard Huffman weights");
        }
        std::uint32_t weight_total = 0U;
        for (std::uint8_t weight : explicit_weights)
        {
            if (weight > 11U)
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "Zstandard Huffman weight exceeds the maximum tree depth");
            }
            if (weight != 0U)
            {
                weight_total += 1U << (weight - 1U);
            }
        }
        if (weight_total == 0U)
        {
            throw compression_error(error_code::invalid_data, format::zstandard, "empty Zstandard Huffman tree");
        }
        std::uint32_t const table_size = std::bit_ceil(weight_total + 1U);
        if (table_size > (1U << 11U))
        {
            throw compression_error(error_code::invalid_data, format::zstandard, "Zstandard Huffman tree exceeds the maximum depth");
        }
        std::uint32_t const final_weight_value = table_size - weight_total;
        if (!std::has_single_bit(final_weight_value))
        {
            throw compression_error(error_code::invalid_data, format::zstandard, "Zstandard Huffman weights do not complete a canonical tree");
        }
        std::uint8_t const final_weight = static_cast< std::uint8_t >(std::bit_width(final_weight_value));
        std::uint8_t const table_log = static_cast< std::uint8_t >(std::bit_width(table_size) - 1);
        std::vector< std::uint8_t > weights(explicit_weights.begin(), explicit_weights.end());
        weights.push_back(final_weight);
 
        huffman_table table{{huffman_node{}}};
        std::uint32_t code_space = 0U;
        for (std::uint8_t weight = 1U; weight <= table_log; ++weight)
        {
            for (std::size_t symbol = 0U; symbol < weights.size(); ++symbol)
            {
                if (weights[symbol] != weight)
                {
                    continue;
                }
                std::uint8_t const number_of_bits = static_cast< std::uint8_t >(table_log + 1U - weight);
                std::uint32_t const code = code_space >> (weight - 1U);
                std::size_t node_index = 0U;
                for (std::uint8_t depth = 0U; depth < number_of_bits; ++depth)
                {
                    if (table.nodes[node_index].symbol.has_value())
                    {
                        throw compression_error(error_code::invalid_data, format::zstandard, "overlapping Zstandard Huffman prefix codes");
                    }
                    std::uint8_t const bit = static_cast< std::uint8_t >((code >> (number_of_bits - 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::zstandard, "Zstandard Huffman tree is too large");
                        }
                        std::uint16_t const new_node_index = static_cast< std::uint16_t >(table.nodes.size());
                        child = new_node_index;
                        node_index = new_node_index;
                        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::zstandard, "duplicate Zstandard Huffman prefix code");
                }
                table.nodes[node_index].symbol = static_cast< std::uint8_t >(symbol);
                code_space += 1U << (weight - 1U);
            }
        }
        if (code_space != table_size)
        {
            throw compression_error(error_code::invalid_data, format::zstandard, "incomplete Zstandard Huffman tree");
        }
        return table;
    }
 
    /**
     * @brief Parses a direct or FSE-compressed Huffman tree description.
     * @param input Bytes beginning with a Huffman description header.
     * @return Parsed tree and occupied byte count.
     */
    [[nodiscard]] inline huffman_description_result parse_huffman_description(std::span< std::byte const > input)
    {
        std::uint8_t const header = static_cast< std::uint8_t >(read_integer(input, 0U, 1U));
        std::vector< std::uint8_t > weights;
        std::size_t consumed_bytes = 1U;
        if (header < 128U)
        {
            std::size_t const compressed_size = header;
            if (compressed_size == 0U || compressed_size > input.size() - 1U)
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "truncated FSE-compressed Zstandard Huffman tree");
            }
            weights = decode_fse_weights(input.subspan(1U, compressed_size));
            consumed_bytes += compressed_size;
        }
        else
        {
            std::size_t const weight_count = static_cast< std::size_t >(header) - 127U;
            std::size_t const weight_bytes = (weight_count + 1U) / 2U;
            if (weight_bytes > input.size() - 1U)
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "truncated direct Zstandard Huffman tree");
            }
            weights.reserve(weight_count);
            for (std::size_t index = 0U; index < weight_count; ++index)
            {
                std::uint8_t const pair = std::to_integer< std::uint8_t >(input[1U + index / 2U]);
                weights.push_back(index % 2U == 0U ? pair >> 4U : pair & 0x0fU);
            }
            consumed_bytes += weight_bytes;
        }
        return huffman_description_result{build_huffman_table(weights), consumed_bytes};
    }
 
    /**
     * @brief Decodes one backward Huffman literal stream to an exact byte count.
     * @param input Reverse-coded Huffman stream.
     * @param regenerated_size Exact number of literals to produce.
     * @param table Canonical decoding tree.
     * @return Regenerated literal bytes.
     */
    [[nodiscard]] inline std::vector< std::byte > decode_huffman_stream(std::span< std::byte const > input, std::size_t regenerated_size, huffman_table const& table)
    {
        reverse_bit_reader reader(input);
        std::vector< std::byte > output;
        output.reserve(regenerated_size);
        for (std::size_t output_index = 0U; output_index < regenerated_size; ++output_index)
        {
            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::zstandard, "invalid Zstandard Huffman prefix code");
                }
                node_index = *child;
            }
            output.push_back(static_cast< std::byte >(*table.nodes[node_index].symbol));
        }
        if (reader.remaining_bits() != 0U)
        {
            throw compression_error(error_code::invalid_data, format::zstandard, "Zstandard Huffman stream was not fully consumed");
        }
        return output;
    }
 
    /**
     * @brief Decodes the literals section at the front of a compressed block.
     * @param block Complete compressed block payload.
     * @param state Frame decoder state retaining a reusable Huffman table.
     * @return Literals and the number of block bytes they occupied.
     */
    [[nodiscard]] inline literals_result decode_literals(std::span< std::byte const > block, decoder_state& state)
    {
        std::uint8_t const first_byte = static_cast< std::uint8_t >(read_integer(block, 0U, 1U));
        std::uint8_t const literals_type = first_byte & 0x03U;
        std::uint8_t const size_format = static_cast< std::uint8_t >((first_byte >> 2U) & 0x03U);
        if (literals_type <= 1U)
        {
            std::uint8_t header_size = 1U;
            if (size_format == 1U)
            {
                header_size = 2U;
            }
            else if (size_format == 3U)
            {
                header_size = 3U;
            }
            std::uint64_t const header = read_integer(block, 0U, header_size);
            std::size_t const regenerated_size = size_format == 0U || size_format == 2U ? static_cast< std::size_t >(header >> 3U) : static_cast< std::size_t >(header >> 4U);
            std::size_t const content_size = literals_type == 0U ? regenerated_size : 1U;
            if (header_size > block.size() || content_size > block.size() - header_size)
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "truncated Zstandard literals section");
            }
 
            std::vector< std::byte > literals;
            if (literals_type == 0U)
            {
                literals.insert(literals.end(), block.begin() + static_cast< std::ptrdiff_t >(header_size), block.begin() + static_cast< std::ptrdiff_t >(header_size + content_size));
            }
            else
            {
                literals.insert(literals.end(), regenerated_size, block[header_size]);
            }
            return literals_result{std::move(literals), header_size + content_size};
        }
 
        std::uint8_t header_size = 3U;
        std::uint8_t size_bits = 10U;
        std::uint8_t compressed_shift = 14U;
        if (size_format == 2U)
        {
            header_size = 4U;
            size_bits = 14U;
            compressed_shift = 18U;
        }
        else if (size_format == 3U)
        {
            header_size = 5U;
            size_bits = 18U;
            compressed_shift = 22U;
        }
        std::uint64_t const header = read_integer(block, 0U, header_size);
        std::uint64_t const size_mask = (std::uint64_t{1U} << size_bits) - 1U;
        std::size_t const regenerated_size = static_cast< std::size_t >((header >> 4U) & size_mask);
        std::size_t const compressed_size = static_cast< std::size_t >((header >> compressed_shift) & size_mask);
        if (header_size > block.size() || compressed_size > block.size() - header_size)
        {
            throw compression_error(error_code::invalid_data, format::zstandard, "truncated Huffman-coded Zstandard literals section");
        }
        std::span< std::byte const > const content = block.subspan(header_size, compressed_size);
        std::size_t stream_position = 0U;
        if (literals_type == 2U)
        {
            huffman_description_result description = parse_huffman_description(content);
            state.huffman_literals_table = std::move(description.table);
            stream_position = description.consumed_bytes;
        }
        else if (!state.huffman_literals_table.has_value())
        {
            throw compression_error(error_code::invalid_data, format::zstandard, "treeless Zstandard literals have no previous Huffman table");
        }
        if (stream_position >= content.size())
        {
            throw compression_error(error_code::invalid_data, format::zstandard, "missing Zstandard Huffman literal stream");
        }
 
        std::vector< std::byte > literals;
        if (size_format == 0U)
        {
            literals = decode_huffman_stream(content.subspan(stream_position), regenerated_size, *state.huffman_literals_table);
        }
        else
        {
            if (content.size() - stream_position < 6U)
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "truncated Zstandard Huffman jump table");
            }
            std::size_t const stream1_size = static_cast< std::size_t >(read_integer(content, stream_position, 2U));
            std::size_t const stream2_size = static_cast< std::size_t >(read_integer(content, stream_position + 2U, 2U));
            std::size_t const stream3_size = static_cast< std::size_t >(read_integer(content, stream_position + 4U, 2U));
            std::size_t const streams_size = content.size() - stream_position;
            if (stream1_size > streams_size - 6U || stream2_size > streams_size - 6U - stream1_size || stream3_size > streams_size - 6U - stream1_size - stream2_size)
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "invalid Zstandard Huffman stream sizes");
            }
            std::size_t const stream4_size = streams_size - 6U - stream1_size - stream2_size - stream3_size;
            std::size_t const segment_size = (regenerated_size + 3U) / 4U;
            if (segment_size * 3U > regenerated_size)
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "invalid four-stream Zstandard literal size");
            }
            std::size_t const stream1_position = stream_position + 6U;
            std::size_t const stream2_position = stream1_position + stream1_size;
            std::size_t const stream3_position = stream2_position + stream2_size;
            std::size_t const stream4_position = stream3_position + stream3_size;
            std::vector< std::byte > decoded1 = decode_huffman_stream(content.subspan(stream1_position, stream1_size), segment_size, *state.huffman_literals_table);
            std::vector< std::byte > decoded2 = decode_huffman_stream(content.subspan(stream2_position, stream2_size), segment_size, *state.huffman_literals_table);
            std::vector< std::byte > decoded3 = decode_huffman_stream(content.subspan(stream3_position, stream3_size), segment_size, *state.huffman_literals_table);
            std::vector< std::byte > decoded4 = decode_huffman_stream(content.subspan(stream4_position, stream4_size), regenerated_size - segment_size * 3U, *state.huffman_literals_table);
            literals.reserve(regenerated_size);
            literals.insert(literals.end(), decoded1.begin(), decoded1.end());
            literals.insert(literals.end(), decoded2.begin(), decoded2.end());
            literals.insert(literals.end(), decoded3.begin(), decoded3.end());
            literals.insert(literals.end(), decoded4.begin(), decoded4.end());
        }
        return literals_result{std::move(literals), header_size + compressed_size};
    }
 
    /**
     * @brief Decodes one compressed block into frame output.
     * @param block Complete compressed block payload.
     * @param window_size Declared maximum backward-match window.
     * @param maximum_output_size Absolute output-size limit.
     * @param state Entropy tables and repeat offsets retained across blocks.
     * @param output Frame output and match-history storage.
     */
    inline void decompress_compressed_block(std::span< std::byte const > block, std::size_t window_size, std::size_t maximum_output_size, decoder_state& state, std::vector< std::byte >& output)
    {
        literals_result literals = decode_literals(block, state);
        std::size_t position = literals.consumed_bytes;
        std::uint8_t const first_sequence_count = static_cast< std::uint8_t >(read_integer(block, position, 1U));
        ++position;
        std::size_t sequence_count = first_sequence_count;
        if (first_sequence_count >= 128U && first_sequence_count < 255U)
        {
            std::uint8_t const second_byte = static_cast< std::uint8_t >(read_integer(block, position, 1U));
            ++position;
            sequence_count = (static_cast< std::size_t >(first_sequence_count - 128U) << 8U) + second_byte;
        }
        else if (first_sequence_count == 255U)
        {
            sequence_count = static_cast< std::size_t >(read_integer(block, position, 2U)) + 0x7f00U;
            position += 2U;
        }
 
        std::size_t const block_output_start = output.size();
        std::size_t const block_output_limit = std::min< std::size_t >(window_size, 128U * 1024U);
        if (sequence_count == 0U)
        {
            if (position != block.size())
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "Zstandard compressed block contains trailing sequence data");
            }
            if (literals.literals.size() > block_output_limit)
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "Zstandard compressed block exceeds its regenerated-size limit");
            }
            if (output.size() > maximum_output_size || literals.literals.size() > maximum_output_size - output.size())
            {
                throw compression_error(error_code::output_limit_exceeded, format::zstandard, "decompressed output exceeds configured limit");
            }
            output.insert(output.end(), literals.literals.begin(), literals.literals.end());
            return;
        }
 
        std::uint8_t const modes = static_cast< std::uint8_t >(read_integer(block, position, 1U));
        ++position;
        if ((modes & 0x03U) != 0U)
        {
            throw compression_error(error_code::invalid_data, format::zstandard, "reserved Zstandard sequence mode bits are set");
        }
 
        auto read_table = [&](std::uint8_t mode, std::uint8_t maximum_symbol, std::uint8_t maximum_accuracy_log, fse_table predefined_table, std::optional< fse_table >& previous_table)
        {
            if (mode == 0U)
            {
                previous_table = std::move(predefined_table);
                return;
            }
            if (mode == 1U)
            {
                std::uint8_t const symbol = static_cast< std::uint8_t >(read_integer(block, position, 1U));
                ++position;
                if (symbol > maximum_symbol)
                {
                    throw compression_error(error_code::invalid_data, format::zstandard, "Zstandard RLE sequence symbol exceeds its alphabet");
                }
                previous_table = build_rle_fse_table(symbol);
                return;
            }
            if (mode == 2U)
            {
                if (position > block.size())
                {
                    throw compression_error(error_code::invalid_data, format::zstandard, "truncated Zstandard sequence table");
                }
                normalized_probability_result probabilities = parse_normalized_probabilities(block.subspan(position), maximum_symbol, maximum_accuracy_log);
                position += probabilities.consumed_bytes;
                previous_table = build_fse_table(probabilities.probabilities, probabilities.accuracy_log);
                return;
            }
            if (!previous_table.has_value())
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "Zstandard repeat mode has no previous FSE table");
            }
        };
 
        read_table(static_cast< std::uint8_t >(modes >> 6U), 35U, 9U, build_predefined_literal_length_table(), state.literal_length_table);
        read_table(static_cast< std::uint8_t >((modes >> 4U) & 0x03U), 31U, 8U, build_predefined_offset_table(), state.offset_table);
        read_table(static_cast< std::uint8_t >((modes >> 2U) & 0x03U), 52U, 9U, build_predefined_match_length_table(), state.match_length_table);
 
        if (position >= block.size())
        {
            throw compression_error(error_code::invalid_data, format::zstandard, "missing Zstandard sequence bitstream");
        }
        fse_table const& literal_length_table = *state.literal_length_table;
        fse_table const& offset_table = *state.offset_table;
        fse_table const& match_length_table = *state.match_length_table;
        reverse_bit_reader reader(block.subspan(position));
        std::size_t literal_length_state = reader.read_bits(literal_length_table.accuracy_log);
        std::size_t offset_state = reader.read_bits(offset_table.accuracy_log);
        std::size_t match_length_state = reader.read_bits(match_length_table.accuracy_log);
        if (literal_length_state >= literal_length_table.entries.size() || offset_state >= offset_table.entries.size() || match_length_state >= match_length_table.entries.size())
        {
            throw compression_error(error_code::invalid_data, format::zstandard, "invalid initial Zstandard FSE state");
        }
 
        std::size_t literal_position = 0U;
        for (std::size_t sequence_index = 0U; sequence_index < sequence_count; ++sequence_index)
        {
            fse_entry const literal_length_transition = literal_length_table.entries[literal_length_state];
            fse_entry const offset_transition = offset_table.entries[offset_state];
            fse_entry const match_length_transition = match_length_table.entries[match_length_state];
            if (literal_length_transition.symbol >= literal_length_codes.size() || match_length_transition.symbol >= match_length_codes.size() || offset_transition.symbol > 31U)
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "Zstandard sequence code exceeds its alphabet");
            }
 
            length_code_entry const literal_length_code = literal_length_codes[literal_length_transition.symbol];
            length_code_entry const match_length_code = match_length_codes[match_length_transition.symbol];
            std::uint64_t const offset_value_64 = (std::uint64_t{1U} << offset_transition.symbol) + reader.read_bits(offset_transition.symbol);
            std::size_t const match_length = static_cast< std::size_t >(match_length_code.baseline + reader.read_bits(match_length_code.number_of_bits));
            std::size_t const literal_length = static_cast< std::size_t >(literal_length_code.baseline + reader.read_bits(literal_length_code.number_of_bits));
            if (offset_value_64 > std::numeric_limits< std::size_t >::max())
            {
                throw compression_error(error_code::unsupported_feature, format::zstandard, "Zstandard offset exceeds the platform size");
            }
            std::size_t const offset_value = static_cast< std::size_t >(offset_value_64);
            if (literal_position > literals.literals.size() || literal_length > literals.literals.size() - literal_position)
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "Zstandard sequence consumes too many literals");
            }
            if (output.size() > maximum_output_size || literal_length > maximum_output_size - output.size())
            {
                throw compression_error(error_code::output_limit_exceeded, format::zstandard, "decompressed output exceeds configured limit");
            }
            output.insert(output.end(), literals.literals.begin() + static_cast< std::ptrdiff_t >(literal_position), literals.literals.begin() + static_cast< std::ptrdiff_t >(literal_position + literal_length));
            literal_position += literal_length;
 
            std::size_t resolved_offset = 0U;
            bool insert_new_offset = false;
            std::size_t repeated_index = 0U;
            if (offset_value > 3U)
            {
                resolved_offset = offset_value - 3U;
                insert_new_offset = true;
            }
            else if (literal_length == 0U && offset_value == 3U)
            {
                if (state.repeated_offsets[0U] <= 1U)
                {
                    throw compression_error(error_code::invalid_data, format::zstandard, "invalid decremented Zstandard repeat offset");
                }
                resolved_offset = state.repeated_offsets[0U] - 1U;
                insert_new_offset = true;
            }
            else
            {
                repeated_index = literal_length == 0U ? offset_value : offset_value - 1U;
                if (repeated_index >= state.repeated_offsets.size())
                {
                    throw compression_error(error_code::invalid_data, format::zstandard, "invalid Zstandard repeat offset code");
                }
                resolved_offset = state.repeated_offsets[repeated_index];
            }
 
            if (insert_new_offset)
            {
                state.repeated_offsets[2U] = state.repeated_offsets[1U];
                state.repeated_offsets[1U] = state.repeated_offsets[0U];
                state.repeated_offsets[0U] = resolved_offset;
            }
            else
            {
                for (std::size_t index = repeated_index; index > 0U; --index)
                {
                    state.repeated_offsets[index] = state.repeated_offsets[index - 1U];
                }
                state.repeated_offsets[0U] = resolved_offset;
            }
            if (resolved_offset == 0U || resolved_offset > output.size() || resolved_offset > window_size)
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "Zstandard match offset exceeds available history");
            }
            if (output.size() > maximum_output_size || match_length > maximum_output_size - output.size())
            {
                throw compression_error(error_code::output_limit_exceeded, format::zstandard, "decompressed output exceeds configured limit");
            }
            for (std::size_t match_index = 0U; match_index < match_length; ++match_index)
            {
                output.push_back(output[output.size() - resolved_offset]);
            }
 
            if (sequence_index + 1U < sequence_count)
            {
                literal_length_state = literal_length_transition.baseline + reader.read_bits(literal_length_transition.number_of_bits);
                match_length_state = match_length_transition.baseline + reader.read_bits(match_length_transition.number_of_bits);
                offset_state = offset_transition.baseline + reader.read_bits(offset_transition.number_of_bits);
                if (literal_length_state >= literal_length_table.entries.size() || offset_state >= offset_table.entries.size() || match_length_state >= match_length_table.entries.size())
                {
                    throw compression_error(error_code::invalid_data, format::zstandard, "updated Zstandard FSE state exceeds its table");
                }
            }
        }
 
        if (reader.remaining_bits() != 0U)
        {
            throw compression_error(error_code::invalid_data, format::zstandard, "Zstandard sequence bitstream was not fully consumed");
        }
        std::size_t const remaining_literals = literals.literals.size() - literal_position;
        if (output.size() > maximum_output_size || remaining_literals > maximum_output_size - output.size())
        {
            throw compression_error(error_code::output_limit_exceeded, format::zstandard, "decompressed output exceeds configured limit");
        }
        output.insert(output.end(), literals.literals.begin() + static_cast< std::ptrdiff_t >(literal_position), literals.literals.end());
        if (output.size() - block_output_start > block_output_limit)
        {
            throw compression_error(error_code::invalid_data, format::zstandard, "Zstandard compressed block exceeds its regenerated-size limit");
        }
    }
 
    /**
     * @brief Selects the sequence length code covering one exact length.
     * @tparam code_count Number of entries in @p codes.
     * @param length Exact sequence length.
     * @param codes Ordered baseline and additional-bit definitions.
     * @return Wire code and additional value bits.
     */
    template < std::size_t code_count >
    [[nodiscard]] inline encoded_length encode_length(std::size_t length, std::array< length_code_entry, code_count > const& codes)
    {
        for (std::size_t code = 0U; code < codes.size(); ++code)
        {
            length_code_entry const definition = codes[code];
            std::uint32_t const maximum_additional_value = definition.number_of_bits == 0U ? 0U : (std::uint32_t{1U} << definition.number_of_bits) - 1U;
            if (length >= definition.baseline && length - definition.baseline <= maximum_additional_value)
            {
                return encoded_length{static_cast< std::uint8_t >(code), static_cast< std::uint32_t >(length - definition.baseline), definition.number_of_bits};
            }
        }
        throw compression_error(error_code::invalid_data, format::zstandard, "Zstandard sequence length has no wire code");
    }
 
    /**
     * @brief Finds a block prefix whose repetition regenerates the suffix.
     * @param block Candidate periodic block.
     * @return Repeating period, or no value if no useful repeated suffix exists.
     */
    [[nodiscard]] inline std::optional< std::size_t > find_repeating_period(std::span< std::byte const > block)
    {
        if (block.size() < 4U)
        {
            return std::nullopt;
        }
        std::vector< std::size_t > prefix_lengths(block.size(), 0U);
        for (std::size_t position = 1U; position < block.size(); ++position)
        {
            std::size_t prefix_length = prefix_lengths[position - 1U];
            while (prefix_length != 0U && block[position] != block[prefix_length])
            {
                prefix_length = prefix_lengths[prefix_length - 1U];
            }
            if (block[position] == block[prefix_length])
            {
                ++prefix_length;
            }
            prefix_lengths[position] = prefix_length;
        }
        std::size_t const match_length = prefix_lengths.back();
        if (match_length < 3U)
        {
            return std::nullopt;
        }
        return block.size() - match_length;
    }
 
    /**
     * @brief Encodes a periodic block as raw literals plus one match sequence.
     * @param block Candidate block.
     * @return Compressed payload when smaller than the source, otherwise no value.
     */
    [[nodiscard]] inline std::optional< std::vector< std::byte > > compress_periodic_block(std::span< std::byte const > block)
    {
        std::optional< std::size_t > const period = find_repeating_period(block);
        if (!period.has_value())
        {
            return std::nullopt;
        }
        std::size_t const match_length = block.size() - *period;
        encoded_length const literal_length = encode_length(*period, literal_length_codes);
        encoded_length const encoded_match_length = encode_length(match_length, match_length_codes);
        std::uint64_t const offset_value = static_cast< std::uint64_t >(*period) + 3U;
        std::uint8_t const offset_code = static_cast< std::uint8_t >(std::bit_width(offset_value) - 1);
        std::uint64_t const offset_additional_value = offset_value - (std::uint64_t{1U} << offset_code);
 
        std::vector< std::byte > encoded;
        if (*period <= 31U)
        {
            encoded.push_back(static_cast< std::byte >(*period << 3U));
        }
        else if (*period <= 4095U)
        {
            append_integer(encoded, (*period << 4U) | 0x04U, 2U);
        }
        else
        {
            append_integer(encoded, (*period << 4U) | 0x0cU, 3U);
        }
        encoded.insert(encoded.end(), block.begin(), block.begin() + static_cast< std::ptrdiff_t >(*period));
        encoded.push_back(std::byte{0x01});
        encoded.push_back(std::byte{0x54});
        encoded.push_back(static_cast< std::byte >(literal_length.code));
        encoded.push_back(static_cast< std::byte >(offset_code));
        encoded.push_back(static_cast< std::byte >(encoded_match_length.code));
 
        std::size_t const bit_count = literal_length.number_of_bits + encoded_match_length.number_of_bits + offset_code;
        std::vector< std::byte > bitstream((bit_count + 1U + 7U) / 8U, std::byte{0});
        std::size_t bit_position = 0U;
        auto append_bits = [&](std::uint64_t value, std::uint8_t count)
        {
            for (std::uint8_t bit_index = 0U; bit_index < count; ++bit_index)
            {
                if (((value >> bit_index) & 1U) != 0U)
                {
                    bitstream[bit_position / 8U] |= static_cast< std::byte >(1U << (bit_position % 8U));
                }
                ++bit_position;
            }
        };
        append_bits(literal_length.additional_value, literal_length.number_of_bits);
        append_bits(encoded_match_length.additional_value, encoded_match_length.number_of_bits);
        append_bits(offset_additional_value, offset_code);
        bitstream[bit_position / 8U] |= static_cast< std::byte >(1U << (bit_position % 8U));
        encoded.insert(encoded.end(), bitstream.begin(), bitstream.end());
        if (encoded.size() >= block.size())
        {
            return std::nullopt;
        }
        return encoded;
    }
 
    /**
     * @brief Compresses an iterator range as a Zstandard frame.
     * @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 22.
     * @return Destination advanced past the frame checksum.
     */
    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(3);
        if (level < 0 || level > 22)
        {
            throw compression_error(error_code::invalid_option, format::zstandard, "Zstandard compression level must be between 0 and 22");
        }
        auto write_integer = [&](std::uint64_t value, std::uint8_t byte_count)
        {
            for (std::uint8_t index = 0U; index < byte_count; ++index)
            {
                implementation::write_byte(output, static_cast< std::byte >(value >> (index * 8U)));
            }
        };
        write_integer(0xfd2fb528U, 4U);
        implementation::write_byte(output, std::byte{0x00});
        implementation::write_byte(output, std::byte{0x38});
 
        constexpr std::size_t block_limit = 128U * 1024U;
        std::vector< std::byte > block;
        block.reserve(block_limit);
        bool emitted_block = false;
        do
        {
            block.clear();
            while (first != last && block.size() < block_limit)
            {
                block.push_back(implementation::to_byte(*first));
                ++first;
            }
            bool const last_block = first == last;
            bool rle_block = !block.empty();
            for (std::size_t index = 1U; index < block.size() && rle_block; ++index)
            {
                rle_block = block[index] == block[0U];
            }
            std::optional< std::vector< std::byte > > encoded;
            if (!rle_block && level != 0)
            {
                encoded = compress_periodic_block(block);
            }
            if (rle_block)
            {
                std::uint32_t const header = static_cast< std::uint32_t >(last_block ? 1U : 0U) | 2U | (static_cast< std::uint32_t >(block.size()) << 3U);
                write_integer(header, 3U);
                implementation::write_byte(output, block[0U]);
            }
            else if (encoded.has_value())
            {
                std::uint32_t const header = static_cast< std::uint32_t >(last_block ? 1U : 0U) | 4U | (static_cast< std::uint32_t >(encoded->size()) << 3U);
                write_integer(header, 3U);
                for (std::byte value : *encoded)
                {
                    implementation::write_byte(output, value);
                }
            }
            else
            {
                std::uint32_t const header = static_cast< std::uint32_t >(last_block ? 1U : 0U) | (static_cast< std::uint32_t >(block.size()) << 3U);
                write_integer(header, 3U);
                for (std::byte value : block)
                {
                    implementation::write_byte(output, value);
                }
            }
            emitted_block = true;
            if (last_block)
            {
                break;
            }
        } while (!emitted_block || first != last);
        return output;
    }
 
    /**
     * @brief Decompresses one or more Zstandard or skippable frames.
     * @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-frame 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 > reader(std::move(first), std::move(last));
        auto read_byte = [&]() -> std::byte
        {
            std::byte value{};
            if (!reader.read(value))
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "truncated Zstandard frame");
            }
            return value;
        };
        auto read_integer = [&](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_frame = false;
        while (!reader.empty())
        {
            std::uint32_t const magic = static_cast< std::uint32_t >(read_integer(4U));
            if (magic >= 0x184d2a50U && magic <= 0x184d2a5fU)
            {
                std::size_t const skip_size = static_cast< std::size_t >(read_integer(4U));
                for (std::size_t index = 0U; index < skip_size; ++index)
                {
                    static_cast< void >(read_byte());
                }
                continue;
            }
            if (decoded_frame && !options.allow_concatenated_streams)
            {
                throw compression_error(error_code::trailing_data, format::zstandard, "Zstandard frame contains trailing data");
            }
            if (magic != 0xfd2fb528U)
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "invalid Zstandard frame magic");
            }
            std::uint8_t const descriptor = std::to_integer< std::uint8_t >(read_byte());
            if ((descriptor & 0x08U) != 0U)
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "Zstandard frame uses reserved descriptor bits");
            }
            bool const single_segment = (descriptor & 0x20U) != 0U;
            bool const checksum_present = (descriptor & 0x04U) != 0U;
            std::uint8_t const dictionary_flag = descriptor & 0x03U;
            std::uint8_t const content_size_flag = descriptor >> 6U;
            std::optional< std::size_t > window_size;
            if (!single_segment)
            {
                std::uint8_t const window_descriptor = std::to_integer< std::uint8_t >(read_byte());
                std::uint8_t const window_log = static_cast< std::uint8_t >(10U + (window_descriptor >> 3U));
                if (window_log >= std::numeric_limits< std::size_t >::digits)
                {
                    throw compression_error(error_code::unsupported_feature, format::zstandard, "Zstandard window exceeds the platform size");
                }
                std::size_t const base = static_cast< std::size_t >(1U) << window_log;
                window_size = base + (base >> 3U) * (window_descriptor & 0x07U);
            }
            constexpr std::array< std::uint8_t, 4U > dictionary_sizes{0U, 1U, 2U, 4U};
            if (read_integer(dictionary_sizes[dictionary_flag]) != 0U)
            {
                throw compression_error(error_code::unsupported_feature, format::zstandard, "dictionary-based Zstandard frames are unsupported");
            }
            std::uint8_t content_size_bytes = 0U;
            if (content_size_flag == 0U)
            {
                content_size_bytes = single_segment ? 1U : 0U;
            }
            else
            {
                constexpr std::array< std::uint8_t, 4U > content_sizes{0U, 2U, 4U, 8U};
                content_size_bytes = content_sizes[content_size_flag];
            }
            std::optional< std::uint64_t > content_size;
            if (content_size_bytes != 0U)
            {
                content_size = read_integer(content_size_bytes);
                if (content_size_flag == 1U)
                {
                    *content_size += 256U;
                }
                if (*content_size > options.maximum_output_size - std::min(total_output, options.maximum_output_size))
                {
                    throw compression_error(error_code::output_limit_exceeded, format::zstandard, "Zstandard content size exceeds configured limit");
                }
            }
            if (single_segment)
            {
                window_size = static_cast< std::size_t >(content_size.value_or(0U));
            }
            std::size_t const effective_window = window_size.value_or(128U * 1024U);
            std::vector< std::byte > history;
            history.reserve(std::min< std::size_t >(effective_window, options.maximum_output_size));
            xxhash64_accumulator checksum;
            decoder_state state;
            std::size_t const frame_begin = total_output;
            auto emit_output = [&](std::byte value)
            {
                if (total_output == options.maximum_output_size)
                {
                    throw compression_error(error_code::output_limit_exceeded, format::zstandard, "decompressed output exceeds configured limit");
                }
                if (checksum_present)
                {
                    checksum.update(value);
                }
                ++total_output;
                implementation::write_byte(output, value);
            };
            auto emit = [&](std::byte value)
            {
                history.push_back(value);
                emit_output(value);
            };
 
            bool last_block = false;
            while (!last_block)
            {
                std::uint32_t const header = static_cast< std::uint32_t >(read_integer(3U));
                last_block = (header & 1U) != 0U;
                std::uint8_t const block_type = static_cast< std::uint8_t >((header >> 1U) & 0x03U);
                std::size_t const block_size = header >> 3U;
                std::size_t const maximum_block = std::min< std::size_t >(effective_window, 128U * 1024U);
                if (block_size > maximum_block)
                {
                    throw compression_error(error_code::invalid_data, format::zstandard, "Zstandard block exceeds the frame block-size limit");
                }
                if (block_type == 0U)
                {
                    for (std::size_t index = 0U; index < block_size; ++index)
                    {
                        emit(read_byte());
                    }
                }
                else if (block_type == 1U)
                {
                    std::byte const value = read_byte();
                    for (std::size_t index = 0U; index < block_size; ++index)
                    {
                        emit(value);
                    }
                }
                else if (block_type == 2U)
                {
                    std::vector< std::byte > block;
                    block.reserve(block_size);
                    for (std::size_t index = 0U; index < block_size; ++index)
                    {
                        block.push_back(read_byte());
                    }
                    std::vector< std::byte > working = std::move(history);
                    std::size_t const history_size = working.size();
                    std::size_t const available = options.maximum_output_size - total_output;
                    decompress_compressed_block(block, effective_window, history_size + available, state, working);
                    for (std::size_t index = history_size; index < working.size(); ++index)
                    {
                        emit_output(working[index]);
                    }
                    std::size_t const retained = std::min< std::size_t >(working.size(), effective_window);
                    history.assign(working.end() - static_cast< std::ptrdiff_t >(retained), working.end());
                }
                else
                {
                    throw compression_error(error_code::invalid_data, format::zstandard, "reserved Zstandard block type");
                }
                if (history.size() > effective_window)
                {
                    history.erase(history.begin(), history.begin() + static_cast< std::ptrdiff_t >(history.size() - effective_window));
                }
            }
            if (checksum_present && static_cast< std::uint32_t >(read_integer(4U)) != static_cast< std::uint32_t >(checksum.value()))
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "Zstandard content checksum mismatch");
            }
            if (content_size.has_value() && total_output - frame_begin != *content_size)
            {
                throw compression_error(error_code::invalid_data, format::zstandard, "Zstandard content size mismatch");
            }
            decoded_frame = true;
        }
        if (!decoded_frame)
        {
            throw compression_error(error_code::invalid_data, format::zstandard, "empty Zstandard input");
        }
        return output;
    }
 
} // namespace rpnx::compression::zstandard_codec
 
#endif