fix test

minor improvement to level 3 dictionary compression ratio

small dictionary compression speed improvement

not as good as small-blocks improvement,
but generally positive.

Merge pull request #4167 from facebook/ci_m32test_faster

attempt to make 32-bit tests faster

attempt parallel test running with -j

measure if -O2 makes the test complete faster

attempt to make 32-bit tests faster

this is the longest CI test, reaching ~40mn on last PR

Merge pull request #4165 from facebook/cspeed_cmov

Improve compression speed on small blocks

rename variable name

findMatch -> matchFound
since it's a test, as opposed to an active search operation.
suggested by @terrelln

fixed parameter ordering in `dfast`

noticed by @terrelln

Merge pull request #4164 from facebook/spec_043

spec update: huffman prefix code paragraph

minor: better variable naming

added ascending order example

make __asm__ a __GNUC__ specific

store dummy bytes within ZSTD_match4Found_cmov()

feels more logical, better contained

introduce memory barrier to force test order

suggested by @terrelln

made search strategy switchable

between cmov and branch
and use a simple heuristic based on wlog to select between them.

note: performance is not good on clang (yet)

refactor search into an inline function

for easier swapping with a parameter

refactor huffman prefix code paragraph

minor refactor zstd_fast

make hot variables more local

Merge pull request #4160 from facebook/fix_nightly

fix dependency for nightly github actions tests

fix dependency for nightly github actions tests

Merge pull request #4159 from facebook/spec_refactor_fse

specification update

refactor documentation of the FSE decoding table build process

Merge pull request #4153 from artem/fix-meson-includes

meson: Do not export private headers in libzstd_dep to avoid name clash

Merge pull request #4156 from facebook/rm_circleci

removing nightly tests built on circleci

Merge pull request #4157 from facebook/fix_result_c

fix incorrect pointer manipulation

Merge pull request #4158 from facebook/benchzstd_fclose

fix missing fclose()

fix missing fclose()

fix #4151

fix incorrect pointer manipulation

fix #4155

removing nightly tests built on circleci

Merge pull request #4154 from dearblue/freebsd-14.1

Update FreeBSD VM image to 14.1

meson: Fix contrib and tests build

meson: Do not export private headers in libzstd_dep to avoid name clash

This way libzstd_dep does not override, for instance, <xxhash.h>

Update FreeBSD VM image to 14.1

FreeBSD 14.0 will reach the end of life on 2024-09-30.
The updated 14.1 is scheduled to end-of-life on 2025-03-31.

ref. https://www.freebsd.org/releases/14.2R/schedule/

Merge pull request #4146 from facebook/dictBench_Doc

update documentation: specify that Dictionary can be used for benchmark

Merge pull request #4013 from elasota/spec-clarify-offset-code-overflow

Specify that decoders may reject non-zero probabilities for larger offset codes than implementation supports

update documentation to specify that Dictionary can be used for benchmark

fix #4139

Included suggestion from @neheb

Fixed warning when compiling pzstd with CPPFLAGS=-Wunused-result and CXXFLAGS=-std=c++17

Merge pull request #4119 from xionghul/dev

Fix zstd-pgo run error

Merge pull request #4143 from facebook/fix_dictsizemin_dic

fix doc nit: ZDICT_DICTSIZE_MIN

Optimize compression by avoiding unpredictable branches

Avoid unpredictable branch. Use conditional move to generate the address
that is guaranteed to be safe and compare unconditionally.
Instead of

if (idx < limit && x[idx] == val ) // mispredicted idx < limit branch

Do

addr = cmov(safe,x+idx)
if (*addr == val && idx < limit) // almost always false so well predicted

Using microbenchmarks from https://github.com/google/fleetbench,
I get about ~10% speed-up:

