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