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 |