lz4.hpp

Go to the documentation of this file.

#ifndef RPNX_COMPRESSION_IMPLEMENTATION_LZ4_HPP
#define RPNX_COMPRESSION_IMPLEMENTATION_LZ4_HPP
 
#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <limits>
#include <optional>
#include <span>
#include <type_traits>
#include <vector>
 
#include <rpnx/compression/implementation/io.hpp>
 
/**
 * @file
 * @brief Native LZ4 block and frame coding implementation.
 */
 
/** @brief Internal implementation of LZ4 frame compression and decompression. */
namespace rpnx::compression::lz4_codec
{
 
    /**
     * @brief Rotates a 32-bit value left without compiler-specific intrinsics.
     * @param value Value to rotate.
     * @param count Rotation distance in the range 1--31.
     * @return Rotated value.
     */
    [[nodiscard]] inline std::uint32_t rotate_left(std::uint32_t value, std::uint8_t count) noexcept
    {
        return (value << count) | (value >> (32U - count));
    }
 
    /**
     * @brief Reads an unchecked little-endian word from a known-valid range.
     * @param input Byte range containing at least four bytes at @p offset.
     * @param offset Position of the first byte.
     * @return Decoded 32-bit word.
     */
    [[nodiscard]] inline std::uint32_t read_word(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 Computes XXH32 as required by the LZ4 frame format.
     * @param input Bytes to hash.
     * @param seed XXH32 seed.
     * @return Finalized 32-bit hash.
     */
    [[nodiscard]] inline std::uint32_t xxhash32(std::span< std::byte const > input, std::uint32_t seed = 0U) noexcept
    {
        constexpr std::uint32_t prime1 = 0x9e3779b1U;
        constexpr std::uint32_t prime2 = 0x85ebca77U;
        constexpr std::uint32_t prime3 = 0xc2b2ae3dU;
        constexpr std::uint32_t prime4 = 0x27d4eb2fU;
        constexpr std::uint32_t prime5 = 0x165667b1U;
        std::size_t position = 0U;
        std::uint32_t hash = 0U;
        if (input.size() >= 16U)
        {
            std::uint32_t lane1 = seed + prime1 + prime2;
            std::uint32_t lane2 = seed + prime2;
            std::uint32_t lane3 = seed;
            std::uint32_t lane4 = seed - prime1;
            while (position + 16U <= input.size())
            {
                lane1 = rotate_left(lane1 + read_word(input, position) * prime2, 13U) * prime1;
                lane2 = rotate_left(lane2 + read_word(input, position + 4U) * prime2, 13U) * prime1;
                lane3 = rotate_left(lane3 + read_word(input, position + 8U) * prime2, 13U) * prime1;
                lane4 = rotate_left(lane4 + read_word(input, position + 12U) * prime2, 13U) * prime1;
                position += 16U;
            }
            hash = rotate_left(lane1, 1U) + rotate_left(lane2, 7U) + rotate_left(lane3, 12U) + rotate_left(lane4, 18U);
        }
        else
        {
            hash = seed + prime5;
        }
        hash += static_cast< std::uint32_t >(input.size());
        while (position + 4U <= input.size())
        {
            hash = rotate_left(hash + read_word(input, position) * prime3, 17U) * prime4;
            position += 4U;
        }
        while (position < input.size())
        {
            hash = rotate_left(hash + std::to_integer< std::uint8_t >(input[position]) * prime5, 11U) * prime1;
            ++position;
        }
        hash ^= hash >> 15U;
        hash *= prime2;
        hash ^= hash >> 13U;
        hash *= prime3;
        hash ^= hash >> 16U;
        return hash;
    }
 
    /** Incremental XXH32 accumulator for streamed LZ4 content checksums. */
    class xxhash32_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_word(m_buffer, 0U));
                m_lane2 = round(m_lane2, read_word(m_buffer, 4U));
                m_lane3 = round(m_lane3, read_word(m_buffer, 8U));
                m_lane4 = round(m_lane4, read_word(m_buffer, 12U));
                m_buffer_size = 0U;
            }
        }
 
        /**
         * @brief Returns the hash for all supplied bytes.
         * @return Finalized XXH32 value without changing accumulator state.
         */
        [[nodiscard]] std::uint32_t value() const noexcept
        {
            constexpr std::uint32_t prime1 = 0x9e3779b1U;
            constexpr std::uint32_t prime2 = 0x85ebca77U;
            constexpr std::uint32_t prime3 = 0xc2b2ae3dU;
            constexpr std::uint32_t prime4 = 0x27d4eb2fU;
            constexpr std::uint32_t prime5 = 0x165667b1U;
            std::uint32_t hash = m_total_size >= 16U ? rotate_left(m_lane1, 1U) + rotate_left(m_lane2, 7U) + rotate_left(m_lane3, 12U) + rotate_left(m_lane4, 18U) : prime5;
            hash += static_cast< std::uint32_t >(m_total_size);
            std::size_t position = 0U;
            std::span< std::byte const > const remaining(m_buffer.data(), m_buffer_size);
            while (position + 4U <= remaining.size())
            {
                hash = rotate_left(hash + read_word(remaining, position) * prime3, 17U) * prime4;
                position += 4U;
            }
            while (position < remaining.size())
            {
                hash = rotate_left(hash + std::to_integer< std::uint8_t >(remaining[position]) * prime5, 11U) * prime1;
                ++position;
            }
            hash ^= hash >> 15U;
            hash *= prime2;
            hash ^= hash >> 13U;
            hash *= prime3;
            hash ^= hash >> 16U;
            return hash;
        }
 
      private:
        /**
         * @brief Applies one XXH32 lane round.
         * @param lane Current lane accumulator.
         * @param value Next little-endian input word.
         * @return Updated lane accumulator.
         */
        [[nodiscard]] static std::uint32_t round(std::uint32_t lane, std::uint32_t value) noexcept
        {
            constexpr std::uint32_t prime1 = 0x9e3779b1U;
            constexpr std::uint32_t prime2 = 0x85ebca77U;
            return rotate_left(lane + value * prime2, 13U) * prime1;
        }
 
        std::array< std::byte, 16U > m_buffer{};
        std::size_t m_buffer_size = 0U;
        std::size_t m_total_size = 0U;
        std::uint32_t m_lane1 = 0x9e3779b1U + 0x85ebca77U;
        std::uint32_t m_lane2 = 0x85ebca77U;
        std::uint32_t m_lane3 = 0U;
        std::uint32_t m_lane4 = 0U - 0x9e3779b1U;
    };
 
    /**
     * @brief Encodes an extended LZ4 literal or match length.
     * @param output Block buffer receiving extension bytes.
     * @param length Amount beyond the token's base length.
     */
    inline void append_extended_length(std::vector< std::byte >& output, std::size_t length)
    {
        while (length >= 255U)
        {
            output.push_back(std::byte{0xff});
            length -= 255U;
        }
        output.push_back(static_cast< std::byte >(length));
    }
 
    /**
     * @brief Compresses one independent LZ4 block.
     * @param input Uncompressed block containing at most 64 KiB.
     * @param level Search level from 0 through 12.
     * @return Encoded block without an LZ4 frame header.
     */
    [[nodiscard]] inline std::vector< std::byte > compress_block(std::span< std::byte const > input, std::int32_t level)
    {
        constexpr std::size_t no_position = std::numeric_limits< std::size_t >::max();
        std::array< std::size_t, 65536U > heads{};
        heads.fill(no_position);
        std::vector< std::size_t > previous(input.size(), no_position);
        std::vector< std::byte > output;
        std::size_t anchor = 0U;
        std::size_t position = 0U;
        std::size_t const search_depth = level == 0 ? 1U : 4U + static_cast< std::size_t >(level) * 16U;
        auto hash_at = [&](std::size_t offset)
        {
            return static_cast< std::uint16_t >((read_word(input, offset) * 2654435761U) >> 16U);
        };
 
        while (position + 12U <= input.size())
        {
            std::uint16_t const hash = hash_at(position);
            std::size_t candidate = heads[hash];
            previous[position] = candidate;
            heads[hash] = position;
            std::size_t best_length = 0U;
            std::size_t best_distance = 0U;
            std::size_t depth = 0U;
            while (candidate != no_position && position - candidate <= 65535U && depth < search_depth)
            {
                if (read_word(input, candidate) == read_word(input, position))
                {
                    std::size_t length = 4U;
                    std::size_t const maximum_match_length = input.size() - position - 5U;
                    while (length < maximum_match_length && input[candidate + length] == input[position + length])
                    {
                        ++length;
                    }
                    if (length > best_length)
                    {
                        best_length = length;
                        best_distance = position - candidate;
                    }
                }
                candidate = previous[candidate];
                ++depth;
            }
            if (best_length < 4U)
            {
                ++position;
                continue;
            }
 
            std::size_t const literal_length = position - anchor;
            std::size_t const match_length = best_length - 4U;
            std::size_t const token_position = output.size();
            output.push_back(std::byte{0x00});
            std::uint8_t token = static_cast< std::uint8_t >(std::min< std::size_t >(literal_length, 15U) << 4U);
            token = static_cast< std::uint8_t >(token | std::min< std::size_t >(match_length, 15U));
            output[token_position] = static_cast< std::byte >(token);
            if (literal_length >= 15U)
            {
                append_extended_length(output, literal_length - 15U);
            }
            output.insert(output.end(), input.begin() + static_cast< std::ptrdiff_t >(anchor), input.begin() + static_cast< std::ptrdiff_t >(position));
            output.push_back(static_cast< std::byte >(best_distance & 0xffU));
            output.push_back(static_cast< std::byte >((best_distance >> 8U) & 0xffU));
            if (match_length >= 15U)
            {
                append_extended_length(output, match_length - 15U);
            }
 
            std::size_t const match_end = position + best_length;
            for (std::size_t inserted = position + 1U; inserted < match_end && inserted + 4U <= input.size(); ++inserted)
            {
                std::uint16_t const inserted_hash = hash_at(inserted);
                previous[inserted] = heads[inserted_hash];
                heads[inserted_hash] = inserted;
            }
            position = match_end;
            anchor = position;
        }
 
        std::size_t const literal_length = input.size() - anchor;
        output.push_back(static_cast< std::byte >(std::min< std::size_t >(literal_length, 15U) << 4U));
        if (literal_length >= 15U)
        {
            append_extended_length(output, literal_length - 15U);
        }
        output.insert(output.end(), input.begin() + static_cast< std::ptrdiff_t >(anchor), input.end());
        return output;
    }
 
    /**
     * @brief Reads an LZ4 extended length while checking block bounds.
     * @param input Encoded block.
     * @param position Current byte position, advanced past extension bytes.
     * @param initial Length nibble from the token.
     * @return Complete literal or match length.
     * @throws compression_error If the extension is truncated or overflows size_t.
     */
    [[nodiscard]] inline std::size_t read_extended_length(std::span< std::byte const > input, std::size_t& position, std::size_t initial)
    {
        std::size_t length = initial;
        if (initial != 15U)
        {
            return length;
        }
        while (true)
        {
            if (position == input.size())
            {
                throw compression_error(error_code::invalid_data, format::lz4_frame, "truncated LZ4 extended length");
            }
            std::uint8_t const extension = std::to_integer< std::uint8_t >(input[position++]);
            if (length > std::numeric_limits< std::size_t >::max() - extension)
            {
                throw compression_error(error_code::invalid_data, format::lz4_frame, "LZ4 length overflows the platform size");
            }
            length += extension;
            if (extension != 255U)
            {
                return length;
            }
        }
    }
 
    /**
     * @brief Compresses an iterator range as an LZ4 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 12.
     * @return Destination advanced past the frame end mark.
     */
    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(0);
        if (level < 0 || level > 12)
        {
            throw compression_error(error_code::invalid_option, format::lz4_frame, "LZ4 compression level must be between 0 and 12");
        }
        auto write_u32 = [&](std::uint32_t value)
        {
            for (std::uint8_t index = 0U; index < 4U; ++index)
            {
                implementation::write_byte(output, static_cast< std::byte >(value >> (index * 8U)));
            }
        };
        write_u32(0x184d2204U);
        std::array< std::byte, 2U > const descriptor{std::byte{0x60}, std::byte{0x40}};
        implementation::write_byte(output, descriptor[0U]);
        implementation::write_byte(output, descriptor[1U]);
        implementation::write_byte(output, static_cast< std::byte >((xxhash32(descriptor) >> 8U) & 0xffU));
 
        constexpr std::size_t block_limit = 64U * 1024U;
        std::vector< std::byte > block;
        block.reserve(block_limit);
        while (first != last)
        {
            block.clear();
            while (first != last && block.size() < block_limit)
            {
                block.push_back(implementation::to_byte(*first));
                ++first;
            }
            std::vector< std::byte > encoded = compress_block(block, level);
            if (encoded.size() < block.size())
            {
                write_u32(static_cast< std::uint32_t >(encoded.size()));
                for (std::byte value : encoded)
                {
                    implementation::write_byte(output, value);
                }
            }
            else
            {
                write_u32(static_cast< std::uint32_t >(block.size()) | 0x80000000U);
                for (std::byte value : block)
                {
                    implementation::write_byte(output, value);
                }
            }
        }
        write_u32(0U);
        return output;
    }
 
    /**
     * @brief Decompresses one or more LZ4 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::lz4_frame, "truncated LZ4 frame");
            }
            return value;
        };
        auto read_u32 = [&]() -> std::uint32_t
        {
            std::uint32_t value = 0U;
            for (std::uint8_t index = 0U; index < 4U; ++index)
            {
                value |= static_cast< std::uint32_t >(std::to_integer< std::uint8_t >(read_byte())) << (index * 8U);
            }
            return value;
        };
        std::array< std::byte, 65536U > history{};
        std::size_t total_output = 0U;
        bool decoded_frame = false;
        do
        {
            if (decoded_frame && !options.allow_concatenated_streams)
            {
                throw compression_error(error_code::trailing_data, format::lz4_frame, "LZ4 frame contains trailing data");
            }
            if (read_u32() != 0x184d2204U)
            {
                throw compression_error(error_code::invalid_data, format::lz4_frame, "invalid LZ4 frame magic");
            }
            std::array< std::byte, 10U > descriptor{};
            std::size_t descriptor_size = 0U;
            std::byte const flags_byte = read_byte();
            std::byte const block_descriptor_byte = read_byte();
            descriptor[descriptor_size++] = flags_byte;
            descriptor[descriptor_size++] = block_descriptor_byte;
            std::uint8_t const flags = std::to_integer< std::uint8_t >(flags_byte);
            std::uint8_t const block_descriptor = std::to_integer< std::uint8_t >(block_descriptor_byte);
            if ((flags & 0xc0U) != 0x40U || (flags & 0x02U) != 0U || (block_descriptor & 0x8fU) != 0U)
            {
                throw compression_error(error_code::invalid_data, format::lz4_frame, "invalid LZ4 frame flags");
            }
            std::uint8_t const block_size_code = static_cast< std::uint8_t >((block_descriptor >> 4U) & 0x07U);
            if (block_size_code < 4U || block_size_code > 7U)
            {
                throw compression_error(error_code::invalid_data, format::lz4_frame, "invalid LZ4 maximum block size");
            }
            constexpr std::array< std::size_t, 4U > maximum_block_sizes{64U * 1024U, 256U * 1024U, 1024U * 1024U, 4U * 1024U * 1024U};
            std::size_t const maximum_block_size = maximum_block_sizes[block_size_code - 4U];
            std::optional< std::uint64_t > content_size;
            if ((flags & 0x08U) != 0U)
            {
                std::uint64_t size = 0U;
                for (std::uint8_t index = 0U; index < 8U; ++index)
                {
                    std::byte const value = read_byte();
                    descriptor[descriptor_size++] = value;
                    size |= static_cast< std::uint64_t >(std::to_integer< std::uint8_t >(value)) << (index * 8U);
                }
                content_size = size;
            }
            if ((flags & 0x01U) != 0U)
            {
                throw compression_error(error_code::unsupported_feature, format::lz4_frame, "dictionary-based LZ4 frames are not supported");
            }
            if (std::to_integer< std::uint8_t >(read_byte()) != static_cast< std::uint8_t >((xxhash32(std::span< std::byte const >(descriptor).first(descriptor_size)) >> 8U) & 0xffU))
            {
                throw compression_error(error_code::invalid_data, format::lz4_frame, "LZ4 header checksum mismatch");
            }
 
            std::size_t const frame_begin = total_output;
            std::size_t history_begin = frame_begin;
            xxhash32_accumulator frame_checksum;
            auto emit = [&](std::byte value)
            {
                if (total_output == options.maximum_output_size)
                {
                    throw compression_error(error_code::output_limit_exceeded, format::lz4_frame, "decompressed LZ4 output exceeds its limit");
                }
                history[total_output % history.size()] = value;
                ++total_output;
                if ((flags & 0x04U) != 0U)
                {
                    frame_checksum.update(value);
                }
                implementation::write_byte(output, value);
            };
 
            while (true)
            {
                std::uint32_t const block_header = read_u32();
                if (block_header == 0U)
                {
                    break;
                }
                bool const uncompressed = (block_header & 0x80000000U) != 0U;
                std::size_t const block_size = block_header & 0x7fffffffU;
                if (block_size > maximum_block_size)
                {
                    throw compression_error(error_code::invalid_data, format::lz4_frame, "invalid LZ4 block size");
                }
                std::vector< std::byte > block;
                block.reserve(block_size);
                for (std::size_t index = 0U; index < block_size; ++index)
                {
                    block.push_back(read_byte());
                }
                if ((flags & 0x10U) != 0U && read_u32() != xxhash32(block))
                {
                    throw compression_error(error_code::invalid_data, format::lz4_frame, "LZ4 block checksum mismatch");
                }
                if ((flags & 0x20U) != 0U)
                {
                    history_begin = total_output;
                }
                if (uncompressed)
                {
                    for (std::byte value : block)
                    {
                        emit(value);
                    }
                    continue;
                }
 
                std::size_t position = 0U;
                while (position < block.size())
                {
                    std::uint8_t const token = std::to_integer< std::uint8_t >(block[position++]);
                    std::size_t const literal_length = read_extended_length(block, position, token >> 4U);
                    if (literal_length > block.size() - std::min(position, block.size()))
                    {
                        throw compression_error(error_code::invalid_data, format::lz4_frame, "invalid LZ4 literal length");
                    }
                    for (std::size_t index = 0U; index < literal_length; ++index)
                    {
                        emit(block[position++]);
                    }
                    if (position == block.size())
                    {
                        break;
                    }
                    if (block.size() - position < 2U)
                    {
                        throw compression_error(error_code::invalid_data, format::lz4_frame, "truncated LZ4 match offset");
                    }
                    std::size_t const distance = std::to_integer< std::uint8_t >(block[position]) | (static_cast< std::size_t >(std::to_integer< std::uint8_t >(block[position + 1U])) << 8U);
                    position += 2U;
                    std::size_t const match_length = read_extended_length(block, position, token & 0x0fU) + 4U;
                    if (distance == 0U || distance > total_output - history_begin || distance > history.size())
                    {
                        throw compression_error(error_code::invalid_data, format::lz4_frame, "invalid LZ4 match distance or length");
                    }
                    for (std::size_t index = 0U; index < match_length; ++index)
                    {
                        emit(history[(total_output - distance) % history.size()]);
                    }
                }
            }
            if ((flags & 0x04U) != 0U && read_u32() != frame_checksum.value())
            {
                throw compression_error(error_code::invalid_data, format::lz4_frame, "LZ4 content checksum mismatch");
            }
            if (content_size.has_value() && total_output - frame_begin != *content_size)
            {
                throw compression_error(error_code::invalid_data, format::lz4_frame, "LZ4 content size mismatch");
            }
            decoded_frame = true;
        } while (!reader.empty());
        return output;
    }
 
} // namespace rpnx::compression::lz4_codec
 
#endif