deflate.hpp

Go to the documentation of this file.

#ifndef RPNX_COMPRESSION_IMPLEMENTATION_DEFLATE_HPP
#define RPNX_COMPRESSION_IMPLEMENTATION_DEFLATE_HPP
 
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <limits>
#include <span>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>
 
#include <rpnx/compression/implementation/io.hpp>
 
/**
 * @file
 * @brief Native raw DEFLATE, zlib, and gzip coding implementation.
 */
 
/** @brief Internal implementation shared by raw DEFLATE, zlib, gzip, and ZIP. */
namespace rpnx::compression::deflate_codec
{
 
    /** Canonical Huffman decoder for the bit-reversed codes used by DEFLATE. */
    class huffman_decoder
    {
      public:
        /**
         * @brief Builds and validates a decoder from per-symbol code lengths.
         * @param lengths Code length for each symbol in symbol order.
         * @param stream_format Format used to classify validation errors.
         * @param allow_empty Whether an all-zero length set is accepted.
         * @throws compression_error If lengths exceed 15 bits or oversubscribe the tree.
         */
        void build(std::span< std::uint8_t const > lengths, format stream_format, bool allow_empty = false)
        {
            for (std::vector< std::int16_t >& table : m_symbols_by_length)
            {
                table.clear();
            }
            std::array< std::uint16_t, 16U > counts{};
            std::size_t symbol_count = 0U;
            for (std::uint8_t length : lengths)
            {
                if (length > 15U)
                {
                    throw compression_error(error_code::invalid_data, stream_format, "DEFLATE Huffman code is too long");
                }
                if (length != 0U)
                {
                    ++counts[length];
                    ++symbol_count;
                }
            }
            if (symbol_count == 0U)
            {
                if (allow_empty)
                {
                    return;
                }
                throw compression_error(error_code::invalid_data, stream_format, "DEFLATE Huffman tree is empty");
            }
 
            std::int32_t remaining_codes = 1;
            for (std::size_t length = 1U; length <= 15U; ++length)
            {
                remaining_codes = remaining_codes * 2 - counts[length];
                if (remaining_codes < 0)
                {
                    throw compression_error(error_code::invalid_data, stream_format, "oversubscribed DEFLATE Huffman tree");
                }
            }
 
            std::array< std::uint16_t, 16U > next_code{};
            std::uint16_t code = 0U;
            for (std::size_t length = 1U; length <= 15U; ++length)
            {
                code = static_cast< std::uint16_t >((code + counts[length - 1U]) << 1U);
                next_code[length] = code;
                if (counts[length] != 0U)
                {
                    m_symbols_by_length[length].assign(static_cast< std::size_t >(1U) << length, -1);
                }
            }
 
            for (std::size_t symbol = 0U; symbol < lengths.size(); ++symbol)
            {
                std::uint8_t const length = lengths[symbol];
                if (length == 0U)
                {
                    continue;
                }
                std::uint16_t canonical_code = next_code[length]++;
                std::uint16_t reversed_code = 0U;
                for (std::uint8_t bit = 0U; bit < length; ++bit)
                {
                    reversed_code = static_cast< std::uint16_t >((static_cast< std::uint32_t >(reversed_code) << 1U) | (static_cast< std::uint32_t >(canonical_code) & 1U));
                    canonical_code = static_cast< std::uint16_t >(canonical_code >> 1U);
                }
                m_symbols_by_length[length][reversed_code] = static_cast< std::int16_t >(symbol);
            }
        }
 
        /**
         * @brief Decodes one symbol from a bit reader.
         * @tparam reader_type LSB-first reader providing read_bits().
         * @param reader Source bit reader.
         * @param stream_format Format used to classify validation errors.
         * @return Decoded symbol index.
         * @throws compression_error If no code matches the next input bits.
         */
        template < typename reader_type >
        [[nodiscard]] std::uint16_t decode(reader_type& reader, format stream_format) const
        {
            std::uint16_t code = 0U;
            for (std::uint8_t length = 1U; length <= 15U; ++length)
            {
                code = static_cast< std::uint16_t >(code | (reader.read_bits(1U) << (length - 1U)));
                if (!m_symbols_by_length[length].empty() && m_symbols_by_length[length][code] >= 0)
                {
                    return static_cast< std::uint16_t >(m_symbols_by_length[length][code]);
                }
            }
            throw compression_error(error_code::invalid_data, stream_format, "invalid DEFLATE Huffman code");
        }
 
