patch_writer.h 9.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272
  1. // Copyright 2017 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #ifndef COMPONENTS_ZUCCHINI_PATCH_WRITER_H_
  5. #define COMPONENTS_ZUCCHINI_PATCH_WRITER_H_
  6. #include <stddef.h>
  7. #include <stdint.h>
  8. #include <map>
  9. #include <utility>
  10. #include <vector>
  11. #include "base/check.h"
  12. #include "components/zucchini/buffer_sink.h"
  13. #include "components/zucchini/buffer_view.h"
  14. #include "components/zucchini/image_utils.h"
  15. #include "components/zucchini/patch_utils.h"
  16. #include "third_party/abseil-cpp/absl/types/optional.h"
  17. namespace zucchini {
  18. namespace patch {
  19. // If sufficient space is available, serializes |element_match| into |sink| and
  20. // returns true. Otherwise returns false, and |sink| will be in an undefined
  21. // state.
  22. bool SerializeElementMatch(const ElementMatch& element_match, BufferSink* sink);
  23. // Returns the size in bytes required to serialize |element_match|.
  24. size_t SerializedElementMatchSize(const ElementMatch& element_match);
  25. // If sufficient space is available, serializes |buffer| into |sink| and returns
  26. // true. Otherwise returns false, and |sink| will be in an undefined state.
  27. bool SerializeBuffer(const std::vector<uint8_t>& buffer, BufferSink* sink);
  28. // Returns the size in bytes required to serialize |buffer|.
  29. size_t SerializedBufferSize(const std::vector<uint8_t>& buffer);
  30. } // namespace patch
  31. // Each of *Sink classes below has an associated "main type", and performs the
  32. // following:
  33. // - Receives multiple "main type" elements (hence "Sink" in the name).
  34. // - Encodes list of received data, and writes them to internal storage (e.g.,
  35. // applying delta encoding).
  36. // - Writes encoded data to BufferSink.
  37. //
  38. // Common "core functions" implemented for *Sink classes are:
  39. // - void PutNext(const MAIN_TYPE& inst): Encodes and writes an instance of
  40. // MAIN_TYPE to internal storage. Assumptions may be applied to successive
  41. // |inst| provided.
  42. // - size_t SerializedSize() const: Returns the serialized size in bytes of
  43. // internal storage.
  44. // - bool SerializeInto(BufferSink* sink) const: If |sink| has enough space,
  45. // serializes internal storage into |sink|, and returns true. Otherwise
  46. // returns false.
  47. //
  48. // Usage of *Sink instances don't mix, and PuttNext() have dissimilar
  49. // interfaces. Therefore we do not use inheritance to relate *Sink classes,
  50. // simply implement "core functions" with matching names.
  51. // Sink for equivalences.
  52. class EquivalenceSink {
  53. public:
  54. EquivalenceSink();
  55. EquivalenceSink(const std::vector<uint8_t>& src_skip,
  56. const std::vector<uint8_t>& dst_skip,
  57. const std::vector<uint8_t>& copy_count);
  58. EquivalenceSink(EquivalenceSink&&);
  59. ~EquivalenceSink();
  60. // Core functions.
  61. // Equivalences must be given by increasing |Equivalence::dst_offset|.
  62. void PutNext(const Equivalence& equivalence);
  63. size_t SerializedSize() const;
  64. bool SerializeInto(BufferSink* sink) const;
  65. private:
  66. // Offset in source, delta-encoded starting from end of last equivalence, and
  67. // stored as signed varint.
  68. std::vector<uint8_t> src_skip_;
  69. // Offset in destination, delta-encoded starting from end of last equivalence,
  70. // and stored as unsigned varint.
  71. std::vector<uint8_t> dst_skip_;
  72. // Length of equivalence stored as unsigned varint.
  73. // TODO(etiennep): Investigate on bias.
  74. std::vector<uint8_t> copy_count_;
  75. offset_t src_offset_ = 0; // Last offset in source.
  76. offset_t dst_offset_ = 0; // Last offset in destination.
  77. };
  78. // Sink for extra data.
  79. class ExtraDataSink {
  80. public:
  81. ExtraDataSink();
  82. explicit ExtraDataSink(const std::vector<uint8_t>& extra_data);
  83. ExtraDataSink(ExtraDataSink&&);
  84. ~ExtraDataSink();
  85. // Core functions.
  86. void PutNext(ConstBufferView region);
  87. size_t SerializedSize() const;
  88. bool SerializeInto(BufferSink* sink) const;
  89. private:
  90. std::vector<uint8_t> extra_data_;
  91. };
  92. // Sink for raw delta.
  93. class RawDeltaSink {
  94. public:
  95. RawDeltaSink();
  96. RawDeltaSink(const std::vector<uint8_t>& raw_delta_skip,
  97. const std::vector<uint8_t>& raw_delta_diff);
  98. RawDeltaSink(RawDeltaSink&&);
  99. ~RawDeltaSink();
  100. // Core functions.
  101. // Deltas must be given by increasing |RawDeltaUnit::copy_offset|.
  102. void PutNext(const RawDeltaUnit& delta);
  103. size_t SerializedSize() const;
  104. bool SerializeInto(BufferSink* sink) const;
  105. private:
  106. std::vector<uint8_t> raw_delta_skip_; // Copy offset stating from last delta.
  107. std::vector<uint8_t> raw_delta_diff_; // Bytewise difference.
  108. // We keep track of the compensation needed for next copy offset, taking into
  109. // accound delta encoding and bias of -1. Stored delta are biased by -1, so a
  110. // sequence of single byte deltas is represented as a string of 0's.
  111. offset_t copy_offset_compensation_ = 0;
  112. };
  113. // Sink for reference delta.
  114. class ReferenceDeltaSink {
  115. public:
  116. ReferenceDeltaSink();
  117. explicit ReferenceDeltaSink(const std::vector<uint8_t>& reference_delta);
  118. ReferenceDeltaSink(ReferenceDeltaSink&&);
  119. ~ReferenceDeltaSink();
  120. // Core functions.
  121. void PutNext(int32_t diff);
  122. size_t SerializedSize() const;
  123. bool SerializeInto(BufferSink* sink) const;
  124. private:
  125. std::vector<uint8_t> reference_delta_;
  126. };
  127. // Sink for additional targets.
  128. class TargetSink {
  129. public:
  130. TargetSink();
  131. explicit TargetSink(const std::vector<uint8_t>& extra_targets);
  132. TargetSink(TargetSink&&);
  133. ~TargetSink();
  134. // Core functions.
  135. // Targets must be given by increasing order.
  136. void PutNext(uint32_t target);
  137. size_t SerializedSize() const;
  138. bool SerializeInto(BufferSink* sink) const;
  139. private:
  140. // Targets are delta-encoded and biaised by 1, stored as unsigned varint.
  141. std::vector<uint8_t> extra_targets_;
  142. // We keep track of the compensation needed for next target, taking into
  143. // accound delta encoding and bias of -1.
  144. offset_t target_compensation_ = 0;
  145. };
  146. // Following are utility classes to write structured data forming a patch.
  147. // Utility to write a patch element. A patch element contains all the
  148. // information necessary to patch a single element. This class
  149. // provides an interface to individually set different building blocks of data
  150. // in the patch element.
  151. class PatchElementWriter {
  152. public:
  153. PatchElementWriter();
  154. explicit PatchElementWriter(ElementMatch element_match);
  155. PatchElementWriter(PatchElementWriter&&);
  156. ~PatchElementWriter();
  157. const ElementMatch& element_match() const { return element_match_; }
  158. const Element& old_element() const { return element_match_.old_element; }
  159. const Element& new_element() const { return element_match_.new_element; }
  160. // Following methods set individual blocks for this element. Previous
  161. // corresponding block is replaced. All streams must be set before call to
  162. // SerializedSize() of SerializeInto().
  163. void SetEquivalenceSink(EquivalenceSink&& equivalences) {
  164. equivalences_.emplace(std::move(equivalences));
  165. }
  166. void SetExtraDataSink(ExtraDataSink&& extra_data) {
  167. extra_data_.emplace(std::move(extra_data));
  168. }
  169. void SetRawDeltaSink(RawDeltaSink&& raw_delta) {
  170. raw_delta_.emplace(std::move(raw_delta));
  171. }
  172. void SetReferenceDeltaSink(ReferenceDeltaSink reference_delta) {
  173. reference_delta_.emplace(std::move(reference_delta));
  174. }
  175. // Set additional targets for pool identified with |pool_tag|.
  176. void SetTargetSink(PoolTag pool_tag, TargetSink&& extra_targets) {
  177. DCHECK(pool_tag != kNoPoolTag);
  178. extra_targets_.emplace(pool_tag, std::move(extra_targets));
  179. }
  180. // Returns the serialized size in bytes of the data this object is holding.
  181. size_t SerializedSize() const;
  182. // If sufficient space is available, serializes data into |sink|, which is at
  183. // least SerializedSize() bytes, and returns true. Otherwise returns false.
  184. bool SerializeInto(BufferSink* sink) const;
  185. private:
  186. ElementMatch element_match_;
  187. absl::optional<EquivalenceSink> equivalences_;
  188. absl::optional<ExtraDataSink> extra_data_;
  189. absl::optional<RawDeltaSink> raw_delta_;
  190. absl::optional<ReferenceDeltaSink> reference_delta_;
  191. std::map<PoolTag, TargetSink> extra_targets_;
  192. };
  193. // Utility to write a Zucchini ensemble patch. An ensemble patch is the
  194. // concatenation of a patch header with a vector of patch elements.
  195. class EnsemblePatchWriter {
  196. public:
  197. explicit EnsemblePatchWriter(const PatchHeader& header);
  198. EnsemblePatchWriter(ConstBufferView old_image, ConstBufferView new_image);
  199. EnsemblePatchWriter(const EnsemblePatchWriter&) = delete;
  200. const EnsemblePatchWriter& operator=(const EnsemblePatchWriter&) = delete;
  201. ~EnsemblePatchWriter();
  202. // Reserves space for |count| patch elements.
  203. void ReserveElements(size_t count) { elements_.reserve(count); }
  204. // Adds an patch element into the patch. Patch elements must be ordered by
  205. // their location in the new image file.
  206. void AddElement(PatchElementWriter&& patch_element);
  207. // Returns the serialized size in bytes of the data this object is holding.
  208. size_t SerializedSize() const;
  209. // If sufficient space is available, serializes data into |sink|, which is at
  210. // least SerializedSize() bytes, and returns true. Otherwise returns false.
  211. bool SerializeInto(BufferSink* sink) const;
  212. // If sufficient space is available, serializes data into |buffer|, which is
  213. // at least SerializedSize() bytes, and returns true. Otherwise returns false.
  214. bool SerializeInto(MutableBufferView buffer) const {
  215. BufferSink sink(buffer);
  216. return SerializeInto(&sink);
  217. }
  218. private:
  219. PatchHeader header_;
  220. std::vector<PatchElementWriter> elements_;
  221. offset_t current_dst_offset_ = 0;
  222. };
  223. } // namespace zucchini
  224. #endif // COMPONENTS_ZUCCHINI_PATCH_WRITER_H_