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 "quiche/spdy/core/hpack/hpack_encoder.h"
6
7 #include <algorithm>
8 #include <cstddef>
9 #include <limits>
10 #include <memory>
11 #include <string>
12 #include <utility>
13
14 #include "absl/strings/string_view.h"
15 #include "quiche/http2/hpack/huffman/hpack_huffman_encoder.h"
16 #include "quiche/common/platform/api/quiche_bug_tracker.h"
17 #include "quiche/common/platform/api/quiche_logging.h"
18 #include "quiche/spdy/core/hpack/hpack_constants.h"
19 #include "quiche/spdy/core/hpack/hpack_header_table.h"
20 #include "quiche/spdy/core/hpack/hpack_output_stream.h"
21 #include "quiche/spdy/core/http2_header_block.h"
22
23 namespace spdy {
24
25 class HpackEncoder::RepresentationIterator {
26 public:
27 // |pseudo_headers| and |regular_headers| must outlive the iterator.
RepresentationIterator(const Representations & pseudo_headers,const Representations & regular_headers)28 RepresentationIterator(const Representations& pseudo_headers,
29 const Representations& regular_headers)
30 : pseudo_begin_(pseudo_headers.begin()),
31 pseudo_end_(pseudo_headers.end()),
32 regular_begin_(regular_headers.begin()),
33 regular_end_(regular_headers.end()) {}
34
35 // |headers| must outlive the iterator.
RepresentationIterator(const Representations & headers)36 explicit RepresentationIterator(const Representations& headers)
37 : pseudo_begin_(headers.begin()),
38 pseudo_end_(headers.end()),
39 regular_begin_(headers.end()),
40 regular_end_(headers.end()) {}
41
HasNext()42 bool HasNext() {
43 return pseudo_begin_ != pseudo_end_ || regular_begin_ != regular_end_;
44 }
45
Next()46 const Representation Next() {
47 if (pseudo_begin_ != pseudo_end_) {
48 return *pseudo_begin_++;
49 } else {
50 return *regular_begin_++;
51 }
52 }
53
54 private:
55 Representations::const_iterator pseudo_begin_;
56 Representations::const_iterator pseudo_end_;
57 Representations::const_iterator regular_begin_;
58 Representations::const_iterator regular_end_;
59 };
60
61 namespace {
62
63 // The default header listener.
NoOpListener(absl::string_view,absl::string_view)64 void NoOpListener(absl::string_view /*name*/, absl::string_view /*value*/) {}
65
66 // The default HPACK indexing policy.
DefaultPolicy(absl::string_view name,absl::string_view)67 bool DefaultPolicy(absl::string_view name, absl::string_view /* value */) {
68 if (name.empty()) {
69 return false;
70 }
71 // :authority is always present and rarely changes, and has moderate
72 // length, therefore it makes a lot of sense to index (insert in the
73 // dynamic table).
74 if (name[0] == kPseudoHeaderPrefix) {
75 return name == ":authority";
76 }
77 return true;
78 }
79
80 } // namespace
81
HpackEncoder()82 HpackEncoder::HpackEncoder()
83 : output_stream_(),
84 min_table_size_setting_received_(std::numeric_limits<size_t>::max()),
85 listener_(NoOpListener),
86 should_index_(DefaultPolicy),
87 enable_compression_(true),
88 should_emit_table_size_(false) {}
89
90 HpackEncoder::~HpackEncoder() = default;
91
EncodeHeaderBlock(const Http2HeaderBlock & header_set)92 std::string HpackEncoder::EncodeHeaderBlock(
93 const Http2HeaderBlock& header_set) {
94 // Separate header set into pseudo-headers and regular headers.
95 Representations pseudo_headers;
96 Representations regular_headers;
97 bool found_cookie = false;
98 for (const auto& header : header_set) {
99 if (!found_cookie && header.first == "cookie") {
100 // Note that there can only be one "cookie" header, because header_set is
101 // a map.
102 found_cookie = true;
103 CookieToCrumbs(header, ®ular_headers);
104 } else if (!header.first.empty() &&
105 header.first[0] == kPseudoHeaderPrefix) {
106 DecomposeRepresentation(header, &pseudo_headers);
107 } else {
108 DecomposeRepresentation(header, ®ular_headers);
109 }
110 }
111
112 RepresentationIterator iter(pseudo_headers, regular_headers);
113 return EncodeRepresentations(&iter);
114 }
115
ApplyHeaderTableSizeSetting(size_t size_setting)116 void HpackEncoder::ApplyHeaderTableSizeSetting(size_t size_setting) {
117 if (size_setting == header_table_.settings_size_bound()) {
118 return;
119 }
120 if (size_setting < header_table_.settings_size_bound()) {
121 min_table_size_setting_received_ =
122 std::min(size_setting, min_table_size_setting_received_);
123 }
124 header_table_.SetSettingsHeaderTableSize(size_setting);
125 should_emit_table_size_ = true;
126 }
127
EncodeRepresentations(RepresentationIterator * iter)128 std::string HpackEncoder::EncodeRepresentations(RepresentationIterator* iter) {
129 MaybeEmitTableSize();
130 while (iter->HasNext()) {
131 const auto header = iter->Next();
132 listener_(header.first, header.second);
133 if (enable_compression_) {
134 size_t index =
135 header_table_.GetByNameAndValue(header.first, header.second);
136 if (index != kHpackEntryNotFound) {
137 EmitIndex(index);
138 } else if (should_index_(header.first, header.second)) {
139 EmitIndexedLiteral(header);
140 } else {
141 EmitNonIndexedLiteral(header, enable_compression_);
142 }
143 } else {
144 EmitNonIndexedLiteral(header, enable_compression_);
145 }
146 }
147
148 return output_stream_.TakeString();
149 }
150
EmitIndex(size_t index)151 void HpackEncoder::EmitIndex(size_t index) {
152 QUICHE_DVLOG(2) << "Emitting index " << index;
153 output_stream_.AppendPrefix(kIndexedOpcode);
154 output_stream_.AppendUint32(index);
155 }
156
EmitIndexedLiteral(const Representation & representation)157 void HpackEncoder::EmitIndexedLiteral(const Representation& representation) {
158 QUICHE_DVLOG(2) << "Emitting indexed literal: (" << representation.first
159 << ", " << representation.second << ")";
160 output_stream_.AppendPrefix(kLiteralIncrementalIndexOpcode);
161 EmitLiteral(representation);
162 header_table_.TryAddEntry(representation.first, representation.second);
163 }
164
EmitNonIndexedLiteral(const Representation & representation,bool enable_compression)165 void HpackEncoder::EmitNonIndexedLiteral(const Representation& representation,
166 bool enable_compression) {
167 QUICHE_DVLOG(2) << "Emitting nonindexed literal: (" << representation.first
168 << ", " << representation.second << ")";
169 output_stream_.AppendPrefix(kLiteralNoIndexOpcode);
170 size_t name_index = header_table_.GetByName(representation.first);
171 if (enable_compression && name_index != kHpackEntryNotFound) {
172 output_stream_.AppendUint32(name_index);
173 } else {
174 output_stream_.AppendUint32(0);
175 EmitString(representation.first);
176 }
177 EmitString(representation.second);
178 }
179
EmitLiteral(const Representation & representation)180 void HpackEncoder::EmitLiteral(const Representation& representation) {
181 size_t name_index = header_table_.GetByName(representation.first);
182 if (name_index != kHpackEntryNotFound) {
183 output_stream_.AppendUint32(name_index);
184 } else {
185 output_stream_.AppendUint32(0);
186 EmitString(representation.first);
187 }
188 EmitString(representation.second);
189 }
190
EmitString(absl::string_view str)191 void HpackEncoder::EmitString(absl::string_view str) {
192 size_t encoded_size =
193 enable_compression_ ? http2::HuffmanSize(str) : str.size();
194 if (encoded_size < str.size()) {
195 QUICHE_DVLOG(2) << "Emitted Huffman-encoded string of length "
196 << encoded_size;
197 output_stream_.AppendPrefix(kStringLiteralHuffmanEncoded);
198 output_stream_.AppendUint32(encoded_size);
199 http2::HuffmanEncodeFast(str, encoded_size, output_stream_.MutableString());
200 } else {
201 QUICHE_DVLOG(2) << "Emitted literal string of length " << str.size();
202 output_stream_.AppendPrefix(kStringLiteralIdentityEncoded);
203 output_stream_.AppendUint32(str.size());
204 output_stream_.AppendBytes(str);
205 }
206 }
207
MaybeEmitTableSize()208 void HpackEncoder::MaybeEmitTableSize() {
209 if (!should_emit_table_size_) {
210 return;
211 }
212 const size_t current_size = CurrentHeaderTableSizeSetting();
213 QUICHE_DVLOG(1) << "MaybeEmitTableSize current_size=" << current_size;
214 QUICHE_DVLOG(1) << "MaybeEmitTableSize min_table_size_setting_received_="
215 << min_table_size_setting_received_;
216 if (min_table_size_setting_received_ < current_size) {
217 output_stream_.AppendPrefix(kHeaderTableSizeUpdateOpcode);
218 output_stream_.AppendUint32(min_table_size_setting_received_);
219 }
220 output_stream_.AppendPrefix(kHeaderTableSizeUpdateOpcode);
221 output_stream_.AppendUint32(current_size);
222 min_table_size_setting_received_ = std::numeric_limits<size_t>::max();
223 should_emit_table_size_ = false;
224 }
225
226 // static
CookieToCrumbs(const Representation & cookie,Representations * out)227 void HpackEncoder::CookieToCrumbs(const Representation& cookie,
228 Representations* out) {
229 // See Section 8.1.2.5. "Compressing the Cookie Header Field" in the HTTP/2
230 // specification at https://tools.ietf.org/html/draft-ietf-httpbis-http2-14.
231 // Cookie values are split into individually-encoded HPACK representations.
232 absl::string_view cookie_value = cookie.second;
233 // Consume leading and trailing whitespace if present.
234 absl::string_view::size_type first = cookie_value.find_first_not_of(" \t");
235 absl::string_view::size_type last = cookie_value.find_last_not_of(" \t");
236 if (first == absl::string_view::npos) {
237 cookie_value = absl::string_view();
238 } else {
239 cookie_value = cookie_value.substr(first, (last - first) + 1);
240 }
241 for (size_t pos = 0;;) {
242 size_t end = cookie_value.find(';', pos);
243
244 if (end == absl::string_view::npos) {
245 out->push_back(std::make_pair(cookie.first, cookie_value.substr(pos)));
246 break;
247 }
248 out->push_back(
249 std::make_pair(cookie.first, cookie_value.substr(pos, end - pos)));
250
251 // Consume next space if present.
252 pos = end + 1;
253 if (pos != cookie_value.size() && cookie_value[pos] == ' ') {
254 pos++;
255 }
256 }
257 }
258
259 // static
DecomposeRepresentation(const Representation & header_field,Representations * out)260 void HpackEncoder::DecomposeRepresentation(const Representation& header_field,
261 Representations* out) {
262 size_t pos = 0;
263 size_t end = 0;
264 while (end != absl::string_view::npos) {
265 end = header_field.second.find('\0', pos);
266 out->push_back(std::make_pair(
267 header_field.first,
268 header_field.second.substr(
269 pos, end == absl::string_view::npos ? end : end - pos)));
270 pos = end + 1;
271 }
272 }
273
274 // Iteratively encodes a Http2HeaderBlock.
275 class HpackEncoder::Encoderator : public ProgressiveEncoder {
276 public:
277 Encoderator(const Http2HeaderBlock& header_set, HpackEncoder* encoder);
278 Encoderator(const Representations& representations, HpackEncoder* encoder);
279
280 // Encoderator is neither copyable nor movable.
281 Encoderator(const Encoderator&) = delete;
282 Encoderator& operator=(const Encoderator&) = delete;
283
284 // Returns true iff more remains to encode.
HasNext() const285 bool HasNext() const override { return has_next_; }
286
287 // Encodes and returns up to max_encoded_bytes of the current header block.
288 std::string Next(size_t max_encoded_bytes) override;
289
290 private:
291 HpackEncoder* encoder_;
292 std::unique_ptr<RepresentationIterator> header_it_;
293 Representations pseudo_headers_;
294 Representations regular_headers_;
295 bool has_next_;
296 };
297
Encoderator(const Http2HeaderBlock & header_set,HpackEncoder * encoder)298 HpackEncoder::Encoderator::Encoderator(const Http2HeaderBlock& header_set,
299 HpackEncoder* encoder)
300 : encoder_(encoder), has_next_(true) {
301 // Separate header set into pseudo-headers and regular headers.
302 bool found_cookie = false;
303 for (const auto& header : header_set) {
304 if (!found_cookie && header.first == "cookie") {
305 // Note that there can only be one "cookie" header, because header_set
306 // is a map.
307 found_cookie = true;
308 CookieToCrumbs(header, ®ular_headers_);
309 } else if (!header.first.empty() &&
310 header.first[0] == kPseudoHeaderPrefix) {
311 DecomposeRepresentation(header, &pseudo_headers_);
312 } else {
313 DecomposeRepresentation(header, ®ular_headers_);
314 }
315 }
316 header_it_ = std::make_unique<RepresentationIterator>(pseudo_headers_,
317 regular_headers_);
318
319 encoder_->MaybeEmitTableSize();
320 }
321
Encoderator(const Representations & representations,HpackEncoder * encoder)322 HpackEncoder::Encoderator::Encoderator(const Representations& representations,
323 HpackEncoder* encoder)
324 : encoder_(encoder), has_next_(true) {
325 for (const auto& header : representations) {
326 if (header.first == "cookie") {
327 CookieToCrumbs(header, ®ular_headers_);
328 } else if (!header.first.empty() &&
329 header.first[0] == kPseudoHeaderPrefix) {
330 pseudo_headers_.push_back(header);
331 } else {
332 regular_headers_.push_back(header);
333 }
334 }
335 header_it_ = std::make_unique<RepresentationIterator>(pseudo_headers_,
336 regular_headers_);
337
338 encoder_->MaybeEmitTableSize();
339 }
340
Next(size_t max_encoded_bytes)341 std::string HpackEncoder::Encoderator::Next(size_t max_encoded_bytes) {
342 QUICHE_BUG_IF(spdy_bug_61_1, !has_next_)
343 << "Encoderator::Next called with nothing left to encode.";
344 const bool enable_compression = encoder_->enable_compression_;
345
346 // Encode up to max_encoded_bytes of headers.
347 while (header_it_->HasNext() &&
348 encoder_->output_stream_.size() <= max_encoded_bytes) {
349 const Representation header = header_it_->Next();
350 encoder_->listener_(header.first, header.second);
351 if (enable_compression) {
352 size_t index = encoder_->header_table_.GetByNameAndValue(header.first,
353 header.second);
354 if (index != kHpackEntryNotFound) {
355 encoder_->EmitIndex(index);
356 } else if (encoder_->should_index_(header.first, header.second)) {
357 encoder_->EmitIndexedLiteral(header);
358 } else {
359 encoder_->EmitNonIndexedLiteral(header, enable_compression);
360 }
361 } else {
362 encoder_->EmitNonIndexedLiteral(header, enable_compression);
363 }
364 }
365
366 has_next_ = encoder_->output_stream_.size() > max_encoded_bytes;
367 return encoder_->output_stream_.BoundedTakeString(max_encoded_bytes);
368 }
369
EncodeHeaderSet(const Http2HeaderBlock & header_set)370 std::unique_ptr<HpackEncoder::ProgressiveEncoder> HpackEncoder::EncodeHeaderSet(
371 const Http2HeaderBlock& header_set) {
372 return std::make_unique<Encoderator>(header_set, this);
373 }
374
375 std::unique_ptr<HpackEncoder::ProgressiveEncoder>
EncodeRepresentations(const Representations & representations)376 HpackEncoder::EncodeRepresentations(const Representations& representations) {
377 return std::make_unique<Encoderator>(representations, this);
378 }
379
380 } // namespace spdy
381