1
Fork 0
mirror of https://github.com/RGBCube/serenity synced 2025-07-26 12:07:45 +00:00
Commit graph

1 commit

Author SHA1 Message Date
Idan Horowitz
b749167506 LibCompress: Fix off-by-one error in generate_huffman_lengths
Previously we would calculate the index of the first parent node as
heap.size() (which is initialized to non_zero_freqs), so in the edge
case in which all symbols had a non-zero frequency, we would use the
Size-index entry in the array for both the first symbol's leaf node,
and the first parent node.

The result would either be a non-optimal huffman code (bad), or an
illegal huffman code that would then go on to crash due to an error
check in CanonicalCode::from_bytes. (worse)

We now store parent nodes starting at heap.size() - 1, which eliminates
the potential overlap, and resolves the issue.
2023-12-04 00:06:38 +01:00