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   // and |symbol_count| must fit in a uint16.
  72   bool Initialize(const Symbol* input_symbols, size_t symbol_count);
  73
  74   // Returns whether Initialize() has been successfully called.
  75   bool IsInitialized() const;
  76
  77   // Encodes the input string to the output stream using the table's Huffman
  78   // context.
  79   void EncodeString(base::StringPiece in, HpackOutputStream* out) const;
  80
  81   // Returns the encoded size of the input string.
  82   size_t EncodedSize(base::StringPiece in) const;
  83
  84   // Decodes symbols from |in| into |out|. It is the caller's responsibility
  85   // to ensure |out| has a reserved a sufficient buffer to hold decoded output.
  86   // DecodeString() halts when |in| runs out of input, in which case true is
  87   // returned. It also halts (returning false) if an invalid Huffman code
  88   // prefix is read, or if |out_capacity| would otherwise be overflowed.
  89   bool DecodeString(HpackInputStream* in,
  90                     size_t out_capacity,
  91                     std::string* out) const;
  92
  93  private:
  94   // Expects symbols ordered on length & ID ascending.
  95   void BuildDecodeTables(const std::vector<Symbol>& symbols);
  96
  97   // Expects symbols ordered on ID ascending.
  98   void BuildEncodeTable(const std::vector<Symbol>& symbols);
  99
 100   // Adds a new DecodeTable with the argument prefix & indexed length.
 101   // Returns the new table index.
 102   uint8 AddDecodeTable(uint8 prefix, uint8 indexed);
 103
 104   const DecodeEntry& Entry(const DecodeTable& table, uint32 index) const;
 105
 106   void SetEntry(const DecodeTable& table, uint32 index,
 107                 const DecodeEntry& entry);
 108
 109   std::vector<DecodeTable> decode_tables_;
 110   std::vector<DecodeEntry> decode_entries_;
 111
 112   // Symbol code and code length, in ascending symbol ID order.
 113   // Codes are stored in the most-significant bits of the word.
 114   std::vector<uint32> code_by_id_;
 115   std::vector<uint8> length_by_id_;
 116
 117   // The first 8 bits of the longest code. Applied when generating padding bits.
 118   uint8 pad_bits_;
 119
 120   // If initialization fails, preserve the symbol ID which failed validation
 121   // for examination in tests.
 122   uint16 failed_symbol_id_;
 123 };
 124
 125 }  // namespace net
 126
 127 #endif  // NET_SPDY_HPACK_HUFFMAN_TABLE_H_