src/lib/chunked-compression/chunked-archive.h - fuchsia - Git at Google

 // 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.
 //
 // This header describes *Version 2* of the format. All other versions are unsupported.
 //
 //       0     1     2     3     4     5     6     7
 //    +-----+-----+-----+-----+-----+-----+-----+-----+
 //  0 |                 Magic Number                  |
 //    +-----+-----+-----+-----+-----+-----+-----+-----+
 //  8 |  Version  |  Reserved |       Num Frames      |  // Reserved bytes must be zero.
 //    +-----+-----+-----+-----+-----+-----+-----+-----+
 // 16 |    Header CRC32       |        Reserved       |  // Reserved bytes must be zero.
 //    +-----+-----+-----+-----+-----+-----+-----+-----+
 // 24 |                    Reserved                   |  // Reserved bytes must be zero.
 //    +-----+-----+-----+-----+-----+-----+-----+-----+
 // 32 |                                               |
 // 40 |                   Seek Table                  |
 // 48 |                     Entry                     |
 // 56 |                                               |
 //    +-----+-----+-----+-----+-----+-----+-----+-----+
 // .. |                                               |
 // .. |                   Seek Table                  |
 // .. |                     Entry                     |
 // .. |                                               |
 //    +-----+-----+-----+-----+-----+-----+-----+-----+
 //
 // The Header CRC32 is computed based on the entire header including each 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.
 //
 // A seek table can hold at most 1023 entries (which results in a 32KiB header).
 //
 // ### 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 ArchiveVersionType = uint16_t;
 using ChunkCountType = uint32_t;

 // The magic number is an arbitrary unique value used to identify files as being of this format.  It
 // can be derived as follows:
 //
 //   sha256sum <<< "Fuchsia is a vivid purplish red color" | head -c16
 //
 constexpr size_t kArchiveMagicLength = sizeof(uint64_t);
 constexpr uint8_t kChunkArchiveMagic[kArchiveMagicLength] = {
     0x46, 0x9b, 0x78, 0xef, 0x0f, 0xd0, 0xb2, 0x03,
 };
 constexpr ArchiveVersionType kVersion = 2u;

 constexpr size_t kChunkArchiveMagicOffset = 0ul;
 constexpr size_t kChunkArchiveVersionOffset = 8ul;
 constexpr size_t kChunkArchiveReserved1Offset = 10ul;
 constexpr size_t kChunkArchiveNumChunksOffset = 12ul;
 constexpr size_t kChunkArchiveHeaderCrc32Offset = 16ul;
 constexpr size_t kChunkArchiveReserved2Offset = 20ul;
 constexpr size_t kChunkArchiveSeekTableOffset = 32ul;

 // 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");

 constexpr ChunkCountType kChunkArchiveMaxFrames = 1023;

 constexpr size_t kChunkArchiveMinHeaderSize = kChunkArchiveSeekTableOffset;
 constexpr size_t kChunkArchiveMaxHeaderSize =
     kChunkArchiveSeekTableOffset + (kChunkArchiveMaxFrames * sizeof(SeekTableEntry));

 // This assert just documents the relationship between the maximum number of frames and the actual
 // maximum header size (32KiB).
 static_assert(kChunkArchiveMaxHeaderSize == (32 * 1024), "");

 static_assert(kChunkArchiveMagicOffset == 0ul, "Breaking change to archive format");
 static_assert(kChunkArchiveVersionOffset == kChunkArchiveMagicOffset + kArchiveMagicLength,
               "Breaking change to archive format");
 static_assert(kChunkArchiveReserved1Offset ==
                   kChunkArchiveVersionOffset + sizeof(ArchiveVersionType),
               "Breaking change to archive format");
 static_assert(kChunkArchiveNumChunksOffset == kChunkArchiveReserved1Offset + sizeof(uint16_t),
               "Breaking change to archive format");
 static_assert(kChunkArchiveHeaderCrc32Offset ==
                   kChunkArchiveNumChunksOffset + sizeof(ChunkCountType),
               "Breaking change to archive format");
 static_assert(kChunkArchiveReserved2Offset == kChunkArchiveHeaderCrc32Offset + sizeof(uint32_t),
               "Breaking change to archive format");
 static_assert(kChunkArchiveSeekTableOffset ==
                   kChunkArchiveReserved2Offset + sizeof(uint32_t) + sizeof(uint64_t),
               "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 CheckChecksum(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);

   // Computes the CRC32 checksum for |header|.
   static uint32_t ComputeChecksum(const uint8_t* header, size_t header_length);
 };

 // HeaderWriter writes chunked archive headers to a target buffer.
 class HeaderWriter {
  public:
   HeaderWriter() = default;
   HeaderWriter(HeaderWriter&& o) = default;
   HeaderWriter& operator=(HeaderWriter&& o) = default;
   DISALLOW_COPY_AND_ASSIGN_ALLOW_MOVE(HeaderWriter);

   // Initializes |out| to write a header to |dst| (which is a buffer of |dst_len| bytes).
   // Exactly |num_frames| will be written.
   static Status Create(void* dst, size_t dst_len, size_t num_frames, HeaderWriter* out);

   // 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 header 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:
   HeaderWriter(void* dst, size_t dst_len, size_t num_frames);

   uint8_t* dst_ = nullptr;
   size_t dst_length_;
   SeekTableEntry* entries_ = nullptr;
   unsigned current_frame_ = 0;
   ChunkCountType num_frames_;
 };

 }  // namespace chunked_compression

 #endif  // SRC_LIB_CHUNKED_COMPRESSION_CHUNKED_ARCHIVE_H_
	// 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.
	//
	// This header describes Version 2 of the format. All other versions are unsupported.
	//
	// 0 1 2 3 4 5 6 7
	// +-----+-----+-----+-----+-----+-----+-----+-----+
	// 0 \| Magic Number \|
	// +-----+-----+-----+-----+-----+-----+-----+-----+
	// 8 \| Version \| Reserved \| Num Frames \| // Reserved bytes must be zero.
	// +-----+-----+-----+-----+-----+-----+-----+-----+
	// 16 \| Header CRC32 \| Reserved \| // Reserved bytes must be zero.
	// +-----+-----+-----+-----+-----+-----+-----+-----+
	// 24 \| Reserved \| // Reserved bytes must be zero.
	// +-----+-----+-----+-----+-----+-----+-----+-----+
	// 32 \| \|
	// 40 \| Seek Table \|
	// 48 \| Entry \|
	// 56 \| \|
	// +-----+-----+-----+-----+-----+-----+-----+-----+
	// .. \| \|
	// .. \| Seek Table \|
	// .. \| Entry \|
	// .. \| \|
	// +-----+-----+-----+-----+-----+-----+-----+-----+
	//
	// The Header CRC32 is computed based on the entire header including each 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.
	//
	// A seek table can hold at most 1023 entries (which results in a 32KiB header).
	//
	// ### 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 ArchiveVersionType = uint16_t;
	using ChunkCountType = uint32_t;

	// The magic number is an arbitrary unique value used to identify files as being of this format. It
	// can be derived as follows:
	//
	// sha256sum <<< "Fuchsia is a vivid purplish red color" \| head -c16
	//
	constexpr size_t kArchiveMagicLength = sizeof(uint64_t);
	constexpr uint8_t kChunkArchiveMagic[kArchiveMagicLength] = {
	0x46, 0x9b, 0x78, 0xef, 0x0f, 0xd0, 0xb2, 0x03,
	};
	constexpr ArchiveVersionType kVersion = 2u;

	constexpr size_t kChunkArchiveMagicOffset = 0ul;
	constexpr size_t kChunkArchiveVersionOffset = 8ul;
	constexpr size_t kChunkArchiveReserved1Offset = 10ul;
	constexpr size_t kChunkArchiveNumChunksOffset = 12ul;
	constexpr size_t kChunkArchiveHeaderCrc32Offset = 16ul;
	constexpr size_t kChunkArchiveReserved2Offset = 20ul;
	constexpr size_t kChunkArchiveSeekTableOffset = 32ul;

	// 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");

	constexpr ChunkCountType kChunkArchiveMaxFrames = 1023;

	constexpr size_t kChunkArchiveMinHeaderSize = kChunkArchiveSeekTableOffset;
	constexpr size_t kChunkArchiveMaxHeaderSize =
	kChunkArchiveSeekTableOffset + (kChunkArchiveMaxFrames * sizeof(SeekTableEntry));

	// This assert just documents the relationship between the maximum number of frames and the actual
	// maximum header size (32KiB).
	static_assert(kChunkArchiveMaxHeaderSize == (32 * 1024), "");

	static_assert(kChunkArchiveMagicOffset == 0ul, "Breaking change to archive format");
	static_assert(kChunkArchiveVersionOffset == kChunkArchiveMagicOffset + kArchiveMagicLength,
	"Breaking change to archive format");
	static_assert(kChunkArchiveReserved1Offset ==
	kChunkArchiveVersionOffset + sizeof(ArchiveVersionType),
	"Breaking change to archive format");
	static_assert(kChunkArchiveNumChunksOffset == kChunkArchiveReserved1Offset + sizeof(uint16_t),
	"Breaking change to archive format");
	static_assert(kChunkArchiveHeaderCrc32Offset ==
	kChunkArchiveNumChunksOffset + sizeof(ChunkCountType),
	"Breaking change to archive format");
	static_assert(kChunkArchiveReserved2Offset == kChunkArchiveHeaderCrc32Offset + sizeof(uint32_t),
	"Breaking change to archive format");
	static_assert(kChunkArchiveSeekTableOffset ==
	kChunkArchiveReserved2Offset + sizeof(uint32_t) + sizeof(uint64_t),
	"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 CheckChecksum(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);

	// Computes the CRC32 checksum for \|header\|.
	static uint32_t ComputeChecksum(const uint8_t* header, size_t header_length);
	};

	// HeaderWriter writes chunked archive headers to a target buffer.
	class HeaderWriter {
	public:
	HeaderWriter() = default;
	HeaderWriter(HeaderWriter&& o) = default;
	HeaderWriter& operator=(HeaderWriter&& o) = default;
	DISALLOW_COPY_AND_ASSIGN_ALLOW_MOVE(HeaderWriter);

	// Initializes \|out\| to write a header to \|dst\| (which is a buffer of \|dst_len\| bytes).
	// Exactly \|num_frames\| will be written.
	static Status Create(void* dst, size_t dst_len, size_t num_frames, HeaderWriter* out);

	// 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 header 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:
	HeaderWriter(void* dst, size_t dst_len, size_t num_frames);

	uint8_t* dst_ = nullptr;
	size_t dst_length_;
	SeekTableEntry* entries_ = nullptr;
	unsigned current_frame_ = 0;
	ChunkCountType num_frames_;
	};

	} // namespace chunked_compression

	#endif // SRC_LIB_CHUNKED_COMPRESSION_CHUNKED_ARCHIVE_H_