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