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.
4
5#ifndef NET_SPDY_HPACK_HUFFMAN_TABLE_H_
6#define NET_SPDY_HPACK_HUFFMAN_TABLE_H_
7
8#include <cstddef>
9#include <string>
10#include <vector>
11
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"
16
17namespace net {
18
19namespace test {
20class HpackHuffmanTablePeer;
21}  // namespace test
22
23class HpackInputStream;
24class HpackOutputStream;
25
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.
29class NET_EXPORT_PRIVATE HpackHuffmanTable {
30 public:
31  friend class test::HpackHuffmanTablePeer;
32
33  typedef HpackHuffmanSymbol Symbol;
34
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 {
40    DecodeEntry();
41    DecodeEntry(uint8 next_table_index, uint8 length, uint16 symbol_id);
42
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.
48    uint8 length;
49    // Set only for terminal entries.
50    uint16 symbol_id;
51  };
52  struct NET_EXPORT_PRIVATE DecodeTable {
53    // Number of bits indexed by the chain leading to this table.
54    uint8 prefix_length;
55    // Number of additional prefix bits this table indexes.
56    uint8 indexed_length;
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|.
61    size_t size() const;
62  };
63
64  HpackHuffmanTable();
65  ~HpackHuffmanTable();
66
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);
72
73  // Returns whether Initialize() has been successfully called.
74  bool IsInitialized() const;
75
76  // Encodes the input string to the output stream using the table's Huffman
77  // context.
78  void EncodeString(base::StringPiece in, HpackOutputStream* out) const;
79
80  // Returns the encoded size of the input string.
81  size_t EncodedSize(base::StringPiece in) const;
82
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,
89                    size_t out_capacity,
90                    std::string* out) const;
91
92 private:
93  // Expects symbols ordered on length & ID ascending.
94  void BuildDecodeTables(const std::vector<Symbol>& symbols);
95
96  // Expects symbols ordered on ID ascending.
97  void BuildEncodeTable(const std::vector<Symbol>& symbols);
98
99  // Adds a new DecodeTable with the argument prefix & indexed length.
100  // Returns the new table index.
101  uint8 AddDecodeTable(uint8 prefix, uint8 indexed);
102
103  const DecodeEntry& Entry(const DecodeTable& table, uint32 index) const;
104
105  void SetEntry(const DecodeTable& table, uint32 index,
106                const DecodeEntry& entry);
107
108  std::vector<DecodeTable> decode_tables_;
109  std::vector<DecodeEntry> decode_entries_;
110
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_;
115
116  // The first 8 bits of the longest code. Applied when generating padding bits.
117  uint8 pad_bits_;
118
119  // If initialization fails, preserve the symbol ID which failed validation
120  // for examination in tests.
121  uint16 failed_symbol_id_;
122};
123
124}  // namespace net
125
126#endif  // NET_SPDY_HPACK_HUFFMAN_TABLE_H_
127