disassembler_ztf_unittest.cc 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401
  1. // Copyright 2018 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/disassembler_ztf.h"
  5. #include <stddef.h>
  6. #include <stdint.h>
  7. #include <algorithm>
  8. #include <map>
  9. #include <set>
  10. #include <utility>
  11. #include <vector>
  12. #include "base/strings/string_piece.h"
  13. #include "components/zucchini/buffer_view.h"
  14. #include "components/zucchini/element_detection.h"
  15. #include "testing/gtest/include/gtest/gtest.h"
  16. namespace zucchini {
  17. namespace {
  18. constexpr char kNormalText[] = R"(ZTxt
  19. Hello World!
  20. This is an example of an absolute reference <<1,1>>
  21. And {-01,+05} is an example of a relative ref
  22. txTZ
  23. TRAILING DATA)";
  24. // -1 to exclude null byte.
  25. constexpr size_t kNormalTextExtraBytes = std::size("TRAILING DATA") - 1;
  26. constexpr char kOutOfBoundsText[] = R"(ZTxt<1,1>
  27. Hello World!
  28. This is an example of an OOB absolute reference <890,605>
  29. And {-050,+100} is an example of an OOB relative ref.
  30. but [+00,+10] is valid at least. As is (1,5).
  31. <1, 6> and { ,1} aren't nor is {4,5]
  32. {7,6}<1,1><2,3>{+00,+00}{004,100}[+00,+60][+000,-100]<-000,-035>(-00,-00)txTZ
  33. )";
  34. // Converts a raw string into data.
  35. std::vector<uint8_t> StrToData(base::StringPiece s) {
  36. return std::vector<uint8_t>(s.begin(), s.end());
  37. }
  38. // Compare if |a.location < b.location| as references have unique locations.
  39. struct ReferenceCompare {
  40. bool operator()(const Reference& a, const Reference& b) const {
  41. return a.location < b.location;
  42. }
  43. };
  44. using ReferenceKey =
  45. std::pair<DisassemblerZtf::ReferencePool, DisassemblerZtf::ReferenceType>;
  46. using ReferenceSets =
  47. std::map<ReferenceKey, std::set<Reference, ReferenceCompare>>;
  48. // Write references in |refs_to_write| to |image|. Also validate the
  49. // disassembler parses |image| such that it is of |expected_size|.
  50. void WriteReferences(MutableBufferView image,
  51. size_t expected_size,
  52. const ReferenceSets& refs_to_write) {
  53. EXPECT_TRUE(DisassemblerZtf::QuickDetect(image));
  54. std::unique_ptr<DisassemblerZtf> dis =
  55. Disassembler::Make<DisassemblerZtf>(image);
  56. EXPECT_TRUE(dis);
  57. EXPECT_EQ(expected_size, dis->size());
  58. image.shrink(dis->size());
  59. auto reference_groups = dis->MakeReferenceGroups();
  60. for (const auto& group : reference_groups) {
  61. auto writer = group.GetWriter(image, dis.get());
  62. ReferenceKey key = {
  63. static_cast<DisassemblerZtf::ReferencePool>(group.pool_tag().value()),
  64. static_cast<DisassemblerZtf::ReferenceType>(group.type_tag().value())};
  65. if (!refs_to_write.count(key))
  66. continue;
  67. for (const auto& ref : refs_to_write.at(key))
  68. writer->PutNext(ref);
  69. }
  70. }
  71. // Read references in |refs_to_read| from |image|. Once found
  72. // the elements are removed from |refs_to_read|. Also validate the
  73. // disassembler parses |image| such that it is of |expected_size|.
  74. void ReadReferences(ConstBufferView image,
  75. size_t expected_size,
  76. ReferenceSets* refs_to_read) {
  77. EXPECT_TRUE(DisassemblerZtf::QuickDetect(image));
  78. std::unique_ptr<DisassemblerZtf> dis =
  79. Disassembler::Make<DisassemblerZtf>(image);
  80. EXPECT_TRUE(dis);
  81. EXPECT_EQ(expected_size, dis->size());
  82. auto reference_groups = dis->MakeReferenceGroups();
  83. for (const auto& group : reference_groups) {
  84. auto reader = group.GetReader(dis.get());
  85. ReferenceKey key = {
  86. static_cast<DisassemblerZtf::ReferencePool>(group.pool_tag().value()),
  87. static_cast<DisassemblerZtf::ReferenceType>(group.type_tag().value())};
  88. if (!refs_to_read->count(key)) {
  89. // No elements of this pool/type pair are expected so assert that none are
  90. // found.
  91. auto ref = reader->GetNext();
  92. EXPECT_FALSE(ref.has_value());
  93. continue;
  94. }
  95. // For each reference remove it from the set if it exists, error if
  96. // unexpected references are found.
  97. for (auto ref = reader->GetNext(); ref.has_value();
  98. ref = reader->GetNext()) {
  99. EXPECT_EQ(1UL, refs_to_read->at(key).erase(ref.value()));
  100. }
  101. EXPECT_EQ(0U, refs_to_read->at(key).size());
  102. }
  103. }
  104. void TestTranslation(const ZtfTranslator& translator,
  105. offset_t expected_location,
  106. ztf::LineCol lc) {
  107. // Check the lc is translated to the expected location.
  108. EXPECT_EQ(expected_location, translator.LineColToOffset(lc));
  109. auto new_lc = translator.OffsetToLineCol(expected_location);
  110. if (expected_location == kInvalidOffset) {
  111. EXPECT_FALSE(translator.IsValid(lc));
  112. EXPECT_FALSE(new_lc.has_value());
  113. } else {
  114. EXPECT_TRUE(translator.IsValid(lc));
  115. // Check that the reverse is true. |ztf::LineCol{0, 0}| is a sentinel and
  116. // should never be valid.
  117. EXPECT_EQ(lc.line, new_lc->line);
  118. EXPECT_EQ(lc.col, new_lc->col);
  119. }
  120. }
  121. template <typename T>
  122. size_t CountDistinct(const std::vector<T>& v) {
  123. return std::set<T>(v.begin(), v.end()).size();
  124. }
  125. } // namespace
  126. TEST(ZtfTranslatorTest, Translate) {
  127. ztf::dim_t kMaxVal = INT16_MAX;
  128. ztf::dim_t kMinVal = INT16_MIN;
  129. const std::vector<uint8_t> text(StrToData(kOutOfBoundsText));
  130. ConstBufferView image(text.data(), text.size());
  131. ZtfTranslator translator;
  132. EXPECT_TRUE(translator.Init(image));
  133. // Absolute Translations:
  134. // Check a bunch of invalid locations.
  135. TestTranslation(translator, kInvalidOffset, ztf::LineCol{50, 60});
  136. TestTranslation(translator, kInvalidOffset, ztf::LineCol{0, 0});
  137. TestTranslation(translator, kInvalidOffset, ztf::LineCol{1, 0});
  138. TestTranslation(translator, kInvalidOffset, ztf::LineCol{0, 1});
  139. TestTranslation(translator, kInvalidOffset, ztf::LineCol{0, 1});
  140. TestTranslation(translator, kInvalidOffset, ztf::LineCol{1, -1});
  141. TestTranslation(translator, kInvalidOffset, ztf::LineCol{-1, 1});
  142. TestTranslation(translator, kInvalidOffset, ztf::LineCol{-1, -1});
  143. TestTranslation(translator, kInvalidOffset, ztf::LineCol{1, kMaxVal});
  144. TestTranslation(translator, kInvalidOffset, ztf::LineCol{kMaxVal, 1});
  145. TestTranslation(translator, kInvalidOffset, ztf::LineCol{1, kMinVal});
  146. TestTranslation(translator, kInvalidOffset, ztf::LineCol{kMinVal, 1});
  147. // Check the start of the file.
  148. TestTranslation(translator, 0, ztf::LineCol{1, 1});
  149. TestTranslation(translator, 1, ztf::LineCol{1, 2});
  150. // Check the boundary around a newline.
  151. TestTranslation(translator, 9, ztf::LineCol{1, 10});
  152. TestTranslation(translator, kInvalidOffset, ztf::LineCol{1, 11});
  153. TestTranslation(translator, 10, ztf::LineCol{2, 1});
  154. TestTranslation(translator, kInvalidOffset, ztf::LineCol{2, 0});
  155. // Check the end of the file.
  156. TestTranslation(translator, kInvalidOffset, ztf::LineCol{8, 1});
  157. TestTranslation(translator, kInvalidOffset, ztf::LineCol{7, 79});
  158. // Need to subtract to account for the newline.
  159. TestTranslation(translator, text.size() - 1, ztf::LineCol{7, 78});
  160. TestTranslation(translator, text.size() - 2, ztf::LineCol{7, 77});
  161. // Delta Validity
  162. // - Reminder! 0 -> 1:1
  163. // Common possible edge cases.
  164. EXPECT_TRUE(translator.IsValid(0, ztf::DeltaLineCol{0, 0}));
  165. EXPECT_TRUE(translator.IsValid(0, ztf::DeltaLineCol{0, 1}));
  166. EXPECT_TRUE(translator.IsValid(0, ztf::DeltaLineCol{1, 0}));
  167. EXPECT_FALSE(translator.IsValid(0, ztf::DeltaLineCol{-1, -1}));
  168. EXPECT_FALSE(translator.IsValid(0, ztf::DeltaLineCol{-1, 0}));
  169. EXPECT_FALSE(translator.IsValid(0, ztf::DeltaLineCol{0, -1}));
  170. EXPECT_FALSE(translator.IsValid(0, ztf::DeltaLineCol{0, -1}));
  171. EXPECT_FALSE(translator.IsValid(0, ztf::DeltaLineCol{0, kMaxVal}));
  172. EXPECT_FALSE(translator.IsValid(0, ztf::DeltaLineCol{kMaxVal, 0}));
  173. EXPECT_FALSE(translator.IsValid(0, ztf::DeltaLineCol{0, kMinVal}));
  174. EXPECT_FALSE(translator.IsValid(0, ztf::DeltaLineCol{kMinVal, 0}));
  175. EXPECT_FALSE(translator.IsValid(233, ztf::DeltaLineCol{0, kMaxVal}));
  176. EXPECT_FALSE(translator.IsValid(233, ztf::DeltaLineCol{kMaxVal, 0}));
  177. EXPECT_FALSE(translator.IsValid(233, ztf::DeltaLineCol{kMaxVal, kMaxVal}));
  178. // Newline area.
  179. EXPECT_TRUE(translator.IsValid(0, ztf::DeltaLineCol{0, 9}));
  180. EXPECT_FALSE(translator.IsValid(0, ztf::DeltaLineCol{0, 10}));
  181. EXPECT_FALSE(translator.IsValid(9, ztf::DeltaLineCol{0, 1}));
  182. EXPECT_FALSE(translator.IsValid(9, ztf::DeltaLineCol{-1, 0}));
  183. EXPECT_FALSE(translator.IsValid(9, ztf::DeltaLineCol{1, -10}));
  184. EXPECT_TRUE(translator.IsValid(9, ztf::DeltaLineCol{1, -9}));
  185. // End of file.
  186. EXPECT_FALSE(translator.IsValid(0, ztf::DeltaLineCol{7, 78}));
  187. EXPECT_FALSE(translator.IsValid(0, ztf::DeltaLineCol{7, 77}));
  188. EXPECT_FALSE(translator.IsValid(0, ztf::DeltaLineCol{6, 78}));
  189. EXPECT_TRUE(translator.IsValid(0, ztf::DeltaLineCol{6, 77}));
  190. EXPECT_FALSE(translator.IsValid(text.size() - 1, ztf::DeltaLineCol{0, 1}));
  191. EXPECT_FALSE(translator.IsValid(text.size() - 1, ztf::DeltaLineCol{1, 0}));
  192. EXPECT_TRUE(translator.IsValid(text.size() - 2, ztf::DeltaLineCol{0, 1}));
  193. EXPECT_FALSE(translator.IsValid(text.size() - 2, ztf::DeltaLineCol{1, 0}));
  194. }
  195. // Ensures that ReferenceGroups from DisassemblerZtf::MakeReferenceGroups()
  196. // cover each non-sentinel element in ReferenceType in order, exactly once. Also
  197. // ensures that the ReferenceType elements are grouped by ReferencePool, and
  198. // listed in increasing order.
  199. TEST(DisassemblerZtfTest, ReferenceGroups) {
  200. std::vector<uint32_t> pool_list;
  201. std::vector<uint32_t> type_list;
  202. DisassemblerZtf dis;
  203. for (ReferenceGroup group : dis.MakeReferenceGroups()) {
  204. pool_list.push_back(static_cast<uint32_t>(group.pool_tag().value()));
  205. type_list.push_back(static_cast<uint32_t>(group.type_tag().value()));
  206. }
  207. // Check ReferenceByte coverage.
  208. constexpr size_t kNumTypes = DisassemblerZtf::kNumTypes;
  209. EXPECT_EQ(kNumTypes, type_list.size());
  210. EXPECT_EQ(kNumTypes, CountDistinct(type_list));
  211. EXPECT_TRUE(std::is_sorted(type_list.begin(), type_list.end()));
  212. // Check that ReferenceType elements are grouped by ReferencePool. Note that
  213. // repeats can occur, and pools can be skipped.
  214. EXPECT_TRUE(std::is_sorted(pool_list.begin(), pool_list.end()));
  215. }
  216. TEST(DisassemblerZtfTest, BadMagic) {
  217. // Test a case where there is no header so a disassembler cannot be created.
  218. {
  219. const std::vector<uint8_t> text(StrToData("foobarbaz bazbarfoo"));
  220. ConstBufferView image(text.data(), text.size());
  221. EXPECT_FALSE(DisassemblerZtf::QuickDetect(image));
  222. EXPECT_FALSE(Disassembler::Make<DisassemblerZtf>(image));
  223. }
  224. // Test a case where there is no footer so a disassembler cannot be created.
  225. {
  226. const std::vector<uint8_t> text(StrToData("ZTxtfoobarbaz bazbarfootxTZ"));
  227. ConstBufferView image(text.data(), text.size());
  228. EXPECT_TRUE(DisassemblerZtf::QuickDetect(image));
  229. EXPECT_FALSE(Disassembler::Make<DisassemblerZtf>(image));
  230. }
  231. // Test when the header is too short
  232. {
  233. const std::vector<uint8_t> text(StrToData("ZTxtxTZ\n"));
  234. ConstBufferView image(text.data(), text.size());
  235. EXPECT_FALSE(DisassemblerZtf::QuickDetect(image));
  236. EXPECT_FALSE(Disassembler::Make<DisassemblerZtf>(image));
  237. }
  238. }
  239. TEST(DisassemblerZtfTest, ZtfSizeBound) {
  240. {
  241. std::vector<uint8_t> text(StrToData("ZTxt"));
  242. std::fill_n(std::back_inserter(text), ztf::kMaxDimValue - 2, '\n');
  243. text.insert(text.end(), {'t', 'x', 'T', 'Z', '\n'});
  244. ConstBufferView image(text.data(), text.size());
  245. EXPECT_TRUE(DisassemblerZtf::QuickDetect(image));
  246. EXPECT_TRUE(Disassembler::Make<DisassemblerZtf>(image));
  247. }
  248. {
  249. std::vector<uint8_t> text(StrToData("ZTxt"));
  250. std::fill_n(std::back_inserter(text), ztf::kMaxDimValue - 1, '\n');
  251. text.insert(text.end(), {'t', 'x', 'T', 'Z', '\n'});
  252. ConstBufferView image(text.data(), text.size());
  253. EXPECT_TRUE(DisassemblerZtf::QuickDetect(image));
  254. EXPECT_FALSE(Disassembler::Make<DisassemblerZtf>(image));
  255. }
  256. }
  257. // Try reading from a well formed source.
  258. TEST(DisassemblerZtfTest, NormalRead) {
  259. const std::vector<uint8_t> text(StrToData(kNormalText));
  260. ConstBufferView image(text.data(), text.size());
  261. ReferenceSets expected_map = {
  262. {{DisassemblerZtf::kAngles, DisassemblerZtf::kAnglesAbs1},
  263. {Reference({63, 0})}},
  264. {{DisassemblerZtf::kBraces, DisassemblerZtf::kBracesRel2},
  265. {Reference({74, 27})}},
  266. };
  267. ReadReferences(image, text.size() - kNormalTextExtraBytes, &expected_map);
  268. }
  269. // Try writing to a well formed source and ensure that what is read back
  270. // reflects what was written.
  271. TEST(DisassemblerZtfTest, NormalWrite) {
  272. std::vector<uint8_t> mutable_text(StrToData(kNormalText));
  273. MutableBufferView image(mutable_text.data(), mutable_text.size());
  274. ReferenceSets change_map = {
  275. {{DisassemblerZtf::kParentheses, DisassemblerZtf::kParenthesesAbs1},
  276. {Reference({63, 71})}},
  277. {{DisassemblerZtf::kBrackets, DisassemblerZtf::kBracketsRel3},
  278. {Reference({74, 4})}},
  279. };
  280. WriteReferences(image, mutable_text.size() - kNormalTextExtraBytes,
  281. change_map);
  282. // As a sanity check see if a disassembler can identify the same references.
  283. ConstBufferView const_image(image);
  284. ReadReferences(const_image, mutable_text.size() - kNormalTextExtraBytes,
  285. &change_map);
  286. }
  287. // Try reading from a source rife with errors.
  288. TEST(DisassemblerZtfTest, ReadOutOfBoundsRefs) {
  289. const std::vector<uint8_t> text(StrToData(kOutOfBoundsText));
  290. ConstBufferView image(text.data(), text.size());
  291. ReferenceSets expected_map = {
  292. {{DisassemblerZtf::kAngles, DisassemblerZtf::kAnglesAbs1},
  293. {Reference({4, 0}), Reference({223, 0}), Reference({228, 12})}},
  294. {{DisassemblerZtf::kBrackets, DisassemblerZtf::kBracketsRel2},
  295. {Reference({139, 149})}},
  296. {{DisassemblerZtf::kBraces, DisassemblerZtf::kBracesAbs1},
  297. {Reference({218, 223})}},
  298. {{DisassemblerZtf::kBraces, DisassemblerZtf::kBracesRel2},
  299. {Reference({233, 233})}},
  300. {{DisassemblerZtf::kParentheses, DisassemblerZtf::kParenthesesAbs1},
  301. {Reference({174, 4})}},
  302. };
  303. ReadReferences(image, text.size(), &expected_map);
  304. }
  305. // Try writing to a source rife with errors (malformed references or ones that
  306. // reference non-existent locations. Some of the values written are also bad. To
  307. // validate check if the expected set of references are read back.
  308. TEST(DisassemblerZtfTest, WriteOutOfBoundsRefs) {
  309. // Replace |old_val| (provided for checking) with |new_val| in |set|.
  310. auto update_set = [](Reference old_ref, Reference new_ref,
  311. std::set<Reference, ReferenceCompare>* set) {
  312. auto it = set->find(old_ref);
  313. EXPECT_NE(it, set->cend());
  314. EXPECT_EQ(*it, old_ref);
  315. set->erase(it);
  316. set->insert(new_ref);
  317. };
  318. // Replace |old_val| (provided for checking) with |new_val| in the set which
  319. // is the value corresponding to |key| in |map|.
  320. auto update_map =
  321. [update_set](
  322. ReferenceKey key, Reference old_ref, Reference new_ref,
  323. std::map<ReferenceKey, std::set<Reference, ReferenceCompare>>* map) {
  324. auto it = map->find(key);
  325. EXPECT_NE(it, map->cend());
  326. update_set(old_ref, new_ref, &(it->second));
  327. };
  328. std::vector<uint8_t> mutable_text(StrToData(kOutOfBoundsText));
  329. MutableBufferView image(mutable_text.data(), mutable_text.size());
  330. ReferenceSets change_map = {
  331. {{DisassemblerZtf::kAngles, DisassemblerZtf::kAnglesAbs1},
  332. {Reference({223, 15}), Reference({228, 13})}},
  333. {{DisassemblerZtf::kAngles, DisassemblerZtf::kAnglesAbs3},
  334. {Reference({4, 50})}}, // This should fail to write.
  335. {{DisassemblerZtf::kBrackets, DisassemblerZtf::kBracketsRel2},
  336. {Reference({139, static_cast<offset_t>(
  337. mutable_text.size())})}}, // This should fail.
  338. {{DisassemblerZtf::kParentheses, DisassemblerZtf::kParenthesesAbs1},
  339. {Reference({174, 21})}}, // This should fail.
  340. {{DisassemblerZtf::kBraces, DisassemblerZtf::kBracesAbs1},
  341. {Reference({218, 219})}},
  342. {{DisassemblerZtf::kBraces, DisassemblerZtf::kBracesRel2},
  343. {Reference({233, 174})}},
  344. };
  345. WriteReferences(image, mutable_text.size(), change_map);
  346. // As a sanity check see if a disassembler can identify the same references
  347. // (excluding the invalid ones).
  348. change_map.erase(change_map.find(
  349. {DisassemblerZtf::kAngles, DisassemblerZtf::kAnglesAbs3}));
  350. change_map.at({DisassemblerZtf::kAngles, DisassemblerZtf::kAnglesAbs1})
  351. .emplace(Reference{4, 0});
  352. update_map({DisassemblerZtf::kBrackets, DisassemblerZtf::kBracketsRel2},
  353. Reference({139, static_cast<offset_t>(mutable_text.size())}),
  354. Reference({139, 149}), &change_map);
  355. update_map({DisassemblerZtf::kParentheses, DisassemblerZtf::kParenthesesAbs1},
  356. Reference({174, 21}), Reference({174, 4}), &change_map);
  357. ConstBufferView const_image(image);
  358. ReadReferences(const_image, mutable_text.size(), &change_map);
  359. }
  360. } // namespace zucchini