summaryrefslogtreecommitdiffstatshomepage
path: root/3rdparty/bgfx/3rdparty/spirv-tools/test/huffman_codec.cpp
diff options
context:
space:
mode:
Diffstat (limited to '3rdparty/bgfx/3rdparty/spirv-tools/test/huffman_codec.cpp')
-rw-r--r--3rdparty/bgfx/3rdparty/spirv-tools/test/huffman_codec.cpp317
1 files changed, 0 insertions, 317 deletions
diff --git a/3rdparty/bgfx/3rdparty/spirv-tools/test/huffman_codec.cpp b/3rdparty/bgfx/3rdparty/spirv-tools/test/huffman_codec.cpp
deleted file mode 100644
index 58a78106133..00000000000
--- a/3rdparty/bgfx/3rdparty/spirv-tools/test/huffman_codec.cpp
+++ /dev/null
@@ -1,317 +0,0 @@
-// 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