123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318 |
- // Copyright (c) 2017 Google Inc.
- //
- // Licensed under the Apache License, Version 2.0 (the "License");
- // you may not use this file except in compliance with the License.
- // You may obtain a copy of the License at
- //
- // http://www.apache.org/licenses/LICENSE-2.0
- //
- // Unless required by applicable law or agreed to in writing, software
- // distributed under the License is distributed on an "AS IS" BASIS,
- // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- // See the License for the specific language governing permissions and
- // limitations under the License.
- #include <algorithm>
- #include <map>
- #include <sstream>
- #include <string>
- #include <unordered_map>
- #include <utility>
- #include <vector>
- #include "gmock/gmock.h"
- #include "source/comp/bit_stream.h"
- #include "source/comp/huffman_codec.h"
- namespace spvtools {
- namespace comp {
- namespace {
- const std::map<std::string, uint32_t>& GetTestSet() {
- static const std::map<std::string, uint32_t> hist = {
- {"a", 4}, {"e", 7}, {"f", 3}, {"h", 2}, {"i", 3},
- {"m", 2}, {"n", 2}, {"s", 2}, {"t", 2}, {"l", 1},
- {"o", 2}, {"p", 1}, {"r", 1}, {"u", 1}, {"x", 1},
- };
- return hist;
- }
- class TestBitReader {
- public:
- TestBitReader(const std::string& bits) : bits_(bits) {}
- bool ReadBit(bool* bit) {
- if (pos_ < bits_.length()) {
- *bit = bits_[pos_++] == '0' ? false : true;
- return true;
- }
- return false;
- }
- private:
- std::string bits_;
- size_t pos_ = 0;
- };
- TEST(Huffman, PrintTree) {
- HuffmanCodec<std::string> huffman(GetTestSet());
- std::stringstream ss;
- huffman.PrintTree(ss);
- // clang-format off
- const std::string expected = std::string(R"(
- 15-----7------e
- 8------4------a
- 4------2------m
- 2------n
- 19-----8------4------2------o
- 2------s
- 4------2------t
- 2------1------l
- 1------p
- 11-----5------2------1------r
- 1------u
- 3------f
- 6------3------i
- 3------1------x
- 2------h
- )").substr(1);
- // clang-format on
- EXPECT_EQ(expected, ss.str());
- }
- TEST(Huffman, PrintTable) {
- HuffmanCodec<std::string> huffman(GetTestSet());
- std::stringstream ss;
- huffman.PrintTable(ss);
- const std::string expected = std::string(R"(
- e 7 11
- a 4 101
- i 3 0001
- f 3 0010
- t 2 0101
- s 2 0110
- o 2 0111
- n 2 1000
- m 2 1001
- h 2 00000
- x 1 00001
- u 1 00110
- r 1 00111
- p 1 01000
- l 1 01001
- )")
- .substr(1);
- EXPECT_EQ(expected, ss.str());
- }
- TEST(Huffman, TestValidity) {
- HuffmanCodec<std::string> huffman(GetTestSet());
- const auto& encoding_table = huffman.GetEncodingTable();
- std::vector<std::string> codes;
- for (const auto& entry : encoding_table) {
- codes.push_back(BitsToStream(entry.second.first, entry.second.second));
- }
- std::sort(codes.begin(), codes.end());
- ASSERT_LT(codes.size(), 20u) << "Inefficient test ahead";
- for (size_t i = 0; i < codes.size(); ++i) {
- for (size_t j = i + 1; j < codes.size(); ++j) {
- ASSERT_FALSE(codes[i] == codes[j].substr(0, codes[i].length()))
- << codes[i] << " is prefix of " << codes[j];
- }
- }
- }
- TEST(Huffman, TestEncode) {
- HuffmanCodec<std::string> huffman(GetTestSet());
- uint64_t bits = 0;
- size_t num_bits = 0;
- EXPECT_TRUE(huffman.Encode("e", &bits, &num_bits));
- EXPECT_EQ(2u, num_bits);
- EXPECT_EQ("11", BitsToStream(bits, num_bits));
- EXPECT_TRUE(huffman.Encode("a", &bits, &num_bits));
- EXPECT_EQ(3u, num_bits);
- EXPECT_EQ("101", BitsToStream(bits, num_bits));
- EXPECT_TRUE(huffman.Encode("x", &bits, &num_bits));
- EXPECT_EQ(5u, num_bits);
- EXPECT_EQ("00001", BitsToStream(bits, num_bits));
- EXPECT_FALSE(huffman.Encode("y", &bits, &num_bits));
- }
- TEST(Huffman, TestDecode) {
- HuffmanCodec<std::string> huffman(GetTestSet());
- TestBitReader bit_reader(
- "01001"
- "0001"
- "1000"
- "00110"
- "00001"
- "00");
- auto read_bit = [&bit_reader](bool* bit) { return bit_reader.ReadBit(bit); };
- std::string decoded;
- ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
- EXPECT_EQ("l", decoded);
- ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
- EXPECT_EQ("i", decoded);
- ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
- EXPECT_EQ("n", decoded);
- ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
- EXPECT_EQ("u", decoded);
- ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
- EXPECT_EQ("x", decoded);
- ASSERT_FALSE(huffman.DecodeFromStream(read_bit, &decoded));
- }
- TEST(Huffman, TestDecodeNumbers) {
- const std::map<uint32_t, uint32_t> hist = {{1, 10}, {2, 5}, {3, 15}};
- HuffmanCodec<uint32_t> huffman(hist);
- TestBitReader bit_reader(
- "1"
- "1"
- "01"
- "00"
- "01"
- "1");
- auto read_bit = [&bit_reader](bool* bit) { return bit_reader.ReadBit(bit); };
- uint32_t decoded;
- ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
- EXPECT_EQ(3u, decoded);
- ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
- EXPECT_EQ(3u, decoded);
- ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
- EXPECT_EQ(2u, decoded);
- ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
- EXPECT_EQ(1u, decoded);
- ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
- EXPECT_EQ(2u, decoded);
- ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
- EXPECT_EQ(3u, decoded);
- }
- TEST(Huffman, SerializeToTextU64) {
- const std::map<uint64_t, uint32_t> hist = {{1001, 10}, {1002, 5}, {1003, 15}};
- HuffmanCodec<uint64_t> huffman(hist);
- const std::string code = huffman.SerializeToText(2);
- const std::string expected = R"((5, {
- {0, 0, 0},
- {1001, 0, 0},
- {1002, 0, 0},
- {1003, 0, 0},
- {0, 1, 2},
- {0, 4, 3},
- }))";
- ASSERT_EQ(expected, code);
- }
- TEST(Huffman, SerializeToTextString) {
- const std::map<std::string, uint32_t> hist = {
- {"aaa", 10}, {"bbb", 20}, {"ccc", 15}};
- HuffmanCodec<std::string> huffman(hist);
- const std::string code = huffman.SerializeToText(4);
- const std::string expected = R"((5, {
- {"", 0, 0},
- {"aaa", 0, 0},
- {"bbb", 0, 0},
- {"ccc", 0, 0},
- {"", 3, 1},
- {"", 4, 2},
- }))";
- ASSERT_EQ(expected, code);
- }
- TEST(Huffman, CreateFromTextString) {
- std::vector<HuffmanCodec<std::string>::Node> nodes = {
- {},
- {"root", 2, 3},
- {"left", 0, 0},
- {"right", 0, 0},
- };
- HuffmanCodec<std::string> huffman(1, std::move(nodes));
- std::stringstream ss;
- huffman.PrintTree(ss);
- const std::string expected = std::string(R"(
- 0------right
- 0------left
- )")
- .substr(1);
- EXPECT_EQ(expected, ss.str());
- }
- TEST(Huffman, CreateFromTextU64) {
- HuffmanCodec<uint64_t> huffman(5, {
- {0, 0, 0},
- {1001, 0, 0},
- {1002, 0, 0},
- {1003, 0, 0},
- {0, 1, 2},
- {0, 4, 3},
- });
- std::stringstream ss;
- huffman.PrintTree(ss);
- const std::string expected = std::string(R"(
- 0------1003
- 0------0------1002
- 0------1001
- )")
- .substr(1);
- EXPECT_EQ(expected, ss.str());
- TestBitReader bit_reader("01");
- auto read_bit = [&bit_reader](bool* bit) { return bit_reader.ReadBit(bit); };
- uint64_t decoded = 0;
- ASSERT_TRUE(huffman.DecodeFromStream(read_bit, &decoded));
- EXPECT_EQ(1002u, decoded);
- uint64_t bits = 0;
- size_t num_bits = 0;
- EXPECT_TRUE(huffman.Encode(1001, &bits, &num_bits));
- EXPECT_EQ(2u, num_bits);
- EXPECT_EQ("00", BitsToStream(bits, num_bits));
- }
- } // namespace
- } // namespace comp
- } // namespace spvtools
|