| /**************************************************************************** |
| ** |
| ** Copyright (C) 2016 The Qt Company Ltd. |
| ** Contact: https://www.qt.io/licensing/ |
| ** |
| ** This file is part of the QtNetwork module of the Qt Toolkit. |
| ** |
| ** $QT_BEGIN_LICENSE:LGPL$ |
| ** Commercial License Usage |
| ** Licensees holding valid commercial Qt licenses may use this file in |
| ** accordance with the commercial license agreement provided with the |
| ** Software or, alternatively, in accordance with the terms contained in |
| ** a written agreement between you and The Qt Company. For licensing terms |
| ** and conditions see https://www.qt.io/terms-conditions. For further |
| ** information use the contact form at https://www.qt.io/contact-us. |
| ** |
| ** GNU Lesser General Public License Usage |
| ** Alternatively, this file may be used under the terms of the GNU Lesser |
| ** General Public License version 3 as published by the Free Software |
| ** Foundation and appearing in the file LICENSE.LGPL3 included in the |
| ** packaging of this file. Please review the following information to |
| ** ensure the GNU Lesser General Public License version 3 requirements |
| ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. |
| ** |
| ** GNU General Public License Usage |
| ** Alternatively, this file may be used under the terms of the GNU |
| ** General Public License version 2.0 or (at your option) the GNU General |
| ** Public license version 3 or any later version approved by the KDE Free |
| ** Qt Foundation. The licenses are as published by the Free Software |
| ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 |
| ** included in the packaging of this file. Please review the following |
| ** information to ensure the GNU General Public License requirements will |
| ** be met: https://www.gnu.org/licenses/gpl-2.0.html and |
| ** https://www.gnu.org/licenses/gpl-3.0.html. |
| ** |
| ** $QT_END_LICENSE$ |
| ** |
| ****************************************************************************/ |
| |
| #include "bitstreams_p.h" |
| #include "huffman_p.h" |
| |
| #include <QtCore/qbytearray.h> |
| |
| #include <algorithm> |
| #include <limits> |
| |
| QT_BEGIN_NAMESPACE |
| |
| namespace HPack |
| { |
| |
| /* |
| The static Huffman code used here was extracted from: |
| https://http2.github.io/http2-spec/compression.html#huffman.code |
| |
| This code was generated from statistics obtained on a large |
| sample of HTTP headers. It is a canonical Huffman code |
| with some tweaking to ensure that no symbol has a unique |
| code length. All codes were left-aligned - for implementation |
| convenience. |
| |
| Using binary trees to implement decoding would be prohibitively |
| expensive (both memory and time-wise). Instead we use a table-based |
| approach and any given code itself works as an index into such table(s). |
| We have 256 possible byte values and code lengths in |
| a range [5, 26]. This would require a huge table (and most of entries |
| would be 'wasted', since we only have to encode 256 elements). |
| Instead we use multi-level tables. The first level table |
| is using 9-bit length index; some entries in this table are 'terminal', |
| some reference the next level table(s). |
| |
| For example, bytes with values 48 and 49 (ASCII codes for '0' and '1') |
| both have code length 5, Huffman codes are: 00000 and 00001. They |
| both are placed in the 'root' table, |
| the 'root' table has index length == 9: |
| [00000 | 4 remaining bits] |
| ... |
| [00001 | 4 remaining bits] |
| |
| All entires with indices between these two will 'point' to value 48 |
| with bitLength == 5 so that bit stream (for example) 000001010 will be |
| decoded as: 48 + "put 1010 back into bitstream". |
| |
| A good description can be found here: |
| http://commandlinefanatic.com/cgi-bin/showarticle.cgi?article=art007 |
| or just google "Efficient Huffman Decoding". |
| Also see comments below about 'filling holes'. |
| */ |
| |
| namespace |
| { |
| |
| const CodeEntry staticHuffmanCodeTable[] |
| { |
| { 0, 0xffc00000ul, 13}, // 11111111|11000 |
| { 1, 0xffffb000ul, 23}, // 11111111|11111111|1011000 |
| { 2, 0xfffffe20ul, 28}, // 11111111|11111111|11111110|0010 |
| { 3, 0xfffffe30ul, 28}, // 11111111|11111111|11111110|0011 |
| { 4, 0xfffffe40ul, 28}, // 11111111|11111111|11111110|0100 |
| { 5, 0xfffffe50ul, 28}, // 11111111|11111111|11111110|0101 |
| { 6, 0xfffffe60ul, 28}, // 11111111|11111111|11111110|0110 |
| { 7, 0xfffffe70ul, 28}, // 11111111|11111111|11111110|0111 |
| { 8, 0xfffffe80ul, 28}, // 11111111|11111111|11111110|1000 |
| { 9, 0xffffea00ul, 24}, // 11111111|11111111|11101010 |
| { 10, 0xfffffff0ul, 30}, // 11111111|11111111|11111111|111100 |
| { 11, 0xfffffe90ul, 28}, // 11111111|11111111|11111110|1001 |
| { 12, 0xfffffea0ul, 28}, // 11111111|11111111|11111110|1010 |
| { 13, 0xfffffff4ul, 30}, // 11111111|11111111|11111111|111101 |
| { 14, 0xfffffeb0ul, 28}, // 11111111|11111111|11111110|1011 |
| { 15, 0xfffffec0ul, 28}, // 11111111|11111111|11111110|1100 |
| { 16, 0xfffffed0ul, 28}, // 11111111|11111111|11111110|1101 |
| { 17, 0xfffffee0ul, 28}, // 11111111|11111111|11111110|1110 |
| { 18, 0xfffffef0ul, 28}, // 11111111|11111111|11111110|1111 |
| { 19, 0xffffff00ul, 28}, // 11111111|11111111|11111111|0000 |
| { 20, 0xffffff10ul, 28}, // 11111111|11111111|11111111|0001 |
| { 21, 0xffffff20ul, 28}, // 11111111|11111111|11111111|0010 |
| { 22, 0xfffffff8ul, 30}, // 11111111|11111111|11111111|111110 |
| { 23, 0xffffff30ul, 28}, // 11111111|11111111|11111111|0011 |
| { 24, 0xffffff40ul, 28}, // 11111111|11111111|11111111|0100 |
| { 25, 0xffffff50ul, 28}, // 11111111|11111111|11111111|0101 |
| { 26, 0xffffff60ul, 28}, // 11111111|11111111|11111111|0110 |
| { 27, 0xffffff70ul, 28}, // 11111111|11111111|11111111|0111 |
| { 28, 0xffffff80ul, 28}, // 11111111|11111111|11111111|1000 |
| { 29, 0xffffff90ul, 28}, // 11111111|11111111|11111111|1001 |
| { 30, 0xffffffa0ul, 28}, // 11111111|11111111|11111111|1010 |
| { 31, 0xffffffb0ul, 28}, // 11111111|11111111|11111111|1011 |
| { 32, 0x50000000ul, 6}, // ' ' 010100 |
| { 33, 0xfe000000ul, 10}, // '!' 11111110|00 |
| { 34, 0xfe400000ul, 10}, // '"' 11111110|01 |
| { 35, 0xffa00000ul, 12}, // '#' 11111111|1010 |
| { 36, 0xffc80000ul, 13}, // '$' 11111111|11001 |
| { 37, 0x54000000ul, 6}, // '%' 010101 |
| { 38, 0xf8000000ul, 8}, // '&' 11111000 |
| { 39, 0xff400000ul, 11}, // ''' 11111111|010 |
| { 40, 0xfe800000ul, 10}, // '(' 11111110|10 |
| { 41, 0xfec00000ul, 10}, // ')' 11111110|11 |
| { 42, 0xf9000000ul, 8}, // '*' 11111001 |
| { 43, 0xff600000ul, 11}, // '+' 11111111|011 |
| { 44, 0xfa000000ul, 8}, // ',' 11111010 |
| { 45, 0x58000000ul, 6}, // '-' 010110 |
| { 46, 0x5c000000ul, 6}, // '.' 010111 |
| { 47, 0x60000000ul, 6}, // '/' 011000 |
| { 48, 0x00000000ul, 5}, // '0' 00000 |
| { 49, 0x08000000ul, 5}, // '1' 00001 |
| { 50, 0x10000000ul, 5}, // '2' 00010 |
| { 51, 0x64000000ul, 6}, // '3' 011001 |
| { 52, 0x68000000ul, 6}, // '4' 011010 |
| { 53, 0x6c000000ul, 6}, // '5' 011011 |
| { 54, 0x70000000ul, 6}, // '6' 011100 |
| { 55, 0x74000000ul, 6}, // '7' 011101 |
| { 56, 0x78000000ul, 6}, // '8' 011110 |
| { 57, 0x7c000000ul, 6}, // '9' 011111 |
| { 58, 0xb8000000ul, 7}, // ':' 1011100 |
| { 59, 0xfb000000ul, 8}, // ';' 11111011 |
| { 60, 0xfff80000ul, 15}, // '<' 11111111|1111100 |
| { 61, 0x80000000ul, 6}, // '=' 100000 |
| { 62, 0xffb00000ul, 12}, // '>' 11111111|1011 |
| { 63, 0xff000000ul, 10}, // '?' 11111111|00 |
| { 64, 0xffd00000ul, 13}, // '@' 11111111|11010 |
| { 65, 0x84000000ul, 6}, // 'A' 100001 |
| { 66, 0xba000000ul, 7}, // 'B' 1011101 |
| { 67, 0xbc000000ul, 7}, // 'C' 1011110 |
| { 68, 0xbe000000ul, 7}, // 'D' 1011111 |
| { 69, 0xc0000000ul, 7}, // 'E' 1100000 |
| { 70, 0xc2000000ul, 7}, // 'F' 1100001 |
| { 71, 0xc4000000ul, 7}, // 'G' 1100010 |
| { 72, 0xc6000000ul, 7}, // 'H' 1100011 |
| { 73, 0xc8000000ul, 7}, // 'I' 1100100 |
| { 74, 0xca000000ul, 7}, // 'J' 1100101 |
| { 75, 0xcc000000ul, 7}, // 'K' 1100110 |
| { 76, 0xce000000ul, 7}, // 'L' 1100111 |
| { 77, 0xd0000000ul, 7}, // 'M' 1101000 |
| { 78, 0xd2000000ul, 7}, // 'N' 1101001 |
| { 79, 0xd4000000ul, 7}, // 'O' 1101010 |
| { 80, 0xd6000000ul, 7}, // 'P' 1101011 |
| { 81, 0xd8000000ul, 7}, // 'Q' 1101100 |
| { 82, 0xda000000ul, 7}, // 'R' 1101101 |
| { 83, 0xdc000000ul, 7}, // 'S' 1101110 |
| { 84, 0xde000000ul, 7}, // 'T' 1101111 |
| { 85, 0xe0000000ul, 7}, // 'U' 1110000 |
| { 86, 0xe2000000ul, 7}, // 'V' 1110001 |
| { 87, 0xe4000000ul, 7}, // 'W' 1110010 |
| { 88, 0xfc000000ul, 8}, // 'X' 11111100 |
| { 89, 0xe6000000ul, 7}, // 'Y' 1110011 |
| { 90, 0xfd000000ul, 8}, // 'Z' 11111101 |
| { 91, 0xffd80000ul, 13}, // '[' 11111111|11011 |
| { 92, 0xfffe0000ul, 19}, // '\' 11111111|11111110|000 |
| { 93, 0xffe00000ul, 13}, // ']' 11111111|11100 |
| { 94, 0xfff00000ul, 14}, // '^' 11111111|111100 |
| { 95, 0x88000000ul, 6}, // '_' 100010 |
| { 96, 0xfffa0000ul, 15}, // '`' 11111111|1111101 |
| { 97, 0x18000000ul, 5}, // 'a' 00011 |
| { 98, 0x8c000000ul, 6}, // 'b' 100011 |
| { 99, 0x20000000ul, 5}, // 'c' 00100 |
| {100, 0x90000000ul, 6}, // 'd' 100100 |
| {101, 0x28000000ul, 5}, // 'e' 00101 |
| {102, 0x94000000ul, 6}, // 'f' 100101 |
| {103, 0x98000000ul, 6}, // 'g' 100110 |
| {104, 0x9c000000ul, 6}, // 'h' 100111 |
| {105, 0x30000000ul, 5}, // 'i' 00110 |
| {106, 0xe8000000ul, 7}, // 'j' 1110100 |
| {107, 0xea000000ul, 7}, // 'k' 1110101 |
| {108, 0xa0000000ul, 6}, // 'l' 101000 |
| {109, 0xa4000000ul, 6}, // 'm' 101001 |
| {110, 0xa8000000ul, 6}, // 'n' 101010 |
| {111, 0x38000000ul, 5}, // 'o' 00111 |
| {112, 0xac000000ul, 6}, // 'p' 101011 |
| {113, 0xec000000ul, 7}, // 'q' 1110110 |
| {114, 0xb0000000ul, 6}, // 'r' 101100 |
| {115, 0x40000000ul, 5}, // 's' 01000 |
| {116, 0x48000000ul, 5}, // 't' 01001 |
| {117, 0xb4000000ul, 6}, // 'u' 101101 |
| {118, 0xee000000ul, 7}, // 'v' 1110111 |
| {119, 0xf0000000ul, 7}, // 'w' 1111000 |
| {120, 0xf2000000ul, 7}, // 'x' 1111001 |
| {121, 0xf4000000ul, 7}, // 'y' 1111010 |
| {122, 0xf6000000ul, 7}, // 'z' 1111011 |
| {123, 0xfffc0000ul, 15}, // '{' 11111111|1111110 |
| {124, 0xff800000ul, 11}, // '|' 11111111|100 |
| {125, 0xfff40000ul, 14}, // '}' 11111111|111101 |
| {126, 0xffe80000ul, 13}, // '~' 11111111|11101 |
| {127, 0xffffffc0ul, 28}, // 11111111|11111111|11111111|1100 |
| {128, 0xfffe6000ul, 20}, // 11111111|11111110|0110 |
| {129, 0xffff4800ul, 22}, // 11111111|11111111|010010 |
| {130, 0xfffe7000ul, 20}, // 11111111|11111110|0111 |
| {131, 0xfffe8000ul, 20}, // 11111111|11111110|1000 |
| {132, 0xffff4c00ul, 22}, // 11111111|11111111|010011 |
| {133, 0xffff5000ul, 22}, // 11111111|11111111|010100 |
| {134, 0xffff5400ul, 22}, // 11111111|11111111|010101 |
| {135, 0xffffb200ul, 23}, // 11111111|11111111|1011001 |
| {136, 0xffff5800ul, 22}, // 11111111|11111111|010110 |
| {137, 0xffffb400ul, 23}, // 11111111|11111111|1011010 |
| {138, 0xffffb600ul, 23}, // 11111111|11111111|1011011 |
| {139, 0xffffb800ul, 23}, // 11111111|11111111|1011100 |
| {140, 0xffffba00ul, 23}, // 11111111|11111111|1011101 |
| {141, 0xffffbc00ul, 23}, // 11111111|11111111|1011110 |
| {142, 0xffffeb00ul, 24}, // 11111111|11111111|11101011 |
| {143, 0xffffbe00ul, 23}, // 11111111|11111111|1011111 |
| {144, 0xffffec00ul, 24}, // 11111111|11111111|11101100 |
| {145, 0xffffed00ul, 24}, // 11111111|11111111|11101101 |
| {146, 0xffff5c00ul, 22}, // 11111111|11111111|010111 |
| {147, 0xffffc000ul, 23}, // 11111111|11111111|1100000 |
| {148, 0xffffee00ul, 24}, // 11111111|11111111|11101110 |
| {149, 0xffffc200ul, 23}, // 11111111|11111111|1100001 |
| {150, 0xffffc400ul, 23}, // 11111111|11111111|1100010 |
| {151, 0xffffc600ul, 23}, // 11111111|11111111|1100011 |
| {152, 0xffffc800ul, 23}, // 11111111|11111111|1100100 |
| {153, 0xfffee000ul, 21}, // 11111111|11111110|11100 |
| {154, 0xffff6000ul, 22}, // 11111111|11111111|011000 |
| {155, 0xffffca00ul, 23}, // 11111111|11111111|1100101 |
| {156, 0xffff6400ul, 22}, // 11111111|11111111|011001 |
| {157, 0xffffcc00ul, 23}, // 11111111|11111111|1100110 |
| {158, 0xffffce00ul, 23}, // 11111111|11111111|1100111 |
| {159, 0xffffef00ul, 24}, // 11111111|11111111|11101111 |
| {160, 0xffff6800ul, 22}, // 11111111|11111111|011010 |
| {161, 0xfffee800ul, 21}, // 11111111|11111110|11101 |
| {162, 0xfffe9000ul, 20}, // 11111111|11111110|1001 |
| {163, 0xffff6c00ul, 22}, // 11111111|11111111|011011 |
| {164, 0xffff7000ul, 22}, // 11111111|11111111|011100 |
| {165, 0xffffd000ul, 23}, // 11111111|11111111|1101000 |
| {166, 0xffffd200ul, 23}, // 11111111|11111111|1101001 |
| {167, 0xfffef000ul, 21}, // 11111111|11111110|11110 |
| {168, 0xffffd400ul, 23}, // 11111111|11111111|1101010 |
| {169, 0xffff7400ul, 22}, // 11111111|11111111|011101 |
| {170, 0xffff7800ul, 22}, // 11111111|11111111|011110 |
| {171, 0xfffff000ul, 24}, // 11111111|11111111|11110000 |
| {172, 0xfffef800ul, 21}, // 11111111|11111110|11111 |
| {173, 0xffff7c00ul, 22}, // 11111111|11111111|011111 |
| {174, 0xffffd600ul, 23}, // 11111111|11111111|1101011 |
| {175, 0xffffd800ul, 23}, // 11111111|11111111|1101100 |
| {176, 0xffff0000ul, 21}, // 11111111|11111111|00000 |
| {177, 0xffff0800ul, 21}, // 11111111|11111111|00001 |
| {178, 0xffff8000ul, 22}, // 11111111|11111111|100000 |
| {179, 0xffff1000ul, 21}, // 11111111|11111111|00010 |
| {180, 0xffffda00ul, 23}, // 11111111|11111111|1101101 |
| {181, 0xffff8400ul, 22}, // 11111111|11111111|100001 |
| {182, 0xffffdc00ul, 23}, // 11111111|11111111|1101110 |
| {183, 0xffffde00ul, 23}, // 11111111|11111111|1101111 |
| {184, 0xfffea000ul, 20}, // 11111111|11111110|1010 |
| {185, 0xffff8800ul, 22}, // 11111111|11111111|100010 |
| {186, 0xffff8c00ul, 22}, // 11111111|11111111|100011 |
| {187, 0xffff9000ul, 22}, // 11111111|11111111|100100 |
| {188, 0xffffe000ul, 23}, // 11111111|11111111|1110000 |
| {189, 0xffff9400ul, 22}, // 11111111|11111111|100101 |
| {190, 0xffff9800ul, 22}, // 11111111|11111111|100110 |
| {191, 0xffffe200ul, 23}, // 11111111|11111111|1110001 |
| {192, 0xfffff800ul, 26}, // 11111111|11111111|11111000|00 |
| {193, 0xfffff840ul, 26}, // 11111111|11111111|11111000|01 |
| {194, 0xfffeb000ul, 20}, // 11111111|11111110|1011 |
| {195, 0xfffe2000ul, 19}, // 11111111|11111110|001 |
| {196, 0xffff9c00ul, 22}, // 11111111|11111111|100111 |
| {197, 0xffffe400ul, 23}, // 11111111|11111111|1110010 |
| {198, 0xffffa000ul, 22}, // 11111111|11111111|101000 |
| {199, 0xfffff600ul, 25}, // 11111111|11111111|11110110|0 |
| {200, 0xfffff880ul, 26}, // 11111111|11111111|11111000|10 |
| {201, 0xfffff8c0ul, 26}, // 11111111|11111111|11111000|11 |
| {202, 0xfffff900ul, 26}, // 11111111|11111111|11111001|00 |
| {203, 0xfffffbc0ul, 27}, // 11111111|11111111|11111011|110 |
| {204, 0xfffffbe0ul, 27}, // 11111111|11111111|11111011|111 |
| {205, 0xfffff940ul, 26}, // 11111111|11111111|11111001|01 |
| {206, 0xfffff100ul, 24}, // 11111111|11111111|11110001 |
| {207, 0xfffff680ul, 25}, // 11111111|11111111|11110110|1 |
| {208, 0xfffe4000ul, 19}, // 11111111|11111110|010 |
| {209, 0xffff1800ul, 21}, // 11111111|11111111|00011 |
| {210, 0xfffff980ul, 26}, // 11111111|11111111|11111001|10 |
| {211, 0xfffffc00ul, 27}, // 11111111|11111111|11111100|000 |
| {212, 0xfffffc20ul, 27}, // 11111111|11111111|11111100|001 |
| {213, 0xfffff9c0ul, 26}, // 11111111|11111111|11111001|11 |
| {214, 0xfffffc40ul, 27}, // 11111111|11111111|11111100|010 |
| {215, 0xfffff200ul, 24}, // 11111111|11111111|11110010 |
| {216, 0xffff2000ul, 21}, // 11111111|11111111|00100 |
| {217, 0xffff2800ul, 21}, // 11111111|11111111|00101 |
| {218, 0xfffffa00ul, 26}, // 11111111|11111111|11111010|00 |
| {219, 0xfffffa40ul, 26}, // 11111111|11111111|11111010|01 |
| {220, 0xffffffd0ul, 28}, // 11111111|11111111|11111111|1101 |
| {221, 0xfffffc60ul, 27}, // 11111111|11111111|11111100|011 |
| {222, 0xfffffc80ul, 27}, // 11111111|11111111|11111100|100 |
| {223, 0xfffffca0ul, 27}, // 11111111|11111111|11111100|101 |
| {224, 0xfffec000ul, 20}, // 11111111|11111110|1100 |
| {225, 0xfffff300ul, 24}, // 11111111|11111111|11110011 |
| {226, 0xfffed000ul, 20}, // 11111111|11111110|1101 |
| {227, 0xffff3000ul, 21}, // 11111111|11111111|00110 |
| {228, 0xffffa400ul, 22}, // 11111111|11111111|101001 |
| {229, 0xffff3800ul, 21}, // 11111111|11111111|00111 |
| {230, 0xffff4000ul, 21}, // 11111111|11111111|01000 |
| {231, 0xffffe600ul, 23}, // 11111111|11111111|1110011 |
| {232, 0xffffa800ul, 22}, // 11111111|11111111|101010 |
| {233, 0xffffac00ul, 22}, // 11111111|11111111|101011 |
| {234, 0xfffff700ul, 25}, // 11111111|11111111|11110111|0 |
| {235, 0xfffff780ul, 25}, // 11111111|11111111|11110111|1 |
| {236, 0xfffff400ul, 24}, // 11111111|11111111|11110100 |
| {237, 0xfffff500ul, 24}, // 11111111|11111111|11110101 |
| {238, 0xfffffa80ul, 26}, // 11111111|11111111|11111010|10 |
| {239, 0xffffe800ul, 23}, // 11111111|11111111|1110100 |
| {240, 0xfffffac0ul, 26}, // 11111111|11111111|11111010|11 |
| {241, 0xfffffcc0ul, 27}, // 11111111|11111111|11111100|110 |
| {242, 0xfffffb00ul, 26}, // 11111111|11111111|11111011|00 |
| {243, 0xfffffb40ul, 26}, // 11111111|11111111|11111011|01 |
| {244, 0xfffffce0ul, 27}, // 11111111|11111111|11111100|111 |
| {245, 0xfffffd00ul, 27}, // 11111111|11111111|11111101|000 |
| {246, 0xfffffd20ul, 27}, // 11111111|11111111|11111101|001 |
| {247, 0xfffffd40ul, 27}, // 11111111|11111111|11111101|010 |
| {248, 0xfffffd60ul, 27}, // 11111111|11111111|11111101|011 |
| {249, 0xffffffe0ul, 28}, // 11111111|11111111|11111111|1110 |
| {250, 0xfffffd80ul, 27}, // 11111111|11111111|11111101|100 |
| {251, 0xfffffda0ul, 27}, // 11111111|11111111|11111101|101 |
| {252, 0xfffffdc0ul, 27}, // 11111111|11111111|11111101|110 |
| {253, 0xfffffde0ul, 27}, // 11111111|11111111|11111101|111 |
| {254, 0xfffffe00ul, 27}, // 11111111|11111111|11111110|000 |
| {255, 0xfffffb80ul, 26}, // 11111111|11111111|11111011|10 |
| {256, 0xfffffffcul, 30} // EOS 11111111|11111111|11111111|111111 |
| }; |
| |
| void write_huffman_code(BitOStream &outputStream, const CodeEntry &code) |
| { |
| // Append octet by octet. |
| auto bitLength = code.bitLength; |
| const auto hc = code.huffmanCode >> (32 - bitLength); |
| |
| if (bitLength > 24) { |
| outputStream.writeBits(uchar(hc >> 24), bitLength - 24); |
| bitLength = 24; |
| } |
| |
| if (bitLength > 16) { |
| outputStream.writeBits(uchar(hc >> 16), bitLength - 16); |
| bitLength = 16; |
| } |
| |
| if (bitLength > 8) { |
| outputStream.writeBits(uchar(hc >> 8), bitLength - 8); |
| bitLength = 8; |
| } |
| |
| outputStream.writeBits(uchar(hc), bitLength); |
| } |
| |
| } |
| |
| // That's from HPACK's specs - we deal with octets. |
| static_assert(std::numeric_limits<uchar>::digits == 8, "octets expected"); |
| |
| quint64 huffman_encoded_bit_length(const QByteArray &inputData) |
| { |
| quint64 bitLength = 0; |
| for (int i = 0, e = inputData.size(); i < e; ++i) |
| bitLength += staticHuffmanCodeTable[int(inputData[i])].bitLength; |
| |
| return bitLength; |
| } |
| |
| void huffman_encode_string(const QByteArray &inputData, BitOStream &outputStream) |
| { |
| for (int i = 0, e = inputData.size(); i < e; ++i) |
| write_huffman_code(outputStream, staticHuffmanCodeTable[int(inputData[i])]); |
| |
| // Pad bits ... |
| if (outputStream.bitLength() % 8) |
| outputStream.writeBits(0xff, 8 - outputStream.bitLength() % 8); |
| } |
| |
| bool padding_is_valid(quint32 chunk, quint32 nBits) |
| { |
| Q_ASSERT(nBits); |
| |
| // HPACK, 5.2: "A padding strictly longer than 7 bits MUST be |
| // treated as a decoding error." |
| if (nBits > 7) |
| return false; |
| // HPACK, 5.2: |
| // "A padding not corresponding to the most significant bits |
| // of the code for the EOS symbol MUST be treated as a decoding error." |
| return (chunk >> (32 - nBits)) == quint32((1 << nBits) - 1); |
| } |
| |
| HuffmanDecoder::HuffmanDecoder() |
| : minCodeLength() |
| { |
| const auto nCodes = sizeof staticHuffmanCodeTable / sizeof staticHuffmanCodeTable[0]; |
| |
| std::vector<CodeEntry> symbols(staticHuffmanCodeTable, staticHuffmanCodeTable + nCodes); |
| // Now we sort: by bit length first (in the descending order) and by the symbol |
| // value (descending). Descending order: to make sure we do not create prefix tables with |
| // short 'indexLength' first and having longer codes that do not fit into such tables later. |
| std::sort(symbols.begin(), symbols.end(), [](const CodeEntry &code1, const CodeEntry &code2) { |
| if (code1.bitLength == code2.bitLength) |
| return code1.byteValue > code2.byteValue; |
| return code1.bitLength > code2.bitLength; |
| }); |
| |
| minCodeLength = symbols.back().bitLength; // The shortest one, currently it's 5. |
| |
| // TODO: add a verification - Huffman codes |
| // within a given bit length range also |
| // should be in descending order. |
| |
| // Initialize 'prefixTables' and 'tableData'. |
| addTable(0, quint32(BitConstants::rootPrefix)); // 'root' table. |
| |
| for (const auto &s : symbols) { |
| quint32 tableIndex = 0; |
| while (true) { |
| Q_ASSERT(tableIndex < prefixTables.size()); |
| // Note, by value - since prefixTables will be updated in between. |
| const auto table = prefixTables[tableIndex]; |
| // We skip prefixed bits (if any) and use indexed bits only: |
| const auto entryIndex = s.huffmanCode << table.prefixLength >> (32 - table.indexLength); |
| // Again, by value. |
| PrefixTableEntry entry = tableEntry(table, entryIndex); |
| // How many bits were coded by previous tables and this table: |
| const auto codedLength = table.prefixLength + table.indexLength; |
| if (codedLength < s.bitLength) { |
| // We have to add a new prefix table ... (if it's not done yet). |
| if (!entry.bitLength) { |
| entry.nextTable = addTable(codedLength, std::min<quint32>(quint32(BitConstants::childPrefix), |
| s.bitLength - codedLength)); |
| entry.bitLength = s.bitLength; |
| entry.byteValue = s.byteValue; |
| setTableEntry(table, entryIndex, entry); |
| } |
| tableIndex = entry.nextTable; |
| } else { |
| // We found the slot for our code (terminal entry): |
| entry.byteValue = s.byteValue; |
| entry.bitLength = s.bitLength; |
| // Refer to our own table as 'nextTable': |
| entry.nextTable = tableIndex; |
| setTableEntry(table, entryIndex, entry); |
| break; |
| } |
| } |
| } |
| |
| // Now, we have a table(s) and have to fill 'holes' to |
| // 'fix' terminal entries. |
| for (const auto &table : prefixTables) { |
| const quint32 codedLength = table.prefixLength + table.indexLength; |
| for (quint32 j = 0; j < table.size();) { |
| const PrefixTableEntry &entry = tableEntry(table, j); |
| if (entry.bitLength && entry.bitLength < codedLength) { |
| const quint32 range = 1 << (codedLength - entry.bitLength); |
| for (quint32 k = 1; k < range; ++k) |
| setTableEntry(table, j + k, entry); |
| j += range; |
| } else { |
| ++j; |
| } |
| } |
| } |
| } |
| |
| bool HuffmanDecoder::decodeStream(BitIStream &inputStream, QByteArray &outputBuffer) |
| { |
| while (true) { |
| quint32 chunk = 0; |
| const quint32 readBits = inputStream.peekBits(inputStream.streamOffset(), 32, &chunk); |
| if (!readBits) |
| return !inputStream.hasMoreBits(); |
| |
| if (readBits < minCodeLength) { |
| inputStream.skipBits(readBits); |
| return padding_is_valid(chunk, readBits); |
| } |
| |
| quint32 tableIndex = 0; |
| const PrefixTable *table = &prefixTables[tableIndex]; |
| quint32 entryIndex = chunk >> (32 - table->indexLength); |
| PrefixTableEntry entry = tableEntry(*table, entryIndex); |
| |
| while (true) { |
| if (entry.nextTable == tableIndex) |
| break; |
| |
| tableIndex = entry.nextTable; |
| table = &prefixTables[tableIndex]; |
| entryIndex = chunk << table->prefixLength >> (32 - table->indexLength); |
| entry = tableEntry(*table, entryIndex); |
| } |
| |
| if (entry.bitLength > readBits) { |
| inputStream.skipBits(readBits); |
| return padding_is_valid(chunk, readBits); |
| } |
| |
| if (!entry.bitLength || entry.byteValue == 256) { |
| //EOS (256) == compression error (HPACK). |
| inputStream.skipBits(readBits); |
| return false; |
| } |
| |
| outputBuffer.append(entry.byteValue); |
| inputStream.skipBits(entry.bitLength); |
| } |
| |
| return false; |
| } |
| |
| quint32 HuffmanDecoder::addTable(quint32 prefix, quint32 index) |
| { |
| PrefixTable newTable{prefix, index}; |
| newTable.offset = quint32(tableData.size()); |
| prefixTables.push_back(newTable); |
| // Add entries for this table: |
| tableData.resize(tableData.size() + newTable.size()); |
| |
| return quint32(prefixTables.size() - 1); |
| } |
| |
| PrefixTableEntry HuffmanDecoder::tableEntry(const PrefixTable &table, quint32 index) |
| { |
| Q_ASSERT(index < table.size()); |
| return tableData[table.offset + index]; |
| } |
| |
| void HuffmanDecoder::setTableEntry(const PrefixTable &table, quint32 index, |
| const PrefixTableEntry &entry) |
| { |
| Q_ASSERT(index < table.size()); |
| tableData[table.offset + index] = entry; |
| } |
| |
| bool huffman_decode_string(BitIStream &inputStream, QByteArray *outputBuffer) |
| { |
| Q_ASSERT(outputBuffer); |
| |
| static HuffmanDecoder decoder; |
| return decoder.decodeStream(inputStream, *outputBuffer); |
| } |
| |
| } |
| |
| QT_END_NAMESPACE |