This is derived from zlib's enough.c, which determines the maximum possible size of 2-level table for given number of symbols, N and the maximum allowed bit length (here 15). I have mentioned that there was the hard-coded maximum number of entries. The actual fix never altered the `ReadSymbol` function at all! But the safety of the tight loop should be still justified, so the wrong justification can ruin everything.Īfter some more reading, I concluded that authors did think about this possibility but wrote a wrong code. I should note that the memory corruption occurs during the table construction, which is not a tight loop, so a partial overflow check would be very helpful. I'm not even sure that a memory safe language could have prevented this this is a rare case where you actively want to avoid the overflow check. ![]() The original commit message refuted this, and was able to be merged. The Huffman decoder optimization described above is well known, but the longer code case is commonly considered less important to optimize because longer code should rarely appear in general. To be fair, I can see why this happened the Huffman decoding step is one of the most computationally intensive part of many compression format and any small improvement matters. So if the Huffman tree was crafted in the way that maximizes the number of entries, it will overflow the allocation. Amusingly enough the code itself had a mode where only the table size is calculated (VP8LBuildHuffmanTable called with `root_table = NULL`), but it wasn't somehow unused and the fixed maximum size was assumed. VP8 Lossless specifically allows up to 15 bits, so the largest possible table has 2^N + 2^15 entries when every single LUT is mapped to its own secondary table, and doing this doesn't need that many symbols (you only need 16-N symbols for each table). Of course, the Huffman tree comes from an untrusted source and you can easily imagine the case where `nbits` is very big. The new version calculated the maximum number of entries based on the number of symbols (kTableSize). So each subsequent table should have `2^(nbits - N)` entries (the root table is always fixed to 2^N entries). Each entry contains (nbits, value) where `nbits` is # bits to be consumed and `value` is normally a symbol, but if `nbits` exceeds N `value` is interpreted as a table index and `nbits` is reinterpreted as the longest code length in that subtree. ![]() The new version improved this by using an array of lookup tables. The old version did use lookup tables for short symbols, but longer symbols needed a graph traversal. The decoder uses a well-known optimization: it reads N bits in advance and determines how many bits have to be actually consumed and which symbol should be decoded, or, if it's an N-bit prefix of multiple symbols, which table should be consulted for remaining bits. The original commit optimizes a Huffman decoder.
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |