Speed up software CRC-32 computation by a factor of 1.5 to 3.
Use the interleaved method of Kadatch and Jenkins in order to make
use of pipelined instructions through multiple ALUs in a single
core. This also speeds up and simplifies the combination of CRCs,
and updates the functions to pre-calculate and use an operator for
CRC combination.

Co-authored-by: Nathan Moinvaziri <nathan@nathanm.com>

Adding avx512_vnni inline + copy elision

Interesting revelation while benchmarking all of this is that our
chunkmemset_avx seems to be slower in a lot of use cases than
chunkmemset_sse.  That will be an interesting function to attempt to
optimize.

Right now though, we're basically beating google for all PNG decode and
encode benchmarks.  There are some variations of flags that can
basically have us trading blows, but we're about as much as 14% faster
than chromium's zlib patches.

While we're here, add a more direct benchmark of the folded copy method
versus the explicit copy + checksum.

Added inlined AVX512 adler checksum + copy

While we're here, also simplfy the "fold" signature, as reducing the
number of rebases and horizontal sums did not prove to be meaningfully
faster (slower in many circumstances).

Add AVX2 inline copy + adler implementation

This was pretty much across the board wins for performance, but the wins
are very data dependent and it sort of depends on what copy runs look
like.  On our less than realistic data in benchmark_zlib_apps, the
decode test saw some of the bigger gains, ranging anywhere from 6 to 11%
when compiled with AVX2 on a Cascade Lake CPU (and with only AVX2
enabled).  The decode on realistic imagery enjoyed smaller gains,
somewhere between 2 and 4%.

Interestingly, there was one outlier on encode, at level 5.  The best
theory for this is that the copy runs for that particular compression
level were such that glibc's ERMS aware memmove implementation managed
to marginally outpace the copy during the checksum with the move rep str
sequence thanks to clever microcoding on Intel's part. It's hard to say
for sure but the most standout difference between the two perf profiles
was more time spent in memmove (which is expected, as it's calling
memcpy instead of copying the bytes during the checksum).

There's the distinct possibility that the AVX2 checksums could be
marginally improved by one level of unrolling (like what's done in the
SSE3 implementation).  The AVX512 implementations are certainly getting
gains from this but it's not appropriate to append this optimization in
this series of commits.

Adding an SSE42 optimized copy + adler checksum implementation

We are protecting its usage around a lot of preprocessor macros as the
other methods are not yet implemented and calling this version bypasses
the faster adler implementations implicitly.

When more versions are written for faster vectorizations, the functable
entries will be populated and preprocessor macros removed. This round,
the copy + checksum is not employing as many tricks as one would hope
with a "folded" checksum routine.  The reason for this is the
particularly tricky case of dealing with unaligned buffers.  The
implementations which don't have CPUs in the mix that have a huge
penalty for unaligned loads will have a much faster implementation.

Fancier methods that minimized rebasing, while having the potential to
be faster, ended up being slower because the compiler structured the
code in a way that ended up either spilling to the stack or trampolining
out of a loop and back in it instead of just jumping over the first load
and store.

Revisiting this for AVX512, where more registers are abundant and more
advanced loads exist, may be prudent.

Create adler32_fold_c* functions

These are very simple wrappers that do nothing clever but serve as a
shim interface for implementing versions which do cleverly track the
number of scalar sums performed so that we can minimize rebasing and
also have an efficient copy elision.

This serves as the baseline as each vectorization gets its own commit.
That way the PR will be bisectable.

Improved chunkset substantially where it's heavily used

For most realistic use cases, this doesn't make a ton of difference.
However, for things which are highly compressible and enjoy very large
run length encodes in the window, this is a huge win.

We leverage a permutation table to swizzle the contents of the memory
chunk into a vector register and then splat that over memory with a fast
copy loop.

In essence, where this helps, it helps a lot.  Where it doesn't, it does
no measurable damage to the runtime.

This commit also simplifies a chunkcopy_safe call for determining a
distance.  Using labs is enough to give the same behavior as before,
with the added benefit that no predication is required _and_, most
importantly, static analysis by GCC's string fortification can't throw a
fit because it conveys better to the compiler that the input into
builtin_memcpy will always be in range.

Make directory for output files.

Signed-off-by: Vladislav Shchapov <vladislav@shchapov.ru>

Fixed incorrect case for __clang__ preprocessor macro in zbuild.h.

