| // Copyright 2014 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "spdy/core/hpack/hpack_huffman_table.h" |
| |
| #include <string> |
| #include <utility> |
| |
| #include "absl/base/macros.h" |
| #include "http2/hpack/huffman/hpack_huffman_decoder.h" |
| #include "common/platform/api/quiche_test.h" |
| #include "spdy/core/hpack/hpack_constants.h" |
| #include "spdy/core/hpack/hpack_output_stream.h" |
| #include "spdy/platform/api/spdy_string_utils.h" |
| |
| namespace spdy { |
| |
| namespace test { |
| |
| class HpackHuffmanTablePeer { |
| public: |
| explicit HpackHuffmanTablePeer(const HpackHuffmanTable& table) |
| : table_(table) {} |
| |
| const std::vector<uint32_t>& code_by_id() const { return table_.code_by_id_; } |
| const std::vector<uint8_t>& length_by_id() const { |
| return table_.length_by_id_; |
| } |
| uint8_t pad_bits() const { return table_.pad_bits_; } |
| uint16_t failed_symbol_id() const { return table_.failed_symbol_id_; } |
| |
| private: |
| const HpackHuffmanTable& table_; |
| }; |
| |
| namespace { |
| |
| // Tests of the ability to encode some canonical Huffman code, |
| // not just the one defined in the RFC 7541. |
| class GenericHuffmanTableTest : public QuicheTest { |
| protected: |
| GenericHuffmanTableTest() : table_(), peer_(table_) {} |
| |
| std::string EncodeString(absl::string_view input) { |
| std::string result; |
| HpackOutputStream output_stream; |
| table_.EncodeString(input, &output_stream); |
| |
| output_stream.TakeString(&result); |
| // Verify EncodedSize() agrees with EncodeString(). |
| EXPECT_EQ(result.size(), table_.EncodedSize(input)); |
| return result; |
| } |
| |
| HpackHuffmanTable table_; |
| HpackHuffmanTablePeer peer_; |
| }; |
| |
| TEST_F(GenericHuffmanTableTest, InitializeEdgeCases) { |
| { |
| // Verify eight symbols can be encoded with 3 bits per symbol. |
| HpackHuffmanSymbol code[] = {{0b00000000000000000000000000000000, 3, 0}, |
| {0b00100000000000000000000000000000, 3, 1}, |
| {0b01000000000000000000000000000000, 3, 2}, |
| {0b01100000000000000000000000000000, 3, 3}, |
| {0b10000000000000000000000000000000, 3, 4}, |
| {0b10100000000000000000000000000000, 3, 5}, |
| {0b11000000000000000000000000000000, 3, 6}, |
| {0b11100000000000000000000000000000, 8, 7}}; |
| HpackHuffmanTable table; |
| EXPECT_TRUE(table.Initialize(code, ABSL_ARRAYSIZE(code))); |
| } |
| { |
| // But using 2 bits with one symbol overflows the code. |
| HpackHuffmanSymbol code[] = { |
| {0b01000000000000000000000000000000, 3, 0}, |
| {0b01100000000000000000000000000000, 3, 1}, |
| {0b00000000000000000000000000000000, 2, 2}, |
| {0b10000000000000000000000000000000, 3, 3}, |
| {0b10100000000000000000000000000000, 3, 4}, |
| {0b11000000000000000000000000000000, 3, 5}, |
| {0b11100000000000000000000000000000, 3, 6}, |
| {0b00000000000000000000000000000000, 8, 7}}; // Overflow. |
| HpackHuffmanTable table; |
| EXPECT_FALSE(table.Initialize(code, ABSL_ARRAYSIZE(code))); |
| EXPECT_EQ(7, HpackHuffmanTablePeer(table).failed_symbol_id()); |
| } |
| { |
| // Verify four symbols can be encoded with incremental bits per symbol. |
| HpackHuffmanSymbol code[] = {{0b00000000000000000000000000000000, 1, 0}, |
| {0b10000000000000000000000000000000, 2, 1}, |
| {0b11000000000000000000000000000000, 3, 2}, |
| {0b11100000000000000000000000000000, 8, 3}}; |
| HpackHuffmanTable table; |
| EXPECT_TRUE(table.Initialize(code, ABSL_ARRAYSIZE(code))); |
| } |
| { |
| // But repeating a length overflows the code. |
| HpackHuffmanSymbol code[] = { |
| {0b00000000000000000000000000000000, 1, 0}, |
| {0b10000000000000000000000000000000, 2, 1}, |
| {0b11000000000000000000000000000000, 2, 2}, |
| {0b00000000000000000000000000000000, 8, 3}}; // Overflow. |
| HpackHuffmanTable table; |
| EXPECT_FALSE(table.Initialize(code, ABSL_ARRAYSIZE(code))); |
| EXPECT_EQ(3, HpackHuffmanTablePeer(table).failed_symbol_id()); |
| } |
| { |
| // Symbol IDs must be assigned sequentially with no gaps. |
| HpackHuffmanSymbol code[] = { |
| {0b00000000000000000000000000000000, 1, 0}, |
| {0b10000000000000000000000000000000, 2, 1}, |
| {0b11000000000000000000000000000000, 3, 1}, // Repeat. |
| {0b11100000000000000000000000000000, 8, 3}}; |
| HpackHuffmanTable table; |
| EXPECT_FALSE(table.Initialize(code, ABSL_ARRAYSIZE(code))); |
| EXPECT_EQ(2, HpackHuffmanTablePeer(table).failed_symbol_id()); |
| } |
| { |
| // Canonical codes must begin with zero. |
| HpackHuffmanSymbol code[] = {{0b10000000000000000000000000000000, 4, 0}, |
| {0b10010000000000000000000000000000, 4, 1}, |
| {0b10100000000000000000000000000000, 4, 2}, |
| {0b10110000000000000000000000000000, 8, 3}}; |
| HpackHuffmanTable table; |
| EXPECT_FALSE(table.Initialize(code, ABSL_ARRAYSIZE(code))); |
| EXPECT_EQ(0, HpackHuffmanTablePeer(table).failed_symbol_id()); |
| } |
| { |
| // Codes must match the expected canonical sequence. |
| HpackHuffmanSymbol code[] = { |
| {0b00000000000000000000000000000000, 2, 0}, |
| {0b01000000000000000000000000000000, 2, 1}, |
| {0b11000000000000000000000000000000, 2, 2}, // Code not canonical. |
| {0b10000000000000000000000000000000, 8, 3}}; |
| HpackHuffmanTable table; |
| EXPECT_FALSE(table.Initialize(code, ABSL_ARRAYSIZE(code))); |
| EXPECT_EQ(2, HpackHuffmanTablePeer(table).failed_symbol_id()); |
| } |
| { |
| // At least one code must have a length of 8 bits (to ensure pad-ability). |
| HpackHuffmanSymbol code[] = {{0b00000000000000000000000000000000, 1, 0}, |
| {0b10000000000000000000000000000000, 2, 1}, |
| {0b11000000000000000000000000000000, 3, 2}, |
| {0b11100000000000000000000000000000, 7, 3}}; |
| HpackHuffmanTable table; |
| EXPECT_FALSE(table.Initialize(code, ABSL_ARRAYSIZE(code))); |
| } |
| } |
| |
| TEST_F(GenericHuffmanTableTest, ValidateInternalsWithSmallCode) { |
| HpackHuffmanSymbol code[] = { |
| {0b01100000000000000000000000000000, 4, 0}, // 3rd. |
| {0b01110000000000000000000000000000, 4, 1}, // 4th. |
| {0b00000000000000000000000000000000, 2, 2}, // 1st assigned code. |
| {0b01000000000000000000000000000000, 3, 3}, // 2nd. |
| {0b10000000000000000000000000000000, 5, 4}, // 5th. |
| {0b10001000000000000000000000000000, 5, 5}, // 6th. |
| {0b10011000000000000000000000000000, 8, 6}, // 8th. |
| {0b10010000000000000000000000000000, 5, 7}}; // 7th. |
| EXPECT_TRUE(table_.Initialize(code, ABSL_ARRAYSIZE(code))); |
| |
| ASSERT_EQ(ABSL_ARRAYSIZE(code), peer_.code_by_id().size()); |
| ASSERT_EQ(ABSL_ARRAYSIZE(code), peer_.length_by_id().size()); |
| for (size_t i = 0; i < ABSL_ARRAYSIZE(code); ++i) { |
| EXPECT_EQ(code[i].code, peer_.code_by_id()[i]); |
| EXPECT_EQ(code[i].length, peer_.length_by_id()[i]); |
| } |
| |
| EXPECT_EQ(0b10011000, peer_.pad_bits()); |
| |
| char input_storage[] = {2, 3, 2, 7, 4}; |
| absl::string_view input(input_storage, ABSL_ARRAYSIZE(input_storage)); |
| // By symbol: (2) 00 (3) 010 (2) 00 (7) 10010 (4) 10000 (6 as pad) 1001100. |
| char expect_storage[] = {0b00010001, 0b00101000, 0b01001100}; |
| absl::string_view expect(expect_storage, ABSL_ARRAYSIZE(expect_storage)); |
| EXPECT_EQ(expect, EncodeString(input)); |
| } |
| |
| // Tests of the ability to encode the HPACK Huffman Code, defined in: |
| // https://httpwg.github.io/specs/rfc7541.html#huffman.code |
| class HpackHuffmanTableTest : public GenericHuffmanTableTest { |
| protected: |
| void SetUp() override { |
| EXPECT_TRUE(table_.Initialize(HpackHuffmanCodeVector().data(), |
| HpackHuffmanCodeVector().size())); |
| EXPECT_TRUE(table_.IsInitialized()); |
| } |
| |
| // Use http2::HpackHuffmanDecoder for roundtrip tests. |
| void DecodeString(const std::string& encoded, std::string* out) { |
| http2::HpackHuffmanDecoder decoder; |
| out->clear(); |
| EXPECT_TRUE(decoder.Decode(encoded, out)); |
| } |
| }; |
| |
| TEST_F(HpackHuffmanTableTest, InitializeHpackCode) { |
| EXPECT_EQ(peer_.pad_bits(), 0b11111111); // First 8 bits of EOS. |
| } |
| |
| TEST_F(HpackHuffmanTableTest, SpecRequestExamples) { |
| std::string buffer; |
| std::string test_table[] = { |
| SpdyHexDecode("f1e3c2e5f23a6ba0ab90f4ff"), |
| "www.example.com", |
| SpdyHexDecode("a8eb10649cbf"), |
| "no-cache", |
| SpdyHexDecode("25a849e95ba97d7f"), |
| "custom-key", |
| SpdyHexDecode("25a849e95bb8e8b4bf"), |
| "custom-value", |
| }; |
| // Round-trip each test example. |
| for (size_t i = 0; i != ABSL_ARRAYSIZE(test_table); i += 2) { |
| const std::string& encodedFixture(test_table[i]); |
| const std::string& decodedFixture(test_table[i + 1]); |
| DecodeString(encodedFixture, &buffer); |
| EXPECT_EQ(decodedFixture, buffer); |
| buffer = EncodeString(decodedFixture); |
| EXPECT_EQ(encodedFixture, buffer); |
| } |
| } |
| |
| TEST_F(HpackHuffmanTableTest, SpecResponseExamples) { |
| std::string buffer; |
| std::string test_table[] = { |
| SpdyHexDecode("6402"), |
| "302", |
| SpdyHexDecode("aec3771a4b"), |
| "private", |
| SpdyHexDecode("d07abe941054d444a8200595040b8166" |
| "e082a62d1bff"), |
| "Mon, 21 Oct 2013 20:13:21 GMT", |
| SpdyHexDecode("9d29ad171863c78f0b97c8e9ae82ae43" |
| "d3"), |
| "https://www.example.com", |
| SpdyHexDecode("94e7821dd7f2e6c7b335dfdfcd5b3960" |
| "d5af27087f3672c1ab270fb5291f9587" |
| "316065c003ed4ee5b1063d5007"), |
| "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1", |
| }; |
| // Round-trip each test example. |
| for (size_t i = 0; i != ABSL_ARRAYSIZE(test_table); i += 2) { |
| const std::string& encodedFixture(test_table[i]); |
| const std::string& decodedFixture(test_table[i + 1]); |
| DecodeString(encodedFixture, &buffer); |
| EXPECT_EQ(decodedFixture, buffer); |
| buffer = EncodeString(decodedFixture); |
| EXPECT_EQ(encodedFixture, buffer); |
| } |
| } |
| |
| TEST_F(HpackHuffmanTableTest, RoundTripIndividualSymbols) { |
| for (size_t i = 0; i != 256; i++) { |
| char c = static_cast<char>(i); |
| char storage[3] = {c, c, c}; |
| absl::string_view input(storage, ABSL_ARRAYSIZE(storage)); |
| std::string buffer_in = EncodeString(input); |
| std::string buffer_out; |
| DecodeString(buffer_in, &buffer_out); |
| EXPECT_EQ(input, buffer_out); |
| } |
| } |
| |
| TEST_F(HpackHuffmanTableTest, RoundTripSymbolSequence) { |
| char storage[512]; |
| for (size_t i = 0; i != 256; i++) { |
| storage[i] = static_cast<char>(i); |
| storage[511 - i] = static_cast<char>(i); |
| } |
| absl::string_view input(storage, ABSL_ARRAYSIZE(storage)); |
| std::string buffer_in = EncodeString(input); |
| std::string buffer_out; |
| DecodeString(buffer_in, &buffer_out); |
| EXPECT_EQ(input, buffer_out); |
| } |
| |
| TEST_F(HpackHuffmanTableTest, EncodedSizeAgreesWithEncodeString) { |
| std::string test_table[] = { |
| "", |
| "Mon, 21 Oct 2013 20:13:21 GMT", |
| "https://www.example.com", |
| "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1", |
| std::string(1, '\0'), |
| std::string("foo\0bar", 7), |
| std::string(256, '\0'), |
| }; |
| for (size_t i = 0; i != 256; ++i) { |
| // Expand last |test_table| entry to cover all codes. |
| test_table[ABSL_ARRAYSIZE(test_table) - 1][i] = static_cast<char>(i); |
| } |
| |
| HpackOutputStream output_stream; |
| std::string encoding; |
| for (size_t i = 0; i != ABSL_ARRAYSIZE(test_table); ++i) { |
| table_.EncodeString(test_table[i], &output_stream); |
| output_stream.TakeString(&encoding); |
| EXPECT_EQ(encoding.size(), table_.EncodedSize(test_table[i])); |
| } |
| } |
| |
| } // namespace |
| |
| } // namespace test |
| |
| } // namespace spdy |