net/spdy/hpack_huffman_table_test.cc

   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
   3 // found in the LICENSE file.
   4
   5 #include "net/spdy/hpack_huffman_table.h"
   6
   7 #include <bitset>
   8 #include <string>
   9
  10 #include "base/logging.h"
  11 #include "net/spdy/hpack_constants.h"
  12 #include "net/spdy/hpack_input_stream.h"
  13 #include "net/spdy/hpack_output_stream.h"
  14 #include "net/spdy/spdy_test_utils.h"
  15 #include "testing/gmock/include/gmock/gmock.h"
  16 #include "testing/gtest/include/gtest/gtest.h"
  17
  18 using base::StringPiece;
  19 using net::test::a2b_hex;
  20 using std::string;
  21 using testing::ElementsAreArray;
  22 using testing::Pointwise;
  23
  24 namespace net {
  25
  26 namespace test {
  27
  28 typedef HpackHuffmanTable::DecodeEntry DecodeEntry;
  29 typedef HpackHuffmanTable::DecodeTable DecodeTable;
  30
  31 class HpackHuffmanTablePeer {
  32  public:
  33   explicit HpackHuffmanTablePeer(const HpackHuffmanTable& table)
  34       : table_(table) { }
  35
  36   const std::vector<uint32>& code_by_id() const {
  37     return table_.code_by_id_;
  38   }
  39   const std::vector<uint8>& length_by_id() const {
  40     return table_.length_by_id_;
  41   }
  42   const std::vector<DecodeTable>& decode_tables() const {
  43     return table_.decode_tables_;
  44   }
  45   char pad_bits() const {
  46     // Cast to match signed-ness of bits8().
  47     return static_cast<char>(table_.pad_bits_);
  48   }
  49   uint16 failed_symbol_id() const {
  50     return table_.failed_symbol_id_;
  51   }
  52   std::vector<DecodeEntry> decode_entries(const DecodeTable& decode_table) {
  53     std::vector<DecodeEntry>::const_iterator begin =
  54         table_.decode_entries_.begin() + decode_table.entries_offset;
  55     return std::vector<DecodeEntry>(begin, begin + decode_table.size());
  56   }
  57
  58  private:
  59   const HpackHuffmanTable& table_;
  60 };
  61
  62 namespace {
  63
  64 class HpackHuffmanTableTest : public ::testing::Test {
  65  protected:
  66   HpackHuffmanTableTest()
  67       : table_(),
  68         peer_(table_) {}
  69
  70   string EncodeString(StringPiece input) {
  71     string result;
  72     HpackOutputStream output_stream;
  73     table_.EncodeString(input, &output_stream);
  74
  75     output_stream.TakeString(&result);
  76     // Verify EncodedSize() agrees with EncodeString().
  77     EXPECT_EQ(result.size(), table_.EncodedSize(input));
  78     return result;
  79   }
  80
  81   HpackHuffmanTable table_;
  82   HpackHuffmanTablePeer peer_;
  83 };
  84
  85 MATCHER(DecodeEntryEq, "") {
  86   const DecodeEntry& lhs = std::tr1::get<0>(arg);
  87   const DecodeEntry& rhs = std::tr1::get<1>(arg);
  88   return lhs.next_table_index == rhs.next_table_index &&
  89       lhs.length == rhs.length &&
  90       lhs.symbol_id == rhs.symbol_id;
  91 }
  92
  93 uint32 bits32(const string& bitstring) {
  94   return std::bitset<32>(bitstring).to_ulong();
  95 }
  96 char bits8(const string& bitstring) {
  97   return static_cast<char>(std::bitset<8>(bitstring).to_ulong());
  98 }
  99
 100 TEST_F(HpackHuffmanTableTest, InitializeHpackCode) {
 101   std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode();
 102   EXPECT_TRUE(table_.Initialize(&code[0], code.size()));
 103   EXPECT_TRUE(table_.IsInitialized());
 104   EXPECT_EQ(peer_.pad_bits(), bits8("11111111"));  // First 8 bits of EOS.
 105 }
 106
 107 TEST_F(HpackHuffmanTableTest, InitializeEdgeCases) {
 108   {
 109     // Verify eight symbols can be encoded with 3 bits per symbol.
 110     HpackHuffmanSymbol code[] = {
 111       {bits32("00000000000000000000000000000000"), 3, 0},
 112       {bits32("00100000000000000000000000000000"), 3, 1},
 113       {bits32("01000000000000000000000000000000"), 3, 2},
 114       {bits32("01100000000000000000000000000000"), 3, 3},
 115       {bits32("10000000000000000000000000000000"), 3, 4},
 116       {bits32("10100000000000000000000000000000"), 3, 5},
 117       {bits32("11000000000000000000000000000000"), 3, 6},
 118       {bits32("11100000000000000000000000000000"), 8, 7}};
 119     HpackHuffmanTable table;
 120     EXPECT_TRUE(table.Initialize(code, arraysize(code)));
 121   }
 122   {
 123     // But using 2 bits with one symbol overflows the code.
 124     HpackHuffmanSymbol code[] = {
 125       {bits32("01000000000000000000000000000000"), 3, 0},
 126       {bits32("01100000000000000000000000000000"), 3, 1},
 127       {bits32("00000000000000000000000000000000"), 2, 2},
 128       {bits32("10000000000000000000000000000000"), 3, 3},
 129       {bits32("10100000000000000000000000000000"), 3, 4},
 130       {bits32("11000000000000000000000000000000"), 3, 5},
 131       {bits32("11100000000000000000000000000000"), 3, 6},
 132       {bits32("00000000000000000000000000000000"), 8, 7}};  // Overflow.
 133     HpackHuffmanTable table;
 134     EXPECT_FALSE(table.Initialize(code, arraysize(code)));
 135     EXPECT_EQ(7, HpackHuffmanTablePeer(table).failed_symbol_id());
 136   }
 137   {
 138     // Verify four symbols can be encoded with incremental bits per symbol.
 139     HpackHuffmanSymbol code[] = {
 140       {bits32("00000000000000000000000000000000"), 1, 0},
 141       {bits32("10000000000000000000000000000000"), 2, 1},
 142       {bits32("11000000000000000000000000000000"), 3, 2},
 143       {bits32("11100000000000000000000000000000"), 8, 3}};
 144     HpackHuffmanTable table;
 145     EXPECT_TRUE(table.Initialize(code, arraysize(code)));
 146   }
 147   {
 148     // But repeating a length overflows the code.
 149     HpackHuffmanSymbol code[] = {
 150       {bits32("00000000000000000000000000000000"), 1, 0},
 151       {bits32("10000000000000000000000000000000"), 2, 1},
 152       {bits32("11000000000000000000000000000000"), 2, 2},
 153       {bits32("00000000000000000000000000000000"), 8, 3}};  // Overflow.
 154     HpackHuffmanTable table;
 155     EXPECT_FALSE(table.Initialize(code, arraysize(code)));
 156     EXPECT_EQ(3, HpackHuffmanTablePeer(table).failed_symbol_id());
 157   }
 158   {
 159     // Symbol IDs must be assigned sequentially with no gaps.
 160     HpackHuffmanSymbol code[] = {
 161       {bits32("00000000000000000000000000000000"), 1, 0},
 162       {bits32("10000000000000000000000000000000"), 2, 1},
 163       {bits32("11000000000000000000000000000000"), 3, 1},  // Repeat.
 164       {bits32("11100000000000000000000000000000"), 8, 3}};
 165     HpackHuffmanTable table;
 166     EXPECT_FALSE(table.Initialize(code, arraysize(code)));
 167     EXPECT_EQ(2, HpackHuffmanTablePeer(table).failed_symbol_id());
 168   }
 169   {
 170     // Canonical codes must begin with zero.
 171     HpackHuffmanSymbol code[] = {
 172       {bits32("10000000000000000000000000000000"), 4, 0},
 173       {bits32("10010000000000000000000000000000"), 4, 1},
 174       {bits32("10100000000000000000000000000000"), 4, 2},
 175       {bits32("10110000000000000000000000000000"), 8, 3}};
 176     HpackHuffmanTable table;
 177     EXPECT_FALSE(table.Initialize(code, arraysize(code)));
 178     EXPECT_EQ(0, HpackHuffmanTablePeer(table).failed_symbol_id());
 179   }
 180   {
 181     // Codes must match the expected canonical sequence.
 182     HpackHuffmanSymbol code[] = {
 183       {bits32("00000000000000000000000000000000"), 2, 0},
 184       {bits32("01000000000000000000000000000000"), 2, 1},
 185       {bits32("11000000000000000000000000000000"), 2, 2},  // Not canonical.
 186       {bits32("10000000000000000000000000000000"), 8, 3}};
 187     HpackHuffmanTable table;
 188     EXPECT_FALSE(table.Initialize(code, arraysize(code)));
 189     EXPECT_EQ(2, HpackHuffmanTablePeer(table).failed_symbol_id());
 190   }
 191   {
 192     // At least one code must have a length of 8 bits (to ensure pad-ability).
 193     HpackHuffmanSymbol code[] = {
 194       {bits32("00000000000000000000000000000000"), 1, 0},
 195       {bits32("10000000000000000000000000000000"), 2, 1},
 196       {bits32("11000000000000000000000000000000"), 3, 2},
 197       {bits32("11100000000000000000000000000000"), 7, 3}};
 198     HpackHuffmanTable table;
 199     EXPECT_FALSE(table.Initialize(code, arraysize(code)));
 200   }
 201 }
 202
 203 TEST_F(HpackHuffmanTableTest, ValidateInternalsWithSmallCode) {
 204   HpackHuffmanSymbol code[] = {
 205     {bits32("01100000000000000000000000000000"), 4, 0},  // 3rd.
 206     {bits32("01110000000000000000000000000000"), 4, 1},  // 4th.
 207     {bits32("00000000000000000000000000000000"), 2, 2},  // 1st assigned code.
 208     {bits32("01000000000000000000000000000000"), 3, 3},  // 2nd.
 209     {bits32("10000000000000000000000000000000"), 5, 4},  // 5th.
 210     {bits32("10001000000000000000000000000000"), 5, 5},  // 6th.
 211     {bits32("10011000000000000000000000000000"), 8, 6},  // 8th.
 212     {bits32("10010000000000000000000000000000"), 5, 7}};  // 7th.
 213   EXPECT_TRUE(table_.Initialize(code, arraysize(code)));
 214   ASSERT_EQ(arraysize(code), peer_.code_by_id().size());
 215   ASSERT_EQ(arraysize(code), peer_.length_by_id().size());
 216   for (size_t i = 0; i < arraysize(code); ++i) {
 217     EXPECT_EQ(code[i].code, peer_.code_by_id()[i]);
 218     EXPECT_EQ(code[i].length, peer_.length_by_id()[i]);
 219   }
 220
 221   EXPECT_EQ(1u, peer_.decode_tables().size());
 222   {
 223     std::vector<DecodeEntry> expected;
 224     expected.resize(128, DecodeEntry(0, 2, 2));  // Fills 128.
 225     expected.resize(192, DecodeEntry(0, 3, 3));  // Fills 64.
 226     expected.resize(224, DecodeEntry(0, 4, 0));  // Fills 32.
 227     expected.resize(256, DecodeEntry(0, 4, 1));  // Fills 32.
 228     expected.resize(272, DecodeEntry(0, 5, 4));  // Fills 16.
 229     expected.resize(288, DecodeEntry(0, 5, 5));  // Fills 16.
 230     expected.resize(304, DecodeEntry(0, 5, 7));  // Fills 16.
 231     expected.resize(306, DecodeEntry(0, 8, 6));  // Fills 2.
 232     expected.resize(512, DecodeEntry());  // Remainder is empty.
 233
 234     EXPECT_THAT(peer_.decode_entries(peer_.decode_tables()[0]),
 235                 Pointwise(DecodeEntryEq(), expected));
 236   }
 237   EXPECT_EQ(bits8("10011000"), peer_.pad_bits());
 238
 239   char input_storage[] = {2, 3, 2, 7, 4};
 240   StringPiece input(input_storage, arraysize(input_storage));
 241   // By symbol: (2) 00 (3) 010 (2) 00 (7) 10010 (4) 10000 (6 as pad) 1001100.
 242   char expect_storage[] = {
 243     bits8("00010001"),
 244     bits8("00101000"),
 245     bits8("01001100")};
 246   StringPiece expect(expect_storage, arraysize(expect_storage));
 247
 248   string buffer_in = EncodeString(input);
 249   EXPECT_EQ(expect, buffer_in);
 250
 251   string buffer_out;
 252   HpackInputStream input_stream(kuint32max, buffer_in);
 253   EXPECT_TRUE(table_.DecodeString(&input_stream, input.size(),  &buffer_out));
 254   EXPECT_EQ(buffer_out, input);
 255 }
 256
 257 TEST_F(HpackHuffmanTableTest, ValidateMultiLevelDecodeTables) {
 258   HpackHuffmanSymbol code[] = {
 259     {bits32("00000000000000000000000000000000"), 6, 0},
 260     {bits32("00000100000000000000000000000000"), 6, 1},
 261     {bits32("00001000000000000000000000000000"), 11, 2},
 262     {bits32("00001000001000000000000000000000"), 11, 3},
 263     {bits32("00001000010000000000000000000000"), 12, 4},
 264   };
 265   EXPECT_TRUE(table_.Initialize(code, arraysize(code)));
 266
 267   EXPECT_EQ(2u, peer_.decode_tables().size());
 268   {
 269     std::vector<DecodeEntry> expected;
 270     expected.resize(8, DecodeEntry(0, 6, 0));  // Fills 8.
 271     expected.resize(16, DecodeEntry(0, 6, 1));  // Fills 8.
 272     expected.resize(17, DecodeEntry(1, 12, 0));  // Pointer. Fills 1.
 273     expected.resize(512, DecodeEntry());  // Remainder is empty.
 274
 275     const DecodeTable& decode_table = peer_.decode_tables()[0];
 276     EXPECT_EQ(decode_table.prefix_length, 0);
 277     EXPECT_EQ(decode_table.indexed_length, 9);
 278     EXPECT_THAT(peer_.decode_entries(decode_table),
 279                 Pointwise(DecodeEntryEq(), expected));
 280   }
 281   {
 282     std::vector<DecodeEntry> expected;
 283     expected.resize(2, DecodeEntry(1, 11, 2));  // Fills 2.
 284     expected.resize(4, DecodeEntry(1, 11, 3));  // Fills 2.
 285     expected.resize(5, DecodeEntry(1, 12, 4));  // Fills 1.
 286     expected.resize(8, DecodeEntry());  // Remainder is empty.
 287
 288     const DecodeTable& decode_table = peer_.decode_tables()[1];
 289     EXPECT_EQ(decode_table.prefix_length, 9);
 290     EXPECT_EQ(decode_table.indexed_length, 3);
 291     EXPECT_THAT(peer_.decode_entries(decode_table),
 292                 Pointwise(DecodeEntryEq(), expected));
 293   }
 294   EXPECT_EQ(bits8("00001000"), peer_.pad_bits());
 295 }
 296
 297 TEST_F(HpackHuffmanTableTest, DecodeWithBadInput) {
 298   HpackHuffmanSymbol code[] = {
 299     {bits32("01100000000000000000000000000000"), 4, 0},
 300     {bits32("01110000000000000000000000000000"), 4, 1},
 301     {bits32("00000000000000000000000000000000"), 2, 2},
 302     {bits32("01000000000000000000000000000000"), 3, 3},
 303     {bits32("10000000000000000000000000000000"), 5, 4},
 304     {bits32("10001000000000000000000000000000"), 5, 5},
 305     {bits32("10011000000000000000000000000000"), 6, 6},
 306     {bits32("10010000000000000000000000000000"), 5, 7},
 307     {bits32("10011100000000000000000000000000"), 16, 8}};
 308   EXPECT_TRUE(table_.Initialize(code, arraysize(code)));
 309
 310   string buffer;
 311   const size_t capacity = 4;
 312   {
 313     // This example works: (2) 00 (3) 010 (2) 00 (6) 100110 (pad) 100.
 314     char input_storage[] = {bits8("00010001"), bits8("00110100")};
 315     StringPiece input(input_storage, arraysize(input_storage));
 316
 317     HpackInputStream input_stream(kuint32max, input);
 318     EXPECT_TRUE(table_.DecodeString(&input_stream, capacity, &buffer));
 319     EXPECT_EQ(buffer, "\x02\x03\x02\x06");
 320   }
 321   {
 322     // Expect to fail on an invalid code prefix.
 323     // (2) 00 (3) 010 (2) 00 (too-large) 101000 (pad) 100.
 324     char input_storage[] = {bits8("00010001"), bits8("01000111")};
 325     StringPiece input(input_storage, arraysize(input_storage));
 326
 327     HpackInputStream input_stream(kuint32max, input);
 328     EXPECT_FALSE(table_.DecodeString(&input_stream, capacity, &buffer));
 329     EXPECT_EQ(buffer, "\x02\x03\x02");
 330   }
 331   {
 332     // Repeat the shortest 0b00 code to overflow |buffer|. Expect to fail.
 333     std::vector<char> input_storage(1 + capacity / 4, '\0');
 334     StringPiece input(&input_storage[0], input_storage.size());
 335
 336     HpackInputStream input_stream(kuint32max, input);
 337     EXPECT_FALSE(table_.DecodeString(&input_stream, capacity, &buffer));
 338
 339     std::vector<char> expected(capacity, '\x02');
 340     EXPECT_THAT(buffer, ElementsAreArray(expected));
 341     EXPECT_EQ(capacity, buffer.size());
 342   }
 343   {
 344     // Expect to fail if more than a byte of unconsumed input remains.
 345     // (6) 100110 (8 truncated) 1001110000
 346     char input_storage[] = {bits8("10011010"), bits8("01110000")};
 347     StringPiece input(input_storage, arraysize(input_storage));
 348
 349     HpackInputStream input_stream(kuint32max, input);
 350     EXPECT_FALSE(table_.DecodeString(&input_stream, capacity, &buffer));
 351     EXPECT_EQ(buffer, "\x06");
 352   }
 353 }
 354
 355 TEST_F(HpackHuffmanTableTest, SpecRequestExamples) {
 356   std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode();
 357   EXPECT_TRUE(table_.Initialize(&code[0], code.size()));
 358
 359   string buffer;
 360   string test_table[] = {
 361     a2b_hex("f1e3c2e5f23a6ba0ab90f4ff"),
 362     "www.example.com",
 363     a2b_hex("a8eb10649cbf"),
 364     "no-cache",
 365     a2b_hex("25a849e95ba97d7f"),
 366     "custom-key",
 367     a2b_hex("25a849e95bb8e8b4bf"),
 368     "custom-value",
 369   };
 370   // Round-trip each test example.
 371   for (size_t i = 0; i != arraysize(test_table); i += 2) {
 372     const string& encodedFixture(test_table[i]);
 373     const string& decodedFixture(test_table[i+1]);
 374     HpackInputStream input_stream(kuint32max, encodedFixture);
 375
 376     EXPECT_TRUE(table_.DecodeString(&input_stream, decodedFixture.size(),
 377                                     &buffer));
 378     EXPECT_EQ(decodedFixture, buffer);
 379     buffer = EncodeString(decodedFixture);
 380     EXPECT_EQ(encodedFixture, buffer);
 381   }
 382 }
 383
 384 TEST_F(HpackHuffmanTableTest, SpecResponseExamples) {
 385   std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode();
 386   EXPECT_TRUE(table_.Initialize(&code[0], code.size()));
 387
 388   string buffer;
 389   string test_table[] = {
 390     a2b_hex("6402"),
 391     "302",
 392     a2b_hex("aec3771a4b"),
 393     "private",
 394     a2b_hex("d07abe941054d444a8200595040b8166"
 395             "e082a62d1bff"),
 396     "Mon, 21 Oct 2013 20:13:21 GMT",
 397     a2b_hex("9d29ad171863c78f0b97c8e9ae82ae43"
 398             "d3"),
 399     "https://www.example.com",
 400     a2b_hex("94e7821dd7f2e6c7b335dfdfcd5b3960"
 401             "d5af27087f3672c1ab270fb5291f9587"
 402             "316065c003ed4ee5b1063d5007"),
 403     "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1",
 404   };
 405   // Round-trip each test example.
 406   for (size_t i = 0; i != arraysize(test_table); i += 2) {
 407     const string& encodedFixture(test_table[i]);
 408     const string& decodedFixture(test_table[i+1]);
 409     HpackInputStream input_stream(kuint32max, encodedFixture);
 410
 411     EXPECT_TRUE(table_.DecodeString(&input_stream, decodedFixture.size(),
 412                                     &buffer));
 413     EXPECT_EQ(decodedFixture, buffer);
 414     buffer = EncodeString(decodedFixture);
 415     EXPECT_EQ(encodedFixture, buffer);
 416   }
 417 }
 418
 419 TEST_F(HpackHuffmanTableTest, RoundTripIndvidualSymbols) {
 420   std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode();
 421   EXPECT_TRUE(table_.Initialize(&code[0], code.size()));
 422
 423   for (size_t i = 0; i != 256; i++) {
 424     char c = static_cast<char>(i);
 425     char storage[3] = {c, c, c};
 426     StringPiece input(storage, arraysize(storage));
 427
 428     string buffer_in = EncodeString(input);
 429     string buffer_out;
 430
 431     HpackInputStream input_stream(kuint32max, buffer_in);
 432     EXPECT_TRUE(table_.DecodeString(&input_stream, input.size(), &buffer_out));
 433     EXPECT_EQ(input, buffer_out);
 434   }
 435 }
 436
 437 TEST_F(HpackHuffmanTableTest, RoundTripSymbolSequence) {
 438   std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode();
 439   EXPECT_TRUE(table_.Initialize(&code[0], code.size()));
 440
 441
 442   char storage[512];
 443   for (size_t i = 0; i != 256; i++) {
 444     storage[i] = static_cast<char>(i);
 445     storage[511 - i] = static_cast<char>(i);
 446   }
 447   StringPiece input(storage, arraysize(storage));
 448
 449   string buffer_in = EncodeString(input);
 450   string buffer_out;
 451
 452   HpackInputStream input_stream(kuint32max, buffer_in);
 453   EXPECT_TRUE(table_.DecodeString(&input_stream, input.size(), &buffer_out));
 454   EXPECT_EQ(input, buffer_out);
 455 }
 456
 457 TEST_F(HpackHuffmanTableTest, EncodedSizeAgreesWithEncodeString) {
 458   std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode();
 459   EXPECT_TRUE(table_.Initialize(&code[0], code.size()));
 460
 461   string test_table[] = {
 462     "",
 463     "Mon, 21 Oct 2013 20:13:21 GMT",
 464     "https://www.example.com",
 465     "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1",
 466     string(1, '\0'),
 467     string("foo\0bar", 7),
 468     string(256, '\0'),
 469   };
 470   for (size_t i = 0; i != 256; ++i) {
 471     // Expand last |test_table| entry to cover all codes.
 472     test_table[arraysize(test_table)-1][i] = static_cast<char>(i);
 473   }
 474
 475   HpackOutputStream output_stream;
 476   string encoding;
 477   for (size_t i = 0; i != arraysize(test_table); ++i) {
 478     table_.EncodeString(test_table[i], &output_stream);
 479     output_stream.TakeString(&encoding);
 480     EXPECT_EQ(encoding.size(), table_.EncodedSize(test_table[i]));
 481   }
 482 }
 483
 484 }  // namespace
 485
 486 }  // namespace test
 487
 488 }  // namespace net