      private:
        std::array< std::vector< std::int16_t >, 16U > m_symbols_by_length;
    };
 
    /**
     * @brief Reverses the selected low bits for DEFLATE wire order.
     * @param value Value containing the bits to reverse.
     * @param bit_count Number of low bits to reverse.
     * @return Reversed bits in the low part of the result.
     */
    [[nodiscard]] inline std::uint16_t reverse_bits(std::uint16_t value, std::uint8_t bit_count) noexcept
    {
        std::uint16_t result = 0U;
        for (std::uint8_t bit = 0U; bit < bit_count; ++bit)
        {
            result = static_cast< std::uint16_t >((static_cast< std::uint32_t >(result) << 1U) | (static_cast< std::uint32_t >(value) & 1U));
            value = static_cast< std::uint16_t >(value >> 1U);
        }
        return result;
    }
 
    /**
     * @brief Emits one fixed-Huffman literal or length symbol.
     * @tparam writer_type LSB-first writer providing write_bits().
     * @param writer Destination bit writer.
     * @param symbol DEFLATE literal, end-of-block, or length symbol.
     */
    template < typename writer_type >
    void write_fixed_symbol(writer_type& writer, std::uint16_t symbol)
    {
        if (symbol <= 143U)
        {
            writer.write_bits(reverse_bits(static_cast< std::uint16_t >(0x30U + symbol), 8U), 8U);
        }
        else if (symbol <= 255U)
        {
            writer.write_bits(reverse_bits(static_cast< std::uint16_t >(0x190U + symbol - 144U), 9U), 9U);
        }
        else if (symbol <= 279U)
        {
            writer.write_bits(reverse_bits(static_cast< std::uint16_t >(symbol - 256U), 7U), 7U);
        }
        else
        {
            writer.write_bits(reverse_bits(static_cast< std::uint16_t >(0xc0U + symbol - 280U), 8U), 8U);
        }
    }
 
    /**
     * @brief Computes the reflected IEEE CRC-32 used by gzip and ZIP.
     * @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 checksum = 0xffffffffU;
        for (std::byte value : input)
        {
            checksum ^= std::to_integer< std::uint8_t >(value);
            for (std::uint8_t bit = 0U; bit < 8U; ++bit)
            {
                std::uint32_t const mask = 0U - (checksum & 1U);
                checksum = (checksum >> 1U) ^ (0xedb88320U & mask);
            }
        }
        return ~checksum;
    }
 
    /**
     * @brief LSB-first bit writer that emits bytes through an STL output iterator.
     * @tparam output_iterator Destination accepting byte assignments.
     */
    template < typename output_iterator >
    class iterator_bit_writer
    {
      public:
        /**
         * @brief Constructs a writer owning an output iterator.
         * @param output Destination iterator.
         */
        explicit iterator_bit_writer(output_iterator output) : m_output(std::move(output))
        {
        }
 
        /**
         * @brief Appends the selected low bits of a value.
         * @param value Value containing the field.
         * @param bit_count Number of low bits to emit least significant first.
         */
        void write_bits(std::uint32_t value, std::uint8_t bit_count)
        {
            m_bits |= static_cast< std::uint64_t >(value) << m_bit_count;
            m_bit_count = static_cast< std::uint8_t >(m_bit_count + bit_count);
            while (m_bit_count >= 8U)
            {
                implementation::write_byte(m_output, static_cast< std::byte >(m_bits & 0xffU));
                m_bits >>= 8U;
                m_bit_count = static_cast< std::uint8_t >(m_bit_count - 8U);
            }
        }
 
