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