Fixed issue #1264: Use fallback for _mm256_zextsi128_si256 on Xcode < 9.3

Remove extra CMake messages from ARM toolchains.

Implement power9 version of compare256.

Co-authored-by: Nathan Moinvaziri <nathan@nathanm.com>

The names CMAKE_INTERPROCEDURAL_OPTIMIZATION_* must be uppercase.

Signed-off-by: Vladislav Shchapov <vladislav@shchapov.ru>

Implement neon version of compare256.

Co-authored-by: Adam Stylinski <kungfujesus06@gmail.com>

Fixed warning about strict prototypes for cpu_check_features.

Remove unused chunkmemset_1 code.

Disable redirection to 64-bit function variants when Z_SOLO is defined

See #1262.

Improve deflateBound unit test to test a range of small buffer lengths with various deflateBound initialization values.

Co-authored-by: Mika T. Lindqvist <postmaster@raasu.org>

Added compressBound tests for small buffers.

Co-authored-by: Mika T. Lindqvist <postmaster@raasu.org>

Fixed MSVC warning about unknown option for AVX512 flag.

cl : command line warning D9002: ignoring unknown option '/ARCH:AVX512'

Add test for stream adler after inflateSetDictionary

This test passes prior to commit
8550a90de4dcb8589a7d48fe308c4c45bba5a466 ("Leverage inline CRC + copy")
and fails after that commit.

Fixed regression introduced by inlining CRC + copy

Pretty much every time updatewindow has been called, implicitly a
checksum was performed unless on s/390 or state->wrap & 4 == 0. The
inflateSetDictionary function instead separately calls this checksum
before invoking update window and checks the checksum to see if it
matches the initial checksum (a property that happens from parsing the
DICTID section of the headers).

Instead, we can make updatewindow have a "copy" parameter, which is the
state->wrap value that is being checked anyway.  We instead move the 3rd
bit check to be checked by the caller rather than the callee.

IBM Z DFLTCC: Split deflate and inflate states

Currently deflate and inflate both use a common state struct. There are
several variables in this struct that we don't need for inflate, and
more may be coming in the future. Therefore split them in two separate
structs. This in turn requires splitting ZALLOC_STATE and ZCOPY_STATE
macros.

macOs M1 build fix on arm cpu checks.

Remove trailing whitespace in several source code files

Fixed forcing CMAKE_BUILD_TYPE to Release on multi config generators such as Xcode or MSVC.

Co-authored-by: Sergey Markelov <sergio-nsk@users.noreply.github.com>

Remove CVE testing from configure script.

Use PREFIX() for some of the Z_INTERNAL symbols

https://github.com/powturbo/TurboBench links zlib and zlib-ng into the
same binary, causing non-static symbol conflicts. Fix by using PREFIX()
for flush_pending(), bi_reverse(), inflate_ensure_window() and all of
the IBM Z symbols.

Note: do not use an explicit zng_, since one of the long-term goals is
to be able to link two versions of zlib-ng into the same binary for
benchmarking [1].

[1] https://github.com/zlib-ng/zlib-ng/pull/1248#issuecomment-1096648932

Don't try to build tests or benchmarks if cmake is too old for them.

Check that sys/auxv.h exists at configure time and add preprocessor define for it.
* Protect including sys/auxv.h in all relevant files with the new preprocessor define
* Test for both existence of both sys/auxv.h and getauxval() with both cmake and configure

Fixed failed tools tests when source directory is read-only.

Add test for issue #1235.
* Test both compressBound() and deflateBound() as those share same code fragment.

Add one extra byte to return value of compressBound and deflateBound for small lengths due to shift returning 0.
* Treat 0 byte input as 1 byte input when calculating compressBound and deflateBound

Disable LTO in CMake

Use _msan_unposion to unposion end of window for when it needs to read the past < chunksize bytes in the window. See #1245.

Co-authored-by: Adam Stylinski <kungfujesus06@gmail.com>

Rename memory alignment functions because they handle custom allocator which is the first parameter so having calloc and cfree (c = custom) is confusing in the name.

Fixed off-by-one error when benchmarking compare256 resulting in heap-buffer-overflow.

Mimic minigzip behavior and only unlink files if not using -c copy out argument.

Fix the custom PNG image based benchmark

The height parameter was using a fixed macro, written at a time when the
test imagery was fully synthetic.  Because of this, images smaller than
than our in-memory generated imagery will artificially throw a CRC
error.

