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