equivalence_map.h 9.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208
  1. // Copyright 2017 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. #ifndef COMPONENTS_ZUCCHINI_EQUIVALENCE_MAP_H_
  5. #define COMPONENTS_ZUCCHINI_EQUIVALENCE_MAP_H_
  6. #include <stddef.h>
  7. #include <deque>
  8. #include <limits>
  9. #include <vector>
  10. #include "components/zucchini/image_index.h"
  11. #include "components/zucchini/image_utils.h"
  12. #include "components/zucchini/targets_affinity.h"
  13. namespace zucchini {
  14. constexpr double kMismatchFatal = -std::numeric_limits<double>::infinity();
  15. class EncodedView;
  16. class EquivalenceSource;
  17. // Returns similarity score between a token (raw byte or first byte of a
  18. // reference) in |old_image_index| at |src| and a token in |new_image_index|
  19. // at |dst|. |targets_affinities| describes affinities for each target pool and
  20. // is used to evaluate similarity between references, hence it's size must be
  21. // equal to the number of pools in both |old_image_index| and |new_image_index|.
  22. // Both |src| and |dst| must refer to tokens in |old_image_index| and
  23. // |new_image_index|.
  24. double GetTokenSimilarity(
  25. const ImageIndex& old_image_index,
  26. const ImageIndex& new_image_index,
  27. const std::vector<TargetsAffinity>& targets_affinities,
  28. offset_t src,
  29. offset_t dst);
  30. // Returns a similarity score between content in |old_image_index| and
  31. // |new_image_index| at regions described by |equivalence|, using
  32. // |targets_affinities| to evaluate similarity between references.
  33. double GetEquivalenceSimilarity(
  34. const ImageIndex& old_image_index,
  35. const ImageIndex& new_image_index,
  36. const std::vector<TargetsAffinity>& targets_affinities,
  37. const Equivalence& equivalence);
  38. // Extends |equivalence| forward and returns the result. This is related to
  39. // VisitEquivalenceSeed().
  40. EquivalenceCandidate ExtendEquivalenceForward(
  41. const ImageIndex& old_image_index,
  42. const ImageIndex& new_image_index,
  43. const std::vector<TargetsAffinity>& targets_affinities,
  44. const EquivalenceCandidate& equivalence,
  45. double min_similarity);
  46. // Extends |equivalence| backward and returns the result. This is related to
  47. // VisitEquivalenceSeed().
  48. EquivalenceCandidate ExtendEquivalenceBackward(
  49. const ImageIndex& old_image_index,
  50. const ImageIndex& new_image_index,
  51. const std::vector<TargetsAffinity>& targets_affinities,
  52. const EquivalenceCandidate& equivalence,
  53. double min_similarity);
  54. // Creates an equivalence, starting with |src| and |dst| as offset hint, and
  55. // extends it both forward and backward, trying to maximise similarity between
  56. // |old_image_index| and |new_image_index|, and returns the result.
  57. // |targets_affinities| is used to evaluate similarity between references.
  58. // |min_similarity| describes the minimum acceptable similarity score and is
  59. // used as threshold to discard bad equivalences.
  60. EquivalenceCandidate VisitEquivalenceSeed(
  61. const ImageIndex& old_image_index,
  62. const ImageIndex& new_image_index,
  63. const std::vector<TargetsAffinity>& targets_affinities,
  64. offset_t src,
  65. offset_t dst,
  66. double min_similarity);
  67. // Container of pruned equivalences used to map offsets from |old_image| to
  68. // offsets in |new_image|. Equivalences are pruned by cropping smaller
  69. // equivalences to avoid overlaps, to make the equivalence map (for covered
  70. // bytes in |old_image| and |new_image|) one-to-one.
  71. class OffsetMapper {
  72. public:
  73. using const_iterator = std::deque<Equivalence>::const_iterator;
  74. // Constructors for various data sources. "Old" and "new" image sizes are
  75. // needed for bounds checks and to handle dangling targets.
  76. // - From a list of |equivalences|, already sorted (by |src_offset|) and
  77. // pruned, useful for tests.
  78. OffsetMapper(std::deque<Equivalence>&& equivalences,
  79. offset_t old_image_size,
  80. offset_t new_image_size);
  81. // - From a generator, useful for Zucchini-apply.
  82. OffsetMapper(EquivalenceSource&& equivalence_source,
  83. offset_t old_image_size,
  84. offset_t new_image_size);
  85. // - From an EquivalenceMap that needs to be processed, useful for
  86. // Zucchini-gen.
  87. OffsetMapper(const EquivalenceMap& equivalence_map,
  88. offset_t old_image_size,
  89. offset_t new_image_size);
  90. ~OffsetMapper();
  91. size_t size() const { return equivalences_.size(); }
  92. const_iterator begin() const { return equivalences_.begin(); }
  93. const_iterator end() const { return equivalences_.end(); }
  94. // Returns naive extended forward-projection of "old" |offset| that follows
  95. // |eq|'s delta. |eq| needs not cover |offset|.
  96. // - Averts underflow / overflow by clamping to |[0, new_image_size_)|.
  97. // - However, |offset| is *not* restricted to |[0, old_image_size_)|; the
  98. // caller must to make the check (hence "naive").
  99. offset_t NaiveExtendedForwardProject(const Equivalence& unit,
  100. offset_t offset) const;
  101. // Returns an offset in |new_image| corresponding to |offset| in |old_image|.
  102. // Assumes |equivalences_| to be non-empty. Cases:
  103. // - If |offset| is covered (i.e., in an "old" block), then use the delta of
  104. // the (unique) equivalence unit that covers |offset|.
  105. // - If |offset| is non-covered, but in |[0, old_image_size_)|, then find the
  106. // nearest "old" block, use its delta, and avert underflow / overflow by
  107. // clamping the result to |[0, new_image_size_)|.
  108. // - If |offset| is >= |new_image_size_| (a "fake offset"), then use
  109. // |new_image_size_ - old_image_size_| as the delta.
  110. offset_t ExtendedForwardProject(offset_t offset) const;
  111. // Given sorted |offsets|, applies a projection in-place of all offsets that
  112. // are part of a pruned equivalence from |old_image| to |new_image|. Other
  113. // offsets are removed from |offsets|.
  114. void ForwardProjectAll(std::deque<offset_t>* offsets) const;
  115. // Accessor for testing.
  116. const std::deque<Equivalence> equivalences() const { return equivalences_; }
  117. // Sorts |equivalences| by |src_offset| and removes all source overlaps; so a
  118. // source location that was covered by some Equivalence would become covered
  119. // by exactly one Equivalence. Moreover, for the offset, the equivalence
  120. // corresponds to the largest (pre-pruning) covering Equivalence, and in case
  121. // of a tie, the Equivalence with minimal |src_offset|. |equivalences| may
  122. // change in size since empty Equivalences are removed.
  123. static void PruneEquivalencesAndSortBySource(
  124. std::deque<Equivalence>* equivalences);
  125. private:
  126. // |equivalences_| is pruned, i.e., no "old" blocks overlap (and no "new"
  127. // block overlaps). Also, it is sorted by "old" offsets.
  128. std::deque<Equivalence> equivalences_;
  129. const offset_t old_image_size_;
  130. const offset_t new_image_size_;
  131. };
  132. // Container of equivalences between |old_image_index| and |new_image_index|,
  133. // sorted by |Equivalence::dst_offset|, only used during patch generation.
  134. class EquivalenceMap {
  135. public:
  136. using const_iterator = std::vector<EquivalenceCandidate>::const_iterator;
  137. EquivalenceMap();
  138. // Initializes the object with |equivalences|.
  139. explicit EquivalenceMap(std::vector<EquivalenceCandidate>&& candidates);
  140. EquivalenceMap(EquivalenceMap&&);
  141. EquivalenceMap(const EquivalenceMap&) = delete;
  142. ~EquivalenceMap();
  143. // Finds relevant equivalences between |old_view| and |new_view|, using
  144. // suffix array |old_sa| computed from |old_view| and using
  145. // |targets_affinities| to evaluate similarity between references. This
  146. // function is not symmetric. Equivalences might overlap in |old_view|, but
  147. // not in |new_view|. It tries to maximize accumulated similarity within each
  148. // equivalence, while maximizing |new_view| coverage. The minimum similarity
  149. // of an equivalence is given by |min_similarity|.
  150. void Build(const std::vector<offset_t>& old_sa,
  151. const EncodedView& old_view,
  152. const EncodedView& new_view,
  153. const std::vector<TargetsAffinity>& targets_affinities,
  154. double min_similarity);
  155. size_t size() const { return candidates_.size(); }
  156. const_iterator begin() const { return candidates_.begin(); }
  157. const_iterator end() const { return candidates_.end(); }
  158. private:
  159. // Discovers equivalence candidates between |old_view| and |new_view| and
  160. // stores them in the object. Note that resulting candidates are not sorted
  161. // and might be overlapping in new image.
  162. void CreateCandidates(const std::vector<offset_t>& old_sa,
  163. const EncodedView& old_view,
  164. const EncodedView& new_view,
  165. const std::vector<TargetsAffinity>& targets_affinities,
  166. double min_similarity);
  167. // Sorts candidates by their offset in new image.
  168. void SortByDestination();
  169. // Visits |candidates_| (sorted by |dst_offset|) and remove all destination
  170. // overlaps. Candidates with low similarity scores are more likely to be
  171. // shrunken. Unfit candidates may be removed.
  172. void Prune(const EncodedView& old_view,
  173. const EncodedView& new_view,
  174. const std::vector<TargetsAffinity>& targets_affinities,
  175. double min_similarity);
  176. std::vector<EquivalenceCandidate> candidates_;
  177. };
  178. } // namespace zucchini
  179. #endif // COMPONENTS_ZUCCHINI_EQUIVALENCE_MAP_H_