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 #ifndef HUFFMAN_P_H
41 #define HUFFMAN_P_H
42 
43 //
44 //  W A R N I N G
45 //  -------------
46 //
47 // This file is not part of the Qt API.  It exists for the convenience
48 // of other Qt classes.  This header file may change from version to
49 // version without notice, or even be removed.
50 //
51 // We mean it.
52 //
53 
54 #include <QtCore/qglobal.h>
55 
56 QT_BEGIN_NAMESPACE
57 
58 class QByteArray;
59 
60 namespace HPack
61 {
62 
63 struct CodeEntry
64 {
65     quint32 byteValue;
66     quint32 huffmanCode;
67     quint32 bitLength;
68 };
69 
70 class BitOStream;
71 
72 quint64 huffman_encoded_bit_length(const QByteArray &inputData);
73 void huffman_encode_string(const QByteArray &inputData, BitOStream &outputStream);
74 
75 // PrefixTable:
76 // Huffman codes with a small bit length
77 // fit into a table (these are 'terminal' symbols),
78 // codes with longer codes require additional
79 // tables, so several symbols will have the same index
80 // in a table - pointing into the next table.
81 // Every table has an 'indexLength' - that's
82 // how many bits can fit in table's indices +
83 // 'prefixLength' - how many bits were addressed
84 // by its 'parent' table(s).
85 // All PrefixTables are kept in 'prefixTables' array.
86 // PrefixTable itself does not have any entries,
87 // it just holds table's prefix/index + 'offset' -
88 // there table's data starts in an array of all
89 // possible entries ('tableData').
90 
91 struct PrefixTable
92 {
PrefixTablePrefixTable93     PrefixTable()
94         : prefixLength(),
95           indexLength(),
96           offset()
97     {
98     }
99 
PrefixTablePrefixTable100     PrefixTable(quint32 prefix, quint32 index)
101         : prefixLength(prefix),
102           indexLength(index),
103           offset()
104     {
105     }
106 
sizePrefixTable107     quint32 size()const
108     {
109         // Number of entries table contains:
110         return 1 << indexLength;
111     }
112 
113     quint32 prefixLength;
114     quint32 indexLength;
115     quint32 offset;
116 };
117 
118 // Table entry is either a terminal entry (thus probably the code found)
119 // or points into another table ('nextTable' - index into
120 // 'prefixTables' array). If it's a terminal, 'nextTable' index
121 // refers to the same table.
122 
123 struct PrefixTableEntry
124 {
PrefixTableEntryPrefixTableEntry125     PrefixTableEntry()
126         : bitLength(),
127           nextTable(),
128           byteValue()
129     {
130     }
131 
132     quint32 bitLength;
133     quint32 nextTable;
134     quint32 byteValue;
135 };
136 
137 class BitIStream;
138 
139 class HuffmanDecoder
140 {
141 public:
142     enum class BitConstants
143     {
144         rootPrefix = 9,
145         childPrefix = 6
146     };
147 
148     HuffmanDecoder();
149 
150     bool decodeStream(BitIStream &inputStream, QByteArray &outputBuffer);
151 
152 private:
153     quint32 addTable(quint32 prefixLength, quint32 indexLength);
154     PrefixTableEntry tableEntry(const PrefixTable &table, quint32 index);
155     void setTableEntry(const PrefixTable &table, quint32 index, const PrefixTableEntry &entry);
156 
157     std::vector<PrefixTable> prefixTables;
158     std::vector<PrefixTableEntry> tableData;
159     quint32 minCodeLength;
160 };
161 
162 bool huffman_decode_string(BitIStream &inputStream, QByteArray *outputBuffer);
163 
164 } // namespace HPack
165 
166 QT_END_NAMESPACE
167 
168 #endif
169 
170