| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2009 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 | |
| 12 // This file contains the code to create the patch. | |
| 13 | |
| 14 | |
| 15 #include "third_party/courgette/ensemble.h" | |
| 16 | |
| 17 #include <vector> | |
| 18 #include <limits> | |
| 19 | |
| 20 #include "base/basictypes.h" | |
| 21 #include "base/logging.h" | |
| 22 #include "base/time.h" | |
| 23 | |
| 24 #include "third_party/courgette/bsdiff.h" | |
| 25 #include "third_party/courgette/crc.h" | |
| 26 #include "third_party/courgette/difference_estimator.h" | |
| 27 #include "third_party/courgette/image_info.h" | |
| 28 #include "third_party/courgette/streams.h" | |
| 29 #include "third_party/courgette/region.h" | |
| 30 #include "third_party/courgette/simple_delta.h" | |
| 31 | |
| 32 #include "third_party/courgette/win32_x86_patcher.h" | |
| 33 #include "third_party/courgette/win32_x86_generator.h" | |
| 34 | |
| 35 namespace courgette { | |
| 36 | |
| 37 TransformationPatchGenerator::TransformationPatchGenerator( | |
| 38 Element* old_element, | |
| 39 Element* new_element, | |
| 40 TransformationPatcher* patcher) | |
| 41 : old_element_(old_element), | |
| 42 new_element_(new_element), | |
| 43 patcher_(patcher) { | |
| 44 } | |
| 45 | |
| 46 TransformationPatchGenerator::~TransformationPatchGenerator() { | |
| 47 delete patcher_; | |
| 48 } | |
| 49 | |
| 50 // The default implementation of PredictTransformParameters delegates to the | |
| 51 // patcher. | |
| 52 Status TransformationPatchGenerator::PredictTransformParameters( | |
| 53 SinkStreamSet* prediction) { | |
| 54 return patcher_->PredictTransformParameters(prediction); | |
| 55 } | |
| 56 | |
| 57 // The default implementation of Reform delegates to the patcher. | |
| 58 Status TransformationPatchGenerator::Reform( | |
| 59 SourceStreamSet* transformed_element, | |
| 60 SinkStream* reformed_element) { | |
| 61 return patcher_->Reform(transformed_element, reformed_element); | |
| 62 } | |
| 63 | |
| 64 // Makes a TransformationPatchGenerator of the appropriate variety for the | |
| 65 // Element kind. | |
| 66 TransformationPatchGenerator* MakeGenerator(Element* old_element, | |
| 67 Element* new_element) { | |
| 68 if (new_element->kind() == Element::WIN32_X86_WITH_CODE) { | |
| 69 CourgetteWin32X86PatchGenerator* generator = | |
| 70 new CourgetteWin32X86PatchGenerator( | |
| 71 old_element, | |
| 72 new_element, | |
| 73 new CourgetteWin32X86Patcher(old_element->region())); | |
| 74 return generator; | |
| 75 } else { | |
| 76 LOG(WARNING) << "Unexpected Element::Kind " << old_element->kind(); | |
| 77 return NULL; | |
| 78 } | |
| 79 } | |
| 80 | |
| 81 // FindGenerators finds TransformationPatchGenerators for the elements of | |
| 82 // |new_ensemble|. For each element of |new_ensemble| we find the closest | |
| 83 // matching element from |old_ensemble| and use that as the basis for | |
| 84 // differential compression. The elements have to be the same kind so as to | |
| 85 // support transformation into the same kind of 'new representation'. | |
| 86 // | |
| 87 Status FindGenerators(Ensemble* old_ensemble, Ensemble* new_ensemble, | |
| 88 std::vector<TransformationPatchGenerator*>* generators) { | |
| 89 base::Time start_find_time = base::Time::Now(); | |
| 90 old_ensemble->FindEmbeddedElements(); | |
| 91 new_ensemble->FindEmbeddedElements(); | |
| 92 LOG(INFO) << "done FindEmbeddedElements " | |
| 93 << (base::Time::Now() - start_find_time).InSecondsF(); | |
| 94 | |
| 95 std::vector<Element*> old_elements(old_ensemble->elements()); | |
| 96 std::vector<Element*> new_elements(new_ensemble->elements()); | |
| 97 | |
| 98 LOG(INFO) << "old has " << old_elements.size() << " elements"; | |
| 99 LOG(INFO) << "new has " << new_elements.size() << " elements"; | |
| 100 | |
| 101 DifferenceEstimator difference_estimator; | |
| 102 std::vector<DifferenceEstimator::Base*> bases; | |
| 103 | |
| 104 base::Time start_bases_time = base::Time::Now(); | |
| 105 for (size_t i = 0; i < old_elements.size(); ++i) { | |
| 106 bases.push_back( | |
| 107 difference_estimator.MakeBase(old_elements[i]->region())); | |
| 108 } | |
| 109 LOG(INFO) << "done make bases " | |
| 110 << (base::Time::Now() - start_bases_time).InSecondsF() | |
| 111 << "s"; | |
| 112 | |
| 113 for (size_t new_index = 0; new_index < new_elements.size(); ++new_index) { | |
| 114 Element* new_element = new_elements[new_index]; | |
| 115 DifferenceEstimator::Subject* new_subject = | |
| 116 difference_estimator.MakeSubject(new_element->region()); | |
| 117 | |
| 118 // Search through old elements to find the best match. | |
| 119 // | |
| 120 // TODO(sra): This is O(N x M), i.e. O(N^2) since old_ensemble and | |
| 121 // new_ensemble probably have a very similar structure. We can make the | |
| 122 // search faster by making the comparison provided by DifferenceEstimator | |
| 123 // more nuanced, returning early if the measured difference is greater than | |
| 124 // the current best. This will be most effective if we can arrange that the | |
| 125 // first elements we try to match are likely the 'right' ones. We could | |
| 126 // prioritize elements that are of a similar size or similar position in the | |
| 127 // sequence of elements. | |
| 128 // | |
| 129 Element* best_old_element = NULL; | |
| 130 size_t best_difference = std::numeric_limits<size_t>::max(); | |
| 131 for (size_t old_index = 0; old_index < old_elements.size(); ++old_index) { | |
| 132 Element* old_element = old_elements[old_index]; | |
| 133 // Elements of different kinds are incompatible. | |
| 134 if (old_element->kind() != new_element->kind()) | |
| 135 continue; | |
| 136 | |
| 137 base::Time start_compare = base::Time::Now(); | |
| 138 DifferenceEstimator::Base* old_base = bases[old_index]; | |
| 139 size_t difference = difference_estimator.Measure(old_base, new_subject); | |
| 140 | |
| 141 LOG(INFO) << "Compare " << old_element->Name() | |
| 142 << " to " << new_element->Name() | |
| 143 << " --> " << difference | |
| 144 << " in " << (base::Time::Now() - start_compare).InSecondsF() | |
| 145 << "s"; | |
| 146 if (difference == 0) { | |
| 147 LOG(INFO) << "Skip " << new_element->Name() | |
| 148 << " - identical to " << old_element->Name(); | |
| 149 best_difference = 0; | |
| 150 best_old_element = NULL; | |
| 151 break; | |
| 152 } | |
| 153 if (difference < best_difference) { | |
| 154 best_difference = difference; | |
| 155 best_old_element = old_element; | |
| 156 } | |
| 157 } | |
| 158 | |
| 159 if (best_old_element) { | |
| 160 LOG(INFO) << "Matched " << best_old_element->Name() | |
| 161 << " to " << new_element->Name() | |
| 162 << " --> " << best_difference; | |
| 163 TransformationPatchGenerator* generator = | |
| 164 MakeGenerator(best_old_element, new_element); | |
| 165 if (generator) | |
| 166 generators->push_back(generator); | |
| 167 } | |
| 168 } | |
| 169 | |
| 170 LOG(INFO) << "done FindGenerators " | |
| 171 << "found " << generators->size() << " in " | |
| 172 << (base::Time::Now() - start_find_time).InSecondsF() << "s"; | |
| 173 | |
| 174 return C_OK; | |
| 175 } | |
| 176 | |
| 177 void FreeGenerators(std::vector<TransformationPatchGenerator*>* generators) { | |
| 178 for (size_t i = 0; i < generators->size(); ++i) { | |
| 179 delete (*generators)[i]; | |
| 180 } | |
| 181 generators->clear(); | |
| 182 } | |
| 183 | |
| 184 //////////////////////////////////////////////////////////////////////////////// | |
| 185 | |
| 186 Status GenerateEnsemblePatch(SourceStream* base, | |
| 187 SourceStream* update, | |
| 188 SinkStream* final_patch) { | |
| 189 Region old_region(base->Buffer(), base->Remaining()); | |
| 190 Region new_region(update->Buffer(), update->Remaining()); | |
| 191 Ensemble old_ensemble(old_region, "old"); | |
| 192 Ensemble new_ensemble(new_region, "new"); | |
| 193 std::vector<TransformationPatchGenerator*> generators; | |
| 194 Status generators_status = FindGenerators(&old_ensemble, &new_ensemble, | |
| 195 &generators); | |
| 196 if (generators_status != C_OK) | |
| 197 return generators_status; | |
| 198 | |
| 199 SinkStreamSet patch_streams; | |
| 200 | |
| 201 SinkStream* tranformation_descriptions = patch_streams.stream(0); | |
| 202 SinkStream* parameter_correction = patch_streams.stream(1); | |
| 203 SinkStream* transformed_elements_correction = patch_streams.stream(2); | |
| 204 SinkStream* ensemble_correction = patch_streams.stream(3); | |
| 205 | |
| 206 uint32 number_of_transformations = generators.size(); | |
| 207 tranformation_descriptions->WriteVarint32(number_of_transformations); | |
| 208 | |
| 209 for (size_t i = 0; i < number_of_transformations; ++i) { | |
| 210 CourgettePatchFile::TransformationMethodId kind = generators[i]->Kind(); | |
| 211 tranformation_descriptions->WriteVarint32(kind); | |
| 212 } | |
| 213 | |
| 214 for (size_t i = 0; i < number_of_transformations; ++i) { | |
| 215 Status status = | |
| 216 generators[i]->WriteInitialParameters(tranformation_descriptions); | |
| 217 if (status != C_OK) | |
| 218 return status; | |
| 219 } | |
| 220 | |
| 221 // | |
| 222 // Generate sub-patch for parameters. | |
| 223 // | |
| 224 SinkStreamSet predicted_parameters_sink; | |
| 225 SinkStreamSet corrected_parameters_sink; | |
| 226 | |
| 227 for (size_t i = 0; i < number_of_transformations; ++i) { | |
| 228 SinkStreamSet single_predicted_parameters; | |
| 229 Status status; | |
| 230 status = generators[i]->PredictTransformParameters( | |
| 231 &single_predicted_parameters); | |
| 232 if (status != C_OK) | |
| 233 return status; | |
| 234 if (!predicted_parameters_sink.WriteSet(&single_predicted_parameters)) | |
| 235 return C_STREAM_ERROR; | |
| 236 | |
| 237 SinkStreamSet single_corrected_parameters; | |
| 238 status = generators[i]->CorrectedTransformParameters( | |
| 239 &single_corrected_parameters); | |
| 240 if (status != C_OK) | |
| 241 return status; | |
| 242 if (!corrected_parameters_sink.WriteSet(&single_corrected_parameters)) | |
| 243 return C_STREAM_ERROR; | |
| 244 } | |
| 245 | |
| 246 SinkStream linearized_predicted_parameters; | |
| 247 SinkStream linearized_corrected_parameters; | |
| 248 | |
| 249 if (!predicted_parameters_sink.CopyTo(&linearized_predicted_parameters)) | |
| 250 return C_STREAM_ERROR; | |
| 251 if (!corrected_parameters_sink.CopyTo(&linearized_corrected_parameters)) | |
| 252 return C_STREAM_ERROR; | |
| 253 | |
| 254 SourceStream predicted_parameters_source; | |
| 255 SourceStream corrected_parameters_source; | |
| 256 predicted_parameters_source.Init(linearized_predicted_parameters); | |
| 257 corrected_parameters_source.Init(linearized_corrected_parameters); | |
| 258 | |
| 259 Status delta1_status = GenerateSimpleDelta(&predicted_parameters_source, | |
| 260 &corrected_parameters_source, | |
| 261 parameter_correction); | |
| 262 if (delta1_status != C_OK) | |
| 263 return delta1_status; | |
| 264 | |
| 265 // | |
| 266 // Generate sub-patch for elements. | |
| 267 // | |
| 268 corrected_parameters_source.Init(linearized_corrected_parameters); | |
| 269 SourceStreamSet corrected_parameters_source_set; | |
| 270 if (!corrected_parameters_source_set.Init(&corrected_parameters_source)) | |
| 271 return C_STREAM_ERROR; | |
| 272 | |
| 273 SinkStreamSet predicted_transformed_elements; | |
| 274 SinkStreamSet corrected_transformed_elements; | |
| 275 | |
| 276 for (size_t i = 0; i < number_of_transformations; ++i) { | |
| 277 SourceStreamSet single_parameters; | |
| 278 if (!corrected_parameters_source_set.ReadSet(&single_parameters)) | |
| 279 return C_STREAM_ERROR; | |
| 280 SinkStreamSet single_predicted_transformed_element; | |
| 281 SinkStreamSet single_corrected_transformed_element; | |
| 282 Status status = generators[i]->Transform( | |
| 283 &single_parameters, | |
| 284 &single_predicted_transformed_element, | |
| 285 &single_corrected_transformed_element); | |
| 286 if (status != C_OK) | |
| 287 return status; | |
| 288 if (!single_parameters.Empty()) | |
| 289 return C_STREAM_NOT_CONSUMED; | |
| 290 if (!predicted_transformed_elements.WriteSet( | |
| 291 &single_predicted_transformed_element)) | |
| 292 return C_STREAM_ERROR; | |
| 293 if (!corrected_transformed_elements.WriteSet( | |
| 294 &single_corrected_transformed_element)) | |
| 295 return C_STREAM_ERROR; | |
| 296 } | |
| 297 | |
| 298 if (!corrected_parameters_source_set.Empty()) | |
| 299 return C_STREAM_NOT_CONSUMED; | |
| 300 | |
| 301 SinkStream linearized_predicted_transformed_elements; | |
| 302 SinkStream linearized_corrected_transformed_elements; | |
| 303 | |
| 304 if (!predicted_transformed_elements.CopyTo( | |
| 305 &linearized_predicted_transformed_elements)) | |
| 306 return C_STREAM_ERROR; | |
| 307 if (!corrected_transformed_elements.CopyTo( | |
| 308 &linearized_corrected_transformed_elements)) | |
| 309 return C_STREAM_ERROR; | |
| 310 | |
| 311 SourceStream predicted_transformed_elements_source; | |
| 312 SourceStream corrected_transformed_elements_source; | |
| 313 predicted_transformed_elements_source | |
| 314 .Init(linearized_predicted_transformed_elements); | |
| 315 corrected_transformed_elements_source | |
| 316 .Init(linearized_corrected_transformed_elements); | |
| 317 | |
| 318 Status delta2_status = | |
| 319 GenerateSimpleDelta(&predicted_transformed_elements_source, | |
| 320 &corrected_transformed_elements_source, | |
| 321 transformed_elements_correction); | |
| 322 if (delta2_status != C_OK) | |
| 323 return delta2_status; | |
| 324 | |
| 325 // | |
| 326 // Generate sub-patch for whole enchilada. | |
| 327 // | |
| 328 SinkStream predicted_ensemble; | |
| 329 | |
| 330 predicted_ensemble.Write(base->Buffer(), base->Remaining()); | |
| 331 | |
| 332 SourceStreamSet corrected_transformed_elements_source_set; | |
| 333 corrected_transformed_elements_source | |
| 334 .Init(linearized_corrected_transformed_elements); | |
| 335 if (!corrected_transformed_elements_source_set | |
| 336 .Init(&corrected_transformed_elements_source)) | |
| 337 return C_STREAM_ERROR; | |
| 338 | |
| 339 for (size_t i = 0; i < number_of_transformations; ++i) { | |
| 340 SourceStreamSet single_corrected_transformed_element; | |
| 341 if (!corrected_transformed_elements_source_set.ReadSet( | |
| 342 &single_corrected_transformed_element)) | |
| 343 return C_STREAM_ERROR; | |
| 344 Status status = generators[i]->Reform(&single_corrected_transformed_element, | |
| 345 &predicted_ensemble); | |
| 346 if (status != C_OK) | |
| 347 return status; | |
| 348 if (!single_corrected_transformed_element.Empty()) | |
| 349 return C_STREAM_NOT_CONSUMED; | |
| 350 } | |
| 351 | |
| 352 if (!corrected_transformed_elements_source_set.Empty()) | |
| 353 return C_STREAM_NOT_CONSUMED; | |
| 354 | |
| 355 FreeGenerators(&generators); | |
| 356 | |
| 357 SourceStream predicted_ensemble_source; | |
| 358 predicted_ensemble_source.Init(predicted_ensemble); | |
| 359 Status delta3_status = GenerateSimpleDelta(&predicted_ensemble_source, | |
| 360 update, | |
| 361 ensemble_correction); | |
| 362 if (delta3_status != C_OK) | |
| 363 return delta3_status; | |
| 364 | |
| 365 // | |
| 366 // Final output stream has a header followed by a StreamSet. | |
| 367 // | |
| 368 final_patch->WriteVarint32(CourgettePatchFile::kMagic); | |
| 369 final_patch->WriteVarint32(CourgettePatchFile::kVersion); | |
| 370 | |
| 371 final_patch->WriteVarint32( | |
| 372 CalculateCrc(old_region.start(), old_region.length())); | |
| 373 final_patch->WriteVarint32( | |
| 374 CalculateCrc(new_region.start(), new_region.length())); | |
| 375 | |
| 376 if (!patch_streams.CopyTo(final_patch)) | |
| 377 return C_STREAM_ERROR; | |
| 378 | |
| 379 return C_OK; | |
| 380 } | |
| 381 | |
| 382 } // namespace | |
| OLD | NEW |
|---|
Chromium Code Reviews
