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/trie/trie_bit_buffer.h"
6 #include "net/tools/huffman_trie/bit_writer.h"
7 #include "net/tools/huffman_trie/huffman/huffman_builder.h"
8 #include "testing/gmock/include/gmock/gmock.h"
9 #include "testing/gtest/include/gtest/gtest.h"
10
11 namespace net::huffman_trie {
12
13 namespace {
14
15 // Test writing single bits to the buffer.
TEST(TrieBitBufferTest,WriteBit)16 TEST(TrieBitBufferTest, WriteBit) {
17 TrieBitBuffer buffer;
18
19 buffer.WriteBit(0);
20 buffer.WriteBit(1);
21 buffer.WriteBit(0);
22 buffer.WriteBit(1);
23 buffer.WriteBit(0);
24 buffer.WriteBit(1);
25 buffer.WriteBit(0);
26 buffer.WriteBit(1);
27
28 BitWriter writer;
29 buffer.WriteToBitWriter(&writer);
30
31 writer.Flush();
32
33 // 0 + 1 + 0 + 1 + 0 + 1 + 0 + 1 = 0x55
34 EXPECT_THAT(writer.bytes(), testing::ElementsAre(0x55, 0x0));
35 EXPECT_EQ(16U, writer.position());
36
37 buffer.WriteBit(0);
38 buffer.WriteBit(1);
39 buffer.WriteBit(0);
40
41 BitWriter writer2;
42 buffer.WriteToBitWriter(&writer2);
43 EXPECT_EQ(11U, writer2.position());
44
45 writer2.Flush();
46
47 // 0 + 1 + 0 + 1 + 0 + 1 + 0 + 1 + 0 + 1 + 0 + 00000 (padding) = 0x5540.
48 EXPECT_THAT(writer2.bytes(), testing::ElementsAre(0x55, 0x40));
49 }
50
51 // Test writing multiple bits at once. Specifically, that the correct bits are
52 // written and byte boundaries are respected.
TEST(TrieBitBufferTest,WriteBits)53 TEST(TrieBitBufferTest, WriteBits) {
54 TrieBitBuffer buffer;
55
56 // 0xAA is 10101010 in binary. WritBits will write the n least significant
57 // bits where n is given as the second parameter.
58 buffer.WriteBits(0xAA, 1);
59 buffer.WriteBits(0xAA, 2);
60 buffer.WriteBits(0xAA, 3);
61
62 BitWriter writer;
63 buffer.WriteToBitWriter(&writer);
64 EXPECT_EQ(6U, writer.position());
65
66 writer.Flush();
67
68 // 0 + 10 + 010 + 00 (padding) = 0x48
69 EXPECT_THAT(writer.bytes(), testing::ElementsAre(0x48));
70
71 buffer.WriteBits(0xAA, 2);
72 buffer.WriteBits(0xAA, 2);
73
74 BitWriter writer2;
75 buffer.WriteToBitWriter(&writer2);
76 EXPECT_EQ(10U, writer2.position());
77
78 writer2.Flush();
79
80 // 0 + 10 + 010 + 10 + 10 + 000000 (padding) = 0x4A80.
81 EXPECT_THAT(writer2.bytes(), testing::ElementsAre(0x4A, 0x80));
82
83 buffer.WriteBits(0xAA, 2);
84
85 BitWriter writer3;
86 buffer.WriteToBitWriter(&writer3);
87 EXPECT_EQ(12U, writer3.position());
88
89 writer3.Flush();
90
91 // 0 + 10 + 010 + 10 + 10 + 10 + 0000 (padding) = 0x4AA0.
92 EXPECT_THAT(writer3.bytes(), testing::ElementsAre(0x4A, 0xA0));
93 }
94
95 // Test writing position (delta's).
TEST(TrieBitBufferTest,WritePosition)96 TEST(TrieBitBufferTest, WritePosition) {
97 TrieBitBuffer buffer;
98 BitWriter writer;
99
100 buffer.WriteBit(1);
101 // 0xAA is 10101010 in binary. WritBits will write the n least significant
102 // bits where n is given as the second parameter.
103 buffer.WriteBits(0xAA, 6);
104
105 buffer.WriteToBitWriter(&writer);
106
107 TrieBitBuffer buffer2;
108 int32_t last_position = -1;
109 buffer2.WritePosition(4, &last_position);
110 EXPECT_EQ(4, last_position);
111
112 buffer2.WriteBits(0xAA, 8);
113 buffer2.WritePosition(8, &last_position);
114 EXPECT_EQ(8, last_position);
115
116 buffer2.WriteToBitWriter(&writer);
117 writer.Flush();
118
119 EXPECT_EQ(4U, writer.bytes().size());
120
121 // The buffer should contain, in order:
122 // - the bit 1
123 // - the last 6 bits of '0xAA'
124 // - five bits representing '2'; the bit length of the following field
125 // - 2 bits representing '3' (the delta 7 - 4)
126 // - 8 bits representing 0xAA
127 // - A zero indicating the following 7 bits represent a delta
128 // - 7 bits representing 4 (the delta 8 - 4)
129 // - padding
130 //
131 // 1 + 101010 + 00010 + 11 + 10101010 + 0 + 0000100 + 00 (padding)
132 EXPECT_THAT(writer.bytes(), testing::ElementsAre(0xD4, 0x2E, 0xA8, 0x10));
133 }
134
135 // Test writing characters to the buffer using Huffman.
TEST(TrieBitBufferTest,WriteChar)136 TEST(TrieBitBufferTest, WriteChar) {
137 TrieBitBuffer buffer;
138 HuffmanBuilder huffman_builder;
139 HuffmanRepresentationTable table;
140
141 table['a'] = HuffmanRepresentation();
142 table['a'].bits = 0x0A;
143 table['a'].number_of_bits = 4;
144
145 table['b'] = HuffmanRepresentation();
146 table['b'].bits = 0x0F;
147 table['b'].number_of_bits = 4;
148
149 buffer.WriteChar('a', table, &huffman_builder);
150
151 HuffmanRepresentationTable encoding = huffman_builder.ToTable();
152
153 // 'a' should have a Huffman encoding.
154 EXPECT_NE(encoding.cend(), encoding.find('a'));
155
156 buffer.WriteChar('a', table, &huffman_builder);
157 buffer.WriteChar('b', table, &huffman_builder);
158
159 encoding = huffman_builder.ToTable();
160
161 // Both 'a' and 'b' should have a Huffman encoding.
162 EXPECT_NE(encoding.cend(), encoding.find('a'));
163 EXPECT_NE(encoding.cend(), encoding.find('b'));
164
165 BitWriter writer;
166 buffer.WriteToBitWriter(&writer);
167 writer.Flush();
168
169 // There should be 3 characters in the writer. 'a' twice followed by 'b' once.
170 // The characters are written as the representation in |table|.
171 EXPECT_EQ(2U, writer.bytes().size());
172
173 // Twice 'a', once 'b' and padding
174 EXPECT_THAT(writer.bytes(), testing::ElementsAre(0xAA, 0xF0));
175 }
176
177 // Test writing a mix of items. Specifically, that the correct values are
178 // written in the correct order and byte boundaries are respected.
TEST(TrieBitBufferTest,WriteMix)179 TEST(TrieBitBufferTest, WriteMix) {
180 TrieBitBuffer buffer;
181
182 HuffmanRepresentationTable table;
183 table['a'] = HuffmanRepresentation();
184 table['a'].bits = 0x0A;
185 table['a'].number_of_bits = 4;
186
187 // 0xAA is 10101010 in binary. WritBits will write the n least significant
188 // bits where n is given as the second parameter.
189 buffer.WriteBits(0xAA, 1);
190 buffer.WriteBit(1);
191
192 buffer.WriteChar('a', table, nullptr);
193
194 buffer.WriteBits(0xAA, 2);
195 buffer.WriteBits(0xAA, 3);
196
197 BitWriter writer;
198 buffer.WriteToBitWriter(&writer);
199
200 // 1 + 1 + 4 + 2 + 3 = 11.
201 EXPECT_EQ(writer.position(), 11U);
202
203 TrieBitBuffer buffer2;
204 buffer2.WriteBit(1);
205 buffer2.WriteBits(0xAA, 2);
206 buffer2.WriteBit(0);
207
208 buffer2.WriteToBitWriter(&writer);
209 EXPECT_EQ(writer.position(), 15U);
210 EXPECT_EQ(writer.bytes().size(), 1U);
211
212 writer.Flush();
213
214 EXPECT_EQ(writer.bytes().size(), 2U);
215
216 // 0 + 1 + 1010 + 10 + 010 + 1 + 10 + 0 + 0 (padding) = 0x6A58.
217 EXPECT_THAT(writer.bytes(), testing::ElementsAre(0x6A, 0x58));
218 }
219
220 } // namespace
221
222 } // namespace net::huffman_trie
223