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