123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130 |
- // 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.
- // We want to measure the similarity of two sequences of bytes as a surrogate
- // for measuring how well a second sequence will compress differentially to the
- // first sequence.
- #include "courgette/difference_estimator.h"
- #include <stddef.h>
- #include <stdint.h>
- #include <string.h>
- #include <unordered_set>
- namespace courgette {
- // Our difference measure is the number of k-tuples that occur in Subject that
- // don't occur in Base.
- const int kTupleSize = 4;
- namespace {
- static_assert(kTupleSize >= 4 && kTupleSize <= 8,
- "kTupleSize should be between 4 and 8");
- size_t HashTuple(const uint8_t* source) {
- size_t hash1 = *reinterpret_cast<const uint32_t*>(source);
- size_t hash2 = *reinterpret_cast<const uint32_t*>(source + kTupleSize - 4);
- size_t hash = ((hash1 * 17 + hash2 * 37) + (hash1 >> 17)) ^ (hash2 >> 23);
- return hash;
- }
- bool RegionsEqual(const Region& a, const Region& b) {
- if (a.length() != b.length())
- return false;
- return memcmp(a.start(), b.start(), a.length()) == 0;
- }
- } // anonymous namepace
- class DifferenceEstimator::Base {
- public:
- explicit Base(const Region& region) : region_(region) { }
- Base(const Base&) = delete;
- Base& operator=(const Base&) = delete;
- void Init() {
- if (region_.length() < kTupleSize)
- return;
- const uint8_t* start = region_.start();
- const uint8_t* end = region_.end() - (kTupleSize - 1);
- for (const uint8_t* p = start; p < end; ++p) {
- size_t hash = HashTuple(p);
- hashes_.insert(hash);
- }
- }
- const Region& region() const { return region_; }
- private:
- Region region_;
- std::unordered_set<size_t> hashes_;
- friend class DifferenceEstimator;
- };
- class DifferenceEstimator::Subject {
- public:
- explicit Subject(const Region& region) : region_(region) {}
- Subject(const Subject&) = delete;
- Subject& operator=(const Subject&) = delete;
- const Region& region() const { return region_; }
- private:
- Region region_;
- };
- DifferenceEstimator::DifferenceEstimator() = default;
- DifferenceEstimator::~DifferenceEstimator() {
- for (size_t i = 0; i < owned_bases_.size(); ++i)
- delete owned_bases_[i];
- for (size_t i = 0; i < owned_subjects_.size(); ++i)
- delete owned_subjects_[i];
- }
- DifferenceEstimator::Base* DifferenceEstimator::MakeBase(const Region& region) {
- Base* base = new Base(region);
- base->Init();
- owned_bases_.push_back(base);
- return base;
- }
- DifferenceEstimator::Subject* DifferenceEstimator::MakeSubject(
- const Region& region) {
- Subject* subject = new Subject(region);
- owned_subjects_.push_back(subject);
- return subject;
- }
- size_t DifferenceEstimator::Measure(Base* base, Subject* subject) {
- size_t mismatches = 0;
- if (subject->region().length() >= kTupleSize) {
- const uint8_t* start = subject->region().start();
- const uint8_t* end = subject->region().end() - (kTupleSize - 1);
- const uint8_t* p = start;
- while (p < end) {
- size_t hash = HashTuple(p);
- if (base->hashes_.find(hash) == base->hashes_.end()) {
- ++mismatches;
- }
- p += 1;
- }
- }
- if (mismatches == 0) {
- if (RegionsEqual(base->region(), subject->region()))
- return 0;
- }
- ++mismatches; // Guarantee not zero.
- return mismatches;
- }
- } // namespace
|