Loading...
Searching...
No Matches
Huffman tables (QPACK only) (headers) More...
#include <stdint.h>#include <glib.h>
Go to the source code of this file.
Data Structures | |
| struct | imquic_huffman_table |
| Ascii symbol and its length in bits as Huffman code, relatively to the current level. More... | |
| struct | imquic_huffman_bits |
| Huffman code and its length in bits as Huffman code, mapped to the related ascii code. More... | |
Huffman decoding | |
| typedef struct imquic_huffman_table | imquic_huffman_table |
| Ascii symbol and its length in bits as Huffman code, relatively to the current level. | |
| imquic_huffman_table | level0_root [256] |
| Root level of parsing (first byte) | |
| imquic_huffman_table | level0_11111110 [256] |
| Second level of parsing (second byte), if the first byte was 11111110. | |
| imquic_huffman_table | level0_11111111 [256] |
| Second level of parsing (second byte), if the first byte was 11111111. | |
| imquic_huffman_table | level0_11111111_11111110 [256] |
| Third level of parsing (third byte), if the second byte was 11111110. | |
| imquic_huffman_table | level0_11111111_11111111 [256] |
| Third level of parsing (third byte), if the second byte was 11111111. | |
| imquic_huffman_table | level0_11111111_11111111_11110110 [256] |
| Fourth level of parsing (fourth byte), if the third byte was 11110110. | |
| imquic_huffman_table | level0_11111111_11111111_11110111 [256] |
| Fourth level of parsing (fourth byte), if the third byte was 11110111. | |
| imquic_huffman_table | level0_11111111_11111111_11111000 [256] |
| Fourth level of parsing (fourth byte), if the third byte was 11111000. | |
| imquic_huffman_table | level0_11111111_11111111_11111001 [256] |
| Fourth level of parsing (fourth byte), if the third byte was 11111001. | |
| imquic_huffman_table | level0_11111111_11111111_11111010 [256] |
| Fourth level of parsing (fourth byte), if the third byte was 11111010. | |
| imquic_huffman_table | level0_11111111_11111111_11111011 [256] |
| Fourth level of parsing (fourth byte), if the third byte was 11111011. | |
| imquic_huffman_table | level0_11111111_11111111_11111100 [256] |
| Fourth level of parsing (fourth byte), if the third byte was 11111100. | |
| imquic_huffman_table | level0_11111111_11111111_11111101 [256] |
| Fourth level of parsing (fourth byte), if the third byte was 11111101. | |
| imquic_huffman_table | level0_11111111_11111111_11111110 [256] |
| Fourth level of parsing (fourth byte), if the third byte was 11111110. | |
| imquic_huffman_table | level0_11111111_11111111_11111111 [256] |
| Fourth level of parsing (fourth byte), if the third byte was 11111111. | |
| imquic_huffman_table * | imquic_huffman_transitions [16] |
| Map of transitions, to allow moving from one table to another at different levels. | |
Huffman encoding | |
| typedef struct imquic_huffman_bits | imquic_huffman_bits |
| Huffman code and its length in bits as Huffman code, mapped to the related ascii code. | |
| imquic_huffman_bits | table [] |
| Table mapping each ascii code to its Huffman code representation. | |
Huffman tables (QPACK only) (headers)
Naive implementation of Huffman tables, used for quick encoding and decoding by the QPACK part of our basic HTTP/3 stack.
The decoder works by processing the incoming bitstream 8 bits at a time, and so in bytes. This is inspired by different blog posts, most importantly this one explaining the reasoning behind LWAN's decoder implementation. Using a bitstream reader, we can peek 8 bits at a time, and then look for the related imquic_huffman_table instance in the root table: if we get a symbol right away, we return that and consume its size in bits from the bitstream: if we're redirected to another table, because the Huffman code uses more than 8 bits, we read 8 more bits and try to find a match in the related table; and so on and so forth. Redirecting to a different table is done by using negative values in the num_bits property, which removing the sign act as keys to our transitions map in imquic_huffman_transitions.
Encoding uses a single table, instead, where we look for the imquic_huffman_bits instance mapped to the ascii symbol we want to encode. That instance contains both a hex representation of the Huffman code, and how many bits we should actually write, which we can then pass to a bitstream writer for the purpose. The last byte is padded with a sequence of up to 7 1 to act as an EOS.
| typedef struct imquic_huffman_bits imquic_huffman_bits |
Huffman code and its length in bits as Huffman code, mapped to the related ascii code.
| typedef struct imquic_huffman_table imquic_huffman_table |
Ascii symbol and its length in bits as Huffman code, relatively to the current level.
| imquic_huffman_table* imquic_huffman_transitions[16] |
Map of transitions, to allow moving from one table to another at different levels.
| imquic_huffman_table level0_11111110[256] |
Second level of parsing (second byte), if the first byte was 11111110.
| imquic_huffman_table level0_11111111[256] |
Second level of parsing (second byte), if the first byte was 11111111.
| imquic_huffman_table level0_11111111_11111110[256] |
Third level of parsing (third byte), if the second byte was 11111110.
| imquic_huffman_table level0_11111111_11111111[256] |
Third level of parsing (third byte), if the second byte was 11111111.
| imquic_huffman_table level0_11111111_11111111_11110110[256] |
Fourth level of parsing (fourth byte), if the third byte was 11110110.
| imquic_huffman_table level0_11111111_11111111_11110111[256] |
Fourth level of parsing (fourth byte), if the third byte was 11110111.
| imquic_huffman_table level0_11111111_11111111_11111000[256] |
Fourth level of parsing (fourth byte), if the third byte was 11111000.
| imquic_huffman_table level0_11111111_11111111_11111001[256] |
Fourth level of parsing (fourth byte), if the third byte was 11111001.
| imquic_huffman_table level0_11111111_11111111_11111010[256] |
Fourth level of parsing (fourth byte), if the third byte was 11111010.
| imquic_huffman_table level0_11111111_11111111_11111011[256] |
Fourth level of parsing (fourth byte), if the third byte was 11111011.
| imquic_huffman_table level0_11111111_11111111_11111100[256] |
Fourth level of parsing (fourth byte), if the third byte was 11111100.
| imquic_huffman_table level0_11111111_11111111_11111101[256] |
Fourth level of parsing (fourth byte), if the third byte was 11111101.
| imquic_huffman_table level0_11111111_11111111_11111110[256] |
Fourth level of parsing (fourth byte), if the third byte was 11111110.
| imquic_huffman_table level0_11111111_11111111_11111111[256] |
Fourth level of parsing (fourth byte), if the third byte was 11111111.
| imquic_huffman_table level0_root[256] |
Root level of parsing (first byte)
| imquic_huffman_bits table[] |
Table mapping each ascii code to its Huffman code representation.