src/courgette/ensemble.h

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