Implement better HPACK Huffman code decoder.

net/spdy/hpack/hpack_huffman_table_test.cc

 // Copyright 2014 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "net/spdy/hpack/hpack_huffman_table.h"
 
 #include <stdint.h>
 
 #include <bitset>
 #include <limits>
 #include <string>
+#include <utility>
 
 #include "base/logging.h"
+#include "base/macros.h"
 #include "net/spdy/hpack/hpack_constants.h"
+#include "net/spdy/hpack/hpack_huffman_decoder.h"
 #include "net/spdy/hpack/hpack_input_stream.h"
 #include "net/spdy/hpack/hpack_output_stream.h"
 #include "net/spdy/spdy_test_utils.h"
 #include "testing/gmock/include/gmock/gmock.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 using base::StringPiece;
 using std::string;
 using testing::ElementsAreArray;
 using testing::Pointwise;
@@ skipping 27 matching lines @@
         table_.decode_entries_.begin() + decode_table.entries_offset;
     return std::vector<DecodeEntry>(begin, begin + decode_table.size());
   }
 
  private:
   const HpackHuffmanTable& table_;
 };
 
 namespace {
 
-class HpackHuffmanTableTest : public ::testing::Test {
+// Tests of the ability to decode some canonical Huffman code,
+// not just the one defined in the RFC 7541.
+class GenericHuffmanTableTest : public ::testing::TestWithParam<bool> {
  protected:
-  HpackHuffmanTableTest() : table_(), peer_(table_) {}
+  GenericHuffmanTableTest() : table_(), peer_(table_) {}
 
   string EncodeString(StringPiece input) {
     string result;
     HpackOutputStream output_stream;
     table_.EncodeString(input, &output_stream);
 
     output_stream.TakeString(&result);
     // Verify EncodedSize() agrees with EncodeString().
     EXPECT_EQ(result.size(), table_.EncodedSize(input));
     return result;
@@ skipping 10 matching lines @@
          lhs.length == rhs.length && lhs.symbol_id == rhs.symbol_id;
 }
 
 uint32_t bits32(const string& bitstring) {
   return std::bitset<32>(bitstring).to_ulong();
 }
 char bits8(const string& bitstring) {
   return static_cast<char>(std::bitset<8>(bitstring).to_ulong());
 }
 
-TEST_F(HpackHuffmanTableTest, InitializeHpackCode) {
-  std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode();
-  EXPECT_TRUE(table_.Initialize(&code[0], code.size()));
-  EXPECT_TRUE(table_.IsInitialized());
-  EXPECT_EQ(peer_.pad_bits(), bits8("11111111"));  // First 8 bits of EOS.
-}
-
-TEST_F(HpackHuffmanTableTest, InitializeEdgeCases) {
+TEST_F(GenericHuffmanTableTest, InitializeEdgeCases) {
   {
     // Verify eight symbols can be encoded with 3 bits per symbol.
     HpackHuffmanSymbol code[] = {
         {bits32("00000000000000000000000000000000"), 3, 0},
         {bits32("00100000000000000000000000000000"), 3, 1},
         {bits32("01000000000000000000000000000000"), 3, 2},
         {bits32("01100000000000000000000000000000"), 3, 3},
         {bits32("10000000000000000000000000000000"), 3, 4},
         {bits32("10100000000000000000000000000000"), 3, 5},
         {bits32("11000000000000000000000000000000"), 3, 6},
@@ skipping 75 matching lines @@
     HpackHuffmanSymbol code[] = {
         {bits32("00000000000000000000000000000000"), 1, 0},
         {bits32("10000000000000000000000000000000"), 2, 1},
         {bits32("11000000000000000000000000000000"), 3, 2},
         {bits32("11100000000000000000000000000000"), 7, 3}};
     HpackHuffmanTable table;
     EXPECT_FALSE(table.Initialize(code, arraysize(code)));
   }
 }
 
-TEST_F(HpackHuffmanTableTest, ValidateInternalsWithSmallCode) {
+TEST_F(GenericHuffmanTableTest, ValidateInternalsWithSmallCode) {
   HpackHuffmanSymbol code[] = {
       {bits32("01100000000000000000000000000000"), 4, 0},  // 3rd.
       {bits32("01110000000000000000000000000000"), 4, 1},  // 4th.
       {bits32("00000000000000000000000000000000"), 2, 2},  // 1st assigned code.
       {bits32("01000000000000000000000000000000"), 3, 3},  // 2nd.
       {bits32("10000000000000000000000000000000"), 5, 4},  // 5th.
       {bits32("10001000000000000000000000000000"), 5, 5},  // 6th.
       {bits32("10011000000000000000000000000000"), 8, 6},  // 8th.
       {bits32("10010000000000000000000000000000"), 5, 7}};  // 7th.
   EXPECT_TRUE(table_.Initialize(code, arraysize(code)));
@@ skipping 28 matching lines @@
   char expect_storage[] = {bits8("00010001"), bits8("00101000"),
                            bits8("01001100")};
   StringPiece expect(expect_storage, arraysize(expect_storage));
 
   string buffer_in = EncodeString(input);
   EXPECT_EQ(expect, buffer_in);
 
   string buffer_out;
   HpackInputStream input_stream(std::numeric_limits<uint32_t>::max(),
                                 buffer_in);
-  EXPECT_TRUE(table_.DecodeString(&input_stream, input.size(), &buffer_out));
+  EXPECT_TRUE(
+      table_.GenericDecodeString(&input_stream, input.size(), &buffer_out));
   EXPECT_EQ(buffer_out, input);
 }
 
-TEST_F(HpackHuffmanTableTest, ValidateMultiLevelDecodeTables) {
+TEST_F(GenericHuffmanTableTest, ValidateMultiLevelDecodeTables) {
   HpackHuffmanSymbol code[] = {
       {bits32("00000000000000000000000000000000"), 6, 0},
       {bits32("00000100000000000000000000000000"), 6, 1},
       {bits32("00001000000000000000000000000000"), 11, 2},
       {bits32("00001000001000000000000000000000"), 11, 3},
       {bits32("00001000010000000000000000000000"), 12, 4},
   };
   EXPECT_TRUE(table_.Initialize(code, arraysize(code)));
 
   EXPECT_EQ(2u, peer_.decode_tables().size());
@@ skipping 19 matching lines @@
 
     const DecodeTable& decode_table = peer_.decode_tables()[1];
     EXPECT_EQ(decode_table.prefix_length, 9);
     EXPECT_EQ(decode_table.indexed_length, 3);
     EXPECT_THAT(peer_.decode_entries(decode_table),
                 Pointwise(DecodeEntryEq(), expected));
   }
   EXPECT_EQ(bits8("00001000"), peer_.pad_bits());
 }
 
-TEST_F(HpackHuffmanTableTest, DecodeWithBadInput) {
+TEST_F(GenericHuffmanTableTest, DecodeWithBadInput) {
   HpackHuffmanSymbol code[] = {
       {bits32("01100000000000000000000000000000"), 4, 0},
       {bits32("01110000000000000000000000000000"), 4, 1},
       {bits32("00000000000000000000000000000000"), 2, 2},
       {bits32("01000000000000000000000000000000"), 3, 3},
       {bits32("10000000000000000000000000000000"), 5, 4},
       {bits32("10001000000000000000000000000000"), 5, 5},
       {bits32("10011000000000000000000000000000"), 6, 6},
       {bits32("10010000000000000000000000000000"), 5, 7},
       {bits32("10011100000000000000000000000000"), 16, 8}};
   EXPECT_TRUE(table_.Initialize(code, arraysize(code)));
 
   string buffer;
   const size_t capacity = 4;
   {
     // This example works: (2) 00 (3) 010 (2) 00 (6) 100110 (pad) 100.
     char input_storage[] = {bits8("00010001"), bits8("00110100")};
     StringPiece input(input_storage, arraysize(input_storage));
 
     HpackInputStream input_stream(std::numeric_limits<uint32_t>::max(), input);
-    EXPECT_TRUE(table_.DecodeString(&input_stream, capacity, &buffer));
+    EXPECT_TRUE(table_.GenericDecodeString(&input_stream, capacity, &buffer));
     EXPECT_EQ(buffer, "\x02\x03\x02\x06");
   }
   {
     // Expect to fail on an invalid code prefix.
     // (2) 00 (3) 010 (2) 00 (too-large) 101000 (pad) 100.
     char input_storage[] = {bits8("00010001"), bits8("01000111")};
     StringPiece input(input_storage, arraysize(input_storage));
 
     HpackInputStream input_stream(std::numeric_limits<uint32_t>::max(), input);
-    EXPECT_FALSE(table_.DecodeString(&input_stream, capacity, &buffer));
+    EXPECT_FALSE(table_.GenericDecodeString(&input_stream, capacity, &buffer));
     EXPECT_EQ(buffer, "\x02\x03\x02");
   }
   {
     // Repeat the shortest 0b00 code to overflow |buffer|. Expect to fail.
     std::vector<char> input_storage(1 + capacity / 4, '\0');
     StringPiece input(&input_storage[0], input_storage.size());
 
     HpackInputStream input_stream(std::numeric_limits<uint32_t>::max(), input);
-    EXPECT_FALSE(table_.DecodeString(&input_stream, capacity, &buffer));
+    EXPECT_FALSE(table_.GenericDecodeString(&input_stream, capacity, &buffer));
 
     std::vector<char> expected(capacity, '\x02');
     EXPECT_THAT(buffer, ElementsAreArray(expected));
     EXPECT_EQ(capacity, buffer.size());
   }
   {
     // Expect to fail if more than a byte of unconsumed input remains.
     // (6) 100110 (8 truncated) 1001110000
     char input_storage[] = {bits8("10011010"), bits8("01110000")};
     StringPiece input(input_storage, arraysize(input_storage));
 
     HpackInputStream input_stream(std::numeric_limits<uint32_t>::max(), input);
-    EXPECT_FALSE(table_.DecodeString(&input_stream, capacity, &buffer));
+    EXPECT_FALSE(table_.GenericDecodeString(&input_stream, capacity, &buffer));
     EXPECT_EQ(buffer, "\x06");
   }
 }
 
+// Tests of the ability to decode the HPACK Huffman Code, defined in:
+//     https://httpwg.github.io/specs/rfc7541.html#huffman.code
+class HpackHuffmanTableTest : public GenericHuffmanTableTest {
+ protected:
+  void SetUp() override {
+    std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode();
+    EXPECT_TRUE(table_.Initialize(&code[0], code.size()));
+    EXPECT_TRUE(table_.IsInitialized());
+  }
+
+  void DecodeStringTwice(const string& encoded,
+                         size_t out_capacity,
+                         string* out) {
+    // First decode with HpackHuffmanTable.
+    {
+      HpackInputStream input_stream(std::numeric_limits<uint32_t>::max(),
+                                    encoded);
+      EXPECT_TRUE(table_.GenericDecodeString(&input_stream, out_capacity, out));
+    }
+    // And decode again with the fixed decoder, confirming that the result is
+    // the same.
+    {
+      HpackInputStream input_stream(std::numeric_limits<uint32_t>::max(),
+                                    encoded);
+      string buf;
+      EXPECT_TRUE(
+          HpackHuffmanDecoder::DecodeString(&input_stream, out_capacity, &buf));
+      EXPECT_EQ(*out, buf);
+    }
+  }
+};
+
+TEST_F(HpackHuffmanTableTest, InitializeHpackCode) {
+  EXPECT_EQ(peer_.pad_bits(), '\xFF');  // First 8 bits of EOS.
+}
+
 TEST_F(HpackHuffmanTableTest, SpecRequestExamples) {
-  std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode();
-  EXPECT_TRUE(table_.Initialize(&code[0], code.size()));
-
   string buffer;
   string test_table[] = {
       a2b_hex("f1e3c2e5f23a6ba0ab90f4ff"),
       "www.example.com",
       a2b_hex("a8eb10649cbf"),
       "no-cache",
       a2b_hex("25a849e95ba97d7f"),
       "custom-key",
       a2b_hex("25a849e95bb8e8b4bf"),
       "custom-value",
   };
   // Round-trip each test example.
   for (size_t i = 0; i != arraysize(test_table); i += 2) {
     const string& encodedFixture(test_table[i]);
     const string& decodedFixture(test_table[i + 1]);
-    HpackInputStream input_stream(std::numeric_limits<uint32_t>::max(),
-                                  encodedFixture);
-
-    EXPECT_TRUE(
-        table_.DecodeString(&input_stream, decodedFixture.size(), &buffer));
+    DecodeStringTwice(encodedFixture, decodedFixture.size(), &buffer);
     EXPECT_EQ(decodedFixture, buffer);
     buffer = EncodeString(decodedFixture);
     EXPECT_EQ(encodedFixture, buffer);
   }
 }
 
 TEST_F(HpackHuffmanTableTest, SpecResponseExamples) {
-  std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode();
-  EXPECT_TRUE(table_.Initialize(&code[0], code.size()));
-
   string buffer;
   string test_table[] = {
       a2b_hex("6402"), "302", a2b_hex("aec3771a4b"), "private",
       a2b_hex("d07abe941054d444a8200595040b8166"
               "e082a62d1bff"),
       "Mon, 21 Oct 2013 20:13:21 GMT",
       a2b_hex("9d29ad171863c78f0b97c8e9ae82ae43"
               "d3"),
       "https://www.example.com", a2b_hex("94e7821dd7f2e6c7b335dfdfcd5b3960"
                                          "d5af27087f3672c1ab270fb5291f9587"
                                          "316065c003ed4ee5b1063d5007"),
       "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1",
   };
   // Round-trip each test example.
   for (size_t i = 0; i != arraysize(test_table); i += 2) {
     const string& encodedFixture(test_table[i]);
     const string& decodedFixture(test_table[i + 1]);
-    HpackInputStream input_stream(std::numeric_limits<uint32_t>::max(),
-                                  encodedFixture);
-
-    EXPECT_TRUE(
-        table_.DecodeString(&input_stream, decodedFixture.size(), &buffer));
+    DecodeStringTwice(encodedFixture, decodedFixture.size(), &buffer);
     EXPECT_EQ(decodedFixture, buffer);
     buffer = EncodeString(decodedFixture);
     EXPECT_EQ(encodedFixture, buffer);
   }
 }
 
-TEST_F(HpackHuffmanTableTest, RoundTripIndvidualSymbols) {
-  std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode();
-  EXPECT_TRUE(table_.Initialize(&code[0], code.size()));
-
+TEST_F(HpackHuffmanTableTest, RoundTripIndividualSymbols) {
   for (size_t i = 0; i != 256; i++) {
     char c = static_cast<char>(i);
     char storage[3] = {c, c, c};
     StringPiece input(storage, arraysize(storage));
-
     string buffer_in = EncodeString(input);
     string buffer_out;
 
-    HpackInputStream input_stream(std::numeric_limits<uint32_t>::max(),
-                                  buffer_in);
-    EXPECT_TRUE(table_.DecodeString(&input_stream, input.size(), &buffer_out));
+    DecodeStringTwice(buffer_in, input.size(), &buffer_out);
     EXPECT_EQ(input, buffer_out);
   }
 }
 
 TEST_F(HpackHuffmanTableTest, RoundTripSymbolSequence) {
-  std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode();
-  EXPECT_TRUE(table_.Initialize(&code[0], code.size()));
-
   char storage[512];
   for (size_t i = 0; i != 256; i++) {
     storage[i] = static_cast<char>(i);
     storage[511 - i] = static_cast<char>(i);
   }
   StringPiece input(storage, arraysize(storage));
 
   string buffer_in = EncodeString(input);
   string buffer_out;
-
-  HpackInputStream input_stream(std::numeric_limits<uint32_t>::max(),
-                                buffer_in);
-  EXPECT_TRUE(table_.DecodeString(&input_stream, input.size(), &buffer_out));
+  DecodeStringTwice(buffer_in, input.size(), &buffer_out);
   EXPECT_EQ(input, buffer_out);
 }
 
 TEST_F(HpackHuffmanTableTest, EncodedSizeAgreesWithEncodeString) {
-  std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode();
-  EXPECT_TRUE(table_.Initialize(&code[0], code.size()));
-
   string test_table[] = {
       "",
       "Mon, 21 Oct 2013 20:13:21 GMT",
       "https://www.example.com",
       "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1",
       string(1, '\0'),
       string("foo\0bar", 7),
       string(256, '\0'),
   };
   for (size_t i = 0; i != 256; ++i) {
     // Expand last |test_table| entry to cover all codes.
     test_table[arraysize(test_table) - 1][i] = static_cast<char>(i);
   }
 
   HpackOutputStream output_stream;
   string encoding;
   for (size_t i = 0; i != arraysize(test_table); ++i) {
     table_.EncodeString(test_table[i], &output_stream);
     output_stream.TakeString(&encoding);
     EXPECT_EQ(encoding.size(), table_.EncodedSize(test_table[i]));
   }
 }
 
 }  // namespace
 
 }  // namespace test
 
 }  // namespace net