Fix LZ4 Compression Buffer Overflow

Fixes issue where, when `zstd --format=lz4` is fed an input larger than 128KB,
the read overruns the input buffer. This changes Zstd to use LZ4 with chained
64KB blocks. This is technically a breaking change in that some third party
LZ4 implementations may not support linked blocks. However, progress should not
be allowed to be stopped by such petty concerns as backwards compatibility!

Add Test on LZ4 Format Input Buffer Overrun

install: changed variable MANDIR into MAN1DIR

MANDIR still exists, and is now the parent of MAN1DIR

zstreamtest : in `-T#s`, s considered a suffix meaning "seconds"

avoid unintentionnally triggering `seedset`,
so that seed gets automatically determined when not set.

updated man page

following patch #931 by @scottchiefbaker

minor update

Merge pull request #931 from scottchiefbaker/documentation

Include information about the benchmark output/methodology

Include information about the benchmark output/methodology

Addresses #930

Merge pull request #924 from facebook/opt2

faster btopt variant

fixed comment, reported by @gyscos

fixed comment, as suggested by @terrelln

Merge pull request #925 from dusta/patch-1

Missing dot

Missing dot

strategy ZSTD_btopt pinned to (0) variant (faster one)

slightly improved compression speed

slightly improved ratio at -22

merging of repcode search into btsearch introduced a small compression ratio regressio at max level :
1.3.2 : 52728769
after repMerge patch : 52760789 (+32020)

A few minor changes have produced this difference.
They can be hard to spot.

This patch buys back about half of the difference,
by no longer inserting position at hc3 when a long match is found there.
It feels strangely counter-intuitive, but works :
after this patch : 52742555 (-18234)

minor : search early-out on sufficient_len for hc3 and rep

very very small speed and ratio increases

btopt0 : a bit faster and weaker

created (hidden) new strategy btopt0

about ~+10% faster but losing ~0.01 compression ratio
(note : amplitude vary a lot depending on files, but direction remains the same)

zstd_opt: minor speed optimization

Calculate reference log2sums only once per serie of sequence
(as opposed to once per sequence)

Also: improved code comments

bench: slightly adjusted display format

adapt accuracy depending on value.
makes it possible to have higher accuracy for small value,
notably small compression speed.
This capability is expected to be useful while modifying optimal parser.

minor spelling fixes

fix ZSTD_COMPRESSBOUND() macro

It was using macro `KB`, which is not defined in `zstd.h`.

Merge pull request #922 from terrelln/signal

[zstd] Fix rare bug with signal handler

Merge pull request #921 from facebook/ubfix

Fixes some arithmetic pointer operations

[zstd] Fix rare bug with signal handler

fix un-initialized memory warning

harmless, but cleaner

Merge pull request #920 from facebook/benchSeparate

Bench multiple files

fix one UB pointer arithmetic in encoder

Instead of calculating distance between 2 memory objects, which is UB,
we extract the offset from object 1, and transfer it into object 2.

fixed one UB pointer arithmetic

Merge pull request #916 from facebook/optMergeRep

Optimal parser part 2 : Merge normal and _extDict parsers

fixed circle-ci script

minor interface adjustments

bench: added cli command `-S` to benchmark multiple files separately

Currently, all files are joined by default,
they are compressed separately but benchmarked together,
providing a single final result.

Benchmarking files separately make it possible to accurately measure difference for each file.
This is expected to be useful while tuning optimal parser.

bench: realTime is a global parameter

like most parameters not directly related to compression

fixed minor warning

warning: void function returning a value
(even if the return value is void)

fixed some complex scenarios

Fixed : multithreading to compress some small data with dictionary
Fixed : ZSTD_initCStream_usingCDict()
Improved streaming memory usage when pledgedSrcSize is known.

Fixed Btree update

ZSTD_updateTree() expected to be followed by a Bt match finder, which would update zc->nextToUpdate.
With the new optimal match finder, it's not necessarily the case : a match might be found during repcode or hash3, and stops there because it reaches sufficient_len, without even entering the binary tree.
Previous policy was to nonetheless update zc->nextToUpdate, but the current position would not be inserted, creating "holes" in the btree, aka positions that will no longer be searched.
Now, when current position is not inserted, zc->nextToUpdate is not update, expecting ZSTD_updateTree() to fill the tree later on.

Solution selected is that ZSTD_updateTree() takes care of properly setting zc->nextToUpdate,
so that it no longer depends on a future function to do this job.

It took time to get there, as the issue started with a memory sanitizer error.
The pb would have been easier to spot with a proper `assert()`.
So this patch add a few of them.

Additionnally, I discovered that `make test` does not enable `assert()` during CLI tests.
This patch enables them.

Unfortunately, these `assert()` triggered other (unrelated) bugs during CLI tests, mostly within zstdmt.
So this patch also fixes them.

