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.
Note that in some cases (in particular SQL::Result and PDFErrorOr),
there is no Formatter defined for the error type, hence TRY_OR_FAIL
cannot work as-is. Furthermore, this commit leaves untouched the places
where MUST could be replaced by TRY_OR_FAIL.
Inspired by:
https://github.com/SerenityOS/serenity/pull/18710#discussion_r1186892445
Rather than the very C-like API we currently have, accepting a void* and
a length, let's take a Bytes object instead. In almost all existing
cases, the compiler figures out the length.
This is to differentiate between the upcoming `AllocatingMemoryStream`,
which automatically allocates memory as needed instead of operating on a
static memory area.
The round trip compress test wants the first half of the byte buffer to
be filled with random data, and the second half to be all zeroes. The
strategy of using memset on ByteBuffer::offset_pointer confuses
__builtin_memset_chk when building with -fsanitize=undefined. It thinks
that the buffer is using inline capacity when we can prove to ourselves
pretty easily that it's not. To avoid this, just create the buffer
zeroed to start, and then fill the first half with the random data.
