1// Copyright (C) 2016 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
3// Qt-Security score:critical reason:network-protocol
4
5#include "bitstreams_p.h"
6#include "huffman_p.h"
7
8#include <QtCore/qbytearray.h>
9
10#include <limits>
11
12QT_BEGIN_NAMESPACE
13
14static_assert(std::numeric_limits<uchar>::digits == 8, "octets expected");
15
16namespace HPack
17{
18
19BitOStream::BitOStream(std::vector<uchar> &b)
20 : buffer(b),
21 // All data 'packed' before:
22 bitsSet(8 * quint64(b.size()))
23{
24}
25
26void BitOStream::writeBits(uchar bits, quint8 bitLength)
27{
28 Q_ASSERT(bitLength <= 8);
29
30 quint8 count = bitsSet % 8; // bits used in buffer.back(), but 0 means 8
31 bits <<= 8 - bitLength; // at top of byte, lower bits clear
32 if (count) { // we have a part-used byte; fill it some more:
33 buffer.back() |= bits >> count;
34 count = 8 - count;
35 } // count bits have been consumed (and 0 now means 0)
36 if (bitLength > count)
37 buffer.push_back(x: bits << count);
38
39 bitsSet += bitLength;
40}
41
42void BitOStream::write(quint32 src)
43{
44 const quint8 prefixLen = 8 - bitsSet % 8;
45 const quint32 fullPrefix = (1 << prefixLen) - 1;
46
47 // https://http2.github.io/http2-spec/compression.html#low-level.representation,
48 // 5.1
49 if (src < fullPrefix) {
50 writeBits(bits: uchar(src), bitLength: prefixLen);
51 } else {
52 writeBits(bits: uchar(fullPrefix), bitLength: prefixLen);
53 // We're on the byte boundary now,
54 // so we can just 'push_back'.
55 Q_ASSERT(!(bitsSet % 8));
56 src -= fullPrefix;
57 while (src >= 128) {
58 buffer.push_back(x: uchar(src % 128 + 128));
59 src /= 128;
60 bitsSet += 8;
61 }
62 buffer.push_back(x: src);
63 bitsSet += 8;
64 }
65}
66
67void BitOStream::write(QByteArrayView src, bool compressed)
68{
69 quint32 byteLen = src.size();
70 if (compressed && byteLen) {
71 const auto bitLen = huffman_encoded_bit_length(inputData: src);
72 Q_ASSERT(bitLen && std::numeric_limits<quint32>::max() >= (bitLen + 7) / 8);
73 byteLen = (bitLen + 7) / 8;
74 writeBits(bits: uchar(1), bitLength: 1); // bit set - compressed
75 } else {
76 writeBits(bits: uchar(0), bitLength: 1); // no compression.
77 }
78
79 write(src: byteLen);
80
81 if (compressed) {
82 huffman_encode_string(inputData: src, outputStream&: *this);
83 } else {
84 bitsSet += quint64(src.size()) * 8;
85 buffer.insert(position: buffer.end(), first: src.begin(), last: src.end());
86 }
87}
88
89quint64 BitOStream::bitLength() const
90{
91 return bitsSet;
92}
93
94quint64 BitOStream::byteLength() const
95{
96 return buffer.size();
97}
98
99const uchar *BitOStream::begin() const
100{
101 return &buffer[0];
102}
103
104const uchar *BitOStream::end() const
105{
106 return &buffer[0] + buffer.size();
107}
108
109void BitOStream::clear()
110{
111 buffer.clear();
112 bitsSet = 0;
113}
114
115BitIStream::BitIStream()
116 : first(),
117 last(),
118 offset(),
119 streamError(Error::NoError)
120{
121}
122
123BitIStream::BitIStream(const uchar *begin, const uchar *end)
124 : first(begin),
125 last(end),
126 offset(),
127 streamError(Error::NoError)
128{
129}
130
131quint64 BitIStream::bitLength() const
132{
133 return quint64(last - first) * 8;
134}
135
136bool BitIStream::hasMoreBits() const
137{
138 return offset < bitLength();
139}
140
141bool BitIStream::skipBits(quint64 nBits)
142{
143 if (nBits > bitLength() || bitLength() - nBits < offset)
144 return false;
145
146 offset += nBits;
147 return true;
148}
149
150bool BitIStream::rewindOffset(quint64 nBits)
151{
152 if (nBits > offset)
153 return false;
154
155 offset -= nBits;
156 return true;
157}
158
159bool BitIStream::read(quint32 *dstPtr)
160{
161 Q_ASSERT(dstPtr);
162 quint32 &dst = *dstPtr;
163
164 // 5.1 Integer Representation
165 //
166 // Integers are used to represent name indexes, header field indexes, or string lengths.
167 // An integer representation can start anywhere within an octet.
168 // To allow for optimized processing, an integer representation always finishes at the end of an octet.
169 // An integer is represented in two parts: a prefix that fills the current octet and an optional
170 // list of octets that are used if the integer value does not fit within the prefix.
171 // The number of bits of the prefix (called N) is a parameter of the integer representation.
172 // If the integer value is small enough, i.e., strictly less than 2N-1, it is compressed within the N-bit prefix.
173 // ...
174 // The prefix size, N, is always between 1 and 8 bits. An integer
175 // starting at an octet boundary will have an 8-bit prefix.
176
177 // Technically, such integers can be of any size, but as we do not have arbitrary-long integers,
178 // everything that does not fit into 'dst' we consider as an error (after all, try to allocate a string
179 // of such size and ... hehehe - send it as a part of a header!
180
181 // This function updates the offset _only_ if the read was successful.
182 if (offset >= bitLength()) {
183 setError(Error::NotEnoughData);
184 return false;
185 }
186
187 setError(Error::NoError);
188
189 const quint32 prefixLen = 8 - offset % 8;
190 const quint32 fullPrefix = (1 << prefixLen) - 1;
191
192 const uchar prefix = uchar(first[offset / 8] & fullPrefix);
193 if (prefix < fullPrefix) {
194 // The number fitted into the prefix bits.
195 dst = prefix;
196 offset += prefixLen;
197 return true;
198 }
199
200 quint32 newOffset = offset + prefixLen;
201 // We have a list of bytes representing an integer ...
202 quint64 val = prefix;
203 quint32 octetPower = 0;
204
205 while (true) {
206 if (newOffset >= bitLength()) {
207 setError(Error::NotEnoughData);
208 return false;
209 }
210
211 const uchar octet = first[newOffset / 8];
212
213 if (octetPower == 28 && octet > 15) {
214 qCritical(msg: "integer is too big");
215 setError(Error::InvalidInteger);
216 return false;
217 }
218
219 val += quint32(octet & 0x7f) << octetPower;
220 newOffset += 8;
221
222 if (!(octet & 0x80)) {
223 // The most significant bit of each octet is used
224 // as a continuation flag: its value is set to 1
225 // except for the last octet in the list.
226 break;
227 }
228
229 octetPower += 7;
230 }
231
232 dst = val;
233 offset = newOffset;
234 Q_ASSERT(!(offset % 8));
235
236 return true;
237}
238
239bool BitIStream::read(QByteArray *dstPtr)
240{
241 Q_ASSERT(dstPtr);
242 QByteArray &dst = *dstPtr;
243 //5.2 String Literal Representation
244 //
245 // Header field names and header field values can be represented as string literals.
246 // A string literal is compressed as a sequence of octets, either by directly encoding
247 // the string literal's octets or by using a Huffman code.
248
249 // We update the offset _only_ if the read was successful.
250
251 const quint64 oldOffset = offset;
252 uchar compressed = 0;
253 if (peekBits(from: offset, length: 1, dstPtr: &compressed) != 1 || !skipBits(nBits: 1)) {
254 setError(Error::NotEnoughData);
255 return false;
256 }
257
258 setError(Error::NoError);
259
260 quint32 len = 0;
261 if (read(dstPtr: &len)) {
262 Q_ASSERT(!(offset % 8));
263 if (len <= (bitLength() - offset) / 8) { // We have enough data to read a string ...
264 if (!compressed) {
265 // Now good news, integer always ends on a byte boundary.
266 // We can read 'len' bytes without any bit magic.
267 const char *src = reinterpret_cast<const char *>(first + offset / 8);
268 dst = QByteArray(src, len);
269 offset += quint64(len) * 8;
270 return true;
271 }
272
273 BitIStream slice(first + offset / 8, first + offset / 8 + len);
274 if (huffman_decode_string(inputStream&: slice, outputBuffer: &dst)) {
275 offset += quint64(len) * 8;
276 return true;
277 }
278
279 setError(Error::CompressionError);
280 } else {
281 setError(Error::NotEnoughData);
282 }
283 } // else the exact reason was set by read(quint32).
284
285 offset = oldOffset;
286 return false;
287}
288
289BitIStream::Error BitIStream::error() const
290{
291 return streamError;
292}
293
294void BitIStream::setError(Error newState)
295{
296 streamError = newState;
297}
298
299} // namespace HPack
300
301QT_END_NAMESPACE
302

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