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 // Contains utils for reading, writing and debug printing bit streams.
16
17 #include <map>
18 #include <sstream>
19 #include <string>
20 #include <unordered_map>
21
22 #include "util/huffman_codec.h"
23 #include "util/bit_stream.h"
24 #include "gmock/gmock.h"
25
26 namespace {
27
28 using spvutils::HuffmanCodec;
29 using spvutils::BitsToStream;
30
GetTestSet()31 const std::map<std::string, uint32_t>& GetTestSet() {
32 static const std::map<std::string, uint32_t> hist = {
33 {"a", 4},
34 {"e", 7},
35 {"f", 3},
36 {"h", 2},
37 {"i", 3},
38 {"m", 2},
39 {"n", 2},
40 {"s", 2},
41 {"t", 2},
42 {"l", 1},
43 {"o", 2},
44 {"p", 1},
45 {"r", 1},
46 {"u", 1},
47 {"x", 1},
48 };
49
50 return hist;
51 }
52
53 class TestBitReader {
54 public:
TestBitReader(const std::string & bits)55 TestBitReader(const std::string& bits) : bits_(bits) {}
56
ReadBit(bool * bit)57 bool ReadBit(bool* bit) {
58 if (pos_ < bits_.length()) {
59 *bit = bits_[pos_++] == '0' ? false : true;
60 return true;
61 }
62 return false;
63 }
64
65 private:
66 std::string bits_;
67 size_t pos_ = 0;
68 };
69
TEST(Huffman,PrintTree)70 TEST(Huffman, PrintTree) {
71 HuffmanCodec<std::string> huffman(GetTestSet());
72 std::stringstream ss;
73 huffman.PrintTree(ss);
74
75 const std::string expected = std::string(R"(
76 15-----7------e
77 8------4------a
78 4------2------m
79 2------n
80 19-----8------4------2------o
81 2------s
82 4------2------t
83 2------1------l
84 1------p
85 11-----5------2------1------r
86 1------u
87 3------f
88 6------3------i
89 3------1------x
90 2------h
91 )").substr(1);
92
93 EXPECT_EQ(expected, ss.str());
94 }
95
TEST(Huffman,PrintTable)96 TEST(Huffman, PrintTable) {
97 HuffmanCodec<std::string> huffman(GetTestSet());
98 std::stringstream ss;
99 huffman.PrintTable(ss);
100
101 const std::string expected = std::string(R"(
102 e 7 11
103 a 4 101
104 i 3 0001
105 f 3 0010
106 t 2 0101
107 s 2 0110
108 o 2 0111
109 n 2 1000
110 m 2 1001
111 h 2 00000
112 x 1 00001
113 u 1 00110
114 r 1 00111
115 p 1 01000
116 l 1 01001
117 )").substr(1);
118
119 EXPECT_EQ(expected, ss.str());
120 }
121
TEST(Huffman,TestValidity)122 TEST(Huffman, TestValidity) {
123 HuffmanCodec<std::string> huffman(GetTestSet());
124 const auto& encoding_table = huffman.GetEncodingTable();
125 std::vector<std::string> codes;
126 for (const auto& entry : encoding_table) {
127 codes.push_back(BitsToStream(entry.second.first, entry.second.second));
128 }
129
130 std::sort(codes.begin(), codes.end());
131
132 ASSERT_LT(codes.size(), 20u) << "Inefficient test ahead";
133
134 for (size_t i = 0; i < codes.size(); ++i) {
135 for (size_t j = i + 1; j < codes.size(); ++j) {
136 ASSERT_FALSE(codes[i] == codes[j].substr(0, codes[i].length()))
137 << codes[i] << " is prefix of " << codes[j];
138 }
139 }
140 }
141
TEST(Huffman,TestEncode)142 TEST(Huffman, TestEncode) {
143 HuffmanCodec<std::string> huffman(GetTestSet());
144
145 uint64_t bits = 0;
146 size_t num_bits = 0;
147
148 EXPECT_TRUE(huffman.Encode("e", &bits, &num_bits));
149 EXPECT_EQ(2u, num_bits);
150 EXPECT_EQ("11", BitsToStream(bits, num_bits));
151
152 EXPECT_TRUE(huffman.Encode("a", &bits, &num_bits));
153 EXPECT_EQ(3u, num_bits);
154 EXPECT_EQ("101", BitsToStream(bits, num_bits));
155
156 EXPECT_TRUE(huffman.Encode("x", &bits, &num_bits));
157 EXPECT_EQ(5u, num_bits);
158 EXPECT_EQ("00001", BitsToStream(bits, num_bits));
159
160 EXPECT_FALSE(huffman.Encode("y", &bits, &num_bits));
161 }
162
TEST(Huffman,TestDecode)163 TEST(Huffman, TestDecode) {
164 HuffmanCodec<std::string> huffman(GetTestSet());
165 TestBitReader bit_reader("01001""0001""1000""00110""00001""00");
166 auto read_bit = [&bit_reader](bool* bit) {
167 return bit_reader.ReadBit(bit);
168 };
169
170 std::string decoded;
171
172 ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
173 EXPECT_EQ("l", decoded);
174
175 ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
176 EXPECT_EQ("i", decoded);
177
178 ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
179 EXPECT_EQ("n", decoded);
180
181 ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
182 EXPECT_EQ("u", decoded);
183
184 ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
185 EXPECT_EQ("x", decoded);
186
187 ASSERT_FALSE(huffman.DecodeFromStream(read_bit, &decoded));
188 }
189
TEST(Huffman,TestDecodeNumbers)190 TEST(Huffman, TestDecodeNumbers) {
191 const std::map<uint32_t, uint32_t> hist = { {1, 10}, {2, 5}, {3, 15} };
192 HuffmanCodec<uint32_t> huffman(hist);
193
194 TestBitReader bit_reader("1""1""01""00""01""1");
195 auto read_bit = [&bit_reader](bool* bit) {
196 return bit_reader.ReadBit(bit);
197 };
198
199 uint32_t decoded;
200
201 ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
202 EXPECT_EQ(3u, decoded);
203
204 ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
205 EXPECT_EQ(3u, decoded);
206
207 ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
208 EXPECT_EQ(2u, decoded);
209
210 ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
211 EXPECT_EQ(1u, decoded);
212
213 ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
214 EXPECT_EQ(2u, decoded);
215
216 ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
217 EXPECT_EQ(3u, decoded);
218 }
219
220 } // anonymous namespace
221