]> git.ipfire.org Git - thirdparty/haproxy.git/commit
IMPORT: slz: use the exact switch cost for the last literals of a block
authorAurelien DARRAGON <adarragon@haproxy.com>
Tue, 11 Aug 2026 15:57:56 +0000 (17:57 +0200)
committerAurelien DARRAGON <adarragon@haproxy.com>
Wed, 12 Aug 2026 07:14:07 +0000 (09:14 +0200)
commitba66fec003fb6c8a760eaf186959ae1a6845c78d
tree7d5010797bb93d90d38d94877f1980ce4385de4f
parent71f54efa28d285e066922666bfe7e47879d246bb
IMPORT: slz: use the exact switch cost for the last literals of a block

The decision to send the pending literals as a stored block rather than in
fixed huffman mode is taken when the 9-bit literals wasted more than the
52 bits it costs to leave the fixed huffman encoding and to come back to
it. But for the last literals of a block, nothing comes after the stored
block, so there is no need to pay for the block type of a next block nor
for the EOB, while the huffman variant still has to send an EOB. The
switch is thus 10 bits cheaper, and 10 more when the stream is still in
EOB state, since then the block type is needed in both cases and no EOB
has to be terminated.

Using 52 there made the encoder prefer huffman for data that was cheaper
to store, and the output could exceed the documented maximum. The smallest
case found by fuzzing is a 47-byte input entirely made of bytes >= 144
which produced 55 bytes (3 bits of block type + 47*9 bits + 7 bits of EOB)
where the stored block only needs 52, for a documented maximum of 54.

With these correct costs, we no longer see outputs exceed the documented
maximum, wether it's with small inputs (tested with ~3 million random
small inputs as small as 47 bytes), or usual files found in tests/ and
bash, gcc, libc, and silesia. No performance change was observed either.

Note that a stream can still exceed the documented maximum by a few bytes
(17 bytes were observed on a 390000-byte crafted input) because each
reference emitted between two stored blocks forces them out and adds a
5-byte block header that the accounting attributes to the reference. This
is for a future fix.

This is libslz upstream commit 97757536178f24aeb2cb41278706a88c1242f414
src/slz.c