1 // Copyright 2016 The Chromium Authors. All rights reserved.
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 "quiche/http2/hpack/huffman/hpack_huffman_decoder.h"
6
7 // Tests of HpackHuffmanDecoder and HuffmanBitBuffer.
8
9 #include <cstddef>
10 #include <iostream>
11 #include <string>
12
13 #include "absl/base/macros.h"
14 #include "absl/strings/escaping.h"
15 #include "quiche/http2/decoder/decode_buffer.h"
16 #include "quiche/http2/decoder/decode_status.h"
17 #include "quiche/http2/test_tools/random_decoder_test_base.h"
18 #include "quiche/common/platform/api/quiche_expect_bug.h"
19 #include "quiche/common/platform/api/quiche_test.h"
20
21 namespace http2 {
22 namespace test {
23 namespace {
24
TEST(HuffmanBitBufferTest,Reset)25 TEST(HuffmanBitBufferTest, Reset) {
26 HuffmanBitBuffer bb;
27 EXPECT_TRUE(bb.IsEmpty());
28 EXPECT_TRUE(bb.InputProperlyTerminated());
29 EXPECT_EQ(bb.count(), 0u);
30 EXPECT_EQ(bb.free_count(), 64u);
31 EXPECT_EQ(bb.value(), 0u);
32 }
33
TEST(HuffmanBitBufferTest,AppendBytesAligned)34 TEST(HuffmanBitBufferTest, AppendBytesAligned) {
35 std::string s;
36 s.push_back('\x11');
37 s.push_back('\x22');
38 s.push_back('\x33');
39 absl::string_view sp(s);
40
41 HuffmanBitBuffer bb;
42 sp.remove_prefix(bb.AppendBytes(sp));
43 EXPECT_TRUE(sp.empty());
44 EXPECT_FALSE(bb.IsEmpty()) << bb;
45 EXPECT_FALSE(bb.InputProperlyTerminated());
46 EXPECT_EQ(bb.count(), 24u) << bb;
47 EXPECT_EQ(bb.free_count(), 40u) << bb;
48 EXPECT_EQ(bb.value(), HuffmanAccumulator(0x112233) << 40) << bb;
49
50 s.clear();
51 s.push_back('\x44');
52 sp = s;
53
54 sp.remove_prefix(bb.AppendBytes(sp));
55 EXPECT_TRUE(sp.empty());
56 EXPECT_EQ(bb.count(), 32u) << bb;
57 EXPECT_EQ(bb.free_count(), 32u) << bb;
58 EXPECT_EQ(bb.value(), HuffmanAccumulator(0x11223344) << 32) << bb;
59
60 s.clear();
61 s.push_back('\x55');
62 s.push_back('\x66');
63 s.push_back('\x77');
64 s.push_back('\x88');
65 s.push_back('\x99');
66 sp = s;
67
68 sp.remove_prefix(bb.AppendBytes(sp));
69 EXPECT_EQ(sp.size(), 1u);
70 EXPECT_EQ('\x99', sp[0]);
71 EXPECT_EQ(bb.count(), 64u) << bb;
72 EXPECT_EQ(bb.free_count(), 0u) << bb;
73 EXPECT_EQ(bb.value(), HuffmanAccumulator(0x1122334455667788LL)) << bb;
74
75 sp.remove_prefix(bb.AppendBytes(sp));
76 EXPECT_EQ(sp.size(), 1u);
77 EXPECT_EQ('\x99', sp[0]);
78 EXPECT_EQ(bb.count(), 64u) << bb;
79 EXPECT_EQ(bb.free_count(), 0u) << bb;
80 EXPECT_EQ(bb.value(), HuffmanAccumulator(0x1122334455667788LL)) << bb;
81 }
82
TEST(HuffmanBitBufferTest,ConsumeBits)83 TEST(HuffmanBitBufferTest, ConsumeBits) {
84 std::string s;
85 s.push_back('\x11');
86 s.push_back('\x22');
87 s.push_back('\x33');
88 absl::string_view sp(s);
89
90 HuffmanBitBuffer bb;
91 sp.remove_prefix(bb.AppendBytes(sp));
92 EXPECT_TRUE(sp.empty());
93
94 bb.ConsumeBits(1);
95 EXPECT_EQ(bb.count(), 23u) << bb;
96 EXPECT_EQ(bb.free_count(), 41u) << bb;
97 EXPECT_EQ(bb.value(), HuffmanAccumulator(0x112233) << 41) << bb;
98
99 bb.ConsumeBits(20);
100 EXPECT_EQ(bb.count(), 3u) << bb;
101 EXPECT_EQ(bb.free_count(), 61u) << bb;
102 EXPECT_EQ(bb.value(), HuffmanAccumulator(0x3) << 61) << bb;
103 }
104
TEST(HuffmanBitBufferTest,AppendBytesUnaligned)105 TEST(HuffmanBitBufferTest, AppendBytesUnaligned) {
106 std::string s;
107 s.push_back('\x11');
108 s.push_back('\x22');
109 s.push_back('\x33');
110 s.push_back('\x44');
111 s.push_back('\x55');
112 s.push_back('\x66');
113 s.push_back('\x77');
114 s.push_back('\x88');
115 s.push_back('\x99');
116 s.push_back('\xaa');
117 s.push_back('\xbb');
118 s.push_back('\xcc');
119 s.push_back('\xdd');
120 absl::string_view sp(s);
121
122 HuffmanBitBuffer bb;
123 sp.remove_prefix(bb.AppendBytes(sp));
124 EXPECT_EQ(sp.size(), 5u);
125 EXPECT_FALSE(bb.InputProperlyTerminated());
126
127 bb.ConsumeBits(15);
128 EXPECT_EQ(bb.count(), 49u) << bb;
129 EXPECT_EQ(bb.free_count(), 15u) << bb;
130
131 HuffmanAccumulator expected(0x1122334455667788);
132 expected <<= 15;
133 EXPECT_EQ(bb.value(), expected);
134
135 sp.remove_prefix(bb.AppendBytes(sp));
136 EXPECT_EQ(sp.size(), 4u);
137 EXPECT_EQ(bb.count(), 57u) << bb;
138 EXPECT_EQ(bb.free_count(), 7u) << bb;
139
140 expected |= (HuffmanAccumulator(0x99) << 7);
141 EXPECT_EQ(bb.value(), expected)
142 << bb << std::hex << "\n actual: " << bb.value()
143 << "\n expected: " << expected;
144 }
145
146 class HpackHuffmanDecoderTest : public RandomDecoderTest {
147 protected:
HpackHuffmanDecoderTest()148 HpackHuffmanDecoderTest() {
149 // The decoder may return true, and its accumulator may be empty, at
150 // many boundaries while decoding, and yet the whole string hasn't
151 // been decoded.
152 stop_decode_on_done_ = false;
153 }
154
StartDecoding(DecodeBuffer * b)155 DecodeStatus StartDecoding(DecodeBuffer* b) override {
156 input_bytes_seen_ = 0;
157 output_buffer_.clear();
158 decoder_.Reset();
159 return ResumeDecoding(b);
160 }
161
ResumeDecoding(DecodeBuffer * b)162 DecodeStatus ResumeDecoding(DecodeBuffer* b) override {
163 input_bytes_seen_ += b->Remaining();
164 absl::string_view sp(b->cursor(), b->Remaining());
165 if (decoder_.Decode(sp, &output_buffer_)) {
166 b->AdvanceCursor(b->Remaining());
167 // Successfully decoded (or buffered) the bytes in absl::string_view.
168 EXPECT_LE(input_bytes_seen_, input_bytes_expected_);
169 // Have we reached the end of the encoded string?
170 if (input_bytes_expected_ == input_bytes_seen_) {
171 if (decoder_.InputProperlyTerminated()) {
172 return DecodeStatus::kDecodeDone;
173 } else {
174 return DecodeStatus::kDecodeError;
175 }
176 }
177 return DecodeStatus::kDecodeInProgress;
178 }
179 return DecodeStatus::kDecodeError;
180 }
181
182 HpackHuffmanDecoder decoder_;
183 std::string output_buffer_;
184 size_t input_bytes_seen_;
185 size_t input_bytes_expected_;
186 };
187
TEST_F(HpackHuffmanDecoderTest,SpecRequestExamples)188 TEST_F(HpackHuffmanDecoderTest, SpecRequestExamples) {
189 HpackHuffmanDecoder decoder;
190 std::string test_table[] = {
191 "f1e3c2e5f23a6ba0ab90f4ff",
192 "www.example.com",
193
194 "a8eb10649cbf",
195 "no-cache",
196
197 "25a849e95ba97d7f",
198 "custom-key",
199
200 "25a849e95bb8e8b4bf",
201 "custom-value",
202 };
203 for (size_t i = 0; i != ABSL_ARRAYSIZE(test_table); i += 2) {
204 std::string huffman_encoded;
205 ASSERT_TRUE(absl::HexStringToBytes(test_table[i], &huffman_encoded));
206 const std::string& plain_string(test_table[i + 1]);
207 std::string buffer;
208 decoder.Reset();
209 EXPECT_TRUE(decoder.Decode(huffman_encoded, &buffer)) << decoder;
210 EXPECT_TRUE(decoder.InputProperlyTerminated()) << decoder;
211 EXPECT_EQ(buffer, plain_string);
212 }
213 }
214
TEST_F(HpackHuffmanDecoderTest,SpecResponseExamples)215 TEST_F(HpackHuffmanDecoderTest, SpecResponseExamples) {
216 HpackHuffmanDecoder decoder;
217 std::string test_table[] = {
218 "6402",
219 "302",
220
221 "aec3771a4b",
222 "private",
223
224 "d07abe941054d444a8200595040b8166e082a62d1bff",
225 "Mon, 21 Oct 2013 20:13:21 GMT",
226
227 "9d29ad171863c78f0b97c8e9ae82ae43d3",
228 "https://www.example.com",
229
230 "94e7821dd7f2e6c7b335dfdfcd5b3960d5af27087f3672c1ab270fb5291f9587316065c0"
231 "03ed4ee5b1063d5007",
232 "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1",
233 };
234 for (size_t i = 0; i != ABSL_ARRAYSIZE(test_table); i += 2) {
235 std::string huffman_encoded;
236 ASSERT_TRUE(absl::HexStringToBytes(test_table[i], &huffman_encoded));
237 const std::string& plain_string(test_table[i + 1]);
238 std::string buffer;
239 decoder.Reset();
240 EXPECT_TRUE(decoder.Decode(huffman_encoded, &buffer)) << decoder;
241 EXPECT_TRUE(decoder.InputProperlyTerminated()) << decoder;
242 EXPECT_EQ(buffer, plain_string);
243 }
244 }
245
246 } // namespace
247 } // namespace test
248 } // namespace http2
249