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