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
18using base::StringPiece;
19using net::test::a2b_hex;
20using std::string;
21using testing::ElementsAre;
22using testing::ElementsAreArray;
23using testing::Pointwise;
24
25namespace net {
26
27namespace test {
28
29typedef HpackHuffmanTable::DecodeEntry DecodeEntry;
30typedef HpackHuffmanTable::DecodeTable DecodeTable;
31
32class 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
89namespace {
90
91class 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
112MATCHER(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
120uint32 bits32(const string& bitstring) {
121  return std::bitset<32>(bitstring).to_ulong();
122}
123char bits8(const string& bitstring) {
124  return static_cast<char>(std::bitset<8>(bitstring).to_ulong());
125}
126
127TEST_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
134TEST_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
230TEST_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
290TEST_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
330TEST_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
388TEST_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
417TEST_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
452TEST_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
470TEST_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
490TEST_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