label_manager.h 4.5 KB

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