Nick Terrell [Thu, 27 Oct 2016 23:19:54 +0000 (16:19 -0700)]
Fix ZSTD_execSequence() performance regression
Commit ae1cb3b3d07024618269b89e3421d828adfd34d9 caused the regression.
It is an instruction alignment issue, because if it is `U64 i` instead
of `U32 i`, the regression returns. This patch fixes the regression
in gcc, but only gets some of the clang performance back.
Benchmarks:
Run on `silesia.tar`. I only show levels 1-5 because the performance
regression was uniform across all levels. I did one run on levels
1-19 and it looked good.
Nick Terrell [Fri, 21 Oct 2016 23:55:26 +0000 (16:55 -0700)]
ZSTD_execSequence() accepts match in last 7 bytes
The zstd reference compressor will not emit a match in the last 7
bytes of a block. The decompressor will also not accept a match
in the last 7 bytes. This patch makes the decompressor accept a
match in the last 7 bytes.
Nick Terrell [Mon, 24 Oct 2016 20:10:13 +0000 (13:10 -0700)]
Merge remote-tracking branch 'upstream/dev' into fixes
* upstream/dev:
added doc\zstd_manual.html
added contrib\gen_html
zstd_compression_format.md moved to doc/
Fix small bug in ZSTD_execSequence()
improved ZSTD_compressBlock_opt_extDict_generic
protect ZSTD_decodeFrameHeader() from invalid usage, as suggested by @spaskob
zstd_opt.h: small improvement in compression ratio
improved dicitonary segment merge
use implicit rules to compile zstd_decompress.c
detect early impossible decompression scenario in legacy decoder v0.5
no repeat mode in legacy v0.5
fixed invalid invocation of dictionary in legacy decoder v0.5
fix edge case
fix command line interpretation
fixed minor corner case
zstd.h: added the Introduction section
fixed clang 3.5 warnings
zstd.h: updated comments
Nick Terrell [Thu, 20 Oct 2016 00:22:08 +0000 (17:22 -0700)]
Reject dictionaries with incomplete entropy tables
If a dictionary specifies that a symbol has probability zero in its
`matchLength`, `literalLength`, or `offset` FSE table, but the symbol
appears when compressing input, the compressor fails.
Ensure that dictionaries support all `matchLength`, and `literalLength`
codes. They must also support all of the `offset` codes required to
represent every possible offset that can appear in the first block.
Nick Terrell [Thu, 20 Oct 2016 23:45:10 +0000 (16:45 -0700)]
Fix small bug in ZSTD_execSequence()
`memmove(op, match, sequence.matchLength)` is not the desired behavior.
Overlap is allowed, and handled as if we did `*op++ = *match++`, which
is not how `memmove()` handles overlap.
Only triggered if both of the following conditions are met:
* The match spans extDict & currentPrefixSegment
* `oLitEnd <= oend_w < oLitEnd + length1 < oMatchEnd <= oend`.
These two conditions imply that the block is less than 15 bytes long.
This bug isn't triggered by the streaming API, because it allocates
enough space for the window size + the block size, so there cannot be
a match that is within 8 bytes of the end and overlaps with itself.
It cannot be triggered by the block decompression API because all of
the decompressed data is in the currentPrefixSegment.
Nick Terrell [Wed, 19 Oct 2016 18:19:54 +0000 (11:19 -0700)]
Fix stack buffer overrun when weightTotal == 0
If `weightTotal == 0`, then `BIT_highbit32(weightTotal)` is
undefined behavior in the case that it calls `__builtin_clz()`.
If `tableLog == HUF_TABLELOG_ABSOLUTEMAX` then we will access one
byte beyond the end of the buffer.
Nick Terrell [Tue, 18 Oct 2016 23:08:52 +0000 (16:08 -0700)]
Unitialized memory read in ZSTD_decodeSeqHeaders()
Caused by two things:
1. Not checking that `ip` is in range except for the first byte.
2. `ZSTDv0{5,6}_decodeLiteralsBlock()` could return a value larger than `srcSize`.
Nick Terrell [Tue, 18 Oct 2016 01:16:57 +0000 (18:16 -0700)]
Fix stack buffer overflow in HUF_readCTable()
If `w ==0` on line 153, then `CTable[n].nbBits == tableLog + 1`.
Then `nbPerRank[CTable[n].nbBits]` and `valPerRank[CTable[n].nbBits]`
are stack buffer overflows.
Nick Terrell [Mon, 17 Oct 2016 23:55:52 +0000 (16:55 -0700)]
Fix buffer overrun in ZSTD_loadDictEntropyStats()
The table log set by `FSE_readNCount()` was not checked in
`ZSTD_loadDictEntropyStats()`. This caused `FSE_buildCTable()`
to stack/heap overflow in a few places.
The benchmarks look good, there is no obvious compression performance regression:
Nick Terrell [Mon, 17 Oct 2016 22:49:50 +0000 (15:49 -0700)]
Fix buffer overrun in ZSTD_loadEntropy()
The table log set by `FSE_readNCount()` was not checked in
`ZSTD_loadEntropy()`. This caused `FSE_buildDTable(dctx->MLTable, ...)`
to overwrite the beginning of `dctx->hufTable`.
The benchmarks look good, there is no obvious performance regression:
Nick Terrell [Fri, 7 Oct 2016 04:32:06 +0000 (21:32 -0700)]
[pzstd] Add asan and tsan tests to travis
gcc-6 tsan is buggy.
It fails to use the correct linker.
It is also broken with `-pie` with linux kernels newer than 4.1, but previous versions require `-pie`...
projects / thirdparty / zstd.git / log
