| // Copyright 2020 The Fuchsia Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #ifndef SRC_LIB_CHUNKED_COMPRESSION_CHUNKED_ARCHIVE_H_ |
| #define SRC_LIB_CHUNKED_COMPRESSION_CHUNKED_ARCHIVE_H_ |
| |
| #include <optional> |
| |
| #include <fbl/algorithm.h> |
| #include <fbl/array.h> |
| #include <fbl/macros.h> |
| |
| #include "status.h" |
| |
| // Format specification for chunked archives. |
| // |
| // A chunked archive has a Header followed by zero or more Frames. |
| // |
| // ## Header |
| // |
| // The header describes the format of the archive and contains the Seek Table which maps the |
| // compressed frames to decompressed space. |
| // |
| // 0 1 2 3 4 5 6 7 |
| // +-----+-----+-----+-----+-----+-----+-----+-----+ |
| // 0 | Magic Number | |
| // +-----+-----+-----+-----+-----+-----+-----+-----+ |
| // 8 | Version | Reserved | Num Frames | // Reserved bytes must be zero. |
| // +-----+-----+-----+-----+-----+-----+-----+-----+ |
| // 16 | | |
| // 24 | Seek Table | |
| // 32 | Entry | |
| // 48 | | |
| // +-----+-----+-----+-----+-----+-----+-----+-----+ |
| // .. | | |
| // .. | Seek Table | |
| // .. | Entry | |
| // .. | | |
| // +-----+-----+-----+-----+-----+-----+-----+-----+ |
| // |
| // ### Seek Table |
| // |
| // Each Seek Table Entry describes a contiguous range of data in the compressed space, and where |
| // in the decompressed data it expands to. |
| // |
| // +-----+-----+-----+-----+-----+-----+-----+-----+ |
| // 0 | Decompressed Offset | |
| // +-----+-----+-----+-----+-----+-----+-----+-----+ |
| // 8 | Decompressed Size | |
| // +-----+-----+-----+-----+-----+-----+-----+-----+ |
| // 16 | Compressed Offset | |
| // +-----+-----+-----+-----+-----+-----+-----+-----+ |
| // 24 | Compressed Size | |
| // +-----+-----+-----+-----+-----+-----+-----+-----+ |
| // |
| // Seek table entries are *contiguous* in decompressed space, but may be *discontiguous* in |
| // compressed space. This is to support adding alignment/padding to output files to improve storage |
| // access efficiency. |
| // |
| // ### Seek Table Invariants |
| // |
| // I0: The first seek table entry must have decompressed offset 0. |
| // I1: The first seek table entry must have compressed offset greater than or equal to the size of |
| // the header. |
| // I2: Each entry's decompressed offset must be equal to the end of the previous frame (i.e. to |
| // the previous frame's decompressed offset+length). |
| // I3: Each entry's compressed offset must be greater than or equal to the end of the previous |
| // frame (i.e. to the previous frame's compressed offset+length). |
| // I4: Each entry must have a non-zero decompressed and compressed length. |
| // I5: No compressed frame may exceed the end of the file. |
| // |
| // ## Compressed Frames |
| // |
| // The compressed frames are contiguous ranges of bytes stored in the file at the offsets described |
| // by their seek table entry. |
| // |
| // Any ranges of bytes in the file not covered by the seek table are ignored. |
| |
| namespace chunked_compression { |
| |
| using ArchiveMagicType = uint64_t; |
| using ArchiveVersionType = uint16_t; |
| using ChunkCountType = uint32_t; |
| |
| constexpr ArchiveMagicType kChunkedCompressionArchiveMagic = 0x60427041'62407140; |
| constexpr ArchiveVersionType kVersion = 1u; |
| |
| constexpr ChunkCountType kChunkArchiveMaxFrames = UINT32_MAX; |
| |
| constexpr size_t kChunkArchiveMagicOffset = 0ul; |
| constexpr size_t kChunkArchiveVersionOffset = 8ul; |
| constexpr size_t kChunkArchiveReservedOffset = 10ul; |
| constexpr size_t kChunkArchiveNumChunksOffset = 12ul; |
| constexpr size_t kChunkArchiveSeekTableOffset = 16ul; |
| |
| constexpr size_t kChunkArchiveMinHeaderSize = kChunkArchiveSeekTableOffset; |
| |
| static_assert(kChunkArchiveMagicOffset == 0ul, "Breaking change to archive format"); |
| static_assert(kChunkArchiveVersionOffset == kChunkArchiveMagicOffset + sizeof(ArchiveMagicType), |
| "Breaking change to archive format"); |
| static_assert(kChunkArchiveReservedOffset == |
| kChunkArchiveVersionOffset + sizeof(ArchiveVersionType), |
| "Breaking change to archive format"); |
| static_assert(kChunkArchiveNumChunksOffset == kChunkArchiveReservedOffset + sizeof(uint16_t), |
| "Breaking change to archive format"); |
| static_assert(kChunkArchiveSeekTableOffset == kChunkArchiveNumChunksOffset + sizeof(ChunkCountType), |
| "Breaking change to archive format"); |
| |
| // A single entry into the seek table. Describes where an extent of decompressed |
| // data lives in the compressed space. |
| struct SeekTableEntry { |
| uint64_t decompressed_offset; |
| uint64_t decompressed_size; |
| uint64_t compressed_offset; |
| uint64_t compressed_size; |
| }; |
| static_assert(sizeof(SeekTableEntry) == 32ul, "Breaking change to archive format"); |
| |
| // A parsed view of a chunked archive's seek table. |
| // Constructed by parsing a buffer containing a raw archive (see |HeaderReader::Parse()|). |
| class SeekTable { |
| public: |
| SeekTable() = default; |
| SeekTable(SeekTable&& o) = default; |
| SeekTable& operator=(SeekTable&& o) = default; |
| ~SeekTable() = default; |
| DISALLOW_COPY_AND_ASSIGN_ALLOW_MOVE(SeekTable); |
| |
| // Returns a reference to the seek table of the archive. |
| const fbl::Array<SeekTableEntry>& Entries() const { return entries_; } |
| |
| // Returns the size of the compressed archive. |
| // Equal to the end of the greatest frame (i.e. its offset + size). |
| size_t CompressedSize() const; |
| |
| // Returns the size of the serialized header (i.e. everything but the actual compressed frames). |
| size_t SerializedHeaderSize() const; |
| |
| // Returns the expected size of the archive after decompression. |
| // Equal to the end of the greatest frame (i.e. its offset + size). |
| size_t DecompressedSize() const; |
| |
| // Lookup functions to find the entry in the seek table which covers |offset| in either the |
| // compressed or decompressed space. |
| // Returns the index into |SeekTable()| where the entry is stored, or std::nullopt if the |
| // offset is not covered. (Note that there can be gaps in the *compressed* frames, but the |
| // decompressed frames are contiguous). |
| std::optional<unsigned> EntryForCompressedOffset(size_t offset) const; |
| std::optional<unsigned> EntryForDecompressedOffset(size_t offset) const; |
| |
| // Allow HeaderReader to initialize these objects with a validated parsed seek table |
| friend class HeaderReader; |
| |
| private: |
| fbl::Array<SeekTableEntry> entries_; |
| }; |
| |
| // HeaderReader reads chunked archive headers and produces in-memory SeekTable representations. |
| class HeaderReader { |
| public: |
| HeaderReader() = default; |
| DISALLOW_COPY_ASSIGN_AND_MOVE(HeaderReader); |
| |
| // Validates that |data| is a valid chunked archive header and fills |out| with a copy of its |
| // seek table. |
| // |len| must be at least long enough to include the entire header; any actual compressed frames |
| // contained in |data| will not be accessed. |
| // |file_length| is the known length of the overall file. This is used for sanity checking the |
| // entries in the seek table. If any compressed frames exceed this length, the header is assumed |
| // to be corrupted. |
| Status Parse(const void* data, size_t len, size_t file_length, SeekTable* out); |
| |
| // Share validation routines with HeaderWriter |
| friend class HeaderWriter; |
| |
| private: |
| static Status CheckMagic(const uint8_t* data, size_t len); |
| static Status CheckVersion(const uint8_t* data, size_t len); |
| static Status GetNumChunks(const uint8_t* data, size_t len, ChunkCountType* num_chunks_out); |
| static Status ParseSeekTable(const uint8_t* data, size_t len, size_t file_length, |
| fbl::Array<SeekTableEntry>* entries_out); |
| static Status CheckSeekTable(const fbl::Array<SeekTableEntry>& seek_table, size_t header_end, |
| size_t file_length); |
| // NOTE: |prev| is optional, and is nullptr if |entry| is the first entry. |
| // (Ideally this would be a std::optional<const T&>, but optional references are not legal.) |
| static Status CheckSeekTableEntry(const SeekTableEntry& entry, const SeekTableEntry* prev, |
| size_t header_end, size_t file_length); |
| }; |
| |
| // HeaderWriter writes chunked archive headers to a target buffer. |
| class HeaderWriter { |
| public: |
| HeaderWriter(void* dst, size_t dst_len, size_t num_frames); |
| HeaderWriter() = delete; |
| ~HeaderWriter() = default; |
| DISALLOW_COPY_ASSIGN_AND_MOVE(HeaderWriter); |
| |
| // Computes the number of frames which will be used to compress a |size|-byte input. |
| static size_t NumFramesForDataSize(size_t size, size_t chunk_size) { |
| return fbl::round_up(size, chunk_size) / chunk_size; |
| } |
| |
| // Computes the size of the metadata header necessary for an archive with |num_frames|. |
| static size_t MetadataSizeForNumFrames(size_t num_frames) { |
| return kChunkArchiveSeekTableOffset + (num_frames * sizeof(SeekTableEntry)); |
| } |
| |
| // Adds a copy of |entry| to the seek table. |
| // Returns an error if |entry| is invalid, overlaps an existing entry, or if the table is already |
| // full. |
| Status AddEntry(const SeekTableEntry& entry); |
| |
| // Finishes writing the header out to the target buffer. |
| // |
| // Returns an error if the header was not fully initialized (i.e. not every seek table entry |
| // was filled). |
| // |
| // The target buffer is in an undefined state before Finalize() is called, and should not be |
| // serialized until Finalize() returns successfully. |
| // |
| // The HeaderWriter is in an undefined state after Finalize() returns, regardless of |
| // whether Finalize() succeeded or not. |
| Status Finalize(); |
| |
| private: |
| uint8_t* const dst_; |
| SeekTableEntry* entries_; |
| unsigned current_frame_ = 0; |
| ChunkCountType num_frames_; |
| }; |
| |
| } // namespace chunked_compression |
| |
| #endif // SRC_LIB_CHUNKED_COMPRESSION_CHUNKED_ARCHIVE_H_ |