zip.hpp

Go to the documentation of this file.

#ifndef RPNX_COMPRESSION_ZIP_HPP
#define RPNX_COMPRESSION_ZIP_HPP
 
#include <rpnx/compression/compression.hpp>
#include <rpnx/compression/implementation/io.hpp>
 
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <iterator>
#include <limits>
#include <optional>
#include <set>
#include <span>
#include <string>
#include <string_view>
#include <type_traits>
#include <utility>
#include <vector>
 
/**
 * @file
 * @brief Deterministic ZIP32 archive creation and validated extraction APIs.
 */
 
namespace rpnx::compression
{
 
    /** @brief Compression methods supported for individual ZIP members. */
    enum class zip_compression : std::uint8_t
    {
        stored, ///< Store the member without compression.
        deflate ///< Encode the member as raw DEFLATE.
    };
 
    /**
     * @brief An owning ZIP archive member.
     *
     * Paths use forward slashes and must be relative. Archive creation and
     * extraction reject empty paths, absolute paths, drive-qualified paths,
     * backslashes, embedded nulls, and parent-directory components.
     */
    struct zip_entry
    {
        /** @brief Relative, forward-slash-separated archive path. */
        std::string path;
 
        /** @brief Uncompressed member contents. */
        std::vector< std::byte > data;
 
        /** @brief Method used when the entry is written to an archive. */
        zip_compression compression = zip_compression::deflate;
    };
 
    /** @brief Resource limits applied while parsing a ZIP archive. */
    struct zip_extraction_options
    {
        /** @brief Maximum number of members accepted from one archive. */
        std::size_t maximum_entry_count = 100000U;
 
        /** @brief Maximum uncompressed size accepted for any one member. */
        std::size_t maximum_entry_size = 1024U * 1024U * 1024U;
 
        /** @brief Maximum combined uncompressed size accepted for all members. */
        std::size_t maximum_total_size = std::size_t{4U} * 1024U * 1024U * 1024U;
    };
 
    /**
     * @brief Creates a deterministic ZIP32 archive from contiguous entries.
     * @param entries Members to write in archive order. The span is only borrowed
     * for this call.
     * @return The complete ZIP32 archive.
     * @throws compression_error If a path is unsafe or duplicated, compression
     * fails, or ZIP64 would be required.
     *
     * The writer emits UTF-8 path flags, fixed timestamps, data descriptors, and
     * no extra fields or archive comment. Identical entries therefore produce
     * identical bytes.
     */
    [[nodiscard]] std::vector< std::byte > create_zip(std::span< zip_entry const > entries);
 
    /**
     * @brief Extracts a contiguous ZIP32 archive into owning entries.
     * @param archive Complete ZIP archive. The span is only borrowed for this call.
     * @param options Member-count and uncompressed-size limits.
     * @return Owning entries in central-directory order. Extracted entries record
     * the method declared by the archive.
     * @throws compression_error If the archive is malformed, unsupported, unsafe,
     * duplicated, fails checksum validation, or exceeds a configured limit.
     */
    [[nodiscard]] std::vector< zip_entry > extract_zip(std::span< std::byte const > archive, zip_extraction_options const& options = {});
 
    /** @brief Internal ZIP32 parsing and output-iterator support. */
    namespace zip_detail
    {
 
        /** Directory metadata retained until the central directory is emitted. */
        struct directory_record
        {
            /** @brief Archive member path. */
            std::string path;
 
            /** @brief CRC-32 of the uncompressed member. */
            std::uint32_t checksum;
 
            /** @brief Encoded member size. */
            std::uint32_t compressed_size;
 
            /** @brief Decoded member size. */
            std::uint32_t uncompressed_size;
 
            /** @brief Byte offset of the corresponding local header. */
            std::uint32_t local_header_offset;
 
            /** @brief ZIP compression-method identifier. */
            std::uint16_t method;
 
            /** @brief General-purpose ZIP flags copied to the central directory. */
            std::uint16_t flags;
        };
 
