| // Copyright 2014 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #ifndef NET_SPDY_HPACK_HUFFMAN_TABLE_H_ |
| #define NET_SPDY_HPACK_HUFFMAN_TABLE_H_ |
| |
| #include <stdint.h> |
| |
| #include <cstddef> |
| #include <string> |
| #include <vector> |
| |
| #include "base/strings/string_piece.h" |
| #include "net/base/net_export.h" |
| #include "net/spdy/hpack/hpack_constants.h" |
| |
| namespace net { |
| |
| namespace test { |
| class HpackHuffmanTablePeer; |
| } // namespace test |
| |
| class HpackInputStream; |
| class HpackOutputStream; |
| |
| // HpackHuffmanTable encodes and decodes string literals using a constructed |
| // canonical Huffman code. Once initialized, an instance is read only and |
| // may be accessed only through its const interface. |
| class NET_EXPORT_PRIVATE HpackHuffmanTable { |
| public: |
| friend class test::HpackHuffmanTablePeer; |
| |
| typedef HpackHuffmanSymbol Symbol; |
| |
| // DecodeTables are multilevel indexes on code prefixes. Each table indexes |
| // a portion of the prefix mapped to DecodeEntry, which in turn either |
| // captures a terminal symbol, or points to the next DecodeTable to consult |
| // with successive portions of the prefix. |
| struct NET_EXPORT_PRIVATE DecodeEntry { |
| DecodeEntry(); |
| DecodeEntry(uint8_t next_table_index, uint8_t length, uint16_t symbol_id); |
| |
| // The next table to consult. If this is a terminal, |
| // |next_table_index| will be self-referential. |
| uint8_t next_table_index; |
| // Bit-length of terminal code, if this is a terminal. Length of the |
| // longest code having this prefix, if non-terminal. |
| uint8_t length; |
| // Set only for terminal entries. |
| uint16_t symbol_id; |
| }; |
| struct NET_EXPORT_PRIVATE DecodeTable { |
| // Number of bits indexed by the chain leading to this table. |
| uint8_t prefix_length; |
| // Number of additional prefix bits this table indexes. |
| uint8_t indexed_length; |
| // Entries are represented as a length |size()| slice into |
| // |decode_entries_| beginning at |entries_offset|. |
| size_t entries_offset; |
| // Returns |1 << indexed_length|. |
| size_t size() const; |
| }; |
| |
| HpackHuffmanTable(); |
| ~HpackHuffmanTable(); |
| |
| // Prepares HpackHuffmanTable to encode & decode the canonical Huffman |
| // code as determined by the given symbols. Must be called exactly once. |
| // Returns false if the input symbols define an invalid coding, and true |
| // otherwise. Symbols must be presented in ascending ID order with no gaps, |
| // and |symbol_count| must fit in a uint16_t. |
| bool Initialize(const Symbol* input_symbols, size_t symbol_count); |
| |
| // Returns whether Initialize() has been successfully called. |
| bool IsInitialized() const; |
| |
| // Encodes the input string to the output stream using the table's Huffman |
| // context. |
| void EncodeString(base::StringPiece in, HpackOutputStream* out) const; |
| |
| // Returns the encoded size of the input string. |
| size_t EncodedSize(base::StringPiece in) const; |
| |
| // Decodes symbols from |in| into |out|, using the support for generic (any) |
| // huffman tables, not just those defined in the HPACK spec. It is the |
| // caller's responsibility to ensure |out| has reserved a sufficient buffer to |
| // hold decoded output. GenericDecodeString() halts when |in| runs out of |
| // input, in which case true is returned. It also halts (returning false) if |
| // an invalid Huffman code prefix is read, or if |out_capacity| would |
| // otherwise be overflowed. |
| // DEPRECATED: HpackHuffmanDecoder is now used for decoding strings encoded |
| // according to the Huffman Table in the HPACK spec. |
| bool GenericDecodeString(HpackInputStream* in, |
| std::string* out) const; |
| |
| private: |
| // Expects symbols ordered on length & ID ascending. |
| void BuildDecodeTables(const std::vector<Symbol>& symbols); |
| |
| // Expects symbols ordered on ID ascending. |
| void BuildEncodeTable(const std::vector<Symbol>& symbols); |
| |
| // Adds a new DecodeTable with the argument prefix & indexed length. |
| // Returns the new table index. |
| uint8_t AddDecodeTable(uint8_t prefix, uint8_t indexed); |
| |
| const DecodeEntry& Entry(const DecodeTable& table, uint32_t index) const; |
| |
| void SetEntry(const DecodeTable& table, |
| uint32_t index, |
| const DecodeEntry& entry); |
| |
| std::vector<DecodeTable> decode_tables_; |
| std::vector<DecodeEntry> decode_entries_; |
| |
| // Symbol code and code length, in ascending symbol ID order. |
| // Codes are stored in the most-significant bits of the word. |
| std::vector<uint32_t> code_by_id_; |
| std::vector<uint8_t> length_by_id_; |
| |
| // The first 8 bits of the longest code. Applied when generating padding bits. |
| uint8_t pad_bits_; |
| |
| // If initialization fails, preserve the symbol ID which failed validation |
| // for examination in tests. |
| uint16_t failed_symbol_id_; |
| }; |
| |
| } // namespace net |
| |
| #endif // NET_SPDY_HPACK_HUFFMAN_TABLE_H_ |