difference_estimator.cc 3.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130
  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. // We want to measure the similarity of two sequences of bytes as a surrogate
  5. // for measuring how well a second sequence will compress differentially to the
  6. // first sequence.
  7. #include "courgette/difference_estimator.h"
  8. #include <stddef.h>
  9. #include <stdint.h>
  10. #include <string.h>
  11. #include <unordered_set>
  12. namespace courgette {
  13. // Our difference measure is the number of k-tuples that occur in Subject that
  14. // don't occur in Base.
  15. const int kTupleSize = 4;
  16. namespace {
  17. static_assert(kTupleSize >= 4 && kTupleSize <= 8,
  18. "kTupleSize should be between 4 and 8");
  19. size_t HashTuple(const uint8_t* source) {
  20. size_t hash1 = *reinterpret_cast<const uint32_t*>(source);
  21. size_t hash2 = *reinterpret_cast<const uint32_t*>(source + kTupleSize - 4);
  22. size_t hash = ((hash1 * 17 + hash2 * 37) + (hash1 >> 17)) ^ (hash2 >> 23);
  23. return hash;
  24. }
  25. bool RegionsEqual(const Region& a, const Region& b) {
  26. if (a.length() != b.length())
  27. return false;
  28. return memcmp(a.start(), b.start(), a.length()) == 0;
  29. }
  30. } // anonymous namepace
  31. class DifferenceEstimator::Base {
  32. public:
  33. explicit Base(const Region& region) : region_(region) { }
  34. Base(const Base&) = delete;
  35. Base& operator=(const Base&) = delete;
  36. void Init() {
  37. if (region_.length() < kTupleSize)
  38. return;
  39. const uint8_t* start = region_.start();
  40. const uint8_t* end = region_.end() - (kTupleSize - 1);
  41. for (const uint8_t* p = start; p < end; ++p) {
  42. size_t hash = HashTuple(p);
  43. hashes_.insert(hash);
  44. }
  45. }
  46. const Region& region() const { return region_; }
  47. private:
  48. Region region_;
  49. std::unordered_set<size_t> hashes_;
  50. friend class DifferenceEstimator;
  51. };
  52. class DifferenceEstimator::Subject {
  53. public:
  54. explicit Subject(const Region& region) : region_(region) {}
  55. Subject(const Subject&) = delete;
  56. Subject& operator=(const Subject&) = delete;
  57. const Region& region() const { return region_; }
  58. private:
  59. Region region_;
  60. };
  61. DifferenceEstimator::DifferenceEstimator() = default;
  62. DifferenceEstimator::~DifferenceEstimator() {
  63. for (size_t i = 0; i < owned_bases_.size(); ++i)
  64. delete owned_bases_[i];
  65. for (size_t i = 0; i < owned_subjects_.size(); ++i)
  66. delete owned_subjects_[i];
  67. }
  68. DifferenceEstimator::Base* DifferenceEstimator::MakeBase(const Region& region) {
  69. Base* base = new Base(region);
  70. base->Init();
  71. owned_bases_.push_back(base);
  72. return base;
  73. }
  74. DifferenceEstimator::Subject* DifferenceEstimator::MakeSubject(
  75. const Region& region) {
  76. Subject* subject = new Subject(region);
  77. owned_subjects_.push_back(subject);
  78. return subject;
  79. }
  80. size_t DifferenceEstimator::Measure(Base* base, Subject* subject) {
  81. size_t mismatches = 0;
  82. if (subject->region().length() >= kTupleSize) {
  83. const uint8_t* start = subject->region().start();
  84. const uint8_t* end = subject->region().end() - (kTupleSize - 1);
  85. const uint8_t* p = start;
  86. while (p < end) {
  87. size_t hash = HashTuple(p);
  88. if (base->hashes_.find(hash) == base->hashes_.end()) {
  89. ++mismatches;
  90. }
  91. p += 1;
  92. }
  93. }
  94. if (mismatches == 0) {
  95. if (RegionsEqual(base->region(), subject->region()))
  96. return 0;
  97. }
  98. ++mismatches; // Guarantee not zero.
  99. return mismatches;
  100. }
  101. } // namespace