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