123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401 |
- // Copyright 2018 The Chromium Authors. All rights reserved.
- // Use of this source code is governed by a BSD-style license that can be
- // found in the LICENSE file.
- #include "components/zucchini/disassembler_ztf.h"
- #include <stddef.h>
- #include <stdint.h>
- #include <algorithm>
- #include <map>
- #include <set>
- #include <utility>
- #include <vector>
- #include "base/strings/string_piece.h"
- #include "components/zucchini/buffer_view.h"
- #include "components/zucchini/element_detection.h"
- #include "testing/gtest/include/gtest/gtest.h"
- namespace zucchini {
- namespace {
- constexpr char kNormalText[] = R"(ZTxt
- Hello World!
- This is an example of an absolute reference <<1,1>>
- And {-01,+05} is an example of a relative ref
- txTZ
- TRAILING DATA)";
- // -1 to exclude null byte.
- constexpr size_t kNormalTextExtraBytes = std::size("TRAILING DATA") - 1;
- constexpr char kOutOfBoundsText[] = R"(ZTxt<1,1>
- Hello World!
- This is an example of an OOB absolute reference <890,605>
- And {-050,+100} is an example of an OOB relative ref.
- but [+00,+10] is valid at least. As is (1,5).
- <1, 6> and { ,1} aren't nor is {4,5]
- {7,6}<1,1><2,3>{+00,+00}{004,100}[+00,+60][+000,-100]<-000,-035>(-00,-00)txTZ
- )";
- // Converts a raw string into data.
- std::vector<uint8_t> StrToData(base::StringPiece s) {
- return std::vector<uint8_t>(s.begin(), s.end());
- }
- // Compare if |a.location < b.location| as references have unique locations.
- struct ReferenceCompare {
- bool operator()(const Reference& a, const Reference& b) const {
- return a.location < b.location;
- }
- };
- using ReferenceKey =
- std::pair<DisassemblerZtf::ReferencePool, DisassemblerZtf::ReferenceType>;
- using ReferenceSets =
- std::map<ReferenceKey, std::set<Reference, ReferenceCompare>>;
- // Write references in |refs_to_write| to |image|. Also validate the
- // disassembler parses |image| such that it is of |expected_size|.
- void WriteReferences(MutableBufferView image,
- size_t expected_size,
- const ReferenceSets& refs_to_write) {
- EXPECT_TRUE(DisassemblerZtf::QuickDetect(image));
- std::unique_ptr<DisassemblerZtf> dis =
- Disassembler::Make<DisassemblerZtf>(image);
- EXPECT_TRUE(dis);
- EXPECT_EQ(expected_size, dis->size());
- image.shrink(dis->size());
- auto reference_groups = dis->MakeReferenceGroups();
- for (const auto& group : reference_groups) {
- auto writer = group.GetWriter(image, dis.get());
- ReferenceKey key = {
- static_cast<DisassemblerZtf::ReferencePool>(group.pool_tag().value()),
- static_cast<DisassemblerZtf::ReferenceType>(group.type_tag().value())};
- if (!refs_to_write.count(key))
- continue;
- for (const auto& ref : refs_to_write.at(key))
- writer->PutNext(ref);
- }
- }
- // Read references in |refs_to_read| from |image|. Once found
- // the elements are removed from |refs_to_read|. Also validate the
- // disassembler parses |image| such that it is of |expected_size|.
- void ReadReferences(ConstBufferView image,
- size_t expected_size,
- ReferenceSets* refs_to_read) {
- EXPECT_TRUE(DisassemblerZtf::QuickDetect(image));
- std::unique_ptr<DisassemblerZtf> dis =
- Disassembler::Make<DisassemblerZtf>(image);
- EXPECT_TRUE(dis);
- EXPECT_EQ(expected_size, dis->size());
- auto reference_groups = dis->MakeReferenceGroups();
- for (const auto& group : reference_groups) {
- auto reader = group.GetReader(dis.get());
- ReferenceKey key = {
- static_cast<DisassemblerZtf::ReferencePool>(group.pool_tag().value()),
- static_cast<DisassemblerZtf::ReferenceType>(group.type_tag().value())};
- if (!refs_to_read->count(key)) {
- // No elements of this pool/type pair are expected so assert that none are
- // found.
- auto ref = reader->GetNext();
- EXPECT_FALSE(ref.has_value());
- continue;
- }
- // For each reference remove it from the set if it exists, error if
- // unexpected references are found.
- for (auto ref = reader->GetNext(); ref.has_value();
- ref = reader->GetNext()) {
- EXPECT_EQ(1UL, refs_to_read->at(key).erase(ref.value()));
- }
- EXPECT_EQ(0U, refs_to_read->at(key).size());
- }
- }
- void TestTranslation(const ZtfTranslator& translator,
- offset_t expected_location,
- ztf::LineCol lc) {
- // Check the lc is translated to the expected location.
- EXPECT_EQ(expected_location, translator.LineColToOffset(lc));
- auto new_lc = translator.OffsetToLineCol(expected_location);
- if (expected_location == kInvalidOffset) {
- EXPECT_FALSE(translator.IsValid(lc));
- EXPECT_FALSE(new_lc.has_value());
- } else {
- EXPECT_TRUE(translator.IsValid(lc));
- // Check that the reverse is true. |ztf::LineCol{0, 0}| is a sentinel and
- // should never be valid.
- EXPECT_EQ(lc.line, new_lc->line);
- EXPECT_EQ(lc.col, new_lc->col);
- }
- }
- template <typename T>
- size_t CountDistinct(const std::vector<T>& v) {
- return std::set<T>(v.begin(), v.end()).size();
- }
- } // namespace
- TEST(ZtfTranslatorTest, Translate) {
- ztf::dim_t kMaxVal = INT16_MAX;
- ztf::dim_t kMinVal = INT16_MIN;
- const std::vector<uint8_t> text(StrToData(kOutOfBoundsText));
- ConstBufferView image(text.data(), text.size());
- ZtfTranslator translator;
- EXPECT_TRUE(translator.Init(image));
- // Absolute Translations:
- // Check a bunch of invalid locations.
- TestTranslation(translator, kInvalidOffset, ztf::LineCol{50, 60});
- TestTranslation(translator, kInvalidOffset, ztf::LineCol{0, 0});
- TestTranslation(translator, kInvalidOffset, ztf::LineCol{1, 0});
- TestTranslation(translator, kInvalidOffset, ztf::LineCol{0, 1});
- TestTranslation(translator, kInvalidOffset, ztf::LineCol{0, 1});
- TestTranslation(translator, kInvalidOffset, ztf::LineCol{1, -1});
- TestTranslation(translator, kInvalidOffset, ztf::LineCol{-1, 1});
- TestTranslation(translator, kInvalidOffset, ztf::LineCol{-1, -1});
- TestTranslation(translator, kInvalidOffset, ztf::LineCol{1, kMaxVal});
- TestTranslation(translator, kInvalidOffset, ztf::LineCol{kMaxVal, 1});
- TestTranslation(translator, kInvalidOffset, ztf::LineCol{1, kMinVal});
- TestTranslation(translator, kInvalidOffset, ztf::LineCol{kMinVal, 1});
- // Check the start of the file.
- TestTranslation(translator, 0, ztf::LineCol{1, 1});
- TestTranslation(translator, 1, ztf::LineCol{1, 2});
- // Check the boundary around a newline.
- TestTranslation(translator, 9, ztf::LineCol{1, 10});
- TestTranslation(translator, kInvalidOffset, ztf::LineCol{1, 11});
- TestTranslation(translator, 10, ztf::LineCol{2, 1});
- TestTranslation(translator, kInvalidOffset, ztf::LineCol{2, 0});
- // Check the end of the file.
- TestTranslation(translator, kInvalidOffset, ztf::LineCol{8, 1});
- TestTranslation(translator, kInvalidOffset, ztf::LineCol{7, 79});
- // Need to subtract to account for the newline.
- TestTranslation(translator, text.size() - 1, ztf::LineCol{7, 78});
- TestTranslation(translator, text.size() - 2, ztf::LineCol{7, 77});
- // Delta Validity
- // - Reminder! 0 -> 1:1
- // Common possible edge cases.
- EXPECT_TRUE(translator.IsValid(0, ztf::DeltaLineCol{0, 0}));
- EXPECT_TRUE(translator.IsValid(0, ztf::DeltaLineCol{0, 1}));
- EXPECT_TRUE(translator.IsValid(0, ztf::DeltaLineCol{1, 0}));
- EXPECT_FALSE(translator.IsValid(0, ztf::DeltaLineCol{-1, -1}));
- EXPECT_FALSE(translator.IsValid(0, ztf::DeltaLineCol{-1, 0}));
- EXPECT_FALSE(translator.IsValid(0, ztf::DeltaLineCol{0, -1}));
- EXPECT_FALSE(translator.IsValid(0, ztf::DeltaLineCol{0, -1}));
- EXPECT_FALSE(translator.IsValid(0, ztf::DeltaLineCol{0, kMaxVal}));
- EXPECT_FALSE(translator.IsValid(0, ztf::DeltaLineCol{kMaxVal, 0}));
- EXPECT_FALSE(translator.IsValid(0, ztf::DeltaLineCol{0, kMinVal}));
- EXPECT_FALSE(translator.IsValid(0, ztf::DeltaLineCol{kMinVal, 0}));
- EXPECT_FALSE(translator.IsValid(233, ztf::DeltaLineCol{0, kMaxVal}));
- EXPECT_FALSE(translator.IsValid(233, ztf::DeltaLineCol{kMaxVal, 0}));
- EXPECT_FALSE(translator.IsValid(233, ztf::DeltaLineCol{kMaxVal, kMaxVal}));
- // Newline area.
- EXPECT_TRUE(translator.IsValid(0, ztf::DeltaLineCol{0, 9}));
- EXPECT_FALSE(translator.IsValid(0, ztf::DeltaLineCol{0, 10}));
- EXPECT_FALSE(translator.IsValid(9, ztf::DeltaLineCol{0, 1}));
- EXPECT_FALSE(translator.IsValid(9, ztf::DeltaLineCol{-1, 0}));
- EXPECT_FALSE(translator.IsValid(9, ztf::DeltaLineCol{1, -10}));
- EXPECT_TRUE(translator.IsValid(9, ztf::DeltaLineCol{1, -9}));
- // End of file.
- EXPECT_FALSE(translator.IsValid(0, ztf::DeltaLineCol{7, 78}));
- EXPECT_FALSE(translator.IsValid(0, ztf::DeltaLineCol{7, 77}));
- EXPECT_FALSE(translator.IsValid(0, ztf::DeltaLineCol{6, 78}));
- EXPECT_TRUE(translator.IsValid(0, ztf::DeltaLineCol{6, 77}));
- EXPECT_FALSE(translator.IsValid(text.size() - 1, ztf::DeltaLineCol{0, 1}));
- EXPECT_FALSE(translator.IsValid(text.size() - 1, ztf::DeltaLineCol{1, 0}));
- EXPECT_TRUE(translator.IsValid(text.size() - 2, ztf::DeltaLineCol{0, 1}));
- EXPECT_FALSE(translator.IsValid(text.size() - 2, ztf::DeltaLineCol{1, 0}));
- }
- // Ensures that ReferenceGroups from DisassemblerZtf::MakeReferenceGroups()
- // cover each non-sentinel element in ReferenceType in order, exactly once. Also
- // ensures that the ReferenceType elements are grouped by ReferencePool, and
- // listed in increasing order.
- TEST(DisassemblerZtfTest, ReferenceGroups) {
- std::vector<uint32_t> pool_list;
- std::vector<uint32_t> type_list;
- DisassemblerZtf dis;
- for (ReferenceGroup group : dis.MakeReferenceGroups()) {
- pool_list.push_back(static_cast<uint32_t>(group.pool_tag().value()));
- type_list.push_back(static_cast<uint32_t>(group.type_tag().value()));
- }
- // Check ReferenceByte coverage.
- constexpr size_t kNumTypes = DisassemblerZtf::kNumTypes;
- EXPECT_EQ(kNumTypes, type_list.size());
- EXPECT_EQ(kNumTypes, CountDistinct(type_list));
- EXPECT_TRUE(std::is_sorted(type_list.begin(), type_list.end()));
- // Check that ReferenceType elements are grouped by ReferencePool. Note that
- // repeats can occur, and pools can be skipped.
- EXPECT_TRUE(std::is_sorted(pool_list.begin(), pool_list.end()));
- }
- TEST(DisassemblerZtfTest, BadMagic) {
- // Test a case where there is no header so a disassembler cannot be created.
- {
- const std::vector<uint8_t> text(StrToData("foobarbaz bazbarfoo"));
- ConstBufferView image(text.data(), text.size());
- EXPECT_FALSE(DisassemblerZtf::QuickDetect(image));
- EXPECT_FALSE(Disassembler::Make<DisassemblerZtf>(image));
- }
- // Test a case where there is no footer so a disassembler cannot be created.
- {
- const std::vector<uint8_t> text(StrToData("ZTxtfoobarbaz bazbarfootxTZ"));
- ConstBufferView image(text.data(), text.size());
- EXPECT_TRUE(DisassemblerZtf::QuickDetect(image));
- EXPECT_FALSE(Disassembler::Make<DisassemblerZtf>(image));
- }
- // Test when the header is too short
- {
- const std::vector<uint8_t> text(StrToData("ZTxtxTZ\n"));
- ConstBufferView image(text.data(), text.size());
- EXPECT_FALSE(DisassemblerZtf::QuickDetect(image));
- EXPECT_FALSE(Disassembler::Make<DisassemblerZtf>(image));
- }
- }
- TEST(DisassemblerZtfTest, ZtfSizeBound) {
- {
- std::vector<uint8_t> text(StrToData("ZTxt"));
- std::fill_n(std::back_inserter(text), ztf::kMaxDimValue - 2, '\n');
- text.insert(text.end(), {'t', 'x', 'T', 'Z', '\n'});
- ConstBufferView image(text.data(), text.size());
- EXPECT_TRUE(DisassemblerZtf::QuickDetect(image));
- EXPECT_TRUE(Disassembler::Make<DisassemblerZtf>(image));
- }
- {
- std::vector<uint8_t> text(StrToData("ZTxt"));
- std::fill_n(std::back_inserter(text), ztf::kMaxDimValue - 1, '\n');
- text.insert(text.end(), {'t', 'x', 'T', 'Z', '\n'});
- ConstBufferView image(text.data(), text.size());
- EXPECT_TRUE(DisassemblerZtf::QuickDetect(image));
- EXPECT_FALSE(Disassembler::Make<DisassemblerZtf>(image));
- }
- }
- // Try reading from a well formed source.
- TEST(DisassemblerZtfTest, NormalRead) {
- const std::vector<uint8_t> text(StrToData(kNormalText));
- ConstBufferView image(text.data(), text.size());
- ReferenceSets expected_map = {
- {{DisassemblerZtf::kAngles, DisassemblerZtf::kAnglesAbs1},
- {Reference({63, 0})}},
- {{DisassemblerZtf::kBraces, DisassemblerZtf::kBracesRel2},
- {Reference({74, 27})}},
- };
- ReadReferences(image, text.size() - kNormalTextExtraBytes, &expected_map);
- }
- // Try writing to a well formed source and ensure that what is read back
- // reflects what was written.
- TEST(DisassemblerZtfTest, NormalWrite) {
- std::vector<uint8_t> mutable_text(StrToData(kNormalText));
- MutableBufferView image(mutable_text.data(), mutable_text.size());
- ReferenceSets change_map = {
- {{DisassemblerZtf::kParentheses, DisassemblerZtf::kParenthesesAbs1},
- {Reference({63, 71})}},
- {{DisassemblerZtf::kBrackets, DisassemblerZtf::kBracketsRel3},
- {Reference({74, 4})}},
- };
- WriteReferences(image, mutable_text.size() - kNormalTextExtraBytes,
- change_map);
- // As a sanity check see if a disassembler can identify the same references.
- ConstBufferView const_image(image);
- ReadReferences(const_image, mutable_text.size() - kNormalTextExtraBytes,
- &change_map);
- }
- // Try reading from a source rife with errors.
- TEST(DisassemblerZtfTest, ReadOutOfBoundsRefs) {
- const std::vector<uint8_t> text(StrToData(kOutOfBoundsText));
- ConstBufferView image(text.data(), text.size());
- ReferenceSets expected_map = {
- {{DisassemblerZtf::kAngles, DisassemblerZtf::kAnglesAbs1},
- {Reference({4, 0}), Reference({223, 0}), Reference({228, 12})}},
- {{DisassemblerZtf::kBrackets, DisassemblerZtf::kBracketsRel2},
- {Reference({139, 149})}},
- {{DisassemblerZtf::kBraces, DisassemblerZtf::kBracesAbs1},
- {Reference({218, 223})}},
- {{DisassemblerZtf::kBraces, DisassemblerZtf::kBracesRel2},
- {Reference({233, 233})}},
- {{DisassemblerZtf::kParentheses, DisassemblerZtf::kParenthesesAbs1},
- {Reference({174, 4})}},
- };
- ReadReferences(image, text.size(), &expected_map);
- }
- // Try writing to a source rife with errors (malformed references or ones that
- // reference non-existent locations. Some of the values written are also bad. To
- // validate check if the expected set of references are read back.
- TEST(DisassemblerZtfTest, WriteOutOfBoundsRefs) {
- // Replace |old_val| (provided for checking) with |new_val| in |set|.
- auto update_set = [](Reference old_ref, Reference new_ref,
- std::set<Reference, ReferenceCompare>* set) {
- auto it = set->find(old_ref);
- EXPECT_NE(it, set->cend());
- EXPECT_EQ(*it, old_ref);
- set->erase(it);
- set->insert(new_ref);
- };
- // Replace |old_val| (provided for checking) with |new_val| in the set which
- // is the value corresponding to |key| in |map|.
- auto update_map =
- [update_set](
- ReferenceKey key, Reference old_ref, Reference new_ref,
- std::map<ReferenceKey, std::set<Reference, ReferenceCompare>>* map) {
- auto it = map->find(key);
- EXPECT_NE(it, map->cend());
- update_set(old_ref, new_ref, &(it->second));
- };
- std::vector<uint8_t> mutable_text(StrToData(kOutOfBoundsText));
- MutableBufferView image(mutable_text.data(), mutable_text.size());
- ReferenceSets change_map = {
- {{DisassemblerZtf::kAngles, DisassemblerZtf::kAnglesAbs1},
- {Reference({223, 15}), Reference({228, 13})}},
- {{DisassemblerZtf::kAngles, DisassemblerZtf::kAnglesAbs3},
- {Reference({4, 50})}}, // This should fail to write.
- {{DisassemblerZtf::kBrackets, DisassemblerZtf::kBracketsRel2},
- {Reference({139, static_cast<offset_t>(
- mutable_text.size())})}}, // This should fail.
- {{DisassemblerZtf::kParentheses, DisassemblerZtf::kParenthesesAbs1},
- {Reference({174, 21})}}, // This should fail.
- {{DisassemblerZtf::kBraces, DisassemblerZtf::kBracesAbs1},
- {Reference({218, 219})}},
- {{DisassemblerZtf::kBraces, DisassemblerZtf::kBracesRel2},
- {Reference({233, 174})}},
- };
- WriteReferences(image, mutable_text.size(), change_map);
- // As a sanity check see if a disassembler can identify the same references
- // (excluding the invalid ones).
- change_map.erase(change_map.find(
- {DisassemblerZtf::kAngles, DisassemblerZtf::kAnglesAbs3}));
- change_map.at({DisassemblerZtf::kAngles, DisassemblerZtf::kAnglesAbs1})
- .emplace(Reference{4, 0});
- update_map({DisassemblerZtf::kBrackets, DisassemblerZtf::kBracketsRel2},
- Reference({139, static_cast<offset_t>(mutable_text.size())}),
- Reference({139, 149}), &change_map);
- update_map({DisassemblerZtf::kParentheses, DisassemblerZtf::kParenthesesAbs1},
- Reference({174, 21}), Reference({174, 4}), &change_map);
- ConstBufferView const_image(image);
- ReadReferences(const_image, mutable_text.size(), &change_map);
- }
- } // namespace zucchini
|