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

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