Rewrite Fix to Still Auto-Vectorize

Avoid Reducing Indices to Reserved Values

Previously, if an index was equal to `reducerValue + 1`, it would get remapped
during index reduction to 1 i.e. `ZSTD_DUBT_UNSORTED_MARK`. This can affect the
parsing of the input slightly, by causing tree nodes to be nullified when they
otherwise wouldn't be. This hardly matters from a correctness or efficiency
perspective, but it does impact determinism.

So this commit changes index reduction to avoid mapping indices to collide with
`ZSTD_DUBT_UNSORTED_MARK`.

Merge pull request #2849 from terrelln/linux-kernel-backport

Backport zstd patch from LKML

Backport zstd patch from LKML

Credit to Nathan Chancellor for the bug fix and Nick Desaulniers for the
bug report.

Link: https://github.com/ClangBuiltLinux/linux/issues/1486
Link: https://lore.kernel.org/all/20211021202353.2356400-1-nathan@kernel.org/

Merge pull request #2846 from senhuang42/fix_appveyor

Use unused functions to appease Visual Studio

Merge pull request #2839 from Svetlitski-FB/improve-verbose-output

Improvements to verbose mode output - decompression memory usage

Report memory required to decompress while compressing in verbose mode

Void out unused functions

Move mingw tests from appveyor to github actions (#2838)

Fix oss fuzz test error (#2837)

minor improvements to benchmark display

Merge pull request #2829 from facebook/ZSTD_DECODER_INTERNAL_BUFFER

minor : change build macro to ZSTD_DECODER_INTERNAL_BUFFER

fix minor cast warning

added minimum for decoder buffer

also : introduced macro BOUNDED()

Merge pull request #2830 from facebook/clevels

separate compression level tables into their own file

Merge pull request #2828 from terrelln/lazy-compile

[lazy] Speed up compilation times

separate compression level tables into their own files

that's clearer than finding the tables somewhere in the middle of `compress.c`.

Also, down the line, it may potentially allows zstd to feature adjusted tables depending on target cpu.

build macro ZSTD_DECODER_INTERNAL_BUFFER

just to make the topic more accessible for potential users.

Reduce size of dctx by reutilizing dst buffer (#2751)

* Reduce size of dctx by reutilizing dst buffer

Co-authored-by: Binh Vo <binhvo@fb.com>

Merge pull request #2822 from marxin/fix-zstd-thread-pool-documentation

Support thread pool section in HTML documentation.

[lazy] Speed up compilation times

Speed up compilation times by moving each specialized search function
into its own function. This is faster because compilers can handle many
smaller functions much faster than one gigantic function. The previous
approach generated one giant function with `switch` statements and
inlining to select the implementation.

| Compiler | Flags                               | Dev Time (s) | PR Time (s) | Delta |
|----------|-------------------------------------|--------------|-------------|-------|
| gcc      | -O3                                 |         16.5 |         5.6 |  -66% |
| gcc      | -O3 -g -fsanitize=address,undefined |        158.9 |        38.2 |  -75% |
| clang    | -O3                                 |         36.5 |         5.5 |  -85% |
| clang    | -O3 -g -fsanitize=address,undefined |         27.8 |        17.5 |  -37% |

This also reduces the binary size because the search functions are no
longer inlined into the main body.

| Compiler | Dev libzstd.a Size (B) | PR libzstd.a Size (B) | Delta |
|----------|------------------------|-----------------------|-------|
| gcc      |                1563868 |               1308844 |  -16% |
| clang    |                1924372 |               1376020 |  -28% |

Finally, the performance is not impacted significantly by this change,
in fact we generally see a small speed boost.

| Compiler | Level | Dev Speed (MB/s) | PR Speed (MB/s) | Delta |
|----------|-------|------------------|-----------------|-------|
| gcc      |     5 |            110.6 |           110.0 | -0.5% |
| gcc      |     7 |             70.4 |            72.2 | +2.5% |
| gcc      |     9 |             53.2 |            53.5 | +0.5% |
| gcc      |    13 |             12.7 |            12.9 | +1.5% |
| clang    |     5 |            113.9 |           110.4 | -3.0% |
| clang    |     7 |             67.7 |            70.6 | +4.2% |
| clang    |     9 |             51.9 |            52.2 | +0.5% |
| clang    |    13 |             12.4 |            13.3 | +7.2% |

The compression strategy is unmodified in this PR, so the compressed size
should be exactly the same. I may have a follow up PR to slightly improve
the compression ratio, if it doesn't cost too much speed.

Merge pull request #2825 from terrelln/huf-asm-comments

[asm] Switch to C style comments

[asm] Switch to C style comments

Switch to C style comments for increased portability, and consistency.

Merge pull request #2800 from animalize/fix_c89

Fix a C89 error in msvc

Support thread pool section in HTML documentation.

Merge pull request #2774 from felixhandte/zstd-dfast-pipelined-single

Pipelined Implementation of ZSTD_dfast

Convert Outer Control Structure to Loop

Merge pull request #2813 from marxin/streaming-compress-enhance

Enhance streaming_compression examples.

Enhance streaming_compression examples.

Add level argument to the first test and be more verbose about
used compression level and number of threads.

Merge pull request #2820 from terrelln/nb-compares

[binary-tree] Fix underflow of nbCompares

Merge pull request #2819 from terrelln/ldm-hash-rate-log

[ldm] Fix ZSTD_c_ldmHashRateLog bounds check

Merge pull request #2818 from terrelln/indentation-fix

[nit] Fix buggy indentation

Merge pull request #2817 from terrelln/multiple-ddict-fix

[multiple-ddicts] Fix NULL checks

[binary-tree] Fix underflow of nbCompares

Fix underflow of `nbCompares` by switching to an `int` and comparing
`nbCompares > 0`. This is a minimal fix, because I don't want to change
the logic. These loops seem to be doing `nbCompares + 1` comparisons.

The bug was reported by Dan Carpenter and found by Smatch static
checker.

https://lore.kernel.org/all/20211008063704.GA5370@kili/

[multiple-ddicts] Fix NULL checks

The bug was reported by Dan Carpenter and found by Smatch static
checker.

https://lore.kernel.org/all/20211008063704.GA5370@kili/

[ldm] Fix ZSTD_c_ldmHashRateLog bounds check

There is no minimum value check, so the parameter could be negative.
Switch to the standard pattern of using `BOUNDCHECK()`.

The bug was reported by Dan Carpenter and found by Smatch static
checker.

https://lore.kernel.org/all/20211008063704.GA5370@kili/

[nit] Fix buggy indentation

The bug was reported by Dan Carpenter and found by Smatch static
checker.

https://lore.kernel.org/all/20211008063704.GA5370@kili/

Style: Add Comments to Variables and Move a Couple into the Loop

Fix Flaky Test

This test depended on `_extDict` and `_noDict` compressing identically, which
is not a guarantee we make, AFAIK.

Update results.csv

Simplify DMS Implementation by Removing noDict Support

Fall Back in _extDict to New _noDict Rather than Old Merged Impl

Nit: Rename Function

Nit: Unnest Blocks that Don't Declare Anything

Search One Last Position

Advance Long Index Lookup (+0.5% Speed)

This lookup can be advanced to before the short match check because either way
we will use it (in the next loop iter or in `_search_next_long`).

Write Back Advanced Hash in Long Matches as Well (+Ratio)

Since we're now hashing the position ahead even if we find a long match and
don't search that next position, we can write it back into the hashtable even
in long matches. This seems to cost us no speed, and improves compression
ratio slightly!

Use Look-Ahead Hash for Next Long Check after Short Match (+0.5% Speed)

This costs a little ratio, unfortunately.

Hash Long One Position Ahead (+2.5% Speed)

Aside from maybe a latency win in the loop, this means that when we find a
short match, we've already done the hash we need to check the next long match.

Pull Match Found Stuff Out of the Loop

Extract Working Variables

Track Step Rather than Recalculating (+0.5% Speed)

Extract Single-Segment Variant of ZSTD_dfast

Limit train samples (#2809)

* Limit training samples size to 2GB

* simplified DISPLAYLEVEL() macro to use global vqriable instead of local.

* refactored training samples loading

* fixed compiler warning

* addressed comments from the pull request

* addressed @terrelln comments

* missed some fixes

* fixed type mismatch

* Fixed bug passing estimated number of samples rather insted of the loaded number of samples.
Changed unit conversion not to use bit-shifts.

* fixed a declaration after code

* fixed type conversion compile errors

* fixed more type castting

* fixed more type mismatching

* changed sizes type to size_t

* move type casting

* more type cast fixes

Merge pull request #2747 from Helflym/dev

Add AIX support in Makefile

Merge pull request #2803 from terrelln/linux-kernel-ci

[contrib][linux-kernel] Add standard warnings and -Werror to CI

Merge pull request #2802 from solbjorn/fix-kernel-wundef

[contrib][linux] Fix -Wundef inside Linux kernel tree

Merge pull request #2810 from 3nids/patch-1

add missing BUNDLE DESTINATION

Merge pull request #2755 from senhuang42/skip_long_matches_lazy

Skip most long matches in lazy hash table update

add missing BUNDLE DESTINATION

fixes build on iOS

Fix ZSTD_countTrailingZeros() bug

`>> 3` is wrong.

Update regression test

Pull hot loop into its own function

Try beginning and end of match

Skip most long matches in lazy hash table update

Merge pull request #2808 from terrelln/huf-oss-fuzz-fix

[huf] Fix OSS-Fuzz assert

Merge pull request #2805 from nolange/smaller_code_with_disabled_features

Smaller code with disabled features

[huf] Fix OSS-Fuzz assert

PR #2784 introduced a bug in the decompressor that caused some valid
inputs to fail to decompress. The bitstream isn't reloaded after the 4X*
loop if the number of elements remaining is small enough, causing us to
read more bits than are available in the bitcontainer.

This was caught by the MSAN fuzzer in OSS-Fuzz because the assembly
implementation isn't used in the MSAN build.

Credit to OSS-Fuzz.

Use __assume(0) for unreachable code path in msvc

msvc will optimize away the condition check.

minor : fix comment

provide correct reasons to include zstd_internal.h

added link to RFC

minor : makes the "stable" property of Zstandard format more prominent

zstd_decompress: use a helper function for context create

Multiple ZSTD_createDCtx* functions call other (public)
ZSTD_createDCtx* functions, this makes it harder for humans
and compilers to throw out code that is not used.

This farms out the logic into a static function, if a program
only uses a single ZSTD_createDCtx variant, all others can be easily
dropped and the remaining implementation can be specialized.

decompress: conditionally remove bmi2 from context

Use an helper function, which will just return 0 in case
the feature is disabled.
Allows constant propagation and removal of dead code.

decompress: conditionally remove legacy members from context

Remove the then unneeded variables from the struct,
and all accesses to them.

[contrib][linux] Fix -Wundef inside Linux kernel tree

Commit d7ef97a013b5
("[build] Fix oss-fuzz build with the dataflow sanitizer") broke
build inside Linux-kernel after 'import', as it no longer can
conditionally remove ZSTD_MEMORY_SANITIZER definition from
the #if DEF_A || DEF_B block. This emits -Wundef warning which
can be treated as error.
Split this preprocessor condition into two separate conditions
to fix this.

Fixes: d7ef97a013b5 ("[build] Fix oss-fuzz build with the dataflow sanitizer")
Signed-off-by: Alexander Lobakin <alobakin@pm.me>

Don't initialize the first parameter of _BitScanForward* functions

Like the document example, no need to initialize `r` to 0.
https://docs.microsoft.com/en-us/cpp/intrinsics/bitscanforward-bitscanforward64

Don't initialize the first parameter of _BitScanReverse* functions

Like the document example, no need to initialize `r` to 0.
https://docs.microsoft.com/en-us/cpp/intrinsics/bitscanreverse-bitscanreverse64

Fix a C89 error in msvc

Variables (r) must be declared at the beginning of a code block.
This causes msvc2012 to fail to compile 64-bit build.

[contrib][linux-kernel] Add standard warnings and -Werror to CI

Test the kernel build with the standard warnings enabled so that we
don't miss issues like fixed in PR #2802.

Stacked on top of PR #2802 so CI passes, so it includes the fix. But, I
won't merge until it is merged, so @solbjorn gets the credit for the
fix.

Merge pull request #2790 from solbjorn/huf-asm-kernel

[contrib][linux] Fix build after introducing ASM HUF implementation

Merge pull request #2796 from terrelln/linux-fixes

[lib] Make lib compatible with `-Wfall-through` excepting legacy

Merge pull request #2799 from terrelln/oss-fuzz-build

[build] Fix oss-fuzz build with the dataflow sanitizer

Merge pull request #2798 from abxhr/typo-fix

Fix typo

[build] Fix oss-fuzz build with the dataflow sanitizer

The dataflow sanitizer requires all code to be instrumented. We can't
instrument the ASM function, so we have to disable it.

Merge pull request #2797 from facebook/btconst

minor: constify MatchState* parameter when possible

Fix typo

[lib] Make lib compatible with `-Wfall-through` excepting legacy

Switch to a macro `ZSTD_FALLTHROUGH;` instead of a comment. On supported
compilers this uses an attribute, otherwise it becomes a comment.

This is necessary to be compatible with clang's `-Wfall-through`, and
gcc's `-Wfall-through=2` which don't support comments. Without this the
linux build emits a bunch of warnings.

Also add a test to CI to ensure that we don't regress.

constify MatchState* parameter when possible

turns out, it's possible to constify MatchState* parameter
in some parts of the binary tree algorithm,
making it a pure read-only parameter,
as opposed to a mutable state.

This is supposed to be helpful for both maintenance and the compiler.

[contrib][linux] Add contrib/linux-kernel/linux to .gitignore

The mentioned path is being created/used by the 'import' rule for
generating source files for Linux kernel.

Signed-off-by: Alexander Lobakin <alobakin@pm.me>

[contrib][linux] Add huf_decompress_amd64.o target to Makefile

Commit a5f2c4552803 ("Huffman ASM") added a new ASM source file,
but it wasn't added to the kernel Makefile despite that it received
support for Huffman ASM according to the internal definitions. This
leads to undefined references, as huf_decompress.o now calls those
ASM functions.
Add it to the list of sources when building inside the kernel tree.
Kbuild can handle .S files just fine, so none additional rules
needed.

Fixes: a5f2c4552803 ("Huffman ASM")
Signed-off-by: Alexander Lobakin <alobakin@pm.me>

[contrib][linux] Fix build with CONFIG_WERROR

Linux 5.15 introduces a new Kconfig option, CONFIG_WERROR, which
forces -Werror for the entire kernel.
Current in-kernel ZSTD implementation uses functions deprecated
in 1.5.0, and thus fails on -Wdeprecated-declarations.
Turn this particular error into warning to be able to build the
kernel with CONFIG_WERROR. I'm not disabling them completely to
make sure they'll be visible and [hopefully] fixed sooner or later.

Signed-off-by: Alexander Lobakin <alobakin@pm.me>

Merge pull request #2780 from senhuang42/blocksplit_stack_reduce

Reduce stack usage of block splitter

Move block splitter from stack to CCtx

Merge pull request #2795 from terrelln/linux-fixes

[contrib][linux] Reduce stack usage by 80 bytes

[contrib][linux] Reduce stack usage by 80 bytes

Instead of calling `ZSTD_compress_advanced()` and
`ZSTD_initCStream_advanced()`, which each take a `ZSTD_parameters` by
value, use the new advanced API.

Stack usage went from 2024 -> 1944.

Merge pull request #2794 from terrelln/spdx-license

[contrib][linux] Fix up SPDX license identifiers

Merge pull request #2793 from facebook/rdoc

Minor documentation update

[contrib][linux] Fix up SPDX license identifiers

Correctly identify that we are GPL v2+ or BSD 3 clause, as pointed out
in issue #2663.

regenerated zstdless.1