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 11 #include <deque> 12 #include <vector> 13 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(); 25 TargetsAffinity(const TargetsAffinity&) = delete; 26 const TargetsAffinity& operator=(const TargetsAffinity&) = delete; 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, 34 const std::deque<offset_t>& old_targets, 35 const std::deque<offset_t>& new_targets); 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_; 70 }; 71 72 } // namespace zucchini 73 74 #endif // COMPONENTS_ZUCCHINI_TARGETS_AFFINITY_H_ 75