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 29namespace courgette { 30 31// Forward declarations: 32class Ensemble; 33 34// An Element is a region of an Ensemble with an identifyable kind. 35// 36class 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 63class 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 90inline 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. 96struct 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// 161class 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// 196class 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_ 249