1 // Copyright 2017 The Chromium Authors
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "net/tools/huffman_trie/huffman/huffman_builder.h"
6 #include "testing/gmock/include/gmock/gmock.h"
7 #include "testing/gtest/include/gtest/gtest.h"
8
9 namespace net::huffman_trie {
10
11 namespace {
12
13 // Test that there are no Huffman representations that are a prefix for another.
TEST(HuffmanBuilderTest,NoPrefixCollision)14 TEST(HuffmanBuilderTest, NoPrefixCollision) {
15 HuffmanBuilder builder;
16 HuffmanRepresentationTable encoding;
17 for (uint8_t i = 0; i <= 127; i++) {
18 // Make sure all values have an identical count to at least some other
19 // values.
20 for (uint8_t j = 0; j <= i % 32; j++) {
21 builder.RecordUsage(i);
22 }
23 }
24
25 encoding = builder.ToTable();
26 for (uint8_t i = 0; i <= 127; i++) {
27 // There should never exist a representation that is a prefix for, or
28 // identical to, another.
29 uint32_t mask = 0;
30 for (uint32_t k = 0; k <= encoding[i].number_of_bits; k++) {
31 mask = (mask << 1) | 1;
32 }
33 mask = mask << (32 - encoding[i].number_of_bits);
34
35 for (uint8_t j = 0; j <= 127; j++) {
36 if (i == j) {
37 continue;
38 }
39
40 uint32_t aligned_i = encoding[i].bits
41 << (32 - encoding[i].number_of_bits);
42 uint32_t aligned_j = encoding[j].bits
43 << (32 - encoding[j].number_of_bits);
44 EXPECT_NE(aligned_i, aligned_j & mask);
45 }
46 }
47 }
48
49 // Test that all recorded characters get a representation and that no other
50 // representations are created.
51 // Note: There is an exception for encodings with less than 2 unique inputs.
TEST(HuffmanBuilderTest,NoMissingInputs)52 TEST(HuffmanBuilderTest, NoMissingInputs) {
53 HuffmanBuilder builder;
54 HuffmanRepresentationTable encoding;
55 for (uint8_t i = 0; i <= 127; i++) {
56 if (i % 2) {
57 for (uint8_t j = 0; j <= i % 5; j++) {
58 builder.RecordUsage(i);
59 }
60 }
61 }
62
63 encoding = builder.ToTable();
64 for (uint8_t i = 0; i <= 127; i++) {
65 if (i % 2) {
66 EXPECT_NE(encoding.find(i), encoding.cend());
67 } else {
68 EXPECT_EQ(encoding.find(i), encoding.cend());
69 }
70 }
71 }
72
73 // Test that the representations have optimal order by checking that characters
74 // with higher counts get shorter (or equal length) representations than those
75 // with lower counts.
TEST(HuffmanBuilderTest,OptimalCodeOrder)76 TEST(HuffmanBuilderTest, OptimalCodeOrder) {
77 HuffmanBuilder builder;
78 HuffmanRepresentationTable encoding;
79 for (uint8_t i = 0; i <= 127; i++) {
80 for (uint8_t j = 0; j <= (i + 1); j++) {
81 builder.RecordUsage(i);
82 }
83 }
84
85 encoding = builder.ToTable();
86 for (uint8_t i = 0; i <= 127; i++) {
87 // The representation for |i| should be longer or have the same length as
88 // all following representations because they have a higher frequency and
89 // therefor should never get a longer representation.
90 for (uint8_t j = i; j <= 127; j++) {
91 // A representation for the values should exist in the table.
92 ASSERT_NE(encoding.find(i), encoding.cend());
93 ASSERT_NE(encoding.find(j), encoding.cend());
94
95 EXPECT_GE(encoding[i].number_of_bits, encoding[j].number_of_bits);
96 }
97 }
98 }
99
100 // Test that the ToVector() creates a byte vector that represents the expected
101 // Huffman Tree.
TEST(HuffmanBuilderTest,ToVector)102 TEST(HuffmanBuilderTest, ToVector) {
103 // Build a small tree.
104 HuffmanBuilder builder;
105 builder.RecordUsage('a');
106 builder.RecordUsage('b');
107 builder.RecordUsage('b');
108 builder.RecordUsage('c');
109 builder.RecordUsage('c');
110 builder.RecordUsage('d');
111 builder.RecordUsage('d');
112 builder.RecordUsage('d');
113 builder.RecordUsage('e');
114 builder.RecordUsage('e');
115 builder.RecordUsage('e');
116
117 std::vector<uint8_t> output = builder.ToVector();
118
119 // This represents 4 nodes (4 groups of 2 uint8_t's) which, when decoded,
120 // yields the expected Huffman Tree:
121 // root (node 3)
122 // / \
123 // node 1 node 2
124 // / \ / \
125 // 0xE3 (c) node 0 0xE4 (d) 0xE5 (e)
126 // / \
127 // 0xE1 (a) 0xE2 (b)
128 EXPECT_THAT(output, testing::ElementsAre(0xE1, 0xE2, 0xE3, 0x0, 0xE4, 0xE5,
129 0x1, 0x2));
130 }
131
132 // The ToVector() logic requires at least 2 unique inputs to construct the
133 // vector. Test that nodes are appended when there are less than 2 unique
134 // inputs.
TEST(HuffmanBuilderTest,ToVectorSingle)135 TEST(HuffmanBuilderTest, ToVectorSingle) {
136 // Build a single element tree. Another element should be added automatically.
137 HuffmanBuilder builder;
138 builder.RecordUsage('a');
139
140 std::vector<uint8_t> output = builder.ToVector();
141
142 // This represents 1 node (1 group of 2 uint8_t's) which, when decoded,
143 // yields the expected Huffman Tree:
144 // root (node 0)
145 // / \
146 // 0x80 (\0) 0xE1 (a)
147 //
148 // Note: the node \0 node was appended to the tree.
149 EXPECT_THAT(output, testing::ElementsAre(0x80, 0xE1));
150 }
151
152 } // namespace
153
154 } // namespace net::huffman_trie
155