1 // Copyright 2018 Google LLC
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "src/decoder/partition.h"
16
17 #include <gmock/gmock.h>
18 #include <gtest/gtest.h>
19
20 #include <array>
21 #include <random>
22 #include <string>
23 #include <vector>
24
25 namespace {
26
27 using ::testing::ElementsAreArray;
28 using ::testing::Eq;
29 using ::testing::Le;
30 using ::testing::Not;
31
32 using astc_codec::Footprint;
33 using astc_codec::Partition;
34 using astc_codec::PartitionMetric;
35 using astc_codec::GetASTCPartition;
36 using astc_codec::FindClosestASTCPartition;
37
38 // Test to make sure that a simple difference between two partitions where
39 // most of the values are the same returns what we expect.
TEST(PartitionTest,TestSimplePartitionMetric)40 TEST(PartitionTest, TestSimplePartitionMetric) {
41 Partition a = {Footprint::Get6x6(), /* num_parts = */ 2,
42 /* partition_id = */ {}, /* assignment = */ {}};
43 Partition b = a;
44
45 a.assignment = {
46 0, 0, 0, 0, 0, 0,
47 0, 0, 0, 0, 0, 0,
48 0, 0, 0, 0, 0, 0,
49 0, 0, 0, 0, 0, 0,
50 0, 0, 0, 0, 0, 0,
51 0, 0, 0, 0, 0, 1,
52 };
53
54 b.assignment = {
55 1, 0, 0, 0, 0, 0,
56 0, 0, 0, 0, 0, 0,
57 0, 0, 0, 0, 0, 0,
58 0, 0, 0, 0, 0, 0,
59 0, 0, 0, 0, 0, 0,
60 0, 0, 0, 0, 0, 0,
61 };
62
63 const int dist = PartitionMetric(a, b);
64 EXPECT_EQ(dist, 2);
65 }
66
67 // Test to make sure that if one partition is a subset of another that we still
68 // return the proper difference against the subset of the larger one.
TEST(PartitionDeathTest,TestPartitionMetric)69 TEST(PartitionDeathTest, TestPartitionMetric) {
70 Partition a = {Footprint::Get4x4(), /* num_parts = */ 2,
71 /* partition_id = */ {}, /* assignment = */ {}};
72 Partition b = {Footprint::Get6x6(), /* num_parts = */ 2,
73 /* partition_id = */ {}, /* assignment = */ {}};
74
75 a.assignment = {{
76 1, 1, 1, 1,
77 0, 0, 0, 0,
78 0, 0, 0, 0,
79 0, 0, 0, 1,
80 }};
81
82 b.assignment = {{
83 1, 0, 0, 0, 0, 0,
84 0, 0, 0, 0, 0, 0,
85 0, 0, 0, 0, 0, 1,
86 0, 0, 0, 0, 0, 0,
87 0, 1, 0, 0, 1, 0,
88 0, 0, 1, 1, 0, 0,
89 }};
90
91 EXPECT_DEATH(PartitionMetric(a, b), "");
92 }
93
94 // Test to make sure that even if we have different numbers of subsets for each
95 // partition, that the returned value is what we'd expect.
TEST(PartitionTest,TestDiffPartsPartitionMetric)96 TEST(PartitionTest, TestDiffPartsPartitionMetric) {
97 Partition a = {Footprint::Get4x4(), /* num_parts = */ 2,
98 /* partition_id = */ {}, /* assignment = */ {}};
99 Partition b = {Footprint::Get4x4(), /* num_parts = */ 3,
100 /* partition_id = */ {}, /* assignment = */ {}};
101
102 a.assignment = {{
103 2, 2, 2, 0,
104 0, 0, 0, 0,
105 0, 0, 0, 0,
106 0, 0, 0, 1,
107 }};
108
109 b.assignment = {{
110 1, 0, 0, 0,
111 0, 0, 0, 0,
112 0, 0, 0, 0,
113 0, 0, 0, 0
114 }};
115
116 const int dist = PartitionMetric(a, b);
117 EXPECT_EQ(dist, 3);
118 }
119
120 // An additional sanity check test that makes sure that we're not always mapping
121 // zero to zero in our tests.
TEST(PartitionTest,TestDiffMappingPartitionMetric)122 TEST(PartitionTest, TestDiffMappingPartitionMetric) {
123 Partition a = {Footprint::Get4x4(), /* num_parts = */ 2,
124 /* partition_id = */ {}, /* assignment = */ {}};
125 Partition b = {Footprint::Get4x4(), /* num_parts = */ 3,
126 /* partition_id = */ {}, /* assignment = */ {}};
127
128 a.assignment = {{
129 0, 1, 2, 2,
130 2, 2, 2, 2,
131 2, 2, 2, 2,
132 2, 2, 2, 2,
133 }};
134
135 b.assignment = {{
136 1, 0, 0, 0,
137 0, 0, 0, 0,
138 0, 0, 0, 0,
139 0, 0, 0, 0,
140 }};
141
142 const int dist = PartitionMetric(a, b);
143 EXPECT_EQ(dist, 1);
144 }
145
146 // Finally, if we grab an ASTC partition and modify it a tad, the closest
147 // partition should still be the same ASTC partition.
TEST(PartitionTest,TestFindingASTCPartition)148 TEST(PartitionTest, TestFindingASTCPartition) {
149 const Partition astc = GetASTCPartition(Footprint::Get12x12(), 3, 0x3CB);
150 Partition almost_astc = astc;
151 almost_astc.assignment[0]++;
152
153 const Partition& closest_astc = FindClosestASTCPartition(almost_astc);
154 EXPECT_EQ(astc, closest_astc);
155 }
156
157 // Test a partition that was obtained from the reference ASTC encoder. We should
158 // be able to match it exactly
TEST(PartitionTest,TestSpecificPartition)159 TEST(PartitionTest, TestSpecificPartition) {
160 const Partition astc = GetASTCPartition(Footprint::Get10x6(), 3, 557);
161 EXPECT_THAT(astc.assignment, ElementsAreArray(std::array<int, 60> {{
162 0, 0, 0, 0, 1, 1, 1, 2, 2, 2,
163 0, 0, 0, 0, 1, 1, 1, 2, 2, 2,
164 0, 0, 0, 0, 1, 1, 1, 2, 2, 2,
165 0, 0, 0, 0, 1, 1, 1, 2, 2, 2,
166 0, 0, 0, 0, 1, 1, 1, 2, 2, 2,
167 0, 0, 0, 0, 1, 1, 1, 2, 2, 2 }}));
168 }
169
170 // Make sure that when we match against this specific partition, it'll return a
171 // partition with the same number of subsets
TEST(PartitionTest,EstimatedPartitionSubsets)172 TEST(PartitionTest, EstimatedPartitionSubsets) {
173 Partition partition = {
174 /* footprint = */ Footprint::Get6x6(),
175 /* num_parts = */ 2,
176 /* partition_id = */ {},
177 /* assignment = */ {
178 0, 0, 1, 1, 1, 0,
179 0, 0, 0, 0, 0, 0,
180 0, 0, 0, 0, 0, 0,
181 0, 1, 1, 1, 1, 1,
182 0, 0, 0, 0, 0, 0,
183 1, 1, 1, 1, 1, 1
184 }};
185
186 const Partition astc = FindClosestASTCPartition(partition);
187 EXPECT_THAT(astc.num_parts, Eq(partition.num_parts));
188 }
189
190 // Make sure that regardless of what partition we match against, it'll return a
191 // partition with at most a fewer number of subsets
TEST(PartitionTest,EstimatedPartitionFewerSubsets)192 TEST(PartitionTest, EstimatedPartitionFewerSubsets) {
193 std::mt19937 random(0xdeadbeef);
194 auto randUniform = [&random](int max) {
195 std::uniform_int_distribution<> dist(0, max - 1);
196 return dist(random);
197 };
198
199 constexpr int kNumFootprints = Footprint::NumValidFootprints();
200 const auto kFootprints = std::array<Footprint, kNumFootprints> {{
201 Footprint::Get4x4(),
202 Footprint::Get5x4(),
203 Footprint::Get5x5(),
204 Footprint::Get6x5(),
205 Footprint::Get6x6(),
206 Footprint::Get8x5(),
207 Footprint::Get8x6(),
208 Footprint::Get8x8(),
209 Footprint::Get10x5(),
210 Footprint::Get10x6(),
211 Footprint::Get10x8(),
212 Footprint::Get10x10(),
213 Footprint::Get12x10(),
214 Footprint::Get12x12()
215 }};
216
217 constexpr int kNumTests = 200;
218 for (int i = 0; i < kNumTests; ++i) {
219 const auto& footprint = kFootprints[randUniform(kNumFootprints)];
220 const int num_parts = 2 + randUniform(3);
221 Partition partition = {
222 footprint,
223 num_parts,
224 /* partition_id = */ {},
225 /* assignment = */ std::vector<int>(footprint.NumPixels(), 0)};
226
227 for (auto& p : partition.assignment) {
228 p = randUniform(num_parts);
229 }
230
231 const Partition astc = FindClosestASTCPartition(partition);
232 EXPECT_THAT(astc.num_parts, Le(partition.num_parts))
233 << "Test #" << i << ": "
234 << "Selected partition with ID " << astc.partition_id.value();
235 }
236 }
237
238 // Make sure that we generate unique partitions that are close to the
239 // candidates.
TEST(PartitionTest,UniquePartitionResults)240 TEST(PartitionTest, UniquePartitionResults) {
241 Partition partition = {
242 /* footprint = */ Footprint::Get6x6(),
243 /* num_parts = */ 2,
244 /* partition_id = */ {},
245 /* assignment = */ {
246 0, 1, 1, 1, 1, 1,
247 0, 1, 1, 1, 1, 1,
248 0, 1, 1, 1, 1, 1,
249 0, 1, 1, 1, 1, 1,
250 0, 1, 1, 1, 1, 1,
251 0, 1, 1, 1, 1, 1
252 }};
253
254 const auto parts = FindKClosestASTCPartitions(partition, 2);
255 EXPECT_THAT(*parts[0], Not(Eq(*parts[1])));
256 }
257
258 // TODO(google): Verify somehow that the assignment generated from
259 // GetASTCPartition actually matches what's in the spec. The selection
260 // function was more or less copy/pasted though so it's unclear how to
261 // measure that against e.g. the ASTC encoder.
262
263 } // namespace
264