1 // Copyright 2015 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
5 #ifndef COURGETTE_LABEL_MANAGER_H_
6 #define COURGETTE_LABEL_MANAGER_H_
14 #include "base/gtest_prod_util.h"
15 #include "base/memory/raw_ptr.h"
16 #include "courgette/image_utils.h"
20 using LabelVector = std::vector<Label>;
21 using RVAToLabel = std::map<RVA, Label*>;
23 // A container to store and manage Label instances, dedicated to reducing peak
24 // memory usage. To this end we preallocate Label instances in bulk, and
25 // carefully control transient memory usage when initializing Labels.
28 // A helper class to heuristically complete index assignment for a list of
29 // Labels that have partially assigned indexes.
30 // Goal: An address table compresses best when each index is associated with
31 // an address that is slightly larger than the previous index.
32 // For example, suppose we have RVAs
33 // [0x0000, 0x0070, 0x00E0, 0x0150].
34 // Consider candidate (RVA, index) assignments A and B:
35 // A: [(0x0000, 0), (0x0070, 1), (0x00E0, 2), (0x0150, 3)],
36 // B: [(0x0000, 2), (0x0070, 1), (0x00E0, 0), (0x0150, 3)].
37 // To form the address table, we first sort by indexes:
38 // A: [(0x0000, 0), (0x0070, 1), (0x00E0, 2), (0x0150, 3)],
39 // B: [(0x00E0, 0), (0x0070, 1), (0x0000, 2), (0x0150, 3)].
40 // Then we extract the RVAs for storage:
41 // A: [0x0000, 0x0070, 0x00E0, 0x0150],
42 // B: [0x00E0, 0x0070, 0x0000, 0x0150].
43 // Clearly A compresses better than B under (signed) delta encoding.
44 // In Courgette-gen, an assignment algorithm (subclass of AdjustmentMethod)
45 // creates partial and arbitrary index assignments (to attempt to match one
46 // file against another). So the sorted case (like A) won't happen in general.
47 // Our helper class fills in the missing assignments by creating runs of
48 // consecutive indexes, so once RVAs are sorted by these indexes we'd reduce
49 // distances between successive RVAs.
50 class SimpleIndexAssigner {
52 explicit SimpleIndexAssigner(LabelVector* labels);
54 SimpleIndexAssigner(const SimpleIndexAssigner&) = delete;
55 SimpleIndexAssigner& operator=(const SimpleIndexAssigner&) = delete;
57 ~SimpleIndexAssigner();
59 // Scans forward to assign successive indexes to Labels, using existing
60 // indexes as start-anchors.
63 // Scans backward to assign successive indexes to Labels, using existing
64 // indexes as end-anchors.
65 void DoBackwardFill();
67 // Assigns all unsigned indexes using what's available, disregarding current
72 // The target LabelVector, owned by the caller.
73 raw_ptr<LabelVector> labels_;
75 // A bound on indexes.
78 // Tracker for index usage to ensure uniqueness of indexes.
79 std::vector<bool> available_;
84 LabelManager(const LabelManager&) = delete;
85 LabelManager& operator=(const LabelManager&) = delete;
89 // Returns an exclusive upper bound for all assigned indexes in |labels|.
90 static int GetLabelIndexBound(const LabelVector& labels);
92 // Accessor to stored Label instances.
93 const LabelVector& Labels() const { return labels_; }
95 // Efficiently searches for a Label that targets |rva|. Returns the pointer to
96 // the stored Label instance if found, or null otherwise. Non-const to support
97 // implementations that allocate-on-read.
100 // Removes Label instances whose |count_| is less than |count_threshold|.
101 void RemoveUnderusedLabels(int32_t count_threshold);
103 // Resets all indexes to an unassigned state.
104 void UnassignIndexes();
106 // Assigns indexes to successive integers from 0, ordered by RVA.
107 void DefaultAssignIndexes();
109 // Assigns indexes to any Label instances that don't have one yet.
110 void AssignRemainingIndexes();
112 // Populates |labels_| using RVAs from |rva_visitor|. Each distinct RVA from
113 // |rva_visitor| yields a Label with |rva_| assigned as the RVA, and |count_|
114 // assigned as the repeat.
115 void Read(RvaVisitor* rva_visitor);
118 FRIEND_TEST_ALL_PREFIXES(LabelManagerTest, TrivialAssign);
119 FRIEND_TEST_ALL_PREFIXES(LabelManagerTest, AssignRemainingIndexes);
121 // The main list of Label instances, sorted by the |rva_| member.
125 } // namespace courgette
127 #endif // COURGETTE_LABEL_MANAGER_H_