name                                                                                          old cpu/op   new cpu/op    delta
BM_ZSTD_COMPRESS_Fleet/compression_level:-7/window_log:15                                     1.46ns ± 3%   1.31ns ± 7%   -9.88%  (p=0.000 n=35+38)
BM_ZSTD_COMPRESS_Fleet/compression_level:-7/window_log:16                                     1.41ns ± 3%   1.28ns ± 3%   -9.56%  (p=0.000 n=36+39)
BM_ZSTD_COMPRESS_Fleet/compression_level:-5/window_log:15                                     1.61ns ± 1%   1.43ns ± 3%  -10.70%  (p=0.000 n=30+39)
BM_ZSTD_COMPRESS_Fleet/compression_level:-5/window_log:16                                     1.54ns ± 2%   1.39ns ± 3%   -9.21%  (p=0.000 n=37+39)
BM_ZSTD_COMPRESS_Fleet/compression_level:-3/window_log:15                                     1.82ns ± 2%   1.61ns ± 3%  -11.31%  (p=0.000 n=37+40)
BM_ZSTD_COMPRESS_Fleet/compression_level:-3/window_log:16                                     1.73ns ± 3%   1.56ns ± 3%   -9.50%  (p=0.000 n=38+39)
BM_ZSTD_COMPRESS_Fleet/compression_level:-1/window_log:15                                     2.12ns ± 2%   1.79ns ± 3%  -15.55%  (p=0.000 n=34+39)
BM_ZSTD_COMPRESS_Fleet/compression_level:-1/window_log:16                                     1.99ns ± 3%   1.72ns ± 3%  -13.70%  (p=0.000 n=38+38)
BM_ZSTD_COMPRESS_Fleet/compression_level:0/window_log:15                                      3.22ns ± 3%   2.94ns ± 3%   -8.67%  (p=0.000 n=38+40)
BM_ZSTD_COMPRESS_Fleet/compression_level:0/window_log:16                                      3.19ns ± 4%   2.86ns ± 4%  -10.55%  (p=0.000 n=40+38)
BM_ZSTD_COMPRESS_Fleet/compression_level:1/window_log:15                                      2.60ns ± 3%   2.22ns ± 3%  -14.53%  (p=0.000 n=40+39)
BM_ZSTD_COMPRESS_Fleet/compression_level:1/window_log:16                                      2.46ns ± 3%   2.13ns ± 2%  -13.67%  (p=0.000 n=39+36)
BM_ZSTD_COMPRESS_Fleet/compression_level:2/window_log:15                                      2.69ns ± 3%   2.46ns ± 3%   -8.63%  (p=0.000 n=37+39)
BM_ZSTD_COMPRESS_Fleet/compression_level:2/window_log:16                                      2.63ns ± 3%   2.36ns ± 3%  -10.47%  (p=0.000 n=40+40)
BM_ZSTD_COMPRESS_Fleet/compression_level:3/window_log:15                                      3.20ns ± 2%   2.95ns ± 3%   -7.94%  (p=0.000 n=35+40)
BM_ZSTD_COMPRESS_Fleet/compression_level:3/window_log:16                                      3.20ns ± 4%   2.87ns ± 4%  -10.33%  (p=0.000 n=40+40)

I've also measured the impact on internal workloads and saw similar
~10% improvement in performance, measured by cpu usage/byte of data.

fix doc nit: ZDICT_DICTSIZE_MIN

fix #4142

Merge pull request #4129 from facebook/mitigate_32bit

Limit range of operations on Indexes in 32-bit mode

Limit range of operations on Indexes in 32-bit mode

and use unsigned type.
This reduce risks that an operation produces a negative number when crossing the 2 GB limit.

Merge pull request #4128 from facebook/dependabot/github_actions/github/codeql-action-3.26.2

Bump github/codeql-action from 3.25.1 to 3.26.2

Bump github/codeql-action from 3.25.1 to 3.26.2

