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 <stddef.h>
  12
  13 #include <vector>
  14
  15 #include "base/macros.h"
  16 #include "courgette/region.h"
  17
  18 namespace courgette {
  19
  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.
  25 //
  26 // The measure is asymmetric, if the Subject is a small substring of the Base
  27 // then it should match very well.
  28 //
  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
  32 // comparison.
  33 //
  34 class DifferenceEstimator {
  35  public:
  36   DifferenceEstimator();
  37   ~DifferenceEstimator();
  38
  39   class Base;
  40   class Subject;
  41
  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);
  47
  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);
  52
  53  private:
  54   std::vector<Base*> owned_bases_;
  55   std::vector<Subject*> owned_subjects_;
  56   DISALLOW_COPY_AND_ASSIGN(DifferenceEstimator);
  57 };
  58
  59 }  // namespace
  60
  61 #endif  // COURGETTE_DIFFERENCE_ESTIMATOR_H_