ensemble.h 8.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253
  1. // Copyright (c) 2011 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. // The main idea in Courgette is to do patching *under a tranformation*. The
  5. // input is transformed into a new representation, patching occurs in the new
  6. // repesentation, and then the tranform is reversed to get the patched data.
  7. //
  8. // The idea is applied to pieces (or 'Elements') of the whole (or 'Ensemble').
  9. // Each of the elements has to go through the same set of steps in lock-step,
  10. // but there may be many different kinds of elements, which have different
  11. // transformation.
  12. //
  13. // This file declares all the main types involved in creating and applying a
  14. // patch with this structure.
  15. #ifndef COURGETTE_ENSEMBLE_H_
  16. #define COURGETTE_ENSEMBLE_H_
  17. #include <stddef.h>
  18. #include <stdint.h>
  19. #include <string>
  20. #include <vector>
  21. #include "base/memory/raw_ptr.h"
  22. #include "courgette/courgette.h"
  23. #include "courgette/region.h"
  24. #include "courgette/streams.h"
  25. namespace courgette {
  26. // Forward declarations:
  27. class Ensemble;
  28. // An Element is a region of an Ensemble with an identifyable kind.
  29. //
  30. class Element {
  31. public:
  32. Element(ExecutableType kind,
  33. Ensemble* ensemble,
  34. const Region& region);
  35. Element(const Element&) = delete;
  36. Element& operator=(const Element&) = delete;
  37. virtual ~Element();
  38. ExecutableType kind() const { return kind_; }
  39. const Region& region() const { return region_; }
  40. // The name is used only for debugging and logging.
  41. virtual std::string Name() const;
  42. // Returns the byte position of this Element relative to the start of
  43. // containing Ensemble.
  44. size_t offset_in_ensemble() const;
  45. private:
  46. ExecutableType kind_;
  47. raw_ptr<Ensemble> ensemble_;
  48. Region region_;
  49. };
  50. class Ensemble {
  51. public:
  52. Ensemble(const Region& region, const char* name)
  53. : region_(region), name_(name) {}
  54. Ensemble(const Ensemble&) = delete;
  55. Ensemble& operator=(const Ensemble&) = delete;
  56. ~Ensemble();
  57. const Region& region() const { return region_; }
  58. const std::string& name() const { return name_; }
  59. // Scans the region to find Elements within the region().
  60. Status FindEmbeddedElements();
  61. // Returns the elements found by 'FindEmbeddedElements'.
  62. const std::vector<Element*>& elements() const { return elements_; }
  63. private:
  64. Region region_; // The memory, owned by caller, containing the
  65. // Ensemble's data.
  66. std::string name_; // A debugging/logging name for the Ensemble.
  67. std::vector<Element*> elements_; // Embedded elements discovered.
  68. std::vector<Element*> owned_elements_; // For deallocation.
  69. };
  70. inline size_t Element::offset_in_ensemble() const {
  71. return region().start() - ensemble_->region().start();
  72. }
  73. // The 'CourgettePatchFile' is class is a 'namespace' for the constants that
  74. // appear in a Courgette patch file.
  75. struct CourgettePatchFile {
  76. //
  77. // The Courgette patch format interleaves the data for N embedded Elements.
  78. //
  79. // Format of a patch file:
  80. // header:
  81. // magic
  82. // version
  83. // source-checksum
  84. // target-checksum
  85. // final-patch-input-size (an allocation hint)
  86. // multiple-streams:
  87. // stream 0:
  88. // number-of-transformed-elements (N) - varint32
  89. // transformation-1-method-id
  90. // transformation-2-method-id
  91. // ...
  92. // transformation-1-initial-parameters
  93. // transformation-2-initial-parameters
  94. // ...
  95. // stream 1:
  96. // correction:
  97. // transformation-1-parameters
  98. // transformation-2-parameters
  99. // ...
  100. // stream 2:
  101. // correction:
  102. // transformed-element-1
  103. // transformed-element-2
  104. // ...
  105. // stream 3:
  106. // correction:
  107. // base-file
  108. // element-1
  109. // element-2
  110. // ...
  111. static const uint32_t kMagic = 'C' | ('o' << 8) | ('u' << 16);
  112. static const uint32_t kVersion = 20110216;
  113. };
  114. // For any transform you would implement both a TransformationPatcher and a
  115. // TransformationPatchGenerator.
  116. //
  117. // TransformationPatcher is the interface which abstracts out the actual
  118. // transformation used on an Element. The patching itself happens outside the
  119. // actions of a TransformationPatcher. There are four steps.
  120. //
  121. // The first step is an Init step. The parameters to the Init step identify the
  122. // element, for example, range of locations within the original ensemble that
  123. // correspond to the element.
  124. //
  125. // PredictTransformParameters, explained below.
  126. //
  127. // The two final steps are 'Transform' - to transform the element into a new
  128. // representation, and to 'Reform' - to transform from the new representation
  129. // back to the original form.
  130. //
  131. // The Transform step takes some parameters. This allows the transform to be
  132. // customized to the particular element, or to receive some assistance in the
  133. // analysis required to perform the transform. The transform parameters might
  134. // be extensive but mostly predicable, so preceeding Transform is a
  135. // PredictTransformParameters step.
  136. //
  137. class TransformationPatcher {
  138. public:
  139. virtual ~TransformationPatcher() {}
  140. // First step: provides parameters for the patching. This would at a minimum
  141. // identify the element within the ensemble being patched.
  142. virtual Status Init(SourceStream* parameter_stream) = 0;
  143. // Second step: predicts transform parameters.
  144. virtual Status PredictTransformParameters(
  145. SinkStreamSet* predicted_parameters) = 0;
  146. // Third step: transforms element from original representation into alternate
  147. // representation.
  148. virtual Status Transform(SourceStreamSet* corrected_parameters,
  149. SinkStreamSet* transformed_element) = 0;
  150. // Final step: transforms element back from alternate representation into
  151. // original representation.
  152. virtual Status Reform(SourceStreamSet* transformed_element,
  153. SinkStream* reformed_element) = 0;
  154. };
  155. // TransformationPatchGenerator is the interface which abstracts out the actual
  156. // transformation used (and adjustment used) when differentially compressing one
  157. // Element from the |new_ensemble| against a corresponding element in the
  158. // |old_ensemble|.
  159. //
  160. // This is not a pure interface. There is a small amount of inheritance
  161. // implementation for the fields and actions common to all
  162. // TransformationPatchGenerators.
  163. //
  164. // When TransformationPatchGenerator is subclassed, there will be a
  165. // corresponding subclass of TransformationPatcher.
  166. //
  167. class TransformationPatchGenerator {
  168. public:
  169. TransformationPatchGenerator(Element* old_element,
  170. Element* new_element,
  171. TransformationPatcher* patcher);
  172. virtual ~TransformationPatchGenerator();
  173. // Returns the TransformationMethodId that identies this transformation.
  174. virtual ExecutableType Kind() = 0;
  175. // Writes the parameters that will be passed to TransformationPatcher::Init.
  176. virtual Status WriteInitialParameters(SinkStream* parameter_stream) = 0;
  177. // Predicts the transform parameters for the |old_element|. This must match
  178. // exactly the output that will be produced by the PredictTransformParameters
  179. // method of the corresponding subclass of TransformationPatcher. This method
  180. // is not pure. The default implementation delegates to the patcher to
  181. // guarantee matching output.
  182. virtual Status PredictTransformParameters(SinkStreamSet* prediction);
  183. // Writes the desired parameters for the transform of the old element from the
  184. // file representation to the alternate representation.
  185. virtual Status CorrectedTransformParameters(SinkStreamSet* parameters) = 0;
  186. // Writes both |old_element| and |new_element| in the new representation.
  187. // |old_corrected_parameters| will match the |corrected_parameters| passed to
  188. // the Transform method of the corresponding sublcass of
  189. // TransformationPatcher.
  190. //
  191. // The output written to |old_transformed_element| must match exactly the
  192. // output written by the Transform method of the corresponding subclass of
  193. // TransformationPatcher.
  194. virtual Status Transform(SourceStreamSet* old_corrected_parameters,
  195. SinkStreamSet* old_transformed_element,
  196. SinkStreamSet* new_transformed_element) = 0;
  197. // Transforms the new transformed_element back from the alternate
  198. // representation into the original file format. This must match exactly the
  199. // output that will be produced by the corresponding subclass of
  200. // TransformationPatcher::Reform. This method is not pure. The default
  201. // implementation delegates to the patcher.
  202. virtual Status Reform(SourceStreamSet* transformed_element,
  203. SinkStream* reformed_element);
  204. protected:
  205. raw_ptr<Element> old_element_;
  206. raw_ptr<Element> new_element_;
  207. raw_ptr<TransformationPatcher> patcher_;
  208. };
  209. } // namespace
  210. #endif // COURGETTE_ENSEMBLE_H_