1// Copyright (C) 2016 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3
4#include "bitstreams_p.h"
5#include "hpack_p.h"
6
7#include <QtCore/qbytearray.h>
8#include <QtCore/qdebug.h>
9
10#include <limits>
11
12QT_BEGIN_NAMESPACE
13
14namespace HPack
15{
16
17HeaderSize header_size(const HttpHeader &header)
18{
19 HeaderSize size(true, 0);
20 for (const HeaderField &field : header) {
21 HeaderSize delta = entry_size(entry: field);
22 if (!delta.first)
23 return HeaderSize();
24 if (std::numeric_limits<quint32>::max() - size.second < delta.second)
25 return HeaderSize();
26 size.second += delta.second;
27 }
28
29 return size;
30}
31
32struct BitPattern
33{
34 uchar value;
35 uchar bitLength;
36};
37
38bool operator == (const BitPattern &lhs, const BitPattern &rhs)
39{
40 return lhs.bitLength == rhs.bitLength && lhs.value == rhs.value;
41}
42
43namespace
44{
45
46using StreamError = BitIStream::Error;
47
48// There are several bit patterns to distinguish header fields:
49// 1 - indexed
50// 01 - literal with incremented indexing
51// 0000 - literal without indexing
52// 0001 - literal, never indexing
53// 001 - dynamic table size update.
54
55// It's always 1 or 0 actually, but the number of bits to extract
56// from the input stream - differs.
57const BitPattern Indexed = {.value: 1, .bitLength: 1};
58const BitPattern LiteralIncrementalIndexing = {.value: 1, .bitLength: 2};
59const BitPattern LiteralNoIndexing = {.value: 0, .bitLength: 4};
60const BitPattern LiteralNeverIndexing = {.value: 1, .bitLength: 4};
61const BitPattern SizeUpdate = {.value: 1, .bitLength: 3};
62
63bool is_literal_field(const BitPattern &pattern)
64{
65 return pattern == LiteralIncrementalIndexing
66 || pattern == LiteralNoIndexing
67 || pattern == LiteralNeverIndexing;
68}
69
70void write_bit_pattern(const BitPattern &pattern, BitOStream &outputStream)
71{
72 outputStream.writeBits(bits: pattern.value, bitLength: pattern.bitLength);
73}
74
75bool read_bit_pattern(const BitPattern &pattern, BitIStream &inputStream)
76{
77 uchar chunk = 0;
78
79 const quint32 bitsRead = inputStream.peekBits(from: inputStream.streamOffset(),
80 length: pattern.bitLength, dstPtr: &chunk);
81 if (bitsRead != pattern.bitLength)
82 return false;
83
84 // Since peekBits packs in the most significant bits, shift it!
85 chunk >>= (8 - bitsRead);
86 if (chunk != pattern.value)
87 return false;
88
89 inputStream.skipBits(nBits: pattern.bitLength);
90
91 return true;
92}
93
94bool is_request_pseudo_header(const QByteArray &name)
95{
96 return name == ":method" || name == ":scheme" ||
97 name == ":authority" || name == ":path";
98}
99
100} // unnamed namespace
101
102Encoder::Encoder(quint32 size, bool compress)
103 : lookupTable(size, true /*encoder needs search index*/),
104 compressStrings(compress)
105{
106}
107
108quint32 Encoder::dynamicTableSize() const
109{
110 return lookupTable.dynamicDataSize();
111}
112
113bool Encoder::encodeRequest(BitOStream &outputStream, const HttpHeader &header)
114{
115 if (!header.size()) {
116 qDebug(msg: "empty header");
117 return false;
118 }
119
120 if (!encodeRequestPseudoHeaders(outputStream, header))
121 return false;
122
123 for (const auto &field : header) {
124 if (is_request_pseudo_header(name: field.name))
125 continue;
126
127 if (!encodeHeaderField(outputStream, field))
128 return false;
129 }
130
131 return true;
132}
133
134bool Encoder::encodeResponse(BitOStream &outputStream, const HttpHeader &header)
135{
136 if (!header.size()) {
137 qDebug(msg: "empty header");
138 return false;
139 }
140
141 if (!encodeResponsePseudoHeaders(outputStream, header))
142 return false;
143
144 for (const auto &field : header) {
145 if (field.name == ":status")
146 continue;
147
148 if (!encodeHeaderField(outputStream, field))
149 return false;
150 }
151
152 return true;
153}
154
155bool Encoder::encodeSizeUpdate(BitOStream &outputStream, quint32 newSize)
156{
157 if (!lookupTable.updateDynamicTableSize(size: newSize)) {
158 qDebug(msg: "failed to update own table size");
159 return false;
160 }
161
162 write_bit_pattern(pattern: SizeUpdate, outputStream);
163 outputStream.write(src: newSize);
164
165 return true;
166}
167
168void Encoder::setMaxDynamicTableSize(quint32 size)
169{
170 // Up to a caller (HTTP2 protocol handler)
171 // to validate this size first.
172 lookupTable.setMaxDynamicTableSize(size);
173}
174
175void Encoder::setCompressStrings(bool compress)
176{
177 compressStrings = compress;
178}
179
180bool Encoder::encodeRequestPseudoHeaders(BitOStream &outputStream,
181 const HttpHeader &header)
182{
183 // The following pseudo-header fields are defined for HTTP/2 requests:
184 // - The :method pseudo-header field includes the HTTP method
185 // - The :scheme pseudo-header field includes the scheme portion of the target URI
186 // - The :authority pseudo-header field includes the authority portion of the target URI
187 // - The :path pseudo-header field includes the path and query parts of the target URI
188
189 // All HTTP/2 requests MUST include exactly one valid value for the :method,
190 // :scheme, and :path pseudo-header fields, unless it is a CONNECT request
191 // (Section 8.3). An HTTP request that omits mandatory pseudo-header fields
192 // is malformed (Section 8.1.2.6).
193
194 using size_type = decltype(header.size());
195
196 bool methodFound = false;
197 const char *headerName[] = {":authority", ":scheme", ":path"};
198 const size_type nHeaders = sizeof headerName / sizeof headerName[0];
199 bool headerFound[nHeaders] = {};
200
201 for (const auto &field : header) {
202 if (field.name == ":status") {
203 qCritical(msg: "invalid pseudo-header (:status) in a request");
204 return false;
205 }
206
207 if (field.name == ":method") {
208 if (methodFound) {
209 qCritical(msg: "only one :method pseudo-header is allowed");
210 return false;
211 }
212
213 if (!encodeMethod(outputStream, field))
214 return false;
215 methodFound = true;
216 } else if (field.name == "cookie") {
217 // "crumbs" ...
218 } else {
219 for (size_type j = 0; j < nHeaders; ++j) {
220 if (field.name == headerName[j]) {
221 if (headerFound[j]) {
222 qCritical() << "only one" << headerName[j] << "pseudo-header is allowed";
223 return false;
224 }
225 if (!encodeHeaderField(outputStream, field))
226 return false;
227 headerFound[j] = true;
228 break;
229 }
230 }
231 }
232 }
233
234 if (!methodFound) {
235 qCritical(msg: "mandatory :method pseudo-header not found");
236 return false;
237 }
238
239 // 1: don't demand headerFound[0], as :authority isn't mandatory.
240 for (size_type i = 1; i < nHeaders; ++i) {
241 if (!headerFound[i]) {
242 qCritical() << "mandatory" << headerName[i]
243 << "pseudo-header not found";
244 return false;
245 }
246 }
247
248 return true;
249}
250
251bool Encoder::encodeHeaderField(BitOStream &outputStream, const HeaderField &field)
252{
253 // TODO: at the moment we never use LiteralNo/Never Indexing ...
254
255 // Here we try:
256 // 1. indexed
257 // 2. literal indexed with indexed name/literal value
258 // 3. literal indexed with literal name/literal value
259 if (const auto index = lookupTable.indexOf(name: field.name, value: field.value))
260 return encodeIndexedField(outputStream, index);
261
262 if (const auto index = lookupTable.indexOf(name: field.name)) {
263 return encodeLiteralField(outputStream, fieldType: LiteralIncrementalIndexing,
264 nameIndex: index, value: field.value, withCompression: compressStrings);
265 }
266
267 return encodeLiteralField(outputStream, fieldType: LiteralIncrementalIndexing,
268 name: field.name, value: field.value, withCompression: compressStrings);
269}
270
271bool Encoder::encodeMethod(BitOStream &outputStream, const HeaderField &field)
272{
273 Q_ASSERT(field.name == ":method");
274 quint32 index = lookupTable.indexOf(name: field.name, value: field.value);
275 if (index)
276 return encodeIndexedField(outputStream, index);
277
278 index = lookupTable.indexOf(name: field.name);
279 Q_ASSERT(index); // ":method" is always in the static table ...
280 return encodeLiteralField(outputStream, fieldType: LiteralIncrementalIndexing,
281 nameIndex: index, value: field.value, withCompression: compressStrings);
282}
283
284bool Encoder::encodeResponsePseudoHeaders(BitOStream &outputStream, const HttpHeader &header)
285{
286 bool statusFound = false;
287 for (const auto &field : header) {
288 if (is_request_pseudo_header(name: field.name)) {
289 qCritical() << "invalid pseudo-header" << field.name << "in http response";
290 return false;
291 }
292
293 if (field.name == ":status") {
294 if (statusFound) {
295 qDebug(msg: "only one :status pseudo-header is allowed");
296 return false;
297 }
298 if (!encodeHeaderField(outputStream, field))
299 return false;
300 statusFound = true;
301 } else if (field.name == "cookie") {
302 // "crumbs"..
303 }
304 }
305
306 if (!statusFound)
307 qCritical(msg: "mandatory :status pseudo-header not found");
308
309 return statusFound;
310}
311
312bool Encoder::encodeIndexedField(BitOStream &outputStream, quint32 index) const
313{
314 Q_ASSERT(lookupTable.indexIsValid(index));
315
316 write_bit_pattern(pattern: Indexed, outputStream);
317 outputStream.write(src: index);
318
319 return true;
320}
321
322bool Encoder::encodeLiteralField(BitOStream &outputStream, const BitPattern &fieldType,
323 const QByteArray &name, const QByteArray &value,
324 bool withCompression)
325{
326 Q_ASSERT(is_literal_field(fieldType));
327 // According to HPACK, the bit pattern is
328 // 01 | 000000 (integer 0 that fits into 6-bit prefix),
329 // since integers always end on byte boundary,
330 // this also implies that we always start at bit offset == 0.
331 if (outputStream.bitLength() % 8) {
332 qCritical(msg: "invalid bit offset");
333 return false;
334 }
335
336 if (fieldType == LiteralIncrementalIndexing) {
337 if (!lookupTable.prependField(name, value))
338 qDebug(msg: "failed to prepend a new field");
339 }
340
341 write_bit_pattern(pattern: fieldType, outputStream);
342
343 outputStream.write(src: 0);
344 outputStream.write(src: name, compressed: withCompression);
345 outputStream.write(src: value, compressed: withCompression);
346
347 return true;
348}
349
350bool Encoder::encodeLiteralField(BitOStream &outputStream, const BitPattern &fieldType,
351 quint32 nameIndex, const QByteArray &value,
352 bool withCompression)
353{
354 Q_ASSERT(is_literal_field(fieldType));
355
356 QByteArray name;
357 const bool found = lookupTable.fieldName(index: nameIndex, dst: &name);
358 Q_UNUSED(found);
359 Q_ASSERT(found);
360
361 if (fieldType == LiteralIncrementalIndexing) {
362 if (!lookupTable.prependField(name, value))
363 qDebug(msg: "failed to prepend a new field");
364 }
365
366 write_bit_pattern(pattern: fieldType, outputStream);
367 outputStream.write(src: nameIndex);
368 outputStream.write(src: value, compressed: withCompression);
369
370 return true;
371}
372
373Decoder::Decoder(quint32 size)
374 : lookupTable{size, false /* we do not need search index ... */}
375{
376}
377
378bool Decoder::decodeHeaderFields(BitIStream &inputStream)
379{
380 header.clear();
381 while (true) {
382 if (read_bit_pattern(pattern: Indexed, inputStream)) {
383 if (!decodeIndexedField(inputStream))
384 return false;
385 } else if (read_bit_pattern(pattern: LiteralIncrementalIndexing, inputStream)) {
386 if (!decodeLiteralField(fieldType: LiteralIncrementalIndexing, inputStream))
387 return false;
388 } else if (read_bit_pattern(pattern: LiteralNoIndexing, inputStream)) {
389 if (!decodeLiteralField(fieldType: LiteralNoIndexing, inputStream))
390 return false;
391 } else if (read_bit_pattern(pattern: LiteralNeverIndexing, inputStream)) {
392 if (!decodeLiteralField(fieldType: LiteralNeverIndexing, inputStream))
393 return false;
394 } else if (read_bit_pattern(pattern: SizeUpdate, inputStream)) {
395 if (!decodeSizeUpdate(inputStream))
396 return false;
397 } else {
398 return inputStream.bitLength() == inputStream.streamOffset();
399 }
400 }
401
402 return false;
403}
404
405quint32 Decoder::dynamicTableSize() const
406{
407 return lookupTable.dynamicDataSize();
408}
409
410void Decoder::setMaxDynamicTableSize(quint32 size)
411{
412 // Up to a caller (HTTP2 protocol handler)
413 // to validate this size first.
414 lookupTable.setMaxDynamicTableSize(size);
415}
416
417bool Decoder::decodeIndexedField(BitIStream &inputStream)
418{
419 quint32 index = 0;
420 if (inputStream.read(dstPtr: &index)) {
421 if (!index) {
422 // "The index value of 0 is not used.
423 // It MUST be treated as a decoding
424 // error if found in an indexed header
425 // field representation."
426 return false;
427 }
428
429 QByteArray name, value;
430 if (lookupTable.field(index, name: &name, value: &value))
431 return processDecodedField(fieldType: Indexed, name, value);
432 } else {
433 handleStreamError(inputStream);
434 }
435
436 return false;
437}
438
439bool Decoder::decodeSizeUpdate(BitIStream &inputStream)
440{
441 // For now, just read and skip bits.
442 quint32 maxSize = 0;
443 if (inputStream.read(dstPtr: &maxSize)) {
444 if (!lookupTable.updateDynamicTableSize(size: maxSize))
445 return false;
446
447 return true;
448 }
449
450 handleStreamError(inputStream);
451 return false;
452}
453
454bool Decoder::decodeLiteralField(const BitPattern &fieldType, BitIStream &inputStream)
455{
456 // https://http2.github.io/http2-spec/compression.html
457 // 6.2.1, 6.2.2, 6.2.3
458 // Format for all 'literal' is similar,
459 // the difference - is how we update/not our lookup table.
460 quint32 index = 0;
461 if (inputStream.read(dstPtr: &index)) {
462 QByteArray name;
463 if (!index) {
464 // Read a string.
465 if (!inputStream.read(dstPtr: &name)) {
466 handleStreamError(inputStream);
467 return false;
468 }
469 } else {
470 if (!lookupTable.fieldName(index, dst: &name))
471 return false;
472 }
473
474 QByteArray value;
475 if (inputStream.read(dstPtr: &value))
476 return processDecodedField(fieldType, name, value);
477 }
478
479 handleStreamError(inputStream);
480
481 return false;
482}
483
484bool Decoder::processDecodedField(const BitPattern &fieldType,
485 const QByteArray &name,
486 const QByteArray &value)
487{
488 if (fieldType == LiteralIncrementalIndexing) {
489 if (!lookupTable.prependField(name, value))
490 return false;
491 }
492
493 header.push_back(x: HeaderField(name, value));
494 return true;
495}
496
497void Decoder::handleStreamError(BitIStream &inputStream)
498{
499 const auto errorCode(inputStream.error());
500 if (errorCode == StreamError::NoError)
501 return;
502
503 // For now error handling not needed here,
504 // HTTP2 layer will end with session error/COMPRESSION_ERROR.
505}
506
507}
508
509QT_END_NAMESPACE
510

source code of qtbase/src/network/access/http2/hpack.cpp