label_manager_unittest.cc 12 KB

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