courgette/label_manager.h

   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
   5 #ifndef COURGETTE_LABEL_MANAGER_H_
   6 #define COURGETTE_LABEL_MANAGER_H_
   7
   8 #include <stddef.h>
   9 #include <stdint.h>
  10
  11 #include <map>
  12 #include <vector>
  13
  14 #include "base/gtest_prod_util.h"
  15 #include "base/macros.h"
  16 #include "courgette/image_utils.h"
  17
  18 namespace courgette {
  19
  20 using LabelVector = std::vector<Label>;
  21 using RVAToLabel = std::map<RVA, Label*>;
  22
  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.
  26 class LabelManager {
  27  public:
  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 {
  51    public:
  52     explicit SimpleIndexAssigner(LabelVector* labels);
  53     ~SimpleIndexAssigner();
  54
  55     // Scans forward to assign successive indexes to Labels, using existing
  56     // indexes as start-anchors.
  57     void DoForwardFill();
  58
  59     // Scans backward to assign successive indexes to Labels, using existing
  60     // indexes as end-anchors.
  61     void DoBackwardFill();
  62
  63     // Assigns all unsigned indexes using what's available, disregarding current
  64     // Label assignment.
  65     void DoInFill();
  66
  67    private:
  68     // The target LabelVector, owned by the caller.
  69     LabelVector* labels_;
  70
  71     // A bound on indexes.
  72     int num_index_ = 0;
  73
  74     // Tracker for index usage to ensure uniqueness of indexes.
  75     std::vector<bool> available_;
  76
  77     DISALLOW_COPY_AND_ASSIGN(SimpleIndexAssigner);
  78   };
  79
  80   LabelManager();
  81   ~LabelManager();
  82
  83   // Returns an exclusive upper bound for all assigned indexes in |labels|.
  84   static int GetLabelIndexBound(const LabelVector& labels);
  85
  86   // Accessor to stored Label instances.
  87   const LabelVector& Labels() const { return labels_; }
  88
  89   // Efficiently searches for a Label that targets |rva|. Returns the pointer to
  90   // the stored Label instance if found, or null otherwise. Non-const to support
  91   // implementations that allocate-on-read.
  92   Label* Find(RVA rva);
  93
  94   // Removes Label instances whose |count_| is less than |count_threshold|.
  95   void RemoveUnderusedLabels(int32_t count_threshold);
  96
  97   // Resets all indexes to an unassigned state.
  98   void UnassignIndexes();
  99
 100   // Assigns indexes to successive integers from 0, ordered by RVA.
 101   void DefaultAssignIndexes();
 102
 103   // Assigns indexes to any Label instances that don't have one yet.
 104   void AssignRemainingIndexes();
 105
 106   // Populates |labels_| using RVAs from |rva_visitor|. Each distinct RVA from
 107   // |rva_visitor| yields a Label with |rva_| assigned as the RVA, and |count_|
 108   // assigned as the repeat.
 109   void Read(RvaVisitor* rva_visitor);
 110
 111  protected:
 112   FRIEND_TEST_ALL_PREFIXES(LabelManagerTest, TrivialAssign);
 113   FRIEND_TEST_ALL_PREFIXES(LabelManagerTest, AssignRemainingIndexes);
 114
 115   // The main list of Label instances, sorted by the |rva_| member.
 116   LabelVector labels_;
 117
 118  private:
 119   DISALLOW_COPY_AND_ASSIGN(LabelManager);
 120 };
 121
 122 }  // namespace courgette
 123
 124 #endif  // COURGETTE_LABEL_MANAGER_H_