Remove sanitizer support from configure since it is better supported in cmake. Anybody who still needs it can use cmake or manually set CFLAGS and LDFLAGS.

abicheck.sh: don't export CHOST if it wasn't already exported.

This fixes https://github.com/zlib-ng/zlib-ng/issues/1219,
a regression when running abicheck.sh with default compiler.

Fixed missing crc32_combine exports for zlib 1.2.12.

abicheck.sh: zlib-ng is a bash script, not a sh script, don't hardcode shell when running configure

Fixed building tests when -DWITH_GZFILEOP=OFF

Move fuzzer cmake into fuzz directory.

Use latest stable version of google test instead of unstable main branch.

abicheck.sh: implement --refresh-if option as documented.

Also change exit status to nonzero if there is no abifile and --refresh or --refresh-if were not specified.

Grammar fixes

Remove support for building fuzzers from configure.

Test CVE-2018-25032 against the default level and levels 1 and 2.

Added unit test against CVE-2018-25032 with default strategy.

Co-authored-by: Eric Biggers <ebiggers@kernel.org>

Added unit test against CVE-2018-25032.
Sample input from https://www.openwall.com/lists/oss-security/2022/03/26/1.

Co-authored-by: Tavis Ormandy <taviso@users.noreply.github.com>

Added missing -F argument for Z_FIXED strategy in minideflate.

Use size_t types for len arithmetic, matching signature

This suppresses a warning and keeps everything safely the same type.
While it's unlikely that the input for any of this will exceed the size
of an unsigned 32 bit integer, this approach is cleaner than casting and
should not result in a performance degradation.

Use standalone fuzzing runner only when fuzzing engine is not found.

Allow SSE2 and AVX2 functions with -DWITH_UNALIGNED=OFF. Even though they use unaligned loads, they don't result in undefined behavior.

Leverage inline CRC + copy

This brings back a bit of the performance that may have been sacrificed
by reverting the reorganized inflate window. Doing a copy at the same
time as a CRC is basically free.

Fixed clang signed/unsigned warning in chunkcopy_safe.

inflate_p.h:159:18: warning: comparison of integers of different signs: 'int32_t' (aka 'int') and 'size_t' (aka 'unsigned long') [-Wsign-compare]
        tocopy = MIN(non_olap_size, len);
                 ^   ~~~~~~~~~~~~~  ~~~
zbuild.h:74:24: note: expanded from macro 'MIN'
#define MIN(a, b) ((a) > (b) ? (b) : (a))
                    ~  ^  ~

Use specific gcovr version 5.0 due to parser errors with 5.1.
https://github.com/gcovr/gcovr/issues/583

Remove unistd.h include from gzguts.h which is already included from zconf.h via zlib.h.

Use HAVE instead of HAS for variable name for consistency.

Remove detect_leaks=0 from non-ASAN cmake jobs.

Fixed error with compare256_unaligned_avx2 undefined if unaligned access is disabled.

Fixed signed comparison warning in zng_calloc_aligned.

zutil.c: In function ‘zng_calloc_aligned’:
zutil.c:133:20: warning: comparison of integer expressions of different signedness: ‘int32_t’ {aka ‘int’} and ‘long unsigned int’ [-Wsign-compare]

Fixed unused opaque variable in aligned alloc test.

test_aligned_alloc.cc: In function ‘void* zng_calloc_unaligned(void*, unsigned int, unsigned int)’:
test_aligned_alloc.cc:14:34: warning: unused parameter ‘opaque’ [-Wunused-parameter]
test_aligned_alloc.cc: In function ‘void zng_cfree_unaligned(void*, void*)’:
test_aligned_alloc.cc:28:32: warning: unused parameter ‘opaque’ [-Wunused-parameter]

Fixed operator precedence warnings in slide_hash_sse2.

slide_hash_sse2.c(58,5): warning C4554: '&': check operator precedence for possible error; use parentheses to clarify precedence
slide_hash_sse2.c(59,5): warning C4554: '&': check operator precedence for possible error; use parentheses to clarify precedence

Fixed signed/unsigned warning in chunkmemset.

chunkset_tpl.h(107,24): warning C4018: '>': signed/unsigned mismatch

Fixed MSVC warnings in chunkcopy_safe.

