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.
The safe loop had its own copy of LZ4_memcpy_using_offset_base(), the
fast loop's helper: the same inc32table/dec64table trick for offsets
below 8, followed by the same 8-byte copies. Use the shared helper.
It now supports offset 1 (first 4 bytes copied one by one), is defined
without LZ4_FAST_DEC_LOOP, and follows the safe loop's structure: the
second 8 bytes are copied directly, LZ4_wildCopy8() only beyond 16 bytes.
No behavior change. Instruction counts move by less than 0.15%.
Speed: +0% to +3.7% on all decoders without LZ4_FAST_DEC_LOOP;
with it, -3% to +4% depending on decoder and code alignment.
LZ4_wildCopy64 (long literals, and matches with offset >= 64) was restricted to aarch64.
It speeds up decompression on x86-64 too.
AMD EPYC Genoa (Zen 4), gcc 11, silesia files :
level 1 : +5.1% (geomean), up to +18.8% (sao) ; level 9 : +2.6%, up to +9.8% (xml).
Worst cases : -1.7% (sao, level 9), -1.0% (reymont, level 9).
Not enabled on 32-bit x86 (same machine, gcc 12 -m32) :
without SSE2 : -0.8% / -1.9% (geomean, levels 1 / 9), down to -10.2% (osdb) ;
with SSE2 : +0.7% / +1.0%, from -3.0% (sao) to +12.1% (x-ray).
Other targets are unchanged.
Proposed for x86 in #1407 by Nicolas De Carli.
Firefox stores its .jsonlz4 / .mozlz4 files (session, bookmark backups,
search engines) as "mozLz40\0", the decompressed size (LE32),
then a single LZ4 block extending to the end of the file
(see MozLZ4 in Firefox's xpcom/ioutils/IOUtils.cpp).
`lz4 -d`, `lz4 -t` and `lz4cat` now recognize this format,
and decode it like Firefox's reader :
- the decompressed size is only used as decoding capacity
- empty content has no block (Firefox doesn't write one)
Allocations are bounded : sizes > LZ4_MAX_INPUT_SIZE are rejected,
as they can't be compressed into a single block,
and input is read up to LZ4_COMPRESSBOUND(size), the largest valid block.
Data starting with the first half of the magic only ("mozL") keeps
the previous behavior : `lz4cat` passes it through unchanged,
including the bytes read to check the second half.
Decoding only : lz4 doesn't produce this non-standard format.
Based on #1259 by @UnitedMarsupials, rewritten for current dev
(no mmap, bounded allocations, full magic check, tests).
The fast loop checked for the safe loop handover twice, once per branch
of the match length token, and nested its 18-byte copy shortcut in the
short match branch. Decode the full match length first, then check the
handover once, then try the shortcut, in the same order as the safe loop.
No behavior change. Without LZ4_FAST_DEC_LOOP the generated code is
identical; with it, instruction counts move by less than 0.2%.
Scorecard fails on every push: v2.4.0 pulls its image from gcr.io,
which has been retired ("denied: This API method requires billing").
The Scorecard v5.6.0 release notes ask action users to upgrade
to v2.5.0 or later, which pull from ghcr.io.
Supersedes #1659 (v2.4.3).
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).
The legacy compressor used acceleration = -cLevel,
while lz4frame and bench use -cLevel + 1.
Legacy levels were shifted by one: `lz4 -l --fast=1` produced the same
output as `lz4 -l -1`, and `-l --fast=2` matched the frame `--fast=1`.
Use the same mapping, capped at LZ4_ACCELERATION_MAX
(avoids a signed overflow with --fast=2147483647).
Levels >= 0 are unchanged.
test-lz4-basic.sh: `-l --fast=1` must compress less than `-l -1`
(fails on dev), and `-l --fast=2147483647` runs.
Follow-up to "lz4frame: avoid signed overflow", per the #1824 review:
saturate at LZ4_ACCELERATION_MAX rather than INT_MAX,
since higher values make no difference.
LZ4_ACCELERATION_DEFAULT and LZ4_ACCELERATION_MAX move from lz4.c
to the LZ4_STATIC_LINKING_ONLY section of lz4.h, which lz4.c, lz4frame.c,
bench.c and frametest.c already include, so their values derive from it.
The LZ4_compress_fast() documentation already referred to both constants.
bench.c computed the acceleration the same way (-cLevel + 1),
so `lz4 -b --fast=2147483647` hit the same signed overflow:
apply the same cap there.
test-lz4-basic.sh: --fast=2147483647 must produce the same frame
as --fast=65536 (fails on dev, where acceleration wraps to the default),
and its benchmark runs (caught by the UBSan CI job before this fix).
lz4.1: --fast values above 65536 make no difference.
cLevelLast defaulted to -10000, meaning "unset".
With --fast=# and # > 10000, cLevel is below this sentinel,
so -b benchmarked all levels from -# up to -10000:
--fast=10003 ran 4 benchmarks, --fast=2147483647 ~2 billions.
Use INT_MIN as the sentinel instead.
LZ4F_compressBlock() and LZ4F_compressBlock_continue() compute the
acceleration as -level + 1. For compressionLevel == INT_MIN + 1 this
overflows (INT_MAX + 1), and for INT_MIN the negation itself overflows.
Both are undefined behavior (UBSan reports them, e.g. with
`lz4 --fast=2147483647`). In practice the result wraps to a negative
acceleration, which LZ4_compress_fast*() replaces with the default (1),
so the fastest requested levels silently compress at default speed.
Compute the acceleration in a helper that saturates instead of
overflowing. LZ4_compress_fast*() already caps acceleration at
LZ4_ACCELERATION_MAX, so the result is unchanged for every other level.
Add a frametest check that levels -65537, INT_MIN + 1 and INT_MIN
produce the same frame as level -65536.
readU32FromChar() silently wrapped around on values larger than 32 bits,
and compression levels were then cast to int without a range check.
As a result, out-of-range arguments did something unrelated instead of
failing, for example:
lz4 --fast=3000000000 compressed at maximum (HC) level
lz4 -3000000000 used the fastest level (output larger than input)
lz4 -4294967305 used level 9
lz4 -B4294967300 used 64 KB blocks
lz4 -B4194305K used 1 KB blocks
readU32FromChar() now exits with an error when the value (including
K/M suffixes) overflows 32 bits, and compression level arguments
(-#, -e#, --fast=#) are rejected when larger than INT_MAX.
LZ4_CLEVEL and LZ4_NBWORKERS values that overflow are ignored with the
existing warning, like other invalid values.
Also fix the --fast=0 and --fast=-1 tests in test-lz4-basic.sh: they
used a misspelled file name (dg20K instead of dg20k), so lz4 failed
because the file was missing rather than because of the option.
The safe loop's last literals path took about 50 lines, with 8 DEBUGLOG
and 6 comment blocks, for two rules: partialDecoding clamps the literal
length to the input and output left, otherwise the literals must end
exactly at input end, within output. State them directly, with MIN().
No behavior change: full-block decoders compile to identical code.
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.
A single variable `length` held the literal length, then the match length
token, then the full match length, so its meaning at a given point,
especially at safe_match_copy, had to be inferred from the control flow.
Use `ll` and `ml`, as LZ4_decompress_unsafe_generic() already does.
Also declare token, ll and cpy in each loop body, since they never outlive
an iteration: only match, offset and ml remain shared by both loops,
as the fast loop hands them over at safe_match_copy.
Renaming and scoping only: the generated code is identical.
When the second stage of the shortcut didn't work out, it jumped over
the normal literals path to _copy_match. Put the normal literals path
in the else branch instead: both branches decode the offset and match
length token, then join before the match length extension.
No behavior change: the combined output check of both shortcut stages
is kept, and the generated code runs the same number of instructions.
The fast decoder loop relies on wide unaligned copies being cheap.
On RISC-V, compilers only assume so when __riscv_misaligned_fast is
defined (-mno-strict-align, or a -mcpu with fast unaligned accesses).
Otherwise, unaligned LZ4_memcpy() are compiled as byte copies,
and the fast loop nearly doubles them in LZ4_decompress_safe()
(clang 21 -O3, rv64gc: 147 -> 266 lbu/sb).
This is consistent with results reported in #1678, #1686 and #1739,
which enable the fast loop unconditionally on riscv64:
between -2.9% and +2.8% decompression speed on real data.
Default builds (rv64gc, rva23u64) are unchanged.
-mcpu=spacemit-x60 or -mno-strict-align now select the fast loop.
Near the end of the block, the safe loop copied a match in 3 different ways:
the extDict branch with its own end-of-block check, a partialDecoding-only
branch with an exact copy, and the full decoding path, which mixed the
end-of-block error with a wild copy limited to oend-7 and a byte loop.
The safe loop now checks the end of block once (partialDecoding: truncate,
otherwise: error), then copies the match with LZ4_copyExtDictMatch(),
or close to the end with the new LZ4_copyMatchExact(), or else with
the wild copy, which no longer deals with the end of block.
LZ4_copyMatchExact() also replaces the byte loop of LZ4_copyExtDictMatch().
It copies an overlapping match by copying the whole repeated pattern,
doubling the distance up to 2 KB, instead of re-reading just written bytes,
so long repetitive matches decode faster (period 3: x16, zeros: +20%).
It is not inlined (new LZ4_FORCE_NOINLINE): its memcpy() calls slowed down
the hot loops of extDict decoders.
- grammar: "a lossless compression algorithm", "multi-core CPUs",
"The LZ4 library ... the BSD 2-Clause license", "defined in"
- clarify that the acceleration factor tunes compression speed
- dictionary API / CLI links were pinned to v1.8.3:
point to the in-tree lib/lz4frame.h and programs/lz4.1.md instead
- Zstandard dictionary builder link: v1.3.5 -> dev
- mention the GPL-2.0-or-later license of the CLI, as stated in LICENSE
- switch homepage, zlib, zstd and Silesia links to https
- point to build/ for CMake, Meson and Visual Studio builds
- vcpkg instructions: ./vcpkg, not ./vcpkg.exe, after bootstrap-vcpkg.sh
- list the API headers in the Documentation section
build/README.md: VS2022 solution outputs to build\VS2022\bin, not build\VS2010\bin
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.
Removing the 4-byte content checksum from a valid frame must make
`lz4 --list` fail. Before the previous commit, the checksum was skipped
with fseek(), which succeeds past the end of file, so --list reported
the truncated frame as valid (exit 0) while `lz4 -t` rejected it.
The CLI is not covered by the fuzzers; this test runs in milliseconds.
The fast loop jumped into the safe loop at 3 places, each expecting
a different partially decoded state. Two of them happen before anything
is written for the current sequence: near the end of input, and for long
literals too close to the end for a wild copy. In both cases, rewind ip
to the token, and let the safe loop restart the sequence.
This removes the labels safe_literal_copy_early and safe_literal_copy.
The only remaining entry in the middle of a sequence is safe_match_copy,
with a fully decoded match.
Also comment the state expected at each remaining label and the role of
the safe loop, and remove two comments outdated since decompress_fast*()
left this function.