        /**
         * @brief Flushes zero byte padding and releases the output iterator.
         * @return Destination iterator advanced past all emitted bytes.
         */
        [[nodiscard]] output_iterator finish()
        {
            if (m_bit_count != 0U)
            {
                implementation::write_byte(m_output, static_cast< std::byte >(m_bits & 0xffU));
                m_bits = 0U;
                m_bit_count = 0U;
            }
            return std::move(m_output);
        }
 
      private:
        output_iterator m_output;
        std::uint64_t m_bits = 0U;
        std::uint8_t m_bit_count = 0U;
    };
 
    /**
     * @brief LSB-first bit reader that consumes a single-pass byte reader.
     * @tparam byte_reader_type Source reader providing read().
     */
    template < typename byte_reader_type >
    class iterator_bit_reader
    {
      public:
        /**
         * @brief Constructs a bit reader for one DEFLATE-family stream.
         * @param input Borrowed source reader that must outlive this object.
         * @param stream_format Format used to classify truncated-input errors.
         */
        iterator_bit_reader(byte_reader_type& input, format stream_format) noexcept : m_input(input), m_stream_format(stream_format)
        {
        }
 
        /**
         * @brief Consumes a low-order-first bit field.
         * @param bit_count Number of bits to consume.
         * @return Field value with the earliest bit in the least significant position.
         * @throws compression_error If the source ends before the field is complete.
         */
        [[nodiscard]] std::uint32_t read_bits(std::uint8_t bit_count)
        {
            while (m_bit_count < bit_count)
            {
                std::byte value{};
                if (!m_input.read(value))
                {
                    throw compression_error(error_code::invalid_data, m_stream_format, "truncated DEFLATE bit stream");
                }
                m_bits |= static_cast< std::uint64_t >(std::to_integer< std::uint8_t >(value)) << m_bit_count;
                m_bit_count = static_cast< std::uint8_t >(m_bit_count + 8U);
            }
            std::uint32_t const mask = bit_count == 32U ? std::numeric_limits< std::uint32_t >::max() : (static_cast< std::uint32_t >(1U) << bit_count) - 1U;
            std::uint32_t const value = static_cast< std::uint32_t >(m_bits) & mask;
            m_bits >>= bit_count;
            m_bit_count = static_cast< std::uint8_t >(m_bit_count - bit_count);
            return value;
        }
 
        /** Discard padding through the next byte boundary. */
        void align_to_byte() noexcept
        {
            m_bits = 0U;
            m_bit_count = 0U;
        }
 
      private:
        byte_reader_type& m_input;
        format m_stream_format;
        std::uint64_t m_bits = 0U;
        std::uint8_t m_bit_count = 0U;
    };
 
