Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 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 | |
| 5 | #ifndef COMPONENTS_ZUCCHINI_TARGETS_AFFINITY_H_ |
| 6 | #define COMPONENTS_ZUCCHINI_TARGETS_AFFINITY_H_ |
| 7 | |
| 8 | #include <stddef.h> |
| 9 | #include <stdint.h> |
| 10 | |
Etienne Pierre-doray | aff4086 | 2021-09-14 17:31:51 +0000 | [diff] [blame] | 11 | #include <deque> |
Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 12 | #include <vector> |
| 13 | |
Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 14 | #include "components/zucchini/image_utils.h" |
| 15 | |
| 16 | namespace zucchini { |
| 17 | |
| 18 | class EquivalenceMap; |
| 19 | |
| 20 | // Computes and stores affinity between old and new targets for a single target |
| 21 | // pool. This is only used during patch generation. |
| 22 | class TargetsAffinity { |
| 23 | public: |
| 24 | TargetsAffinity(); |
Samuel Huang | f137bf4 | 2021-08-13 15:42:26 +0000 | [diff] [blame] | 25 | TargetsAffinity(const TargetsAffinity&) = delete; |
| 26 | const TargetsAffinity& operator=(const TargetsAffinity&) = delete; |
Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 27 | ~TargetsAffinity(); |
| 28 | |
| 29 | // Infers affinity between |old_targets| and |new_targets| using similarities |
| 30 | // described by |equivalence_map|, and updates internal state for retrieval of |
| 31 | // affinity scores. Both |old_targets| and |new_targets| are targets in the |
| 32 | // same pool and are sorted in ascending order. |
| 33 | void InferFromSimilarities(const EquivalenceMap& equivalence_map, |
Etienne Pierre-doray | aff4086 | 2021-09-14 17:31:51 +0000 | [diff] [blame] | 34 | const std::deque<offset_t>& old_targets, |
| 35 | const std::deque<offset_t>& new_targets); |
Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 36 | |
| 37 | // Assigns labels to targets based on associations previously inferred, using |
| 38 | // |min_affinity| to reject associations with weak |affinity|. Label 0 is |
| 39 | // assigned to unassociated targets. Labels for old targets are written to |
| 40 | // |old_labels| and labels for new targets are written to |new_labels|. |
| 41 | // Returns the upper bound on assigned labels (>= 1 since 0 is used). |
| 42 | uint32_t AssignLabels(double min_affinity, |
| 43 | std::vector<uint32_t>* old_labels, |
| 44 | std::vector<uint32_t>* new_labels); |
| 45 | |
| 46 | // Returns the affinity score between targets identified by |old_key| and |
| 47 | // |new_keys|. Affinity > 0 means an association is likely, < 0 means |
| 48 | // incompatible association, and 0 means neither targets have been associated. |
| 49 | double AffinityBetween(key_t old_key, key_t new_key) const; |
| 50 | |
| 51 | private: |
| 52 | struct Association { |
| 53 | key_t other = 0; |
| 54 | double affinity = 0.0; |
| 55 | }; |
| 56 | |
| 57 | // Forward and backward associations between old and new targets. For each |
| 58 | // Association element, if |affinity == 0.0| then no association is defined |
| 59 | // (and |other| is meaningless|. Otherwise |affinity > 0.0|, and the |
| 60 | // association between |old_labels[old_key]| and |new_labels[new_key]| is |
| 61 | // represented by: |
| 62 | // forward_association_[old_key].other == new_key; |
| 63 | // backward_association_[new_key].other == old_key; |
| 64 | // forward_association_[old_key].affinity == |
| 65 | // backward_association_[new_key].affinity; |
| 66 | // The two lists contain the same information, but having both enables quick |
| 67 | // lookup, given |old_key| or |new_key|. |
| 68 | std::vector<Association> forward_association_; |
| 69 | std::vector<Association> backward_association_; |
Samuel Huang | 06f1ae9 | 2018-03-13 18:19:34 +0000 | [diff] [blame] | 70 | }; |
| 71 | |
| 72 | } // namespace zucchini |
| 73 | |
| 74 | #endif // COMPONENTS_ZUCCHINI_TARGETS_AFFINITY_H_ |