/src/qtbase/src/network/access/http2/huffman.cpp

Line	Count	Source
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:critical reason:network-protocol
4
5		#include "bitstreams_p.h"
6		#include "huffman_p.h"
7
8		#include <QtCore/qbytearray.h>
9
10		#include <algorithm>
11		#include <limits>
12
13		QT_BEGIN_NAMESPACE
14
15		namespace HPack
16		{
17
18		/*
19		The static Huffman code used here was extracted from:
20		https://http2.github.io/http2-spec/compression.html#huffman.code
21
22		This code was generated from statistics obtained on a large
23		sample of HTTP headers. It is a canonical Huffman code
24		with some tweaking to ensure that no symbol has a unique
25		code length. All codes were left-aligned - for implementation
26		convenience.
27
28		Using binary trees to implement decoding would be prohibitively
29		expensive (both memory and time-wise). Instead we use a table-based
30		approach and any given code itself works as an index into such table(s).
31		We have 256 possible byte values and code lengths in
32		a range [5, 26]. This would require a huge table (and most of entries
33		would be 'wasted', since we only have to encode 256 elements).
34		Instead we use multi-level tables. The first level table
35		is using 9-bit length index; some entries in this table are 'terminal',
36		some reference the next level table(s).
37
38		For example, bytes with values 48 and 49 (ASCII codes for '0' and '1')
39		both have code length 5, Huffman codes are: 00000 and 00001. They
40		both are placed in the 'root' table,
41		the 'root' table has index length == 9:
42		[00000 \| 4 remaining bits]
43		...
44		[00001 \| 4 remaining bits]
45
46		All entries with indices between these two will 'point' to value 48
47		with bitLength == 5 so that bit stream (for example) 000001010 will be
48		decoded as: 48 + "put 1010 back into bitstream".
49
50		A good description can be found here:
51		http://commandlinefanatic.com/cgi-bin/showarticle.cgi?article=art007
52		or just google "Efficient Huffman Decoding".
53		Also see comments below about 'filling holes'.
54		*/
55
56		namespace
57		{
58
59		const CodeEntry staticHuffmanCodeTable[]
60		{
61		{ 0, 0xffc00000ul, 13}, // 11111111\|11000
62		{ 1, 0xffffb000ul, 23}, // 11111111\|11111111\|1011000
63		{ 2, 0xfffffe20ul, 28}, // 11111111\|11111111\|11111110\|0010
64		{ 3, 0xfffffe30ul, 28}, // 11111111\|11111111\|11111110\|0011
65		{ 4, 0xfffffe40ul, 28}, // 11111111\|11111111\|11111110\|0100
66		{ 5, 0xfffffe50ul, 28}, // 11111111\|11111111\|11111110\|0101
67		{ 6, 0xfffffe60ul, 28}, // 11111111\|11111111\|11111110\|0110
68		{ 7, 0xfffffe70ul, 28}, // 11111111\|11111111\|11111110\|0111
69		{ 8, 0xfffffe80ul, 28}, // 11111111\|11111111\|11111110\|1000
70		{ 9, 0xffffea00ul, 24}, // 11111111\|11111111\|11101010
71		{ 10, 0xfffffff0ul, 30}, // 11111111\|11111111\|11111111\|111100
72		{ 11, 0xfffffe90ul, 28}, // 11111111\|11111111\|11111110\|1001
73		{ 12, 0xfffffea0ul, 28}, // 11111111\|11111111\|11111110\|1010
74		{ 13, 0xfffffff4ul, 30}, // 11111111\|11111111\|11111111\|111101
75		{ 14, 0xfffffeb0ul, 28}, // 11111111\|11111111\|11111110\|1011
76		{ 15, 0xfffffec0ul, 28}, // 11111111\|11111111\|11111110\|1100
77		{ 16, 0xfffffed0ul, 28}, // 11111111\|11111111\|11111110\|1101
78		{ 17, 0xfffffee0ul, 28}, // 11111111\|11111111\|11111110\|1110
79		{ 18, 0xfffffef0ul, 28}, // 11111111\|11111111\|11111110\|1111
80		{ 19, 0xffffff00ul, 28}, // 11111111\|11111111\|11111111\|0000
81		{ 20, 0xffffff10ul, 28}, // 11111111\|11111111\|11111111\|0001
82		{ 21, 0xffffff20ul, 28}, // 11111111\|11111111\|11111111\|0010
83		{ 22, 0xfffffff8ul, 30}, // 11111111\|11111111\|11111111\|111110
84		{ 23, 0xffffff30ul, 28}, // 11111111\|11111111\|11111111\|0011
85		{ 24, 0xffffff40ul, 28}, // 11111111\|11111111\|11111111\|0100
86		{ 25, 0xffffff50ul, 28}, // 11111111\|11111111\|11111111\|0101
87		{ 26, 0xffffff60ul, 28}, // 11111111\|11111111\|11111111\|0110
88		{ 27, 0xffffff70ul, 28}, // 11111111\|11111111\|11111111\|0111
89		{ 28, 0xffffff80ul, 28}, // 11111111\|11111111\|11111111\|1000
90		{ 29, 0xffffff90ul, 28}, // 11111111\|11111111\|11111111\|1001
91		{ 30, 0xffffffa0ul, 28}, // 11111111\|11111111\|11111111\|1010
92		{ 31, 0xffffffb0ul, 28}, // 11111111\|11111111\|11111111\|1011
93		{ 32, 0x50000000ul, 6}, // ' ' 010100
94		{ 33, 0xfe000000ul, 10}, // '!' 11111110\|00
95		{ 34, 0xfe400000ul, 10}, // '"' 11111110\|01
96		{ 35, 0xffa00000ul, 12}, // '#' 11111111\|1010
97		{ 36, 0xffc80000ul, 13}, // '$' 11111111\|11001
98		{ 37, 0x54000000ul, 6}, // '%' 010101
99		{ 38, 0xf8000000ul, 8}, // '&' 11111000
100		{ 39, 0xff400000ul, 11}, // ''' 11111111\|010
101		{ 40, 0xfe800000ul, 10}, // '(' 11111110\|10
102		{ 41, 0xfec00000ul, 10}, // ')' 11111110\|11
103		{ 42, 0xf9000000ul, 8}, // '*' 11111001
104		{ 43, 0xff600000ul, 11}, // '+' 11111111\|011
105		{ 44, 0xfa000000ul, 8}, // ',' 11111010
106		{ 45, 0x58000000ul, 6}, // '-' 010110
107		{ 46, 0x5c000000ul, 6}, // '.' 010111
108		{ 47, 0x60000000ul, 6}, // '/' 011000
109		{ 48, 0x00000000ul, 5}, // '0' 00000
110		{ 49, 0x08000000ul, 5}, // '1' 00001
111		{ 50, 0x10000000ul, 5}, // '2' 00010
112		{ 51, 0x64000000ul, 6}, // '3' 011001
113		{ 52, 0x68000000ul, 6}, // '4' 011010
114		{ 53, 0x6c000000ul, 6}, // '5' 011011
115		{ 54, 0x70000000ul, 6}, // '6' 011100
116		{ 55, 0x74000000ul, 6}, // '7' 011101
117		{ 56, 0x78000000ul, 6}, // '8' 011110
118		{ 57, 0x7c000000ul, 6}, // '9' 011111
119		{ 58, 0xb8000000ul, 7}, // ':' 1011100
120		{ 59, 0xfb000000ul, 8}, // ';' 11111011
121		{ 60, 0xfff80000ul, 15}, // '<' 11111111\|1111100
122		{ 61, 0x80000000ul, 6}, // '=' 100000
123		{ 62, 0xffb00000ul, 12}, // '>' 11111111\|1011
124		{ 63, 0xff000000ul, 10}, // '?' 11111111\|00
125		{ 64, 0xffd00000ul, 13}, // '@' 11111111\|11010
126		{ 65, 0x84000000ul, 6}, // 'A' 100001
127		{ 66, 0xba000000ul, 7}, // 'B' 1011101
128		{ 67, 0xbc000000ul, 7}, // 'C' 1011110
129		{ 68, 0xbe000000ul, 7}, // 'D' 1011111
130		{ 69, 0xc0000000ul, 7}, // 'E' 1100000
131		{ 70, 0xc2000000ul, 7}, // 'F' 1100001
132		{ 71, 0xc4000000ul, 7}, // 'G' 1100010
133		{ 72, 0xc6000000ul, 7}, // 'H' 1100011
134		{ 73, 0xc8000000ul, 7}, // 'I' 1100100
135		{ 74, 0xca000000ul, 7}, // 'J' 1100101
136		{ 75, 0xcc000000ul, 7}, // 'K' 1100110
137		{ 76, 0xce000000ul, 7}, // 'L' 1100111
138		{ 77, 0xd0000000ul, 7}, // 'M' 1101000
139		{ 78, 0xd2000000ul, 7}, // 'N' 1101001
140		{ 79, 0xd4000000ul, 7}, // 'O' 1101010
141		{ 80, 0xd6000000ul, 7}, // 'P' 1101011
142		{ 81, 0xd8000000ul, 7}, // 'Q' 1101100
143		{ 82, 0xda000000ul, 7}, // 'R' 1101101
144		{ 83, 0xdc000000ul, 7}, // 'S' 1101110
145		{ 84, 0xde000000ul, 7}, // 'T' 1101111
146		{ 85, 0xe0000000ul, 7}, // 'U' 1110000
147		{ 86, 0xe2000000ul, 7}, // 'V' 1110001
148		{ 87, 0xe4000000ul, 7}, // 'W' 1110010
149		{ 88, 0xfc000000ul, 8}, // 'X' 11111100
150		{ 89, 0xe6000000ul, 7}, // 'Y' 1110011
151		{ 90, 0xfd000000ul, 8}, // 'Z' 11111101
152		{ 91, 0xffd80000ul, 13}, // '[' 11111111\|11011
153		{ 92, 0xfffe0000ul, 19}, // '\' 11111111\|11111110\|000
154		{ 93, 0xffe00000ul, 13}, // ']' 11111111\|11100
155		{ 94, 0xfff00000ul, 14}, // '^' 11111111\|111100
156		{ 95, 0x88000000ul, 6}, // '_' 100010
157		{ 96, 0xfffa0000ul, 15}, // '`' 11111111\|1111101
158		{ 97, 0x18000000ul, 5}, // 'a' 00011
159		{ 98, 0x8c000000ul, 6}, // 'b' 100011
160		{ 99, 0x20000000ul, 5}, // 'c' 00100
161		{100, 0x90000000ul, 6}, // 'd' 100100
162		{101, 0x28000000ul, 5}, // 'e' 00101
163		{102, 0x94000000ul, 6}, // 'f' 100101
164		{103, 0x98000000ul, 6}, // 'g' 100110
165		{104, 0x9c000000ul, 6}, // 'h' 100111
166		{105, 0x30000000ul, 5}, // 'i' 00110
167		{106, 0xe8000000ul, 7}, // 'j' 1110100
168		{107, 0xea000000ul, 7}, // 'k' 1110101
169		{108, 0xa0000000ul, 6}, // 'l' 101000
170		{109, 0xa4000000ul, 6}, // 'm' 101001
171		{110, 0xa8000000ul, 6}, // 'n' 101010
172		{111, 0x38000000ul, 5}, // 'o' 00111
173		{112, 0xac000000ul, 6}, // 'p' 101011
174		{113, 0xec000000ul, 7}, // 'q' 1110110
175		{114, 0xb0000000ul, 6}, // 'r' 101100
176		{115, 0x40000000ul, 5}, // 's' 01000
177		{116, 0x48000000ul, 5}, // 't' 01001
178		{117, 0xb4000000ul, 6}, // 'u' 101101
179		{118, 0xee000000ul, 7}, // 'v' 1110111
180		{119, 0xf0000000ul, 7}, // 'w' 1111000
181		{120, 0xf2000000ul, 7}, // 'x' 1111001
182		{121, 0xf4000000ul, 7}, // 'y' 1111010
183		{122, 0xf6000000ul, 7}, // 'z' 1111011
184		{123, 0xfffc0000ul, 15}, // '{' 11111111\|1111110
185		{124, 0xff800000ul, 11}, // '\|' 11111111\|100
186		{125, 0xfff40000ul, 14}, // '}' 11111111\|111101
187		{126, 0xffe80000ul, 13}, // '~' 11111111\|11101
188		{127, 0xffffffc0ul, 28}, // 11111111\|11111111\|11111111\|1100
189		{128, 0xfffe6000ul, 20}, // 11111111\|11111110\|0110
190		{129, 0xffff4800ul, 22}, // 11111111\|11111111\|010010
191		{130, 0xfffe7000ul, 20}, // 11111111\|11111110\|0111
192		{131, 0xfffe8000ul, 20}, // 11111111\|11111110\|1000
193		{132, 0xffff4c00ul, 22}, // 11111111\|11111111\|010011
194		{133, 0xffff5000ul, 22}, // 11111111\|11111111\|010100
195		{134, 0xffff5400ul, 22}, // 11111111\|11111111\|010101
196		{135, 0xffffb200ul, 23}, // 11111111\|11111111\|1011001
197		{136, 0xffff5800ul, 22}, // 11111111\|11111111\|010110
198		{137, 0xffffb400ul, 23}, // 11111111\|11111111\|1011010
199		{138, 0xffffb600ul, 23}, // 11111111\|11111111\|1011011
200		{139, 0xffffb800ul, 23}, // 11111111\|11111111\|1011100
201		{140, 0xffffba00ul, 23}, // 11111111\|11111111\|1011101
202		{141, 0xffffbc00ul, 23}, // 11111111\|11111111\|1011110
203		{142, 0xffffeb00ul, 24}, // 11111111\|11111111\|11101011
204		{143, 0xffffbe00ul, 23}, // 11111111\|11111111\|1011111
205		{144, 0xffffec00ul, 24}, // 11111111\|11111111\|11101100
206		{145, 0xffffed00ul, 24}, // 11111111\|11111111\|11101101
207		{146, 0xffff5c00ul, 22}, // 11111111\|11111111\|010111
208		{147, 0xffffc000ul, 23}, // 11111111\|11111111\|1100000
209		{148, 0xffffee00ul, 24}, // 11111111\|11111111\|11101110
210		{149, 0xffffc200ul, 23}, // 11111111\|11111111\|1100001
211		{150, 0xffffc400ul, 23}, // 11111111\|11111111\|1100010
212		{151, 0xffffc600ul, 23}, // 11111111\|11111111\|1100011
213		{152, 0xffffc800ul, 23}, // 11111111\|11111111\|1100100
214		{153, 0xfffee000ul, 21}, // 11111111\|11111110\|11100
215		{154, 0xffff6000ul, 22}, // 11111111\|11111111\|011000
216		{155, 0xffffca00ul, 23}, // 11111111\|11111111\|1100101
217		{156, 0xffff6400ul, 22}, // 11111111\|11111111\|011001
218		{157, 0xffffcc00ul, 23}, // 11111111\|11111111\|1100110
219		{158, 0xffffce00ul, 23}, // 11111111\|11111111\|1100111
220		{159, 0xffffef00ul, 24}, // 11111111\|11111111\|11101111
221		{160, 0xffff6800ul, 22}, // 11111111\|11111111\|011010
222		{161, 0xfffee800ul, 21}, // 11111111\|11111110\|11101
223		{162, 0xfffe9000ul, 20}, // 11111111\|11111110\|1001
224		{163, 0xffff6c00ul, 22}, // 11111111\|11111111\|011011
225		{164, 0xffff7000ul, 22}, // 11111111\|11111111\|011100
226		{165, 0xffffd000ul, 23}, // 11111111\|11111111\|1101000
227		{166, 0xffffd200ul, 23}, // 11111111\|11111111\|1101001
228		{167, 0xfffef000ul, 21}, // 11111111\|11111110\|11110
229		{168, 0xffffd400ul, 23}, // 11111111\|11111111\|1101010
230		{169, 0xffff7400ul, 22}, // 11111111\|11111111\|011101
231		{170, 0xffff7800ul, 22}, // 11111111\|11111111\|011110
232		{171, 0xfffff000ul, 24}, // 11111111\|11111111\|11110000
233		{172, 0xfffef800ul, 21}, // 11111111\|11111110\|11111
234		{173, 0xffff7c00ul, 22}, // 11111111\|11111111\|011111
235		{174, 0xffffd600ul, 23}, // 11111111\|11111111\|1101011
236		{175, 0xffffd800ul, 23}, // 11111111\|11111111\|1101100
237		{176, 0xffff0000ul, 21}, // 11111111\|11111111\|00000
238		{177, 0xffff0800ul, 21}, // 11111111\|11111111\|00001
239		{178, 0xffff8000ul, 22}, // 11111111\|11111111\|100000
240		{179, 0xffff1000ul, 21}, // 11111111\|11111111\|00010
241		{180, 0xffffda00ul, 23}, // 11111111\|11111111\|1101101
242		{181, 0xffff8400ul, 22}, // 11111111\|11111111\|100001
243		{182, 0xffffdc00ul, 23}, // 11111111\|11111111\|1101110
244		{183, 0xffffde00ul, 23}, // 11111111\|11111111\|1101111
245		{184, 0xfffea000ul, 20}, // 11111111\|11111110\|1010
246		{185, 0xffff8800ul, 22}, // 11111111\|11111111\|100010
247		{186, 0xffff8c00ul, 22}, // 11111111\|11111111\|100011
248		{187, 0xffff9000ul, 22}, // 11111111\|11111111\|100100
249		{188, 0xffffe000ul, 23}, // 11111111\|11111111\|1110000
250		{189, 0xffff9400ul, 22}, // 11111111\|11111111\|100101
251		{190, 0xffff9800ul, 22}, // 11111111\|11111111\|100110
252		{191, 0xffffe200ul, 23}, // 11111111\|11111111\|1110001
253		{192, 0xfffff800ul, 26}, // 11111111\|11111111\|11111000\|00
254		{193, 0xfffff840ul, 26}, // 11111111\|11111111\|11111000\|01
255		{194, 0xfffeb000ul, 20}, // 11111111\|11111110\|1011
256		{195, 0xfffe2000ul, 19}, // 11111111\|11111110\|001
257		{196, 0xffff9c00ul, 22}, // 11111111\|11111111\|100111
258		{197, 0xffffe400ul, 23}, // 11111111\|11111111\|1110010
259		{198, 0xffffa000ul, 22}, // 11111111\|11111111\|101000
260		{199, 0xfffff600ul, 25}, // 11111111\|11111111\|11110110\|0
261		{200, 0xfffff880ul, 26}, // 11111111\|11111111\|11111000\|10
262		{201, 0xfffff8c0ul, 26}, // 11111111\|11111111\|11111000\|11
263		{202, 0xfffff900ul, 26}, // 11111111\|11111111\|11111001\|00
264		{203, 0xfffffbc0ul, 27}, // 11111111\|11111111\|11111011\|110
265		{204, 0xfffffbe0ul, 27}, // 11111111\|11111111\|11111011\|111
266		{205, 0xfffff940ul, 26}, // 11111111\|11111111\|11111001\|01
267		{206, 0xfffff100ul, 24}, // 11111111\|11111111\|11110001
268		{207, 0xfffff680ul, 25}, // 11111111\|11111111\|11110110\|1
269		{208, 0xfffe4000ul, 19}, // 11111111\|11111110\|010
270		{209, 0xffff1800ul, 21}, // 11111111\|11111111\|00011
271		{210, 0xfffff980ul, 26}, // 11111111\|11111111\|11111001\|10
272		{211, 0xfffffc00ul, 27}, // 11111111\|11111111\|11111100\|000
273		{212, 0xfffffc20ul, 27}, // 11111111\|11111111\|11111100\|001
274		{213, 0xfffff9c0ul, 26}, // 11111111\|11111111\|11111001\|11
275		{214, 0xfffffc40ul, 27}, // 11111111\|11111111\|11111100\|010
276		{215, 0xfffff200ul, 24}, // 11111111\|11111111\|11110010
277		{216, 0xffff2000ul, 21}, // 11111111\|11111111\|00100
278		{217, 0xffff2800ul, 21}, // 11111111\|11111111\|00101
279		{218, 0xfffffa00ul, 26}, // 11111111\|11111111\|11111010\|00
280		{219, 0xfffffa40ul, 26}, // 11111111\|11111111\|11111010\|01
281		{220, 0xffffffd0ul, 28}, // 11111111\|11111111\|11111111\|1101
282		{221, 0xfffffc60ul, 27}, // 11111111\|11111111\|11111100\|011
283		{222, 0xfffffc80ul, 27}, // 11111111\|11111111\|11111100\|100
284		{223, 0xfffffca0ul, 27}, // 11111111\|11111111\|11111100\|101
285		{224, 0xfffec000ul, 20}, // 11111111\|11111110\|1100
286		{225, 0xfffff300ul, 24}, // 11111111\|11111111\|11110011
287		{226, 0xfffed000ul, 20}, // 11111111\|11111110\|1101
288		{227, 0xffff3000ul, 21}, // 11111111\|11111111\|00110
289		{228, 0xffffa400ul, 22}, // 11111111\|11111111\|101001
290		{229, 0xffff3800ul, 21}, // 11111111\|11111111\|00111
291		{230, 0xffff4000ul, 21}, // 11111111\|11111111\|01000
292		{231, 0xffffe600ul, 23}, // 11111111\|11111111\|1110011
293		{232, 0xffffa800ul, 22}, // 11111111\|11111111\|101010
294		{233, 0xffffac00ul, 22}, // 11111111\|11111111\|101011
295		{234, 0xfffff700ul, 25}, // 11111111\|11111111\|11110111\|0
296		{235, 0xfffff780ul, 25}, // 11111111\|11111111\|11110111\|1
297		{236, 0xfffff400ul, 24}, // 11111111\|11111111\|11110100
298		{237, 0xfffff500ul, 24}, // 11111111\|11111111\|11110101
299		{238, 0xfffffa80ul, 26}, // 11111111\|11111111\|11111010\|10
300		{239, 0xffffe800ul, 23}, // 11111111\|11111111\|1110100
301		{240, 0xfffffac0ul, 26}, // 11111111\|11111111\|11111010\|11
302		{241, 0xfffffcc0ul, 27}, // 11111111\|11111111\|11111100\|110
303		{242, 0xfffffb00ul, 26}, // 11111111\|11111111\|11111011\|00
304		{243, 0xfffffb40ul, 26}, // 11111111\|11111111\|11111011\|01
305		{244, 0xfffffce0ul, 27}, // 11111111\|11111111\|11111100\|111
306		{245, 0xfffffd00ul, 27}, // 11111111\|11111111\|11111101\|000
307		{246, 0xfffffd20ul, 27}, // 11111111\|11111111\|11111101\|001
308		{247, 0xfffffd40ul, 27}, // 11111111\|11111111\|11111101\|010
309		{248, 0xfffffd60ul, 27}, // 11111111\|11111111\|11111101\|011
310		{249, 0xffffffe0ul, 28}, // 11111111\|11111111\|11111111\|1110
311		{250, 0xfffffd80ul, 27}, // 11111111\|11111111\|11111101\|100
312		{251, 0xfffffda0ul, 27}, // 11111111\|11111111\|11111101\|101
313		{252, 0xfffffdc0ul, 27}, // 11111111\|11111111\|11111101\|110
314		{253, 0xfffffde0ul, 27}, // 11111111\|11111111\|11111101\|111
315		{254, 0xfffffe00ul, 27}, // 11111111\|11111111\|11111110\|000
316		{255, 0xfffffb80ul, 26}, // 11111111\|11111111\|11111011\|10
317		{256, 0xfffffffcul, 30} // EOS 11111111\|11111111\|11111111\|111111
318		};
319
320		void write_huffman_code(BitOStream &outputStream, CodeEntry code)
321	0	{
322		// Append octet by octet.
323	0	auto bitLength = code.bitLength;
324	0	const auto hc = code.huffmanCode >> (32 - bitLength);
325
326	0	if (bitLength > 24) {
327	0	outputStream.writeBits(uchar(hc >> 24), bitLength - 24);
328	0	bitLength = 24;
329	0	}
330
331	0	if (bitLength > 16) {
332	0	outputStream.writeBits(uchar(hc >> 16), bitLength - 16);
333	0	bitLength = 16;
334	0	}
335
336	0	if (bitLength > 8) {
337	0	outputStream.writeBits(uchar(hc >> 8), bitLength - 8);
338	0	bitLength = 8;
339	0	}
340
341	0	outputStream.writeBits(uchar(hc), bitLength);
342	0	}
343
344		}
345
346		// That's from HPACK's specs - we deal with octets.
347		static_assert(std::numeric_limits<uchar>::digits == 8, "octets expected");
348
349		quint64 huffman_encoded_bit_length(QByteArrayView inputData)
350	0	{
351	0	quint64 bitLength = 0;
352	0	for (int i = 0, e = inputData.size(); i < e; ++i)
353	0	bitLength += staticHuffmanCodeTable[int(inputData[i])].bitLength;
354
355	0	return bitLength;
356	0	}
357
358		void huffman_encode_string(QByteArrayView inputData, BitOStream &outputStream)
359	0	{
360	0	for (int i = 0, e = inputData.size(); i < e; ++i) {
361	0	const auto value = uchar(inputData[i]);
362	0	write_huffman_code(outputStream, staticHuffmanCodeTable[value]);
363	0	}
364
365		// Pad bits ...
366	0	if (outputStream.bitLength() % 8)
367	0	outputStream.writeBits(0xff, 8 - outputStream.bitLength() % 8);
368	0	}
369
370		static constexpr
371		bool padding_is_valid(quint32 chunk, quint32 nBits)
372	0	{
373	0	Q_ASSERT(nBits);
374
375		// HPACK, 5.2: "A padding strictly longer than 7 bits MUST be
376		// treated as a decoding error."
377	0	if (nBits > 7)
378	0	return false;
379		// HPACK, 5.2:
380		// "A padding not corresponding to the most significant bits
381		// of the code for the EOS symbol MUST be treated as a decoding error."
382	0	return (chunk >> (32 - nBits)) == quint32((1 << nBits) - 1);
383	0	}
384
385		HuffmanDecoder::HuffmanDecoder()
386		: minCodeLength()
387	0	{
388	0	const auto nCodes = sizeof staticHuffmanCodeTable / sizeof staticHuffmanCodeTable[0];
389
390	0	std::vector<CodeEntry> symbols(staticHuffmanCodeTable, staticHuffmanCodeTable + nCodes);
391		// Now we sort: by bit length first (in the descending order) and by the symbol
392		// value (descending). Descending order: to make sure we do not create prefix tables with
393		// short 'indexLength' first and having longer codes that do not fit into such tables later.
394	0	std::sort(symbols.begin(), symbols.end(), [](CodeEntry code1, CodeEntry code2) {
395	0	if (code1.bitLength == code2.bitLength)
396	0	return code1.byteValue > code2.byteValue;
397	0	return code1.bitLength > code2.bitLength;
398	0	});
399
400	0	minCodeLength = symbols.back().bitLength; // The shortest one, currently it's 5.
401
402		// TODO: add a verification - Huffman codes
403		// within a given bit length range also
404		// should be in descending order.
405
406		// Initialize 'prefixTables' and 'tableData'.
407	0	addTable(0, quint32(BitConstants::rootPrefix)); // 'root' table.
408
409	0	for (const auto &s : symbols) {
410	0	quint32 tableIndex = 0;
411	0	while (true) {
412	0	Q_ASSERT(tableIndex < prefixTables.size());
413		// Note, by value - since prefixTables will be updated in between.
414	0	const auto table = prefixTables[tableIndex];
415		// We skip prefixed bits (if any) and use indexed bits only:
416	0	const auto entryIndex = s.huffmanCode << table.prefixLength >> (32 - table.indexLength);
417		// Again, by value.
418	0	PrefixTableEntry entry = tableEntry(table, entryIndex);
419		// How many bits were coded by previous tables and this table:
420	0	const auto codedLength = table.prefixLength + table.indexLength;
421	0	if (codedLength < s.bitLength) {
422		// We have to add a new prefix table ... (if it's not done yet).
423	0	if (!entry.bitLength) {
424	0	entry.nextTable = addTable(codedLength, std::min<quint32>(quint32(BitConstants::childPrefix),
425	0	s.bitLength - codedLength));
426	0	entry.bitLength = s.bitLength;
427	0	entry.byteValue = s.byteValue;
428	0	setTableEntry(table, entryIndex, entry);
429	0	}
430	0	tableIndex = entry.nextTable;
431	0	} else {
432		// We found the slot for our code (terminal entry):
433	0	entry.byteValue = s.byteValue;
434	0	entry.bitLength = s.bitLength;
435		// Refer to our own table as 'nextTable':
436	0	entry.nextTable = tableIndex;
437	0	setTableEntry(table, entryIndex, entry);
438	0	break;
439	0	}
440	0	}
441	0	}
442
443		// Now, we have a table(s) and have to fill 'holes' to
444		// 'fix' terminal entries.
445	0	for (const auto &table : prefixTables) {
446	0	const quint32 codedLength = table.prefixLength + table.indexLength;
447	0	for (quint32 j = 0; j < table.size();) {
448	0	const PrefixTableEntry &entry = tableEntry(table, j);
449	0	if (entry.bitLength && entry.bitLength < codedLength) {
450	0	const quint32 range = 1 << (codedLength - entry.bitLength);
451	0	for (quint32 k = 1; k < range; ++k)
452	0	setTableEntry(table, j + k, entry);
453	0	j += range;
454	0	} else {
455	0	++j;
456	0	}
457	0	}
458	0	}
459	0	}
460
461		bool HuffmanDecoder::decodeStream(BitIStream &inputStream, QByteArray &outputBuffer)
462	0	{
463	0	while (true) {
464	0	quint32 chunk = 0;
465	0	const quint32 readBits = inputStream.peekBits(inputStream.streamOffset(), 32, &chunk);
466	0	if (!readBits)
467	0	return !inputStream.hasMoreBits();
468
469	0	if (readBits < minCodeLength) {
470	0	inputStream.skipBits(readBits);
471	0	return padding_is_valid(chunk, readBits);
472	0	}
473
474	0	quint32 tableIndex = 0;
475	0	const PrefixTable *table = &prefixTables[tableIndex];
476	0	quint32 entryIndex = chunk >> (32 - table->indexLength);
477	0	PrefixTableEntry entry = tableEntry(*table, entryIndex);
478
479	0	while (true) {
480	0	if (entry.nextTable == tableIndex)
481	0	break;
482
483	0	tableIndex = entry.nextTable;
484	0	table = &prefixTables[tableIndex];
485	0	entryIndex = chunk << table->prefixLength >> (32 - table->indexLength);
486	0	entry = tableEntry(*table, entryIndex);
487	0	}
488
489	0	if (entry.bitLength > readBits) {
490	0	inputStream.skipBits(readBits);
491	0	return padding_is_valid(chunk, readBits);
492	0	}
493
494	0	if (!entry.bitLength \|\| entry.byteValue == 256) {
495		//EOS (256) == compression error (HPACK).
496	0	inputStream.skipBits(readBits);
497	0	return false;
498	0	}
499
500	0	outputBuffer.append(entry.byteValue);
501	0	inputStream.skipBits(entry.bitLength);
502	0	}
503
504	0	return false;
505	0	}
506
507		quint32 HuffmanDecoder::addTable(quint32 prefix, quint32 index)
508	0	{
509	0	PrefixTable newTable{prefix, index};
510	0	newTable.offset = quint32(tableData.size());
511	0	prefixTables.push_back(newTable);
512		// Add entries for this table:
513	0	tableData.resize(tableData.size() + newTable.size());
514
515	0	return quint32(prefixTables.size() - 1);
516	0	}
517
518		PrefixTableEntry HuffmanDecoder::tableEntry(PrefixTable table, quint32 index)
519	0	{
520	0	Q_ASSERT(index < table.size());
521	0	return tableData[table.offset + index];
522	0	}
523
524		void HuffmanDecoder::setTableEntry(PrefixTable table, quint32 index,
525		PrefixTableEntry entry)
526	0	{
527	0	Q_ASSERT(index < table.size());
528	0	tableData[table.offset + index] = entry;
529	0	}
530
531		bool huffman_decode_string(BitIStream &inputStream, QByteArray *outputBuffer)
532	0	{
533	0	Q_ASSERT(outputBuffer);
534
535	0	static HuffmanDecoder decoder;
536	0	return decoder.decodeStream(inputStream, *outputBuffer);
537	0	}
538
539		}
540
541		QT_END_NAMESPACE

Coverage Report

Created: 2026-08-17 07:50