From 71f507788baa7c4c9946788f77182ccfd9748bb6 Mon Sep 17 00:00:00 2001 From: Timur Pocheptsov Date: Wed, 23 Dec 2015 11:41:29 +0100 Subject: HPACK implementation Static Huffman coding + HPACK encode/decode algorithm (for HTTP2) + auto test. Change-Id: I85d6269076cc1d586d17c87bcdee49c21522ef78 Task-number: QTBUG-50946 Reviewed-by: Allan Sandfeld Jensen --- src/network/access/access.pri | 1 + src/network/access/http2/bitstreams.cpp | 336 ++++++++++ src/network/access/http2/bitstreams_p.h | 185 ++++++ src/network/access/http2/hpack.cpp | 551 +++++++++++++++++ src/network/access/http2/hpack_p.h | 155 +++++ src/network/access/http2/hpacktable.cpp | 533 ++++++++++++++++ src/network/access/http2/hpacktable_p.h | 237 +++++++ src/network/access/http2/http2.pri | 11 + src/network/access/http2/huffman.cpp | 573 +++++++++++++++++ src/network/access/http2/huffman_p.h | 182 ++++++ tests/auto/network/access/access.pro | 2 + tests/auto/network/access/hpack/hpack.pro | 6 + tests/auto/network/access/hpack/tst_hpack.cpp | 852 ++++++++++++++++++++++++++ 13 files changed, 3624 insertions(+) create mode 100644 src/network/access/http2/bitstreams.cpp create mode 100644 src/network/access/http2/bitstreams_p.h create mode 100644 src/network/access/http2/hpack.cpp create mode 100644 src/network/access/http2/hpack_p.h create mode 100644 src/network/access/http2/hpacktable.cpp create mode 100644 src/network/access/http2/hpacktable_p.h create mode 100644 src/network/access/http2/http2.pri create mode 100644 src/network/access/http2/huffman.cpp create mode 100644 src/network/access/http2/huffman_p.h create mode 100644 tests/auto/network/access/hpack/hpack.pro create mode 100644 tests/auto/network/access/hpack/tst_hpack.cpp diff --git a/src/network/access/access.pri b/src/network/access/access.pri index ba0e448010..746ddc6916 100644 --- a/src/network/access/access.pri +++ b/src/network/access/access.pri @@ -75,3 +75,4 @@ SOURCES += \ mac: LIBS_PRIVATE += -framework Security include($$PWD/../../3rdparty/zlib_dependency.pri) +include($$PWD/http2/http2.pri) diff --git a/src/network/access/http2/bitstreams.cpp b/src/network/access/http2/bitstreams.cpp new file mode 100644 index 0000000000..d22c7cd4ec --- /dev/null +++ b/src/network/access/http2/bitstreams.cpp @@ -0,0 +1,336 @@ +/**************************************************************************** +** +** Copyright (C) 2016 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtNetwork module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include "bitstreams_p.h" +#include "huffman_p.h" + +#include + +#include + +QT_BEGIN_NAMESPACE + +static_assert(std::numeric_limits::digits == 8, "octets expected"); + +namespace HPack +{ + +BitOStream::BitOStream(std::vector &b) + : buffer(b), + // All data 'packed' before: + bitsSet(8 * quint64(b.size())) +{ +} + +void BitOStream::writeBits(uchar bits, quint8 bitLength) +{ + Q_ASSERT(bitLength <= 8); + + quint8 count = bitsSet % 8; // bits used in buffer.back(), but 0 means 8 + bits <<= 8 - bitLength; // at top of byte, lower bits clear + if (count) { // we have a part-used byte; fill it some more: + buffer.back() |= bits >> count; + count = 8 - count; + } // count bits have been consumed (and 0 now means 0) + if (bitLength > count) + buffer.push_back(bits << count); + + bitsSet += bitLength; +} + +void BitOStream::write(quint32 src) +{ + const quint8 prefixLen = 8 - bitsSet % 8; + const quint32 fullPrefix = (1 << prefixLen) - 1; + + // https://http2.github.io/http2-spec/compression.html#low-level.representation, + // 5.1 + if (src < fullPrefix) { + writeBits(uchar(src), prefixLen); + } else { + writeBits(uchar(fullPrefix), prefixLen); + // We're on the byte boundary now, + // so we can just 'push_back'. + Q_ASSERT(!(bitsSet % 8)); + src -= fullPrefix; + while (src >= 128) { + buffer.push_back(uchar(src % 128 + 128)); + src /= 128; + bitsSet += 8; + } + buffer.push_back(src); + bitsSet += 8; + } +} + +void BitOStream::write(const QByteArray &src, bool compressed) +{ + quint32 byteLen = src.size(); + if (compressed && byteLen) { + const auto bitLen = huffman_encoded_bit_length(src); + Q_ASSERT(bitLen && std::numeric_limits::max() >= (bitLen + 7) / 8); + byteLen = (bitLen + 7) / 8; + writeBits(uchar(1), 1); // bit set - compressed + } else { + writeBits(uchar(0), 1); // no compression. + } + + write(byteLen); + + if (compressed) { + huffman_encode_string(src, *this); + } else { + bitsSet += quint64(src.size()) * 8; + buffer.insert(buffer.end(), src.begin(), src.end()); + } +} + +quint64 BitOStream::bitLength() const +{ + return bitsSet; +} + +quint64 BitOStream::byteLength() const +{ + return buffer.size(); +} + +const uchar *BitOStream::begin() const +{ + return &buffer[0]; +} + +const uchar *BitOStream::end() const +{ + return &buffer[0] + buffer.size(); +} + +void BitOStream::clear() +{ + buffer.clear(); + bitsSet = 0; +} + +BitIStream::BitIStream() + : first(), + last(), + offset(), + streamError(Error::NoError) +{ +} + +BitIStream::BitIStream(const uchar *begin, const uchar *end) + : first(begin), + last(end), + offset(), + streamError(Error::NoError) +{ +} + +quint64 BitIStream::bitLength() const +{ + return quint64(last - first) * 8; +} + +bool BitIStream::hasMoreBits() const +{ + return offset < bitLength(); +} + +bool BitIStream::skipBits(quint64 nBits) +{ + if (nBits > bitLength() || bitLength() - nBits < offset) + return false; + + offset += nBits; + return true; +} + +bool BitIStream::rewindOffset(quint64 nBits) +{ + if (nBits > offset) + return false; + + offset -= nBits; + return true; +} + +bool BitIStream::read(quint32 *dstPtr) +{ + Q_ASSERT(dstPtr); + quint32 &dst = *dstPtr; + + // 5.1 Integer Representation + // + // Integers are used to represent name indexes, header field indexes, or string lengths. + // An integer representation can start anywhere within an octet. + // To allow for optimized processing, an integer representation always finishes at the end of an octet. + // An integer is represented in two parts: a prefix that fills the current octet and an optional + // list of octets that are used if the integer value does not fit within the prefix. + // The number of bits of the prefix (called N) is a parameter of the integer representation. + // If the integer value is small enough, i.e., strictly less than 2N-1, it is compressed within the N-bit prefix. + // ... + // The prefix size, N, is always between 1 and 8 bits. An integer + // starting at an octet boundary will have an 8-bit prefix. + + // Technically, such integers can be of any size, but as we do not have arbitrary-long integers, + // everything that does not fit into 'dst' we consider as an error (after all, try to allocate a string + // of such size and ... hehehe - send it as a part of a header! + + // This function updates the offset _only_ if the read was successful. + if (offset >= bitLength()) { + setError(Error::NotEnoughData); + return false; + } + + setError(Error::NoError); + + const quint32 prefixLen = 8 - offset % 8; + const quint32 fullPrefix = (1 << prefixLen) - 1; + + const uchar prefix = uchar(first[offset / 8] & fullPrefix); + if (prefix < fullPrefix) { + // The number fitted into the prefix bits. + dst = prefix; + offset += prefixLen; + return true; + } + + quint32 newOffset = offset + prefixLen; + // We have a list of bytes representing an integer ... + quint64 val = prefix; + quint32 octetPower = 0; + + while (true) { + if (newOffset >= bitLength()) { + setError(Error::NotEnoughData); + return false; + } + + const uchar octet = first[newOffset / 8]; + + if (octetPower == 28 && octet > 15) { + qCritical("integer is too big"); + setError(Error::InvalidInteger); + return false; + } + + val += quint32(octet & 0x7f) << octetPower; + newOffset += 8; + + if (!(octet & 0x80)) { + // The most significant bit of each octet is used + // as a continuation flag: its value is set to 1 + // except for the last octet in the list. + break; + } + + octetPower += 7; + } + + dst = val; + offset = newOffset; + Q_ASSERT(!(offset % 8)); + + return true; +} + +bool BitIStream::read(QByteArray *dstPtr) +{ + Q_ASSERT(dstPtr); + QByteArray &dst = *dstPtr; + //5.2 String Literal Representation + // + // Header field names and header field values can be represented as string literals. + // A string literal is compressed as a sequence of octets, either by directly encoding + // the string literal's octets or by using a Huffman code. + + // We update the offset _only_ if the read was successful. + + const quint64 oldOffset = offset; + uchar compressed = 0; + if (peekBits(offset, 1, &compressed) != 1 || !skipBits(1)) { + setError(Error::NotEnoughData); + return false; + } + + setError(Error::NoError); + + quint32 len = 0; + if (read(&len)) { + Q_ASSERT(!(offset % 8)); + if (len <= (bitLength() - offset) / 8) { // We have enough data to read a string ... + if (!compressed) { + // Now good news, integer always ends on a byte boundary. + // We can read 'len' bytes without any bit magic. + const char *src = reinterpret_cast(first + offset / 8); + dst = QByteArray(src, len); + offset += quint64(len) * 8; + return true; + } + + BitIStream slice(first + offset / 8, first + offset / 8 + len); + if (huffman_decode_string(slice, &dst)) { + offset += quint64(len) * 8; + return true; + } + + setError(Error::CompressionError); + } else { + setError(Error::NotEnoughData); + } + } // else the exact reason was set by read(quint32). + + offset = oldOffset; + return false; +} + +BitIStream::Error BitIStream::error() const +{ + return streamError; +} + +void BitIStream::setError(Error newState) +{ + streamError = newState; +} + +} // namespace HPack + +QT_END_NAMESPACE diff --git a/src/network/access/http2/bitstreams_p.h b/src/network/access/http2/bitstreams_p.h new file mode 100644 index 0000000000..9eba319dc2 --- /dev/null +++ b/src/network/access/http2/bitstreams_p.h @@ -0,0 +1,185 @@ +/**************************************************************************** +** +** Copyright (C) 2016 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtNetwork module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef BITSTREAMS_P_H +#define BITSTREAMS_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists for the convenience +// of other Qt classes. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include +#include + +#include +#include +#include + +QT_BEGIN_NAMESPACE + +class QByteArray; + +namespace HPack +{ + +// BitOStream works with an external buffer, +// for example, HEADERS frame. +class Q_AUTOTEST_EXPORT BitOStream +{ +public: + BitOStream(std::vector &buffer); + + // Write 'bitLength' bits from the least significant + // bits in 'bits' to bitstream: + void writeBits(uchar bits, quint8 bitLength); + // HPACK data format, we support: + // * 32-bit integers + // * strings + void write(quint32 src); + void write(const QByteArray &src, bool compressed); + + quint64 bitLength() const; + quint64 byteLength() const; + const uchar *begin() const; + const uchar *end() const; + + void clear(); + +private: + Q_DISABLE_COPY(BitOStream); + + std::vector &buffer; + quint64 bitsSet; +}; + +class Q_AUTOTEST_EXPORT BitIStream +{ +public: + // Error is set by 'read' functions. + // 'peek' does not set the error, + // since it just peeks some bits + // without the notion of wrong/right. + // 'read' functions only change 'streamOffset' + // on success. + enum class Error + { + NoError, + NotEnoughData, + CompressionError, + InvalidInteger + }; + + BitIStream(); + BitIStream(const uchar *f, const uchar *l); + + quint64 bitLength() const; + bool hasMoreBits() const; + + // peekBits tries to read 'length' bits from the bitstream into + // 'dst' ('length' must be <= sizeof(dst) * 8), packing them + // starting from the most significant bit of the most significant + // byte. It's a template so that we can use it with different + // integer types. Returns the number of bits actually read. + // Does not change stream's offset. + + template + quint64 peekBits(quint64 from, quint64 length, T *dstPtr) const + { + static_assert(std::is_unsigned::value, "peekBits: unsigned integer type expected"); + + Q_ASSERT(dstPtr); + Q_ASSERT(length <= sizeof(T) * 8); + + if (from >= bitLength() || !length) + return 0; + + T &dst = *dstPtr; + dst = T(); + length = std::min(length, bitLength() - from); + + const uchar *srcByte = first + from / 8; + auto bitsToRead = length + from % 8; + + while (bitsToRead > 8) { + dst = (dst << 8) | *srcByte; + bitsToRead -= 8; + ++srcByte; + } + + dst <<= bitsToRead; + dst |= *srcByte >> (8 - bitsToRead); + dst <<= sizeof(T) * 8 - length; + + return length; + } + + quint64 streamOffset() const + { + return offset; + } + + bool skipBits(quint64 nBits); + bool rewindOffset(quint64 nBits); + + bool read(quint32 *dstPtr); + bool read(QByteArray *dstPtr); + + Error error() const; + +private: + void setError(Error newState); + + const uchar *first; + const uchar *last; + quint64 offset; + Error streamError; +}; + +} // namespace HPack + +QT_END_NAMESPACE + +#endif diff --git a/src/network/access/http2/hpack.cpp b/src/network/access/http2/hpack.cpp new file mode 100644 index 0000000000..95e6f9051b --- /dev/null +++ b/src/network/access/http2/hpack.cpp @@ -0,0 +1,551 @@ +/**************************************************************************** +** +** Copyright (C) 2016 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtNetwork module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include "bitstreams_p.h" +#include "hpack_p.h" + +#include +#include + +#include + +QT_BEGIN_NAMESPACE + +namespace HPack +{ + +HeaderSize header_size(const HttpHeader &header) +{ + HeaderSize size(true, 0); + for (const HeaderField &field : header) { + HeaderSize delta = entry_size(field); + if (!delta.first) + return HeaderSize(); + if (std::numeric_limits::max() - size.second < delta.second) + return HeaderSize(); + size.second += delta.second; + } + + return size; +} + +struct BitPattern +{ + BitPattern() + : value(), + bitLength() + { + } + + BitPattern(uchar v, uchar len) + : value(v), + bitLength(len) + { + } + + uchar value; + uchar bitLength; +}; + +bool operator == (const BitPattern &lhs, const BitPattern &rhs) +{ + return lhs.bitLength == rhs.bitLength && lhs.value == rhs.value; +} + +namespace +{ + +using StreamError = BitIStream::Error; + +// There are several bit patterns to distinguish header fields: +// 1 - indexed +// 01 - literal with incremented indexing +// 0000 - literal without indexing +// 0001 - literal, never indexing +// 001 - dynamic table size update. + +// It's always 1 or 0 actually, but the number of bits to extract +// from the input stream - differs. +const BitPattern Indexed(1, 1); +const BitPattern LiteralIncrementalIndexing(1, 2); +const BitPattern LiteralNoIndexing(0, 4); +const BitPattern LiteralNeverIndexing(1, 4); +const BitPattern SizeUpdate(1, 3); + +bool is_literal_field(const BitPattern &pattern) +{ + return pattern == LiteralIncrementalIndexing + || pattern == LiteralNoIndexing + || pattern == LiteralNeverIndexing; +} + +void write_bit_pattern(const BitPattern &pattern, BitOStream &outputStream) +{ + outputStream.writeBits(pattern.value, pattern.bitLength); +} + +bool read_bit_pattern(const BitPattern &pattern, BitIStream &inputStream) +{ + uchar chunk = 0; + + const quint32 bitsRead = inputStream.peekBits(inputStream.streamOffset(), + pattern.bitLength, &chunk); + if (bitsRead != pattern.bitLength) + return false; + + // Since peekBits packs in the most significant bits, shift it! + chunk >>= (8 - bitsRead); + if (chunk != pattern.value) + return false; + + inputStream.skipBits(pattern.bitLength); + + return true; +} + +bool is_request_pseudo_header(const QByteArray &name) +{ + return name == ":method" || name == ":scheme" || + name == ":authority" || name == ":path"; +} + +} // unnamed namespace + +Encoder::Encoder(quint32 size, bool compress) + : lookupTable(size, true /*encoder needs search index*/), + compressStrings(compress) +{ +} + +quint32 Encoder::dynamicTableSize() const +{ + return lookupTable.dynamicDataSize(); +} + +bool Encoder::encodeRequest(BitOStream &outputStream, const HttpHeader &header) +{ + if (!header.size()) { + qDebug("empty header"); + return false; + } + + if (!encodeRequestPseudoHeaders(outputStream, header)) + return false; + + for (const auto &field : header) { + if (is_request_pseudo_header(field.name)) + continue; + + if (!encodeHeaderField(outputStream, field)) + return false; + } + + return true; +} + +bool Encoder::encodeResponse(BitOStream &outputStream, const HttpHeader &header) +{ + if (!header.size()) { + qDebug("empty header"); + return false; + } + + if (!encodeResponsePseudoHeaders(outputStream, header)) + return false; + + for (const auto &field : header) { + if (field.name == ":status") + continue; + + if (!encodeHeaderField(outputStream, field)) + return false; + } + + return true; +} + +bool Encoder::encodeSizeUpdate(BitOStream &outputStream, quint32 newSize) +{ + if (!lookupTable.updateDynamicTableSize(newSize)) { + qDebug("failed to update own table size"); + return false; + } + + write_bit_pattern(SizeUpdate, outputStream); + outputStream.write(newSize); + + return true; +} + +void Encoder::setMaxDynamicTableSize(quint32 size) +{ + // Up to a caller (HTTP2 protocol handler) + // to validate this size first. + lookupTable.setMaxDynamicTableSize(size); +} + +bool Encoder::encodeRequestPseudoHeaders(BitOStream &outputStream, + const HttpHeader &header) +{ + // The following pseudo-header fields are defined for HTTP/2 requests: + // - The :method pseudo-header field includes the HTTP method + // - The :scheme pseudo-header field includes the scheme portion of the target URI + // - The :authority pseudo-header field includes the authority portion of the target URI + // - The :path pseudo-header field includes the path and query parts of the target URI + + // All HTTP/2 requests MUST include exactly one valid value for the :method, + // :scheme, and :path pseudo-header fields, unless it is a CONNECT request + // (Section 8.3). An HTTP request that omits mandatory pseudo-header fields + // is malformed (Section 8.1.2.6). + + using size_type = decltype(header.size()); + + bool methodFound = false; + const char *headerName[] = {":authority", ":scheme", ":path"}; + const size_type nHeaders = sizeof headerName / sizeof headerName[0]; + bool headerFound[nHeaders] = {}; + + for (const auto &field : header) { + if (field.name == ":status") { + qCritical("invalid pseudo-header (:status) in a request"); + return false; + } + + if (field.name == ":method") { + if (methodFound) { + qCritical("only one :method pseudo-header is allowed"); + return false; + } + + if (!encodeMethod(outputStream, field)) + return false; + methodFound = true; + } else if (field.name == "cookie") { + // "crumbs" ... + } else { + for (size_type j = 0; j < nHeaders; ++j) { + if (field.name == headerName[j]) { + if (headerFound[j]) { + qCritical() << "only one" << headerName[j] << "pseudo-header is allowed"; + return false; + } + if (!encodeHeaderField(outputStream, field)) + return false; + headerFound[j] = true; + break; + } + } + } + } + + if (!methodFound) { + qCritical("mandatory :method pseudo-header not found"); + return false; + } + + // 1: don't demand headerFound[0], as :authority isn't mandatory. + for (size_type i = 1; i < nHeaders; ++i) { + if (!headerFound[i]) { + qCritical() << "mandatory" << headerName[i] + << "pseudo-header not found"; + return false; + } + } + + return true; +} + +bool Encoder::encodeHeaderField(BitOStream &outputStream, const HeaderField &field) +{ + // TODO: at the moment we never use LiteralNo/Never Indexing ... + + // Here we try: + // 1. indexed + // 2. literal indexed with indexed name/literal value + // 3. literal indexed with literal name/literal value + if (const auto index = lookupTable.indexOf(field.name, field.value)) + return encodeIndexedField(outputStream, index); + + if (const auto index = lookupTable.indexOf(field.name)) { + return encodeLiteralField(outputStream, LiteralIncrementalIndexing, + index, field.value, compressStrings); + } + + return encodeLiteralField(outputStream, LiteralIncrementalIndexing, + field.name, field.value, compressStrings); +} + +bool Encoder::encodeMethod(BitOStream &outputStream, const HeaderField &field) +{ + Q_ASSERT(field.name == ":method"); + quint32 index = lookupTable.indexOf(field.name, field.value); + if (index) + return encodeIndexedField(outputStream, index); + + index = lookupTable.indexOf(field.name); + Q_ASSERT(index); // ":method" is always in the static table ... + return encodeLiteralField(outputStream, LiteralIncrementalIndexing, + index, field.value, compressStrings); +} + +bool Encoder::encodeResponsePseudoHeaders(BitOStream &outputStream, const HttpHeader &header) +{ + bool statusFound = false; + for (const auto &field : header) { + if (is_request_pseudo_header(field.name)) { + qCritical() << "invalid pseudo-header" << field.name << "in http response"; + return false; + } + + if (field.name == ":status") { + if (statusFound) { + qDebug("only one :status pseudo-header is allowed"); + return false; + } + if (!encodeHeaderField(outputStream, field)) + return false; + statusFound = true; + } else if (field.name == "cookie") { + // "crumbs".. + } + } + + if (!statusFound) + qCritical("mandatory :status pseudo-header not found"); + + return statusFound; +} + +bool Encoder::encodeIndexedField(BitOStream &outputStream, quint32 index) const +{ + Q_ASSERT(lookupTable.indexIsValid(index)); + + write_bit_pattern(Indexed, outputStream); + outputStream.write(index); + + return true; +} + +bool Encoder::encodeLiteralField(BitOStream &outputStream, const BitPattern &fieldType, + const QByteArray &name, const QByteArray &value, + bool withCompression) +{ + Q_ASSERT(is_literal_field(fieldType)); + // According to HPACK, the bit pattern is + // 01 | 000000 (integer 0 that fits into 6-bit prefix), + // since integers always end on byte boundary, + // this also implies that we always start at bit offset == 0. + if (outputStream.bitLength() % 8) { + qCritical("invalid bit offset"); + return false; + } + + if (fieldType == LiteralIncrementalIndexing) { + if (!lookupTable.prependField(name, value)) + qDebug("failed to prepend a new field"); + } + + write_bit_pattern(fieldType, outputStream); + + outputStream.write(0); + outputStream.write(name, withCompression); + outputStream.write(value, withCompression); + + return true; +} + +bool Encoder::encodeLiteralField(BitOStream &outputStream, const BitPattern &fieldType, + quint32 nameIndex, const QByteArray &value, + bool withCompression) +{ + Q_ASSERT(is_literal_field(fieldType)); + + QByteArray name; + const bool found = lookupTable.fieldName(nameIndex, &name); + Q_UNUSED(found) Q_ASSERT(found); + + if (fieldType == LiteralIncrementalIndexing) { + if (!lookupTable.prependField(name, value)) + qDebug("failed to prepend a new field"); + } + + write_bit_pattern(fieldType, outputStream); + outputStream.write(nameIndex); + outputStream.write(value, withCompression); + + return true; +} + +Decoder::Decoder(quint32 size) + : lookupTable{size, false /* we do not need search index ... */} +{ +} + +bool Decoder::decodeHeaderFields(BitIStream &inputStream) +{ + header.clear(); + while (true) { + if (read_bit_pattern(Indexed, inputStream)) { + if (!decodeIndexedField(inputStream)) + return false; + } else if (read_bit_pattern(LiteralIncrementalIndexing, inputStream)) { + if (!decodeLiteralField(LiteralIncrementalIndexing, inputStream)) + return false; + } else if (read_bit_pattern(LiteralNoIndexing, inputStream)) { + if (!decodeLiteralField(LiteralNoIndexing, inputStream)) + return false; + } else if (read_bit_pattern(LiteralNeverIndexing, inputStream)) { + if (!decodeLiteralField(LiteralNeverIndexing, inputStream)) + return false; + } else if (read_bit_pattern(SizeUpdate, inputStream)) { + if (!decodeSizeUpdate(inputStream)) + return false; + } else { + return inputStream.bitLength() == inputStream.streamOffset(); + } + } + + return false; +} + +quint32 Decoder::dynamicTableSize() const +{ + return lookupTable.dynamicDataSize(); +} + +void Decoder::setMaxDynamicTableSize(quint32 size) +{ + // Up to a caller (HTTP2 protocol handler) + // to validate this size first. + lookupTable.setMaxDynamicTableSize(size); +} + +bool Decoder::decodeIndexedField(BitIStream &inputStream) +{ + quint32 index = 0; + if (inputStream.read(&index)) { + if (!index) { + // "The index value of 0 is not used. + // It MUST be treated as a decoding + // error if found in an indexed header + // field representation." + return false; + } + + QByteArray name, value; + if (lookupTable.field(index, &name, &value)) + return processDecodedField(Indexed, name, value); + } else { + handleStreamError(inputStream); + } + + return false; +} + +bool Decoder::decodeSizeUpdate(BitIStream &inputStream) +{ + // For now, just read and skip bits. + quint32 maxSize = 0; + if (inputStream.read(&maxSize)) { + if (!lookupTable.updateDynamicTableSize(maxSize)) + return false; + + return true; + } + + handleStreamError(inputStream); + return false; +} + +bool Decoder::decodeLiteralField(const BitPattern &fieldType, BitIStream &inputStream) +{ + // https://http2.github.io/http2-spec/compression.html + // 6.2.1, 6.2.2, 6.2.3 + // Format for all 'literal' is similar, + // the difference - is how we update/not our lookup table. + quint32 index = 0; + if (inputStream.read(&index)) { + QByteArray name; + if (!index) { + // Read a string. + if (!inputStream.read(&name)) { + handleStreamError(inputStream); + return false; + } + } else { + if (!lookupTable.fieldName(index, &name)) + return false; + } + + QByteArray value; + if (inputStream.read(&value)) + return processDecodedField(fieldType, name, value); + } + + handleStreamError(inputStream); + + return false; +} + +bool Decoder::processDecodedField(const BitPattern &fieldType, + const QByteArray &name, + const QByteArray &value) +{ + if (fieldType == LiteralIncrementalIndexing) { + if (!lookupTable.prependField(name, value)) + return false; + } + + header.push_back(HeaderField(name, value)); + return true; +} + +void Decoder::handleStreamError(BitIStream &inputStream) +{ + const auto errorCode(inputStream.error()); + if (errorCode == StreamError::NoError) + return; + + // For now error handling not needed here, + // HTTP2 layer will end with session error/COMPRESSION_ERROR. +} + +} + +QT_END_NAMESPACE diff --git a/src/network/access/http2/hpack_p.h b/src/network/access/http2/hpack_p.h new file mode 100644 index 0000000000..6a1d30d87b --- /dev/null +++ b/src/network/access/http2/hpack_p.h @@ -0,0 +1,155 @@ +/**************************************************************************** +** +** Copyright (C) 2016 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtNetwork module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef HPACK_P_H +#define HPACK_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists for the convenience +// of other Qt classes. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include "hpacktable_p.h" + +#include + +#include + +QT_BEGIN_NAMESPACE + +class QByteArray; + +namespace HPack +{ + +using HttpHeader = std::vector; +HeaderSize header_size(const HttpHeader &header); + +class Q_AUTOTEST_EXPORT Encoder +{ +public: + Encoder(quint32 maxTableSize, bool compressStrings); + + quint32 dynamicTableSize() const; + + bool encodeRequest(class BitOStream &outputStream, + const HttpHeader &header); + bool encodeResponse(BitOStream &outputStream, + const HttpHeader &header); + + bool encodeSizeUpdate(BitOStream &outputStream, + quint32 newSize); + + void setMaxDynamicTableSize(quint32 size); + +private: + bool encodeRequestPseudoHeaders(BitOStream &outputStream, + const HttpHeader &header); + bool encodeHeaderField(BitOStream &outputStream, + const HeaderField &field); + bool encodeMethod(BitOStream &outputStream, + const HeaderField &field); + + bool encodeResponsePseudoHeaders(BitOStream &outputStream, + const HttpHeader &header); + + bool encodeIndexedField(BitOStream &outputStream, quint32 index) const; + + + bool encodeLiteralField(BitOStream &outputStream, + const struct BitPattern &fieldType, + quint32 nameIndex, + const QByteArray &value, + bool withCompression); + + bool encodeLiteralField(BitOStream &outputStream, + const BitPattern &fieldType, + const QByteArray &name, + const QByteArray &value, + bool withCompression); + + FieldLookupTable lookupTable; + bool compressStrings; +}; + +class Q_AUTOTEST_EXPORT Decoder +{ +public: + Decoder(quint32 maxTableSize); + + bool decodeHeaderFields(class BitIStream &inputStream); + + const HttpHeader &decodedHeader() const + { + return header; + } + + quint32 dynamicTableSize() const; + + void setMaxDynamicTableSize(quint32 size); + +private: + + bool decodeIndexedField(BitIStream &inputStream); + bool decodeSizeUpdate(BitIStream &inputStream); + bool decodeLiteralField(const BitPattern &fieldType, + BitIStream &inputStream); + + bool processDecodedField(const BitPattern &fieldType, + const QByteArray &name, + const QByteArray &value); + + void handleStreamError(BitIStream &inputStream); + + HttpHeader header; + FieldLookupTable lookupTable; +}; + +} + +QT_END_NAMESPACE + +#endif + diff --git a/src/network/access/http2/hpacktable.cpp b/src/network/access/http2/hpacktable.cpp new file mode 100644 index 0000000000..db9574e2bc --- /dev/null +++ b/src/network/access/http2/hpacktable.cpp @@ -0,0 +1,533 @@ +/**************************************************************************** +** +** Copyright (C) 2016 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtNetwork module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include "hpacktable_p.h" + +#include + +#include +#include +#include + + +QT_BEGIN_NAMESPACE + +namespace HPack +{ + +HeaderSize entry_size(const QByteArray &name, const QByteArray &value) +{ + // 32 comes from HPACK: + // "4.1 Calculating Table Size + // Note: The additional 32 octets account for an estimated overhead associated + // with an entry. For example, an entry structure using two 64-bit pointers + // to reference the name and the value of the entry and two 64-bit integers + // for counting the number of references to the name and value would have + // 32 octets of overhead." + + const unsigned sum = unsigned(name.size()) + value.size(); + if (std::numeric_limits::max() - 32 < sum) + return HeaderSize(); + if (sum + 32 > std::numeric_limits::max()) + return HeaderSize(); + return HeaderSize(true, quint32(sum + 32)); +} + +namespace +{ + +int compare(const QByteArray &lhs, const QByteArray &rhs) +{ + if (const int minLen = std::min(lhs.size(), rhs.size())) { + // We use memcmp, since strings in headers are allowed + // to contain '\0'. + const int cmp = std::memcmp(lhs.constData(), rhs.constData(), minLen); + if (cmp) + return cmp; + } + + return lhs.size() - rhs.size(); +} + +} // unnamed namespace + +FieldLookupTable::SearchEntry::SearchEntry() + : field(), + chunk(), + offset(), + table() +{ +} + +FieldLookupTable::SearchEntry::SearchEntry(const HeaderField *f, + const Chunk *c, + quint32 o, + const FieldLookupTable *t) + : field(f), + chunk(c), + offset(o), + table(t) +{ + Q_ASSERT(field); +} + +bool FieldLookupTable::SearchEntry::operator < (const SearchEntry &rhs)const +{ + Q_ASSERT(field); + Q_ASSERT(rhs.field); + + int cmp = compare(field->name, rhs.field->name); + if (cmp) + return cmp < 0; + + cmp = compare(field->value, rhs.field->value); + if (cmp) + return cmp < 0; + + if (!chunk) // 'this' is not in the searchIndex. + return rhs.chunk; + + if (!rhs.chunk) // not in the searchIndex. + return false; + + Q_ASSERT(table); + Q_ASSERT(rhs.table == table); + + const quint32 leftChunkIndex = table->indexOfChunk(chunk); + const quint32 rightChunkIndex = rhs.table->indexOfChunk(rhs.chunk); + + // Later added - smaller is chunk index (since we push_front). + if (leftChunkIndex != rightChunkIndex) + return leftChunkIndex > rightChunkIndex; + + // Later added - smaller is offset. + return offset > rhs.offset; +} + +// This data is from HPACK's specs and it's quite +// conveniently sorted == works with binary search as it is. +// Later this can probably change and instead of simple +// vector we'll just reuse FieldLookupTable. +// TODO: it makes sense to generate this table while ... +// configuring/building Qt (some script downloading/parsing/generating +// would be quite handy). +const std::vector &staticTable() +{ + static std::vector table = { + {":authority", ""}, + {":method", "GET"}, + {":method", "POST"}, + {":path", "/"}, + {":path", "/index.html"}, + {":scheme", "http"}, + {":scheme", "https"}, + {":status", "200"}, + {":status", "204"}, + {":status", "206"}, + {":status", "304"}, + {":status", "400"}, + {":status", "404"}, + {":status", "500"}, + {"accept-charset", ""}, + {"accept-encoding", "gzip, deflate"}, + {"accept-language", ""}, + {"accept-ranges", ""}, + {"accept", ""}, + {"access-control-allow-origin", ""}, + {"age", ""}, + {"allow", ""}, + {"authorization", ""}, + {"cache-control", ""}, + {"content-disposition", ""}, + {"content-encoding", ""}, + {"content-language", ""}, + {"content-length", ""}, + {"content-location", ""}, + {"content-range", ""}, + {"content-type", ""}, + {"cookie", ""}, + {"date", ""}, + {"etag", ""}, + {"expect", ""}, + {"expires", ""}, + {"from", ""}, + {"host", ""}, + {"if-match", ""}, + {"if-modified-since", ""}, + {"if-none-match", ""}, + {"if-range", ""}, + {"if-unmodified-since", ""}, + {"last-modified", ""}, + {"link", ""}, + {"location", ""}, + {"max-forwards", ""}, + {"proxy-authenticate", ""}, + {"proxy-authorization", ""}, + {"range", ""}, + {"referer", ""}, + {"refresh", ""}, + {"retry-after", ""}, + {"server", ""}, + {"set-cookie", ""}, + {"strict-transport-security", ""}, + {"transfer-encoding", ""}, + {"user-agent", ""}, + {"vary", ""}, + {"via", ""}, + {"www-authenticate", ""} + }; + + return table; +} + +FieldLookupTable::FieldLookupTable(quint32 maxSize, bool use) + : maxTableSize(maxSize), + tableCapacity(maxSize), + useIndex(use), + nDynamic(), + begin(), + end(), + dataSize() +{ +} + + +bool FieldLookupTable::prependField(const QByteArray &name, const QByteArray &value) +{ + const auto entrySize = entry_size(name, value); + if (!entrySize.first) + return false; + + if (entrySize.second > tableCapacity) { + clearDynamicTable(); + return true; + } + + while (nDynamic && tableCapacity - dataSize < entrySize.second) + evictEntry(); + + if (!begin) { + // Either no more space or empty table ... + chunks.push_front(ChunkPtr(new Chunk(ChunkSize))); + end += ChunkSize; + begin = ChunkSize; + } + + --begin; + + dataSize += entrySize.second; + ++nDynamic; + + auto &newField = front(); + newField.name = name; + newField.value = value; + + if (useIndex) { + const auto result = searchIndex.insert(frontKey()); + Q_UNUSED(result) Q_ASSERT(result.second); + } + + return true; +} + +void FieldLookupTable::evictEntry() +{ + if (!nDynamic) + return; + + Q_ASSERT(end != begin); + + if (useIndex) { + const auto res = searchIndex.erase(backKey()); + Q_UNUSED(res) Q_ASSERT(res == 1); + } + + const HeaderField &field = back(); + const auto entrySize = entry_size(field); + Q_ASSERT(entrySize.first); + Q_ASSERT(dataSize >= entrySize.second); + dataSize -= entrySize.second; + + --nDynamic; + --end; + + if (end == begin) { + Q_ASSERT(chunks.size() == 1); + end = ChunkSize; + begin = end; + } else if (!(end % ChunkSize)) { + chunks.pop_back(); + } +} + +quint32 FieldLookupTable::numberOfEntries() const +{ + return quint32(staticTable().size()) + nDynamic; +} + +quint32 FieldLookupTable::numberOfStaticEntries() const +{ + return quint32(staticTable().size()); +} + +quint32 FieldLookupTable::numberOfDynamicEntries() const +{ + return nDynamic; +} + +quint32 FieldLookupTable::dynamicDataSize() const +{ + return dataSize; +} + +void FieldLookupTable::clearDynamicTable() +{ + searchIndex.clear(); + chunks.clear(); + begin = 0; + end = 0; + nDynamic = 0; + dataSize = 0; +} + +bool FieldLookupTable::indexIsValid(quint32 index) const +{ + return index && index <= staticTable().size() + nDynamic; +} + +quint32 FieldLookupTable::indexOf(const QByteArray &name, const QByteArray &value)const +{ + // Start from the static part first: + const auto &table = staticTable(); + const HeaderField field(name, value); + const auto staticPos = std::lower_bound(table.begin(), table.end(), field, + [](const HeaderField &lhs, const HeaderField &rhs) { + int cmp = compare(lhs.name, rhs.name); + if (cmp) + return cmp < 0; + return compare(lhs.value, rhs.value) < 0; + }); + if (staticPos != table.end()) { + if (staticPos->name == name && staticPos->value == value) + return staticPos - table.begin() + 1; + } + + // Now we have to lookup in our dynamic part ... + if (!useIndex) { + qCritical("lookup in dynamic table requires search index enabled"); + return 0; + } + + const SearchEntry key(&field, nullptr, 0, this); + const auto pos = searchIndex.lower_bound(key); + if (pos != searchIndex.end()) { + const HeaderField &found = *pos->field; + if (found.name == name && found.value == value) + return keyToIndex(*pos); + } + + return 0; +} + +quint32 FieldLookupTable::indexOf(const QByteArray &name) const +{ + // Start from the static part first: + const auto &table = staticTable(); + const HeaderField field(name, QByteArray()); + const auto staticPos = std::lower_bound(table.begin(), table.end(), field, + [](const HeaderField &lhs, const HeaderField &rhs) { + return compare(lhs.name, rhs.name) < 0; + }); + if (staticPos != table.end()) { + if (staticPos->name == name) + return staticPos - table.begin() + 1; + } + + // Now we have to lookup in our dynamic part ... + if (!useIndex) { + qCritical("lookup in dynamic table requires search index enabled"); + return 0; + } + + const SearchEntry key(&field, nullptr, 0, this); + const auto pos = searchIndex.lower_bound(key); + if (pos != searchIndex.end()) { + const HeaderField &found = *pos->field; + if (found.name == name) + return keyToIndex(*pos); + } + + return 0; +} + +bool FieldLookupTable::field(quint32 index, QByteArray *name, QByteArray *value) const +{ + Q_ASSERT(name); + Q_ASSERT(value); + + if (!indexIsValid(index)) + return false; + + const auto &table = staticTable(); + if (index - 1 < table.size()) { + *name = table[index - 1].name; + *value = table[index - 1].value; + return true; + } + + index = index - 1 - quint32(table.size()) + begin; + const auto chunkIndex = index / ChunkSize; + Q_ASSERT(chunkIndex < chunks.size()); + const auto offset = index % ChunkSize; + const HeaderField &found = (*chunks[chunkIndex])[offset]; + *name = found.name; + *value = found.value; + + return true; +} + +bool FieldLookupTable::fieldName(quint32 index, QByteArray *dst) const +{ + Q_ASSERT(dst); + return field(index, dst, &dummyDst); +} + +bool FieldLookupTable::fieldValue(quint32 index, QByteArray *dst) const +{ + Q_ASSERT(dst); + return field(index, &dummyDst, dst); +} + +const HeaderField &FieldLookupTable::front() const +{ + Q_ASSERT(nDynamic && begin != end && chunks.size()); + return (*chunks[0])[begin]; +} + +HeaderField &FieldLookupTable::front() +{ + Q_ASSERT(nDynamic && begin != end && chunks.size()); + return (*chunks[0])[begin]; +} + +const HeaderField &FieldLookupTable::back() const +{ + Q_ASSERT(nDynamic && end && end != begin); + + const quint32 absIndex = end - 1; + const quint32 chunkIndex = absIndex / ChunkSize; + Q_ASSERT(chunkIndex < chunks.size()); + const quint32 offset = absIndex % ChunkSize; + return (*chunks[chunkIndex])[offset]; +} + +quint32 FieldLookupTable::indexOfChunk(const Chunk *chunk) const +{ + Q_ASSERT(chunk); + + for (size_type i = 0; i < chunks.size(); ++i) { + if (chunks[i].get() == chunk) + return quint32(i); + } + + Q_UNREACHABLE(); + return 0; +} + +quint32 FieldLookupTable::keyToIndex(const SearchEntry &key) const +{ + Q_ASSERT(key.chunk); + + const auto chunkIndex = indexOfChunk(key.chunk); + const auto offset = key.offset; + Q_ASSERT(offset < ChunkSize); + Q_ASSERT(chunkIndex || offset >= begin); + + return quint32(offset + chunkIndex * ChunkSize - begin + 1 + staticTable().size()); +} + +FieldLookupTable::SearchEntry FieldLookupTable::frontKey() const +{ + Q_ASSERT(chunks.size() && end != begin); + return SearchEntry(&front(), chunks.front().get(), begin, this); +} + +FieldLookupTable::SearchEntry FieldLookupTable::backKey() const +{ + Q_ASSERT(chunks.size() && end != begin); + + const HeaderField &field = back(); + const quint32 absIndex = end - 1; + const auto offset = absIndex % ChunkSize; + const auto chunk = chunks[absIndex / ChunkSize].get(); + + return SearchEntry(&field, chunk, offset, this); +} + +bool FieldLookupTable::updateDynamicTableSize(quint32 size) +{ + if (!size) { + clearDynamicTable(); + return true; + } + + if (size > maxTableSize) + return false; + + tableCapacity = size; + while (nDynamic && dataSize > tableCapacity) + evictEntry(); + + return true; +} + +void FieldLookupTable::setMaxDynamicTableSize(quint32 size) +{ + // This is for an external user, for example, HTTP2 protocol + // layer that can receive SETTINGS frame from its peer. + // No validity checks here, up to this external user. + // We update max size and capacity (this can also result in + // items evicted or even dynamic table completely cleared). + maxTableSize = size; + updateDynamicTableSize(size); +} + +} + +QT_END_NAMESPACE diff --git a/src/network/access/http2/hpacktable_p.h b/src/network/access/http2/hpacktable_p.h new file mode 100644 index 0000000000..aaea89b986 --- /dev/null +++ b/src/network/access/http2/hpacktable_p.h @@ -0,0 +1,237 @@ +/**************************************************************************** +** +** Copyright (C) 2016 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtNetwork module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef HPACKTABLE_P_H +#define HPACKTABLE_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists for the convenience +// of other Qt classes. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include +#include +#include + +#include +#include +#include +#include + +QT_BEGIN_NAMESPACE + +namespace HPack +{ + +struct Q_AUTOTEST_EXPORT HeaderField +{ + HeaderField() + { + } + + HeaderField(const QByteArray &n, const QByteArray &v) + : name(n), + value(v) + { + } + + bool operator == (const HeaderField &rhs) const + { + return name == rhs.name && value == rhs.value; + } + + QByteArray name; + QByteArray value; +}; + +using HeaderSize = QPair; + +HeaderSize entry_size(const QByteArray &name, const QByteArray &value); + +inline HeaderSize entry_size(const HeaderField &entry) +{ + return entry_size(entry.name, entry.value); +} + +/* + Lookup table consists of two parts (HPACK, 2.3): + the immutable static table (pre-defined by HPACK's specs) + and dynamic table which is updated while + compressing/decompressing headers. + + Table must provide/implement: + 1. Fast random access - we read fields' indices from + HPACK's bit stream. + 2. FIFO for dynamic part - to push new items to the front + and evict them from the back (HPACK, 2.3.2). + 3. Fast lookup - encoder receives pairs of strings + (name|value) and it has to find an index for a pair + as the whole or for a name at least (if it's already + in either static or dynamic table). + + Static table is an immutable vector. + + Dynamic part is implemented in a way similar to std::deque - + it's a vector of pointers to chunks. Each chunk is a vector of + (name|value) pairs. Once allocated with a fixed size, chunk + never re-allocates its data, so entries' addresses do not change. + We add new chunks prepending them to the front of a vector, + in each chunk we fill (name|value) pairs starting from the back + of the chunk (this simplifies item eviction/FIFO). + Given a 'linear' index we can find a chunk number and + offset in this chunk - random access. + + Lookup in a static part is straightforward: + it's an (immutable) vector, data is sorted, + contains no duplicates, we use binary search comparing string values. + + To provide a lookup in dynamic table faster than a linear search, + we have an std::set of 'SearchEntries', where each entry contains: + - a pointer to a (name|value) pair (to compare + name|value strings). + - a pointer to a chunk containing this pair and + - an offset within this chunk - to calculate a + 'linear' index. + + Entries in a table can be duplicated (HPACK, 2.3.2), + if we evict an entry, we must update our index removing + the exactly right key, thus keys in this set are sorted + by name|value pairs first, and then by chunk index/offset + (so that NewSearchEntryKey < OldSearchEntry even if strings + are equal). +*/ + +class Q_AUTOTEST_EXPORT FieldLookupTable +{ +public: + enum + { + ChunkSize = 16, + DefaultSize = 4096 // Recommended by HTTP2. + }; + + FieldLookupTable(quint32 maxTableSize, bool useIndex); + + bool prependField(const QByteArray &name, const QByteArray &value); + void evictEntry(); + + quint32 numberOfEntries() const; + quint32 numberOfStaticEntries() const; + quint32 numberOfDynamicEntries() const; + quint32 dynamicDataSize() const; + void clearDynamicTable(); + + bool indexIsValid(quint32 index) const; + quint32 indexOf(const QByteArray &name, const QByteArray &value) const; + quint32 indexOf(const QByteArray &name) const; + bool field(quint32 index, QByteArray *name, QByteArray *value) const; + bool fieldName(quint32 index, QByteArray *dst) const; + bool fieldValue(quint32 index, QByteArray *dst) const; + + bool updateDynamicTableSize(quint32 size); + void setMaxDynamicTableSize(quint32 size); + +private: + // Table's maximum size is controlled + // by SETTINGS_HEADER_TABLE_SIZE (HTTP/2, 6.5.2). + quint32 maxTableSize; + // The tableCapacity is how many bytes the table + // can currently hold. It cannot exceed maxTableSize. + // It can be modified by a special message in + // the HPACK bit stream (HPACK, 6.3). + quint32 tableCapacity; + + using Chunk = std::vector; + using ChunkPtr = std::unique_ptr; + std::deque chunks; + using size_type = std::deque::size_type; + + struct SearchEntry; + friend struct SearchEntry; + + struct SearchEntry + { + SearchEntry(); + SearchEntry(const HeaderField *f, const Chunk *c, + quint32 o, const FieldLookupTable *t); + + const HeaderField *field; + const Chunk *chunk; + const quint32 offset; + const FieldLookupTable *table; + + bool operator < (const SearchEntry &rhs) const; + }; + + bool useIndex; + std::set searchIndex; + + SearchEntry frontKey() const; + SearchEntry backKey() const; + + bool fieldAt(quint32 index, HeaderField *field) const; + + const HeaderField &front() const; + HeaderField &front(); + const HeaderField &back() const; + + quint32 nDynamic; + quint32 begin; + quint32 end; + quint32 dataSize; + + quint32 indexOfChunk(const Chunk *chunk) const; + quint32 keyToIndex(const SearchEntry &key) const; + + mutable QByteArray dummyDst; + + Q_DISABLE_COPY(FieldLookupTable); +}; + +} + +QT_END_NAMESPACE + +#endif diff --git a/src/network/access/http2/http2.pri b/src/network/access/http2/http2.pri new file mode 100644 index 0000000000..2157e35e2f --- /dev/null +++ b/src/network/access/http2/http2.pri @@ -0,0 +1,11 @@ +HEADERS += \ + access/http2/bitstreams_p.h \ + access/http2/huffman_p.h \ + access/http2/hpack_p.h \ + access/http2/hpacktable_p.h + +SOURCES += \ + access/http2/bitstreams.cpp \ + access/http2/huffman.cpp \ + access/http2/hpack.cpp \ + access/http2/hpacktable.cpp diff --git a/src/network/access/http2/huffman.cpp b/src/network/access/http2/huffman.cpp new file mode 100644 index 0000000000..0c1aa54dd6 --- /dev/null +++ b/src/network/access/http2/huffman.cpp @@ -0,0 +1,573 @@ +/**************************************************************************** +** +** Copyright (C) 2016 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtNetwork module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include "bitstreams_p.h" +#include "huffman_p.h" + +#include + +#include +#include + +QT_BEGIN_NAMESPACE + +namespace HPack +{ + +/* + The static Huffman code used here was extracted from: + https://http2.github.io/http2-spec/compression.html#huffman.code + + This code was generated from statistics obtained on a large + sample of HTTP headers. It is a canonical Huffman code + with some tweaking to ensure that no symbol has a unique + code length. All codes were left-aligned - for implementation + convenience. + + Using binary trees to implement decoding would be prohibitively + expensive (both memory and time-wise). Instead we use a table-based + approach and any given code itself works as an index into such table(s). + We have 256 possible byte values and code lengths in + a range [5, 26]. This would require a huge table (and most of entries + would be 'wasted', since we only have to encode 256 elements). + Instead we use multi-level tables. The first level table + is using 9-bit length index; some entries in this table are 'terminal', + some reference the next level table(s). + + For example, bytes with values 48 and 49 (ASCII codes for '0' and '1') + both have code length 5, Huffman codes are: 00000 and 00001. They + both are placed in the 'root' table, + the 'root' table has index length == 9: + [00000 | 4 remaining bits] + ... + [00001 | 4 remaining bits] + + All entires with indices between these two will 'point' to value 48 + with bitLength == 5 so that bit stream (for example) 000001010 will be + decoded as: 48 + "put 1010 back into bitstream". + + A good description can be found here: + http://commandlinefanatic.com/cgi-bin/showarticle.cgi?article=art007 + or just google "Efficient Huffman Decoding". + Also see comments below about 'filling holes'. +*/ + +namespace +{ + +const CodeEntry staticHuffmanCodeTable[] +{ + { 0, 0xffc00000ul, 13}, // 11111111|11000 + { 1, 0xffffb000ul, 23}, // 11111111|11111111|1011000 + { 2, 0xfffffe20ul, 28}, // 11111111|11111111|11111110|0010 + { 3, 0xfffffe30ul, 28}, // 11111111|11111111|11111110|0011 + { 4, 0xfffffe40ul, 28}, // 11111111|11111111|11111110|0100 + { 5, 0xfffffe50ul, 28}, // 11111111|11111111|11111110|0101 + { 6, 0xfffffe60ul, 28}, // 11111111|11111111|11111110|0110 + { 7, 0xfffffe70ul, 28}, // 11111111|11111111|11111110|0111 + { 8, 0xfffffe80ul, 28}, // 11111111|11111111|11111110|1000 + { 9, 0xffffea00ul, 24}, // 11111111|11111111|11101010 + { 10, 0xfffffff0ul, 30}, // 11111111|11111111|11111111|111100 + { 11, 0xfffffe90ul, 28}, // 11111111|11111111|11111110|1001 + { 12, 0xfffffea0ul, 28}, // 11111111|11111111|11111110|1010 + { 13, 0xfffffff4ul, 30}, // 11111111|11111111|11111111|111101 + { 14, 0xfffffeb0ul, 28}, // 11111111|11111111|11111110|1011 + { 15, 0xfffffec0ul, 28}, // 11111111|11111111|11111110|1100 + { 16, 0xfffffed0ul, 28}, // 11111111|11111111|11111110|1101 + { 17, 0xfffffee0ul, 28}, // 11111111|11111111|11111110|1110 + { 18, 0xfffffef0ul, 28}, // 11111111|11111111|11111110|1111 + { 19, 0xffffff00ul, 28}, // 11111111|11111111|11111111|0000 + { 20, 0xffffff10ul, 28}, // 11111111|11111111|11111111|0001 + { 21, 0xffffff20ul, 28}, // 11111111|11111111|11111111|0010 + { 22, 0xfffffff8ul, 30}, // 11111111|11111111|11111111|111110 + { 23, 0xffffff30ul, 28}, // 11111111|11111111|11111111|0011 + { 24, 0xffffff40ul, 28}, // 11111111|11111111|11111111|0100 + { 25, 0xffffff50ul, 28}, // 11111111|11111111|11111111|0101 + { 26, 0xffffff60ul, 28}, // 11111111|11111111|11111111|0110 + { 27, 0xffffff70ul, 28}, // 11111111|11111111|11111111|0111 + { 28, 0xffffff80ul, 28}, // 11111111|11111111|11111111|1000 + { 29, 0xffffff90ul, 28}, // 11111111|11111111|11111111|1001 + { 30, 0xffffffa0ul, 28}, // 11111111|11111111|11111111|1010 + { 31, 0xffffffb0ul, 28}, // 11111111|11111111|11111111|1011 + { 32, 0x50000000ul, 6}, // ' ' 010100 + { 33, 0xfe000000ul, 10}, // '!' 11111110|00 + { 34, 0xfe400000ul, 10}, // '"' 11111110|01 + { 35, 0xffa00000ul, 12}, // '#' 11111111|1010 + { 36, 0xffc80000ul, 13}, // '$' 11111111|11001 + { 37, 0x54000000ul, 6}, // '%' 010101 + { 38, 0xf8000000ul, 8}, // '&' 11111000 + { 39, 0xff400000ul, 11}, // ''' 11111111|010 + { 40, 0xfe800000ul, 10}, // '(' 11111110|10 + { 41, 0xfec00000ul, 10}, // ')' 11111110|11 + { 42, 0xf9000000ul, 8}, // '*' 11111001 + { 43, 0xff600000ul, 11}, // '+' 11111111|011 + { 44, 0xfa000000ul, 8}, // ',' 11111010 + { 45, 0x58000000ul, 6}, // '-' 010110 + { 46, 0x5c000000ul, 6}, // '.' 010111 + { 47, 0x60000000ul, 6}, // '/' 011000 + { 48, 0x00000000ul, 5}, // '0' 00000 + { 49, 0x08000000ul, 5}, // '1' 00001 + { 50, 0x10000000ul, 5}, // '2' 00010 + { 51, 0x64000000ul, 6}, // '3' 011001 + { 52, 0x68000000ul, 6}, // '4' 011010 + { 53, 0x6c000000ul, 6}, // '5' 011011 + { 54, 0x70000000ul, 6}, // '6' 011100 + { 55, 0x74000000ul, 6}, // '7' 011101 + { 56, 0x78000000ul, 6}, // '8' 011110 + { 57, 0x7c000000ul, 6}, // '9' 011111 + { 58, 0xb8000000ul, 7}, // ':' 1011100 + { 59, 0xfb000000ul, 8}, // ';' 11111011 + { 60, 0xfff80000ul, 15}, // '<' 11111111|1111100 + { 61, 0x80000000ul, 6}, // '=' 100000 + { 62, 0xffb00000ul, 12}, // '>' 11111111|1011 + { 63, 0xff000000ul, 10}, // '?' 11111111|00 + { 64, 0xffd00000ul, 13}, // '@' 11111111|11010 + { 65, 0x84000000ul, 6}, // 'A' 100001 + { 66, 0xba000000ul, 7}, // 'B' 1011101 + { 67, 0xbc000000ul, 7}, // 'C' 1011110 + { 68, 0xbe000000ul, 7}, // 'D' 1011111 + { 69, 0xc0000000ul, 7}, // 'E' 1100000 + { 70, 0xc2000000ul, 7}, // 'F' 1100001 + { 71, 0xc4000000ul, 7}, // 'G' 1100010 + { 72, 0xc6000000ul, 7}, // 'H' 1100011 + { 73, 0xc8000000ul, 7}, // 'I' 1100100 + { 74, 0xca000000ul, 7}, // 'J' 1100101 + { 75, 0xcc000000ul, 7}, // 'K' 1100110 + { 76, 0xce000000ul, 7}, // 'L' 1100111 + { 77, 0xd0000000ul, 7}, // 'M' 1101000 + { 78, 0xd2000000ul, 7}, // 'N' 1101001 + { 79, 0xd4000000ul, 7}, // 'O' 1101010 + { 80, 0xd6000000ul, 7}, // 'P' 1101011 + { 81, 0xd8000000ul, 7}, // 'Q' 1101100 + { 82, 0xda000000ul, 7}, // 'R' 1101101 + { 83, 0xdc000000ul, 7}, // 'S' 1101110 + { 84, 0xde000000ul, 7}, // 'T' 1101111 + { 85, 0xe0000000ul, 7}, // 'U' 1110000 + { 86, 0xe2000000ul, 7}, // 'V' 1110001 + { 87, 0xe4000000ul, 7}, // 'W' 1110010 + { 88, 0xfc000000ul, 8}, // 'X' 11111100 + { 89, 0xe6000000ul, 7}, // 'Y' 1110011 + { 90, 0xfd000000ul, 8}, // 'Z' 11111101 + { 91, 0xffd80000ul, 13}, // '[' 11111111|11011 + { 92, 0xfffe0000ul, 19}, // '\' 11111111|11111110|000 + { 93, 0xffe00000ul, 13}, // ']' 11111111|11100 + { 94, 0xfff00000ul, 14}, // '^' 11111111|111100 + { 95, 0x88000000ul, 6}, // '_' 100010 + { 96, 0xfffa0000ul, 15}, // '`' 11111111|1111101 + { 97, 0x18000000ul, 5}, // 'a' 00011 + { 98, 0x8c000000ul, 6}, // 'b' 100011 + { 99, 0x20000000ul, 5}, // 'c' 00100 + {100, 0x90000000ul, 6}, // 'd' 100100 + {101, 0x28000000ul, 5}, // 'e' 00101 + {102, 0x94000000ul, 6}, // 'f' 100101 + {103, 0x98000000ul, 6}, // 'g' 100110 + {104, 0x9c000000ul, 6}, // 'h' 100111 + {105, 0x30000000ul, 5}, // 'i' 00110 + {106, 0xe8000000ul, 7}, // 'j' 1110100 + {107, 0xea000000ul, 7}, // 'k' 1110101 + {108, 0xa0000000ul, 6}, // 'l' 101000 + {109, 0xa4000000ul, 6}, // 'm' 101001 + {110, 0xa8000000ul, 6}, // 'n' 101010 + {111, 0x38000000ul, 5}, // 'o' 00111 + {112, 0xac000000ul, 6}, // 'p' 101011 + {113, 0xec000000ul, 7}, // 'q' 1110110 + {114, 0xb0000000ul, 6}, // 'r' 101100 + {115, 0x40000000ul, 5}, // 's' 01000 + {116, 0x48000000ul, 5}, // 't' 01001 + {117, 0xb4000000ul, 6}, // 'u' 101101 + {118, 0xee000000ul, 7}, // 'v' 1110111 + {119, 0xf0000000ul, 7}, // 'w' 1111000 + {120, 0xf2000000ul, 7}, // 'x' 1111001 + {121, 0xf4000000ul, 7}, // 'y' 1111010 + {122, 0xf6000000ul, 7}, // 'z' 1111011 + {123, 0xfffc0000ul, 15}, // '{' 11111111|1111110 + {124, 0xff800000ul, 11}, // '|' 11111111|100 + {125, 0xfff40000ul, 14}, // '}' 11111111|111101 + {126, 0xffe80000ul, 13}, // '~' 11111111|11101 + {127, 0xffffffc0ul, 28}, // 11111111|11111111|11111111|1100 + {128, 0xfffe6000ul, 20}, // 11111111|11111110|0110 + {129, 0xffff4800ul, 22}, // 11111111|11111111|010010 + {130, 0xfffe7000ul, 20}, // 11111111|11111110|0111 + {131, 0xfffe8000ul, 20}, // 11111111|11111110|1000 + {132, 0xffff4c00ul, 22}, // 11111111|11111111|010011 + {133, 0xffff5000ul, 22}, // 11111111|11111111|010100 + {134, 0xffff5400ul, 22}, // 11111111|11111111|010101 + {135, 0xffffb200ul, 23}, // 11111111|11111111|1011001 + {136, 0xffff5800ul, 22}, // 11111111|11111111|010110 + {137, 0xffffb400ul, 23}, // 11111111|11111111|1011010 + {138, 0xffffb600ul, 23}, // 11111111|11111111|1011011 + {139, 0xffffb800ul, 23}, // 11111111|11111111|1011100 + {140, 0xffffba00ul, 23}, // 11111111|11111111|1011101 + {141, 0xffffbc00ul, 23}, // 11111111|11111111|1011110 + {142, 0xffffeb00ul, 24}, // 11111111|11111111|11101011 + {143, 0xffffbe00ul, 23}, // 11111111|11111111|1011111 + {144, 0xffffec00ul, 24}, // 11111111|11111111|11101100 + {145, 0xffffed00ul, 24}, // 11111111|11111111|11101101 + {146, 0xffff5c00ul, 22}, // 11111111|11111111|010111 + {147, 0xffffc000ul, 23}, // 11111111|11111111|1100000 + {148, 0xffffee00ul, 24}, // 11111111|11111111|11101110 + {149, 0xffffc200ul, 23}, // 11111111|11111111|1100001 + {150, 0xffffc400ul, 23}, // 11111111|11111111|1100010 + {151, 0xffffc600ul, 23}, // 11111111|11111111|1100011 + {152, 0xffffc800ul, 23}, // 11111111|11111111|1100100 + {153, 0xfffee000ul, 21}, // 11111111|11111110|11100 + {154, 0xffff6000ul, 22}, // 11111111|11111111|011000 + {155, 0xffffca00ul, 23}, // 11111111|11111111|1100101 + {156, 0xffff6400ul, 22}, // 11111111|11111111|011001 + {157, 0xffffcc00ul, 23}, // 11111111|11111111|1100110 + {158, 0xffffce00ul, 23}, // 11111111|11111111|1100111 + {159, 0xffffef00ul, 24}, // 11111111|11111111|11101111 + {160, 0xffff6800ul, 22}, // 11111111|11111111|011010 + {161, 0xfffee800ul, 21}, // 11111111|11111110|11101 + {162, 0xfffe9000ul, 20}, // 11111111|11111110|1001 + {163, 0xffff6c00ul, 22}, // 11111111|11111111|011011 + {164, 0xffff7000ul, 22}, // 11111111|11111111|011100 + {165, 0xffffd000ul, 23}, // 11111111|11111111|1101000 + {166, 0xffffd200ul, 23}, // 11111111|11111111|1101001 + {167, 0xfffef000ul, 21}, // 11111111|11111110|11110 + {168, 0xffffd400ul, 23}, // 11111111|11111111|1101010 + {169, 0xffff7400ul, 22}, // 11111111|11111111|011101 + {170, 0xffff7800ul, 22}, // 11111111|11111111|011110 + {171, 0xfffff000ul, 24}, // 11111111|11111111|11110000 + {172, 0xfffef800ul, 21}, // 11111111|11111110|11111 + {173, 0xffff7c00ul, 22}, // 11111111|11111111|011111 + {174, 0xffffd600ul, 23}, // 11111111|11111111|1101011 + {175, 0xffffd800ul, 23}, // 11111111|11111111|1101100 + {176, 0xffff0000ul, 21}, // 11111111|11111111|00000 + {177, 0xffff0800ul, 21}, // 11111111|11111111|00001 + {178, 0xffff8000ul, 22}, // 11111111|11111111|100000 + {179, 0xffff1000ul, 21}, // 11111111|11111111|00010 + {180, 0xffffda00ul, 23}, // 11111111|11111111|1101101 + {181, 0xffff8400ul, 22}, // 11111111|11111111|100001 + {182, 0xffffdc00ul, 23}, // 11111111|11111111|1101110 + {183, 0xffffde00ul, 23}, // 11111111|11111111|1101111 + {184, 0xfffea000ul, 20}, // 11111111|11111110|1010 + {185, 0xffff8800ul, 22}, // 11111111|11111111|100010 + {186, 0xffff8c00ul, 22}, // 11111111|11111111|100011 + {187, 0xffff9000ul, 22}, // 11111111|11111111|100100 + {188, 0xffffe000ul, 23}, // 11111111|11111111|1110000 + {189, 0xffff9400ul, 22}, // 11111111|11111111|100101 + {190, 0xffff9800ul, 22}, // 11111111|11111111|100110 + {191, 0xffffe200ul, 23}, // 11111111|11111111|1110001 + {192, 0xfffff800ul, 26}, // 11111111|11111111|11111000|00 + {193, 0xfffff840ul, 26}, // 11111111|11111111|11111000|01 + {194, 0xfffeb000ul, 20}, // 11111111|11111110|1011 + {195, 0xfffe2000ul, 19}, // 11111111|11111110|001 + {196, 0xffff9c00ul, 22}, // 11111111|11111111|100111 + {197, 0xffffe400ul, 23}, // 11111111|11111111|1110010 + {198, 0xffffa000ul, 22}, // 11111111|11111111|101000 + {199, 0xfffff600ul, 25}, // 11111111|11111111|11110110|0 + {200, 0xfffff880ul, 26}, // 11111111|11111111|11111000|10 + {201, 0xfffff8c0ul, 26}, // 11111111|11111111|11111000|11 + {202, 0xfffff900ul, 26}, // 11111111|11111111|11111001|00 + {203, 0xfffffbc0ul, 27}, // 11111111|11111111|11111011|110 + {204, 0xfffffbe0ul, 27}, // 11111111|11111111|11111011|111 + {205, 0xfffff940ul, 26}, // 11111111|11111111|11111001|01 + {206, 0xfffff100ul, 24}, // 11111111|11111111|11110001 + {207, 0xfffff680ul, 25}, // 11111111|11111111|11110110|1 + {208, 0xfffe4000ul, 19}, // 11111111|11111110|010 + {209, 0xffff1800ul, 21}, // 11111111|11111111|00011 + {210, 0xfffff980ul, 26}, // 11111111|11111111|11111001|10 + {211, 0xfffffc00ul, 27}, // 11111111|11111111|11111100|000 + {212, 0xfffffc20ul, 27}, // 11111111|11111111|11111100|001 + {213, 0xfffff9c0ul, 26}, // 11111111|11111111|11111001|11 + {214, 0xfffffc40ul, 27}, // 11111111|11111111|11111100|010 + {215, 0xfffff200ul, 24}, // 11111111|11111111|11110010 + {216, 0xffff2000ul, 21}, // 11111111|11111111|00100 + {217, 0xffff2800ul, 21}, // 11111111|11111111|00101 + {218, 0xfffffa00ul, 26}, // 11111111|11111111|11111010|00 + {219, 0xfffffa40ul, 26}, // 11111111|11111111|11111010|01 + {220, 0xffffffd0ul, 28}, // 11111111|11111111|11111111|1101 + {221, 0xfffffc60ul, 27}, // 11111111|11111111|11111100|011 + {222, 0xfffffc80ul, 27}, // 11111111|11111111|11111100|100 + {223, 0xfffffca0ul, 27}, // 11111111|11111111|11111100|101 + {224, 0xfffec000ul, 20}, // 11111111|11111110|1100 + {225, 0xfffff300ul, 24}, // 11111111|11111111|11110011 + {226, 0xfffed000ul, 20}, // 11111111|11111110|1101 + {227, 0xffff3000ul, 21}, // 11111111|11111111|00110 + {228, 0xffffa400ul, 22}, // 11111111|11111111|101001 + {229, 0xffff3800ul, 21}, // 11111111|11111111|00111 + {230, 0xffff4000ul, 21}, // 11111111|11111111|01000 + {231, 0xffffe600ul, 23}, // 11111111|11111111|1110011 + {232, 0xffffa800ul, 22}, // 11111111|11111111|101010 + {233, 0xffffac00ul, 22}, // 11111111|11111111|101011 + {234, 0xfffff700ul, 25}, // 11111111|11111111|11110111|0 + {235, 0xfffff780ul, 25}, // 11111111|11111111|11110111|1 + {236, 0xfffff400ul, 24}, // 11111111|11111111|11110100 + {237, 0xfffff500ul, 24}, // 11111111|11111111|11110101 + {238, 0xfffffa80ul, 26}, // 11111111|11111111|11111010|10 + {239, 0xffffe800ul, 23}, // 11111111|11111111|1110100 + {240, 0xfffffac0ul, 26}, // 11111111|11111111|11111010|11 + {241, 0xfffffcc0ul, 27}, // 11111111|11111111|11111100|110 + {242, 0xfffffb00ul, 26}, // 11111111|11111111|11111011|00 + {243, 0xfffffb40ul, 26}, // 11111111|11111111|11111011|01 + {244, 0xfffffce0ul, 27}, // 11111111|11111111|11111100|111 + {245, 0xfffffd00ul, 27}, // 11111111|11111111|11111101|000 + {246, 0xfffffd20ul, 27}, // 11111111|11111111|11111101|001 + {247, 0xfffffd40ul, 27}, // 11111111|11111111|11111101|010 + {248, 0xfffffd60ul, 27}, // 11111111|11111111|11111101|011 + {249, 0xffffffe0ul, 28}, // 11111111|11111111|11111111|1110 + {250, 0xfffffd80ul, 27}, // 11111111|11111111|11111101|100 + {251, 0xfffffda0ul, 27}, // 11111111|11111111|11111101|101 + {252, 0xfffffdc0ul, 27}, // 11111111|11111111|11111101|110 + {253, 0xfffffde0ul, 27}, // 11111111|11111111|11111101|111 + {254, 0xfffffe00ul, 27}, // 11111111|11111111|11111110|000 + {255, 0xfffffb80ul, 26}, // 11111111|11111111|11111011|10 + {256, 0xfffffffcul, 30} // EOS 11111111|11111111|11111111|111111 +}; + +void write_huffman_code(BitOStream &outputStream, const CodeEntry &code) +{ + // Append octet by octet. + auto bitLength = code.bitLength; + const auto hc = code.huffmanCode >> (32 - bitLength); + + if (bitLength > 24) { + outputStream.writeBits(uchar(hc >> 24), bitLength - 24); + bitLength = 24; + } + + if (bitLength > 16) { + outputStream.writeBits(uchar(hc >> 16), bitLength - 16); + bitLength = 16; + } + + if (bitLength > 8) { + outputStream.writeBits(uchar(hc >> 8), bitLength - 8); + bitLength = 8; + } + + outputStream.writeBits(uchar(hc), bitLength); +} + +} + +// That's from HPACK's specs - we deal with octets. +static_assert(std::numeric_limits::digits == 8, "octets expected"); + +quint64 huffman_encoded_bit_length(const QByteArray &inputData) +{ + quint64 bitLength = 0; + for (int i = 0, e = inputData.size(); i < e; ++i) + bitLength += staticHuffmanCodeTable[int(inputData[i])].bitLength; + + return bitLength; +} + +void huffman_encode_string(const QByteArray &inputData, BitOStream &outputStream) +{ + for (int i = 0, e = inputData.size(); i < e; ++i) + write_huffman_code(outputStream, staticHuffmanCodeTable[int(inputData[i])]); + + // Pad bits ... + if (outputStream.bitLength() % 8) + outputStream.writeBits(0xff, 8 - outputStream.bitLength() % 8); +} + +bool padding_is_valid(quint32 chunk, quint32 nBits) +{ + Q_ASSERT(nBits); + + // HPACK, 5.2: "A padding strictly longer than 7 bits MUST be + // treated as a decoding error." + if (nBits > 7) + return false; + // HPACK, 5.2: + // "A padding not corresponding to the most significant bits + // of the code for the EOS symbol MUST be treated as a decoding error." + return (chunk >> (32 - nBits)) == quint32((1 << nBits) - 1); +} + +HuffmanDecoder::HuffmanDecoder() + : minCodeLength() +{ + const auto nCodes = sizeof staticHuffmanCodeTable / sizeof staticHuffmanCodeTable[0]; + + std::vector symbols(staticHuffmanCodeTable, staticHuffmanCodeTable + nCodes); + // Now we sort: by bit length first (in the descending order) and by the symbol + // value (descending). Descending order: to make sure we do not create prefix tables with + // short 'indexLength' first and having longer codes that do not fit into such tables later. + std::sort(symbols.begin(), symbols.end(), [](const CodeEntry &code1, const CodeEntry &code2) { + if (code1.bitLength == code2.bitLength) + return code1.byteValue > code2.byteValue; + return code1.bitLength > code2.bitLength; + }); + + minCodeLength = symbols.back().bitLength; // The shortest one, currently it's 5. + + // TODO: add a verification - Huffman codes + // within a given bit length range also + // should be in descending order. + + // Initialize 'prefixTables' and 'tableData'. + addTable(0, quint32(BitConstants::rootPrefix)); // 'root' table. + + for (const auto &s : symbols) { + quint32 tableIndex = 0; + while (true) { + Q_ASSERT(tableIndex < prefixTables.size()); + // Note, by value - since prefixTables will be updated in between. + const auto table = prefixTables[tableIndex]; + // We skip prefixed bits (if any) and use indexed bits only: + const auto entryIndex = s.huffmanCode << table.prefixLength >> (32 - table.indexLength); + // Again, by value. + PrefixTableEntry entry = tableEntry(table, entryIndex); + // How many bits were coded by previous tables and this table: + const auto codedLength = table.prefixLength + table.indexLength; + if (codedLength < s.bitLength) { + // We have to add a new prefix table ... (if it's not done yet). + if (!entry.bitLength) { + entry.nextTable = addTable(codedLength, std::min(quint32(BitConstants::childPrefix), + s.bitLength - codedLength)); + entry.bitLength = s.bitLength; + entry.byteValue = s.byteValue; + setTableEntry(table, entryIndex, entry); + } + tableIndex = entry.nextTable; + } else { + // We found the slot for our code (terminal entry): + entry.byteValue = s.byteValue; + entry.bitLength = s.bitLength; + // Refer to our own table as 'nextTable': + entry.nextTable = tableIndex; + setTableEntry(table, entryIndex, entry); + break; + } + } + } + + // Now, we have a table(s) and have to fill 'holes' to + // 'fix' terminal entries. + for (const auto &table : prefixTables) { + const quint32 codedLength = table.prefixLength + table.indexLength; + for (quint32 j = 0; j < table.size();) { + const PrefixTableEntry &entry = tableEntry(table, j); + if (entry.bitLength && entry.bitLength < codedLength) { + const quint32 range = 1 << (codedLength - entry.bitLength); + for (quint32 k = 1; k < range; ++k) + setTableEntry(table, j + k, entry); + j += range; + } else { + ++j; + } + } + } +} + +bool HuffmanDecoder::decodeStream(BitIStream &inputStream, QByteArray &outputBuffer) +{ + while (true) { + quint32 chunk = 0; + const quint32 readBits = inputStream.peekBits(inputStream.streamOffset(), 32, &chunk); + if (!readBits) + return !inputStream.hasMoreBits(); + + if (readBits < minCodeLength) { + inputStream.skipBits(readBits); + return padding_is_valid(chunk, readBits); + } + + quint32 tableIndex = 0; + const PrefixTable *table = &prefixTables[tableIndex]; + quint32 entryIndex = chunk >> (32 - table->indexLength); + PrefixTableEntry entry = tableEntry(*table, entryIndex); + + while (true) { + if (entry.nextTable == tableIndex) + break; + + tableIndex = entry.nextTable; + table = &prefixTables[tableIndex]; + entryIndex = chunk << table->prefixLength >> (32 - table->indexLength); + entry = tableEntry(*table, entryIndex); + } + + if (entry.bitLength > readBits) { + inputStream.skipBits(readBits); + return padding_is_valid(chunk, readBits); + } + + if (!entry.bitLength || entry.byteValue == 256) { + //EOS (256) == compression error (HPACK). + inputStream.skipBits(readBits); + return false; + } + + outputBuffer.append(entry.byteValue); + inputStream.skipBits(entry.bitLength); + } + + return false; +} + +quint32 HuffmanDecoder::addTable(quint32 prefix, quint32 index) +{ + PrefixTable newTable{prefix, index}; + newTable.offset = quint32(tableData.size()); + prefixTables.push_back(newTable); + // Add entries for this table: + tableData.resize(tableData.size() + newTable.size()); + + return quint32(prefixTables.size() - 1); +} + +PrefixTableEntry HuffmanDecoder::tableEntry(const PrefixTable &table, quint32 index) +{ + Q_ASSERT(index < table.size()); + return tableData[table.offset + index]; +} + +void HuffmanDecoder::setTableEntry(const PrefixTable &table, quint32 index, + const PrefixTableEntry &entry) +{ + Q_ASSERT(index < table.size()); + tableData[table.offset + index] = entry; +} + +bool huffman_decode_string(BitIStream &inputStream, QByteArray *outputBuffer) +{ + Q_ASSERT(outputBuffer); + + static HuffmanDecoder decoder; + return decoder.decodeStream(inputStream, *outputBuffer); +} + +} + +QT_END_NAMESPACE diff --git a/src/network/access/http2/huffman_p.h b/src/network/access/http2/huffman_p.h new file mode 100644 index 0000000000..7195661664 --- /dev/null +++ b/src/network/access/http2/huffman_p.h @@ -0,0 +1,182 @@ +/**************************************************************************** +** +** Copyright (C) 2016 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtNetwork module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef HUFFMAN_P_H +#define HUFFMAN_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists for the convenience +// of other Qt classes. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include + +QT_BEGIN_NAMESPACE + +class QByteArray; + +namespace HPack +{ + +struct CodeEntry +{ + CodeEntry() : byteValue(), + huffmanCode(), + bitLength() + { + } + + CodeEntry(quint32 val, quint32 code, quint32 len) + : byteValue(val), + huffmanCode(code), + bitLength(len) + { + } + + quint32 byteValue; + quint32 huffmanCode; + quint32 bitLength; +}; + +class BitOStream; + +quint64 huffman_encoded_bit_length(const QByteArray &inputData); +void huffman_encode_string(const QByteArray &inputData, BitOStream &outputStream); + +// PrefixTable: +// Huffman codes with a small bit length +// fit into a table (these are 'terminal' symbols), +// codes with longer codes require additional +// tables, so several symbols will have the same index +// in a table - pointing into the next table. +// Every table has an 'indexLength' - that's +// how many bits can fit in table's indices + +// 'prefixLength' - how many bits were addressed +// by its 'parent' table(s). +// All PrefixTables are kept in 'prefixTables' array. +// PrefixTable itself does not have any entries, +// it just holds table's prefix/index + 'offset' - +// there table's data starts in an array of all +// possible entries ('tableData'). + +struct PrefixTable +{ + PrefixTable() + : prefixLength(), + indexLength(), + offset() + { + } + + PrefixTable(quint32 prefix, quint32 index) + : prefixLength(prefix), + indexLength(index), + offset() + { + } + + quint32 size()const + { + // Number of entries table contains: + return 1 << indexLength; + } + + quint32 prefixLength; + quint32 indexLength; + quint32 offset; +}; + +// Table entry is either a terminal entry (thus probably the code found) +// or points into another table ('nextTable' - index into +// 'prefixTables' array). If it's a terminal, 'nextTable' index +// refers to the same table. + +struct PrefixTableEntry +{ + PrefixTableEntry() + : bitLength(), + nextTable(), + byteValue() + { + } + + quint32 bitLength; + quint32 nextTable; + quint32 byteValue; +}; + +class BitIStream; + +class HuffmanDecoder +{ +public: + enum class BitConstants + { + rootPrefix = 9, + childPrefix = 6 + }; + + HuffmanDecoder(); + + bool decodeStream(BitIStream &inputStream, QByteArray &outputBuffer); + +private: + quint32 addTable(quint32 prefixLength, quint32 indexLength); + PrefixTableEntry tableEntry(const PrefixTable &table, quint32 index); + void setTableEntry(const PrefixTable &table, quint32 index, const PrefixTableEntry &entry); + + std::vector prefixTables; + std::vector tableData; + quint32 minCodeLength; +}; + +bool huffman_decode_string(BitIStream &inputStream, QByteArray *outputBuffer); + +} // namespace HPack + +QT_END_NAMESPACE + +#endif + diff --git a/tests/auto/network/access/access.pro b/tests/auto/network/access/access.pro index bc76190e30..6ef10b7b1b 100644 --- a/tests/auto/network/access/access.pro +++ b/tests/auto/network/access/access.pro @@ -12,9 +12,11 @@ SUBDIRS=\ qftp \ qhttpnetworkreply \ qabstractnetworkcache \ + hpack !contains(QT_CONFIG, private_tests): SUBDIRS -= \ qhttpnetworkconnection \ qhttpnetworkreply \ qftp \ + hpack \ diff --git a/tests/auto/network/access/hpack/hpack.pro b/tests/auto/network/access/hpack/hpack.pro new file mode 100644 index 0000000000..3c8b8e7944 --- /dev/null +++ b/tests/auto/network/access/hpack/hpack.pro @@ -0,0 +1,6 @@ +QT += core core-private network network-private testlib +CONFIG += testcase parallel_test c++14 +TEMPLATE = app +TARGET = tst_hpack + +SOURCES += tst_hpack.cpp diff --git a/tests/auto/network/access/hpack/tst_hpack.cpp b/tests/auto/network/access/hpack/tst_hpack.cpp new file mode 100644 index 0000000000..bd337c9f5f --- /dev/null +++ b/tests/auto/network/access/hpack/tst_hpack.cpp @@ -0,0 +1,852 @@ +/**************************************************************************** +** +** Copyright (C) 2016 The Qt Company Ltd. +** Copyright (C) 2014 Governikus GmbH & Co. KG. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the test suite of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:GPL-EXCEPT$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 3 as published by the Free Software +** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include + +#include +#include + +#include + +#include +#include +#include + +QT_USE_NAMESPACE + +using namespace HPack; + +class tst_Hpack: public QObject +{ + Q_OBJECT + +public: + tst_Hpack(); +private Q_SLOTS: + void bitstreamConstruction(); + void bitstreamWrite(); + void bitstreamReadWrite(); + void bitstreamCompression(); + void bitstreamErrors(); + + void lookupTableConstructor(); + + void lookupTableStatic_data(); + void lookupTableStatic(); + void lookupTableDynamic(); + + void hpackEncodeRequest_data(); + void hpackEncodeRequest(); + void hpackDecodeRequest_data(); + void hpackDecodeRequest(); + + void hpackEncodeResponse_data(); + void hpackEncodeResponse(); + void hpackDecodeResponse_data(); + void hpackDecodeResponse(); + + // TODO: more-more-more tests needed! + +private: + void hpackEncodeRequest(bool withHuffman); + void hpackEncodeResponse(bool withHuffman); + + HttpHeader header1; + std::vector buffer1; + BitOStream request1; + + HttpHeader header2; + std::vector buffer2; + BitOStream request2; + + HttpHeader header3; + std::vector buffer3; + BitOStream request3; +}; + +using StreamError = BitIStream::Error; + +tst_Hpack::tst_Hpack() + : request1(buffer1), + request2(buffer2), + request3(buffer3) +{ +} + +void tst_Hpack::bitstreamConstruction() +{ + const uchar bytes[] = {0xDE, 0xAD, 0xBE, 0xEF}; + const int size = int(sizeof bytes); + + // Default ctors: + std::vector buffer; + { + const BitOStream out(buffer); + QVERIFY(out.bitLength() == 0); + QVERIFY(out.byteLength() == 0); + + const BitIStream in; + QVERIFY(in.bitLength() == 0); + QVERIFY(in.streamOffset() == 0); + QVERIFY(in.error() == StreamError::NoError); + } + + // Create istream with some data: + { + BitIStream in(bytes, bytes + size); + QVERIFY(in.bitLength() == size * 8); + QVERIFY(in.streamOffset() == 0); + QVERIFY(in.error() == StreamError::NoError); + // 'Read' some data back: + for (int i = 0; i < size; ++i) { + uchar bitPattern = 0; + const auto bitsRead = in.peekBits(i * 8, 8, &bitPattern); + QVERIFY(bitsRead == 8); + QVERIFY(bitPattern == bytes[i]); + } + } + + // Copy ctors: + { + // Ostreams - copy is disabled. + // Istreams: + const BitIStream in1; + const BitIStream in2(in1); + QVERIFY(in2.bitLength() == in1.bitLength()); + QVERIFY(in2.streamOffset() == in1.streamOffset()); + QVERIFY(in2.error() == StreamError::NoError); + + const BitIStream in3(bytes, bytes + size); + const BitIStream in4(in3); + QVERIFY(in4.bitLength() == in3.bitLength()); + QVERIFY(in4.streamOffset() == in3.streamOffset()); + QVERIFY(in4.error() == StreamError::NoError); + } +} + +void tst_Hpack::bitstreamWrite() +{ + // Known representations, + // https://http2.github.io/http2-spec/compression.html. + // 5.1 Integer Representation + + // Test bit/byte lengths of the + // resulting data: + std::vector buffer; + BitOStream out(buffer); + out.write(3); + // 11, fits into 8-bit prefix: + QVERIFY(out.bitLength() == 8); + QVERIFY(out.byteLength() == 1); + QVERIFY(out.begin()[0] == 3); + + out.clear(); + QVERIFY(out.bitLength() == 0); + QVERIFY(out.byteLength() == 0); + + // This number does not fit into 8-bit + // prefix we'll need 2 bytes: + out.write(256); + QVERIFY(out.byteLength() == 2); + QVERIFY(out.bitLength() == 16); + QVERIFY(out.begin()[0] == 0xff); + QVERIFY(out.begin()[1] == 1); + + out.clear(); + + // See 5.2 String Literal Representation. + + // We use Huffman code, + // char 'a' has a prefix code 00011 (5 bits) + out.write(QByteArray("aaa", 3), true); + QVERIFY(out.byteLength() == 3); + QVERIFY(out.bitLength() == 24); + // Now we must have in our stream: + // 10000010 | 00011000| 11000111 + const uchar *encoded = out.begin(); + QVERIFY(encoded[0] == 0x82); + QVERIFY(encoded[1] == 0x18); + QVERIFY(encoded[2] == 0xC7); + // TODO: add more tests ... +} + +void tst_Hpack::bitstreamReadWrite() +{ + // We can write into the bit stream: + // 1) bit patterns + // 2) integers (see HPACK, 5.1) + // 3) string (see HPACK, 5.2) + std::vector buffer; + BitOStream out(buffer); + out.writeBits(0xf, 3); + QVERIFY(out.byteLength() == 1); + QVERIFY(out.bitLength() == 3); + + // Now, read it back: + { + BitIStream in(out.begin(), out.end()); + uchar bitPattern = 0; + const auto bitsRead = in.peekBits(0, 3, &bitPattern); + // peekBits pack into the most significant byte/bit: + QVERIFY(bitsRead == 3); + QVERIFY((bitPattern >> 5) == 7); + } + + const quint32 testInt = 133; + out.write(testInt); + + // This integer does not fit into the current 5-bit prefix, + // so byteLength == 2. + QVERIFY(out.byteLength() == 2); + const auto bitLength = out.bitLength(); + QVERIFY(bitLength > 3); + + // Now, read it back: + { + BitIStream in(out.begin(), out.end()); + in.skipBits(3); // Bit pattern + quint32 value = 0; + QVERIFY(in.read(&value)); + QVERIFY(in.error() == StreamError::NoError); + QCOMPARE(value, testInt); + } + + const QByteArray testString("ABCDE", 5); + out.write(testString, true); // Compressed + out.write(testString, false); // Non-compressed + QVERIFY(out.byteLength() > 2); + QVERIFY(out.bitLength() > bitLength); + + // Now, read it back: + { + BitIStream in(out.begin(), out.end()); + in.skipBits(bitLength); // Bit pattern and integer + QByteArray value; + // Read compressed string first ... + QVERIFY(in.read(&value)); + QCOMPARE(value, testString); + QCOMPARE(in.error(), StreamError::NoError); + // Now non-compressed ... + QVERIFY(in.read(&value)); + QCOMPARE(value, testString); + QCOMPARE(in.error(), StreamError::NoError); + } +} + +void tst_Hpack::bitstreamCompression() +{ + // Similar to bitstreamReadWrite but + // writes/reads a lot of mixed strings/integers. + std::vector strings; + std::vector integers; + std::vector isA; // integer or string. + const std::string bytes("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789()[]/*"); + const unsigned nValues = 100000; + + quint64 totalStringBytes = 0; + std::vector buffer; + BitOStream out(buffer); + for (unsigned i = 0; i < nValues; ++i) { + const bool isString = std::rand() % 1000 > 500; + isA.push_back(isString); + if (!isString) { + integers.push_back(std::rand() % 1000); + out.write(integers.back()); + } else { + const auto start = std::rand() % (bytes.length() / 2); + auto end = start * 2; + if (!end) + end = bytes.length() / 2; + strings.push_back(bytes.substr(start, end - start)); + const auto &s = strings.back(); + totalStringBytes += s.size(); + QByteArray data(s.c_str(), int(s.size())); + const bool compressed(std::rand() % 1000 > 500); + out.write(data, compressed); + } + } + + qDebug() << "Compressed(?) byte length:" << out.byteLength() + << "total string bytes:" << totalStringBytes; + qDebug() << "total integer bytes (for quint32):" << integers.size() * sizeof(quint32); + + QVERIFY(out.byteLength() > 0); + QVERIFY(out.bitLength() > 0); + + BitIStream in(out.begin(), out.end()); + + for (unsigned i = 0, iS = 0, iI = 0; i < nValues; ++i) { + if (isA[i]) { + QByteArray data; + QVERIFY(in.read(&data)); + QCOMPARE(in.error(), StreamError::NoError); + QCOMPARE(data.toStdString(), strings[iS]); + ++iS; + } else { + quint32 value = 0; + QVERIFY(in.read(&value)); + QCOMPARE(in.error(), StreamError::NoError); + QCOMPARE(value, integers[iI]); + ++iI; + } + } +} + +void tst_Hpack::bitstreamErrors() +{ + { + BitIStream in; + quint32 val = 0; + QVERIFY(!in.read(&val)); + QCOMPARE(in.error(), StreamError::NotEnoughData); + } + { + // Integer in a stream, that does not fit into quint32. + const uchar bytes[] = {0xff, 0xff, 0xff, 0xff, 0xff, 0xff}; + BitIStream in(bytes, bytes + sizeof bytes); + quint32 val = 0; + QVERIFY(!in.read(&val)); + QCOMPARE(in.error(), StreamError::InvalidInteger); + } + { + const uchar byte = 0x82; // 1 - Huffman compressed, 2 - the (fake) byte length. + BitIStream in(&byte, &byte + 1); + QByteArray val; + QVERIFY(!in.read(&val)); + QCOMPARE(in.error(), StreamError::NotEnoughData); + } +} + +void tst_Hpack::lookupTableConstructor() +{ + { + FieldLookupTable nonIndexed(4096, false); + QVERIFY(nonIndexed.dynamicDataSize() == 0); + QVERIFY(nonIndexed.numberOfDynamicEntries() == 0); + QVERIFY(nonIndexed.numberOfStaticEntries() != 0); + QVERIFY(nonIndexed.numberOfStaticEntries() == nonIndexed.numberOfEntries()); + // Now we add some fake field and verify what 'non-indexed' means ... no search + // by name. + QVERIFY(nonIndexed.prependField("custom-key", "custom-value")); + // 54: 10 + 12 in name/value pair above + 32 required by HPACK specs ... + QVERIFY(nonIndexed.dynamicDataSize() == 54); + QVERIFY(nonIndexed.numberOfDynamicEntries() == 1); + QCOMPARE(nonIndexed.numberOfEntries(), nonIndexed.numberOfStaticEntries() + 1); + // Should fail to find it (invalid index 0) - search is disabled. + QVERIFY(nonIndexed.indexOf("custom-key", "custom-value") == 0); + } + { + // "key" + "value" == 8 bytes, + 32 (HPACK's requirement) == 40. + // Let's ask for a max-size 32 so that entry does not fit: + FieldLookupTable nonIndexed(32, false); + QVERIFY(nonIndexed.prependField("key", "value")); + QVERIFY(nonIndexed.numberOfEntries() == nonIndexed.numberOfStaticEntries()); + QVERIFY(nonIndexed.indexOf("key", "value") == 0); + } + { + FieldLookupTable indexed(4096, true); + QVERIFY(indexed.dynamicDataSize() == 0); + QVERIFY(indexed.numberOfDynamicEntries() == 0); + QVERIFY(indexed.numberOfStaticEntries() != 0); + QVERIFY(indexed.numberOfStaticEntries() == indexed.numberOfEntries()); + QVERIFY(indexed.prependField("custom-key", "custom-value")); + QVERIFY(indexed.dynamicDataSize() == 54); + QVERIFY(indexed.numberOfDynamicEntries() == 1); + QVERIFY(indexed.numberOfEntries() == indexed.numberOfStaticEntries() + 1); + QVERIFY(indexed.indexOf("custom-key") == indexed.numberOfStaticEntries() + 1); + QVERIFY(indexed.indexOf("custom-key", "custom-value") == indexed.numberOfStaticEntries() + 1); + } +} + +void tst_Hpack::lookupTableStatic_data() +{ + QTest::addColumn("expectedName"); + QTest::addColumn("expectedValue"); + + // Some predefined fields to find + // (they are always defined/required by HPACK). + QTest::newRow(":authority|") << QByteArray(":authority") << QByteArray(""); + QTest::newRow(":method|GET") << QByteArray(":method") << QByteArray("GET"); + QTest::newRow(":method|POST") << QByteArray(":method") << QByteArray("POST"); + QTest::newRow(":path|/") << QByteArray(":path") << QByteArray("/"); + QTest::newRow(":path|/index.html") << QByteArray(":path") << QByteArray("/index.html"); + QTest::newRow(":scheme|http") << QByteArray(":scheme") << QByteArray("http"); + QTest::newRow(":scheme|https") << QByteArray(":scheme") << QByteArray("https"); + QTest::newRow(":status|200") << QByteArray(":status") << QByteArray("200"); + QTest::newRow(":status|204") << QByteArray(":status") << QByteArray("204"); + QTest::newRow(":status|206") << QByteArray(":status") << QByteArray("206"); + QTest::newRow(":status|304") << QByteArray(":status") << QByteArray("304"); + QTest::newRow(":status|400") << QByteArray(":status") << QByteArray("400"); + QTest::newRow(":status|404") << QByteArray(":status") << QByteArray("404"); + QTest::newRow(":status|500") << QByteArray(":status") << QByteArray("500"); +} + +void tst_Hpack::lookupTableStatic() +{ + const FieldLookupTable table(0, false /*all static, no need in 'search index'*/); + + QFETCH(QByteArray, expectedName); + QFETCH(QByteArray, expectedValue); + + const quint32 index = table.indexOf(expectedName, expectedValue); + QVERIFY(index != 0); + + QByteArray name, value; + QVERIFY(table.field(index, &name, &value)); + QCOMPARE(name, expectedName); + QCOMPARE(value, expectedValue); +} + +void tst_Hpack::lookupTableDynamic() +{ + // HPACK's table size: + // for every field -> size += field.name.length() + field.value.length() + 32. + // Let's set some size limit and try to fill table with enough entries to have several + // items evicted. + const quint32 tableSize = 8192; + const char stringData[] = "abcdefghijklmnopABCDEFGHIJKLMNOP0123456789()[]:"; + const quint32 dataSize = sizeof stringData - 1; + + FieldLookupTable table(tableSize, true); + + std::vector fieldsToFind; + quint32 evicted = 0; + + while (true) { + // Strings are repeating way too often, I want to + // have at least some items really evicted and not found, + // therefore these weird dances with start/len. + const quint32 start = std::rand() % (dataSize - 10); + quint32 len = std::rand() % (dataSize - start); + if (!len) + len = 1; + + const QByteArray val(stringData + start, len); + fieldsToFind.push_back(val); + const quint32 entriesBefore = table.numberOfDynamicEntries(); + QVERIFY(table.prependField(val, val)); + QVERIFY(table.indexOf(val)); + QVERIFY(table.indexOf(val) == table.indexOf(val, val)); + QByteArray fieldName, fieldValue; + table.field(table.indexOf(val), &fieldName, &fieldValue); + + QVERIFY(val == fieldName); + QVERIFY(val == fieldValue); + + if (table.numberOfDynamicEntries() <= entriesBefore) { + // We had to evict several items ... + evicted += entriesBefore - table.numberOfDynamicEntries() + 1; + if (evicted >= 200) + break; + } + } + + QVERIFY(table.dynamicDataSize() <= tableSize); + QVERIFY(table.numberOfDynamicEntries() > 0); + QVERIFY(table.indexOf(fieldsToFind.back())); // We MUST have it in a table! + + using size_type = std::vector::size_type; + for (size_type i = 0, e = fieldsToFind.size(); i < e; ++i) { + const auto &val = fieldsToFind[i]; + const quint32 index = table.indexOf(val); + if (!index) { + QVERIFY(i < size_type(evicted)); + } else { + QVERIFY(index == table.indexOf(val, val)); + QByteArray fieldName, fieldValue; + QVERIFY(table.field(index, &fieldName, &fieldValue)); + QVERIFY(val == fieldName); + QVERIFY(val == fieldValue); + } + } + + table.clearDynamicTable(); + + QVERIFY(table.numberOfDynamicEntries() == 0); + QVERIFY(table.dynamicDataSize() == 0); + QVERIFY(table.indexOf(fieldsToFind.back()) == 0); + + QVERIFY(table.prependField("name1", "value1")); + QVERIFY(table.prependField("name2", "value2")); + + QVERIFY(table.indexOf("name1") == table.numberOfStaticEntries() + 2); + QVERIFY(table.indexOf("name2", "value2") == table.numberOfStaticEntries() + 1); + QVERIFY(table.indexOf("name1", "value2") == 0); + QVERIFY(table.indexOf("name2", "value1") == 0); + QVERIFY(table.indexOf("name3") == 0); + + QVERIFY(!table.indexIsValid(table.numberOfEntries() + 1)); + + QVERIFY(table.prependField("name1", "value1")); + QVERIFY(table.numberOfDynamicEntries() == 3); + table.evictEntry(); + QVERIFY(table.indexOf("name1") != 0); + table.evictEntry(); + QVERIFY(table.indexOf("name2") == 0); + QVERIFY(table.indexOf("name1") != 0); + table.evictEntry(); + QVERIFY(table.dynamicDataSize() == 0); + QVERIFY(table.numberOfDynamicEntries() == 0); + QVERIFY(table.indexOf("name1") == 0); +} + +void tst_Hpack::hpackEncodeRequest_data() +{ + QTest::addColumn("compression"); + QTest::newRow("no-string-compression") << false; + QTest::newRow("with-string-compression") << true; +} + +void tst_Hpack::hpackEncodeRequest(bool withHuffman) +{ + // This function uses examples from HPACK specs + // (see appendix). + + Encoder encoder(4096, withHuffman); + // HPACK, C.3.1 First Request + /* + :method: GET + :scheme: http + :path: / + :authority: www.example.com + + Hex dump of encoded data (without Huffman): + + 8286 8441 0f77 7777 2e65 7861 6d70 6c65 | ...A.www.example + 2e63 6f6d + + Hex dump of encoded data (with Huffman): + + 8286 8441 8cf1 e3c2 e5f2 3a6b a0ab 90f4 ff + */ + request1.clear(); + header1 = {{":method", "GET"}, + {":scheme", "http"}, + {":path", "/"}, + {":authority", "www.example.com"}}; + QVERIFY(encoder.encodeRequest(request1, header1)); + QVERIFY(encoder.dynamicTableSize() == 57); + + // HPACK, C.3.2 Second Request + /* + Header list to encode: + + :method: GET + :scheme: http + :path: / + :authority: www.example.com + cache-control: no-cache + + Hex dump of encoded data (without Huffman): + + 8286 84be 5808 6e6f 2d63 6163 6865 + + Hex dump of encoded data (with Huffman): + + 8286 84be 5886 a8eb 1064 9cbf + */ + + request2.clear(); + header2 = {{":method", "GET"}, + {":scheme", "http"}, + {":path", "/"}, + {":authority", "www.example.com"}, + {"cache-control", "no-cache"}}; + encoder.encodeRequest(request2, header2); + QVERIFY(encoder.dynamicTableSize() == 110); + + // HPACK, C.3.3 Third Request + /* + Header list to encode: + + :method: GET + :scheme: https + :path: /index.html + :authority: www.example.com + custom-key: custom-value + + Hex dump of encoded data (without Huffman): + + 8287 85bf 400a 6375 7374 6f6d 2d6b 6579 + 0c63 7573 746f 6d2d 7661 6c75 65 + + Hex dump of encoded data (with Huffman): + + 8287 85bf 4088 25a8 49e9 5ba9 7d7f 8925 + a849 e95b b8e8 b4bf + */ + request3.clear(); + header3 = {{":method", "GET"}, + {":scheme", "https"}, + {":path", "/index.html"}, + {":authority", "www.example.com"}, + {"custom-key", "custom-value"}}; + encoder.encodeRequest(request3, header3); + QVERIFY(encoder.dynamicTableSize() == 164); +} + +void tst_Hpack::hpackEncodeRequest() +{ + QFETCH(bool, compression); + + hpackEncodeRequest(compression); + + // See comments above about these hex dumps ... + const uchar bytes1NH[] = {0x82, 0x86, 0x84, 0x41, + 0x0f, 0x77, 0x77, 0x77, + 0x2e, 0x65, 0x78, 0x61, + 0x6d, 0x70, 0x6c, 0x65, + 0x2e, 0x63, 0x6f, 0x6d}; + + const uchar bytes1WH[] = {0x82, 0x86, 0x84, 0x41, + 0x8c, 0xf1, 0xe3, 0xc2, + 0xe5, 0xf2, 0x3a, 0x6b, + 0xa0, 0xab, 0x90, 0xf4, + 0xff}; + + const uchar *hexDump1 = compression ? bytes1WH : bytes1NH; + const quint64 byteLength1 = compression ? sizeof bytes1WH : sizeof bytes1NH; + + QCOMPARE(request1.byteLength(), byteLength1); + QCOMPARE(request1.bitLength(), byteLength1 * 8); + + for (quint32 i = 0, e = request1.byteLength(); i < e; ++i) + QCOMPARE(hexDump1[i], request1.begin()[i]); + + const uchar bytes2NH[] = {0x82, 0x86, 0x84, 0xbe, + 0x58, 0x08, 0x6e, 0x6f, + 0x2d, 0x63, 0x61, 0x63, + 0x68, 0x65}; + + const uchar bytes2WH[] = {0x82, 0x86, 0x84, 0xbe, + 0x58, 0x86, 0xa8, 0xeb, + 0x10, 0x64, 0x9c, 0xbf}; + + const uchar *hexDump2 = compression ? bytes2WH : bytes2NH; + const auto byteLength2 = compression ? sizeof bytes2WH : sizeof bytes2NH; + QVERIFY(request2.byteLength() == byteLength2); + QVERIFY(request2.bitLength() == byteLength2 * 8); + for (quint32 i = 0, e = request2.byteLength(); i < e; ++i) + QCOMPARE(hexDump2[i], request2.begin()[i]); + + const uchar bytes3NH[] = {0x82, 0x87, 0x85, 0xbf, + 0x40, 0x0a, 0x63, 0x75, + 0x73, 0x74, 0x6f, 0x6d, + 0x2d, 0x6b, 0x65, 0x79, + 0x0c, 0x63, 0x75, 0x73, + 0x74, 0x6f, 0x6d, 0x2d, + 0x76, 0x61, 0x6c, 0x75, + 0x65}; + const uchar bytes3WH[] = {0x82, 0x87, 0x85, 0xbf, + 0x40, 0x88, 0x25, 0xa8, + 0x49, 0xe9, 0x5b, 0xa9, + 0x7d, 0x7f, 0x89, 0x25, + 0xa8, 0x49, 0xe9, 0x5b, + 0xb8, 0xe8, 0xb4, 0xbf}; + + const uchar *hexDump3 = compression ? bytes3WH : bytes3NH; + const quint64 byteLength3 = compression ? sizeof bytes3WH : sizeof bytes3NH; + QCOMPARE(request3.byteLength(), byteLength3); + QCOMPARE(request3.bitLength(), byteLength3 * 8); + for (quint32 i = 0, e = request3.byteLength(); i < e; ++i) + QCOMPARE(hexDump3[i], request3.begin()[i]); +} + +void tst_Hpack::hpackDecodeRequest_data() +{ + QTest::addColumn("compression"); + QTest::newRow("no-string-compression") << false; + QTest::newRow("with-string-compression") << true; +} + +void tst_Hpack::hpackDecodeRequest() +{ + QFETCH(bool, compression); + hpackEncodeRequest(compression); + + QVERIFY(request1.byteLength()); + QVERIFY(request2.byteLength()); + QVERIFY(request3.byteLength()); + + Decoder decoder(4096); + BitIStream inputStream1(request1.begin(), request1.end()); + QVERIFY(decoder.decodeHeaderFields(inputStream1)); + QCOMPARE(decoder.dynamicTableSize(), quint32(57)); + { + const auto &decoded = decoder.decodedHeader(); + QVERIFY(decoded == header1); + } + + BitIStream inputStream2{request2.begin(), request2.end()}; + QVERIFY(decoder.decodeHeaderFields(inputStream2)); + QCOMPARE(decoder.dynamicTableSize(), quint32(110)); + { + const auto &decoded = decoder.decodedHeader(); + QVERIFY(decoded == header2); + } + + BitIStream inputStream3(request3.begin(), request3.end()); + QVERIFY(decoder.decodeHeaderFields(inputStream3)); + QCOMPARE(decoder.dynamicTableSize(), quint32(164)); + { + const auto &decoded = decoder.decodedHeader(); + QVERIFY(decoded == header3); + } +} + +void tst_Hpack::hpackEncodeResponse_data() +{ + hpackEncodeRequest_data(); +} + +void tst_Hpack::hpackEncodeResponse() +{ + QFETCH(bool, compression); + + hpackEncodeResponse(compression); + + // TODO: we can also test bytes - using hex dumps from HPACK's specs, + // for now only test a table behavior/expected sizes. +} + +void tst_Hpack::hpackEncodeResponse(bool withCompression) +{ + Encoder encoder(256, withCompression); // 256 - this will result in entries evicted. + + // HPACK, C.5.1 First Response + /* + Header list to encode: + + :status: 302 + cache-control: private + date: Mon, 21 Oct 2013 20:13:21 GMT + location: https://www.example.com + */ + request1.clear(); + header1 = {{":status", "302"}, + {"cache-control", "private"}, + {"date", "Mon, 21 Oct 2013 20:13:21 GMT"}, + {"location", "https://www.example.com"}}; + + QVERIFY(encoder.encodeResponse(request1, header1)); + QCOMPARE(encoder.dynamicTableSize(), quint32(222)); + + // HPACK, C.5.2 Second Response + /* + + + The (":status", "302") header field is evicted from the dynamic + table to free space to allow adding the (":status", "307") header field. + + Header list to encode: + + :status: 307 + cache-control: private + date: Mon, 21 Oct 2013 20:13:21 GMT + location: https://www.example.com + */ + request2.clear(); + header2 = {{":status", "307"}, + {"cache-control", "private"}, + {"date", "Mon, 21 Oct 2013 20:13:21 GMT"}, + {"location", "https://www.example.com"}}; + QVERIFY(encoder.encodeResponse(request2, header2)); + QCOMPARE(encoder.dynamicTableSize(), quint32(222)); + + // HPACK, C.5.3 Third Response + /* + Several header fields are evicted from the dynamic table + during the processing of this header list. + + Header list to encode: + + :status: 200 + cache-control: private + date: Mon, 21 Oct 2013 20:13:22 GMT + location: https://www.example.com + content-encoding: gzip + set-cookie: foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1 + */ + request3.clear(); + header3 = {{":status", "200"}, + {"cache-control", "private"}, + {"date", "Mon, 21 Oct 2013 20:13:22 GMT"}, + {"location", "https://www.example.com"}, + {"content-encoding", "gzip"}, + {"set-cookie", "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1"}}; + QVERIFY(encoder.encodeResponse(request3, header3)); + QCOMPARE(encoder.dynamicTableSize(), quint32(215)); +} + +void tst_Hpack::hpackDecodeResponse_data() +{ + hpackEncodeRequest_data(); +} + +void tst_Hpack::hpackDecodeResponse() +{ + QFETCH(bool, compression); + + hpackEncodeResponse(compression); + + QVERIFY(request1.byteLength()); + Decoder decoder(256); // This size will result in entries evicted. + BitIStream inputStream1(request1.begin(), request1.end()); + QVERIFY(decoder.decodeHeaderFields(inputStream1)); + QCOMPARE(decoder.dynamicTableSize(), quint32(222)); + + { + const auto &decoded = decoder.decodedHeader(); + QVERIFY(decoded == header1); + } + + QVERIFY(request2.byteLength()); + BitIStream inputStream2(request2.begin(), request2.end()); + QVERIFY(decoder.decodeHeaderFields(inputStream2)); + QCOMPARE(decoder.dynamicTableSize(), quint32(222)); + + { + const auto &decoded = decoder.decodedHeader(); + QVERIFY(decoded == header2); + } + + QVERIFY(request3.byteLength()); + BitIStream inputStream3(request3.begin(), request3.end()); + QVERIFY(decoder.decodeHeaderFields(inputStream3)); + QCOMPARE(decoder.dynamicTableSize(), quint32(215)); + + { + const auto &decoded = decoder.decodedHeader(); + QVERIFY(decoded == header3); + } +} + +QTEST_MAIN(tst_Hpack) + +#include "tst_hpack.moc" -- cgit v1.2.3