    /**
     * @brief Emits one fixed-Huffman DEFLATE block from a bounded search buffer.
     * @tparam writer_type LSB-first writer providing write_bits().
     * @param writer Destination bit writer.
     * @param input Uncompressed block.
     * @param final_block Whether to set the DEFLATE final-block bit.
     * @param level Compression level controlling match-search depth.
     */
    template < typename writer_type >
    void compress_fixed_block(writer_type& writer, std::span< std::byte const > input, bool final_block, std::int32_t level)
    {
        constexpr std::array< std::uint16_t, 29U > length_bases{3U, 4U, 5U, 6U, 7U, 8U, 9U, 10U, 11U, 13U, 15U, 17U, 19U, 23U, 27U, 31U, 35U, 43U, 51U, 59U, 67U, 83U, 99U, 115U, 131U, 163U, 195U, 227U, 258U};
        constexpr std::array< std::uint8_t, 29U > length_extras{0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 1U, 1U, 1U, 1U, 2U, 2U, 2U, 2U, 3U, 3U, 3U, 3U, 4U, 4U, 4U, 4U, 5U, 5U, 5U, 5U, 0U};
        constexpr std::array< std::uint16_t, 30U > distance_bases{1U, 2U, 3U, 4U, 5U, 7U, 9U, 13U, 17U, 25U, 33U, 49U, 65U, 97U, 129U, 193U, 257U, 385U, 513U, 769U, 1025U, 1537U, 2049U, 3073U, 4097U, 6145U, 8193U, 12289U, 16385U, 24577U};
        constexpr std::array< std::uint8_t, 30U > distance_extras{0U, 0U, 0U, 0U, 1U, 1U, 2U, 2U, 3U, 3U, 4U, 4U, 5U, 5U, 6U, 6U, 7U, 7U, 8U, 8U, 9U, 9U, 10U, 10U, 11U, 11U, 12U, 12U, 13U, 13U};
 
        writer.write_bits(final_block ? 1U : 0U, 1U);
        writer.write_bits(1U, 2U);
        constexpr std::size_t no_position = std::numeric_limits< std::size_t >::max();
        std::array< std::size_t, 65536U > hash_heads{};
        hash_heads.fill(no_position);
        std::vector< std::size_t > previous(input.size(), no_position);
        std::size_t position = 0U;
        std::size_t const maximum_search_depth = 8U + static_cast< std::size_t >(level) * 28U;
        while (position < input.size())
        {
            std::size_t best_length = 0U;
            std::size_t best_distance = 0U;
            if (position + 2U < input.size())
            {
                std::uint32_t const hash = (static_cast< std::uint32_t >(std::to_integer< std::uint8_t >(input[position])) * 251U ^ static_cast< std::uint32_t >(std::to_integer< std::uint8_t >(input[position + 1U])) * 31U ^ std::to_integer< std::uint8_t >(input[position + 2U])) & 0xffffU;
                std::size_t candidate = hash_heads[hash];
                previous[position] = candidate;
                hash_heads[hash] = position;
                std::size_t depth = 0U;
                std::size_t const maximum_length = std::min< std::size_t >(258U, input.size() - position);
                while (candidate != no_position && position - candidate <= 32768U && depth < maximum_search_depth)
                {
                    std::size_t length = 0U;
                    while (length < maximum_length && input[candidate + length] == input[position + length])
                    {
                        ++length;
                    }
                    if (length > best_length && length >= 3U)
                    {
                        best_length = length;
                        best_distance = position - candidate;
                    }
                    candidate = previous[candidate];
                    ++depth;
                }
            }
            if (best_length < 3U)
            {
                write_fixed_symbol(writer, std::to_integer< std::uint8_t >(input[position++]));
                continue;
            }
            std::size_t length_index = 0U;
            while (length_index + 1U < length_bases.size() && best_length >= length_bases[length_index + 1U])
            {
                ++length_index;
            }
            write_fixed_symbol(writer, static_cast< std::uint16_t >(257U + length_index));
            writer.write_bits(static_cast< std::uint32_t >(best_length - length_bases[length_index]), length_extras[length_index]);
            std::size_t distance_index = 0U;
            while (distance_index + 1U < distance_bases.size() && best_distance >= distance_bases[distance_index + 1U])
            {
                ++distance_index;
            }
            writer.write_bits(reverse_bits(static_cast< std::uint16_t >(distance_index), 5U), 5U);
            writer.write_bits(static_cast< std::uint32_t >(best_distance - distance_bases[distance_index]), distance_extras[distance_index]);
            for (std::size_t offset = 1U; offset < best_length; ++offset)
            {
                std::size_t const inserted = position + offset;
                if (inserted + 2U >= input.size())
                {
                    continue;
                }
                std::uint32_t const hash = (static_cast< std::uint32_t >(std::to_integer< std::uint8_t >(input[inserted])) * 251U ^ static_cast< std::uint32_t >(std::to_integer< std::uint8_t >(input[inserted + 1U])) * 31U ^ std::to_integer< std::uint8_t >(input[inserted + 2U])) & 0xffffU;
                previous[inserted] = hash_heads[hash];
                hash_heads[hash] = inserted;
            }
            position += best_length;
        }
        write_fixed_symbol(writer, 256U);
    }
 
