1 // Copyright (c) 2017 Google Inc.
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 // http://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 <algorithm>
16 #include <map>
17 #include <sstream>
18 #include <string>
19 #include <unordered_map>
20 #include <utility>
21 #include <vector>
22
23 #include "gmock/gmock.h"
24 #include "source/comp/bit_stream.h"
25 #include "source/comp/huffman_codec.h"
26
27 namespace spvtools {
28 namespace comp {
29 namespace {
30
GetTestSet()31 const std::map<std::string, uint32_t>& GetTestSet() {
32 static const std::map<std::string, uint32_t> hist = {
33 {"a", 4}, {"e", 7}, {"f", 3}, {"h", 2}, {"i", 3},
34 {"m", 2}, {"n", 2}, {"s", 2}, {"t", 2}, {"l", 1},
35 {"o", 2}, {"p", 1}, {"r", 1}, {"u", 1}, {"x", 1},
36 };
37
38 return hist;
39 }
40
41 class TestBitReader {
42 public:
TestBitReader(const std::string & bits)43 TestBitReader(const std::string& bits) : bits_(bits) {}
44
ReadBit(bool * bit)45 bool ReadBit(bool* bit) {
46 if (pos_ < bits_.length()) {
47 *bit = bits_[pos_++] == '0' ? false : true;
48 return true;
49 }
50 return false;
51 }
52
53 private:
54 std::string bits_;
55 size_t pos_ = 0;
56 };
57
TEST(Huffman,PrintTree)58 TEST(Huffman, PrintTree) {
59 HuffmanCodec<std::string> huffman(GetTestSet());
60 std::stringstream ss;
61 huffman.PrintTree(ss);
62
63 // clang-format off
64 const std::string expected = std::string(R"(
65 15-----7------e
66 8------4------a
67 4------2------m
68 2------n
69 19-----8------4------2------o
70 2------s
71 4------2------t
72 2------1------l
73 1------p
74 11-----5------2------1------r
75 1------u
76 3------f
77 6------3------i
78 3------1------x
79 2------h
80 )").substr(1);
81 // clang-format on
82
83 EXPECT_EQ(expected, ss.str());
84 }
85
TEST(Huffman,PrintTable)86 TEST(Huffman, PrintTable) {
87 HuffmanCodec<std::string> huffman(GetTestSet());
88 std::stringstream ss;
89 huffman.PrintTable(ss);
90
91 const std::string expected = std::string(R"(
92 e 7 11
93 a 4 101
94 i 3 0001
95 f 3 0010
96 t 2 0101
97 s 2 0110
98 o 2 0111
99 n 2 1000
100 m 2 1001
101 h 2 00000
102 x 1 00001
103 u 1 00110
104 r 1 00111
105 p 1 01000
106 l 1 01001
107 )")
108 .substr(1);
109
110 EXPECT_EQ(expected, ss.str());
111 }
112
TEST(Huffman,TestValidity)113 TEST(Huffman, TestValidity) {
114 HuffmanCodec<std::string> huffman(GetTestSet());
115 const auto& encoding_table = huffman.GetEncodingTable();
116 std::vector<std::string> codes;
117 for (const auto& entry : encoding_table) {
118 codes.push_back(BitsToStream(entry.second.first, entry.second.second));
119 }
120
121 std::sort(codes.begin(), codes.end());
122
123 ASSERT_LT(codes.size(), 20u) << "Inefficient test ahead";
124
125 for (size_t i = 0; i < codes.size(); ++i) {
126 for (size_t j = i + 1; j < codes.size(); ++j) {
127 ASSERT_FALSE(codes[i] == codes[j].substr(0, codes[i].length()))
128 << codes[i] << " is prefix of " << codes[j];
129 }
130 }
131 }
132
TEST(Huffman,TestEncode)133 TEST(Huffman, TestEncode) {
134 HuffmanCodec<std::string> huffman(GetTestSet());
135
136 uint64_t bits = 0;
137 size_t num_bits = 0;
138
139 EXPECT_TRUE(huffman.Encode("e", &bits, &num_bits));
140 EXPECT_EQ(2u, num_bits);
141 EXPECT_EQ("11", BitsToStream(bits, num_bits));
142
143 EXPECT_TRUE(huffman.Encode("a", &bits, &num_bits));
144 EXPECT_EQ(3u, num_bits);
145 EXPECT_EQ("101", BitsToStream(bits, num_bits));
146
147 EXPECT_TRUE(huffman.Encode("x", &bits, &num_bits));
148 EXPECT_EQ(5u, num_bits);
149 EXPECT_EQ("00001", BitsToStream(bits, num_bits));
150
151 EXPECT_FALSE(huffman.Encode("y", &bits, &num_bits));
152 }
153
TEST(Huffman,TestDecode)154 TEST(Huffman, TestDecode) {
155 HuffmanCodec<std::string> huffman(GetTestSet());
156 TestBitReader bit_reader(
157 "01001"
158 "0001"
159 "1000"
160 "00110"
161 "00001"
162 "00");
163 auto read_bit = [&bit_reader](bool* bit) { return bit_reader.ReadBit(bit); };
164
165 std::string decoded;
166
167 ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
168 EXPECT_EQ("l", decoded);
169
170 ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
171 EXPECT_EQ("i", decoded);
172
173 ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
174 EXPECT_EQ("n", decoded);
175
176 ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
177 EXPECT_EQ("u", decoded);
178
179 ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
180 EXPECT_EQ("x", decoded);
181
182 ASSERT_FALSE(huffman.DecodeFromStream(read_bit, &decoded));
183 }
184
TEST(Huffman,TestDecodeNumbers)185 TEST(Huffman, TestDecodeNumbers) {
186 const std::map<uint32_t, uint32_t> hist = {{1, 10}, {2, 5}, {3, 15}};
187 HuffmanCodec<uint32_t> huffman(hist);
188
189 TestBitReader bit_reader(
190 "1"
191 "1"
192 "01"
193 "00"
194 "01"
195 "1");
196 auto read_bit = [&bit_reader](bool* bit) { return bit_reader.ReadBit(bit); };
197
198 uint32_t decoded;
199
200 ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
201 EXPECT_EQ(3u, decoded);
202
203 ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
204 EXPECT_EQ(3u, decoded);
205
206 ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
207 EXPECT_EQ(2u, decoded);
208
209 ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
210 EXPECT_EQ(1u, decoded);
211
212 ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
213 EXPECT_EQ(2u, decoded);
214
215 ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
216 EXPECT_EQ(3u, decoded);
217 }
218
TEST(Huffman,SerializeToTextU64)219 TEST(Huffman, SerializeToTextU64) {
220 const std::map<uint64_t, uint32_t> hist = {{1001, 10}, {1002, 5}, {1003, 15}};
221 HuffmanCodec<uint64_t> huffman(hist);
222
223 const std::string code = huffman.SerializeToText(2);
224
225 const std::string expected = R"((5, {
226 {0, 0, 0},
227 {1001, 0, 0},
228 {1002, 0, 0},
229 {1003, 0, 0},
230 {0, 1, 2},
231 {0, 4, 3},
232 }))";
233
234 ASSERT_EQ(expected, code);
235 }
236
TEST(Huffman,SerializeToTextString)237 TEST(Huffman, SerializeToTextString) {
238 const std::map<std::string, uint32_t> hist = {
239 {"aaa", 10}, {"bbb", 20}, {"ccc", 15}};
240 HuffmanCodec<std::string> huffman(hist);
241
242 const std::string code = huffman.SerializeToText(4);
243
244 const std::string expected = R"((5, {
245 {"", 0, 0},
246 {"aaa", 0, 0},
247 {"bbb", 0, 0},
248 {"ccc", 0, 0},
249 {"", 3, 1},
250 {"", 4, 2},
251 }))";
252
253 ASSERT_EQ(expected, code);
254 }
255
TEST(Huffman,CreateFromTextString)256 TEST(Huffman, CreateFromTextString) {
257 std::vector<HuffmanCodec<std::string>::Node> nodes = {
258 {},
259 {"root", 2, 3},
260 {"left", 0, 0},
261 {"right", 0, 0},
262 };
263
264 HuffmanCodec<std::string> huffman(1, std::move(nodes));
265
266 std::stringstream ss;
267 huffman.PrintTree(ss);
268
269 const std::string expected = std::string(R"(
270 0------right
271 0------left
272 )")
273 .substr(1);
274
275 EXPECT_EQ(expected, ss.str());
276 }
277
TEST(Huffman,CreateFromTextU64)278 TEST(Huffman, CreateFromTextU64) {
279 HuffmanCodec<uint64_t> huffman(5, {
280 {0, 0, 0},
281 {1001, 0, 0},
282 {1002, 0, 0},
283 {1003, 0, 0},
284 {0, 1, 2},
285 {0, 4, 3},
286 });
287
288 std::stringstream ss;
289 huffman.PrintTree(ss);
290
291 const std::string expected = std::string(R"(
292 0------1003
293 0------0------1002
294 0------1001
295 )")
296 .substr(1);
297
298 EXPECT_EQ(expected, ss.str());
299
300 TestBitReader bit_reader("01");
301 auto read_bit = [&bit_reader](bool* bit) { return bit_reader.ReadBit(bit); };
302
303 uint64_t decoded = 0;
304 ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
305 EXPECT_EQ(1002u, decoded);
306
307 uint64_t bits = 0;
308 size_t num_bits = 0;
309
310 EXPECT_TRUE(huffman.Encode(1001, &bits, &num_bits));
311 EXPECT_EQ(2u, num_bits);
312 EXPECT_EQ("00", BitsToStream(bits, num_bits));
313 }
314
315 } // namespace
316 } // namespace comp
317 } // namespace spvtools
318