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