        /**
         * @brief Tests whether a member path is confined to a relative extraction root.
         * @param path Path to validate using ZIP's forward-slash convention.
         * @return true if the non-empty path is relative and contains no parent,
         * drive, backslash, or embedded-null components.
         */
        [[nodiscard]] inline bool path_is_safe(std::string const& path)
        {
            if (path.empty() || path.front() == '/' || path.front() == '\\' || path.find('\0') != std::string::npos || path.find('\\') != std::string::npos)
            {
                return false;
            }
            std::size_t segment_begin = 0U;
            while (segment_begin <= path.size())
            {
                std::size_t const segment_end = path.find('/', segment_begin);
                std::size_t const length = (segment_end == std::string::npos ? path.size() : segment_end) - segment_begin;
                std::string_view const segment(path.data() + segment_begin, length);
                if (segment == ".." || (segment_begin == 0U && segment.find(':') != std::string_view::npos))
                {
                    return false;
                }
                if (segment_end == std::string::npos)
                {
                    break;
                }
                segment_begin = segment_end + 1U;
            }
            return true;
        }
 
        /** Output iterator that counts bytes while forwarding every assignment. */
        template < typename output_iterator >
        class counting_output_iterator
        {
          public:
            /** Assignment proxy returned by operator*. */
            class assignment_proxy
            {
              public:
                /**
                 * @brief Constructs a proxy for one counted iterator position.
                 * @param owner Counting iterator that receives assignments.
                 */
                explicit assignment_proxy(counting_output_iterator& owner) noexcept : m_owner(owner)
                {
                }
 
                /**
                 * @brief Forwards one std::byte assignment.
                 * @param value Byte to write.
                 * @return This proxy after the write has been counted.
                 */
                assignment_proxy& operator=(std::byte value)
                {
                    implementation::write_byte(m_owner.m_output, value);
                    ++m_owner.m_size;
                    return *this;
                }
 
                /**
                 * @brief Forwards one unsigned-byte assignment.
                 * @param value Byte to write.
                 * @return This proxy after the write has been counted.
                 */
                assignment_proxy& operator=(std::uint8_t value)
                {
                    return *this = static_cast< std::byte >(value);
                }
 
              private:
                counting_output_iterator& m_owner;
            };
 
            /** @brief Signed distance type required by the output-iterator interface. */
            using difference_type = std::ptrdiff_t;
 
            /** @brief Iterator category advertised to generic algorithms. */
            using iterator_category = std::output_iterator_tag;
 
            /**
             * @brief Constructs a counter around an output iterator.
             * @param output Destination iterator to own and forward to.
             */
            explicit counting_output_iterator(output_iterator output) : m_output(std::move(output))
            {
            }
 
            /**
             * @brief Returns an assignment proxy for the current position.
             * @return Proxy that forwards and counts one assignment.
             */
            [[nodiscard]] assignment_proxy operator*() noexcept
            {
                return assignment_proxy(*this);
            }
 
            /**
             * @brief Advances after assignment.
             * @return This iterator; the underlying iterator was already advanced by assignment.
             */
            counting_output_iterator& operator++() noexcept
            {
                return *this;
            }
 
            /**
             * @brief Applies output-iterator post-increment semantics.
             * @return A copy referring to the same already-advanced destination state.
             */
            counting_output_iterator operator++(int) noexcept
            {
                return *this;
            }
 
            /**
             * @brief Releases the forwarded output iterator.
             * @return The owned iterator at its current output position.
             */
            [[nodiscard]] output_iterator take_output()
            {
                return std::move(m_output);
            }
 
            /**
             * @brief Returns the number of forwarded byte assignments.
             * @return Encoded byte count since construction.
             */
            [[nodiscard]] std::size_t size() const noexcept
            {
                return m_size;
            }
 
          private:
            output_iterator m_output;
            std::size_t m_size = 0U;
        };
 
