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:significant reason:default
4
5#ifndef HUFFMAN_P_H
6#define HUFFMAN_P_H
7
8//
9// W A R N I N G
10// -------------
11//
12// This file is not part of the Qt API. It exists for the convenience
13// of other Qt classes. This header file may change from version to
14// version without notice, or even be removed.
15//
16// We mean it.
17//
18
19QT_BEGIN_NAMESPACE
20
21class QByteArray;
22
23namespace HPack
24{
25
26struct CodeEntry
27{
28 quint32 byteValue;
29 quint32 huffmanCode;
30 quint32 bitLength;
31};
32
33class BitOStream;
34
35quint64 huffman_encoded_bit_length(QByteArrayView inputData);
36void huffman_encode_string(QByteArrayView inputData, BitOStream &outputStream);
37
38// PrefixTable:
39// Huffman codes with a small bit length
40// fit into a table (these are 'terminal' symbols),
41// codes with longer codes require additional
42// tables, so several symbols will have the same index
43// in a table - pointing into the next table.
44// Every table has an 'indexLength' - that's
45// how many bits can fit in table's indices +
46// 'prefixLength' - how many bits were addressed
47// by its 'parent' table(s).
48// All PrefixTables are kept in 'prefixTables' array.
49// PrefixTable itself does not have any entries,
50// it just holds table's prefix/index + 'offset' -
51// there table's data starts in an array of all
52// possible entries ('tableData').
53
54struct PrefixTable
55{
56 PrefixTable()
57 : prefixLength(),
58 indexLength(),
59 offset()
60 {
61 }
62
63 PrefixTable(quint32 prefix, quint32 index)
64 : prefixLength(prefix),
65 indexLength(index),
66 offset()
67 {
68 }
69
70 quint32 size()const
71 {
72 // Number of entries table contains:
73 return 1 << indexLength;
74 }
75
76 quint32 prefixLength;
77 quint32 indexLength;
78 quint32 offset;
79};
80
81// Table entry is either a terminal entry (thus probably the code found)
82// or points into another table ('nextTable' - index into
83// 'prefixTables' array). If it's a terminal, 'nextTable' index
84// refers to the same table.
85
86struct PrefixTableEntry
87{
88 PrefixTableEntry()
89 : bitLength(),
90 nextTable(),
91 byteValue()
92 {
93 }
94
95 quint32 bitLength;
96 quint32 nextTable;
97 quint32 byteValue;
98};
99
100class BitIStream;
101
102class HuffmanDecoder
103{
104public:
105 enum class BitConstants
106 {
107 rootPrefix = 9,
108 childPrefix = 6
109 };
110
111 HuffmanDecoder();
112
113 bool decodeStream(BitIStream &inputStream, QByteArray &outputBuffer);
114
115private:
116 quint32 addTable(quint32 prefixLength, quint32 indexLength);
117 PrefixTableEntry tableEntry(PrefixTable table, quint32 index);
118 void setTableEntry(PrefixTable table, quint32 index, PrefixTableEntry entry);
119
120 std::vector<PrefixTable> prefixTables;
121 std::vector<PrefixTableEntry> tableData;
122 quint32 minCodeLength;
123};
124
125bool huffman_decode_string(BitIStream &inputStream, QByteArray *outputBuffer);
126
127} // namespace HPack
128
129QT_END_NAMESPACE
130
131#endif
132
133

source code of qtbase/src/network/access/http2/huffman_p.h