123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208 |
- // Copyright 2017 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.
- #ifndef COMPONENTS_ZUCCHINI_EQUIVALENCE_MAP_H_
- #define COMPONENTS_ZUCCHINI_EQUIVALENCE_MAP_H_
- #include <stddef.h>
- #include <deque>
- #include <limits>
- #include <vector>
- #include "components/zucchini/image_index.h"
- #include "components/zucchini/image_utils.h"
- #include "components/zucchini/targets_affinity.h"
- namespace zucchini {
- constexpr double kMismatchFatal = -std::numeric_limits<double>::infinity();
- class EncodedView;
- class EquivalenceSource;
- // Returns similarity score between a token (raw byte or first byte of a
- // reference) in |old_image_index| at |src| and a token in |new_image_index|
- // at |dst|. |targets_affinities| describes affinities for each target pool and
- // is used to evaluate similarity between references, hence it's size must be
- // equal to the number of pools in both |old_image_index| and |new_image_index|.
- // Both |src| and |dst| must refer to tokens in |old_image_index| and
- // |new_image_index|.
- double GetTokenSimilarity(
- const ImageIndex& old_image_index,
- const ImageIndex& new_image_index,
- const std::vector<TargetsAffinity>& targets_affinities,
- offset_t src,
- offset_t dst);
- // Returns a similarity score between content in |old_image_index| and
- // |new_image_index| at regions described by |equivalence|, using
- // |targets_affinities| to evaluate similarity between references.
- double GetEquivalenceSimilarity(
- const ImageIndex& old_image_index,
- const ImageIndex& new_image_index,
- const std::vector<TargetsAffinity>& targets_affinities,
- const Equivalence& equivalence);
- // Extends |equivalence| forward and returns the result. This is related to
- // VisitEquivalenceSeed().
- EquivalenceCandidate ExtendEquivalenceForward(
- const ImageIndex& old_image_index,
- const ImageIndex& new_image_index,
- const std::vector<TargetsAffinity>& targets_affinities,
- const EquivalenceCandidate& equivalence,
- double min_similarity);
- // Extends |equivalence| backward and returns the result. This is related to
- // VisitEquivalenceSeed().
- EquivalenceCandidate ExtendEquivalenceBackward(
- const ImageIndex& old_image_index,
- const ImageIndex& new_image_index,
- const std::vector<TargetsAffinity>& targets_affinities,
- const EquivalenceCandidate& equivalence,
- double min_similarity);
- // Creates an equivalence, starting with |src| and |dst| as offset hint, and
- // extends it both forward and backward, trying to maximise similarity between
- // |old_image_index| and |new_image_index|, and returns the result.
- // |targets_affinities| is used to evaluate similarity between references.
- // |min_similarity| describes the minimum acceptable similarity score and is
- // used as threshold to discard bad equivalences.
- 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);
- // Container of pruned equivalences used to map offsets from |old_image| to
- // offsets in |new_image|. Equivalences are pruned by cropping smaller
- // equivalences to avoid overlaps, to make the equivalence map (for covered
- // bytes in |old_image| and |new_image|) one-to-one.
- class OffsetMapper {
- public:
- using const_iterator = std::deque<Equivalence>::const_iterator;
- // Constructors for various data sources. "Old" and "new" image sizes are
- // needed for bounds checks and to handle dangling targets.
- // - From a list of |equivalences|, already sorted (by |src_offset|) and
- // pruned, useful for tests.
- OffsetMapper(std::deque<Equivalence>&& equivalences,
- offset_t old_image_size,
- offset_t new_image_size);
- // - From a generator, useful for Zucchini-apply.
- OffsetMapper(EquivalenceSource&& equivalence_source,
- offset_t old_image_size,
- offset_t new_image_size);
- // - From an EquivalenceMap that needs to be processed, useful for
- // Zucchini-gen.
- OffsetMapper(const EquivalenceMap& equivalence_map,
- offset_t old_image_size,
- offset_t new_image_size);
- ~OffsetMapper();
- size_t size() const { return equivalences_.size(); }
- const_iterator begin() const { return equivalences_.begin(); }
- const_iterator end() const { return equivalences_.end(); }
- // Returns naive extended forward-projection of "old" |offset| that follows
- // |eq|'s delta. |eq| needs not cover |offset|.
- // - Averts underflow / overflow by clamping to |[0, new_image_size_)|.
- // - However, |offset| is *not* restricted to |[0, old_image_size_)|; the
- // caller must to make the check (hence "naive").
- offset_t NaiveExtendedForwardProject(const Equivalence& unit,
- offset_t offset) const;
- // Returns an offset in |new_image| corresponding to |offset| in |old_image|.
- // Assumes |equivalences_| to be non-empty. Cases:
- // - If |offset| is covered (i.e., in an "old" block), then use the delta of
- // the (unique) equivalence unit that covers |offset|.
- // - If |offset| is non-covered, but in |[0, old_image_size_)|, then find the
- // nearest "old" block, use its delta, and avert underflow / overflow by
- // clamping the result to |[0, new_image_size_)|.
- // - If |offset| is >= |new_image_size_| (a "fake offset"), then use
- // |new_image_size_ - old_image_size_| as the delta.
- offset_t ExtendedForwardProject(offset_t offset) const;
- // Given sorted |offsets|, applies a projection in-place of all offsets that
- // are part of a pruned equivalence from |old_image| to |new_image|. Other
- // offsets are removed from |offsets|.
- void ForwardProjectAll(std::deque<offset_t>* offsets) const;
- // Accessor for testing.
- const std::deque<Equivalence> equivalences() const { return equivalences_; }
- // Sorts |equivalences| by |src_offset| and removes all source overlaps; so a
- // source location that was covered by some Equivalence would become covered
- // by exactly one Equivalence. Moreover, for the offset, the equivalence
- // corresponds to the largest (pre-pruning) covering Equivalence, and in case
- // of a tie, the Equivalence with minimal |src_offset|. |equivalences| may
- // change in size since empty Equivalences are removed.
- static void PruneEquivalencesAndSortBySource(
- std::deque<Equivalence>* equivalences);
- private:
- // |equivalences_| is pruned, i.e., no "old" blocks overlap (and no "new"
- // block overlaps). Also, it is sorted by "old" offsets.
- std::deque<Equivalence> equivalences_;
- const offset_t old_image_size_;
- const offset_t new_image_size_;
- };
- // Container of equivalences between |old_image_index| and |new_image_index|,
- // sorted by |Equivalence::dst_offset|, only used during patch generation.
- class EquivalenceMap {
- public:
- using const_iterator = std::vector<EquivalenceCandidate>::const_iterator;
- EquivalenceMap();
- // Initializes the object with |equivalences|.
- explicit EquivalenceMap(std::vector<EquivalenceCandidate>&& candidates);
- EquivalenceMap(EquivalenceMap&&);
- EquivalenceMap(const EquivalenceMap&) = delete;
- ~EquivalenceMap();
- // Finds relevant equivalences between |old_view| and |new_view|, using
- // suffix array |old_sa| computed from |old_view| and using
- // |targets_affinities| to evaluate similarity between references. This
- // function is not symmetric. Equivalences might overlap in |old_view|, but
- // not in |new_view|. It tries to maximize accumulated similarity within each
- // equivalence, while maximizing |new_view| coverage. The minimum similarity
- // of an equivalence is given by |min_similarity|.
- void 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);
- size_t size() const { return candidates_.size(); }
- const_iterator begin() const { return candidates_.begin(); }
- const_iterator end() const { return candidates_.end(); }
- private:
- // Discovers equivalence candidates between |old_view| and |new_view| and
- // stores them in the object. Note that resulting candidates are not sorted
- // and might be overlapping in new image.
- void 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);
- // Sorts candidates by their offset in new image.
- void SortByDestination();
- // Visits |candidates_| (sorted by |dst_offset|) and remove all destination
- // overlaps. Candidates with low similarity scores are more likely to be
- // shrunken. Unfit candidates may be removed.
- void Prune(const EncodedView& old_view,
- const EncodedView& new_view,
- const std::vector<TargetsAffinity>& targets_affinities,
- double min_similarity);
- std::vector<EquivalenceCandidate> candidates_;
- };
- } // namespace zucchini
- #endif // COMPONENTS_ZUCCHINI_EQUIVALENCE_MAP_H_
|