- Changed packed structure for gcc memory access : memory sanitizer would complain that a read "might" reach out-of-bound position on the ground that the `union` is larger than the type accessed.
  Now, to avoid this issue, each type is independent.
- ZSTD_CCtxParams_setParameter() : @return provides the value of parameter, clamped/fixed appropriately.
- ZSTDMT : changed constant name to ZSTDMT_JOBSIZE_MIN
- ZSTDMT : multithreading is automatically disabled when srcSize <= ZSTDMT_JOBSIZE_MIN, since only one thread will be used in this case (saves memory and runtime).
- ZSTDMT : nbThreads is automatically clamped on setting the value.

removed wrong assertion

removed a few specialized traces

shortened repcode match finder implementation

fixed corruption issue

still fighting data corruption

due to messed up tree.
Seems to happen when reaching end of buffer.

merged rep search into btMatchSearch

but there is a tree corruption somewhere ...
bug hunt ongoing

Merge pull request #912 from facebook/opt

Optimal parser refactoring

merged repcode search into BT match search

this version has same speed as branch `opt`
which is itself 5-10% slower than branch `dev`
(no identified reason)

It does not compress exactly the same as `opt` or `dev`,
maybe because it doesn't stop search after repcodes,
leading to sometimes better compression, sometimes worse
(by a small margin).

warning : _extDict path does not work for the time being
This means that benchmark module works,
but file module will fail with large files (and high compression level).
Objective is to fuse _extDict path into current one,
in order to have a single parser to maintain.

cmake: fixed lib/CMakeLists.txt

changed file name from zstd_compress.h to zstd_compress_internal.h

reduced scope of multiple variables

renamed some variables for better understanding

lib/compress: created ZSTD_LLcode() and ZSTD_MLcode()

transform length into code.
Since transformation is needed in several places throughout the code,
better write the logic in one place.

zstd_opt: simplified ZSTD_getPrice() and ZSTD_updatePrice() interface

ZSTD_getPrice() and ZSTD_updatePrice() accept normal matchlength as argument
instead of matchlength-MINMATCH,
which makes them easier / more logical to use and read.
Conversion is simply done internally.

zstd_opt: refactor code for improved readability

renamed variables to be more meaningful
reduced scope of multiple variables
removed some useless var attribution

zstd_opt: ensure sufficient_len < ZSTD_OPT_NUM to simplify some tests

renamed zstd_compress.h into zstd_compress_internal.h

to emphasize the fact that all definitions it contains
must remain private, accross lib/compress modules.

moved a few structures from `zstd_internal.h` to `zstd_compress.h`

which is a more precise scope

Merge pull request #908 from facebook/ubsan

Modified one pointer arithmetic expression to a more conformant way.

Merge pull request #906 from facebook/fixAutoPledge

fix : ZSTD_compress_generic(,,,ZSTD_e_end) automatically sets pledgedSrcSize

fixed zstreamtest declaration after statement

removed line with `//` comment

this is for a different topic
(better parameter adaptation for small files + dictionary and/or custome parameters)

minor refactor

added some traces and assert
related to hunting a potential ubsan error in 32-bits more
(it ends up being a compiler-side issue : https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82802).

Modified one pointer arithmetic expression for a more conformant way.

Merge pull request #905 from terrelln/skip

Allow skippable frames of any size

fix : ZSTD_compress_generic(,,,ZSTD_e_end) automatically sets pledgedSrcSize

as per documentation, on ZSTD_setPledgedSrcSize() :
> If all data is provided and consumed in a single round,
> this value (pledgedSrcSize) is overriden by srcSize instead.

This wasn't applied before compression level is transformed into compression parameters.
As a consequence, small input missed compression parameters adaptation.

It seems to work fine now : compression was compared with ZSTD_compress_advanced(),
results were the same.

Test large skippable frames

Allow skippable frames of any size

removed direct call to malloc() from pool.c

Merge pull request #903 from terrelln/empty-input

[libzstd] Fix parameter selection for empty input

Merge pull request #902 from terrelln/buck

Update BUCK files

[libzstd] Fix parameter selection for empty input

ZSTD_compress() and friends would treat an empty input as an unknown size
when selecting parameters. Thus, they would drastically overallocate the
context. Tell ZSTD_getParams() that the source size is 1 when it is empty.

Update BUCK files

