libwebp

n the code, a couple too many branches away from being likely to be found by fuzzing.

nd `nbits` is reinterpreted as the longest code length in that subtree. So each subsequent table should have `2^(nbits - N)` entries (the root table is always fixed to 2^N entries). The new version calculated the maximum number of entries based on the number of symbols (kTableSize). Of course, the Huffman tree comes from an untrusted source and you can easily imagine the case where `nbits` is very big. 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). 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. So if the Huffman tree was crafted in the way that maximizes the number of entries, it will overflow the allocation. 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. 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. The original commit message refuted this, and was able to be merged. 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 [1]. [1] 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. 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.