| OLD | NEW |
| 1 // Copyright (c) 2009 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2010 The Chromium Authors. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 // The main idea in Courgette is to do patching *under a tranformation*. The | 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 | 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. | 7 // repesentation, and then the tranform is reversed to get the patched data. |
| 8 // | 8 // |
| 9 // The idea is applied to pieces (or 'elements') of the whole (or 'ensemble'). | 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. | 10 // Each of the elements has to go through the same set of steps in lock-step. |
| 11 | 11 |
| (...skipping 94 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 106 // |new_ensemble|. For each element of |new_ensemble| we find the closest | 106 // |new_ensemble|. For each element of |new_ensemble| we find the closest |
| 107 // matching element from |old_ensemble| and use that as the basis for | 107 // matching element from |old_ensemble| and use that as the basis for |
| 108 // differential compression. The elements have to be the same kind so as to | 108 // differential compression. The elements have to be the same kind so as to |
| 109 // support transformation into the same kind of 'new representation'. | 109 // support transformation into the same kind of 'new representation'. |
| 110 // | 110 // |
| 111 Status FindGenerators(Ensemble* old_ensemble, Ensemble* new_ensemble, | 111 Status FindGenerators(Ensemble* old_ensemble, Ensemble* new_ensemble, |
| 112 std::vector<TransformationPatchGenerator*>* generators) { | 112 std::vector<TransformationPatchGenerator*>* generators) { |
| 113 base::Time start_find_time = base::Time::Now(); | 113 base::Time start_find_time = base::Time::Now(); |
| 114 old_ensemble->FindEmbeddedElements(); | 114 old_ensemble->FindEmbeddedElements(); |
| 115 new_ensemble->FindEmbeddedElements(); | 115 new_ensemble->FindEmbeddedElements(); |
| 116 LOG(INFO) << "done FindEmbeddedElements " | 116 VLOG(1) << "done FindEmbeddedElements " |
| 117 << (base::Time::Now() - start_find_time).InSecondsF(); | 117 << (base::Time::Now() - start_find_time).InSecondsF(); |
| 118 | 118 |
| 119 std::vector<Element*> old_elements(old_ensemble->elements()); | 119 std::vector<Element*> old_elements(old_ensemble->elements()); |
| 120 std::vector<Element*> new_elements(new_ensemble->elements()); | 120 std::vector<Element*> new_elements(new_ensemble->elements()); |
| 121 | 121 |
| 122 LOG(INFO) << "old has " << old_elements.size() << " elements"; | 122 VLOG(1) << "old has " << old_elements.size() << " elements"; |
| 123 LOG(INFO) << "new has " << new_elements.size() << " elements"; | 123 VLOG(1) << "new has " << new_elements.size() << " elements"; |
| 124 | 124 |
| 125 DifferenceEstimator difference_estimator; | 125 DifferenceEstimator difference_estimator; |
| 126 std::vector<DifferenceEstimator::Base*> bases; | 126 std::vector<DifferenceEstimator::Base*> bases; |
| 127 | 127 |
| 128 base::Time start_bases_time = base::Time::Now(); | 128 base::Time start_bases_time = base::Time::Now(); |
| 129 for (size_t i = 0; i < old_elements.size(); ++i) { | 129 for (size_t i = 0; i < old_elements.size(); ++i) { |
| 130 bases.push_back( | 130 bases.push_back( |
| 131 difference_estimator.MakeBase(old_elements[i]->region())); | 131 difference_estimator.MakeBase(old_elements[i]->region())); |
| 132 } | 132 } |
| 133 LOG(INFO) << "done make bases " | 133 VLOG(1) << "done make bases " |
| 134 << (base::Time::Now() - start_bases_time).InSecondsF() | 134 << (base::Time::Now() - start_bases_time).InSecondsF() << "s"; |
| 135 << "s"; | |
| 136 | 135 |
| 137 for (size_t new_index = 0; new_index < new_elements.size(); ++new_index) { | 136 for (size_t new_index = 0; new_index < new_elements.size(); ++new_index) { |
| 138 Element* new_element = new_elements[new_index]; | 137 Element* new_element = new_elements[new_index]; |
| 139 DifferenceEstimator::Subject* new_subject = | 138 DifferenceEstimator::Subject* new_subject = |
| 140 difference_estimator.MakeSubject(new_element->region()); | 139 difference_estimator.MakeSubject(new_element->region()); |
| 141 | 140 |
| 142 // Search through old elements to find the best match. | 141 // Search through old elements to find the best match. |
| 143 // | 142 // |
| 144 // TODO(sra): This is O(N x M), i.e. O(N^2) since old_ensemble and | 143 // TODO(sra): This is O(N x M), i.e. O(N^2) since old_ensemble and |
| 145 // new_ensemble probably have a very similar structure. We can make the | 144 // new_ensemble probably have a very similar structure. We can make the |
| (...skipping 12 matching lines...) Expand all Loading... |
| 158 if (old_element->kind() != new_element->kind()) | 157 if (old_element->kind() != new_element->kind()) |
| 159 continue; | 158 continue; |
| 160 | 159 |
| 161 if (UnsafeDifference(old_element, new_element)) | 160 if (UnsafeDifference(old_element, new_element)) |
| 162 continue; | 161 continue; |
| 163 | 162 |
| 164 base::Time start_compare = base::Time::Now(); | 163 base::Time start_compare = base::Time::Now(); |
| 165 DifferenceEstimator::Base* old_base = bases[old_index]; | 164 DifferenceEstimator::Base* old_base = bases[old_index]; |
| 166 size_t difference = difference_estimator.Measure(old_base, new_subject); | 165 size_t difference = difference_estimator.Measure(old_base, new_subject); |
| 167 | 166 |
| 168 LOG(INFO) << "Compare " << old_element->Name() | 167 VLOG(1) << "Compare " << old_element->Name() |
| 169 << " to " << new_element->Name() | 168 << " to " << new_element->Name() |
| 170 << " --> " << difference | 169 << " --> " << difference |
| 171 << " in " << (base::Time::Now() - start_compare).InSecondsF() | 170 << " in " << (base::Time::Now() - start_compare).InSecondsF() |
| 172 << "s"; | 171 << "s"; |
| 173 if (difference == 0) { | 172 if (difference == 0) { |
| 174 LOG(INFO) << "Skip " << new_element->Name() | 173 VLOG(1) << "Skip " << new_element->Name() |
| 175 << " - identical to " << old_element->Name(); | 174 << " - identical to " << old_element->Name(); |
| 176 best_difference = 0; | 175 best_difference = 0; |
| 177 best_old_element = NULL; | 176 best_old_element = NULL; |
| 178 break; | 177 break; |
| 179 } | 178 } |
| 180 if (difference < best_difference) { | 179 if (difference < best_difference) { |
| 181 best_difference = difference; | 180 best_difference = difference; |
| 182 best_old_element = old_element; | 181 best_old_element = old_element; |
| 183 } | 182 } |
| 184 } | 183 } |
| 185 | 184 |
| 186 if (best_old_element) { | 185 if (best_old_element) { |
| 187 LOG(INFO) << "Matched " << best_old_element->Name() | 186 VLOG(1) << "Matched " << best_old_element->Name() |
| 188 << " to " << new_element->Name() | 187 << " to " << new_element->Name() |
| 189 << " --> " << best_difference; | 188 << " --> " << best_difference; |
| 190 TransformationPatchGenerator* generator = | 189 TransformationPatchGenerator* generator = |
| 191 MakeGenerator(best_old_element, new_element); | 190 MakeGenerator(best_old_element, new_element); |
| 192 if (generator) | 191 if (generator) |
| 193 generators->push_back(generator); | 192 generators->push_back(generator); |
| 194 } | 193 } |
| 195 } | 194 } |
| 196 | 195 |
| 197 LOG(INFO) << "done FindGenerators " | 196 VLOG(1) << "done FindGenerators found " << generators->size() |
| 198 << "found " << generators->size() << " in " | 197 << " in " << (base::Time::Now() - start_find_time).InSecondsF() |
| 199 << (base::Time::Now() - start_find_time).InSecondsF() << "s"; | 198 << "s"; |
| 200 | 199 |
| 201 return C_OK; | 200 return C_OK; |
| 202 } | 201 } |
| 203 | 202 |
| 204 void FreeGenerators(std::vector<TransformationPatchGenerator*>* generators) { | 203 void FreeGenerators(std::vector<TransformationPatchGenerator*>* generators) { |
| 205 for (size_t i = 0; i < generators->size(); ++i) { | 204 for (size_t i = 0; i < generators->size(); ++i) { |
| 206 delete (*generators)[i]; | 205 delete (*generators)[i]; |
| 207 } | 206 } |
| 208 generators->clear(); | 207 generators->clear(); |
| 209 } | 208 } |
| 210 | 209 |
| 211 //////////////////////////////////////////////////////////////////////////////// | 210 //////////////////////////////////////////////////////////////////////////////// |
| 212 | 211 |
| 213 Status GenerateEnsemblePatch(SourceStream* base, | 212 Status GenerateEnsemblePatch(SourceStream* base, |
| 214 SourceStream* update, | 213 SourceStream* update, |
| 215 SinkStream* final_patch) { | 214 SinkStream* final_patch) { |
| 216 LOG(INFO) << "start GenerateEnsemblePatch"; | 215 VLOG(1) << "start GenerateEnsemblePatch"; |
| 217 base::Time start_time = base::Time::Now(); | 216 base::Time start_time = base::Time::Now(); |
| 218 | 217 |
| 219 Region old_region(base->Buffer(), base->Remaining()); | 218 Region old_region(base->Buffer(), base->Remaining()); |
| 220 Region new_region(update->Buffer(), update->Remaining()); | 219 Region new_region(update->Buffer(), update->Remaining()); |
| 221 Ensemble old_ensemble(old_region, "old"); | 220 Ensemble old_ensemble(old_region, "old"); |
| 222 Ensemble new_ensemble(new_region, "new"); | 221 Ensemble new_ensemble(new_region, "new"); |
| 223 std::vector<TransformationPatchGenerator*> generators; | 222 std::vector<TransformationPatchGenerator*> generators; |
| 224 Status generators_status = FindGenerators(&old_ensemble, &new_ensemble, | 223 Status generators_status = FindGenerators(&old_ensemble, &new_ensemble, |
| 225 &generators); | 224 &generators); |
| 226 if (generators_status != C_OK) | 225 if (generators_status != C_OK) |
| (...skipping 172 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 399 final_patch->WriteVarint32(CourgettePatchFile::kVersion); | 398 final_patch->WriteVarint32(CourgettePatchFile::kVersion); |
| 400 | 399 |
| 401 final_patch->WriteVarint32( | 400 final_patch->WriteVarint32( |
| 402 CalculateCrc(old_region.start(), old_region.length())); | 401 CalculateCrc(old_region.start(), old_region.length())); |
| 403 final_patch->WriteVarint32( | 402 final_patch->WriteVarint32( |
| 404 CalculateCrc(new_region.start(), new_region.length())); | 403 CalculateCrc(new_region.start(), new_region.length())); |
| 405 | 404 |
| 406 if (!patch_streams.CopyTo(final_patch)) | 405 if (!patch_streams.CopyTo(final_patch)) |
| 407 return C_STREAM_ERROR; | 406 return C_STREAM_ERROR; |
| 408 | 407 |
| 409 LOG(INFO) << "done GenerateEnsemblePatch " | 408 VLOG(1) << "done GenerateEnsemblePatch " |
| 410 << (base::Time::Now() - start_time).InSecondsF() << "s"; | 409 << (base::Time::Now() - start_time).InSecondsF() << "s"; |
| 411 | 410 |
| 412 return C_OK; | 411 return C_OK; |
| 413 } | 412 } |
| 414 | 413 |
| 415 } // namespace | 414 } // namespace |
| OLD | NEW |