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