inflate_p.h(244,18): warning C4018: '>': signed/unsigned mismatch
inflate_p.h(234,38): warning C4244: 'initializing': conversion from '__int64' to 'int', possible loss of data
inffast.c
inflate_p.h(244,18): warning C4018: '>': signed/unsigned mismatch
inflate_p.h(234,38): warning C4244: 'initializing': conversion from '__int64' to 'int', possible loss of data
inflate.c
inflate_p.h(244,18): warning C4018: '>': signed/unsigned mismatch
inflate_p.h(234,38): warning C4244: 'initializing': conversion from '__int64' to 'int', possible loss of data

Correct typo in functable

Now, I could be wrong about this being an error, but I don't see any discussion suggesting this was intended, so...

Add unit tests for compare256 variants.

Fixed a warning about a comparison of an unsigned with a signed type

Fix an issue with the ubsan for overflow

While this didn't _actually_ cause any issues for us, technically the
_mm512_reduce_add_epi32() intrinsics returns a signed integer and it
does the very last summation in scalar GPRs as signed integers. While
the ALU still did the math properly (the negative representation is the
same addition in hardware, just interpreted differently), the sanitizer
caught window of inputs here definitely outside the range of a signed
integer for this immediate operation.

The solution, as silly as it may seem, would be to implement our own 32
bit horizontal sum function that does all of the work in vector
registers. This allows us to implicitly keep things in vector register
domain and convert at the very end after we've summed the summation.

The compiler's sanitizer doesn't know the wiser and the solution still
results in being correct.

Update language around ABI compatibility with zlib. #1081

Rename adler32_sse41 to adler32_ssse3

As it turns out, the sum of absolute differences instruction _did_ exist
in SSSE3 all along. SSE41 introduced a stranger, less commonly used
variation of the sum of absolute difference instruction.  Knowing this,
the old SSSE3 method can be axed entirely and the SSE41 method can now
be used on CPUs only having SSSE3.

Removing this extra functable entry shrinks the code and allows for a
simpler planned refactor later for the adler checksum and copy elision.

Fixed missing checks around compare256 and longest_match definitions.

Use zmemcmp_2 in 16-bit unaligned compare256 variant.

Revert "Reorganize inflate window layout"

This reverts commit dc3b60841dbfa9cf37be3efb4568f055b4e15580.

Revert "Add back original version of inflate_fast for use with inflateBack."

This reverts commit 2d2dde43b11c40cb58a339ff4a8425bca0091c31.

Revert "DFLTCC update for window optimization from Jim & Nathan"

This reverts commit b4ca25afabba7b4bf74d36e26728006d28df891d.

Added common sanitizer flags for getting optimal stack traces.

Use halt_on_error in sanitizer options.
https://lists.llvm.org/pipermail/cfe-dev/2015-October/045710.html

Make symbolic prefix instance names consistent in NMake GHA workflow.

Fixed misspelling in NO_UNALIGNED flag.

Wrong variable used when detecting unaligned support for sanitize

Added sanitizer tests in configure GitHub Actions workflow.
Added missing OPTIONS environment variable for UBSAN in CMake GitHub workflow.

Use zutil.h which already includes zlib headers.

Remove unused zutil header.

Fix a latent issue with chunkmemset

It would seem that on some platforms, namely those which are
!UNALIGNED64_OK, there was a likelihood of chunkmemset_safe_c copying all
the bytes before passing control flow to chunkcopy, a function which is
explicitly unsafe to be called with a zero length copy.

This fixes that bug for those platforms.

Fix UBSAN's cry afoul

Technically, we weren't actually doing this the way C wants us to,
legally.  The zmemcpy's turn into NOPs for pretty much all > 0
optimization levels and this gets us defined behavior with the
sanitizer, putting the optimized load by arbitrary alignment into the
compiler's hands instead of ours.

Added check for UNALIGNED64_OK when defining zmemcpy_8 and zmemcmp_8.

Added 32-bit GCC build to CMake GitHub Actions.

Make unaligned access being disabled configurable via build scripts.

Move UNALIGNED_OK detection to compile time instead of configure time.

Explicitly install dependencies for wine32.
* Allow downgrading packages to resolve conflicts

Don't use -mtune with ClangCl.

[README] Add missing FORCE_SSE2 for CMake.

Allow bypassing runtime feature check of TZCNT instructions.
* This avoids conditional branch when it's known at build time that TZCNT instructions are always supported

Throw an error when input is raw deflate stream but window_bits is not supplied.

Print help when no arguments supplied to minideflate.

Append extension to output file path based on window_bits when compressing and remove extension from output file path when decompressing.