]> git.ipfire.org Git - thirdparty/zstd.git/commit
[lib] Fix determinism bug in the optimal parser
authorNick Terrell <terrelln@fb.com>
Thu, 13 May 2021 22:44:12 +0000 (15:44 -0700)
committerNick Terrell <terrelln@fb.com>
Fri, 14 May 2021 00:05:59 +0000 (17:05 -0700)
commit91c9a247b67374b74753a7d3dcc8999db710b139
tree393a675814b417be348587abc8ab5333e80478ae
parent06718087f816a705aa40820715d40b540dbe3575
[lib] Fix determinism bug in the optimal parser

`ZSTD_insertBt1()` has a speed optimization that skips the prefix of
very long matches.

https://github.com/facebook/zstd/blob/40def70387f99b239f3f566ba399275a8fd44cde/lib/compress/zstd_opt.c#L476

This optimization is based off the length longest match found. However,
when indices are reset, we only ensure that we can reference the whole
window starting from `ip`. If the previous block ended with a long match
then `nextToUpdate` could be much less than `ip`. It might be far enough
back that `nextToUpdate < maxDist`, so it doesn't have a full window of
data to reference. This can cause non-determinism bugs, because we may
find a match that is beyond `ip - maxDist`, and may sometimes be
un-referencable, and that match triggers the speed optimization.

The fix is to base the `windowLow` off of the `target` of
`ZSTD_updateTree_internal()`, because anything below that value will be
obsolete by the time `ZSTD_updateTree_internal()` completes.
lib/compress/zstd_opt.c