Implement better HPACK Huffman code decoder.

HpackHuffmanDecoder uses less memory and decodes faster (around 30% CPU
reduction in micro benchmark) than previous HpackHuffmanTable decoder.  It is
hard coded; i.e., it cannot decode arbitrary codes, but since the
standardization process is complete, that does not seem necessary.

This CL lands server changes 103090098 and 109220294 by jamessynge
and 111872403 by bnc.

BUG=488484

Review URL: https://codereview.chromium.org/1568423002

Cr-Commit-Position: refs/heads/master@{#368954}

16 files changed, 1039 insertions, 125 deletions

diff --git a/net/net.gypi b/net/net.gypi
index eddea8a..0675546 100644
--- a/net/net.gypi
+++ b/net/net.gypi
@@ -1109,6 +1109,8 @@
       'spdy/hpack/hpack_entry.h',
       'spdy/hpack/hpack_header_table.cc',
       'spdy/hpack/hpack_header_table.h',
+      'spdy/hpack/hpack_huffman_decoder.cc',
+      'spdy/hpack/hpack_huffman_decoder.h',
       'spdy/hpack/hpack_huffman_table.cc',
       'spdy/hpack/hpack_huffman_table.h',
       'spdy/hpack/hpack_input_stream.cc',
@@ -1701,6 +1703,7 @@
       'spdy/hpack/hpack_encoder_test.cc',
       'spdy/hpack/hpack_entry_test.cc',
       'spdy/hpack/hpack_header_table_test.cc',
+      'spdy/hpack/hpack_huffman_decoder_test.cc',
       'spdy/hpack/hpack_huffman_table_test.cc',
       'spdy/hpack/hpack_input_stream_test.cc',
       'spdy/hpack/hpack_output_stream_test.cc',
diff --git a/net/spdy/fuzzing/hpack_fuzz_util.cc b/net/spdy/fuzzing/hpack_fuzz_util.cc
index 7bf5fcd..d82e34c 100644
--- a/net/spdy/fuzzing/hpack_fuzz_util.cc
+++ b/net/spdy/fuzzing/hpack_fuzz_util.cc
@@ -141,9 +141,9 @@ string HpackFuzzUtil::HeaderBlockPrefix(size_t block_size) {
 
 // static
 void HpackFuzzUtil::InitializeFuzzerContext(FuzzerContext* context) {
-  context->first_stage.reset(new HpackDecoder(ObtainHpackHuffmanTable()));
+  context->first_stage.reset(new HpackDecoder());
   context->second_stage.reset(new HpackEncoder(ObtainHpackHuffmanTable()));
-  context->third_stage.reset(new HpackDecoder(ObtainHpackHuffmanTable()));
+  context->third_stage.reset(new HpackDecoder());
 }
 
 // static
diff --git a/net/spdy/hpack/hpack_decoder.cc b/net/spdy/hpack/hpack_decoder.cc
index ab5c783..13654dd 100644
--- a/net/spdy/hpack/hpack_decoder.cc
+++ b/net/spdy/hpack/hpack_decoder.cc
@@ -21,9 +21,8 @@ const char kCookieKey[] = "cookie";
 
 }  // namespace
 
-HpackDecoder::HpackDecoder(const HpackHuffmanTable& table)
+HpackDecoder::HpackDecoder()
     : max_string_literal_size_(kDefaultMaxStringLiteralSize),
-      huffman_table_(table),
       handler_(nullptr),
       regular_header_seen_(false),
       header_block_started_(false) {}
@@ -209,7 +208,7 @@ bool HpackDecoder::DecodeNextStringLiteral(HpackInputStream* input_stream,
                                            StringPiece* output) {
   if (input_stream->MatchPrefixAndConsume(kStringLiteralHuffmanEncoded)) {
     string* buffer = is_key ? &key_buffer_ : &value_buffer_;
-    bool result = input_stream->DecodeNextHuffmanString(huffman_table_, buffer);
+    bool result = input_stream->DecodeNextHuffmanString(buffer);
     *output = StringPiece(*buffer);
     return result;
   }
diff --git a/net/spdy/hpack/hpack_decoder.h b/net/spdy/hpack/hpack_decoder.h
index 85c7f2b5..da6162d 100644
--- a/net/spdy/hpack/hpack_decoder.h
+++ b/net/spdy/hpack/hpack_decoder.h
@@ -25,8 +25,6 @@
 
 namespace net {
 
-class HpackHuffmanTable;
-
 namespace test {
 class HpackDecoderPeer;
 }  // namespace test
@@ -35,9 +33,7 @@ class NET_EXPORT_PRIVATE HpackDecoder {
  public:
   friend class test::HpackDecoderPeer;
 
-  // |table| is an initialized HPACK Huffman table, having an
-  // externally-managed lifetime which spans beyond HpackDecoder.
-  explicit HpackDecoder(const HpackHuffmanTable& table);
+  HpackDecoder();
   ~HpackDecoder();
 
   // Called upon acknowledgement of SETTINGS_HEADER_TABLE_SIZE.
@@ -102,9 +98,7 @@ class NET_EXPORT_PRIVATE HpackDecoder {
   std::string headers_block_buffer_;
   SpdyHeaderBlock decoded_block_;
 
-  // Huffman table to be applied to decoded Huffman literals,
-  // and scratch space for storing those decoded literals.
-  const HpackHuffmanTable& huffman_table_;
+  // Scratch space for storing decoded literals.
   std::string key_buffer_, value_buffer_;
 
   // If non-NULL, handles decoded headers.
diff --git a/net/spdy/hpack/hpack_decoder_test.cc b/net/spdy/hpack/hpack_decoder_test.cc
index bb21457..7c3b7d6 100644
--- a/net/spdy/hpack/hpack_decoder_test.cc
+++ b/net/spdy/hpack/hpack_decoder_test.cc
@@ -90,8 +90,7 @@ const size_t kLiteralBound = 1024;
 
 class HpackDecoderTest : public ::testing::TestWithParam<bool> {
  protected:
-  HpackDecoderTest()
-      : decoder_(ObtainHpackHuffmanTable()), decoder_peer_(&decoder_) {}
+  HpackDecoderTest() : decoder_(), decoder_peer_(&decoder_) {}
 
   bool DecodeHeaderBlock(StringPiece str) {
     if (GetParam()) {
diff --git a/net/spdy/hpack/hpack_huffman_decoder.cc b/net/spdy/hpack/hpack_huffman_decoder.cc
new file mode 100644
index 0000000..3573744
--- /dev/null
+++ b/net/spdy/hpack/hpack_huffman_decoder.cc
@@ -0,0 +1,410 @@
+// Copyright 2016 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.
+//
+// Decoder for strings encoded using the HPACK Huffman Code (see
+// https://httpwg.github.io/specs/rfc7541.html#huffman.code).
+//
+// This implementation is inspired by the One-Shift algorithm described in
+// "On the Implementation of Minimum Redundancy Prefix Codes", by Alistair
+// Moffat and Andrew Turpin, 1997.
+// See also https://en.wikipedia.org/wiki/Canonical_Huffman_code for background
+// on canonical Huffman codes.
+//
+// This decoder differs from that in .../spdy/hpack/hpack_huffman_table.cc
+// as follows:
+//   1) It decodes only the code described in RFC7541, where as the older
+//      implementation supported any canonical Huffman code provided at run
+//      time.
+//   2) It uses a fixed amount of memory allocated at build time; it doesn't
+//      construct a tree of of decoding tables based on an encoding
+//      table provided at run time.
+//   3) In benchmarks it runs from 10% to 70% faster, based on the length
+//      of the strings (faster for longer strings). Some of the improvements
+//      could be back ported, but others are fundamental to the approach.
+
+#include "net/spdy/hpack/hpack_huffman_decoder.h"
+
+#include <bitset>
+#include <limits>
+#include <utility>
+
+#include "base/logging.h"
+#include "net/spdy/hpack/hpack_input_stream.h"
+
+namespace net {
+namespace {
+
+typedef HpackHuffmanDecoder::HuffmanWord HuffmanWord;
+typedef HpackHuffmanDecoder::HuffmanCodeLength HuffmanCodeLength;
+
+const HuffmanCodeLength kHuffmanWordLength =
+    std::numeric_limits<HuffmanWord>::digits;
+
+const HuffmanCodeLength kMinCodeLength = 5;
+const HuffmanCodeLength kMaxCodeLength = 30;
+
+const HuffmanWord kInvalidLJCode = ~static_cast<HuffmanWord>(0);
+// Length of a code in bits to the first code with that length, left-justified.
+// Note that this can be computed from kLengthToFirstCanonical.
+const HuffmanWord kLengthToFirstLJCode[] = {
+    kInvalidLJCode,  // There are no codes of length 0.
+    kInvalidLJCode,  // There are no codes of length 1.
+    kInvalidLJCode,  // There are no codes of length 2.
+    kInvalidLJCode,  // There are no codes of length 3.
+    kInvalidLJCode,  // There are no codes of length 4.
+    0x00000000,      // Length 5.
+    0x50000000,      // Length 6.
+    0xb8000000,      // Length 7.
+    0xf8000000,      // Length 8.
+    kInvalidLJCode,  // There are no codes of length 9.
+    0xfe000000,      // Length 10.
+    0xff400000,      // Length 11.
+    0xffa00000,      // Length 12.
+    0xffc00000,      // Length 13.
+    0xfff00000,      // Length 14.
+    0xfff80000,      // Length 15.
+    kInvalidLJCode,  // There are no codes of length 16.
+    kInvalidLJCode,  // There are no codes of length 17.
+    kInvalidLJCode,  // There are no codes of length 18.
+    0xfffe0000,      // Length 19.
+    0xfffe6000,      // Length 20.
+    0xfffee000,      // Length 21.
+    0xffff4800,      // Length 22.
+    0xffffb000,      // Length 23.
+    0xffffea00,      // Length 24.
+    0xfffff600,      // Length 25.
+    0xfffff800,      // Length 26.
+    0xfffffbc0,      // Length 27.
+    0xfffffe20,      // Length 28.
+    kInvalidLJCode,  // There are no codes of length 29.
+    0xfffffff0,      // Length 30.
+};
+
+// TODO(jamessynge): Determine the performance impact of different types for
+// the elements of this array (i.e. a larger type uses more cache, yet might
+// better on some architectures).
+const uint8_t kInvalidCanonical = 255;
+// Maps from length of a code to the first 'canonical symbol' with that length.
+const uint8_t kLengthToFirstCanonical[] = {
+    kInvalidCanonical,  // Length 0, 0 codes.
+    kInvalidCanonical,  // Length 1, 0 codes.
+    kInvalidCanonical,  // Length 2, 0 codes.
+    kInvalidCanonical,  // Length 3, 0 codes.
+    kInvalidCanonical,  // Length 4, 0 codes.
+    0,                  // Length 5, 10 codes.
+    10,                 // Length 6, 26 codes.
+    36,                 // Length 7, 32 codes.
+    68,                 // Length 8, 6 codes.
+    kInvalidCanonical,  // Length 9, 0 codes.
+    74,                 // Length 10, 5 codes.
+    79,                 // Length 11, 3 codes.
+    82,                 // Length 12, 2 codes.
+    84,                 // Length 13, 6 codes.
+    90,                 // Length 14, 2 codes.
+    92,                 // Length 15, 3 codes.
+    kInvalidCanonical,  // Length 16, 0 codes.
+    kInvalidCanonical,  // Length 17, 0 codes.
+    kInvalidCanonical,  // Length 18, 0 codes.
+    95,                 // Length 19, 3 codes.
+    98,                 // Length 20, 8 codes.
+    106,                // Length 21, 13 codes.
+    119,                // Length 22, 26 codes.
+    145,                // Length 23, 29 codes.
+    174,                // Length 24, 12 codes.
+    186,                // Length 25, 4 codes.
+    190,                // Length 26, 15 codes.
+    205,                // Length 27, 19 codes.
+    224,                // Length 28, 29 codes.
+    kInvalidCanonical,  // Length 29, 0 codes.
+    253,                // Length 30, 4 codes.
+};
+
+// Mapping from canonical symbol (0 to 255) to actual symbol.
+// clang-format off
+const uint8_t kCanonicalToSymbol[] = {
+    '0',  '1',  '2',  'a',  'c',  'e',  'i',  'o',
+    's',  't',  0x20, '%',  '-',  '.',  '/',  '3',
+    '4',  '5',  '6',  '7',  '8',  '9',  '=',  'A',
+    '_',  'b',  'd',  'f',  'g',  'h',  'l',  'm',
+    'n',  'p',  'r',  'u',  ':',  'B',  'C',  'D',
+    'E',  'F',  'G',  'H',  'I',  'J',  'K',  'L',
+    'M',  'N',  'O',  'P',  'Q',  'R',  'S',  'T',
+    'U',  'V',  'W',  'Y',  'j',  'k',  'q',  'v',
+    'w',  'x',  'y',  'z',  '&',  '*',  ',',  ';',
+    'X',  'Z',  '!',  '\"', '(',  ')',  '?',  '\'',
+    '+',  '|',  '#',  '>',  0x00, '$',  '@',  '[',
+    ']',  '~',  '^',  '}',  '<',  '`',  '{',  '\\',
+    0xc3, 0xd0, 0x80, 0x82, 0x83, 0xa2, 0xb8, 0xc2,
+    0xe0, 0xe2, 0x99, 0xa1, 0xa7, 0xac, 0xb0, 0xb1,
+    0xb3, 0xd1, 0xd8, 0xd9, 0xe3, 0xe5, 0xe6, 0x81,
+    0x84, 0x85, 0x86, 0x88, 0x92, 0x9a, 0x9c, 0xa0,
+    0xa3, 0xa4, 0xa9, 0xaa, 0xad, 0xb2, 0xb5, 0xb9,
+    0xba, 0xbb, 0xbd, 0xbe, 0xc4, 0xc6, 0xe4, 0xe8,
+    0xe9, 0x01, 0x87, 0x89, 0x8a, 0x8b, 0x8c, 0x8d,
+    0x8f, 0x93, 0x95, 0x96, 0x97, 0x98, 0x9b, 0x9d,
+    0x9e, 0xa5, 0xa6, 0xa8, 0xae, 0xaf, 0xb4, 0xb6,
+    0xb7, 0xbc, 0xbf, 0xc5, 0xe7, 0xef, 0x09, 0x8e,
+    0x90, 0x91, 0x94, 0x9f, 0xab, 0xce, 0xd7, 0xe1,
+    0xec, 0xed, 0xc7, 0xcf, 0xea, 0xeb, 0xc0, 0xc1,
+    0xc8, 0xc9, 0xca, 0xcd, 0xd2, 0xd5, 0xda, 0xdb,
+    0xee, 0xf0, 0xf2, 0xf3, 0xff, 0xcb, 0xcc, 0xd3,
+    0xd4, 0xd6, 0xdd, 0xde, 0xdf, 0xf1, 0xf4, 0xf5,
+    0xf6, 0xf7, 0xf8, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe,
+    0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x0b,
+    0x0c, 0x0e, 0x0f, 0x10, 0x11, 0x12, 0x13, 0x14,
+    0x15, 0x17, 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d,
+    0x1e, 0x1f, 0x7f, 0xdc, 0xf9, 0x0a, 0x0d, 0x16,
+};
+// clang-format on
+
+#ifndef NDEBUG
+
+// Only used in DLOG.
+bool IsEOSPrefix(HuffmanWord bits, HuffmanCodeLength bits_available) {
+  if (bits_available == 0) {
+    return true;
+  }
+  // We expect all the bits below the high order |bits_available| bits
+  // to be cleared.
+  HuffmanWord expected = HuffmanWord(0xffffffff) << (32 - bits_available);
+  return bits == expected;
+}
+
+#endif  // NDEBUG
+
+}  // namespace
+
+// TODO(jamessynge): Should we read these magic numbers from
+// kLengthToFirstLJCode? Would that reduce cache consumption? Slow decoding?
+// TODO(jamessynge): Is this being inlined by the compiler? Should we inline
+// into DecodeString the tests for code lengths 5 through 8 (> 99% of codes
+// according to the HPACK spec)?
+HpackHuffmanDecoder::HuffmanCodeLength HpackHuffmanDecoder::CodeLengthOfPrefix(
+    HpackHuffmanDecoder::HuffmanWord value) {
+  HuffmanCodeLength length;
+  if (value < 0xb8000000) {
+    if (value < 0x50000000) {
+      length = 5;
+    } else {
+      length = 6;
+    }
+  } else {
+    if (value < 0xfe000000) {
+      if (value < 0xf8000000) {
+        length = 7;
+      } else {
+        length = 8;
+      }
+    } else {
+      if (value < 0xffc00000) {
+        if (value < 0xffa00000) {
+          if (value < 0xff400000) {
+            length = 10;
+          } else {
+            length = 11;
+          }
+        } else {
+          length = 12;
+        }
+      } else {
+        if (value < 0xfffe0000) {
+          if (value < 0xfff80000) {
+            if (value < 0xfff00000) {
+              length = 13;
+            } else {
+              length = 14;
+            }
+          } else {
+            length = 15;
+          }
+        } else {
+          if (value < 0xffff4800) {
+            if (value < 0xfffee000) {
+              if (value < 0xfffe6000) {
+                length = 19;
+              } else {
+                length = 20;
+              }
+            } else {
+              length = 21;
+            }
+          } else {
+            if (value < 0xffffea00) {
+              if (value < 0xffffb000) {
+                length = 22;
+              } else {
+                length = 23;
+              }
+            } else {
+              if (value < 0xfffffbc0) {
+                if (value < 0xfffff800) {
+                  if (value < 0xfffff600) {
+                    length = 24;
+                  } else {
+                    length = 25;
+                  }
+                } else {
+                  length = 26;
+                }
+              } else {
+                if (value < 0xfffffff0) {
+                  if (value < 0xfffffe20) {
+                    length = 27;
+                  } else {
+                    length = 28;
+                  }
+                } else {
+                  length = 30;
+                }
+              }
+            }
+          }
+        }
+      }
+    }
+  }
+  return length;
+}
+
+HuffmanWord HpackHuffmanDecoder::DecodeToCanonical(
+    HuffmanCodeLength code_length,
+    HuffmanWord bits) {
+  DCHECK_LE(kMinCodeLength, code_length);
+  DCHECK_LE(code_length, kMaxCodeLength);
+
+  // What is the first left-justified code of length |code_length|?
+  HuffmanWord first_lj_code = kLengthToFirstLJCode[code_length];
+  DCHECK_NE(kInvalidLJCode, first_lj_code);
+
+  // Which canonical symbol corresponds to the high order |code_length|
+  // bits of |first_lj_code|?
+  HuffmanWord first_canonical = kLengthToFirstCanonical[code_length];
+  DCHECK_NE(kInvalidCanonical, first_canonical);
+
+  // What is the position of the canonical symbol being decoded within
+  // the canonical symbols of length |code_length|?
+  HuffmanWord ordinal_in_length =
+      ((bits - first_lj_code) >> (kHuffmanWordLength - code_length));
+
+  // Combined these two to produce the position of the canonical symbol
+  // being decoded within all of the canonical symbols.
+  return first_canonical + ordinal_in_length;
+}
+
+char HpackHuffmanDecoder::CanonicalToSource(HuffmanWord canonical) {
+  DCHECK_LT(canonical, 256u);
+  return static_cast<char>(kCanonicalToSymbol[canonical]);
+}
+
+// TODO(jamessynge): Maybe further refactorings, including just passing in a
+// StringPiece instead of an HpackInputStream, thus avoiding the PeekBits calls,
+// and also allowing us to separate the code into portions dealing with long
+// strings, and a later portion dealing with the last few bytes of strings.
+// TODO(jamessynge): Determine if that is worth it by adding some counters to
+// measure the distribution of string sizes seen in practice.
+bool HpackHuffmanDecoder::DecodeString(HpackInputStream* in,
+                                       size_t out_capacity,
+                                       std::string* out) {
+  out->clear();
+
+  // Load |bits| with the leading bits of the input stream, left justified
+  // (i.e. the bits of the first byte are the high-order bits of |bits|,
+  // and the bits of the fourth byte are the low-order bits of |bits|).
+  // |peeked_success| if there are more bits in |*in| (i.e. the encoding
+  // of the string to be decoded is more than 4 bytes).
+
+  auto bits_available_and_bits = in->InitializePeekBits();
+  HuffmanCodeLength bits_available = bits_available_and_bits.first;
+  HuffmanWord bits = bits_available_and_bits.second;
+
+  // |peeked_success| tracks whether the previous PeekBits call was able to
+  // store any new bits into |bits|. For the first pass through the loop below
+  // the value false is appropriate:
+  //     If we have 32 bits (i.e. the input has at least 4 bytes), then:
+  //         |peeked_sucess| is not examined because |code_length| is
+  //         at most 30 in the HPACK Huffman Code.
+  //     If we have at most 24 bits (i.e. the input has at most 3 bytes), then:
+  //         It is possible that the very first |code_length| is greater than
+  //         |bits_available|, in which case we need to read peeked_success to
+  //         determine whether we should try to read more input, or have already
+  //         loaded |bits| with the final bits of the input.
+  // After the first loop |peeked_success| has been set by a call to PeekBits.
+  bool peeked_success = false;
+
+  while (true) {
+    const HuffmanCodeLength code_length = CodeLengthOfPrefix(bits);
+    DCHECK_LE(kMinCodeLength, code_length);
+    DCHECK_LE(code_length, kMaxCodeLength);
+    DVLOG(1) << "bits: 0b" << std::bitset<32>(bits)
+             << " (avail=" << bits_available << ")"
+             << "    prefix length: " << code_length
+             << (code_length > bits_available ? "      *****" : "");
+    if (code_length > bits_available) {
+      if (!peeked_success) {
+        // Unable to read enough input for a match. If only a portion of
+        // the last byte remains, this is a successful EOS condition.
+        // Note that this does NOT check whether the available bits are all
+        // set to 1, which the encoder is required to set at EOS, and the
+        // decoder is required to check.
+        // TODO(jamessynge): Discuss whether we should enforce this check,
+        // as required by the RFC, presumably flag guarded so that we can
+        // disable it should it occur a lot. From my testing it appears that
+        // our encoder may be doing this wrong. Sigh.
+        // TODO(jamessynge): Add a counter for how often the remaining bits
+        // are non-zero.
+        in->ConsumeByteRemainder();
+        DLOG_IF(WARNING,
+                (in->HasMoreData() || !IsEOSPrefix(bits, bits_available)))
+            << "bits: 0b" << std::bitset<32>(bits)
+            << " (avail=" << bits_available << ")"
+            << "    prefix length: " << code_length
+            << "    HasMoreData: " << in->HasMoreData();
+        return !in->HasMoreData();
+      }
+      // We're dealing with a long code. It *might* be useful to add a special
+      // method to HpackInputStream for getting more than "at most 8" bits
+      // at a time.
+      do {
+        peeked_success = in->PeekBits(&bits_available, &bits);
+      } while (peeked_success && bits_available < 32);
+    } else {
+      if (out->size() == out_capacity) {
+        // This code would cause us to overflow |out_capacity|.
+        // TODO(jamessynge) Avoid this case by pre-allocating out based on
+        // scaling up the encoded size by 8/5 (shortest codes are 5 bits).
+        DLOG(WARNING) << "Output size too large: " << out_capacity;
+        return false;
+      }
+
+      // Convert from the prefix code of length |code_length| to the
+      // canonical symbol (i.e. where the input symbols (bytes) are ordered by
+      // increasing code length and then by their increasing uint8 value).
+      HuffmanWord canonical = DecodeToCanonical(code_length, bits);
+
+      bits = bits << code_length;
+      bits_available -= code_length;
+      in->ConsumeBits(code_length);
+
+      if (canonical < 256) {
+        out->push_back(CanonicalToSource(canonical));
+      } else {
+        // Encoder is not supposed to explicity encode the EOS symbol (30
+        // 1-bits).
+        // TODO(jamessynge): Discuss returning false here, as required by HPACK.
+        DCHECK(false) << "EOS explicitly encoded!\n"
+                      << "bits: 0b" << std::bitset<32>(bits)
+                      << " (avail=" << bits_available << ")"
+                      << " prefix length: " << code_length
+                      << " canonical: " << canonical;
+      }
+      // Get some more bits for decoding (up to 8). |peeked_success| is true
+      // if we got any bits.
+      peeked_success = in->PeekBits(&bits_available, &bits);
+    }
+    DLOG_IF(WARNING, (VLOG_IS_ON(1) && bits_available < 32 && !peeked_success))
+        << "no more peeking possible";
+  }
+}
+
+}  // namespace net
diff --git a/net/spdy/hpack/hpack_huffman_decoder.h b/net/spdy/hpack/hpack_huffman_decoder.h
new file mode 100644
index 0000000..d63aa04
--- /dev/null
+++ b/net/spdy/hpack/hpack_huffman_decoder.h
@@ -0,0 +1,70 @@
+// Copyright 2016 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.
+
+#ifndef NET_SPDY_HPACK_HPACK_HUFFMAN_DECODER_H_
+#define NET_SPDY_HPACK_HPACK_HUFFMAN_DECODER_H_
+
+#include <stddef.h>
+#include <stdint.h>
+
+#include <string>
+
+#include "net/base/net_export.h"
+#include "net/spdy/hpack/hpack_input_stream.h"
+
+namespace net {
+namespace test {
+class HpackHuffmanDecoderPeer;
+}  // namespace test
+
+// Declared as a class to simplify testing.
+// No instances are actually allocated.
+class NET_EXPORT_PRIVATE HpackHuffmanDecoder {
+ public:
+  typedef uint32_t HuffmanWord;
+  typedef size_t HuffmanCodeLength;
+
+  HpackHuffmanDecoder() = delete;
+
+  // Decodes a string that has been encoded using the HPACK Huffman Code (see
+  // https://httpwg.github.io/specs/rfc7541.html#huffman.code), reading the
+  // encoded bitstream from |*in|, appending each decoded char to |*out|.
+  // To avoid repeatedly growing the |*out| string, the caller should reserve
+  // sufficient space in |*out| to hold decoded output.
+  // DecodeString() halts when |in| runs out of input, in which case true is
+  // returned. It also halts (returning false) if an invalid Huffman code
+  // prefix is read, or if |out_capacity| would otherwise be overflowed.
+  static bool DecodeString(HpackInputStream* in,
+                           size_t out_capacity,
+                           std::string* out);
+
+ private:
+  friend class test::HpackHuffmanDecoderPeer;
+
+  // The following private methods are declared here rather than simply
+  // inlined into DecodeString so that they can be tested directly.
+
+  // Returns the length (in bits) of the HPACK Huffman code that starts with
+  // the high bits of |value|.
+  static HuffmanCodeLength CodeLengthOfPrefix(HuffmanWord value);
+
+  // Decodes the code in the high |code_length| bits of |bits| to the
+  // corresponding canonical symbol.
+  // Returns a value in the range [0, 256] (257 values). 256 is the EOS symbol,
+  // which must not be explicitly encoded; the HPACK spec says that a decoder
+  // must treat EOS as a decoding error.
+  // Note that the canonical symbol is not the final value to be output because
+  // the source symbols are not in descending probability order, so another
+  // translation is required (see CanonicalToSource below).
+  static HuffmanWord DecodeToCanonical(HuffmanCodeLength code_length,
+                                       HuffmanWord bits);
+
+  // Converts a canonical symbol to the source symbol (the char in the original
+  // string that was encoded).
+  static char CanonicalToSource(HuffmanWord canonical);
+};
+
+}  // namespace net
+
+#endif  // NET_SPDY_HPACK_HPACK_HUFFMAN_DECODER_H_
diff --git a/net/spdy/hpack/hpack_huffman_decoder_test.cc b/net/spdy/hpack/hpack_huffman_decoder_test.cc
new file mode 100644
index 0000000..5b7b16c
--- /dev/null
+++ b/net/spdy/hpack/hpack_huffman_decoder_test.cc
@@ -0,0 +1,292 @@
+// Copyright 2016 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_decoder.h"
+
+#include <bitset>
+#include <limits>
+
+#include "base/logging.h"
+#include "base/macros.h"
+#include "base/rand_util.h"
+#include "base/strings/string_piece.h"
+#include "net/spdy/hpack/hpack_constants.h"
+#include "net/spdy/hpack/hpack_huffman_table.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/gtest/include/gtest/gtest.h"
+
+using base::StringPiece;
+
+namespace net {
+namespace test {
+
+namespace {
+
+uint32_t RandUint32() {
+  return static_cast<uint32_t>(base::RandUint64() & 0xffffffff);
+}
+
+}  // anonymous namespace
+
+// Bits(HuffmanWord) constructs a bitset<32>, which produces nicely formatted
+// binary numbers when LOG'd.
+typedef std::bitset<32> Bits;
+
+typedef HpackHuffmanDecoder::HuffmanWord HuffmanWord;
+typedef HpackHuffmanDecoder::HuffmanCodeLength HuffmanCodeLength;
+
+class HpackHuffmanDecoderPeer {
+ public:
+  static HuffmanCodeLength CodeLengthOfPrefix(HuffmanWord value) {
+    return HpackHuffmanDecoder::CodeLengthOfPrefix(value);
+  }
+
+  static HuffmanWord DecodeToCanonical(HuffmanCodeLength code_length,
+                                       HuffmanWord bits) {
+    return HpackHuffmanDecoder::DecodeToCanonical(code_length, bits);
+  }
+
+  static char CanonicalToSource(HuffmanWord canonical) {
+    return HpackHuffmanDecoder::CanonicalToSource(canonical);
+  }
+};
+
+// Tests of the ability to decode the HPACK Huffman Code, defined in:
+//     https://httpwg.github.io/specs/rfc7541.html#huffman.code
+class HpackHuffmanDecoderTest : public ::testing::Test {
+ protected:
+  HpackHuffmanDecoderTest() : table_(ObtainHpackHuffmanTable()) {}
+
+  // Since kHpackHuffmanCode doesn't include the canonical symbol value,
+  // this helper helps us to decode directly to the source symbol, allowing
+  // for EOS.
+  uint16_t DecodeToSource(HuffmanCodeLength code_length, HuffmanWord bits) {
+    HuffmanWord canonical =
+        HpackHuffmanDecoderPeer::DecodeToCanonical(code_length, bits);
+    EXPECT_LE(canonical, 256u);
+    if (canonical == 256u) {
+      return canonical;
+    }
+    return static_cast<unsigned char>(
+        HpackHuffmanDecoderPeer::CanonicalToSource(canonical));
+  }
+
+  void EncodeString(StringPiece input, std::string* encoded) {
+    HpackOutputStream output_stream;
+    table_.EncodeString(input, &output_stream);
+    encoded->clear();
+    output_stream.TakeString(encoded);
+    // Verify EncodedSize() agrees with EncodeString().
+    EXPECT_EQ(encoded->size(), table_.EncodedSize(input));
+  }
+
+  std::string EncodeString(StringPiece input) {
+    std::string result;
+    EncodeString(input, &result);
+    return result;
+  }
+
+  const HpackHuffmanTable& table_;
+};
+
+TEST_F(HpackHuffmanDecoderTest, CodeLengthOfPrefix) {
+  for (const HpackHuffmanSymbol& entry : HpackHuffmanCode()) {
+    // First confirm our assumption that the low order bits of entry.code
+    // (those not part of the high order entry.length bits) are zero.
+    uint32_t non_code_bits = 0xffffffff >> entry.length;
+    EXPECT_EQ(0u, entry.code & non_code_bits);
+
+    // entry.code has a code length of entry.length.
+    EXPECT_EQ(entry.length,
+              HpackHuffmanDecoderPeer::CodeLengthOfPrefix(entry.code))
+        << "Full code: " << Bits(entry.code) << "\n"
+        << "       ID: " << entry.id;
+
+    // Let's try again with all the low order bits set to 1.
+    uint32_t bits = entry.code | (0xffffffff >> entry.length);
+    EXPECT_EQ(entry.length, HpackHuffmanDecoderPeer::CodeLengthOfPrefix(bits))
+        << "Full code: " << Bits(entry.code) << "\n"
+        << "     bits: " << Bits(bits) << "\n"
+        << "       ID: " << entry.id;
+
+    // Let's try again with random low order bits.
+    uint32_t rand = RandUint32() & (0xffffffff >> entry.length);
+    bits = entry.code | rand;
+    EXPECT_EQ(entry.length, HpackHuffmanDecoderPeer::CodeLengthOfPrefix(bits))
+        << "Full code: " << Bits(entry.code) << "\n"
+        << "     rand: " << Bits(rand) << "\n"
+        << "     bits: " << Bits(bits) << "\n"
+        << "       ID: " << entry.id;
+
+    // If fewer bits are available and low order bits are zero after left
+    // shifting (should be true), CodeLengthOfPrefix should never return
+    // a value that is <= the number of available bits.
+    for (uint8_t available = entry.length - 1; available > 0; --available) {
+      uint32_t mask = 0xffffffff;
+      uint32_t avail_mask = mask << (32 - available);
+      bits = entry.code & avail_mask;
+      EXPECT_LT(available, HpackHuffmanDecoderPeer::CodeLengthOfPrefix(bits))
+          << "Full code: " << Bits(entry.code) << "\n"
+          << "availMask: " << Bits(avail_mask) << "\n"
+          << "     bits: " << Bits(bits) << "\n"
+          << "       ID: " << entry.id;
+    }
+  }
+}
+
+TEST_F(HpackHuffmanDecoderTest, DecodeToSource) {
+  for (const HpackHuffmanSymbol& entry : HpackHuffmanCode()) {
+    // Check that entry.code, which has all the low order bits set to 0,
+    // decodes to entry.id.
+    EXPECT_EQ(entry.id, DecodeToSource(entry.length, entry.code))
+        << "   Length: " << entry.length << "\n"
+        << "Full code: " << Bits(entry.code);
+
+    // Let's try again with all the low order bits set to 1.
+    uint32_t bits = entry.code | (0xffffffff >> entry.length);
+    EXPECT_EQ(entry.id, DecodeToSource(entry.length, bits))
+        << "   Length: " << entry.length << "\n"
+        << "Full code: " << Bits(entry.code) << "\n"
+        << "     bits: " << Bits(bits);
+
+    // Let's try again with random low order bits.
+    uint32_t rand = RandUint32() & (0xffffffff >> entry.length);
+    bits = entry.code | rand;
+    EXPECT_EQ(entry.id, DecodeToSource(entry.length, bits))
+        << "   Length: " << entry.length << "\n"
+        << "Full code: " << Bits(entry.code) << "\n"
+        << "     rand: " << Bits(rand) << "\n"
+        << "     bits: " << Bits(bits);
+  }
+}
+
+TEST_F(HpackHuffmanDecoderTest, SpecRequestExamples) {
+  std::string buffer;
+  std::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 std::string& encodedFixture(test_table[i]);
+    const std::string& decodedFixture(test_table[i + 1]);
+    HpackInputStream input_stream(std::numeric_limits<uint32_t>::max(),
+                                  encodedFixture);
+    EXPECT_TRUE(HpackHuffmanDecoder::DecodeString(
+        &input_stream, decodedFixture.size(), &buffer));
+    EXPECT_EQ(decodedFixture, buffer);
+    buffer = EncodeString(decodedFixture);
+    EXPECT_EQ(encodedFixture, buffer);
+  }
+}
+
+TEST_F(HpackHuffmanDecoderTest, TooLong) {
+  std::string buffer;
+  std::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, but with too small an output buffer.
+  for (size_t i = 0; i != arraysize(test_table); i += 2) {
+    const std::string& encodedFixture(test_table[i]);
+    const std::string& decodedFixture(test_table[i + 1]);
+    uint32_t limit = base::RandInt(0, decodedFixture.size() - 1);
+    HpackInputStream strm(std::numeric_limits<uint32_t>::max(), encodedFixture);
+    EXPECT_FALSE(HpackHuffmanDecoder::DecodeString(&strm, limit, &buffer));
+
+    // This is NOT a required test as it really tests an implementation detail,
+    // i.e. the fact that it writes the first |limit| values into |buffer|,
+    // then returns false leaving those chars in the buffer.
+    EXPECT_EQ(decodedFixture.substr(0, limit), buffer);
+  }
+}
+
+TEST_F(HpackHuffmanDecoderTest, SpecResponseExamples) {
+  std::string buffer;
+  // clang-format off
+  std::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",
+  };
+  // clang-format on
+  // Round-trip each test example.
+  for (size_t i = 0; i != arraysize(test_table); i += 2) {
+    const std::string& encodedFixture(test_table[i]);
+    const std::string& decodedFixture(test_table[i + 1]);
+    HpackInputStream input_stream(std::numeric_limits<uint32_t>::max(),
+                                  encodedFixture);
+    EXPECT_TRUE(HpackHuffmanDecoder::DecodeString(
+        &input_stream, decodedFixture.size(), &buffer));
+    EXPECT_EQ(decodedFixture, buffer);
+    buffer = EncodeString(decodedFixture);
+    EXPECT_EQ(encodedFixture, buffer);
+  }
+}
+
+TEST_F(HpackHuffmanDecoderTest, 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));
+    std::string buffer_in = EncodeString(input);
+    std::string buffer_out;
+    HpackInputStream input_stream(std::numeric_limits<uint32_t>::max(),
+                                  buffer_in);
+    EXPECT_TRUE(HpackHuffmanDecoder::DecodeString(&input_stream, input.size(),
+                                                  &buffer_out));
+    EXPECT_EQ(input, buffer_out);
+  }
+}
+
+// Creates 256 input strings, each with a unique byte value i used to sandwich
+// all the other higher byte values.
+TEST_F(HpackHuffmanDecoderTest, RoundTripSymbolSequences) {
+  std::string input;
+  std::string encoded;
+  std::string decoded;
+  for (size_t i = 0; i != 256; i++) {
+    input.clear();
+    auto ic = static_cast<char>(i);
+    input.push_back(ic);
+    for (size_t j = i; j != 256; j++) {
+      input.push_back(static_cast<char>(j));
+      input.push_back(ic);
+    }
+    EncodeString(input, &encoded);
+    HpackInputStream input_stream(std::numeric_limits<uint32_t>::max(),
+                                  encoded);
+    EXPECT_TRUE(HpackHuffmanDecoder::DecodeString(&input_stream, input.size(),
+                                                  &decoded));
+    EXPECT_EQ(input, decoded);
+  }
+}
+
+}  // namespace test
+}  // namespace net
diff --git a/net/spdy/hpack/hpack_huffman_table.cc b/net/spdy/hpack/hpack_huffman_table.cc
index b56c58e..e29e1c4 100644
--- a/net/spdy/hpack/hpack_huffman_table.cc
+++ b/net/spdy/hpack/hpack_huffman_table.cc
@@ -6,6 +6,7 @@
 
 #include <algorithm>
 #include <cmath>
+#include <memory>
 
 #include "base/logging.h"
 #include "base/numerics/safe_conversions.h"
@@ -263,9 +264,9 @@ size_t HpackHuffmanTable::EncodedSize(StringPiece in) const {
   return bit_count / 8;
 }
 
-bool HpackHuffmanTable::DecodeString(HpackInputStream* in,
-                                     size_t out_capacity,
-                                     string* out) const {
+bool HpackHuffmanTable::GenericDecodeString(HpackInputStream* in,
+                                            size_t out_capacity,
+                                            string* out) const {
   // Number of decode iterations required for a 32-bit code.
   const int kDecodeIterations = static_cast<int>(
       std::ceil((32.f - kDecodeTableRootBits) / kDecodeTableBranchBits));
diff --git a/net/spdy/hpack/hpack_huffman_table.h b/net/spdy/hpack/hpack_huffman_table.h
index 5662715..6fd60e4 100644
--- a/net/spdy/hpack/hpack_huffman_table.h
+++ b/net/spdy/hpack/hpack_huffman_table.h
@@ -82,14 +82,18 @@ class NET_EXPORT_PRIVATE HpackHuffmanTable {
   // Returns the encoded size of the input string.
   size_t EncodedSize(base::StringPiece in) const;
 
-  // Decodes symbols from |in| into |out|. It is the caller's responsibility
-  // to ensure |out| has a reserved a sufficient buffer to hold decoded output.
-  // DecodeString() halts when |in| runs out of input, in which case true is
-  // returned. It also halts (returning false) if an invalid Huffman code
-  // prefix is read, or if |out_capacity| would otherwise be overflowed.
-  bool DecodeString(HpackInputStream* in,
-                    size_t out_capacity,
-                    std::string* out) const;
+  // Decodes symbols from |in| into |out|, using the support for generic (any)
+  // huffman tables, not just those defined in the HPACK spec. It is the
+  // caller's responsibility to ensure |out| has reserved a sufficient buffer to
+  // hold decoded output. GenericDecodeString() halts when |in| runs out of
+  // input, in which case true is returned. It also halts (returning false) if
+  // an invalid Huffman code prefix is read, or if |out_capacity| would
+  // otherwise be overflowed.
+  // DEPRECATED: HpackHuffmanDecoder is now used for decoding strings encoded
+  // according to the Huffman Table in the HPACK spec.
+  bool GenericDecodeString(HpackInputStream* in,
+                           size_t out_capacity,
+                           std::string* out) const;
 
  private:
   // Expects symbols ordered on length & ID ascending.
diff --git a/net/spdy/hpack/hpack_huffman_table_test.cc b/net/spdy/hpack/hpack_huffman_table_test.cc
index fe2420e..95ae765 100644
--- a/net/spdy/hpack/hpack_huffman_table_test.cc
+++ b/net/spdy/hpack/hpack_huffman_table_test.cc
@@ -9,9 +9,12 @@
 #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"
@@ -59,9 +62,11 @@ class HpackHuffmanTablePeer {
 
 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;
@@ -92,14 +97,7 @@ 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[] = {
@@ -195,7 +193,7 @@ TEST_F(HpackHuffmanTableTest, InitializeEdgeCases) {
   }
 }
 
-TEST_F(HpackHuffmanTableTest, ValidateInternalsWithSmallCode) {
+TEST_F(GenericHuffmanTableTest, ValidateInternalsWithSmallCode) {
   HpackHuffmanSymbol code[] = {
       {bits32("01100000000000000000000000000000"), 4, 0},  // 3rd.
       {bits32("01110000000000000000000000000000"), 4, 1},  // 4th.
@@ -244,11 +242,12 @@ TEST_F(HpackHuffmanTableTest, ValidateInternalsWithSmallCode) {
   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},
@@ -288,7 +287,7 @@ TEST_F(HpackHuffmanTableTest, ValidateMultiLevelDecodeTables) {
   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},
@@ -309,7 +308,7 @@ TEST_F(HpackHuffmanTableTest, DecodeWithBadInput) {
     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");
   }
   {
@@ -319,7 +318,7 @@ TEST_F(HpackHuffmanTableTest, DecodeWithBadInput) {
     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");
   }
   {
@@ -328,7 +327,7 @@ TEST_F(HpackHuffmanTableTest, DecodeWithBadInput) {
     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));
@@ -341,15 +340,48 @@ TEST_F(HpackHuffmanTableTest, DecodeWithBadInput) {
     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");
   }
 }
 
-TEST_F(HpackHuffmanTableTest, SpecRequestExamples) {
-  std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode();
-  EXPECT_TRUE(table_.Initialize(&code[0], code.size()));
+// 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) {
   string buffer;
   string test_table[] = {
       a2b_hex("f1e3c2e5f23a6ba0ab90f4ff"),
@@ -365,11 +397,7 @@ TEST_F(HpackHuffmanTableTest, SpecRequestExamples) {
   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);
@@ -377,9 +405,6 @@ TEST_F(HpackHuffmanTableTest, SpecRequestExamples) {
 }
 
 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",
@@ -397,40 +422,27 @@ TEST_F(HpackHuffmanTableTest, SpecResponseExamples) {
   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);
@@ -440,17 +452,11 @@ TEST_F(HpackHuffmanTableTest, RoundTripSymbolSequence) {
 
   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",
diff --git a/net/spdy/hpack/hpack_input_stream.cc b/net/spdy/hpack/hpack_input_stream.cc
index f186928..e9e9540 100644
--- a/net/spdy/hpack/hpack_input_stream.cc
+++ b/net/spdy/hpack/hpack_input_stream.cc
@@ -7,6 +7,7 @@
 #include <algorithm>
 
 #include "base/logging.h"
+#include "net/spdy/hpack/hpack_huffman_decoder.h"
 
 namespace net {
 
@@ -45,6 +46,7 @@ bool HpackInputStream::MatchPrefixAndConsume(HpackPrefix prefix) {
 
 bool HpackInputStream::PeekNextOctet(uint8_t* next_octet) {
   if ((bit_offset_ > 0) || buffer_.empty()) {
+    DVLOG(1) << "HpackInputStream::PeekNextOctet bit_offset_=" << bit_offset_;
     return false;
   }
 
@@ -73,6 +75,7 @@ bool HpackInputStream::DecodeNextUint32(uint32_t* I) {
   uint8_t next_marker = (1 << N) - 1;
   uint8_t next_octet = 0;
   if (!DecodeNextOctet(&next_octet)) {
+    DVLOG(1) << "HpackInputStream::DecodeNextUint32 initial octet error";
     return false;
   }
   *I = next_octet & next_marker;
@@ -82,6 +85,7 @@ bool HpackInputStream::DecodeNextUint32(uint32_t* I) {
   while (has_more && (shift < 32)) {
     uint8_t next_octet = 0;
     if (!DecodeNextOctet(&next_octet)) {
+      DVLOG(1) << "HpackInputStream::DecodeNextUint32 shift=" << shift;
       return false;
     }
     has_more = (next_octet & 0x80) != 0;
@@ -89,6 +93,7 @@ bool HpackInputStream::DecodeNextUint32(uint32_t* I) {
     uint32_t addend = next_octet << shift;
     // Check for overflow.
     if ((addend >> shift) != next_octet) {
+      DVLOG(1) << "HpackInputStream::DecodeNextUint32 overflow";
       return false;
     }
     *I += addend;
@@ -117,14 +122,17 @@ bool HpackInputStream::DecodeNextIdentityString(StringPiece* str) {
   return true;
 }
 
-bool HpackInputStream::DecodeNextHuffmanString(const HpackHuffmanTable& table,
-                                               string* str) {
+bool HpackInputStream::DecodeNextHuffmanString(string* str) {
   uint32_t encoded_size = 0;
   if (!DecodeNextUint32(&encoded_size)) {
+    DVLOG(1) << "HpackInputStream::DecodeNextHuffmanString "
+             << "unable to decode size";
     return false;
   }
 
   if (encoded_size > buffer_.size()) {
+    DVLOG(1) << "HpackInputStream::DecodeNextHuffmanString " << encoded_size
+             << " > " << buffer_.size();
     return false;
   }
 
@@ -132,8 +140,10 @@ bool HpackInputStream::DecodeNextHuffmanString(const HpackHuffmanTable& table,
                                   StringPiece(buffer_.data(), encoded_size));
   buffer_.remove_prefix(encoded_size);
 
-  // HpackHuffmanTable will not decode beyond |max_string_literal_size_|.
-  return table.DecodeString(&bounded_reader, max_string_literal_size_, str);
+  // DecodeString will not append more than |max_string_literal_size_| chars
+  // to |str|.
+  return HpackHuffmanDecoder::DecodeString(&bounded_reader,
+                                           max_string_literal_size_, str);
 }
 
 bool HpackInputStream::PeekBits(size_t* peeked_count, uint32_t* out) const {
@@ -161,6 +171,41 @@ bool HpackInputStream::PeekBits(size_t* peeked_count, uint32_t* out) const {
   return true;
 }
 
+std::pair<size_t, uint32_t> HpackInputStream::InitializePeekBits() {
+  size_t peeked_count = 0;
+  uint32_t bits = 0;
+  if (bit_offset_ == 0) {
+    switch (buffer_.size()) {
+      default:
+        DCHECK_LE(4u, buffer_.size());
+        bits = static_cast<uint32_t>(static_cast<unsigned char>(buffer_[3]));
+        peeked_count += 8;
+      /* FALLTHROUGH */
+      case 3:
+        bits |= (static_cast<uint32_t>(static_cast<unsigned char>(buffer_[2]))
+                 << 8);
+        peeked_count += 8;
+      /* FALLTHROUGH */
+      case 2:
+        bits |= (static_cast<uint32_t>(static_cast<unsigned char>(buffer_[1]))
+                 << 16);
+        peeked_count += 8;
+      /* FALLTHROUGH */
+      case 1:
+        bits |= (static_cast<uint32_t>(static_cast<unsigned char>(buffer_[0]))
+                 << 24);
+        peeked_count += 8;
+        break;
+      case 0:
+        break;
+    }
+  } else {
+    LOG(DFATAL) << "InitializePeekBits called with non-zero bit_offset_: "
+                << bit_offset_;
+  }
+  return std::make_pair(peeked_count, bits);
+}
+
 void HpackInputStream::ConsumeBits(size_t bit_count) {
   size_t byte_count = (bit_offset_ + bit_count) / 8;
   bit_offset_ = (bit_offset_ + bit_count) % 8;
diff --git a/net/spdy/hpack/hpack_input_stream.h b/net/spdy/hpack/hpack_input_stream.h
index e7787f7..ab716d0 100644
--- a/net/spdy/hpack/hpack_input_stream.h
+++ b/net/spdy/hpack/hpack_input_stream.h
@@ -9,6 +9,7 @@
 #include <stdint.h>
 
 #include <string>
+#include <utility>
 
 #include "base/macros.h"
 #include "base/strings/string_piece.h"
@@ -21,6 +22,8 @@
 
 namespace net {
 
+typedef std::pair<size_t, uint32_t> InitialPeekResult;
+
 // An HpackInputStream handles all the low-level details of decoding
 // header fields.
 class NET_EXPORT_PRIVATE HpackInputStream {
@@ -42,16 +45,26 @@ class NET_EXPORT_PRIVATE HpackInputStream {
 
   bool DecodeNextUint32(uint32_t* I);
   bool DecodeNextIdentityString(base::StringPiece* str);
-  bool DecodeNextHuffmanString(const HpackHuffmanTable& table,
-                               std::string* str);
+  bool DecodeNextHuffmanString(std::string* str);
 
   // Stores input bits into the most-significant, unfilled bits of |out|.
   // |peeked_count| is the number of filled bits in |out| which have been
   // previously peeked. PeekBits() will fill some number of remaining bits,
   // returning the new total number via |peeked_count|. Returns true if one
-  // or more additional bits could be peeked, and false otherwise.
+  // or more additional bits were added to |out|, and false otherwise.
   bool PeekBits(size_t* peeked_count, uint32_t* out) const;
 
+  // Similar to PeekBits, but intended to be used when starting to decode a
+  // Huffman encoded string. Returns a pair containing the peeked_count and
+  // out values as described for PeekBits, with the bits from the first N bytes
+  // of buffer_, where N == min(4, buffer_.size()), starting with the high
+  // order bits.
+  // Should only be called when first peeking at bits from the input stream as
+  // it does not take peeked_count as an input, so doesn't know how many bits
+  // have already been returned by previous calls to InitializePeekBits and
+  // PeekBits.
+  InitialPeekResult InitializePeekBits();
+
   // Consumes |count| bits of input. Generally paired with PeekBits().
   void ConsumeBits(size_t count);
 
diff --git a/net/spdy/hpack/hpack_input_stream_test.cc b/net/spdy/hpack/hpack_input_stream_test.cc
index 6c4108f..1b68754 100644
--- a/net/spdy/hpack/hpack_input_stream_test.cc
+++ b/net/spdy/hpack/hpack_input_stream_test.cc
@@ -12,6 +12,7 @@
 #include "base/strings/string_piece.h"
 #include "net/spdy/hpack/hpack_constants.h"
 #include "net/spdy/spdy_test_utils.h"
+#include "net/test/gtest_util.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace net {
@@ -24,17 +25,6 @@ using test::a2b_hex;
 
 const size_t kLiteralBound = 1024;
 
-class HpackInputStreamTest : public ::testing::Test {
- public:
-  void SetUp() override {
-    std::vector<HpackHuffmanSymbol> code = HpackHuffmanCode();
-    EXPECT_TRUE(huffman_table_.Initialize(&code[0], code.size()));
-  }
-
- protected:
-  HpackHuffmanTable huffman_table_;
-};
-
 // Hex representation of encoded length and Huffman string.
 const char kEncodedHuffmanFixture[] =
     "2d"  // Length prefix.
@@ -76,7 +66,7 @@ uint32_t bits32(const string& bitstring) {
 // certain integers are decoded correctly with an 8-bit prefix in
 // exactly {Number} bytes.
 
-TEST_F(HpackInputStreamTest, OneByteIntegersEightBitPrefix) {
+TEST(HpackInputStreamTest, OneByteIntegersEightBitPrefix) {
   // Minimum.
   EXPECT_EQ(0x00u, DecodeValidUint32(8, string("\x00", 1)));
   EXPECT_EQ(0x7fu, DecodeValidUint32(8, "\x7f"));
@@ -86,7 +76,7 @@ TEST_F(HpackInputStreamTest, OneByteIntegersEightBitPrefix) {
   ExpectDecodeUint32Invalid(8, "\xff");
 }
 
-TEST_F(HpackInputStreamTest, TwoByteIntegersEightBitPrefix) {
+TEST(HpackInputStreamTest, TwoByteIntegersEightBitPrefix) {
   // Minimum.
   EXPECT_EQ(0xffu, DecodeValidUint32(8, string("\xff\x00", 2)));
   EXPECT_EQ(0x0100u, DecodeValidUint32(8, "\xff\x01"));
@@ -97,7 +87,7 @@ TEST_F(HpackInputStreamTest, TwoByteIntegersEightBitPrefix) {
   ExpectDecodeUint32Invalid(8, "\xff\xff");
 }
 
-TEST_F(HpackInputStreamTest, ThreeByteIntegersEightBitPrefix) {
+TEST(HpackInputStreamTest, ThreeByteIntegersEightBitPrefix) {
   // Minimum.
   EXPECT_EQ(0x017fu, DecodeValidUint32(8, "\xff\x80\x01"));
   EXPECT_EQ(0x0fffu, DecodeValidUint32(8, "\xff\x80\x1e"));
@@ -110,7 +100,7 @@ TEST_F(HpackInputStreamTest, ThreeByteIntegersEightBitPrefix) {
   ExpectDecodeUint32Invalid(8, "\xff\xff\xff");
 }
 
-TEST_F(HpackInputStreamTest, FourByteIntegersEightBitPrefix) {
+TEST(HpackInputStreamTest, FourByteIntegersEightBitPrefix) {
   // Minimum.
   EXPECT_EQ(0x40ffu, DecodeValidUint32(8, "\xff\x80\x80\x01"));
   EXPECT_EQ(0xffffu, DecodeValidUint32(8, "\xff\x80\xfe\x03"));
@@ -123,7 +113,7 @@ TEST_F(HpackInputStreamTest, FourByteIntegersEightBitPrefix) {
   ExpectDecodeUint32Invalid(8, "\xff\xff\xff\xff");
 }
 
-TEST_F(HpackInputStreamTest, FiveByteIntegersEightBitPrefix) {
+TEST(HpackInputStreamTest, FiveByteIntegersEightBitPrefix) {
   // Minimum.
   EXPECT_EQ(0x002000ffu, DecodeValidUint32(8, "\xff\x80\x80\x80\x01"));
   EXPECT_EQ(0x00ffffffu, DecodeValidUint32(8, "\xff\x80\xfe\xff\x07"));
@@ -136,7 +126,7 @@ TEST_F(HpackInputStreamTest, FiveByteIntegersEightBitPrefix) {
   ExpectDecodeUint32Invalid(8, "\xff\xff\xff\xff\xff");
 }
 
-TEST_F(HpackInputStreamTest, SixByteIntegersEightBitPrefix) {
+TEST(HpackInputStreamTest, SixByteIntegersEightBitPrefix) {
   // Minimum.
   EXPECT_EQ(0x100000ffu, DecodeValidUint32(8, "\xff\x80\x80\x80\x80\x01"));
   // Maximum.
@@ -149,7 +139,7 @@ TEST_F(HpackInputStreamTest, SixByteIntegersEightBitPrefix) {
 
 // There are no valid uint32_t encodings that are greater than six
 // bytes.
-TEST_F(HpackInputStreamTest, SevenByteIntegersEightBitPrefix) {
+TEST(HpackInputStreamTest, SevenByteIntegersEightBitPrefix) {
   ExpectDecodeUint32Invalid(8, "\xff\x80\x80\x80\x80\x80\x00");
   ExpectDecodeUint32Invalid(8, "\xff\x80\x80\x80\x80\x80\x01");
   ExpectDecodeUint32Invalid(8, "\xff\xff\xff\xff\xff\xff\xff");
@@ -159,7 +149,7 @@ TEST_F(HpackInputStreamTest, SevenByteIntegersEightBitPrefix) {
 // certain integers are encoded correctly with an N-bit prefix in
 // exactly {Number} bytes for N in {1, 2, ..., 7}.
 
-TEST_F(HpackInputStreamTest, OneByteIntegersOneToSevenBitPrefixes) {
+TEST(HpackInputStreamTest, OneByteIntegersOneToSevenBitPrefixes) {
   // Minimums.
   EXPECT_EQ(0x00u, DecodeValidUint32(7, string("\x00", 1)));
   EXPECT_EQ(0x00u, DecodeValidUint32(7, "\x80"));
@@ -209,7 +199,7 @@ TEST_F(HpackInputStreamTest, OneByteIntegersOneToSevenBitPrefixes) {
   ExpectDecodeUint32Invalid(1, "\xff");
 }
 
-TEST_F(HpackInputStreamTest, TwoByteIntegersOneToSevenBitPrefixes) {
+TEST(HpackInputStreamTest, TwoByteIntegersOneToSevenBitPrefixes) {
   // Minimums.
   EXPECT_EQ(0x7fu, DecodeValidUint32(7, string("\x7f\x00", 2)));
   EXPECT_EQ(0x7fu, DecodeValidUint32(7, string("\xff\x00", 2)));
@@ -259,7 +249,7 @@ TEST_F(HpackInputStreamTest, TwoByteIntegersOneToSevenBitPrefixes) {
   ExpectDecodeUint32Invalid(1, "\xff\xff");
 }
 
-TEST_F(HpackInputStreamTest, ThreeByteIntegersOneToSevenBitPrefixes) {
+TEST(HpackInputStreamTest, ThreeByteIntegersOneToSevenBitPrefixes) {
   // Minimums.
   EXPECT_EQ(0xffu, DecodeValidUint32(7, "\x7f\x80\x01"));
   EXPECT_EQ(0xffu, DecodeValidUint32(7, "\xff\x80\x01"));
@@ -309,7 +299,7 @@ TEST_F(HpackInputStreamTest, ThreeByteIntegersOneToSevenBitPrefixes) {
   ExpectDecodeUint32Invalid(1, "\xff\xff\xff");
 }
 
-TEST_F(HpackInputStreamTest, FourByteIntegersOneToSevenBitPrefixes) {
+TEST(HpackInputStreamTest, FourByteIntegersOneToSevenBitPrefixes) {
   // Minimums.
   EXPECT_EQ(0x407fu, DecodeValidUint32(7, "\x7f\x80\x80\x01"));
   EXPECT_EQ(0x407fu, DecodeValidUint32(7, "\xff\x80\x80\x01"));
@@ -359,7 +349,7 @@ TEST_F(HpackInputStreamTest, FourByteIntegersOneToSevenBitPrefixes) {
   ExpectDecodeUint32Invalid(1, "\xff\xff\xff\xff");
 }
 
-TEST_F(HpackInputStreamTest, FiveByteIntegersOneToSevenBitPrefixes) {
+TEST(HpackInputStreamTest, FiveByteIntegersOneToSevenBitPrefixes) {
   // Minimums.
   EXPECT_EQ(0x20007fu, DecodeValidUint32(7, "\x7f\x80\x80\x80\x01"));
   EXPECT_EQ(0x20007fu, DecodeValidUint32(7, "\xff\x80\x80\x80\x01"));
@@ -409,7 +399,7 @@ TEST_F(HpackInputStreamTest, FiveByteIntegersOneToSevenBitPrefixes) {
   ExpectDecodeUint32Invalid(1, "\xff\xff\xff\xff\xff");
 }
 
-TEST_F(HpackInputStreamTest, SixByteIntegersOneToSevenBitPrefixes) {
+TEST(HpackInputStreamTest, SixByteIntegersOneToSevenBitPrefixes) {
   // Minimums.
   EXPECT_EQ(0x1000007fu, DecodeValidUint32(7, "\x7f\x80\x80\x80\x80\x01"));
   EXPECT_EQ(0x1000007fu, DecodeValidUint32(7, "\xff\x80\x80\x80\x80\x01"));
@@ -461,7 +451,7 @@ TEST_F(HpackInputStreamTest, SixByteIntegersOneToSevenBitPrefixes) {
 
 // There are no valid uint32_t encodings that are greater than six
 // bytes.
-TEST_F(HpackInputStreamTest, SevenByteIntegersOneToSevenBitPrefixes) {
+TEST(HpackInputStreamTest, SevenByteIntegersOneToSevenBitPrefixes) {
   ExpectDecodeUint32Invalid(7, "\x7f\x80\x80\x80\x80\x80\x00");
   ExpectDecodeUint32Invalid(7, "\x7f\x80\x80\x80\x80\x80\x01");
   ExpectDecodeUint32Invalid(7, "\xff\xff\xff\xff\xff\xff\xff");
@@ -486,7 +476,7 @@ TEST_F(HpackInputStreamTest, SevenByteIntegersOneToSevenBitPrefixes) {
 }
 
 // Decoding a valid encoded string literal should work.
-TEST_F(HpackInputStreamTest, DecodeNextIdentityString) {
+TEST(HpackInputStreamTest, DecodeNextIdentityString) {
   HpackInputStream input_stream(kLiteralBound, "\x0estring literal");
 
   EXPECT_TRUE(input_stream.HasMoreData());
@@ -498,7 +488,7 @@ TEST_F(HpackInputStreamTest, DecodeNextIdentityString) {
 
 // Decoding an encoded string literal with size larger than
 // |max_string_literal_size_| should fail.
-TEST_F(HpackInputStreamTest, DecodeNextIdentityStringSizeLimit) {
+TEST(HpackInputStreamTest, DecodeNextIdentityStringSizeLimit) {
   HpackInputStream input_stream(13, "\x0estring literal");
 
   EXPECT_TRUE(input_stream.HasMoreData());
@@ -508,7 +498,7 @@ TEST_F(HpackInputStreamTest, DecodeNextIdentityStringSizeLimit) {
 
 // Decoding an encoded string literal with size larger than the
 // remainder of the buffer should fail.
-TEST_F(HpackInputStreamTest, DecodeNextIdentityStringNotEnoughInput) {
+TEST(HpackInputStreamTest, DecodeNextIdentityStringNotEnoughInput) {
   // Set the length to be one more than it should be.
   HpackInputStream input_stream(kLiteralBound, "\x0fstring literal");
 
@@ -517,37 +507,37 @@ TEST_F(HpackInputStreamTest, DecodeNextIdentityStringNotEnoughInput) {
   EXPECT_FALSE(input_stream.DecodeNextIdentityString(&string_piece));
 }
 
-TEST_F(HpackInputStreamTest, DecodeNextHuffmanString) {
+TEST(HpackInputStreamTest, DecodeNextHuffmanString) {
   string output, input(a2b_hex(kEncodedHuffmanFixture));
   HpackInputStream input_stream(arraysize(kDecodedHuffmanFixture) - 1, input);
 
   EXPECT_TRUE(input_stream.HasMoreData());
-  EXPECT_TRUE(input_stream.DecodeNextHuffmanString(huffman_table_, &output));
+  EXPECT_TRUE(input_stream.DecodeNextHuffmanString(&output));
   EXPECT_EQ(kDecodedHuffmanFixture, output);
   EXPECT_FALSE(input_stream.HasMoreData());
 }
 
-TEST_F(HpackInputStreamTest, DecodeNextHuffmanStringSizeLimit) {
+TEST(HpackInputStreamTest, DecodeNextHuffmanStringSizeLimit) {
   string output, input(a2b_hex(kEncodedHuffmanFixture));
   // Max string literal is one byte shorter than the decoded fixture.
   HpackInputStream input_stream(arraysize(kDecodedHuffmanFixture) - 2, input);
 
   // Decoded string overflows the max string literal.
   EXPECT_TRUE(input_stream.HasMoreData());
-  EXPECT_FALSE(input_stream.DecodeNextHuffmanString(huffman_table_, &output));
+  EXPECT_FALSE(input_stream.DecodeNextHuffmanString(&output));
 }
 
-TEST_F(HpackInputStreamTest, DecodeNextHuffmanStringNotEnoughInput) {
+TEST(HpackInputStreamTest, DecodeNextHuffmanStringNotEnoughInput) {
   string output, input(a2b_hex(kEncodedHuffmanFixture));
   input[0]++;  // Input prefix is one byte larger than available input.
   HpackInputStream input_stream(arraysize(kDecodedHuffmanFixture) - 1, input);
 
   // Not enough buffer for declared encoded length.
   EXPECT_TRUE(input_stream.HasMoreData());
-  EXPECT_FALSE(input_stream.DecodeNextHuffmanString(huffman_table_, &output));
+  EXPECT_FALSE(input_stream.DecodeNextHuffmanString(&output));
 }
 
-TEST_F(HpackInputStreamTest, PeekBitsAndConsume) {
+TEST(HpackInputStreamTest, PeekBitsAndConsume) {
   HpackInputStream input_stream(kLiteralBound, "\xad\xab\xad\xab\xad");
 
   uint32_t bits = 0;
@@ -609,7 +599,97 @@ TEST_F(HpackInputStreamTest, PeekBitsAndConsume) {
   EXPECT_FALSE(input_stream.HasMoreData());
 }
 
-TEST_F(HpackInputStreamTest, ConsumeByteRemainder) {
+TEST(HpackInputStreamTest, InitializePeekBits) {
+  {
+    // Empty input, peeked_count == 0 and bits == 0.
+    HpackInputStream input_stream(kLiteralBound, "");
+    auto peeked_count_and_bits = input_stream.InitializePeekBits();
+    size_t peeked_count = peeked_count_and_bits.first;
+    uint32_t bits = peeked_count_and_bits.second;
+    EXPECT_EQ(0u, peeked_count);
+    EXPECT_EQ(0u, bits);
+  }
+  {
+    // One input byte, returns peeked_count == 8 and bits
+    // has the input byte in its high order bits.
+    HpackInputStream input_stream(kLiteralBound, "\xfe");
+    auto peeked_count_and_bits = input_stream.InitializePeekBits();
+    size_t peeked_count = peeked_count_and_bits.first;
+    uint32_t bits = peeked_count_and_bits.second;
+    EXPECT_EQ(8u, peeked_count);
+    EXPECT_EQ(0xfe000000, bits);
+    input_stream.ConsumeBits(8);
+    EXPECT_FALSE(input_stream.HasMoreData());
+  }
+  {
+    // Two input bytes, returns peeked_count == 16 and bits
+    // has the two input bytes in its high order bits.
+    HpackInputStream input_stream(kLiteralBound, "\xfe\xdc");
+    auto peeked_count_and_bits = input_stream.InitializePeekBits();
+    size_t peeked_count = peeked_count_and_bits.first;
+    uint32_t bits = peeked_count_and_bits.second;
+    EXPECT_EQ(16u, peeked_count);
+    EXPECT_EQ(0xfedc0000, bits);
+    input_stream.ConsumeBits(16);
+    EXPECT_FALSE(input_stream.HasMoreData());
+  }
+  {
+    // Three input bytes, returns peeked_count == 24 and bits
+    // has the three input bytes in its high order bits.
+    HpackInputStream input_stream(kLiteralBound, "\xab\xcd\xef");
+    auto peeked_count_and_bits = input_stream.InitializePeekBits();
+    size_t peeked_count = peeked_count_and_bits.first;
+    uint32_t bits = peeked_count_and_bits.second;
+    EXPECT_EQ(24u, peeked_count);
+    EXPECT_EQ(0xabcdef00, bits);
+    input_stream.ConsumeBits(24);
+    EXPECT_FALSE(input_stream.HasMoreData());
+  }
+  {
+    // Four input bytes, returns peeked_count == 32 and bits
+    // contains the four input bytes.
+    HpackInputStream input_stream(kLiteralBound, "\xfe\xed\xdc\xcb");
+    auto peeked_count_and_bits = input_stream.InitializePeekBits();
+    size_t peeked_count = peeked_count_and_bits.first;
+    uint32_t bits = peeked_count_and_bits.second;
+    EXPECT_EQ(32u, peeked_count);
+    EXPECT_EQ(0xfeeddccb, bits);
+    input_stream.ConsumeBits(32);
+    EXPECT_FALSE(input_stream.HasMoreData());
+  }
+  {
+    // Five input bytes, returns peeked_count == 32 and bits
+    // contains the first four input bytes.
+    HpackInputStream input_stream(kLiteralBound, "\xfe\xed\xdc\xcb\xba");
+    auto peeked_count_and_bits = input_stream.InitializePeekBits();
+    size_t peeked_count = peeked_count_and_bits.first;
+    uint32_t bits = peeked_count_and_bits.second;
+    EXPECT_EQ(32u, peeked_count);
+    EXPECT_EQ(0xfeeddccb, bits);
+    EXPECT_TRUE(input_stream.HasMoreData());
+
+    // If we consume some bits, then InitializePeekBits will return no bits.
+    input_stream.ConsumeBits(28);
+    peeked_count -= 28;
+    bits <<= 28;
+    EXPECT_EQ(0xb0000000, bits);
+
+    EXPECT_DFATAL(peeked_count_and_bits = input_stream.InitializePeekBits(),
+                  "bit_offset_");
+    EXPECT_EQ(0u, peeked_count_and_bits.first);
+    EXPECT_EQ(0u, peeked_count_and_bits.second);
+    EXPECT_TRUE(input_stream.HasMoreData());
+
+    // Can PeekBits, which will get us the last byte's bits.
+    EXPECT_TRUE(input_stream.PeekBits(&peeked_count, &bits));
+    EXPECT_EQ(12u, peeked_count);
+    EXPECT_EQ(0xbba00000, bits);
+    input_stream.ConsumeBits(12);
+    EXPECT_FALSE(input_stream.HasMoreData());
+  }
+}
+
+TEST(HpackInputStreamTest, ConsumeByteRemainder) {
   HpackInputStream input_stream(kLiteralBound, "\xad\xab");
   // Does nothing.
   input_stream.ConsumeByteRemainder();
diff --git a/net/spdy/hpack/hpack_round_trip_test.cc b/net/spdy/hpack/hpack_round_trip_test.cc
index 1b34638..07ab699 100644
--- a/net/spdy/hpack/hpack_round_trip_test.cc
+++ b/net/spdy/hpack/hpack_round_trip_test.cc
@@ -26,9 +26,7 @@ namespace {
 
 class HpackRoundTripTest : public ::testing::Test {
  protected:
-  HpackRoundTripTest()
-      : encoder_(ObtainHpackHuffmanTable()),
-        decoder_(ObtainHpackHuffmanTable()) {}
+  HpackRoundTripTest() : encoder_(ObtainHpackHuffmanTable()), decoder_() {}
 
   void SetUp() override {
     // Use a small table size to tickle eviction handling.
diff --git a/net/spdy/spdy_framer.cc b/net/spdy/spdy_framer.cc
index 2a2fb4d..6568b28 100644
--- a/net/spdy/spdy_framer.cc
+++ b/net/spdy/spdy_framer.cc
@@ -2961,7 +2961,7 @@ HpackEncoder* SpdyFramer::GetHpackEncoder() {
 HpackDecoder* SpdyFramer::GetHpackDecoder() {
   DCHECK_LT(SPDY3, protocol_version());
   if (hpack_decoder_.get() == nullptr) {
-    hpack_decoder_.reset(new HpackDecoder(ObtainHpackHuffmanTable()));
+    hpack_decoder_.reset(new HpackDecoder());
   }
   return hpack_decoder_.get();
 }