courgette/difference_estimator.h

   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_