Move Courgette...

courgette/difference_estimator.h

+// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+// A DifferenceEstimator class provides a means for quickly estimating the
+// difference between two regions of memory.
+
+#ifndef COURGETTE_DIFFERENCE_ESTIMATOR_H_
+#define COURGETTE_DIFFERENCE_ESTIMATOR_H_
+
+#include <vector>
+
+#include "courgette/region.h"
+
+namespace courgette {
+
+// A DifferenceEstimator simplifies the task of determining which 'Subject' byte
+// strings (stored in regions of memory) are good matches to existing 'Base'
+// regions.  The ultimate measure would be to try full differential compression
+// and measure the output size, but an estimate that correlates well with the
+// full compression is more efficient.
+//
+// The measure is asymmetric, if the Subject is a small substring of the Base
+// then it should match very well.
+//
+// The comparison is staged: first make Base and Subject objects for the regions
+// and then call 'Measure' to get the estimate.  The staging allows multiple
+// comparisons to be more efficient by precomputing information used in the
+// comparison.
+//
+class DifferenceEstimator {
+ public:
+  DifferenceEstimator();
+  ~DifferenceEstimator();
+
+  class Base;
+  class Subject;
+
+  // This DifferenceEstimator owns the objects returned by MakeBase and
+  // MakeSubject.  Caller continues to own memory at |region| and must not free
+  // it until ~DifferenceEstimator has been called.
+  Base* MakeBase(const Region& region);
+  Subject* MakeSubject(const Region& region);
+
+  // Returns a value correlated with the size of the bsdiff or xdelta difference
+  // from |base| to |subject|.  Returns zero iff the base and subject regions
+  // are bytewise identical.
+  size_t Measure(Base* base,  Subject* subject);
+
+ private:
+  std::vector<Base*> owned_bases_;
+  std::vector<Subject*> owned_subjects_;
+  DISALLOW_COPY_AND_ASSIGN(DifferenceEstimator);
+};
+
+}  // namespace
+
+#endif  // COURGETTE_DIFFERENCE_ESTIMATOR_H_