33 tests, in 2 new suites : lz4 (decoding of invalid input, one-shot and streaming compression)
and lz4hc (streaming, dictionaries, destSize). Tests depending on the HC level run on both levels
previously selected by fuzzer.
UT_sample(), KB, MB and ARRAY_SIZE() are now provided by unittest.h, for all suites.
On a new or reset stream (prefixStart == NULL), LZ4_saveDictHC() installed @safeBuffer as prefix,
which skipped the initialization done by the next compression (LZ4HC_init_internal()).
The stream then started at index 0, which the hash table uses for empty entries :
positions matched themselves (offset 0), and the block decoded into wrong data, at all HC levels,
also with an attached dictionary. Present in v1.10.0.
It now saves nothing, leaving the stream to be initialized by the next compression.
Found by lz4frame with uncompressed then compressed segments in linked blocks.
tests : fuzzer.c saveDictHC test #926 compresses after LZ4_saveDictHC(), without and with an attached dictionary.
LZ4MID_compress() checked ip+1 for a longer match only after a match
found by the 4-byte table within the prefix, never after a match found
by the 8-byte table. The check now follows any match shorter than 8 bytes,
also within an external dictionary, and skips the candidate ip itself:
inside runs, ip+1 would find ip at offset 1, and periodic data would
lock onto one literal and one offset 1 per run (4 KB to ~1.6 KB).
The previous check is removed.
Compressed size : linux-6.12 tar -1.3%, Silesia -0.6%, enwik9 -0.5%
(4 MB blocks), -0.25% (4 KB blocks), -0.9% (64 KB linked blocks),
-0.2% (4 KB pages with a 64 KB dictionary).
Speed, AMD EPYC Genoa (Zen 4), x86-64, gcc 11 / gcc 15 / clang 22 :
-0.5 to -1.3% (256 KB blocks), -1.3 to -2% (4 KB blocks),
-1.8 to -2.5% (64 KB linked blocks), -0.2 to -1.2% (4 KB pages with a dictionary).
x86 (gcc 12 -m32) : +1.4% (4 KB pages with a dictionary) to -4.9% (64 KB linked blocks).
After each match, the fast parser only tested the most recent occurrence
of the sequence at ip. On periodic data with long runs, it is a short
match, and such matches can chain until the end of the input :
an 8-byte dictionary made a 4 KB page compress to 1543 bytes instead
of 49 (#1805). It also happens without dictionary.
The position following the previous occurrence of ip-1 is now tested
first, also within the dictionary, and taken if it matches 8+ bytes.
The table is filled with ip-1 instead of ip-2.
Both candidates share the same dictionary / current-block selection.
Silesia, compressed size : -0.6% (256 KB blocks), -0.3% (4 KB blocks),
-0.5% (4 KB pages with a 64 KB dictionary).
Speed, AMD EPYC Genoa (Zen 4), x86-64, gcc 11 / gcc 15 / clang 22 :
-0.8 to -1.2% (256 KB blocks), -1.7 to +1.5% (4 KB blocks),
-6 to +1% (4 KB pages with a dictionary).
x86 (gcc 12 -m32) : +1% (4 KB blocks) to -11% (dictionary).
Closes#1805
A ring buffer of LZ4_DECODER_RING_BUFFER_SIZE(maxBlockSize) is allocated statically,
so its size is compiled into applications.
16d695b1 enlarged its margin from 14 to 64 bytes to fit the fast loop's wide copies,
leaving applications compiled with the former macro exposed to corrupted output.
The decoder now also supports the former margin, without advertising it.
When decoding restarts at the beginning of the ring, the oldest referenced history
lies in the external dictionary, ahead of the write position, at a constant distance.
When this distance is shorter than FASTLOOP_SAFE_DISTANCE, the block is decoded by the safe loop,
which writes at most 16 bytes beyond a copy, like the v1.8.x decoder the 14-byte margin was sized for.
This only concerns rings with less than 64 bytes of margin, hence never the current macro,
for the blocks following such a restart, until 64 KB have been decoded.
Other decoders are unaffected : the test is resolved at compile time outside of usingExtDict.
Applications compiled with older headers decode correctly with the new library, without recompiling.
The static assert now checks what correctness requires, i.e. the safe loop's margin,
which the former macro satisfies : on this point, lz4.c compiles again with an older lz4.h (#1863).
The fuzzer's worst-case ring test now also runs with the former ring size :
it fails without this change, and passes with it.
The other ring condition (decoder ring larger than the encoder's by maxBlockSize + 64 bytes, 2f449bb3)
is unchanged : the decoder can't know the encoder's ring size.
Follow-up to the previous commit: instead of returning early,
clamp a negative dictSize to 0, like LZ4_saveDictHC().
Returning early left the stream referencing the previous dictionary,
which the caller is about to overwrite, since it asked to save it:
the next block could then reference stale data.
With dictSize = 0, the stream continues without dictionary.
fuzzer: the next block copies the end of the dictionary,
and must decode without it (fails with the early return),
and saveBuffer is small enough for ASan to detect
the 64 KB copy (fails on dev).
LZ4_decompress_safe_usingDict(), LZ4_decompress_safe_partial_usingDict(),
LZ4_decompress_fast_usingDict() and LZ4_setStreamDecode() only assert()
that dictSize is not negative, then cast it to size_t. In release builds
the dictionary becomes ~SIZE_MAX bytes long, so every match offset is
accepted and decoding reads before the dictionary buffer.
LZ4_loadDictHC() has the same assert(): on lz4mid levels the fill target
of LZ4MID_fillHTable() wraps and it reads up to 32 KB before the
dictionary.
The decoders now return -1, LZ4_setStreamDecode() returns 0 (its
documented error), and LZ4_loadDictHC() loads no dictionary, as
LZ4_loadDict() already does for a negative size.
Near the end of a partial decoding, a match with offset 0 was copied onto
itself, leaving previous dst content in decoded data. doc/lz4_Block_format.md
warns against it (information disclosure), and other decoding paths
already produce 0 bytes. Clear the match segment instead.
Since v1.9.3 (c5d6f8a8), partial decoding clamps literals to the end of input.
With a negative srcSize, iend points before src: (size_t)(iend-ip) became huge,
and the literals memmove() ran far past both buffers.
Reject it in the existing srcSize==0 test of LZ4_decompress_generic(),
which becomes srcSize<=0: the generated code only changes je into jle.
The NEWS line also covers the LZ4_decompress_fast*() fix of #1875 (since v1.9.4).
A negative originalSize made oend point before the output buffer:
(size_t)(oend-op) then became huge, disabling every output bound check,
so decoding wrote and read past the buffers.
Reject it once, in LZ4_decompress_unsafe_generic(), which backs all
LZ4_decompress_fast*() entry points, as LZ4_decompress_generic()
already does for the safe variants.
Values <= 0 produced corrupted output, and large negative values
read out of bounds. The clamp is now a single helper, LZ4_clampAcceleration(),
used by all 4 entry points.
LZ4_loadDict() ignores dictionaries smaller than HASH_UNIT.
A large first block must then give the same output as a new stream,
directly or through LZ4_attach_dictionary().
Fails on dev : after LZ4_loadDict(), the output differs.
The fuzzer can detect it too, as a difference between
LZ4_compress_fast_continue() using extDict and using extDictCtx (seed 9016, cycle 8086).
Worst case, with dstCapacity = maxBlockSize : decoding restarts at the beginning of the ring,
a block ends with a wide copy writing beyond its end, a 1-byte block follows,
then a block references the oldest byte allowed by the encoder's ring.
With the formerly documented margin (maxBlockSize), the output is corrupted since v1.9.0.
The new block overwrites the previous one (its dictionary) at the beginning, at the same place,
entirely, or at the end. Output decoded from a separate buffer must be correct.
Fails on dev : LZ4_compress_fast_continue() only handles an overwritten beginning.
Worst case : decoding restarts at the beginning of the ring with maxBlockSize-1 bytes left at its end,
then a wide copy (long literals or long match) is followed by a match at maximum distance.
The copy writes beyond its end, over the oldest history, still referenced by the match.
Fails on dev : on x86, the margin must be 29 bytes (LZ4_wildCopy32) instead of 14.
Attaching a dictionary to a new state, then compressing with one-shot fast reset,
must give the same output as a new state.
It currently doesn't : the block finds no match, and debug builds hit an assert.
- unit test : a 64 KB block, compressed on a new state,
then as a new stream on the same (now used) state, must be identical,
including after dropping history with LZ4_saveDict(stream, buffer, 0).
The input starts with a 4-byte sequence which reappears right after,
followed by a different 5th byte.
- fuzzer : a state keeps a history across cycles;
each block starts a new stream on it with LZ4_resetStream_fast(),
and blocks >= 64 KB must match the output of a new stream.
64 KB is beyond the table clearing threshold, whatever LZ4_MEMORY_USAGE.
These tests fail on current dev :
LZ4_resetStream_fast() keeps the table, and a used table rejects its stale entries,
while a cleared table tests position 0 for unused hash slots.
Compare its output with LZ4_compress_fast_extState(), which fully initializes the state.
Whether the fast reset clears the table or reuses it,
the output must be the same :
below 64 KB, the table uses a 4-byte hash,
so reusing a table can't miss a match that a cleared table would find.
Beyond, the table is always cleared.
This guards a change of the threshold deciding to clear the table.
A failed compression marks the HC state as dirty,
and LZ4_resetStreamHC_fast() then fully re-initializes it.
- fuzzer : after a failed compression, the next stream
still favors decompression speed, as it would without the failure.
- frametest : with independent blocks at level 10 and favorDecSpeed,
a block following an incompressible block is identical
to the same block compressed alone.
LZ4F compresses each block into srcSize-1 bytes,
so any incompressible block is a failed compression.
These tests fail on current dev :
the re-initialization also resets favorDecSpeed,
so LZ4F ignores it after the first incompressible block of a frame.
by not searching into the 2nd buffer
which is an inefficiency (less compression opportunities)
but makes the code sensibly simpler to read
and is a use-case avoided by lz4frame.
PR #1308 introduces a new symbol, `LZ4_compress_fast_extState_destSize()`,
which, upon inspection, doesn't seem to work as advertised.
In particular, it fails if `dstCapacity` is not large enough,
as opposed to adjusting input size to fit within `dstCapacity`.
Even if it had worked, it would have resulted in problems
for the existing `LZ4_compress_fast_extState()`,
that would have stopped failing when `dstCapacity` is not large enough,
resulting in silent input truncation.
Changed the approach.
It appears the wanted functionality already exists within `lz4` source code,
and is called `LZ4_compress_destSize_extState()`.
It wasn't exposed dues to a (non-verified) problem regarding lz4 state on exit:
it's claimed that since the `_destSize` doesn't completely consume the input,
the state may end up in an "unfinished" status,
making it dangerous to re-employ in later invocations.
Fixed that by enforcing a state initialization at the end of operation.
Also : added some tests,
ensure that `LZ4_compress_fast_extState()` fails as expected when `dstCapacity` is not large enough,
and ensure that `LZ4_compress_destSize_extState()` does succeed in the same circumstance,
by consume less input.
Finally, expose `LZ4_compress_destSize_extState()` as an advanced experimental symbol.
Suppress the following false positive warnings from MSVC:
- Disable all arithmetic overflow (C26451)
- Suppress C6385: Reading invalid data from 'compressedBuffer'.
- Add ULL suffix to unsigned 64-bits constants.
