Merge https://github.com/facebook/zstd into dev

Fix typos.

Merge pull request #2877 from jannkoeker/dev

Add detection when compiling with Clang and Ninja under Windows

Merge pull request #2872 from cntrump/fix_umbrella_header_warning_for_spm

Fix SPM warning: umbrella header for module 'libzstd' does not include header 'xxx.h'

Merge pull request #2845 from senhuang42/appveyor_msvc2

Move visual studio tests from per-release to per-PR

Add GH Actions windows runtime test

Fix build for cygwin/bsd (#2882)

Clarify documentation for -c (#2883)

msvc tests to dev

Update CMakeLists.txt

 Prevents multiple rules error when building with ninja and clang under windows

Remove zstd-umbrella.h

Fix SPM warning: umbrella header for module 'libzstd' does not include header 'xxx.h'

Merge pull request #2869 from felixhandte/oss-fuzz-fix-41005

Determinism: Avoid Mapping Window into Reserved Indices during Reduction

Determinism: Avoid Mapping Window into Reserved Indices during Reduction

PR #2850 attempted to fix a determinism bug that was uncovered by OSS-Fuzz. It
succeeded in addressing that source of non-determinism, but introduced a new
one: it was possible, when index reduction occurred, to map indices in the
window to the reserved value, which would cause them to be zeroed, potentially
altering parsing of the input.

This PR addresses this issue. It makes sure that the bottom of the window is
always `>= ZSTD_WINDOW_START_INDEX`.

I'm not sure if this makes #2850 redundant. I think it's probably still
valuable to have that protection as well.

Credit to OSS-Fuzz for discovering this issue.

Merge pull request #2856 from rex4539/typos

Fix typos

Merge pull request #2858 from cntrump/support_swift_package_manager

Support Swift Package Manager

Merge pull request #2866 from terrelln/linux-O2

[linux-kernel] Don't add -O3 to CFLAGS

[linux-kernel] Don't add -O3 to CFLAGS

It is no longer necessary to get good performance, there is only a small
speed difference between -O2 and -O3, so just stick to the default of
-O2. I've measured neutral compression speed and a ~3% decompression
speed loss in userspace with clang & gcc. I've also measured neutral
compression speed and a ~1% decompression speed loss in the kernel
benchmarks.

This also fixes the stack space usage on parisc. The compiler was buggy
for -O3 and used ~3KB of stack space for several functions. With -O2 the
problem is completely resolved, and stack space is back to a few hundred
bytes.

Additionally, we get a large code size win on gcc:

| Compiler | Before (Bytes) | After (Bytes) | Delta (Bytes) |
|----------|----------------|---------------|---------------|
| gcc-11   |         952754 |        738954 |       -213800 |
| clang-12 |         976290 |        938826 |        -37464 |

Merge pull request #2857 from ko-zu/noexecstack

Remove executable flag from GNU_STACK segment

Merge pull request #2864 from terrelln/linux-opt

[linux-kernel] Don't inline function in zstd_opt.c

[linux-kernel] Don't inline function in zstd_opt.c

The optimal parser is unlikely to be used in the linux kernel in
practice. There is no reason these functions should be force inlined,
since we aren't gaining anything, and are losing build size.

| Compiler | Before (Bytes) | After (Bytes) | Delta (Bytes) |
|----------|----------------|---------------|---------------|
| gcc-11   |        1142090 |        952754 |       -189336 |
| clang-12 |        1228402 |        976290 |       -252112 |

This is a temporary solution pending the resolution of PR #2862 in the
`dev` branch.

Merge pull request #2863 from terrelln/fast-dfast-size

Reduce function size in fast & dfast

Reduce function size in fast & dfast

Take the same approach as in PR #2828 [0] to remove functions that force
inline many function bodies and `switch`. Instead, create one function per
"template" combination, and then switch between these functions. This
allows the compiler to break the large function into many small
functions, which generally helps codegen.

Also, in the `extDict` modes when there is no ext-dict, call the top
level function instead of the force inlined one, to save on code size.

I'm specifically doing this because gcc on the parisc architecture doesn't
handle the large function body well, and ends up using a lot of excess
stack space. Outlining these functions fixes it.

Using `module.modulemap` replace symbol link for public header

Support Swift Package Manager

Remove executable flag from GNU_STACK section

Putting stack marking into every assembly files is required to indicate
that the stack does not need to be executable.
Executable flag on stack conflicts with some security measures, Systemd
MemoryDenyWriteExecute=yes for example.

Fix typos

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

Display command line parameters with concrete values in verbose mode

Integrate verbose mode tests into playTests.sh

Suppress spurious unused parameter warning

Ensure formatting directives for displaying size_t are portable

Ensure print*CParams functions are only defined when used

Add test case for detailed compression parameter verbose output

Merge pull request #2836 from animalize/copy16

ZSTD_copy16() uses ZSTD_memcpy()

Fix const-ness of FIO_displayCompressionParameters

Display --zstd= subparameters in command-line ready form in verbose mode

Merge pull request #2850 from felixhandte/oss-fuzz-fix-40829-for-real-this-time

Fix Determinism Bug: Avoid Reducing Indices to Reserved Values

Fix fullbench CI failure (#2851)

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

Display command line parameters with concrete values in verbose mode

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

ZSTD_copy16() uses SSE2 instructions

This accelerates the decompression speed of MSVC build.

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