net/spdy/hpack_huffman_table.h

   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 #ifndef NET_SPDY_HPACK_HUFFMAN_TABLE_H_
   6 #define NET_SPDY_HPACK_HUFFMAN_TABLE_H_
   7
   8 #include <cstddef>
   9 #include <string>
  10 #include <vector>
  11
  12 #include "base/basictypes.h"
  13 #include "base/strings/string_piece.h"
  14 #include "net/base/net_export.h"
  15 #include "net/spdy/hpack_constants.h"
  16
  17 namespace net {
  18
  19 namespace test {
  20 class HpackHuffmanTablePeer;
  21 }  // namespace test
  22
  23 class HpackInputStream;
  24 class HpackOutputStream;
  25
  26 // HpackHuffmanTable encodes and decodes string literals using a constructed
  27 // canonical Huffman code. Once initialized, an instance is read only and
  28 // may be accessed only through its const interface.
  29 class NET_EXPORT_PRIVATE HpackHuffmanTable {
  30  public:
  31   friend class test::HpackHuffmanTablePeer;
  32
  33   typedef HpackHuffmanSymbol Symbol;
  34
  35   // DecodeTables are multilevel indexes on code prefixes. Each table indexes
  36   // a portion of the prefix mapped to DecodeEntry, which in turn either
  37   // captures a terminal symbol, or points to the next DecodeTable to consult
  38   // with successive portions of the prefix.
  39   struct NET_EXPORT_PRIVATE DecodeEntry {
  40     DecodeEntry();
  41     DecodeEntry(uint8 next_table_index, uint8 length, uint16 symbol_id);
  42
  43     // The next table to consult. If this is a terminal,
  44     // |next_table_index| will be self-referential.
  45     uint8 next_table_index;
  46     // Bit-length of terminal code, if this is a terminal. Length of the
  47     // longest code having this prefix, if non-terminal.
  48     uint8 length;
  49     // Set only for terminal entries.
  50     uint16 symbol_id;
  51   };
  52   struct NET_EXPORT_PRIVATE DecodeTable {
  53     // Number of bits indexed by the chain leading to this table.
  54     uint8 prefix_length;
  55     // Number of additional prefix bits this table indexes.
  56     uint8 indexed_length;
  57     // Entries are represented as a length |size()| slice into
  58     // |decode_entries_| beginning at |entries_offset|.
  59     size_t entries_offset;
  60     // Returns |1 << indexed_length|.
  61     size_t size() const;
  62   };
  63
  64   HpackHuffmanTable();
  65   ~HpackHuffmanTable();
  66
  67   // Prepares HpackHuffmanTable to encode & decode the canonical Huffman
  68   // code as determined by the given symbols. Must be called exactly once.
  69   // Returns false if the input symbols define an invalid coding, and true
  70   // otherwise. Symbols must be presented in ascending ID order with no gaps.
  71   bool Initialize(const Symbol* input_symbols, size_t symbol_count);
  72
  73   // Returns whether Initialize() has been successfully called.
  74   bool IsInitialized() const;
  75
  76   // Encodes the input string to the output stream using the table's Huffman
  77   // context.
  78   void EncodeString(base::StringPiece in, HpackOutputStream* out) const;
  79
  80   // Returns the encoded size of the input string.
  81   size_t EncodedSize(base::StringPiece in) const;
  82
  83   // Decodes symbols from |in| into |out|. It is the caller's responsibility
  84   // to ensure |out| has a reserved a sufficient buffer to hold decoded output.
  85   // DecodeString() halts when |in| runs out of input, in which case true is
  86   // returned. It also halts (returning false) if an invalid Huffman code
  87   // prefix is read, or if |out_capacity| would otherwise be overflowed.
  88   bool DecodeString(HpackInputStream* in,
  89                     size_t out_capacity,
  90                     std::string* out) const;
  91
  92  private:
  93   // Expects symbols ordered on length & ID ascending.
  94   void BuildDecodeTables(const std::vector<Symbol>& symbols);
  95
  96   // Expects symbols ordered on ID ascending.
  97   void BuildEncodeTable(const std::vector<Symbol>& symbols);
  98
  99   // Adds a new DecodeTable with the argument prefix & indexed length.
 100   // Returns the new table index.
 101   uint8 AddDecodeTable(uint8 prefix, uint8 indexed);
 102
 103   const DecodeEntry& Entry(const DecodeTable& table, uint32 index) const;
 104
 105   void SetEntry(const DecodeTable& table, uint32 index,
 106                 const DecodeEntry& entry);
 107
 108   std::vector<DecodeTable> decode_tables_;
 109   std::vector<DecodeEntry> decode_entries_;
 110
 111   // Symbol code and code length, in ascending symbol ID order.
 112   // Codes are stored in the most-significant bits of the word.
 113   std::vector<uint32> code_by_id_;
 114   std::vector<uint8> length_by_id_;
 115
 116   // The first 8 bits of the longest code. Applied when generating padding bits.
 117   uint8 pad_bits_;
 118
 119   // If initialization fails, preserve the symbol ID which failed validation
 120   // for examination in tests.
 121   uint16 failed_symbol_id_;
 122 };
 123
 124 }  // namespace net
 125
 126 #endif  // NET_SPDY_HPACK_HUFFMAN_TABLE_H_