courgette/difference_estimator.cc

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