zucchini_gen_unittest.cc 7.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181
  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/zucchini_gen.h"
  5. #include <stdint.h>
  6. #include <deque>
  7. #include <utility>
  8. #include <vector>
  9. #include "components/zucchini/equivalence_map.h"
  10. #include "components/zucchini/image_index.h"
  11. #include "components/zucchini/image_utils.h"
  12. #include "components/zucchini/test_disassembler.h"
  13. #include "testing/gtest/include/gtest/gtest.h"
  14. namespace zucchini {
  15. namespace {
  16. using OffsetVector = std::vector<offset_t>;
  17. // In normal usage, 0.0 is an unrealistic similarity value for an
  18. // EquivalenceCandiate. Since similarity doesn't affect results for various unit
  19. // tests in this file, we use this dummy value for simplicity.
  20. constexpr double kDummySim = 0.0;
  21. // Helper function wrapping GenerateReferencesDelta().
  22. std::vector<int32_t> GenerateReferencesDeltaTest(
  23. std::vector<Reference>&& old_references,
  24. std::vector<Reference>&& new_references,
  25. std::deque<offset_t>&& exp_old_targets,
  26. std::deque<offset_t>&& exp_projected_old_targets,
  27. EquivalenceMap&& equivalence_map) {
  28. // OffsetMapper needs image sizes for forward-projection overflow check. These
  29. // are tested elsewhere, so just use arbitrary large value.
  30. constexpr offset_t kOldImageSize = 1000000;
  31. constexpr offset_t kNewImageSize = 1001000;
  32. ReferenceDeltaSink reference_delta_sink;
  33. TargetPool old_targets;
  34. old_targets.InsertTargets(old_references);
  35. ReferenceSet old_refs({1, TypeTag(0), PoolTag(0)}, old_targets);
  36. old_refs.InitReferences(old_references);
  37. EXPECT_EQ(exp_old_targets, old_targets.targets());
  38. TargetPool new_targets;
  39. new_targets.InsertTargets(new_references);
  40. ReferenceSet new_refs({1, TypeTag(0), PoolTag(0)}, new_targets);
  41. new_refs.InitReferences(new_references);
  42. OffsetMapper offset_mapper(equivalence_map, kOldImageSize, kNewImageSize);
  43. TargetPool projected_old_targets = old_targets;
  44. projected_old_targets.FilterAndProject(offset_mapper);
  45. std::vector<offset_t> extra_target =
  46. FindExtraTargets(projected_old_targets, new_targets);
  47. projected_old_targets.InsertTargets(extra_target);
  48. EXPECT_EQ(exp_projected_old_targets, projected_old_targets.targets());
  49. GenerateReferencesDelta(old_refs, new_refs, projected_old_targets,
  50. offset_mapper, equivalence_map,
  51. &reference_delta_sink);
  52. // Serialize |reference_delta_sink| to patch format, and read it back as
  53. // std::vector<int32_t>.
  54. std::vector<uint8_t> buffer(reference_delta_sink.SerializedSize());
  55. BufferSink sink(buffer.data(), buffer.size());
  56. reference_delta_sink.SerializeInto(&sink);
  57. BufferSource source(buffer.data(), buffer.size());
  58. ReferenceDeltaSource reference_delta_source;
  59. EXPECT_TRUE(reference_delta_source.Initialize(&source));
  60. std::vector<int32_t> delta_vec;
  61. for (auto delta = reference_delta_source.GetNext(); delta.has_value();
  62. delta = reference_delta_source.GetNext()) {
  63. delta_vec.push_back(*delta);
  64. }
  65. EXPECT_TRUE(reference_delta_source.Done());
  66. return delta_vec;
  67. }
  68. } // namespace
  69. TEST(ZucchiniGenTest, FindExtraTargets) {
  70. EXPECT_EQ(OffsetVector(), FindExtraTargets({}, {}));
  71. EXPECT_EQ(OffsetVector(), FindExtraTargets(TargetPool({3}), {}));
  72. EXPECT_EQ(OffsetVector(), FindExtraTargets(TargetPool({3}), TargetPool({3})));
  73. EXPECT_EQ(OffsetVector({4}),
  74. FindExtraTargets(TargetPool({3}), TargetPool({4})));
  75. EXPECT_EQ(OffsetVector({4}),
  76. FindExtraTargets(TargetPool({3}), TargetPool({3, 4})));
  77. EXPECT_EQ(OffsetVector({4}),
  78. FindExtraTargets(TargetPool({2, 3}), TargetPool({3, 4})));
  79. EXPECT_EQ(OffsetVector({3, 5}),
  80. FindExtraTargets(TargetPool({2, 4}), TargetPool({3, 5})));
  81. }
  82. TEST(ZucchiniGenTest, GenerateReferencesDelta) {
  83. // No equivalences.
  84. EXPECT_EQ(std::vector<int32_t>(),
  85. GenerateReferencesDeltaTest({}, {}, {}, {}, EquivalenceMap()));
  86. EXPECT_EQ(std::vector<int32_t>(),
  87. GenerateReferencesDeltaTest({{10, 0}}, {{20, 0}}, {0}, {0},
  88. EquivalenceMap()));
  89. // Simple cases with one equivalence.
  90. EXPECT_EQ(
  91. std::vector<int32_t>({0}), // {0 - 0}.
  92. GenerateReferencesDeltaTest(
  93. {{10, 3}}, {{20, 3}}, {3}, {3},
  94. EquivalenceMap({{{3, 3, 1}, kDummySim}, {{10, 20, 4}, kDummySim}})));
  95. EXPECT_EQ(
  96. std::vector<int32_t>({-1}), // {0 - 1}.
  97. GenerateReferencesDeltaTest(
  98. {{10, 3}}, {{20, 3}}, {3}, {3, 4},
  99. EquivalenceMap({{{3, 4, 1}, kDummySim}, {{10, 20, 4}, kDummySim}})));
  100. EXPECT_EQ(
  101. std::vector<int32_t>({1}), // {1 - 0}.
  102. GenerateReferencesDeltaTest(
  103. {{10, 3}}, {{20, 3}}, {3}, {2, 3},
  104. EquivalenceMap({{{3, 2, 1}, kDummySim}, {{10, 20, 4}, kDummySim}})));
  105. EXPECT_EQ(std::vector<int32_t>({1, -1}), // {1 - 0, 0 - 1}.
  106. GenerateReferencesDeltaTest(
  107. {{10, 3}, {11, 4}}, {{20, 3}, {21, 4}}, {3, 4}, {2, 3, 4, 5},
  108. EquivalenceMap({{{3, 2, 1}, kDummySim},
  109. {{4, 5, 1}, kDummySim},
  110. {{10, 20, 4}, kDummySim}})));
  111. EXPECT_EQ(
  112. std::vector<int32_t>({0, 0}), // {1 - 1, 2 - 2}.
  113. GenerateReferencesDeltaTest(
  114. {{10, 3}, {11, 4}, {12, 5}, {13, 6}},
  115. {{20, 3}, {21, 4}, {22, 5}, {23, 6}}, {3, 4, 5, 6}, {3, 4, 5, 6},
  116. EquivalenceMap({{{3, 3, 4}, kDummySim}, {{11, 21, 2}, kDummySim}})));
  117. // Multiple equivalences.
  118. EXPECT_EQ(std::vector<int32_t>({-1, 1}), // {0 - 1, 1 - 0}.
  119. GenerateReferencesDeltaTest(
  120. {{10, 0}, {12, 1}}, {{10, 0}, {12, 1}}, {0, 1}, {0, 1},
  121. EquivalenceMap({{{0, 0, 2}, kDummySim},
  122. {{12, 10, 2}, kDummySim},
  123. {{10, 12, 2}, kDummySim}})));
  124. EXPECT_EQ(
  125. std::vector<int32_t>({0, 0}), // {0 - 0, 1 - 1}.
  126. GenerateReferencesDeltaTest(
  127. {{0, 0}, {2, 2}}, {{0, 0}, {2, 2}}, {0, 2}, {0, 2},
  128. EquivalenceMap({{{2, 0, 2}, kDummySim}, {{0, 2, 2}, kDummySim}})));
  129. EXPECT_EQ(std::vector<int32_t>({-2, 2}), // {0 - 2, 2 - 0}.
  130. GenerateReferencesDeltaTest(
  131. {{10, 0}, {12, 1}, {14, 2}}, {{10, 0}, {12, 1}, {14, 2}},
  132. {0, 1, 2}, {0, 1, 2},
  133. EquivalenceMap({{{0, 0, 3}, kDummySim},
  134. {{14, 10, 2}, kDummySim},
  135. {{10, 14, 2}, kDummySim}})));
  136. EXPECT_EQ(std::vector<int32_t>({-2, 2}), // {0 - 2, 2 - 0}.
  137. GenerateReferencesDeltaTest(
  138. {{11, 0}, {14, 1}, {17, 2}}, {{11, 0}, {14, 1}, {17, 2}},
  139. {0, 1, 2}, {0, 1, 2},
  140. EquivalenceMap({{{0, 0, 3}, kDummySim},
  141. {{16, 10, 3}, kDummySim},
  142. {{10, 16, 3}, kDummySim}})));
  143. EXPECT_EQ(
  144. std::vector<int32_t>({-2, 2}), // {0 - 2, 2 - 0}.
  145. GenerateReferencesDeltaTest({{10, 0}, {14, 2}, {16, 1}},
  146. {{10, 0}, {14, 2}}, {0, 1, 2}, {0, 1, 2},
  147. EquivalenceMap({{{0, 0, 3}, kDummySim},
  148. {{14, 10, 2}, kDummySim},
  149. {{12, 12, 2}, kDummySim},
  150. {{10, 14, 2}, kDummySim}})));
  151. }
  152. // TODO(huangs): Add more tests.
  153. } // namespace zucchini