courgette/ensemble.h

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