| bitstreams.cpp |
|
8149 |
- |
| bitstreams_p.h |
|
3628 |
- |
| hpack.cpp |
encoder needs search index |
17319 |
- |
| hpack_p.h |
|
3650 |
- |
| hpacktable.cpp |
|
13436 |
- |
| hpacktable_p.h |
Lookup table consists of two parts (HPACK, 2.3):
the immutable static table (pre-defined by HPACK's specs)
and dynamic table which is updated while
compressing/decompressing headers.
Table must provide/implement:
1. Fast random access - we read fields' indices from
HPACK's bit stream.
2. FIFO for dynamic part - to push new items to the front
and evict them from the back (HPACK, 2.3.2).
3. Fast lookup - encoder receives pairs of strings
(name|value) and it has to find an index for a pair
as the whole or for a name at least (if it's already
in either static or dynamic table).
Static table is an immutable vector.
Dynamic part is implemented in a way similar to std::deque -
it's a vector of pointers to chunks. Each chunk is a vector of
(name|value) pairs. Once allocated with a fixed size, chunk
never re-allocates its data, so entries' addresses do not change.
We add new chunks prepending them to the front of a vector,
in each chunk we fill (name|value) pairs starting from the back
of the chunk (this simplifies item eviction/FIFO).
Given a 'linear' index we can find a chunk number and
offset in this chunk - random access.
Lookup in a static part is straightforward:
it's an (immutable) vector, data is sorted,
contains no duplicates, we use binary search comparing string values.
To provide a lookup in dynamic table faster than a linear search,
we have an std::set of 'SearchEntries', where each entry contains:
- a pointer to a (name|value) pair (to compare
name|value strings).
- a pointer to a chunk containing this pair and
- an offset within this chunk - to calculate a
'linear' index.
Entries in a table can be duplicated (HPACK, 2.3.2),
if we evict an entry, we must update our index removing
the exactly right key, thus keys in this set are sorted
by name|value pairs first, and then by chunk index/offset
(so that NewSearchEntryKey < OldSearchEntry even if strings
are equal).
|
6148 |
- |
| http2frames.cpp |
|
15390 |
- |
| http2frames_p.h |
|
4430 |
- |
| http2protocol.cpp |
|
8239 |
- |
| http2protocol_p.h |
|
5379 |
- |
| http2streams.cpp |
|
1563 |
- |
| http2streams_p.h |
|
2156 |
- |
| huffman.cpp |
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 entries 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'.
|
24765 |
- |
| huffman_p.h |
|
3052 |
- |