        /**
         * @brief Extracts an archive that has been materialized for random access.
         * @tparam output_iterator Output iterator accepting zip_entry values.
         * @param archive Complete archive image.
         * @param output Destination iterator, taken and returned by value.
         * @param options Member-count and uncompressed-size limits.
         * @return The destination iterator advanced past the final extracted member.
         * @throws compression_error If structure, paths, sizes, methods, or checksums
         * fail validation, or extraction exceeds a configured limit.
         */
        template < typename output_iterator >
        output_iterator extract_archive(std::span< std::byte const > archive, output_iterator output, zip_extraction_options const& options)
        {
            auto read_u16 = [&](std::size_t offset)
            {
                if (offset > archive.size() || archive.size() - offset < 2U)
                {
                    throw compression_error(error_code::invalid_data, format::zip, "truncated ZIP integer field");
                }
                return static_cast< std::uint16_t >(std::to_integer< std::uint8_t >(archive[offset]) | static_cast< std::uint16_t >(std::to_integer< std::uint8_t >(archive[offset + 1U]) << 8U));
            };
            auto read_u32 = [&](std::size_t offset)
            {
                if (offset > archive.size() || archive.size() - offset < 4U)
                {
                    throw compression_error(error_code::invalid_data, format::zip, "truncated ZIP integer field");
                }
                return static_cast< std::uint32_t >(std::to_integer< std::uint8_t >(archive[offset])) | (static_cast< std::uint32_t >(std::to_integer< std::uint8_t >(archive[offset + 1U])) << 8U) | (static_cast< std::uint32_t >(std::to_integer< std::uint8_t >(archive[offset + 2U])) << 16U) | (static_cast< std::uint32_t >(std::to_integer< std::uint8_t >(archive[offset + 3U])) << 24U);
            };
            if (archive.size() < 22U)
            {
                throw compression_error(error_code::invalid_data, format::zip, "ZIP archive is too short");
            }
            std::size_t const search_begin = archive.size() > 65557U ? archive.size() - 65557U : 0U;
            std::optional< std::size_t > eocd_offset;
            for (std::size_t offset = archive.size() - 22U;; --offset)
            {
                if (read_u32(offset) == 0x06054b50U)
                {
                    eocd_offset = offset;
                    break;
                }
                if (offset == search_begin)
                {
                    break;
                }
            }
            if (!eocd_offset.has_value())
            {
                throw compression_error(error_code::invalid_data, format::zip, "ZIP end-of-central-directory record is missing");
            }
            std::size_t const eocd = *eocd_offset;
            if (read_u16(eocd + 4U) != 0U || read_u16(eocd + 6U) != 0U || read_u16(eocd + 8U) != read_u16(eocd + 10U))
            {
                throw compression_error(error_code::unsupported_feature, format::zip, "multi-disk ZIP archives are not supported");
            }
            std::size_t const entry_count = read_u16(eocd + 10U);
            std::size_t const directory_size = read_u32(eocd + 12U);
            std::size_t const directory_offset = read_u32(eocd + 16U);
            std::size_t const comment_size = read_u16(eocd + 20U);
            if (eocd + 22U + comment_size != archive.size() || directory_offset > archive.size() || directory_size > archive.size() - directory_offset || directory_offset + directory_size != eocd)
            {
                throw compression_error(error_code::invalid_data, format::zip, "invalid ZIP central-directory bounds");
            }
            if (entry_count > options.maximum_entry_count)
            {
                throw compression_error(error_code::output_limit_exceeded, format::zip, "ZIP entry count exceeds configured limit");
            }
 
            std::set< std::string > paths;
            std::size_t cursor = directory_offset;
            std::size_t total_size = 0U;
            for (std::size_t entry_index = 0U; entry_index < entry_count; ++entry_index)
            {
                if (read_u32(cursor) != 0x02014b50U || cursor > archive.size() || archive.size() - cursor < 46U)
                {
                    throw compression_error(error_code::invalid_data, format::zip, "invalid ZIP central-directory entry");
                }
                std::uint16_t const flags = read_u16(cursor + 8U);
                std::uint16_t const method = read_u16(cursor + 10U);
                std::uint32_t const expected_checksum = read_u32(cursor + 16U);
                std::size_t const compressed_size = read_u32(cursor + 20U);
                std::size_t const uncompressed_size = read_u32(cursor + 24U);
                std::size_t const name_size = read_u16(cursor + 28U);
                std::size_t const extra_size = read_u16(cursor + 30U);
                std::size_t const entry_comment_size = read_u16(cursor + 32U);
                std::size_t const local_offset = read_u32(cursor + 42U);
                std::size_t const central_record_size = 46U + name_size + extra_size + entry_comment_size;
                if ((flags & 0x0001U) != 0U || (method != 0U && method != 8U))
                {
                    throw compression_error(error_code::unsupported_feature, format::zip, "encrypted or unknown ZIP method");
                }
                if (cursor > archive.size() || central_record_size > archive.size() - cursor)
                {
                    throw compression_error(error_code::invalid_data, format::zip, "truncated ZIP central-directory entry");
                }
                std::string path;
                path.reserve(name_size);
                for (std::size_t index = 0U; index < name_size; ++index)
                {
                    path.push_back(static_cast< char >(std::to_integer< std::uint8_t >(archive[cursor + 46U + index])));
                }
                if (!path_is_safe(path) || !paths.insert(path).second)
                {
                    throw compression_error(error_code::invalid_data, format::zip, "ZIP contains an unsafe or duplicate path");
                }
                if (uncompressed_size > options.maximum_entry_size || total_size > options.maximum_total_size || uncompressed_size > options.maximum_total_size - total_size)
                {
                    throw compression_error(error_code::output_limit_exceeded, format::zip, "ZIP output exceeds configured limit");
                }
                if (read_u32(local_offset) != 0x04034b50U || local_offset > archive.size() || archive.size() - local_offset < 30U)
                {
                    throw compression_error(error_code::invalid_data, format::zip, "invalid ZIP local header");
                }
                std::uint16_t const local_flags = read_u16(local_offset + 6U);
                std::size_t const local_name_size = read_u16(local_offset + 26U);
                std::size_t const local_extra_size = read_u16(local_offset + 28U);
                std::size_t const data_offset = local_offset + 30U + local_name_size + local_extra_size;
                bool const uses_descriptor = (flags & 0x0008U) != 0U;
                std::uint32_t const local_checksum = read_u32(local_offset + 14U);
                std::uint32_t const local_compressed_size = read_u32(local_offset + 18U);
                std::uint32_t const local_uncompressed_size = read_u32(local_offset + 22U);
                if (data_offset > directory_offset || compressed_size > directory_offset - data_offset || local_flags != flags || read_u16(local_offset + 8U) != method || local_name_size != name_size || (!uses_descriptor && (local_checksum != expected_checksum || local_compressed_size != compressed_size || local_uncompressed_size != uncompressed_size)) || (uses_descriptor && ((local_checksum != 0U && local_checksum != expected_checksum) || (local_compressed_size != 0U && local_compressed_size != compressed_size) || (local_uncompressed_size != 0U && local_uncompressed_size != uncompressed_size))))
                {
                    throw compression_error(error_code::invalid_data, format::zip, "ZIP local and central headers disagree");
                }
                for (std::size_t index = 0U; index < name_size; ++index)
                {
                    if (archive[local_offset + 30U + index] != archive[cursor + 46U + index])
                    {
                        throw compression_error(error_code::invalid_data, format::zip, "ZIP local and central paths disagree");
                    }
                }
                if (uses_descriptor)
                {
                    std::size_t descriptor = data_offset + compressed_size;
                    if (read_u32(descriptor) == 0x08074b50U)
                    {
                        descriptor += 4U;
                    }
                    if (read_u32(descriptor) != expected_checksum || read_u32(descriptor + 4U) != compressed_size || read_u32(descriptor + 8U) != uncompressed_size)
                    {
                        throw compression_error(error_code::invalid_data, format::zip, "invalid ZIP data descriptor");
                    }
                }
 
                std::span< std::byte const > const encoded = archive.subspan(data_offset, compressed_size);
                std::vector< std::byte > data;
                data.reserve(uncompressed_size);
                if (method == 0U)
                {
                    data.assign(encoded.begin(), encoded.end());
                }
                else
                {
                    decompression_options limits;
                    limits.maximum_output_size = uncompressed_size;
                    rpnx::compression::decompress(format::deflate, encoded.begin(), encoded.end(), std::back_inserter(data), limits);
                }
                if (data.size() != uncompressed_size || deflate_codec::crc32(data) != expected_checksum)
                {
                    throw compression_error(error_code::invalid_data, format::zip, "ZIP member size or checksum is invalid");
                }
                *output = zip_entry{std::move(path), std::move(data), method == 0U ? zip_compression::stored : zip_compression::deflate};
                ++output;
                total_size += uncompressed_size;
                cursor += central_record_size;
            }
            if (cursor != directory_offset + directory_size)
            {
                throw compression_error(error_code::invalid_data, format::zip, "ZIP central-directory size does not match its entries");
            }
            return output;
        }
 
    } // namespace zip_detail
 
