difference_estimator.h 2.1 KB

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