OLD | NEW |
1 // Copyright 2014 The Chromium Authors. All rights reserved. | 1 // Copyright 2014 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "net/spdy/hpack/hpack_huffman_table.h" | 5 #include "net/spdy/hpack/hpack_huffman_table.h" |
6 | 6 |
7 #include <stdint.h> | 7 #include <stdint.h> |
8 | 8 |
9 #include <bitset> | 9 #include <bitset> |
10 #include <string> | |
11 #include <utility> | 10 #include <utility> |
12 | 11 |
13 #include "base/logging.h" | 12 #include "base/logging.h" |
14 #include "base/macros.h" | 13 #include "base/macros.h" |
15 #include "net/spdy/hpack/hpack_constants.h" | 14 #include "net/spdy/hpack/hpack_constants.h" |
16 #include "net/spdy/hpack/hpack_huffman_decoder.h" | 15 #include "net/spdy/hpack/hpack_huffman_decoder.h" |
17 #include "net/spdy/hpack/hpack_input_stream.h" | 16 #include "net/spdy/hpack/hpack_input_stream.h" |
18 #include "net/spdy/hpack/hpack_output_stream.h" | 17 #include "net/spdy/hpack/hpack_output_stream.h" |
19 #include "net/spdy/spdy_test_utils.h" | 18 #include "net/spdy/spdy_test_utils.h" |
20 #include "testing/gmock/include/gmock/gmock.h" | 19 #include "testing/gmock/include/gmock/gmock.h" |
21 #include "testing/gtest/include/gtest/gtest.h" | 20 #include "testing/gtest/include/gtest/gtest.h" |
22 | 21 |
23 using std::string; | |
24 using testing::ElementsAreArray; | 22 using testing::ElementsAreArray; |
25 using testing::Pointwise; | 23 using testing::Pointwise; |
26 | 24 |
27 namespace net { | 25 namespace net { |
28 | 26 |
29 namespace test { | 27 namespace test { |
30 | 28 |
31 typedef HpackHuffmanTable::DecodeEntry DecodeEntry; | 29 typedef HpackHuffmanTable::DecodeEntry DecodeEntry; |
32 typedef HpackHuffmanTable::DecodeTable DecodeTable; | 30 typedef HpackHuffmanTable::DecodeTable DecodeTable; |
33 | 31 |
(...skipping 25 matching lines...) Expand all Loading... |
59 }; | 57 }; |
60 | 58 |
61 namespace { | 59 namespace { |
62 | 60 |
63 // Tests of the ability to decode some canonical Huffman code, | 61 // Tests of the ability to decode some canonical Huffman code, |
64 // not just the one defined in the RFC 7541. | 62 // not just the one defined in the RFC 7541. |
65 class GenericHuffmanTableTest : public ::testing::TestWithParam<bool> { | 63 class GenericHuffmanTableTest : public ::testing::TestWithParam<bool> { |
66 protected: | 64 protected: |
67 GenericHuffmanTableTest() : table_(), peer_(table_) {} | 65 GenericHuffmanTableTest() : table_(), peer_(table_) {} |
68 | 66 |
69 string EncodeString(SpdyStringPiece input) { | 67 SpdyString EncodeString(SpdyStringPiece input) { |
70 string result; | 68 SpdyString result; |
71 HpackOutputStream output_stream; | 69 HpackOutputStream output_stream; |
72 table_.EncodeString(input, &output_stream); | 70 table_.EncodeString(input, &output_stream); |
73 | 71 |
74 output_stream.TakeString(&result); | 72 output_stream.TakeString(&result); |
75 // Verify EncodedSize() agrees with EncodeString(). | 73 // Verify EncodedSize() agrees with EncodeString(). |
76 EXPECT_EQ(result.size(), table_.EncodedSize(input)); | 74 EXPECT_EQ(result.size(), table_.EncodedSize(input)); |
77 return result; | 75 return result; |
78 } | 76 } |
79 | 77 |
80 HpackHuffmanTable table_; | 78 HpackHuffmanTable table_; |
81 HpackHuffmanTablePeer peer_; | 79 HpackHuffmanTablePeer peer_; |
82 }; | 80 }; |
83 | 81 |
84 MATCHER(DecodeEntryEq, "") { | 82 MATCHER(DecodeEntryEq, "") { |
85 const DecodeEntry& lhs = std::tr1::get<0>(arg); | 83 const DecodeEntry& lhs = std::tr1::get<0>(arg); |
86 const DecodeEntry& rhs = std::tr1::get<1>(arg); | 84 const DecodeEntry& rhs = std::tr1::get<1>(arg); |
87 return lhs.next_table_index == rhs.next_table_index && | 85 return lhs.next_table_index == rhs.next_table_index && |
88 lhs.length == rhs.length && lhs.symbol_id == rhs.symbol_id; | 86 lhs.length == rhs.length && lhs.symbol_id == rhs.symbol_id; |
89 } | 87 } |
90 | 88 |
91 uint32_t bits32(const string& bitstring) { | 89 uint32_t bits32(const SpdyString& bitstring) { |
92 return std::bitset<32>(bitstring).to_ulong(); | 90 return std::bitset<32>(bitstring).to_ulong(); |
93 } | 91 } |
94 char bits8(const string& bitstring) { | 92 char bits8(const SpdyString& bitstring) { |
95 return static_cast<char>(std::bitset<8>(bitstring).to_ulong()); | 93 return static_cast<char>(std::bitset<8>(bitstring).to_ulong()); |
96 } | 94 } |
97 | 95 |
98 TEST_F(GenericHuffmanTableTest, InitializeEdgeCases) { | 96 TEST_F(GenericHuffmanTableTest, InitializeEdgeCases) { |
99 { | 97 { |
100 // Verify eight symbols can be encoded with 3 bits per symbol. | 98 // Verify eight symbols can be encoded with 3 bits per symbol. |
101 HpackHuffmanSymbol code[] = { | 99 HpackHuffmanSymbol code[] = { |
102 {bits32("00000000000000000000000000000000"), 3, 0}, | 100 {bits32("00000000000000000000000000000000"), 3, 0}, |
103 {bits32("00100000000000000000000000000000"), 3, 1}, | 101 {bits32("00100000000000000000000000000000"), 3, 1}, |
104 {bits32("01000000000000000000000000000000"), 3, 2}, | 102 {bits32("01000000000000000000000000000000"), 3, 2}, |
(...skipping 122 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
227 } | 225 } |
228 EXPECT_EQ(bits8("10011000"), peer_.pad_bits()); | 226 EXPECT_EQ(bits8("10011000"), peer_.pad_bits()); |
229 | 227 |
230 char input_storage[] = {2, 3, 2, 7, 4}; | 228 char input_storage[] = {2, 3, 2, 7, 4}; |
231 SpdyStringPiece input(input_storage, arraysize(input_storage)); | 229 SpdyStringPiece input(input_storage, arraysize(input_storage)); |
232 // By symbol: (2) 00 (3) 010 (2) 00 (7) 10010 (4) 10000 (6 as pad) 1001100. | 230 // By symbol: (2) 00 (3) 010 (2) 00 (7) 10010 (4) 10000 (6 as pad) 1001100. |
233 char expect_storage[] = {bits8("00010001"), bits8("00101000"), | 231 char expect_storage[] = {bits8("00010001"), bits8("00101000"), |
234 bits8("01001100")}; | 232 bits8("01001100")}; |
235 SpdyStringPiece expect(expect_storage, arraysize(expect_storage)); | 233 SpdyStringPiece expect(expect_storage, arraysize(expect_storage)); |
236 | 234 |
237 string buffer_in = EncodeString(input); | 235 SpdyString buffer_in = EncodeString(input); |
238 EXPECT_EQ(expect, buffer_in); | 236 EXPECT_EQ(expect, buffer_in); |
239 | 237 |
240 string buffer_out; | 238 SpdyString buffer_out; |
241 HpackInputStream input_stream(buffer_in); | 239 HpackInputStream input_stream(buffer_in); |
242 EXPECT_TRUE(table_.GenericDecodeString(&input_stream, &buffer_out)); | 240 EXPECT_TRUE(table_.GenericDecodeString(&input_stream, &buffer_out)); |
243 EXPECT_EQ(buffer_out, input); | 241 EXPECT_EQ(buffer_out, input); |
244 } | 242 } |
245 | 243 |
246 TEST_F(GenericHuffmanTableTest, ValidateMultiLevelDecodeTables) { | 244 TEST_F(GenericHuffmanTableTest, ValidateMultiLevelDecodeTables) { |
247 HpackHuffmanSymbol code[] = { | 245 HpackHuffmanSymbol code[] = { |
248 {bits32("00000000000000000000000000000000"), 6, 0}, | 246 {bits32("00000000000000000000000000000000"), 6, 0}, |
249 {bits32("00000100000000000000000000000000"), 6, 1}, | 247 {bits32("00000100000000000000000000000000"), 6, 1}, |
250 {bits32("00001000000000000000000000000000"), 11, 2}, | 248 {bits32("00001000000000000000000000000000"), 11, 2}, |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
289 {bits32("01110000000000000000000000000000"), 4, 1}, | 287 {bits32("01110000000000000000000000000000"), 4, 1}, |
290 {bits32("00000000000000000000000000000000"), 2, 2}, | 288 {bits32("00000000000000000000000000000000"), 2, 2}, |
291 {bits32("01000000000000000000000000000000"), 3, 3}, | 289 {bits32("01000000000000000000000000000000"), 3, 3}, |
292 {bits32("10000000000000000000000000000000"), 5, 4}, | 290 {bits32("10000000000000000000000000000000"), 5, 4}, |
293 {bits32("10001000000000000000000000000000"), 5, 5}, | 291 {bits32("10001000000000000000000000000000"), 5, 5}, |
294 {bits32("10011000000000000000000000000000"), 6, 6}, | 292 {bits32("10011000000000000000000000000000"), 6, 6}, |
295 {bits32("10010000000000000000000000000000"), 5, 7}, | 293 {bits32("10010000000000000000000000000000"), 5, 7}, |
296 {bits32("10011100000000000000000000000000"), 16, 8}}; | 294 {bits32("10011100000000000000000000000000"), 16, 8}}; |
297 EXPECT_TRUE(table_.Initialize(code, arraysize(code))); | 295 EXPECT_TRUE(table_.Initialize(code, arraysize(code))); |
298 | 296 |
299 string buffer; | 297 SpdyString buffer; |
300 { | 298 { |
301 // This example works: (2) 00 (3) 010 (2) 00 (6) 100110 (pad) 100. | 299 // This example works: (2) 00 (3) 010 (2) 00 (6) 100110 (pad) 100. |
302 char input_storage[] = {bits8("00010001"), bits8("00110100")}; | 300 char input_storage[] = {bits8("00010001"), bits8("00110100")}; |
303 SpdyStringPiece input(input_storage, arraysize(input_storage)); | 301 SpdyStringPiece input(input_storage, arraysize(input_storage)); |
304 | 302 |
305 HpackInputStream input_stream(input); | 303 HpackInputStream input_stream(input); |
306 EXPECT_TRUE(table_.GenericDecodeString(&input_stream, &buffer)); | 304 EXPECT_TRUE(table_.GenericDecodeString(&input_stream, &buffer)); |
307 EXPECT_EQ(buffer, "\x02\x03\x02\x06"); | 305 EXPECT_EQ(buffer, "\x02\x03\x02\x06"); |
308 } | 306 } |
309 { | 307 { |
(...skipping 21 matching lines...) Expand all Loading... |
331 // Tests of the ability to decode the HPACK Huffman Code, defined in: | 329 // Tests of the ability to decode the HPACK Huffman Code, defined in: |
332 // https://httpwg.github.io/specs/rfc7541.html#huffman.code | 330 // https://httpwg.github.io/specs/rfc7541.html#huffman.code |
333 class HpackHuffmanTableTest : public GenericHuffmanTableTest { | 331 class HpackHuffmanTableTest : public GenericHuffmanTableTest { |
334 protected: | 332 protected: |
335 void SetUp() override { | 333 void SetUp() override { |
336 std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); | 334 std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode(); |
337 EXPECT_TRUE(table_.Initialize(&code[0], code.size())); | 335 EXPECT_TRUE(table_.Initialize(&code[0], code.size())); |
338 EXPECT_TRUE(table_.IsInitialized()); | 336 EXPECT_TRUE(table_.IsInitialized()); |
339 } | 337 } |
340 | 338 |
341 void DecodeStringTwice(const string& encoded, string* out) { | 339 void DecodeStringTwice(const SpdyString& encoded, SpdyString* out) { |
342 // First decode with HpackHuffmanTable. | 340 // First decode with HpackHuffmanTable. |
343 { | 341 { |
344 HpackInputStream input_stream(encoded); | 342 HpackInputStream input_stream(encoded); |
345 EXPECT_TRUE(table_.GenericDecodeString(&input_stream, out)); | 343 EXPECT_TRUE(table_.GenericDecodeString(&input_stream, out)); |
346 } | 344 } |
347 // And decode again with the fixed decoder, confirming that the result is | 345 // And decode again with the fixed decoder, confirming that the result is |
348 // the same. | 346 // the same. |
349 { | 347 { |
350 HpackInputStream input_stream(encoded); | 348 HpackInputStream input_stream(encoded); |
351 string buf; | 349 SpdyString buf; |
352 EXPECT_TRUE(HpackHuffmanDecoder::DecodeString(&input_stream, &buf)); | 350 EXPECT_TRUE(HpackHuffmanDecoder::DecodeString(&input_stream, &buf)); |
353 EXPECT_EQ(*out, buf); | 351 EXPECT_EQ(*out, buf); |
354 } | 352 } |
355 } | 353 } |
356 }; | 354 }; |
357 | 355 |
358 TEST_F(HpackHuffmanTableTest, InitializeHpackCode) { | 356 TEST_F(HpackHuffmanTableTest, InitializeHpackCode) { |
359 EXPECT_EQ(peer_.pad_bits(), '\xFF'); // First 8 bits of EOS. | 357 EXPECT_EQ(peer_.pad_bits(), '\xFF'); // First 8 bits of EOS. |
360 } | 358 } |
361 | 359 |
362 TEST_F(HpackHuffmanTableTest, SpecRequestExamples) { | 360 TEST_F(HpackHuffmanTableTest, SpecRequestExamples) { |
363 string buffer; | 361 SpdyString buffer; |
364 string test_table[] = { | 362 SpdyString test_table[] = { |
365 a2b_hex("f1e3c2e5f23a6ba0ab90f4ff"), | 363 a2b_hex("f1e3c2e5f23a6ba0ab90f4ff"), |
366 "www.example.com", | 364 "www.example.com", |
367 a2b_hex("a8eb10649cbf"), | 365 a2b_hex("a8eb10649cbf"), |
368 "no-cache", | 366 "no-cache", |
369 a2b_hex("25a849e95ba97d7f"), | 367 a2b_hex("25a849e95ba97d7f"), |
370 "custom-key", | 368 "custom-key", |
371 a2b_hex("25a849e95bb8e8b4bf"), | 369 a2b_hex("25a849e95bb8e8b4bf"), |
372 "custom-value", | 370 "custom-value", |
373 }; | 371 }; |
374 // Round-trip each test example. | 372 // Round-trip each test example. |
375 for (size_t i = 0; i != arraysize(test_table); i += 2) { | 373 for (size_t i = 0; i != arraysize(test_table); i += 2) { |
376 const string& encodedFixture(test_table[i]); | 374 const SpdyString& encodedFixture(test_table[i]); |
377 const string& decodedFixture(test_table[i + 1]); | 375 const SpdyString& decodedFixture(test_table[i + 1]); |
378 DecodeStringTwice(encodedFixture, &buffer); | 376 DecodeStringTwice(encodedFixture, &buffer); |
379 EXPECT_EQ(decodedFixture, buffer); | 377 EXPECT_EQ(decodedFixture, buffer); |
380 buffer = EncodeString(decodedFixture); | 378 buffer = EncodeString(decodedFixture); |
381 EXPECT_EQ(encodedFixture, buffer); | 379 EXPECT_EQ(encodedFixture, buffer); |
382 } | 380 } |
383 } | 381 } |
384 | 382 |
385 TEST_F(HpackHuffmanTableTest, SpecResponseExamples) { | 383 TEST_F(HpackHuffmanTableTest, SpecResponseExamples) { |
386 string buffer; | 384 SpdyString buffer; |
387 string test_table[] = { | 385 SpdyString test_table[] = { |
388 a2b_hex("6402"), "302", a2b_hex("aec3771a4b"), "private", | 386 a2b_hex("6402"), |
| 387 "302", |
| 388 a2b_hex("aec3771a4b"), |
| 389 "private", |
389 a2b_hex("d07abe941054d444a8200595040b8166" | 390 a2b_hex("d07abe941054d444a8200595040b8166" |
390 "e082a62d1bff"), | 391 "e082a62d1bff"), |
391 "Mon, 21 Oct 2013 20:13:21 GMT", | 392 "Mon, 21 Oct 2013 20:13:21 GMT", |
392 a2b_hex("9d29ad171863c78f0b97c8e9ae82ae43" | 393 a2b_hex("9d29ad171863c78f0b97c8e9ae82ae43" |
393 "d3"), | 394 "d3"), |
394 "https://www.example.com", a2b_hex("94e7821dd7f2e6c7b335dfdfcd5b3960" | 395 "https://www.example.com", |
395 "d5af27087f3672c1ab270fb5291f9587" | 396 a2b_hex("94e7821dd7f2e6c7b335dfdfcd5b3960" |
396 "316065c003ed4ee5b1063d5007"), | 397 "d5af27087f3672c1ab270fb5291f9587" |
| 398 "316065c003ed4ee5b1063d5007"), |
397 "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1", | 399 "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1", |
398 }; | 400 }; |
399 // Round-trip each test example. | 401 // Round-trip each test example. |
400 for (size_t i = 0; i != arraysize(test_table); i += 2) { | 402 for (size_t i = 0; i != arraysize(test_table); i += 2) { |
401 const string& encodedFixture(test_table[i]); | 403 const SpdyString& encodedFixture(test_table[i]); |
402 const string& decodedFixture(test_table[i + 1]); | 404 const SpdyString& decodedFixture(test_table[i + 1]); |
403 DecodeStringTwice(encodedFixture, &buffer); | 405 DecodeStringTwice(encodedFixture, &buffer); |
404 EXPECT_EQ(decodedFixture, buffer); | 406 EXPECT_EQ(decodedFixture, buffer); |
405 buffer = EncodeString(decodedFixture); | 407 buffer = EncodeString(decodedFixture); |
406 EXPECT_EQ(encodedFixture, buffer); | 408 EXPECT_EQ(encodedFixture, buffer); |
407 } | 409 } |
408 } | 410 } |
409 | 411 |
410 TEST_F(HpackHuffmanTableTest, RoundTripIndividualSymbols) { | 412 TEST_F(HpackHuffmanTableTest, RoundTripIndividualSymbols) { |
411 for (size_t i = 0; i != 256; i++) { | 413 for (size_t i = 0; i != 256; i++) { |
412 char c = static_cast<char>(i); | 414 char c = static_cast<char>(i); |
413 char storage[3] = {c, c, c}; | 415 char storage[3] = {c, c, c}; |
414 SpdyStringPiece input(storage, arraysize(storage)); | 416 SpdyStringPiece input(storage, arraysize(storage)); |
415 string buffer_in = EncodeString(input); | 417 SpdyString buffer_in = EncodeString(input); |
416 string buffer_out; | 418 SpdyString buffer_out; |
417 DecodeStringTwice(buffer_in, &buffer_out); | 419 DecodeStringTwice(buffer_in, &buffer_out); |
418 EXPECT_EQ(input, buffer_out); | 420 EXPECT_EQ(input, buffer_out); |
419 } | 421 } |
420 } | 422 } |
421 | 423 |
422 TEST_F(HpackHuffmanTableTest, RoundTripSymbolSequence) { | 424 TEST_F(HpackHuffmanTableTest, RoundTripSymbolSequence) { |
423 char storage[512]; | 425 char storage[512]; |
424 for (size_t i = 0; i != 256; i++) { | 426 for (size_t i = 0; i != 256; i++) { |
425 storage[i] = static_cast<char>(i); | 427 storage[i] = static_cast<char>(i); |
426 storage[511 - i] = static_cast<char>(i); | 428 storage[511 - i] = static_cast<char>(i); |
427 } | 429 } |
428 SpdyStringPiece input(storage, arraysize(storage)); | 430 SpdyStringPiece input(storage, arraysize(storage)); |
429 | 431 |
430 string buffer_in = EncodeString(input); | 432 SpdyString buffer_in = EncodeString(input); |
431 string buffer_out; | 433 SpdyString buffer_out; |
432 DecodeStringTwice(buffer_in, &buffer_out); | 434 DecodeStringTwice(buffer_in, &buffer_out); |
433 EXPECT_EQ(input, buffer_out); | 435 EXPECT_EQ(input, buffer_out); |
434 } | 436 } |
435 | 437 |
436 TEST_F(HpackHuffmanTableTest, EncodedSizeAgreesWithEncodeString) { | 438 TEST_F(HpackHuffmanTableTest, EncodedSizeAgreesWithEncodeString) { |
437 string test_table[] = { | 439 SpdyString test_table[] = { |
438 "", | 440 "", |
439 "Mon, 21 Oct 2013 20:13:21 GMT", | 441 "Mon, 21 Oct 2013 20:13:21 GMT", |
440 "https://www.example.com", | 442 "https://www.example.com", |
441 "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1", | 443 "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1", |
442 string(1, '\0'), | 444 SpdyString(1, '\0'), |
443 string("foo\0bar", 7), | 445 SpdyString("foo\0bar", 7), |
444 string(256, '\0'), | 446 SpdyString(256, '\0'), |
445 }; | 447 }; |
446 for (size_t i = 0; i != 256; ++i) { | 448 for (size_t i = 0; i != 256; ++i) { |
447 // Expand last |test_table| entry to cover all codes. | 449 // Expand last |test_table| entry to cover all codes. |
448 test_table[arraysize(test_table) - 1][i] = static_cast<char>(i); | 450 test_table[arraysize(test_table) - 1][i] = static_cast<char>(i); |
449 } | 451 } |
450 | 452 |
451 HpackOutputStream output_stream; | 453 HpackOutputStream output_stream; |
452 string encoding; | 454 SpdyString encoding; |
453 for (size_t i = 0; i != arraysize(test_table); ++i) { | 455 for (size_t i = 0; i != arraysize(test_table); ++i) { |
454 table_.EncodeString(test_table[i], &output_stream); | 456 table_.EncodeString(test_table[i], &output_stream); |
455 output_stream.TakeString(&encoding); | 457 output_stream.TakeString(&encoding); |
456 EXPECT_EQ(encoding.size(), table_.EncodedSize(test_table[i])); | 458 EXPECT_EQ(encoding.size(), table_.EncodedSize(test_table[i])); |
457 } | 459 } |
458 } | 460 } |
459 | 461 |
460 } // namespace | 462 } // namespace |
461 | 463 |
462 } // namespace test | 464 } // namespace test |
463 | 465 |
464 } // namespace net | 466 } // namespace net |
OLD | NEW |