OLD | NEW |
| (Empty) |
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 "net/http2/hpack/decoder/hpack_varint_decoder.h" | |
6 | |
7 // Tests of HpackVarintDecoder. | |
8 | |
9 #include <stddef.h> | |
10 | |
11 #include <ios> | |
12 #include <iterator> | |
13 #include <ostream> | |
14 #include <set> | |
15 #include <sstream> | |
16 #include <vector> | |
17 | |
18 #include "base/bind.h" | |
19 #include "base/bind_helpers.h" | |
20 #include "base/logging.h" | |
21 #include "base/strings/string_number_conversions.h" | |
22 #include "base/strings/string_piece.h" | |
23 #include "base/strings/stringprintf.h" | |
24 #include "net/http2/hpack/tools/hpack_block_builder.h" | |
25 #include "net/http2/tools/failure.h" | |
26 #include "net/http2/tools/http2_random.h" | |
27 #include "net/http2/tools/random_decoder_test.h" | |
28 #include "testing/gtest/include/gtest/gtest.h" | |
29 | |
30 using ::testing::AssertionFailure; | |
31 using ::testing::AssertionSuccess; | |
32 using base::StringPiece; | |
33 using base::StringPrintf; | |
34 using std::string; | |
35 | |
36 namespace net { | |
37 namespace test { | |
38 namespace { | |
39 | |
40 class HpackVarintDecoderTest : public RandomDecoderTest { | |
41 public: | |
42 AssertionResult ValidatorForValueTooLarge(bool* validated, | |
43 uint32_t expected_offset, | |
44 const DecodeBuffer& db, | |
45 DecodeStatus status) { | |
46 *validated = true; | |
47 VERIFY_EQ(DecodeStatus::kDecodeError, status); | |
48 VERIFY_EQ(expected_offset, db.Offset()); | |
49 return AssertionSuccess(); | |
50 } | |
51 | |
52 protected: | |
53 DecodeStatus StartDecoding(DecodeBuffer* b) override { | |
54 CHECK_LT(0u, b->Remaining()); | |
55 CHECK_NE(0, prefix_mask_); | |
56 uint8_t prefix = b->DecodeUInt8(); | |
57 return decoder_.Start(prefix, prefix_mask_, b); | |
58 } | |
59 | |
60 DecodeStatus ResumeDecoding(DecodeBuffer* b) override { | |
61 return decoder_.Resume(b); | |
62 } | |
63 | |
64 AssertionResult ValidatorForDecodeSeveralWays(uint32_t expected_value, | |
65 const DecodeBuffer& db, | |
66 DecodeStatus status) { | |
67 if (decoder_.value() != expected_value) { | |
68 return AssertionFailure() | |
69 << "Value doesn't match expected: " << decoder_.value() | |
70 << " != " << expected_value; | |
71 } | |
72 return AssertionSuccess(); | |
73 } | |
74 | |
75 void DecodeSeveralWays(uint32_t expected_value, uint32_t expected_offset) { | |
76 // The validator is called after each of the several times that the input | |
77 // DecodeBuffer is decoded, each with a different segmentation of the input. | |
78 // Validate that decoder_.value() matches the expected value. | |
79 Validator validator = | |
80 base::Bind(&HpackVarintDecoderTest::ValidatorForDecodeSeveralWays, | |
81 base::Unretained(this), expected_value); | |
82 | |
83 // First validate that decoding is done and that we've advanced the cursor | |
84 // the expected amount. | |
85 validator = ValidateDoneAndOffset(expected_offset, validator); | |
86 | |
87 // StartDecoding, above, requires the DecodeBuffer be non-empty so that it | |
88 // can call Start with the prefix byte. | |
89 bool return_non_zero_on_first = true; | |
90 | |
91 DecodeBuffer b(buffer_); | |
92 EXPECT_TRUE( | |
93 DecodeAndValidateSeveralWays(&b, return_non_zero_on_first, validator)); | |
94 | |
95 EXPECT_EQ(expected_value, decoder_.value()); | |
96 EXPECT_EQ(expected_offset, b.Offset()); | |
97 } | |
98 | |
99 void EncodeNoRandom(uint32_t value, uint8_t prefix_length) { | |
100 DCHECK_LE(4, prefix_length); | |
101 DCHECK_LE(prefix_length, 7); | |
102 prefix_length_ = prefix_length; | |
103 | |
104 HpackBlockBuilder bb; | |
105 bb.AppendHighBitsAndVarint(0, prefix_length_, value); | |
106 buffer_ = bb.buffer(); | |
107 ASSERT_LT(0u, buffer_.size()); | |
108 | |
109 // Note: setting member variable prefix_mask_ here, which will be read | |
110 // in StartDecoding above. | |
111 prefix_mask_ = (1 << prefix_length_) - 1; | |
112 ASSERT_EQ(buffer_[0], buffer_[0] & prefix_mask_); | |
113 } | |
114 | |
115 void Encode(uint32_t value, uint8_t prefix_length) { | |
116 EncodeNoRandom(value, prefix_length); | |
117 // Add some random bits to the prefix (the first byte) above the mask. | |
118 uint8_t prefix = buffer_[0]; | |
119 buffer_[0] = prefix | (Random().Rand8() << prefix_length); | |
120 ASSERT_EQ(prefix, buffer_[0] & prefix_mask_); | |
121 } | |
122 | |
123 // This is really a test of HpackBlockBuilder, making sure that the input to | |
124 // HpackVarintDecoder is as expected, which also acts as confirmation that | |
125 // my thinking about the encodings being used by the tests, i.e. cover the | |
126 // range desired. | |
127 void ValidateEncoding(uint32_t value, | |
128 uint32_t minimum, | |
129 uint32_t maximum, | |
130 size_t expected_bytes) { | |
131 ASSERT_EQ(expected_bytes, buffer_.size()); | |
132 if (expected_bytes > 1) { | |
133 EXPECT_EQ(prefix_mask_, buffer_[0] & prefix_mask_); | |
134 size_t last = expected_bytes - 1; | |
135 for (size_t ndx = 1; ndx < last; ++ndx) { | |
136 // Before the last extension byte, we expect the high-bit set. | |
137 uint8_t byte = buffer_[ndx]; | |
138 if (value == minimum) { | |
139 EXPECT_EQ(0x80, byte) << "ndx=" << ndx; | |
140 } else if (value == maximum) { | |
141 EXPECT_EQ(0xff, byte) << "ndx=" << ndx; | |
142 } else { | |
143 EXPECT_EQ(0x80, byte & 0x80) << "ndx=" << ndx; | |
144 } | |
145 } | |
146 // The last extension byte should not have the high-bit set. | |
147 uint8_t byte = buffer_[last]; | |
148 if (value == minimum) { | |
149 if (expected_bytes == 2) { | |
150 EXPECT_EQ(0x00, byte); | |
151 } else { | |
152 EXPECT_EQ(0x01, byte); | |
153 } | |
154 } else if (value == maximum) { | |
155 EXPECT_EQ(0x7f, byte); | |
156 } else { | |
157 EXPECT_EQ(0x00, byte & 0x80); | |
158 } | |
159 } else { | |
160 EXPECT_EQ(value, static_cast<uint32_t>(buffer_[0] & prefix_mask_)); | |
161 EXPECT_LT(value, static_cast<uint32_t>(prefix_mask_)); | |
162 } | |
163 } | |
164 | |
165 void EncodeAndDecodeValues(const std::set<uint32_t>& values, | |
166 uint8_t prefix_length, | |
167 size_t expected_bytes) { | |
168 CHECK(!values.empty()); | |
169 const uint32_t minimum = *values.begin(); | |
170 const uint32_t maximum = *values.rbegin(); | |
171 for (const uint32_t value : values) { | |
172 Encode(value, prefix_length); // Sets prefix_mask_ and buffer_ | |
173 | |
174 std::stringstream ss; | |
175 ss << "value=" << value << " (0x" << std::hex << value | |
176 << "), prefix_length=" << std::dec << prefix_length | |
177 << ", expected_bytes=" << expected_bytes << std::endl | |
178 << HexEncode(buffer_); | |
179 string msg(ss.str()); | |
180 | |
181 if (value == minimum) { | |
182 LOG(INFO) << "Checking minimum; " << msg; | |
183 } else if (value == maximum) { | |
184 LOG(INFO) << "Checking maximum; " << msg; | |
185 } | |
186 | |
187 SCOPED_TRACE(msg); | |
188 ValidateEncoding(value, minimum, maximum, expected_bytes); | |
189 DecodeSeveralWays(value, expected_bytes); | |
190 | |
191 // Append some random data to the end of buffer_ and repeat. That random | |
192 // data should be ignored. | |
193 buffer_.append(Random().RandString(1 + Random().Uniform(10))); | |
194 DecodeSeveralWays(value, expected_bytes); | |
195 | |
196 // If possible, add extension bytes that don't change the value. | |
197 if (1 < expected_bytes) { | |
198 buffer_.resize(expected_bytes); | |
199 for (uint8_t total_bytes = expected_bytes + 1; total_bytes <= 6; | |
200 ++total_bytes) { | |
201 // Mark the current last byte as not being the last one. | |
202 EXPECT_EQ(0x00, 0x80 & buffer_.back()); | |
203 buffer_.back() |= 0x80; | |
204 buffer_.push_back('\0'); | |
205 DecodeSeveralWays(value, total_bytes); | |
206 } | |
207 } | |
208 } | |
209 } | |
210 | |
211 void EncodeAndDecodeValuesInRange(uint32_t start, | |
212 uint32_t range, | |
213 uint8_t prefix_length, | |
214 size_t expected_bytes) { | |
215 const uint8_t prefix_mask = (1 << prefix_length) - 1; | |
216 const uint32_t beyond = start + range; | |
217 | |
218 LOG(INFO) << "############################################################"; | |
219 LOG(INFO) << "prefix_length=" << static_cast<int>(prefix_length); | |
220 LOG(INFO) << "prefix_mask=" << std::hex << static_cast<int>(prefix_mask); | |
221 LOG(INFO) << "start=" << start << " (" << std::hex << start << ")"; | |
222 LOG(INFO) << "range=" << range << " (" << std::hex << range << ")"; | |
223 LOG(INFO) << "beyond=" << beyond << " (" << std::hex << beyond << ")"; | |
224 LOG(INFO) << "expected_bytes=" << expected_bytes; | |
225 | |
226 // Confirm the claim that beyond requires more bytes. | |
227 Encode(beyond, prefix_length); | |
228 EXPECT_EQ(expected_bytes + 1, buffer_.size()) << HexEncode(buffer_); | |
229 | |
230 std::set<uint32_t> values; | |
231 if (range < 200) { | |
232 // Select all values in the range. | |
233 for (uint32_t offset = 0; offset < range; ++offset) { | |
234 values.insert(start + offset); | |
235 } | |
236 } else { | |
237 // Select some values in this range, including the minimum and maximum | |
238 // values that require exactly |expected_bytes| extension bytes. | |
239 values.insert({start, start + 1, beyond - 2, beyond - 1}); | |
240 while (values.size() < 100) { | |
241 values.insert(start + Random().Rand32() % range); | |
242 } | |
243 } | |
244 | |
245 EncodeAndDecodeValues(values, prefix_length, expected_bytes); | |
246 } | |
247 | |
248 HpackVarintDecoder decoder_; | |
249 string buffer_; | |
250 uint8_t prefix_mask_ = 0; | |
251 uint8_t prefix_length_ = 0; | |
252 }; | |
253 | |
254 // To help me and future debuggers of varint encodings, this LOGs out the | |
255 // transition points where a new extension byte is added. | |
256 TEST_F(HpackVarintDecoderTest, Encode) { | |
257 for (int prefix_length = 4; prefix_length <= 7; ++prefix_length) { | |
258 const uint32_t a = (1 << prefix_length) - 1; | |
259 const uint32_t b = a + 128; | |
260 const uint32_t c = b + (127 << 7); | |
261 const uint32_t d = c + (127 << 14); | |
262 const uint32_t e = d + (127 << 21); | |
263 | |
264 LOG(INFO) << "############################################################"; | |
265 LOG(INFO) << "prefix_length=" << prefix_length << " a=" << a | |
266 << " b=" << b << " c=" << c; | |
267 | |
268 EXPECT_EQ(a - 1, | |
269 HpackVarintDecoder::HiValueOfExtensionBytes(0, prefix_length)); | |
270 EXPECT_EQ(b - 1, | |
271 HpackVarintDecoder::HiValueOfExtensionBytes(1, prefix_length)); | |
272 EXPECT_EQ(c - 1, | |
273 HpackVarintDecoder::HiValueOfExtensionBytes(2, prefix_length)); | |
274 EXPECT_EQ(d - 1, | |
275 HpackVarintDecoder::HiValueOfExtensionBytes(3, prefix_length)); | |
276 EXPECT_EQ(e - 1, | |
277 HpackVarintDecoder::HiValueOfExtensionBytes(4, prefix_length)); | |
278 | |
279 std::vector<uint32_t> values = { | |
280 0, 1, // Force line break. | |
281 a - 2, a - 1, a, a + 1, a + 2, // Force line break. | |
282 b - 2, b - 1, b, b + 1, b + 2, // Force line break. | |
283 c - 2, c - 1, c, c + 1, c + 2, // Force line break. | |
284 d - 2, d - 1, d, d + 1, d + 2, // Force line break. | |
285 e - 2, e - 1, e, e + 1, e + 2 // Force line break. | |
286 }; | |
287 | |
288 for (uint32_t value : values) { | |
289 EncodeNoRandom(value, prefix_length); | |
290 string dump = HexEncode(buffer_); | |
291 LOG(INFO) << StringPrintf("%10u %0#10x ", value, value) | |
292 << HexEncode(buffer_); | |
293 } | |
294 } | |
295 } | |
296 | |
297 TEST_F(HpackVarintDecoderTest, FromSpec1337) { | |
298 DecodeBuffer b(StringPiece("\x1f\x9a\x0a")); | |
299 uint32_t prefix_length = 5; | |
300 uint32_t prefix_mask = (1 << prefix_length) - 1; | |
301 uint8_t p = b.DecodeUInt8(); | |
302 EXPECT_EQ(1u, b.Offset()); | |
303 EXPECT_EQ(DecodeStatus::kDecodeDone, decoder_.Start(p, prefix_mask, &b)); | |
304 EXPECT_EQ(3u, b.Offset()); | |
305 EXPECT_EQ(1337u, decoder_.value()); | |
306 | |
307 EncodeNoRandom(1337, prefix_length); | |
308 EXPECT_EQ(3u, buffer_.size()); | |
309 EXPECT_EQ('\x1f', buffer_[0]); | |
310 EXPECT_EQ('\x9a', buffer_[1]); | |
311 EXPECT_EQ('\x0a', buffer_[2]); | |
312 } | |
313 | |
314 // Test all the values that fit into the prefix (one less than the mask). | |
315 TEST_F(HpackVarintDecoderTest, ValidatePrefixOnly) { | |
316 for (int prefix_length = 4; prefix_length <= 7; ++prefix_length) { | |
317 const uint8_t prefix_mask = (1 << prefix_length) - 1; | |
318 EncodeAndDecodeValuesInRange(0, prefix_mask, prefix_length, 1); | |
319 } | |
320 } | |
321 | |
322 // Test all values that require exactly 1 extension byte. | |
323 TEST_F(HpackVarintDecoderTest, ValidateOneExtensionByte) { | |
324 for (int prefix_length = 4; prefix_length <= 7; ++prefix_length) { | |
325 const uint32_t start = (1 << prefix_length) - 1; | |
326 EncodeAndDecodeValuesInRange(start, 128, prefix_length, 2); | |
327 } | |
328 } | |
329 | |
330 // Test *some* values that require exactly 2 extension bytes. | |
331 TEST_F(HpackVarintDecoderTest, ValidateTwoExtensionBytes) { | |
332 for (int prefix_length = 4; prefix_length <= 7; ++prefix_length) { | |
333 const uint8_t prefix_mask = (1 << prefix_length) - 1; | |
334 const uint32_t start = prefix_mask + 128; | |
335 const uint32_t range = 127 << 7; | |
336 | |
337 EncodeAndDecodeValuesInRange(start, range, prefix_length, 3); | |
338 } | |
339 } | |
340 | |
341 // Test *some* values that require 3 extension bytes. | |
342 TEST_F(HpackVarintDecoderTest, ValidateThreeExtensionBytes) { | |
343 for (int prefix_length = 4; prefix_length <= 7; ++prefix_length) { | |
344 const uint8_t prefix_mask = (1 << prefix_length) - 1; | |
345 const uint32_t start = prefix_mask + 128 + (127 << 7); | |
346 const uint32_t range = 127 << 14; | |
347 | |
348 EncodeAndDecodeValuesInRange(start, range, prefix_length, 4); | |
349 } | |
350 } | |
351 | |
352 // Test *some* values that require 4 extension bytes. | |
353 TEST_F(HpackVarintDecoderTest, ValidateFourExtensionBytes) { | |
354 for (int prefix_length = 4; prefix_length <= 7; ++prefix_length) { | |
355 const uint8_t prefix_mask = (1 << prefix_length) - 1; | |
356 const uint32_t start = prefix_mask + 128 + (127 << 7) + (127 << 14); | |
357 const uint32_t range = 127 << 21; | |
358 | |
359 EncodeAndDecodeValuesInRange(start, range, prefix_length, 5); | |
360 } | |
361 } | |
362 | |
363 // Test *some* values that require too many extension bytes. | |
364 TEST_F(HpackVarintDecoderTest, ValueTooLarge) { | |
365 const uint32_t expected_offset = HpackVarintDecoder::MaxExtensionBytes() + 1; | |
366 for (prefix_length_ = 4; prefix_length_ <= 7; ++prefix_length_) { | |
367 prefix_mask_ = (1 << prefix_length_) - 1; | |
368 uint64_t too_large = HpackVarintDecoder::HiValueOfExtensionBytes( | |
369 HpackVarintDecoder::MaxExtensionBytes() + 3, prefix_length_); | |
370 HpackBlockBuilder bb; | |
371 bb.AppendHighBitsAndVarint(0, prefix_length_, too_large); | |
372 buffer_ = bb.buffer(); | |
373 | |
374 // The validator is called after each of the several times that the input | |
375 // DecodeBuffer is decoded, each with a different segmentation of the input. | |
376 // Validate that decoder_.value() matches the expected value. | |
377 bool validated = false; | |
378 Validator validator = | |
379 base::Bind(&HpackVarintDecoderTest::ValidatorForValueTooLarge, | |
380 base::Unretained(this), &validated, expected_offset); | |
381 | |
382 // StartDecoding, above, requires the DecodeBuffer be non-empty so that it | |
383 // can call Start with the prefix byte. | |
384 bool return_non_zero_on_first = true; | |
385 DecodeBuffer b(buffer_); | |
386 EXPECT_TRUE( | |
387 DecodeAndValidateSeveralWays(&b, return_non_zero_on_first, validator)); | |
388 EXPECT_EQ(expected_offset, b.Offset()); | |
389 EXPECT_TRUE(validated); | |
390 } | |
391 } | |
392 | |
393 } // namespace | |
394 } // namespace test | |
395 } // namespace net | |
OLD | NEW |