blob: 295ff93a10a2a0e3273b4c775419aedd19f8be1c [file] [log] [blame]
// 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.
#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 {
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);
std::vector<Base*> owned_bases_;
std::vector<Subject*> owned_subjects_;
} // namespace