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/integer_sequence_codec.h"
16 #include "src/base/uint128.h"
17
18 #include <random>
19 #include <string>
20 #include <vector>
21
22 #include <gtest/gtest.h>
23
24 using astc_codec::base::UInt128;
25 using astc_codec::base::BitStream;
26 using astc_codec::IntegerSequenceCodec;
27 using astc_codec::IntegerSequenceEncoder;
28 using astc_codec::IntegerSequenceDecoder;
29
30 namespace {
31
32 // Make sure that the counts returned for a specific range match what's
33 // expected. In particular, make sure that it fits with Table C.2.7
TEST(ASTCIntegerSequenceCodecTest,TestGetCountsForRange)34 TEST(ASTCIntegerSequenceCodecTest, TestGetCountsForRange) {
35 std::array<int, 3> kExpectedCounts[31] = {
36 {{ 0, 0, 1 }}, // 1
37 {{ 1, 0, 0 }}, // 2
38 {{ 0, 0, 2 }}, // 3
39 {{ 0, 1, 0 }}, // 4
40 {{ 1, 0, 1 }}, // 5
41 {{ 0, 0, 3 }}, // 6
42 {{ 0, 0, 3 }}, // 7
43 {{ 0, 1, 1 }}, // 8
44 {{ 0, 1, 1 }}, // 9
45 {{ 1, 0, 2 }}, // 10
46 {{ 1, 0, 2 }}, // 11
47 {{ 0, 0, 4 }}, // 12
48 {{ 0, 0, 4 }}, // 13
49 {{ 0, 0, 4 }}, // 14
50 {{ 0, 0, 4 }}, // 15
51 {{ 0, 1, 2 }}, // 16
52 {{ 0, 1, 2 }}, // 17
53 {{ 0, 1, 2 }}, // 18
54 {{ 0, 1, 2 }}, // 19
55 {{ 1, 0, 3 }}, // 20
56 {{ 1, 0, 3 }}, // 21
57 {{ 1, 0, 3 }}, // 22
58 {{ 1, 0, 3 }}, // 23
59 {{ 0, 0, 5 }}, // 24
60 {{ 0, 0, 5 }}, // 25
61 {{ 0, 0, 5 }}, // 26
62 {{ 0, 0, 5 }}, // 27
63 {{ 0, 0, 5 }}, // 28
64 {{ 0, 0, 5 }}, // 29
65 {{ 0, 0, 5 }}, // 30
66 {{ 0, 0, 5 }}, // 31
67 };
68
69 int t, q, b;
70 for (int i = 1; i < 32; ++i) {
71 IntegerSequenceCodec::GetCountsForRange(i, &t, &q, &b);
72 EXPECT_EQ(t, kExpectedCounts[i - 1][0]);
73 EXPECT_EQ(q, kExpectedCounts[i - 1][1]);
74 EXPECT_EQ(b, kExpectedCounts[i - 1][2]);
75 }
76
77 ASSERT_DEATH(IntegerSequenceCodec::GetCountsForRange(0, &t, &q, &b), "");
78 ASSERT_DEATH(IntegerSequenceCodec::GetCountsForRange(256, &t, &q, &b), "");
79
80 IntegerSequenceCodec::GetCountsForRange(1, &t, &q, &b);
81 EXPECT_EQ(t, 0);
82 EXPECT_EQ(q, 0);
83 EXPECT_EQ(b, 1);
84 }
85
86 // Test to make sure that we're calculating the number of bits needed to
87 // encode a given number of values based on the range of the values.
TEST(ASTCIntegerSequenceCodecTest,TestNumBitsForCounts)88 TEST(ASTCIntegerSequenceCodecTest, TestNumBitsForCounts) {
89 int trits = 0;
90 int quints = 0;
91 int bits = 0;
92
93 // A range of one should have single bits, so n 1-bit values should be n bits.
94 trits = 0;
95 quints = 0;
96 bits = 1;
97 for (int i = 0; i < 64; ++i) {
98 EXPECT_EQ(IntegerSequenceCodec::GetBitCount(i, trits, quints, bits), i);
99 EXPECT_EQ(IntegerSequenceCodec::GetBitCountForRange(i, 1), i);
100 }
101
102 // Similarly, N two-bit values should be 2n bits...
103 trits = 0;
104 quints = 0;
105 bits = 2;
106 for (int i = 0; i < 64; ++i) {
107 int bit_counts = IntegerSequenceCodec::GetBitCount(i, trits, quints, bits);
108 EXPECT_EQ(bit_counts, 2 * i);
109 EXPECT_EQ(IntegerSequenceCodec::GetBitCountForRange(i, 3), 2 * i);
110 }
111
112 // Trits are a bit more complicated -- there are five trits in a block, so
113 // if we encode 15 values with 3 bits each in trits, we'd get three blocks,
114 // each with eight bits of trits.
115 trits = 1;
116 quints = 0;
117 bits = 3;
118 EXPECT_EQ(IntegerSequenceCodec::GetBitCount(15, trits, quints, bits),
119 8 * 3 + 15 * 3);
120 EXPECT_EQ(IntegerSequenceCodec::GetBitCountForRange(15, 23),
121 IntegerSequenceCodec::GetBitCount(15, trits, quints, bits));
122
123 // However, if instead we encode 13 values, we don't need to use the remaining
124 // two values, so we only need bits as they will be encoded. As it turns out,
125 // this means we can avoid three bits in the final block (one for the high
126 // order trit encoding and two for one of the values), resulting in 47 bits.
127 trits = 1;
128 quints = 0;
129 bits = 2;
130 EXPECT_EQ(IntegerSequenceCodec::GetBitCount(13, trits, quints, bits), 47);
131 EXPECT_EQ(IntegerSequenceCodec::GetBitCountForRange(13, 11),
132 IntegerSequenceCodec::GetBitCount(13, trits, quints, bits));
133
134 // Quints have a similar property -- if we encode six values using a quint and
135 // four bits, then we have two quint blocks each with three values and a seven
136 // bit encoded quint triplet...
137 trits = 0;
138 quints = 1;
139 bits = 4;
140 EXPECT_EQ(IntegerSequenceCodec::GetBitCount(6, trits, quints, bits),
141 7 * 2 + 6 * 4);
142 EXPECT_EQ(IntegerSequenceCodec::GetBitCountForRange(6, 79),
143 IntegerSequenceCodec::GetBitCount(6, trits, quints, bits));
144
145 // If we have fewer values than blocks we can again avoid about 2 + nbits
146 // bits...
147 trits = 0;
148 quints = 1;
149 bits = 3;
150 EXPECT_EQ(IntegerSequenceCodec::GetBitCount(7, trits, quints, bits),
151 /* first two quint blocks */ 7 * 2 +
152 /* first two blocks of bits */ 6 * 3 +
153 /* last quint block without the high order four bits */ 3 +
154 /* last block with one set of three bits */ 3);
155 }
156
157 // Tests that the encoder knows how to encode values of the form 5*2^k.
TEST(ASTCIntegerSequenceCodecTest,TestQuintCodec)158 TEST(ASTCIntegerSequenceCodecTest, TestQuintCodec) {
159 // In this case, k = 4
160
161 // Setup bit src/sink
162 BitStream<UInt128> bit_sink;
163
164 const int kValueRange = 79;
165 IntegerSequenceEncoder enc(kValueRange);
166 enc.AddValue(3);
167 enc.AddValue(79);
168 enc.AddValue(37);
169 enc.Encode(&bit_sink);
170
171 // quint: 1000101 m0: 0011 m1: 1111 m2: 0101
172 // 100 0100 0111 1101 0010
173 // interleaved 10m200m1101m0
174 // should be 100 1010 0111 1101 0011 = 0x4A7D3
175 EXPECT_EQ(bit_sink.Bits(), 19);
176
177 uint64_t encoded = 0;
178 bit_sink.GetBits(19, &encoded);
179 EXPECT_EQ(encoded, 0x4A7D3);
180
181 // Now check that decoding it works as well
182 BitStream<UInt128> bit_src(encoded, 19);
183
184 IntegerSequenceDecoder dec(kValueRange);
185 auto decoded_vals = dec.Decode(3, &bit_src);
186 ASSERT_EQ(decoded_vals.size(), 3);
187 EXPECT_EQ(decoded_vals[0], 3);
188 EXPECT_EQ(decoded_vals[1], 79);
189 EXPECT_EQ(decoded_vals[2], 37);
190 }
191
192 // Tests that the encoder knows how to encode values of the form 3*2^k.
TEST(ASTCIntegerSequenceCodecTest,TestTritCodec)193 TEST(ASTCIntegerSequenceCodecTest, TestTritCodec) {
194 uint64_t encoded = 0;
195
196 // Setup bit src/sink
197 BitStream<UInt128> bit_sink(encoded, 0);
198
199 const int kValueRange = 11;
200 IntegerSequenceEncoder enc(kValueRange);
201 enc.AddValue(7);
202 enc.AddValue(5);
203 enc.AddValue(3);
204 enc.AddValue(6);
205 enc.AddValue(10);
206 enc.Encode(&bit_sink);
207
208 EXPECT_EQ(bit_sink.Bits(), 18);
209
210 bit_sink.GetBits(18, &encoded);
211 EXPECT_EQ(encoded, 0x37357);
212
213 // Now check that decoding it works as well
214 BitStream<UInt128> bit_src(encoded, 19);
215
216 IntegerSequenceDecoder dec(kValueRange);
217 auto decoded_vals = dec.Decode(5, &bit_src);
218 ASSERT_EQ(decoded_vals.size(), 5);
219 EXPECT_EQ(decoded_vals[0], 7);
220 EXPECT_EQ(decoded_vals[1], 5);
221 EXPECT_EQ(decoded_vals[2], 3);
222 EXPECT_EQ(decoded_vals[3], 6);
223 EXPECT_EQ(decoded_vals[4], 10);
224 }
225
226 // Test a specific quint encoding/decoding. This test makes sure that the way we
227 // encode and decode integer sequences matches what we should expect out of the
228 // reference ASTC encoder.
TEST(ASTCIntegerSequenceCodecTest,TestDecodeThenEncode)229 TEST(ASTCIntegerSequenceCodecTest, TestDecodeThenEncode) {
230 std::vector<int> vals = {{ 16, 18, 17, 4, 7, 14, 10, 0 }};
231 const uint64_t kValEncoding = 0x2b9c83dc;
232
233 BitStream<UInt128> bit_src(kValEncoding, 64);
234 IntegerSequenceDecoder dec(19);
235 auto decoded_vals = dec.Decode(8, &bit_src);
236 ASSERT_EQ(decoded_vals.size(), vals.size());
237 for (size_t i = 0; i < decoded_vals.size(); ++i) {
238 EXPECT_EQ(decoded_vals[i], vals[i]);
239 }
240
241 // Setup bit src/sink
242 BitStream<UInt128> bit_sink;
243 IntegerSequenceEncoder enc(19);
244 for (const auto& v : vals) {
245 enc.AddValue(v);
246 }
247 enc.Encode(&bit_sink);
248 EXPECT_EQ(bit_sink.Bits(), 35);
249
250 uint64_t encoded = 0;
251 EXPECT_TRUE(bit_sink.GetBits(35, &encoded));
252 EXPECT_EQ(encoded, kValEncoding)
253 << std::hex << encoded << " -- " << kValEncoding;
254 }
255
256 // Same as the previous test, except it uses a trit encoding rather than a
257 // quint encoding.
TEST(ASTCIntegerSequenceCodecTest,TestDecodeThenEncodeTrits)258 TEST(ASTCIntegerSequenceCodecTest, TestDecodeThenEncodeTrits) {
259 std::vector<int> vals = {{ 6, 0, 0, 2, 0, 0, 0, 0, 8, 0, 0, 0, 0, 8, 8, 0 }};
260 const uint64_t kValEncoding = 0x0004c0100001006ULL;
261
262 BitStream<UInt128> bit_src(kValEncoding, 64);
263 IntegerSequenceDecoder dec(11);
264 auto decoded_vals = dec.Decode(vals.size(), &bit_src);
265 ASSERT_EQ(decoded_vals.size(), vals.size());
266 for (size_t i = 0; i < decoded_vals.size(); ++i) {
267 EXPECT_EQ(decoded_vals[i], vals[i]);
268 }
269
270 // Setup bit src/sink
271 BitStream<UInt128> bit_sink;
272 IntegerSequenceEncoder enc(11);
273 for (const auto& v : vals) {
274 enc.AddValue(v);
275 }
276 enc.Encode(&bit_sink);
277 EXPECT_EQ(bit_sink.Bits(), 58);
278
279 uint64_t encoded = 0;
280 EXPECT_TRUE(bit_sink.GetBits(58, &encoded));
281 EXPECT_EQ(encoded, kValEncoding)
282 << std::hex << encoded << " -- " << kValEncoding;
283 }
284
285 // Generate a random sequence of integer codings with different ranges to test
286 // the reciprocability of our codec (encoded sequences should be able to
287 // decoded)
TEST(ASTCIntegerSequenceCodecTest,TestRandomReciprocation)288 TEST(ASTCIntegerSequenceCodecTest, TestRandomReciprocation) {
289 std::mt19937 mt(0xbad7357);
290 std::uniform_int_distribution<int> rand(0, 255);
291
292 for (int test = 0; test < 1600; ++test) {
293 // Generate a random number of values and a random range
294 int num_vals = 4 + rand(mt) % 44; // Up to 48 weights in a grid
295 int range = 1 + rand(mt) % 63;
296
297 // If this produces a bit pattern larger than our buffer, then ignore
298 // it... we already know what our bounds are for the integer sequences
299 int num_bits = IntegerSequenceCodec::GetBitCountForRange(num_vals, range);
300 if (num_bits >= 64) {
301 continue;
302 }
303
304 std::vector<int> generated_vals(num_vals);
305 for (auto& val : generated_vals) {
306 val = rand(mt) % (range + 1);
307 }
308
309 // Encode the values using the
310 BitStream<UInt128> bit_sink;
311
312 // Add them to the encoder
313 IntegerSequenceEncoder enc(range);
314 for (int v : generated_vals) {
315 enc.AddValue(v);
316 }
317 enc.Encode(&bit_sink);
318
319 uint64_t encoded = 0;
320 bit_sink.GetBits(bit_sink.Bits(), &encoded);
321 ASSERT_GE(encoded, 0);
322 EXPECT_LT(encoded, 1ULL << num_bits);
323
324 BitStream<UInt128> bit_src(encoded, 64);
325
326 IntegerSequenceDecoder dec(range);
327 auto decoded_vals = dec.Decode(num_vals, &bit_src);
328
329 ASSERT_EQ(decoded_vals.size(), generated_vals.size());
330 for (size_t i = 0; i < decoded_vals.size(); ++i) {
331 EXPECT_EQ(decoded_vals[i], generated_vals[i]);
332 }
333 }
334 }
335
336 } // namespace
337