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