    /**
     * @brief Compresses an iterator range as raw DEFLATE, zlib, or gzip.
     * @tparam input_iterator Single-pass byte iterator.
     * @tparam sentinel Sentinel for @p first.
     * @tparam output_iterator Destination byte iterator.
     * @param stream_format One of format::deflate, format::zlib, or format::gzip.
     * @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 stream trailer.
     */
    template < std::input_iterator input_iterator, std::sentinel_for< input_iterator > sentinel, typename output_iterator >
    output_iterator compress(format stream_format, 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, stream_format, "DEFLATE compression level must be between 0 and 9");
        }
        if (stream_format != format::deflate && stream_format != format::zlib && stream_format != format::gzip)
        {
            throw compression_error(error_code::invalid_option, stream_format, "native DEFLATE codec received an unrelated format");
        }
        if (stream_format == format::zlib)
        {
            std::uint8_t const flags = level <= 1 ? 0x01U : level <= 5 ? 0x5eU : level == 6 ? 0x9cU : 0xdaU;
            implementation::write_byte(output, std::byte{0x78});
            implementation::write_byte(output, static_cast< std::byte >(flags));
        }
        else if (stream_format == format::gzip)
        {
            constexpr std::array< std::byte, 10U > header{std::byte{0x1f}, std::byte{0x8b}, std::byte{0x08}, std::byte{0x00}, std::byte{0x00}, std::byte{0x00}, std::byte{0x00}, std::byte{0x00}, std::byte{0x00}, std::byte{0xff}};
            for (std::byte value : header)
            {
                implementation::write_byte(output, value);
            }
        }
 
        implementation::crc32_accumulator crc;
        implementation::adler32_accumulator adler;
        std::uint32_t input_size = 0U;
        std::size_t const block_limit = level == 0 ? 65535U : 64U * 1024U;
        std::vector< std::byte > block;
        block.reserve(block_limit);
        iterator_bit_writer< output_iterator > writer(std::move(output));
        do
        {
            block.clear();
            while (first != last && block.size() < block_limit)
            {
                std::byte const value = implementation::to_byte(*first);
                ++first;
                block.push_back(value);
                crc.update(value);
                adler.update(value);
                ++input_size;
            }
            bool const final_block = first == last;
            if (level == 0)
            {
                writer.write_bits(final_block ? 1U : 0U, 1U);
                writer.write_bits(0U, 2U);
                output_iterator temporary = writer.finish();
                std::uint16_t const length = static_cast< std::uint16_t >(block.size());
                std::uint16_t const inverse_length = static_cast< std::uint16_t >(~length);
                implementation::write_byte(temporary, static_cast< std::byte >(length));
                implementation::write_byte(temporary, static_cast< std::byte >(length >> 8U));
                implementation::write_byte(temporary, static_cast< std::byte >(inverse_length));
                implementation::write_byte(temporary, static_cast< std::byte >(inverse_length >> 8U));
                for (std::byte value : block)
                {
                    implementation::write_byte(temporary, value);
                }
                writer = iterator_bit_writer< output_iterator >(std::move(temporary));
            }
            else
            {
                compress_fixed_block(writer, block, final_block, level);
            }
            if (final_block)
            {
                break;
            }
        } while (first != last);
        output = writer.finish();
        auto write_u32 = [&](std::uint32_t value, bool little_endian)
        {
            for (std::uint8_t index = 0U; index < 4U; ++index)
            {
                std::uint8_t const shift = little_endian ? index * 8U : static_cast< std::uint8_t >((3U - index) * 8U);
                implementation::write_byte(output, static_cast< std::byte >(value >> shift));
            }
        };
        if (stream_format == format::zlib)
        {
            write_u32(adler.value(), false);
        }
        else if (stream_format == format::gzip)
        {
            write_u32(crc.value(), true);
            write_u32(input_size, true);
        }
        return output;
    }
 
    /**
     * @brief Decompresses raw DEFLATE, zlib, or gzip input.
     * @tparam input_iterator Single-pass byte iterator.
     * @tparam sentinel Sentinel for @p first.
     * @tparam output_iterator Destination byte iterator.
     * @param stream_format One of format::deflate, format::zlib, or format::gzip.
     * @param first First compressed byte.
     * @param last Sentinel past the compressed input.
     * @param output Destination iterator.
     * @param options Output limit and concatenated-member 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(format stream_format, input_iterator first, sentinel last, output_iterator output, decompression_options const& options)
    {
        if (stream_format != format::deflate && stream_format != format::zlib && stream_format != format::gzip)
        {
            throw compression_error(error_code::invalid_option, stream_format, "native DEFLATE codec received an unrelated format");
        }
        constexpr std::array< std::uint16_t, 29U > length_bases{3U, 4U, 5U, 6U, 7U, 8U, 9U, 10U, 11U, 13U, 15U, 17U, 19U, 23U, 27U, 31U, 35U, 43U, 51U, 59U, 67U, 83U, 99U, 115U, 131U, 163U, 195U, 227U, 258U};
        constexpr std::array< std::uint8_t, 29U > length_extras{0U, 0U, 0U, 0U, 0U, 0U, 0U, 0U, 1U, 1U, 1U, 1U, 2U, 2U, 2U, 2U, 3U, 3U, 3U, 3U, 4U, 4U, 4U, 4U, 5U, 5U, 5U, 5U, 0U};
        constexpr std::array< std::uint16_t, 30U > distance_bases{1U, 2U, 3U, 4U, 5U, 7U, 9U, 13U, 17U, 25U, 33U, 49U, 65U, 97U, 129U, 193U, 257U, 385U, 513U, 769U, 1025U, 1537U, 2049U, 3073U, 4097U, 6145U, 8193U, 12289U, 16385U, 24577U};
        constexpr std::array< std::uint8_t, 30U > distance_extras{0U, 0U, 0U, 0U, 1U, 1U, 2U, 2U, 3U, 3U, 4U, 4U, 5U, 5U, 6U, 6U, 7U, 7U, 8U, 8U, 9U, 9U, 10U, 10U, 11U, 11U, 12U, 12U, 13U, 13U};
 
        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, stream_format, "truncated DEFLATE-family stream");
            }
            return value;
        };
        auto read_u32 = [&](bool little_endian) -> std::uint32_t
        {
            std::uint32_t value = 0U;
            for (std::uint8_t index = 0U; index < 4U; ++index)
            {
                std::uint8_t const shift = little_endian ? index * 8U : static_cast< std::uint8_t >((3U - index) * 8U);
                value |= static_cast< std::uint32_t >(std::to_integer< std::uint8_t >(read_byte())) << shift;
            }
            return value;
        };
 
        std::size_t total_output = 0U;
        bool decoded_member = false;
        do
        {
            if (decoded_member && !options.allow_concatenated_streams)
            {
                throw compression_error(error_code::trailing_data, stream_format, "compressed stream contains trailing data");
            }
            if (stream_format == format::zlib)
            {
                std::uint8_t const method = std::to_integer< std::uint8_t >(read_byte());
                std::uint8_t const flags = std::to_integer< std::uint8_t >(read_byte());
                if ((method & 0x0fU) != 8U || (method >> 4U) > 7U || (static_cast< std::uint16_t >(method) * 256U + flags) % 31U != 0U || (flags & 0x20U) != 0U)
                {
                    throw compression_error(error_code::invalid_data, stream_format, "invalid or dictionary-based zlib header");
                }
            }
            else if (stream_format == format::gzip)
            {
                implementation::crc32_accumulator header_crc;
                auto read_header_byte = [&]() -> std::byte
                {
                    std::byte const value = read_byte();
                    header_crc.update(value);
                    return value;
                };
                if (read_header_byte() != std::byte{0x1f} || read_header_byte() != std::byte{0x8b} || read_header_byte() != std::byte{0x08})
                {
                    throw compression_error(error_code::invalid_data, stream_format, "invalid gzip header");
                }
                std::uint8_t const flags = std::to_integer< std::uint8_t >(read_header_byte());
                if ((flags & 0xe0U) != 0U)
                {
                    throw compression_error(error_code::invalid_data, stream_format, "gzip header uses reserved flags");
                }
                for (std::size_t index = 0U; index < 6U; ++index)
                {
                    static_cast< void >(read_header_byte());
                }
                if ((flags & 0x04U) != 0U)
                {
                    std::uint16_t const extra_size = static_cast< std::uint16_t >(std::to_integer< std::uint8_t >(read_header_byte()) | (static_cast< std::uint16_t >(std::to_integer< std::uint8_t >(read_header_byte())) << 8U));
                    for (std::size_t index = 0U; index < extra_size; ++index)
                    {
                        static_cast< void >(read_header_byte());
                    }
                }
                for (std::uint8_t flag : {std::uint8_t{0x08U}, std::uint8_t{0x10U}})
                {
                    if ((flags & flag) != 0U)
                    {
                        while (read_header_byte() != std::byte{0x00})
                        {
                        }
                    }
                }
                if ((flags & 0x02U) != 0U)
                {
                    std::uint16_t const expected = static_cast< std::uint16_t >(std::to_integer< std::uint8_t >(read_byte()) | (static_cast< std::uint16_t >(std::to_integer< std::uint8_t >(read_byte())) << 8U));
                    if (static_cast< std::uint16_t >(header_crc.value()) != expected)
                    {
                        throw compression_error(error_code::invalid_data, stream_format, "gzip header checksum mismatch");
                    }
                }
            }
 
            iterator_bit_reader< decltype(source) > reader(source, stream_format);
            std::array< std::byte, 32768U > history{};
            std::size_t member_size = 0U;
            implementation::crc32_accumulator member_crc;
            implementation::adler32_accumulator member_adler;
            auto emit = [&](std::byte value)
            {
                if (total_output == options.maximum_output_size)
                {
                    throw compression_error(error_code::output_limit_exceeded, stream_format, "decompressed output exceeds configured limit");
                }
                history[member_size % history.size()] = value;
                ++member_size;
                ++total_output;
                member_crc.update(value);
                member_adler.update(value);
                implementation::write_byte(output, value);
            };
 
            bool final_block = false;
            while (!final_block)
            {
                final_block = reader.read_bits(1U) != 0U;
                std::uint32_t const block_type = reader.read_bits(2U);
                if (block_type == 0U)
                {
                    reader.align_to_byte();
                    std::uint16_t const length = static_cast< std::uint16_t >(reader.read_bits(16U));
                    std::uint16_t const inverse = static_cast< std::uint16_t >(reader.read_bits(16U));
                    if (static_cast< std::uint16_t >(length ^ inverse) != 0xffffU)
                    {
                        throw compression_error(error_code::invalid_data, stream_format, "invalid stored DEFLATE block length");
                    }
                    for (std::size_t index = 0U; index < length; ++index)
                    {
                        emit(static_cast< std::byte >(reader.read_bits(8U)));
                    }
                    continue;
                }
                if (block_type == 3U)
                {
                    throw compression_error(error_code::invalid_data, stream_format, "reserved DEFLATE block type");
                }
                huffman_decoder literal_decoder;
                huffman_decoder distance_decoder;
                if (block_type == 1U)
                {
                    std::array< std::uint8_t, 288U > literal_lengths{};
                    std::fill(literal_lengths.begin(), literal_lengths.begin() + 144, 8U);
                    std::fill(literal_lengths.begin() + 144, literal_lengths.begin() + 256, 9U);
                    std::fill(literal_lengths.begin() + 256, literal_lengths.begin() + 280, 7U);
                    std::fill(literal_lengths.begin() + 280, literal_lengths.end(), 8U);
                    std::array< std::uint8_t, 32U > distance_lengths{};
                    distance_lengths.fill(5U);
                    literal_decoder.build(literal_lengths, stream_format);
                    distance_decoder.build(distance_lengths, stream_format);
                }
                else
                {
                    std::size_t const literal_count = reader.read_bits(5U) + 257U;
                    std::size_t const distance_count = reader.read_bits(5U) + 1U;
                    std::size_t const code_length_count = reader.read_bits(4U) + 4U;
                    constexpr std::array< std::uint8_t, 19U > order{16U, 17U, 18U, 0U, 8U, 7U, 9U, 6U, 10U, 5U, 11U, 4U, 12U, 3U, 13U, 2U, 14U, 1U, 15U};
                    std::array< std::uint8_t, 19U > code_lengths{};
                    for (std::size_t index = 0U; index < code_length_count; ++index)
                    {
                        code_lengths[order[index]] = static_cast< std::uint8_t >(reader.read_bits(3U));
                    }
                    huffman_decoder code_length_decoder;
                    code_length_decoder.build(code_lengths, stream_format);
                    std::vector< std::uint8_t > lengths;
                    lengths.reserve(literal_count + distance_count);
                    while (lengths.size() < literal_count + distance_count)
                    {
                        std::uint16_t const symbol = code_length_decoder.decode(reader, stream_format);
                        if (symbol <= 15U)
                        {
                            lengths.push_back(static_cast< std::uint8_t >(symbol));
                        }
                        else if (symbol == 16U)
                        {
                            if (lengths.empty())
                            {
                                throw compression_error(error_code::invalid_data, stream_format, "DEFLATE repeat has no previous code length");
                            }
                            std::size_t const repeat = reader.read_bits(2U) + 3U;
                            if (repeat > literal_count + distance_count - lengths.size())
                            {
                                throw compression_error(error_code::invalid_data, stream_format, "DEFLATE code-length repeat exceeds the tree");
                            }
                            lengths.insert(lengths.end(), repeat, lengths.back());
                        }
                        else if (symbol == 17U || symbol == 18U)
                        {
                            std::size_t const repeat = symbol == 17U ? reader.read_bits(3U) + 3U : reader.read_bits(7U) + 11U;
                            if (repeat > literal_count + distance_count - lengths.size())
                            {
                                throw compression_error(error_code::invalid_data, stream_format, "DEFLATE zero repeat exceeds the tree");
                            }
                            lengths.insert(lengths.end(), repeat, 0U);
                        }
                        else
                        {
                            throw compression_error(error_code::invalid_data, stream_format, "invalid DEFLATE code-length symbol");
                        }
                    }
                    if (lengths[256U] == 0U)
                    {
                        throw compression_error(error_code::invalid_data, stream_format, "DEFLATE literal tree has no end marker");
                    }
                    literal_decoder.build(std::span< std::uint8_t const >(lengths.data(), literal_count), stream_format);
                    distance_decoder.build(std::span< std::uint8_t const >(lengths.data() + literal_count, distance_count), stream_format, true);
                }
                while (true)
                {
                    std::uint16_t const symbol = literal_decoder.decode(reader, stream_format);
                    if (symbol < 256U)
                    {
                        emit(static_cast< std::byte >(symbol));
                        continue;
                    }
                    if (symbol == 256U)
                    {
                        break;
                    }
                    if (symbol < 257U || symbol > 285U)
                    {
                        throw compression_error(error_code::invalid_data, stream_format, "invalid DEFLATE length symbol");
                    }
                    std::size_t const length_index = symbol - 257U;
                    std::size_t const length = length_bases[length_index] + reader.read_bits(length_extras[length_index]);
                    std::uint16_t const distance_symbol = distance_decoder.decode(reader, stream_format);
                    if (distance_symbol >= distance_bases.size())
                    {
                        throw compression_error(error_code::invalid_data, stream_format, "invalid DEFLATE distance symbol");
                    }
                    std::size_t const distance = distance_bases[distance_symbol] + reader.read_bits(distance_extras[distance_symbol]);
                    if (distance == 0U || distance > member_size || distance > history.size())
                    {
                        throw compression_error(error_code::invalid_data, stream_format, "DEFLATE match distance exceeds available history");
                    }
                    for (std::size_t index = 0U; index < length; ++index)
                    {
                        emit(history[(member_size - distance) % history.size()]);
                    }
                }
            }
            reader.align_to_byte();
            if (stream_format == format::zlib && read_u32(false) != member_adler.value())
            {
                throw compression_error(error_code::invalid_data, stream_format, "zlib Adler-32 mismatch");
            }
            if (stream_format == format::gzip && (read_u32(true) != member_crc.value() || read_u32(true) != static_cast< std::uint32_t >(member_size)))
            {
                throw compression_error(error_code::invalid_data, stream_format, "gzip data checksum or size mismatch");
            }
            decoded_member = true;
        } while (!source.empty());
        return output;
    }
 
} // namespace rpnx::compression::deflate_codec
 
#endif