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