courgette/label_manager_unittest.cc

   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 #include "courgette/label_manager.h"
   6
   7 #include <stddef.h>
   8 #include <stdint.h>
   9
  10 #include <iterator>
  11 #include <map>
  12 #include <set>
  13 #include <string>
  14 #include <utility>
  15 #include <vector>
  16
  17 #include "base/logging.h"
  18 #include "base/macros.h"
  19 #include "courgette/image_utils.h"
  20 #include "testing/gtest/include/gtest/gtest.h"
  21
  22 namespace courgette {
  23
  24 namespace {
  25
  26 class TestLabelManager : public LabelManager {
  27  public:
  28   void SetLabels(const LabelVector& labels) { labels_ = labels; }
  29 };
  30
  31 void CheckLabelManagerContent(LabelManager* label_manager,
  32                               const std::map<RVA, int32_t>& expected) {
  33   EXPECT_EQ(expected.size(), label_manager->Labels().size());
  34   for (const auto& rva_and_count : expected) {
  35     Label* label = label_manager->Find(rva_and_count.first);
  36     EXPECT_TRUE(label != nullptr);
  37     EXPECT_EQ(rva_and_count.first, label->rva_);
  38     EXPECT_EQ(rva_and_count.second, label->count_);
  39   }
  40 }
  41
  42 // Instantiates a LabelVector with |n| instances. The |rva_| fields are assigned
  43 // 0, ..., |n| - 1. The other fields are uninitialized.
  44 LabelVector CreateLabelVectorBasic(size_t n) {
  45   LabelVector labels;
  46   labels.reserve(n);
  47   for (size_t i = 0; i < n; ++i)
  48     labels.push_back(Label(i));
  49   return labels;
  50 }
  51
  52 // Instantiates a list of Labels, one per character |ch| in |encoded_index|.
  53 // - |rva_| is assigned 0, 1, 2, ...
  54 // - |count_| is assigned 1.
  55 // - |index_| depends on |ch|: '.' => kNoIndex, 'A' => 0, ..., 'Z' => 25.
  56 // Each letter (except '.') can appear at most once in |encoded_index|.
  57 // For example, |encoded_index| = "A.E" initializes 3 Labels:
  58 //   [{rva_: 0, count_: 1, index_: 0},
  59 //    {rva_: 1, count_: 1, index_: kNoIndex},
  60 //    {rva_: 2, count_: 1, index_: 4}].
  61 LabelVector CreateLabelVectorWithIndexes(const std::string& encoded_index) {
  62   LabelVector labels;
  63   size_t n = encoded_index.size();
  64   labels.reserve(n);
  65   std::set<char> used_ch;
  66   for (size_t i = 0; i < n; ++i) {
  67     int index = Label::kNoIndex;
  68     char ch = encoded_index[i];
  69     if (ch != '.') {
  70       // Sanity check for test case.
  71       if (ch < 'A' || ch > 'Z' || used_ch.find(ch) != used_ch.end())
  72         NOTREACHED() << "Malformed test case: " << encoded_index;
  73       used_ch.insert(ch);
  74       index = ch - 'A';
  75     }
  76     labels.push_back(Label(i, index, 1));
  77   }
  78   return labels;
  79 }
  80
  81 // Returns a string encoding for |index_| assignments for |label_| instances,
  82 // with kNoIndex => '.', 0 => 'A', ..., '25' => 'Z'. Fails if any |index_|
  83 // does not fit the above.
  84 std::string EncodeLabelIndexes(const LabelVector& labels) {
  85   std::string encoded;
  86   encoded.reserve(labels.size());
  87   for (const Label& label : labels) {
  88     if (label.index_ == Label::kNoIndex)
  89       encoded += '.';
  90     else if (label.index_ >= 0 && label.index_ <= 'Z' - 'A')
  91       encoded += static_cast<char>(label.index_ + 'A');
  92     else
  93       NOTREACHED();
  94   }
  95   return encoded;
  96 }
  97
  98 }  // namespace
  99
 100 TEST(LabelManagerTest, GetLabelIndexBound) {
 101   LabelVector labels0;
 102   EXPECT_EQ(0, LabelManager::GetLabelIndexBound(labels0));
 103
 104   LabelVector labels1_uninit = CreateLabelVectorBasic(1);
 105   ASSERT_EQ(1U, labels1_uninit.size());
 106   EXPECT_EQ(0, LabelManager::GetLabelIndexBound(labels1_uninit));
 107
 108   LabelVector labels1_init = CreateLabelVectorBasic(1);
 109   ASSERT_EQ(1U, labels1_init.size());
 110   labels1_init[0].index_ = 99;
 111   EXPECT_EQ(100, LabelManager::GetLabelIndexBound(labels1_init));
 112
 113   LabelVector labels6_mixed = CreateLabelVectorBasic(6);
 114   ASSERT_EQ(6U, labels6_mixed.size());
 115   labels6_mixed[1].index_ = 5;
 116   labels6_mixed[2].index_ = 2;
 117   labels6_mixed[4].index_ = 15;
 118   labels6_mixed[5].index_ = 7;
 119   EXPECT_EQ(16, LabelManager::GetLabelIndexBound(labels6_mixed));
 120 }
 121
 122 TEST(LabelManagerTest, Basic) {
 123   static const RVA kTestTargetsRaw[] = {
 124     0x04000010,
 125     0x04000030,
 126     0x04000020,
 127     0x04000010,  // Redundant.
 128     0xFEEDF00D,
 129     0x04000030,  // Redundant.
 130     0xFEEDF00D,  // Redundant.
 131     0x00000110,
 132     0x04000010,  // Redundant.
 133     0xABCD1234
 134   };
 135   std::vector<RVA> test_targets(std::begin(kTestTargetsRaw),
 136                                 std::end(kTestTargetsRaw));
 137   TrivialRvaVisitor visitor(test_targets);
 138
 139   // Preallocate targets, then populate.
 140   TestLabelManager label_manager;
 141   label_manager.Read(&visitor);
 142
 143   static const std::pair<RVA, int32_t> kExpected1Raw[] = {
 144       {0x00000110, 1}, {0x04000010, 3}, {0x04000020, 1},
 145       {0x04000030, 2}, {0xABCD1234, 1}, {0xFEEDF00D, 2}};
 146   std::map<RVA, int32_t> expected1(std::begin(kExpected1Raw),
 147                                    std::end(kExpected1Raw));
 148
 149   CheckLabelManagerContent(&label_manager, expected1);
 150
 151   // Expect to *not* find labels for various RVAs that were never added.
 152   EXPECT_EQ(nullptr, label_manager.Find(RVA(0x00000000)));
 153   EXPECT_EQ(nullptr, label_manager.Find(RVA(0x0400000F)));
 154   EXPECT_EQ(nullptr, label_manager.Find(RVA(0x04000011)));
 155   EXPECT_EQ(nullptr, label_manager.Find(RVA(0x5F3759DF)));
 156   EXPECT_EQ(nullptr, label_manager.Find(RVA(0xFEEDFFF0)));
 157   EXPECT_EQ(nullptr, label_manager.Find(RVA(0xFFFFFFFF)));
 158
 159   // Remove Labels with |count_| < 2.
 160   label_manager.RemoveUnderusedLabels(2);
 161   static const std::pair<RVA, int32_t> kExpected2Raw[] = {
 162       {0x04000010, 3}, {0x04000030, 2}, {0xFEEDF00D, 2}};
 163   std::map<RVA, int32_t> expected2(std::begin(kExpected2Raw),
 164                                    std::end(kExpected2Raw));
 165   CheckLabelManagerContent(&label_manager, expected2);
 166 }
 167
 168 TEST(LabelManagerTest, Single) {
 169   const RVA kRva = 12U;
 170   for (int dup = 1; dup < 8; ++dup) {
 171     // Test data: |dup| copies of kRva.
 172     std::vector<RVA> test_targets(dup, kRva);
 173     TrivialRvaVisitor visitor(test_targets);
 174     TestLabelManager label_manager;
 175     label_manager.Read(&visitor);
 176     EXPECT_EQ(1U, label_manager.Labels().size());  // Deduped to 1 Label.
 177
 178     Label* label = label_manager.Find(kRva);
 179     EXPECT_NE(nullptr, label);
 180     EXPECT_EQ(kRva, label->rva_);
 181     EXPECT_EQ(dup, label->count_);
 182
 183     for (RVA rva = 0U; rva < 16U; ++rva) {
 184       if (rva != kRva)
 185         EXPECT_EQ(nullptr, label_manager.Find(rva));
 186     }
 187   }
 188 }
 189
 190 TEST(LabelManagerTest, Empty) {
 191   std::vector<RVA> empty_test_targets;
 192   TrivialRvaVisitor visitor(empty_test_targets);
 193   TestLabelManager label_manager;
 194   label_manager.Read(&visitor);
 195   EXPECT_EQ(0U, label_manager.Labels().size());
 196   for (RVA rva = 0U; rva < 16U; ++rva)
 197     EXPECT_EQ(nullptr, label_manager.Find(rva));
 198 }
 199
 200 TEST(LabelManagerTest, EmptyAssign) {
 201   TestLabelManager label_manager_empty;
 202   label_manager_empty.DefaultAssignIndexes();
 203   label_manager_empty.UnassignIndexes();
 204   label_manager_empty.AssignRemainingIndexes();
 205 }
 206
 207 TEST(LabelManagerTest, TrivialAssign) {
 208   for (size_t size = 0; size < 20; ++size) {
 209     TestLabelManager label_manager;
 210     label_manager.SetLabels(CreateLabelVectorBasic(size));
 211
 212     // Sanity check.
 213     for (size_t i = 0; i < size; ++i)
 214       EXPECT_EQ(Label::kNoIndex, label_manager.Labels()[i].index_);
 215
 216     // Default assign.
 217     label_manager.DefaultAssignIndexes();
 218     for (size_t i = 0; i < size; ++i)
 219       EXPECT_EQ(static_cast<int>(i), label_manager.Labels()[i].index_);
 220
 221     // Heuristic assign, but since everything's assigned, so no change.
 222     label_manager.AssignRemainingIndexes();
 223     for (size_t i = 0; i < size; ++i)
 224       EXPECT_EQ(static_cast<int>(i), label_manager.Labels()[i].index_);
 225
 226     // Unassign.
 227     label_manager.UnassignIndexes();
 228     for (size_t i = 0; i < size; ++i)
 229       EXPECT_EQ(Label::kNoIndex, label_manager.Labels()[i].index_);
 230   }
 231 }
 232
 233 // Tests SimpleIndexAssigner fill strategies independently.
 234 TEST(LabelManagerTest, SimpleIndexAssigner) {
 235   using SimpleIndexAssigner = LabelManager::SimpleIndexAssigner;
 236   // See CreateLabelVectorWithIndexes() explanation on how we encode LabelVector
 237   // |index_| values as a string.
 238   const struct TestCase {
 239     const char* input;
 240     const char* expect_forward;
 241     const char* expect_backward;
 242     const char* expect_in;
 243   } kTestCases[] = {
 244     {"", "", "", ""},
 245     {".", "A", "A", "A"},
 246     {"....", "ABCD", "ABCD", "ABCD"},
 247     {"A...", "ABCD", "ABCD", "ABCD"},
 248     {".A..", ".ABC", ".ACD", "BACD"},
 249     {"...A", "...A", "...A", "BCDA"},
 250     {"C...", "CD.A", "C..D", "CABD"},
 251     {".C..", "ACD.", "BC.D", "ACBD"},
 252     {"...C", "AB.C", ".ABC", "ABDC"},
 253     {"D...", "D.AB", "D...", "DABC"},
 254     {".D..", "AD..", "CD..", "ADBC"},
 255     {"...D", "ABCD", "ABCD", "ABCD"},
 256     {"Z...", "Z.AB", "Z...", "ZABC"},
 257     {".Z..", "AZ..", "YZ..", "AZBC"},
 258     {"...Z", "ABCZ", "WXYZ", "ABCZ"},
 259     {"..AZ..", "..AZ..", "..AZ..", "BCAZDE"},
 260     {"..ZA..", "..ZABC", "XYZA..", "BCZADE"},
 261     {"A....Z", "ABCDEZ", "AVWXYZ", "ABCDEZ"},
 262     {"Z....A", "Z....A", "Z....A", "ZBCDEA"},
 263     {"..CD..", "ABCDEF", "ABCDEF", "ABCDEF"},
 264     {"..DC..", "ABDC..", "..DCEF", "ABDCEF"},
 265     {"..MN..", "ABMN..", "KLMN..", "ABMNCD"},
 266     {"..NM..", "ABNM..", "..NM..", "ABNMCD"},
 267     {".B.D.F.", "ABCDEFG", "ABCDEFG", "ABCDEFG"},
 268     {".D.G.J.", "ADEGHJ.", "CDFGIJ.", "ADBGCJE"},
 269     {".D.Z.J.", "ADEZ.JK", "CDYZIJ.", "ADBZCJE"},
 270     {".B..E..", "ABCDEFG", "ABCDEFG", "ABCDEFG"},
 271     {".B..D..", "ABC.DEF", "AB.CDFG", "ABCEDFG"},
 272   };
 273   const int kNumFuns = 3;
 274   // TestCase member variable pointers to enable iteration.
 275   const char* TestCase::*expect_ptr[kNumFuns] = {
 276     &TestCase::expect_forward,
 277     &TestCase::expect_backward,
 278     &TestCase::expect_in
 279   };
 280   // SimpleIndexAssigner member function pointers to enable iteration.
 281   void (SimpleIndexAssigner::*fun_ptrs[kNumFuns])() = {
 282     &SimpleIndexAssigner::DoForwardFill,
 283     &SimpleIndexAssigner::DoBackwardFill,
 284     &SimpleIndexAssigner::DoInFill
 285   };
 286   for (const auto& test_case : kTestCases) {
 287     // Loop over {forward fill, backward fill, infill}.
 288     for (int i = 0; i < kNumFuns; ++i) {
 289       std::string expect = test_case.*(expect_ptr[i]);
 290       LabelVector labels = CreateLabelVectorWithIndexes(test_case.input);
 291       SimpleIndexAssigner assigner(&labels);
 292       (assigner.*(fun_ptrs[i]))();
 293       std::string result = EncodeLabelIndexes(labels);
 294       EXPECT_EQ(expect, result);
 295     }
 296   }
 297 }
 298
 299 // Tests integrated AssignRemainingIndexes().
 300 TEST(LabelManagerTest, AssignRemainingIndexes) {
 301   const struct {
 302     const char* input;
 303     const char* expect;
 304   } kTestCases[] = {
 305     // Trivial.
 306     {"", ""},
 307     {"M", "M"},
 308     {"ABCDEFG", "ABCDEFG"},
 309     {"THEQUICKBROWNFXJMPSVLAZYDG", "THEQUICKBROWNFXJMPSVLAZYDG"},
 310     // Forward fill only.
 311     {".", "A"},
 312     {".......", "ABCDEFG"},
 313     {"....E..", "ABCDEFG"},  // "E" is at right place.
 314     {".D.B.H.F.", "ADEBCHIFG"},
 315     {"ZN....", "ZNOPQR"},  // "Z" exists, so 'OPQR" are defined.
 316     {"H.D...A..", "HIDEFGABC"},
 317     {"...K.DE..H..Z", "ABCKLDEFGHIJZ"},  // "Z" exists, so "L" defined.
 318     // Infill only.
 319     {"E.", "EA"},
 320     {"...A", "BCDA"},
 321     {"Z...A", "ZBCDA"},
 322     {"AN...", "ANBCD"},
 323     {"...AZ", "BCDAZ"},
 324     {"....AC", "BDEFAC"},
 325     {"ED...C...B....A", "EDFGHCIJKBLMNOA"},
 326     // Forward fill and infill.
 327     {"E..", "EBA"},  // Forward: "A"; in: "B".
 328     {"Z....", "ZDABC"},  // Forward: "ABC"; in: "D".
 329     {".E.....", "AEFGBCD"},  // Forward: "A", "FG"; in: "BCD".
 330     {"....C..", "ABFGCDE"},  // Forward: "AB", "DE"; in: "FG".
 331     {"...Z...", "ABCZDEF"},  // Forward: "ABC"; in: "DEF".
 332     {"...A...", "EFGABCD"},  // Forward: "BCD"; in: "EFG".
 333     // Backward fill only.
 334     {".CA", "BCA"},
 335     {"...ZA", "WXYZA"},
 336     {"BA...Z", "BAWXYZ"},
 337     {"ANM..Z....L...T", "ANMXYZHIJKLQRST"},
 338     {"....G..Z...LAH", "CDEFGXYZIJKLAH"},
 339     // Forward fill and backward fill.
 340     {"..ZA..", "XYZABC"},  // Forward: "BC"; backward: "XY".
 341     {".....ZD", "ABCXYZD"},  // Forward: "ABC"; backward: "XY".
 342     {"DA.....", "DABCEFG"},  // Forward: "BC"; backward: "EFG".
 343     // Backward fill and infill.
 344     {"G....DA", "GEFBCDA"},  // Backward: "BC"; in: "EF".
 345     {"..ZBA..", "XYZBACD"},  // Backward: "XY"; in: "CD".
 346     // All.
 347     {".....ZED.", "ABCXYZEDF"},  // Forward: "ABC"; backward: "XY"; in: "F".
 348     {".....GD.", "ABCHFGDE"},  // Forward: "ABC", "E"; backward: "F"; in: "H".
 349     {"..FE..GD..", "ABFECHGDIJ"}, // Forward: "AB"; backward: "IJ"; in: "CH".
 350   };
 351   for (const auto& test_case : kTestCases) {
 352     TestLabelManager label_manager;
 353     label_manager.SetLabels(CreateLabelVectorWithIndexes(test_case.input));
 354
 355     label_manager.AssignRemainingIndexes();
 356     std::string result = EncodeLabelIndexes(label_manager.Labels());
 357     EXPECT_EQ(test_case.expect, result);
 358   }
 359 }
 360
 361 }  // namespace courgette