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