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.
5 #ifndef NET_SPDY_HPACK_HUFFMAN_TABLE_H_
6 #define NET_SPDY_HPACK_HUFFMAN_TABLE_H_
12 #include "base/basictypes.h"
13 #include "base/strings/string_piece.h"
14 #include "net/base/net_export.h"
15 #include "net/spdy/hpack_constants.h"
20 class HpackHuffmanTablePeer
;
23 class HpackInputStream
;
24 class HpackOutputStream
;
26 // HpackHuffmanTable encodes and decodes string literals using a constructed
27 // canonical Huffman code. Once initialized, an instance is read only and
28 // may be accessed only through its const interface.
29 class NET_EXPORT_PRIVATE HpackHuffmanTable
{
31 friend class test::HpackHuffmanTablePeer
;
33 typedef HpackHuffmanSymbol Symbol
;
35 // DecodeTables are multilevel indexes on code prefixes. Each table indexes
36 // 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 // with successive portions of the prefix.
39 struct NET_EXPORT_PRIVATE DecodeEntry
{
41 DecodeEntry(uint8 next_table_index
, uint8 length
, uint16 symbol_id
);
43 // The next table to consult. If this is a terminal,
44 // |next_table_index| will be self-referential.
45 uint8 next_table_index
;
46 // Bit-length of terminal code, if this is a terminal. Length of the
47 // longest code having this prefix, if non-terminal.
49 // Set only for terminal entries.
52 struct NET_EXPORT_PRIVATE DecodeTable
{
53 // Number of bits indexed by the chain leading to this table.
55 // Number of additional prefix bits this table indexes.
57 // Entries are represented as a length |size()| slice into
58 // |decode_entries_| beginning at |entries_offset|.
59 size_t entries_offset
;
60 // Returns |1 << indexed_length|.
67 // Prepares HpackHuffmanTable to encode & decode the canonical Huffman
68 // 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 // otherwise. Symbols must be presented in ascending ID order with no gaps.
71 bool Initialize(const Symbol
* input_symbols
, size_t symbol_count
);
73 // Returns whether Initialize() has been successfully called.
74 bool IsInitialized() const;
76 // Encodes the input string to the output stream using the table's Huffman
78 void EncodeString(base::StringPiece in
, HpackOutputStream
* out
) const;
80 // Returns the encoded size of the input string.
81 size_t EncodedSize(base::StringPiece in
) const;
83 // Decodes symbols from |in| into |out|. It is the caller's responsibility
84 // to ensure |out| has a reserved a sufficient buffer to hold decoded output.
85 // DecodeString() halts when |in| runs out of input, in which case true is
86 // returned. It also halts (returning false) if an invalid Huffman code
87 // prefix is read, or if |out_capacity| would otherwise be overflowed.
88 bool DecodeString(HpackInputStream
* in
,
90 std::string
* out
) const;
93 // Expects symbols ordered on length & ID ascending.
94 void BuildDecodeTables(const std::vector
<Symbol
>& symbols
);
96 // Expects symbols ordered on ID ascending.
97 void BuildEncodeTable(const std::vector
<Symbol
>& symbols
);
99 // Adds a new DecodeTable with the argument prefix & indexed length.
100 // Returns the new table index.
101 uint8
AddDecodeTable(uint8 prefix
, uint8 indexed
);
103 const DecodeEntry
& Entry(const DecodeTable
& table
, uint32 index
) const;
105 void SetEntry(const DecodeTable
& table
, uint32 index
,
106 const DecodeEntry
& entry
);
108 std::vector
<DecodeTable
> decode_tables_
;
109 std::vector
<DecodeEntry
> decode_entries_
;
111 // Symbol code and code length, in ascending symbol ID order.
112 // Codes are stored in the most-significant bits of the word.
113 std::vector
<uint32
> code_by_id_
;
114 std::vector
<uint8
> length_by_id_
;
116 // The first 8 bits of the longest code. Applied when generating padding bits.
119 // If initialization fails, preserve the symbol ID which failed validation
120 // for examination in tests.
121 uint16 failed_symbol_id_
;
126 #endif // NET_SPDY_HPACK_HUFFMAN_TABLE_H_