    /**
     * @brief Creates a deterministic ZIP32 archive from an iterator range.
     * @tparam input_iterator Single-pass iterator whose value type is zip_entry.
     * @tparam sentinel Sentinel for @p first.
     * @tparam output_iterator Output iterator accepting std::byte or std::uint8_t assignments.
     * @param first Iterator to the first member.
     * @param last Sentinel past the final member.
     * @param output Destination iterator, taken and returned by value.
     * @return The destination iterator advanced past the end-of-central-directory record.
     * @throws compression_error If a member is invalid or ZIP64 would be required.
     *
     * Only central-directory metadata is retained; member data is consumed and
     * emitted in archive order.
     */
    template < std::input_iterator input_iterator, std::sentinel_for< input_iterator > sentinel, typename output_iterator >
    output_iterator create_zip(input_iterator first, sentinel last, output_iterator output)
    {
        std::set< std::string > paths;
        std::vector< zip_detail::directory_record > directory;
        std::uint64_t archive_size = 0U;
        auto write_byte = [&](std::byte value)
        {
            implementation::write_byte(output, value);
            ++archive_size;
            if (archive_size > std::numeric_limits< std::uint32_t >::max())
            {
                throw compression_error(error_code::unsupported_feature, format::zip, "ZIP64 archive creation is not supported");
            }
        };
        auto write_u16 = [&](std::uint16_t value)
        {
            write_byte(static_cast< std::byte >(value));
            write_byte(static_cast< std::byte >(value >> 8U));
        };
        auto write_u32 = [&](std::uint32_t value)
        {
            for (std::uint8_t index = 0U; index < 4U; ++index)
            {
                write_byte(static_cast< std::byte >(value >> (index * 8U)));
            }
        };
        for (; first != last; ++first)
        {
            zip_entry const& entry = *first;
            if (directory.size() == std::numeric_limits< std::uint16_t >::max())
            {
                throw compression_error(error_code::unsupported_feature, format::zip, "ZIP64 is required for more than 65535 entries");
            }
            if (!zip_detail::path_is_safe(entry.path) || !paths.insert(entry.path).second)
            {
                throw compression_error(error_code::invalid_option, format::zip, "ZIP entry path is unsafe or duplicated");
            }
            if (entry.path.size() > std::numeric_limits< std::uint16_t >::max() || entry.data.size() > std::numeric_limits< std::uint32_t >::max())
            {
                throw compression_error(error_code::unsupported_feature, format::zip, "ZIP64 archive creation is not supported");
            }
            std::uint16_t const method = entry.compression == zip_compression::stored ? 0U : 8U;
            constexpr std::uint16_t flags = 0x0808U;
            std::uint32_t const local_offset = static_cast< std::uint32_t >(archive_size);
            std::uint32_t const checksum = deflate_codec::crc32(entry.data);
            write_u32(0x04034b50U);
            write_u16(20U);
            write_u16(flags);
            write_u16(method);
            write_u16(0U);
            write_u16(0x0021U);
            write_u32(0U);
            write_u32(0U);
            write_u32(0U);
            write_u16(static_cast< std::uint16_t >(entry.path.size()));
            write_u16(0U);
            for (char character : entry.path)
            {
                write_byte(static_cast< std::byte >(static_cast< std::uint8_t >(character)));
            }
            zip_detail::counting_output_iterator< output_iterator > counted(std::move(output));
            if (method == 0U)
            {
                for (std::byte value : entry.data)
                {
                    *counted = value;
                    ++counted;
                }
            }
            else
            {
                counted = rpnx::compression::compress(format::deflate, entry.data.begin(), entry.data.end(), std::move(counted));
            }
            std::size_t const compressed_size_value = counted.size();
            output = counted.take_output();
            if (compressed_size_value > std::numeric_limits< std::uint32_t >::max())
            {
                throw compression_error(error_code::unsupported_feature, format::zip, "ZIP64 archive creation is not supported");
            }
            archive_size += compressed_size_value;
            write_u32(0x08074b50U);
            write_u32(checksum);
            write_u32(static_cast< std::uint32_t >(compressed_size_value));
            write_u32(static_cast< std::uint32_t >(entry.data.size()));
            directory.push_back(zip_detail::directory_record{entry.path, checksum, static_cast< std::uint32_t >(compressed_size_value), static_cast< std::uint32_t >(entry.data.size()), local_offset, method, flags});
        }
 
        std::uint32_t const directory_offset = static_cast< std::uint32_t >(archive_size);
        for (zip_detail::directory_record const& record : directory)
        {
            write_u32(0x02014b50U);
            write_u16(20U);
            write_u16(20U);
            write_u16(record.flags);
            write_u16(record.method);
            write_u16(0U);
            write_u16(0x0021U);
            write_u32(record.checksum);
            write_u32(record.compressed_size);
            write_u32(record.uncompressed_size);
            write_u16(static_cast< std::uint16_t >(record.path.size()));
            write_u16(0U);
            write_u16(0U);
            write_u16(0U);
            write_u16(0U);
            write_u32(0U);
            write_u32(record.local_header_offset);
            for (char character : record.path)
            {
                write_byte(static_cast< std::byte >(static_cast< std::uint8_t >(character)));
            }
        }
        std::uint64_t const directory_size = archive_size - directory_offset;
        if (directory_size > std::numeric_limits< std::uint32_t >::max())
        {
            throw compression_error(error_code::unsupported_feature, format::zip, "ZIP64 archive creation is not supported");
        }
        write_u32(0x06054b50U);
        write_u16(0U);
        write_u16(0U);
        write_u16(static_cast< std::uint16_t >(directory.size()));
        write_u16(static_cast< std::uint16_t >(directory.size()));
        write_u32(static_cast< std::uint32_t >(directory_size));
        write_u32(directory_offset);
        write_u16(0U);
        return output;
    }
 
