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#include "net/spdy/hpack_encoder.h"
6
7#include <algorithm>
8
9#include "base/logging.h"
10#include "net/spdy/hpack_header_table.h"
11#include "net/spdy/hpack_huffman_table.h"
12#include "net/spdy/hpack_output_stream.h"
13
14namespace net {
15
16using base::StringPiece;
17using std::string;
18
19HpackEncoder::HpackEncoder(const HpackHuffmanTable& table)
20    : output_stream_(),
21      allow_huffman_compression_(true),
22      huffman_table_(table),
23      char_counts_(NULL),
24      total_char_counts_(NULL) {}
25
26HpackEncoder::~HpackEncoder() {}
27
28bool HpackEncoder::EncodeHeaderSet(const std::map<string, string>& header_set,
29                                   string* output) {
30  // Separate header set into pseudo-headers and regular headers.
31  Representations pseudo_headers;
32  Representations regular_headers;
33  for (std::map<string, string>::const_iterator it = header_set.begin();
34       it != header_set.end(); ++it) {
35    if (it->first == "cookie") {
36      // Note that there can only be one "cookie" header, because header_set is
37      // a map.
38      CookieToCrumbs(*it, &regular_headers);
39    } else if (it->first[0] == kPseudoHeaderPrefix) {
40      DecomposeRepresentation(*it, &pseudo_headers);
41    } else {
42      DecomposeRepresentation(*it, &regular_headers);
43    }
44  }
45
46  // Encode pseudo-headers.
47  for (Representations::const_iterator it = pseudo_headers.begin();
48       it != pseudo_headers.end(); ++it) {
49    const HpackEntry* entry =
50        header_table_.GetByNameAndValue(it->first, it->second);
51    if (entry != NULL) {
52      EmitIndex(entry);
53    } else {
54      if (it->first == ":authority") {
55        // :authority is always present and rarely changes, and has moderate
56        // length, therefore it makes a lot of sense to index (insert in the
57        // header table).
58        EmitIndexedLiteral(*it);
59      } else {
60        // Most common pseudo-header fields are represented in the static table,
61        // while uncommon ones are small, so do not index them.
62        EmitNonIndexedLiteral(*it);
63      }
64    }
65  }
66
67  // Encode regular headers that are already in the header table first,
68  // save the rest into another vector.  This way we avoid evicting an entry
69  // from the header table before it can be used.
70  Representations literal_headers;
71  for (Representations::const_iterator it = regular_headers.begin();
72       it != regular_headers.end(); ++it) {
73    const HpackEntry* entry =
74        header_table_.GetByNameAndValue(it->first, it->second);
75    if (entry != NULL) {
76      EmitIndex(entry);
77    } else {
78      literal_headers.push_back(*it);
79    }
80  }
81
82  // Encode the remaining header fields, while inserting them in the header
83  // table.
84  for (Representations::const_iterator it = literal_headers.begin();
85       it != literal_headers.end(); ++it) {
86    EmitIndexedLiteral(*it);
87  }
88
89  output_stream_.TakeString(output);
90  return true;
91}
92
93bool HpackEncoder::EncodeHeaderSetWithoutCompression(
94    const std::map<string, string>& header_set,
95    string* output) {
96
97  allow_huffman_compression_ = false;
98  for (std::map<string, string>::const_iterator it = header_set.begin();
99       it != header_set.end(); ++it) {
100    // Note that cookies are not crumbled in this case.
101    EmitNonIndexedLiteral(*it);
102  }
103  allow_huffman_compression_ = true;
104  output_stream_.TakeString(output);
105  return true;
106}
107
108void HpackEncoder::EmitIndex(const HpackEntry* entry) {
109  output_stream_.AppendPrefix(kIndexedOpcode);
110  output_stream_.AppendUint32(header_table_.IndexOf(entry));
111}
112
113void HpackEncoder::EmitIndexedLiteral(const Representation& representation) {
114  output_stream_.AppendPrefix(kLiteralIncrementalIndexOpcode);
115  EmitLiteral(representation);
116  header_table_.TryAddEntry(representation.first, representation.second);
117}
118
119void HpackEncoder::EmitNonIndexedLiteral(
120    const Representation& representation) {
121  output_stream_.AppendPrefix(kLiteralNoIndexOpcode);
122  output_stream_.AppendUint32(0);
123  EmitString(representation.first);
124  EmitString(representation.second);
125}
126
127void HpackEncoder::EmitLiteral(const Representation& representation) {
128  const HpackEntry* name_entry = header_table_.GetByName(representation.first);
129  if (name_entry != NULL) {
130    output_stream_.AppendUint32(header_table_.IndexOf(name_entry));
131  } else {
132    output_stream_.AppendUint32(0);
133    EmitString(representation.first);
134  }
135  EmitString(representation.second);
136}
137
138void HpackEncoder::EmitString(StringPiece str) {
139  size_t encoded_size = (!allow_huffman_compression_ ? str.size()
140                         : huffman_table_.EncodedSize(str));
141  if (encoded_size < str.size()) {
142    output_stream_.AppendPrefix(kStringLiteralHuffmanEncoded);
143    output_stream_.AppendUint32(encoded_size);
144    huffman_table_.EncodeString(str, &output_stream_);
145  } else {
146    output_stream_.AppendPrefix(kStringLiteralIdentityEncoded);
147    output_stream_.AppendUint32(str.size());
148    output_stream_.AppendBytes(str);
149  }
150  UpdateCharacterCounts(str);
151}
152
153void HpackEncoder::SetCharCountsStorage(std::vector<size_t>* char_counts,
154                                        size_t* total_char_counts) {
155  CHECK_LE(256u, char_counts->size());
156  char_counts_ = char_counts;
157  total_char_counts_ = total_char_counts;
158}
159
160void HpackEncoder::UpdateCharacterCounts(base::StringPiece str) {
161  if (char_counts_ == NULL || total_char_counts_ == NULL) {
162    return;
163  }
164  for (StringPiece::const_iterator it = str.begin(); it != str.end(); ++it) {
165    ++(*char_counts_)[static_cast<uint8>(*it)];
166  }
167  (*total_char_counts_) += str.size();
168}
169
170// static
171void HpackEncoder::CookieToCrumbs(const Representation& cookie,
172                                  Representations* out) {
173  size_t prior_size = out->size();
174
175  // See Section 8.1.2.5. "Compressing the Cookie Header Field" in the HTTP/2
176  // specification at https://tools.ietf.org/html/draft-ietf-httpbis-http2-14.
177  // Cookie values are split into individually-encoded HPACK representations.
178  for (size_t pos = 0;;) {
179    size_t end = cookie.second.find(";", pos);
180
181    if (end == StringPiece::npos) {
182      out->push_back(make_pair(
183          cookie.first,
184          cookie.second.substr(pos)));
185      break;
186    }
187    out->push_back(make_pair(
188        cookie.first,
189        cookie.second.substr(pos, end - pos)));
190
191    // Consume next space if present.
192    pos = end + 1;
193    if (pos != cookie.second.size() && cookie.second[pos] == ' ') {
194      pos++;
195    }
196  }
197  // Sort crumbs and remove duplicates.
198  std::sort(out->begin() + prior_size, out->end());
199  out->erase(std::unique(out->begin() + prior_size, out->end()),
200             out->end());
201}
202
203// static
204void HpackEncoder::DecomposeRepresentation(const Representation& header_field,
205                                           Representations* out) {
206  size_t pos = 0;
207  size_t end = 0;
208  while (end != StringPiece::npos) {
209    end = header_field.second.find('\0', pos);
210    out->push_back(make_pair(header_field.first,
211                             header_field.second.substr(pos, end - pos)));
212    pos = end + 1;
213  }
214}
215
216}  // namespace net
217