Bumps [github/codeql-action](https://github.com/github/codeql-action) from 3.25.1 to 3.26.2.
- [Release notes](https://github.com/github/codeql-action/releases)
- [Changelog](https://github.com/github/codeql-action/blob/main/CHANGELOG.md)
- [Commits](https://github.com/github/codeql-action/compare/c7f9125735019aa87cfc361530512d50ea439c71...429e1977040da7a23b6822b13c129cd1ba93dbb2)

---
updated-dependencies:
- dependency-name: github/codeql-action
  dependency-type: direct:production
  update-type: version-update:semver-minor
...

Signed-off-by: dependabot[bot] <support@github.com>

Merge pull request #4122 from facebook/dependabot/github_actions/actions/setup-java-4

Bump actions/setup-java from 3 to 4

Bump actions/setup-java from 3 to 4

Bumps [actions/setup-java](https://github.com/actions/setup-java) from 3 to 4.
- [Release notes](https://github.com/actions/setup-java/releases)
- [Commits](https://github.com/actions/setup-java/compare/v3...v4)

---
updated-dependencies:
- dependency-name: actions/setup-java
  dependency-type: direct:production
  update-type: version-update:semver-major
...

Signed-off-by: dependabot[bot] <support@github.com>

Merge pull request #4115 from Adenilson/leak01

[zstd][leak] Avoid memory leak on early return of ZSTD_generateSequence

Merge pull request #4114 from Adenilson/trace01

[riscv] Enable support for weak symbols

Merge pull request #4113 from facebook/fix4110

formatString_u() can display numbers > 100

Fix zstd-pgo run error

The -Werror=missing-profile caused thread/zlib/lzma/lz4 detection failure
when build with profile-use, thus caused ZSTD_MULTITHREAD etc. is not
defined for profile-use, then there will be many profile mismatch information
in output and the final binary reports run error sometimes as below:

Error : ZSTD_CCtx_setParameter(ctx, ZSTD_c_nbWorkers, adv->nbWorkers) failed : Unsupported parameter

Signed-off-by: Xionghu Luo <xionghuluo@tencent.com>

Merge pull request #4109 from facebook/actionsTest

added android-ndk-build

[zstd][leak] Avoid memory leak on early return of ZSTD_generateSequence

Sanity checks on a few of the context parameters (i.e. workers and block size)
may prompt an early return on ZSTD_generateSequences.

Allocating the destination buffer past those return points avoids a potential
memory leak.

This patch should fix issue #4112.

[riscv] Enable support for weak symbols

Both gcc and clang support weak symbols on RISC-V, therefore
let's enable it.

This should fix issue #4069.

fix c90 comment style

formatString_u() can display numbers > 100

fixes #4110

Merge pull request #4111 from facebook/dependabot/github_actions/msys2/setup-msys2-2.24.1

Bump msys2/setup-msys2 from 2.24.0 to 2.24.1

Bump msys2/setup-msys2 from 2.24.0 to 2.24.1

Bumps [msys2/setup-msys2](https://github.com/msys2/setup-msys2) from 2.24.0 to 2.24.1.
- [Release notes](https://github.com/msys2/setup-msys2/releases)
- [Changelog](https://github.com/msys2/setup-msys2/blob/main/CHANGELOG.md)
- [Commits](https://github.com/msys2/setup-msys2/compare/5df0ca6cbf14efcd08f8d5bd5e049a3cc8e07fd2...ddf331adaebd714795f1042345e6ca57bd66cea8)

---
updated-dependencies:
- dependency-name: msys2/setup-msys2
  dependency-type: direct:production
  update-type: version-update:semver-patch
...

Signed-off-by: dependabot[bot] <support@github.com>

Merge pull request #4102 from proppy/decodecorpus-ext

tests/decodecorpus: add more advanced options

added android-ndk-build

Merge pull request #4107 from Adenilson/ndk01

[zstd][android] Fix build with NDK r27

[zstd][android] Fix build with NDK r27

The NDK cross compiler declares the target as __linux (which is
not technically incorrect), which triggers the enablement of _GNU_SOURCE
in the newly added code that requires the presence of qsort_r() used
in the COVER dictionary code.

Even though the NDK uses llvm/libc, it doesn't declare qsort_r()
in the stdlib.h header.

The build fix is to only activate the _GNU_SOURCE macro if the OS is
*not* Android, as then we will fallback to the C90 compliant code.

This patch should solve the reported issue number #4103.

Merge pull request #4094 from RubenKelevra/patchfrom_singlethread_man_update

clarify when to use '--single-thread' with '--patch-from'

Merge pull request #4106 from facebook/dependabot/github_actions/msys2/setup-msys2-2.24.0

Bump msys2/setup-msys2 from 2.23.0 to 2.24.0

Merge pull request #4087 from jclab-joseph/fix/genhtml-windows

gen_html: Fix build error with mingw

Merge pull request #4101 from uilianries/readme/conan

[docs] Add instruction how to install zstd using Conan

Merge pull request #4104 from facebook/dependabot/github_actions/ossf/scorecard-action-2.4.0

Bump ossf/scorecard-action from 2.3.1 to 2.4.0

Bump msys2/setup-msys2 from 2.23.0 to 2.24.0

Bumps [msys2/setup-msys2](https://github.com/msys2/setup-msys2) from 2.23.0 to 2.24.0.
- [Release notes](https://github.com/msys2/setup-msys2/releases)
- [Changelog](https://github.com/msys2/setup-msys2/blob/main/CHANGELOG.md)
- [Commits](https://github.com/msys2/setup-msys2/compare/d0e80f58dffbc64f6a3a1f43527d469b4fc7b6c8...5df0ca6cbf14efcd08f8d5bd5e049a3cc8e07fd2)

---
updated-dependencies:
- dependency-name: msys2/setup-msys2
  dependency-type: direct:production
  update-type: version-update:semver-minor
...

Signed-off-by: dependabot[bot] <support@github.com>

Bump ossf/scorecard-action from 2.3.1 to 2.4.0

Bumps [ossf/scorecard-action](https://github.com/ossf/scorecard-action) from 2.3.1 to 2.4.0.
- [Release notes](https://github.com/ossf/scorecard-action/releases)
- [Changelog](https://github.com/ossf/scorecard-action/blob/main/RELEASE.md)
- [Commits](https://github.com/ossf/scorecard-action/compare/0864cf19026789058feabb7e87baa5f140aac736...62b2cac7ed8198b15735ed49ab1e5cf35480ba46)

---
updated-dependencies:
- dependency-name: ossf/scorecard-action
  dependency-type: direct:production
  update-type: version-update:semver-minor
...

Signed-off-by: dependabot[bot] <support@github.com>

tests/decodecorpus: add more advanced options

- add option to force a specific block type
- add option to force a specific literal tyle
- add option to generate only frame headers
- add option to skip generating magic numbers

Co-authored-by: Maciej Dudek <mdudek@antmicro.com>
Co-authored-by: Pawel Czarnecki <pczarnecki@antmicro.com>
Co-authored-by: Robert Winkler <rwinkler@antmicro.com>
Co-authored-by: Roman Dobrodii <rdobrodii@antmicro.com>

Add Conan to readme

Signed-off-by: Uilian Ries <uilianries@gmail.com>

Merge pull request #4096 from tpetazzoni/build-fix

lib/libzstd.mk: fix typo in the definition of LIB_BINDIR

lib/libzstd.mk: fix typo in the definition of LIB_BINDIR

Commit f4dbfce79cb2b82fb496fcd2518ecd3315051b7d ("define LIB_SRCDIR
and LIB_BINDIR") significantly reworked the build logic, but in its
introduction of LIB_BINDIR a typo was made.

It was introduced as such:

+LIB_SRCDIR ?= $(dir $(realpath $(lastword $(MAKEFILE_LIST))))
+LIB_BINDIR ?= $(LIBSRC_DIR)

But the definition of LIB_BINDIR has a typo: it should use
$(LIB_SRCDIR) not $(LIBSRC_DIR).

Due to this, $(LIB_BINDIR) is empty, therefore in programs/Makefile,
-L$(LIB_BINDIR) is expanded to just -L, and consequently when trying
to link the "zstd" binary with the libzstd library, it cannot find it:

host/lib/gcc/powerpc64-buildroot-linux-gnu/13.3.0/../../../../powerpc64-buildroot-linux-gnu/bin/ld: cannot find -lzstd: No such file or directory

This commit fixes the build by fixing this typo.

Signed-off-by: Thomas Petazzoni <thomas.petazzoni@bootlin.com>

clarify when to use '--single-thread' with '--patch-from'

Using '--single-thread' with '--patch-from' on compression levels above 15 will lead to significantly worse compression ratios.

Corrected the man page not suggest anymore to do this.

Merge pull request #4086 from Adenilson/fix01

[zstd][dict] Ensure that dictionary training functions are fully reen…

gen_html: Fix build error in windows

[zstd][dict] Ensure that dictionary training functions are fully reentrant

The two main functions used for dictionary training using the COVER
algorithm require initialization of a COVER_ctx_t where a call
to qsort() is performed.

The issue is that the standard C99 qsort() function doesn't offer
a way to pass an extra parameter for the comparison function callback
(e.g. a pointer to a context) and currently zstd relies on a *global*
static variable to hold a pointer to a context needed to perform
the sort operation.

If a zstd library user invokes either ZDICT_trainFromBuffer_cover or
ZDICT_optimizeTrainFromBuffer_cover from multiple threads, the
global context may be overwritten before/during the call/execution to qsort()
in the initialization of the COVER_ctx_t, thus yielding to crashes
and other bad things (Tm) as reported on issue #4045.

Enters qsort_r(): it was designed to address precisely this situation,
to quote from the documention [1]: "the comparison function does not need to
use global variables to pass through arbitrary arguments, and is therefore
reentrant and safe to use in threads."

It is available with small variations for multiple OSes (GNU, BSD[2],
Windows[3]), and the ISO C11 [4] standard features on annex B-21 qsort_s() as
part of the <stdlib.h>. Let's hope that compilers eventually catch up
with it.

For now, we have to handle the small variations in function parameters
for each platform.

The current fix solves the problem by allowing each executing thread
pass its own COVER_ctx_t instance to qsort_r(), removing the use of
a global pointer and allowing the code to be reentrant.

Unfortunately for *BSD, we cannot leverage qsort_r() given that its API
has changed on newer versions of FreeBSD (14.0) and the other BSD variants
(e.g. NetBSD, OpenBSD) don't implement it.

For such cases we provide a fallback that will work only requiring support
for compilers implementing support for C90.

[1] https://man7.org/linux/man-pages/man3/qsort_r.3.html
[2] https://man.freebsd.org/cgi/man.cgi?query=qsort_r
[3] https://learn.microsoft.com/en-us/cpp/c-runtime-library/reference/qsort-s?view=msvc-170
[4] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1548.pdf

Merge pull request #4079 from elasota/truncated-huff-state-error

Throw error if Huffman weight initial states are truncated

Merge pull request #4068 from DimitriPapadopoulos/codespell

Fix new typos found by codespell

Throw error if Huffman weight initial states are truncated

Fix typos not found by codespell

Fix new typos found by codespell

Merge pull request #4076 from facebook/fix_macos_build

fix macos build

fix macos build

weird: after replacing the UNAME line with an identical one,
it does work properly now(??).
Possibly a case of hidden special character?

Expose size estimation helpers for Linux (#4064)

Merge pull request #4073 from facebook/cygwin_install

added a cygwin install test to check #4067

added cygwin install test

Merge pull request #4067 from QBos07/filterfix

Fix $filter operants and Msys/Cygwin

Merge pull request #4065 from embg/freebsd_ci

Drop support for FreeBSD 13.2 CI

Fix $filter and Msys/Cygwin

- switched the patter and input of $filter into the right places
- added pattern wildcard to MSYS_NT & CYGWIN_NT as they change with windows versions
- correctly identify MSYS2, even in an env like MINGW64

minor:doc: specify decompression behavior in presence of multiple concatenated frames

directly at ZSTD_decompress() level.

Unit test for external sequence producer + static CCtx + streaming (#4063)

Drop FreeBSD 13.2 CI

Merge pull request #4046 from josepho0918/iar

Improve support for IAR compiler with attributes and intrinsics

Merge pull request #4054 from jbajic/fix-missing-newline

[fix] Add newline when file exceeds 128KB

Refactor dictionary matchfinder index safety check (#4039)

[fix] Add newline when file exceeds 128KB