equivalence_map.cc | Explore in Territory

// Copyright 2017 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "components/zucchini/equivalence_map.h"

#include <deque>
#include <tuple>
#include <utility>
#include <vector>

#include "base/logging.h"
#include "base/numerics/safe_conversions.h"
#include "base/ranges/algorithm.h"
#include "components/zucchini/encoded_view.h"
#include "components/zucchini/patch_reader.h"
#include "components/zucchini/suffix_array.h"

namespace zucchini {

namespace {

// TODO(haungs): Tune these numbers to improve pathological case results.

// In pathological cases Zucchini can exhibit O(n^2) behavior if the seed
// selection process runs to completion. To prevent this we impose a quota for
// the total length of equivalences the seed selection process can perform
// trials on. For regular use cases it is unlikely this quota will be exceeded,
// and if it is the effects on patch size are expected to be small.
constexpr uint64_t kSeedSelectionTotalVisitLengthQuota = …;  // 256 KiB

// The aforementioned quota alone is insufficient, as exploring backwards will
// still be very successful resulting in O(n) behavior in the case of a limited
// seed selection trials. This results in O(n^2) behavior returning. To mitigate
// this we also impose a cap on the ExtendEquivalenceBackward() exploration.
constexpr offset_t kBackwardsExtendLimit = …;  // 64 KiB

}  // namespace

/******** Utility Functions ********/

double GetTokenSimilarity(
    const ImageIndex& old_image_index,
    const ImageIndex& new_image_index,
    const std::vector<TargetsAffinity>& targets_affinities,
    offset_t src,
    offset_t dst) { … }

double GetEquivalenceSimilarity(
    const ImageIndex& old_image_index,
    const ImageIndex& new_image_index,
    const std::vector<TargetsAffinity>& targets_affinities,
    const Equivalence& equivalence) { … }

EquivalenceCandidate ExtendEquivalenceForward(
    const ImageIndex& old_image_index,
    const ImageIndex& new_image_index,
    const std::vector<TargetsAffinity>& targets_affinities,
    const EquivalenceCandidate& candidate,
    double min_similarity) { … }

EquivalenceCandidate ExtendEquivalenceBackward(
    const ImageIndex& old_image_index,
    const ImageIndex& new_image_index,
    const std::vector<TargetsAffinity>& targets_affinities,
    const EquivalenceCandidate& candidate,
    double min_similarity) { … }

EquivalenceCandidate VisitEquivalenceSeed(
    const ImageIndex& old_image_index,
    const ImageIndex& new_image_index,
    const std::vector<TargetsAffinity>& targets_affinities,
    offset_t src,
    offset_t dst,
    double min_similarity) { … }

/******** OffsetMapper ********/

OffsetMapper::OffsetMapper(std::deque<Equivalence>&& equivalences,
                           offset_t old_image_size,
                           offset_t new_image_size)
    : … { … }

OffsetMapper::OffsetMapper(EquivalenceSource&& equivalence_source,
                           offset_t old_image_size,
                           offset_t new_image_size)
    : … { … }

OffsetMapper::OffsetMapper(const EquivalenceMap& equivalence_map,
                           offset_t old_image_size,
                           offset_t new_image_size)
    : … { … }

OffsetMapper::~OffsetMapper() = default;

// Safely evaluates |offset - unit.src_offset + unit.dst_offset| with signed
// arithmetic, then clips the result to |[0, new_image_size_)|.
offset_t OffsetMapper::NaiveExtendedForwardProject(const Equivalence& unit,
                                                   offset_t offset) const { … }

offset_t OffsetMapper::ExtendedForwardProject(offset_t offset) const { … }

void OffsetMapper::ForwardProjectAll(std::deque<offset_t>* offsets) const { … }

void OffsetMapper::PruneEquivalencesAndSortBySource(
    std::deque<Equivalence>* equivalences) { … }

/******** EquivalenceMap ********/

EquivalenceMap::EquivalenceMap() = default;

EquivalenceMap::EquivalenceMap(std::vector<EquivalenceCandidate>&& equivalences)
    : … { … }

EquivalenceMap::EquivalenceMap(EquivalenceMap&&) = default;

EquivalenceMap::~EquivalenceMap() = default;

void EquivalenceMap::Build(
    const std::vector<offset_t>& old_sa,
    const EncodedView& old_view,
    const EncodedView& new_view,
    const std::vector<TargetsAffinity>& targets_affinities,
    double min_similarity) { … }

void EquivalenceMap::CreateCandidates(
    const std::vector<offset_t>& old_sa,
    const EncodedView& old_view,
    const EncodedView& new_view,
    const std::vector<TargetsAffinity>& targets_affinities,
    double min_similarity) { … }

void EquivalenceMap::SortByDestination() { … }

void EquivalenceMap::Prune(
    const EncodedView& old_view,
    const EncodedView& new_view,
    const std::vector<TargetsAffinity>& target_affinities,
    double min_similarity) { … }

}  // namespace zucchini
chromium/components/zucchini/equivalence_map.cc
