Home | History | Annotate | Download | only in spdy 
      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_
    127