    /**
     * @brief Extracts validated ZIP members through an STL output iterator.
     * @tparam input_iterator Single-pass iterator whose value type is std::byte or a one-byte integral type.
     * @tparam sentinel Sentinel for @p first.
     * @tparam output_iterator Output iterator accepting zip_entry values.
     * @param first Iterator to the first archive byte.
     * @param last Sentinel past the final archive byte.
     * @param output Destination iterator, taken and returned by value.
     * @param options Member-count and uncompressed-size limits.
     * @return The destination iterator advanced past the final extracted member.
     * @throws compression_error If the archive is malformed, unsupported, unsafe,
     * duplicated, fails checksum validation, or exceeds a configured limit.
     *
     * ZIP extraction materializes the archive because its trailing central
     * directory points backward to local headers.
     */
    template < std::input_iterator input_iterator, std::sentinel_for< input_iterator > sentinel, typename output_iterator >
    output_iterator extract_zip(input_iterator first, sentinel last, output_iterator output, zip_extraction_options const& options = {})
    {
        using input_value = std::remove_cv_t< std::iter_value_t< input_iterator > >;
        static_assert(std::is_same_v< input_value, std::byte > || (std::is_integral_v< input_value > && sizeof(input_value) == 1U), "ZIP input iterators must contain byte-sized values");
        // A single-pass ZIP reader must retain the archive because the central
        // directory follows member data and points backward to local headers.
        std::vector< std::byte > archive;
        for (; first != last; ++first)
        {
            archive.push_back(implementation::to_byte(*first));
        }
        return zip_detail::extract_archive(archive, std::move(output), options);
    }
 
} // namespace rpnx::compression
 
#endif