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 // A DifferenceEstimator class provides a means for quickly estimating the 6 // difference between two regions of memory. 7 8 #ifndef COURGETTE_DIFFERENCE_ESTIMATOR_H_ 9 #define COURGETTE_DIFFERENCE_ESTIMATOR_H_ 10 11 #include <vector> 12 13 #include "courgette/region.h" 14 15 namespace courgette { 16 17 // A DifferenceEstimator simplifies the task of determining which 'Subject' byte 18 // strings (stored in regions of memory) are good matches to existing 'Base' 19 // regions. The ultimate measure would be to try full differential compression 20 // and measure the output size, but an estimate that correlates well with the 21 // full compression is more efficient. 22 // 23 // The measure is asymmetric, if the Subject is a small substring of the Base 24 // then it should match very well. 25 // 26 // The comparison is staged: first make Base and Subject objects for the regions 27 // and then call 'Measure' to get the estimate. The staging allows multiple 28 // comparisons to be more efficient by precomputing information used in the 29 // comparison. 30 // 31 class DifferenceEstimator { 32 public: 33 DifferenceEstimator(); 34 ~DifferenceEstimator(); 35 36 class Base; 37 class Subject; 38 39 // This DifferenceEstimator owns the objects returned by MakeBase and 40 // MakeSubject. Caller continues to own memory at |region| and must not free 41 // it until ~DifferenceEstimator has been called. 42 Base* MakeBase(const Region& region); 43 Subject* MakeSubject(const Region& region); 44 45 // Returns a value correlated with the size of the bsdiff or xdelta difference 46 // from |base| to |subject|. Returns zero iff the base and subject regions 47 // are bytewise identical. 48 size_t Measure(Base* base, Subject* subject); 49 50 private: 51 std::vector<Base*> owned_bases_; 52 std::vector<Subject*> owned_subjects_; 53 DISALLOW_COPY_AND_ASSIGN(DifferenceEstimator); 54 }; 55 56 } // namespace 57 58 #endif // COURGETTE_DIFFERENCE_ESTIMATOR_H_ 59