* Correct XXH namespace (Fixes #901)
* Multithreading always enabled
* GZIP/LZ4/LZMA always enabled
* Legacy support always fully enabled

fixed zbufftest

preserve "pledgedSrcSize=0" means "unknown" in init_advanced()

Merge pull request #896 from facebook/simplifyio

fileio and bench : ZSTD_NEWAPI as the only code path

fixed missing zstdmt_compress.h dependency

we lose a warning message :
when a job size is chosen < minimum job size for multithreading,
it is automatically resized to minimum size.

If this information is really useful, it should be present in zstd.h now.

bench: fixed Visual warning regarding struct initialization

also :
removed dependency on zstdmt_compress.h
removed several unused macros
fileio : small code refactoring to reduce some variable scope

IO and bench : ZSTD_NEWAPI is the only remaining code path

removed the other 2 code paths (single thread, and ZSTDMT ones)
keeping only the new advanced API, for easier code coverage.

It shall also fix identified issue with Visual Studio
which doesn't have ZSTD_NEWAPI defined.

Merge pull request #895 from facebook/fileSize_unknown

Distinguish 0-size from size-unavailable

fixed wrong test to display compression status

fixed zlib wrapper

it was invoking ZSTD_initCStream_advanced() with pledgedSrcSize==0 and contentSizeFlag=1
which means "empty"
while the intention was to mean "unknown".

The contentSizeFlag==1 is new, it is a consequence of setting this value to 1 by default.

The solution selected here is to pass ZSTD_CONTENTSIZE_UNKNOWN to mean "unknown".
So contentSizeFlag remains set (it wasn't in previous versions).

Merge pull request #891 from facebook/contentSize

Content size

Merge pull request #890 from terrelln/dev

Don't allow default tables to repeat

added a check to ensure 0-size is present in frame header

UTIL_getFileSize() returns UTIL_FILESIZE_UNKNOWN on failure

UTIL_getFileSize() used to return zero on failure.
This made it impossible to distinguish a failure from a genuine empty file.
Both cases where coalesced.

Adding UTIL_FILESIZE_UNKNOWN constant has many consequences on user code,
since in many places, the `0` was assumed to mean "error".
This is no longer the case, and the error code must be actively checked.

Merge pull request #892 from terrelln/seq-test

[test] Exercise all codes in dictionary tables

fixed : Visual build compressing stdin with multi-threading enabled fails

It was multiple reasons stacked :
- Visual use a different code path, because ZSTD_NEWAPI is not defined
- fileio.c sends `0` as `pledgedSrcSize` to mean `ZSTD_CONTENTSIZE_UNKNOWN`  (fixed)
- ZSTDMT_resetCCtx() interpreted `0` as "empty" instead of "unknown" (fixed)

Merge pull request #894 from felixhandte/add-check-target

Add `check` Target to Makefile

Add `check` Target to Makefile

[test] Exercise all codes in dictionary tables

edited ZSTD_initCStream_advanced() comment

playtest : minor cosmetic changes

Don't allow default tables to repeat

It isn't useful in any case to repeat default tables.
Saves a few bytes on Silesia, since we don't trigger the dictionary
heuristic.

Before: 211988480 => 73651998 bytes
After:  211988480 => 73651721 bytes

Merge pull request #889 from terrelln/bug-fix

Fix invalid use of dictionary offcode table

dictionary compression use correct file size estimation

when determining compression parameters
to compress one file only.

For multiple files, it still "bets" that files are going to be small.

There was also a bug recently added in ZSTD_CCtx_loadDictionary_advanced()
making it incapable to use pledgedSrcSize to determine compression parameters.

changed API comments to invite using macro ZSTD_CONTENTSIZE_UNKNOWN

to mean "pledgedSrcSize is not known at init time" instead of `0`.
Note that, a few prototypes created and documented with `0` to mean "unknown" still interpret "0" as unknown,
to avoid breaking 3rd party applications which depend on this behavior.
But this value is no longer recommended to mean "unknown".

In some future version, it might be possible to switch "0" to mean "empty",
as is already the case for several prototypes.
The advantage is that pledgedSrcSize field would have same behavior accross entire API,
making it easier to reason about.

Note that all concerned prototypes belong to the "experimental" API section.

srcSize is controlled at end of compression,
so if someone uses "0" to mean "unknown" while it effectively means "empty",
this is immediately caught by the compression function, which generates an error code : ZSTD_ERROR_srcSize_wrong

minor : zstd -l -v display each file name

add test for presence of decompressed size field in header

previous test was "display" only, it wouldn't trigger an error in case of missing header.

fixed ZSTDMT_initCStream() when contentSizeFlag==1 by default

and a wrong test in zstreamtest --mt

fixed ZSTD_initCStream_advanced() behavior, which depends on contentSizeFlag,

and a stream fuzzer test, which was incorrect
(relied on 0 being unconditionnally transformed into `ZSTD_CONTENTSIZE_UNKNOWN`)

contentSizeFlag enabled by default would also fail for streaming and MT operations

fixed

ensure fParams.contentSizeFlag starts at 1

such default was failing for ZSTD_compressBegin/ZSTD_compressContinue
fixed too

fileio: content size is enabled by default

Add DEBUGLOG() that prints FSE encoding types

Fix invalid use of dictionary offcode table

Fixes #888.