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

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