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 <vector>
12 
13 #include "base/macros.h"
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();
26 
27   // Infers affinity between |old_targets| and |new_targets| using similarities
28   // described by |equivalence_map|, and updates internal state for retrieval of
29   // affinity scores. Both |old_targets| and |new_targets| are targets in the
30   // same pool and are sorted in ascending order.
31   void InferFromSimilarities(const EquivalenceMap& equivalence_map,
32                              const std::vector<offset_t>& old_targets,
33                              const std::vector<offset_t>& new_targets);
34 
35   // Assigns labels to targets based on associations previously inferred, using
36   // |min_affinity| to reject associations with weak |affinity|. Label 0 is
37   // assigned to unassociated targets. Labels for old targets are written to
38   // |old_labels| and labels for new targets are written to |new_labels|.
39   // Returns the upper bound on assigned labels (>= 1 since 0 is used).
40   uint32_t AssignLabels(double min_affinity,
41                         std::vector<uint32_t>* old_labels,
42                         std::vector<uint32_t>* new_labels);
43 
44   // Returns the affinity score between targets identified by |old_key| and
45   // |new_keys|. Affinity > 0 means an association is likely, < 0 means
46   // incompatible association, and 0 means neither targets have been associated.
47   double AffinityBetween(key_t old_key, key_t new_key) const;
48 
49  private:
50   struct Association {
51     key_t other = 0;
52     double affinity = 0.0;
53   };
54 
55   // Forward and backward associations between old and new targets. For each
56   // Association element, if |affinity == 0.0| then no association is defined
57   // (and |other| is meaningless|. Otherwise |affinity > 0.0|, and the
58   // association between |old_labels[old_key]| and |new_labels[new_key]| is
59   // represented by:
60   //   forward_association_[old_key].other == new_key;
61   //   backward_association_[new_key].other == old_key;
62   //   forward_association_[old_key].affinity ==
63   //       backward_association_[new_key].affinity;
64   // The two lists contain the same information, but having both enables quick
65   // lookup, given |old_key| or |new_key|.
66   std::vector<Association> forward_association_;
67   std::vector<Association> backward_association_;
68 
69   DISALLOW_COPY_AND_ASSIGN(TargetsAffinity);
70 };
71 
72 }  // namespace zucchini
73 
74 #endif  // COMPONENTS_ZUCCHINI_TARGETS_AFFINITY_H_
75