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