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