address_translator_unittest.cc 23 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586
  1. // Copyright 2017 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 "components/zucchini/address_translator.h"
  5. #include <algorithm>
  6. #include <string>
  7. #include <utility>
  8. #include "base/format_macros.h"
  9. #include "base/strings/stringprintf.h"
  10. #include "testing/gtest/include/gtest/gtest.h"
  11. namespace zucchini {
  12. namespace {
  13. // Test case structs. The convention of EXPECT() specifies "expectd" value
  14. // before ""actual". However, AddressTranslator interfaces explicitly state "X
  15. // to Y". So it is clearer in test cases to specify "input" before "expect".
  16. struct OffsetToRvaTestCase {
  17. offset_t input;
  18. rva_t expect;
  19. };
  20. struct RvaToOffsetTestCase {
  21. rva_t input;
  22. offset_t expect;
  23. };
  24. class TestAddressTranslator : public AddressTranslator {
  25. public:
  26. using AddressTranslator::AddressTranslator;
  27. // Initialize() alternative that parses a visual representation of offset and
  28. // RVA ranges. Illustrative example ("special" means '.' or '!'):
  29. // "..AAA...|....aaaa" => "..AAA..." for offsets, and "....aaaa" for RVAs:
  30. // - "..AAA...": First non-period character is at 2, so |offset_begin| = 2.
  31. // - "..AAA...": There are 3 non-special characters, so |offset_size| = +3.
  32. // - "....aaaa": First non-period character is at 4, so |rva_begin| = 4.
  33. // - "....aaaa": There are 4 non-special characters, so |rva_size| = +4.
  34. // For the special case of length-0 range, '!' can be used. For example,
  35. // "...!...." specifies |begin| = 3 and |size| = +0.
  36. AddressTranslator::Status InitializeWithStrings(
  37. const std::vector<std::string>& specs) {
  38. std::vector<Unit> units;
  39. units.reserve(specs.size());
  40. for (const std::string& s : specs) {
  41. size_t sep = s.find('|');
  42. CHECK_NE(sep, std::string::npos);
  43. std::string s1 = s.substr(0, sep);
  44. std::string s2 = s.substr(sep + 1);
  45. auto first_non_blank = [](const std::string& t) {
  46. auto is_blank = [](char ch) { return ch == '.'; };
  47. return std::find_if_not(t.begin(), t.end(), is_blank) - t.begin();
  48. };
  49. auto count_non_special = [](const std::string& t) {
  50. auto is_special = [](char ch) { return ch == '.' || ch == '!'; };
  51. return t.size() - std::count_if(t.begin(), t.end(), is_special);
  52. };
  53. units.push_back({static_cast<offset_t>(first_non_blank(s1)),
  54. static_cast<offset_t>(count_non_special(s1)),
  55. static_cast<rva_t>(first_non_blank(s2)),
  56. static_cast<rva_t>(count_non_special(s2))});
  57. }
  58. return Initialize(std::move(units));
  59. }
  60. };
  61. // Simple test: Initialize TestAddressTranslator using |specs|, and match
  62. // |expected| results re. success or failure.
  63. void SimpleTest(const std::vector<std::string>& specs,
  64. AddressTranslator::Status expected,
  65. const std::string& case_name) {
  66. TestAddressTranslator translator;
  67. auto result = translator.InitializeWithStrings(specs);
  68. EXPECT_EQ(expected, result) << case_name;
  69. }
  70. // Test AddressTranslator::Initialize's Unit overlap and error checks over
  71. // multiple test cases, each case consists of a fixed unit (specified as
  72. // string), and a variable string taken from an list.
  73. class TwoUnitOverlapTester {
  74. public:
  75. struct TestCase {
  76. std::string unit_str;
  77. AddressTranslator::Status expected;
  78. };
  79. static void RunTest(const std::string& unit_str1,
  80. const std::vector<TestCase>& test_cases) {
  81. for (size_t i = 0; i < test_cases.size(); ++i) {
  82. const auto& test_case = test_cases[i];
  83. const std::string& unit_str2 = test_case.unit_str;
  84. const std::string str =
  85. base::StringPrintf("Case #%" PRIuS ": %s", i, unit_str2.c_str());
  86. SimpleTest({unit_str1, unit_str2}, test_case.expected, str);
  87. // Switch order. Expect same results.
  88. SimpleTest({unit_str2, unit_str1}, test_case.expected, str);
  89. }
  90. }
  91. };
  92. } // namespace
  93. TEST(AddressTranslatorTest, Empty) {
  94. using AT = AddressTranslator;
  95. TestAddressTranslator translator;
  96. EXPECT_EQ(AT::kSuccess,
  97. translator.Initialize(std::vector<AddressTranslator::Unit>()));
  98. offset_t fake_offset_begin = translator.fake_offset_begin();
  99. // Optimized versions.
  100. AddressTranslator::OffsetToRvaCache offset_to_rva(translator);
  101. AddressTranslator::RvaToOffsetCache rva_to_offset(translator);
  102. EXPECT_EQ(kInvalidRva, translator.OffsetToRva(0U));
  103. EXPECT_EQ(kInvalidRva, translator.OffsetToRva(100U));
  104. EXPECT_EQ(kInvalidRva, offset_to_rva.Convert(0U));
  105. EXPECT_EQ(kInvalidRva, offset_to_rva.Convert(100U));
  106. EXPECT_EQ(kInvalidOffset, translator.RvaToOffset(0U));
  107. EXPECT_EQ(kInvalidOffset, translator.RvaToOffset(100U));
  108. EXPECT_EQ(kInvalidOffset, rva_to_offset.Convert(0U));
  109. EXPECT_EQ(kInvalidOffset, rva_to_offset.Convert(100U));
  110. EXPECT_EQ(kInvalidRva, translator.OffsetToRva(fake_offset_begin));
  111. EXPECT_EQ(kInvalidRva, offset_to_rva.Convert(fake_offset_begin));
  112. }
  113. TEST(AddressTranslatorTest, Single) {
  114. using AT = AddressTranslator;
  115. TestAddressTranslator translator;
  116. // Offsets to RVA: [10, 30) -> [100, 120).
  117. EXPECT_EQ(AT::kSuccess, translator.Initialize({{10U, +20U, 100U, +20U}}));
  118. offset_t fake_offset_begin = translator.fake_offset_begin();
  119. // Optimized versions.
  120. AddressTranslator::OffsetToRvaCache offset_to_rva(translator);
  121. AddressTranslator::RvaToOffsetCache rva_to_offset(translator);
  122. EXPECT_EQ(30U, fake_offset_begin); // Test implementation detail.
  123. // Offsets to RVAs.
  124. OffsetToRvaTestCase test_cases1[] = {
  125. {0U, kInvalidRva}, {9U, kInvalidRva}, {10U, 100U},
  126. {20U, 110U}, {29U, 119U}, {30U, kInvalidRva},
  127. };
  128. for (auto& test_case : test_cases1) {
  129. EXPECT_EQ(test_case.expect, translator.OffsetToRva(test_case.input));
  130. EXPECT_EQ(test_case.expect, offset_to_rva.Convert(test_case.input));
  131. }
  132. // RVAs to offsets.
  133. RvaToOffsetTestCase test_cases2[] = {
  134. {0U, kInvalidOffset}, {99U, kInvalidOffset}, {100U, 10U},
  135. {110U, 20U}, {119U, 29U}, {120U, kInvalidOffset},
  136. };
  137. for (auto& test_case : test_cases2) {
  138. EXPECT_EQ(test_case.expect, translator.RvaToOffset(test_case.input));
  139. EXPECT_EQ(test_case.expect, rva_to_offset.Convert(test_case.input));
  140. }
  141. }
  142. TEST(AddressTranslatorTest, SingleDanglingRva) {
  143. using AT = AddressTranslator;
  144. TestAddressTranslator translator;
  145. // Offsets to RVA: [10, 30) -> [100, 120 + 7), so has dangling RVAs.
  146. EXPECT_EQ(AT::kSuccess,
  147. translator.Initialize({{10U, +20U, 100U, +20U + 7U}}));
  148. offset_t fake_offset_begin = translator.fake_offset_begin();
  149. EXPECT_EQ(30U, fake_offset_begin); // Test implementation detail.
  150. // Optimized versions.
  151. AddressTranslator::OffsetToRvaCache offset_to_rva(translator);
  152. AddressTranslator::RvaToOffsetCache rva_to_offset(translator);
  153. // Offsets to RVAs.
  154. OffsetToRvaTestCase test_cases1[] = {
  155. {0U, kInvalidRva},
  156. {9U, kInvalidRva},
  157. {10U, 100U},
  158. {20U, 110U},
  159. {29U, 119U},
  160. {30U, kInvalidRva},
  161. // Fake offsets to dangling RVAs.
  162. {fake_offset_begin + 100U, kInvalidRva},
  163. {fake_offset_begin + 119U, kInvalidRva},
  164. {fake_offset_begin + 120U, 120U},
  165. {fake_offset_begin + 126U, 126U},
  166. {fake_offset_begin + 127U, kInvalidRva},
  167. };
  168. for (auto& test_case : test_cases1) {
  169. EXPECT_EQ(test_case.expect, translator.OffsetToRva(test_case.input));
  170. EXPECT_EQ(test_case.expect, offset_to_rva.Convert(test_case.input));
  171. }
  172. // RVAs to offsets.
  173. RvaToOffsetTestCase test_cases2[] = {
  174. {0U, kInvalidOffset},
  175. {99U, kInvalidOffset},
  176. {100U, 10U},
  177. {110U, 20U},
  178. {119U, 29U},
  179. // Dangling RVAs to fake offsets.
  180. {120U, fake_offset_begin + 120U},
  181. {126U, fake_offset_begin + 126U},
  182. {127U, kInvalidOffset},
  183. };
  184. for (auto& test_case : test_cases2) {
  185. EXPECT_EQ(test_case.expect, translator.RvaToOffset(test_case.input));
  186. EXPECT_EQ(test_case.expect, rva_to_offset.Convert(test_case.input));
  187. }
  188. }
  189. TEST(AddressTranslatorTest, BasicUsage) {
  190. using AT = AddressTranslator;
  191. TestAddressTranslator translator;
  192. // Offsets covered: [10, 30), [40, 70), [70, 110).
  193. // Map to RVAs: [200, 220 + 5), [300, 330), [100, 140), so has dangling RVAs.
  194. auto result = translator.Initialize({
  195. {10U, +20U, 200U, +20U + 5U}, // Has dangling RVAs.
  196. {40U, +30U, 300U, +20U}, // Extra offset truncated and ignored.
  197. {50U, +20U, 310U, +20U}, // Overlap with previous: Merged.
  198. {70U, +40U, 100U, +20U}, // Tangent with previous but inconsistent; extra
  199. // offset truncated and ignored.
  200. {90U, +20U, 120U, +20U}, // Tangent with previous and consistent: Merged.
  201. });
  202. EXPECT_EQ(AT::kSuccess, result);
  203. offset_t fake_offset_begin = translator.fake_offset_begin();
  204. EXPECT_EQ(110U, fake_offset_begin); // Test implementation detail.
  205. // Optimized versions.
  206. AddressTranslator::OffsetToRvaCache offset_to_rva(translator);
  207. AddressTranslator::RvaToOffsetCache rva_to_offset(translator);
  208. // Offsets to RVAs.
  209. OffsetToRvaTestCase test_cases1[] = {
  210. {0U, kInvalidRva},
  211. {9U, kInvalidRva},
  212. {10U, 200U},
  213. {20U, 210U},
  214. {29U, 219U},
  215. {30U, kInvalidRva},
  216. {39U, kInvalidRva},
  217. {40U, 300U},
  218. {55U, 315U},
  219. {69U, 329U},
  220. {70U, 100U},
  221. {90U, 120U},
  222. {109U, 139U},
  223. {110U, kInvalidRva},
  224. // Fake offsets to dangling RVAs.
  225. {fake_offset_begin + 220U, 220U},
  226. {fake_offset_begin + 224U, 224U},
  227. {fake_offset_begin + 225U, kInvalidRva},
  228. };
  229. for (auto& test_case : test_cases1) {
  230. EXPECT_EQ(test_case.expect, translator.OffsetToRva(test_case.input));
  231. EXPECT_EQ(test_case.expect, offset_to_rva.Convert(test_case.input));
  232. }
  233. // RVAs to offsets.
  234. RvaToOffsetTestCase test_cases2[] = {
  235. {0U, kInvalidOffset},
  236. {99U, kInvalidOffset},
  237. {100U, 70U},
  238. {120U, 90U},
  239. {139U, 109U},
  240. {140U, kInvalidOffset},
  241. {199U, kInvalidOffset},
  242. {200U, 10U},
  243. {210U, 20U},
  244. {219U, 29U},
  245. {225U, kInvalidOffset},
  246. {299U, kInvalidOffset},
  247. {300U, 40U},
  248. {315U, 55U},
  249. {329U, 69U},
  250. {330U, kInvalidOffset},
  251. // Dangling RVAs to fake offsets.
  252. {220U, fake_offset_begin + 220U},
  253. {224U, fake_offset_begin + 224U},
  254. {225U, kInvalidOffset},
  255. };
  256. for (auto& test_case : test_cases2) {
  257. EXPECT_EQ(test_case.expect, translator.RvaToOffset(test_case.input));
  258. EXPECT_EQ(test_case.expect, rva_to_offset.Convert(test_case.input));
  259. }
  260. }
  261. TEST(AddressTranslatorTest, Overflow) {
  262. using AT = AddressTranslator;
  263. // Test assumes that offset_t and rva_t to be 32-bit.
  264. static_assert(sizeof(offset_t) == 4 && sizeof(rva_t) == 4,
  265. "Needs to update test.");
  266. {
  267. AddressTranslator translator1;
  268. EXPECT_EQ(AT::kErrorOverflow,
  269. translator1.Initialize({{0, +0xC0000000U, 0, +0xC0000000U}}));
  270. }
  271. {
  272. AddressTranslator translator2;
  273. EXPECT_EQ(AT::kErrorOverflow,
  274. translator2.Initialize({{0, +0, 0, +0xC0000000U}}));
  275. }
  276. {
  277. // Units are okay, owing to but limitations of the heuristic to convert
  278. // dangling RVA to fake offset, AddressTranslator::Initialize() fails.
  279. AddressTranslator translator3;
  280. EXPECT_EQ(AT::kErrorFakeOffsetBeginTooLarge,
  281. translator3.Initialize(
  282. {{32, +0, 32, +0x50000000U}, {0x50000000U, +16, 0, +16}}));
  283. }
  284. }
  285. // Sanity test for TestAddressTranslator::InitializeWithStrings();
  286. TEST(AddressTranslatorTest, AddUnitAsString) {
  287. using AT = AddressTranslator;
  288. {
  289. TestAddressTranslator translator1;
  290. EXPECT_EQ(AT::kSuccess, translator1.InitializeWithStrings({"..A..|.aaa."}));
  291. AddressTranslator::Unit unit1 = translator1.units_sorted_by_offset()[0];
  292. EXPECT_EQ(2U, unit1.offset_begin);
  293. EXPECT_EQ(+1U, unit1.offset_size);
  294. EXPECT_EQ(1U, unit1.rva_begin);
  295. EXPECT_EQ(+3U, unit1.rva_size);
  296. }
  297. {
  298. TestAddressTranslator translator2;
  299. EXPECT_EQ(AT::kSuccess,
  300. translator2.InitializeWithStrings({".....!...|.bbbbbb..."}));
  301. AddressTranslator::Unit unit2 = translator2.units_sorted_by_offset()[0];
  302. EXPECT_EQ(5U, unit2.offset_begin);
  303. EXPECT_EQ(+0U, unit2.offset_size);
  304. EXPECT_EQ(1U, unit2.rva_begin);
  305. EXPECT_EQ(+6U, unit2.rva_size);
  306. }
  307. }
  308. // AddressTranslator::Initialize() lists Unit merging examples in comments. The
  309. // format is different from that used by InitializeWithStrings(), but adapting
  310. // them is easy, so we may as well do so.
  311. TEST(AddressTranslatorTest, OverlapFromComment) {
  312. using AT = AddressTranslator;
  313. constexpr auto OK = AT::kSuccess;
  314. struct {
  315. const char* rva_str; // RVA comes first in this case.
  316. const char* offset_str;
  317. AT::Status expected;
  318. } test_cases[] = {
  319. {"..ssssffff..", "..SSSSFFFF..", OK},
  320. {"..ssssffff..", "..SSSS..FFFF..", OK},
  321. {"..ssssffff..", "..FFFF..SSSS..", OK},
  322. {"..ssssffff..", "..SSOOFF..", AT::kErrorBadOverlap},
  323. {"..sssooofff..", "..SSSOOOFFF..", OK},
  324. {"..sssooofff..", "..SSSSSOFFFFF..", AT::kErrorBadOverlap},
  325. {"..sssooofff..", "..FFOOOOSS..", AT::kErrorBadOverlap},
  326. {"..sssooofff..", "..SSSOOOF..", OK},
  327. {"..sssooofff..", "..SSSOOOF..", OK},
  328. {"..sssooosss..", "..SSSOOOS..", OK},
  329. {"..sssooofff..", "..SSSOO..", OK},
  330. {"..sssooofff..", "..SSSOFFF..", AT::kErrorBadOverlapDanglingRva},
  331. {"..sssooosss..", "..SSSOOSSSS..", AT::kErrorBadOverlapDanglingRva},
  332. {"..oooooo..", "..OOO..", OK},
  333. };
  334. auto to_period = [](std::string s, char ch) { // |s| passed by value.
  335. std::replace(s.begin(), s.end(), ch, '.');
  336. return s;
  337. };
  338. size_t idx = 0;
  339. for (const auto& test_case : test_cases) {
  340. std::string base_str =
  341. std::string(test_case.offset_str) + "|" + test_case.rva_str;
  342. std::string unit_str1 = to_period(to_period(base_str, 'S'), 's');
  343. std::string unit_str2 = to_period(to_period(base_str, 'F'), 'f');
  344. SimpleTest({unit_str1, unit_str2}, test_case.expected,
  345. base::StringPrintf("Case #%" PRIuS, idx));
  346. ++idx;
  347. }
  348. }
  349. TEST(AddressTranslatorTest, Overlap) {
  350. using AT = AddressTranslator;
  351. constexpr auto OK = AT::kSuccess;
  352. constexpr const char* unit_str1 = "....AAA.......|.....aaa......";
  353. std::vector<TwoUnitOverlapTester::TestCase> test_cases = {
  354. //....AAA.......|.....aaa...... The first Unit. NOLINT
  355. {"....BBB.......|.....bbb......", OK},
  356. {"..BBB.........|...bbb........", OK},
  357. {"......BBB.....|.......bbb....", OK},
  358. {"..BBBBBBBBB...|...bbb........", OK}, // Extra offset get truncated.
  359. {"......BBBBBBBB|.......bbb....", OK},
  360. {"....BBB.......|.......bbb....", AT::kErrorBadOverlap},
  361. {"..BBB.........|.......bbb....", AT::kErrorBadOverlap},
  362. {".......BBB....|.......bbb....", AT::kErrorBadOverlap},
  363. //....AAA.......|.....aaa...... The first Unit. NOLINT
  364. {"....BBB.......|..........bbb.", AT::kErrorBadOverlap},
  365. {"..........BBB.|.......bbb....", AT::kErrorBadOverlap},
  366. {"......BBB.....|.....bbb......", AT::kErrorBadOverlap},
  367. {"......BBB.....|..bbb.........", AT::kErrorBadOverlap},
  368. {"......BBB.....|bbb...........", AT::kErrorBadOverlap},
  369. {"BBB...........|bbb...........", OK}, // Disjoint.
  370. {"........BBB...|.........bbb..", OK}, // Disjoint.
  371. {"BBB...........|..........bbb.", OK}, // Disjoint, offset elsewhere.
  372. //....AAA.......|.....aaa...... The first Unit. NOLINT
  373. {".BBB..........|..bbb.........", OK}, // Tangent.
  374. {".......BBB....|........bbb...", OK}, // Tangent.
  375. {".BBB..........|........bbb...", OK}, // Tangent, offset elsewhere.
  376. {"BBBBBB........|bbb...........", OK}, // Repeat, with extra offsets.
  377. {"........BBBB..|.........bbb..", OK},
  378. {"BBBBBB........|..........bbb.", OK},
  379. {".BBBBBB.......|..bbb.........", OK},
  380. {".......BBBBB..|........bbb...", OK},
  381. //....AAA.......|.....aaa...... The first Unit. NOLINT
  382. {".BBB..........|........bbb...", OK}, // Tangent, offset elsewhere.
  383. {"..BBB.........|........bbb...", AT::kErrorBadOverlap},
  384. {"...BB.........|....bb........", OK},
  385. {"....BB........|.....bb.......", OK},
  386. {".......BB.....|........bb....", OK},
  387. {"...BBBBBB.....|....bbbbbb....", OK},
  388. {"..BBBBBB......|...bbbbbb.....", OK},
  389. {"......BBBBBB..|.......bbbbbb.", OK},
  390. //....AAA.......|.....aaa...... The first Unit. NOLINT
  391. {"BBBBBBBBBBBBBB|bbbbbbbbbbbbbb", AT::kErrorBadOverlap},
  392. {"B.............|b.............", OK},
  393. {"B.............|.............b", OK},
  394. {"....B.........|.....b........", OK},
  395. {"....B.........|......b.......", AT::kErrorBadOverlap},
  396. {"....B.........|......b.......", AT::kErrorBadOverlap},
  397. {"....BBB.......|.....bb.......", OK},
  398. {"....BBBB......|.....bbb......", OK},
  399. //....AAA.......|.....aaa...... The first Unit. NOLINT
  400. {".........BBBBB|.b............", OK},
  401. {"....AAA.......|.....!........", OK},
  402. {"....!.........|.....!........", OK}, // Empty units gets deleted early.
  403. {"....!.........|..........!...", OK}, // Forgiving!
  404. };
  405. TwoUnitOverlapTester::RunTest(unit_str1, test_cases);
  406. }
  407. TEST(AddressTranslatorTest, OverlapOffsetMultiple) {
  408. using AT = AddressTranslator;
  409. // Simple case. Note that RVA ranges don't get merged.
  410. SimpleTest({"A..|a....", //
  411. ".A.|..a..", //
  412. "..A|....a"},
  413. AT::kSuccess, "Case #0");
  414. // Offset range 1 overlaps 2 and 3, but truncation takes place to trim down
  415. // offset ranges, so still successful.
  416. SimpleTest({"..A|a....", //
  417. ".AA|..a..", //
  418. "AAA|....a"},
  419. AT::kSuccess, "Case #1");
  420. // Offset range 2 and 3 overlap, so fail.
  421. SimpleTest({"A..|a....", //
  422. ".A.|..a..", //
  423. ".A.|....a"},
  424. AT::kErrorBadOverlap, "Case #2");
  425. }
  426. TEST(AddressTranslatorTest, OverlapDangling) {
  427. using AT = AddressTranslator;
  428. constexpr auto OK = AT::kSuccess;
  429. // First Unit has dangling offsets at
  430. constexpr const char* unit_str1 = "....AAA.......|.....aaaaaa...";
  431. std::vector<TwoUnitOverlapTester::TestCase> test_cases = {
  432. //....AAA.......|.....aaaaaa... The first Unit. NOLINT
  433. {"....BBB.......|.....bbbbbb...", OK},
  434. {"....BBB.......|.....bbbbb....", OK},
  435. {"....BBB.......|.....bbbb.....", OK},
  436. {"....BBB.......|.....bbb......", OK},
  437. {".....BBB......|......bbb.....", AT::kErrorBadOverlapDanglingRva},
  438. {".....BB.......|......bbb.....", OK},
  439. {"....BBB.......|.....bbbbbbbb.", OK},
  440. {"..BBBBB.......|...bbbbbbbb...", OK},
  441. //....AAA.......|.....aaaaaa... The first Unit. NOLINT
  442. {"......!.......|.bbb..........", AT::kErrorBadOverlap},
  443. {"..BBBBB.......|...bbbbb......", OK},
  444. {".......BBB....|.bbb..........", OK}, // Just tangent: Can go elsewhere.
  445. {".......BBB....|.bbbb.........", OK}, // Can be another dangling RVA.
  446. {".......!......|.bbbb.........", OK}, // Same with empty.
  447. {"......!.......|.......!......", OK}, // Okay, but gets deleted.
  448. {"......!.......|.......b......", AT::kErrorBadOverlapDanglingRva},
  449. {"......B.......|.......b......", OK},
  450. //....AAA.......|.....aaaaaa... The first Unit. NOLINT
  451. {"......BBBB....|.......bbbb...", AT::kErrorBadOverlapDanglingRva},
  452. {"......BB......|.......bb.....", AT::kErrorBadOverlapDanglingRva},
  453. {"......BB......|bb............", AT::kErrorBadOverlap},
  454. };
  455. TwoUnitOverlapTester::RunTest(unit_str1, test_cases);
  456. }
  457. // Tests implementation since algorithm is tricky.
  458. TEST(AddressTranslatorTest, Merge) {
  459. using AT = AddressTranslator;
  460. // Merge a bunch of overlapping Units into one big Unit.
  461. std::vector<std::string> test_case1 = {
  462. "AAA.......|.aaa......", // Comment to prevent wrap by formatter.
  463. "AA........|.aa.......", //
  464. "..AAA.....|...aaa....", //
  465. "....A.....|.....a....", //
  466. ".....AAA..|......aaa.", //
  467. "........A.|.........a", //
  468. };
  469. // Try all 6! permutations.
  470. std::sort(test_case1.begin(), test_case1.end());
  471. do {
  472. TestAddressTranslator translator1;
  473. EXPECT_EQ(AT::kSuccess, translator1.InitializeWithStrings(test_case1));
  474. EXPECT_EQ(9U, translator1.fake_offset_begin());
  475. AT::Unit expected{0U, +9U, 1U, +9U};
  476. EXPECT_EQ(1U, translator1.units_sorted_by_offset().size());
  477. EXPECT_EQ(expected, translator1.units_sorted_by_offset()[0]);
  478. EXPECT_EQ(1U, translator1.units_sorted_by_rva().size());
  479. EXPECT_EQ(expected, translator1.units_sorted_by_rva()[0]);
  480. } while (std::next_permutation(test_case1.begin(), test_case1.end()));
  481. // Merge RVA-adjacent Units into two Units.
  482. std::vector<std::string> test_case2 = {
  483. ".....A..|.a......", // First Unit.
  484. "......A.|..a.....", //
  485. "A.......|...a....", // Second Unit: RVA-adjacent to first Unit, but
  486. ".A......|....a...", // offset would become inconsistent, so a new
  487. "..A.....|.....a..", // Unit gets created.
  488. };
  489. // Try all 5! permutations.
  490. std::sort(test_case2.begin(), test_case2.end());
  491. do {
  492. TestAddressTranslator translator2;
  493. EXPECT_EQ(AT::kSuccess, translator2.InitializeWithStrings(test_case2));
  494. EXPECT_EQ(7U, translator2.fake_offset_begin());
  495. AT::Unit expected1{0U, +3U, 3U, +3U};
  496. AT::Unit expected2{5U, +2U, 1U, +2U};
  497. EXPECT_EQ(2U, translator2.units_sorted_by_offset().size());
  498. EXPECT_EQ(expected1, translator2.units_sorted_by_offset()[0]);
  499. EXPECT_EQ(expected2, translator2.units_sorted_by_offset()[1]);
  500. EXPECT_EQ(2U, translator2.units_sorted_by_rva().size());
  501. EXPECT_EQ(expected2, translator2.units_sorted_by_rva()[0]);
  502. EXPECT_EQ(expected1, translator2.units_sorted_by_rva()[1]);
  503. } while (std::next_permutation(test_case2.begin(), test_case2.end()));
  504. }
  505. TEST(AddressTranslatorTest, RvaToOffsetCache_IsValid) {
  506. AddressTranslator translator;
  507. // Notice that the second section has dangling RVA.
  508. ASSERT_EQ(AddressTranslator::kSuccess,
  509. translator.Initialize(
  510. {{0x04, +0x28, 0x1A00, +0x28}, {0x30, +0x10, 0x3A00, +0x30}}));
  511. AddressTranslator::RvaToOffsetCache rva_checker(translator);
  512. EXPECT_FALSE(rva_checker.IsValid(kInvalidRva));
  513. for (int i = 0; i < 0x28; ++i)
  514. EXPECT_TRUE(rva_checker.IsValid(0x1A00 + i));
  515. EXPECT_FALSE(rva_checker.IsValid(0x1A00 + 0x28));
  516. EXPECT_FALSE(rva_checker.IsValid(0x1A00 + 0x29));
  517. EXPECT_FALSE(rva_checker.IsValid(0x1A00 - 1));
  518. EXPECT_FALSE(rva_checker.IsValid(0x1A00 - 2));
  519. for (int i = 0; i < 0x30; ++i)
  520. EXPECT_TRUE(rva_checker.IsValid(0x3A00 + i));
  521. EXPECT_FALSE(rva_checker.IsValid(0x3A00 + 0x30));
  522. EXPECT_FALSE(rva_checker.IsValid(0x3A00 + 0x31));
  523. EXPECT_FALSE(rva_checker.IsValid(0x3A00 - 1));
  524. EXPECT_FALSE(rva_checker.IsValid(0x3A00 - 2));
  525. EXPECT_FALSE(rva_checker.IsValid(0));
  526. EXPECT_FALSE(rva_checker.IsValid(0x10));
  527. EXPECT_FALSE(rva_checker.IsValid(0x7FFFFFFFU));
  528. EXPECT_FALSE(rva_checker.IsValid(0xFFFFFFFFU));
  529. }
  530. } // namespace zucchini