| 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 |