deflate_compress: optimize gen_codewords()

This can be slightly faster.

.cirrus.yml

@@ -1,8 +1,8 @@
 task:
   freebsd_instance:
     matrix:
-      - image_family: freebsd-11-3-snap
-      - image_family: freebsd-12-1-snap
+      - image_family: freebsd-12-3
+      - image_family: freebsd-13-0
   install_script: pkg install -y gmake
   script:
     - gmake check

.github/workflows/android.yml

@@ -0,0 +1,104 @@
+name: cross compile with android-ndk
+
+on:
+  push:
+    branches: [ master ]
+  pull_request:
+    branches: [ master ]
+
+jobs:
+  cross-compile-for-android:
+    strategy:
+      fail-fast: false
+      matrix:
+        os: [ubuntu-18.04, ubuntu-20.04, macos-10.15, macos-11]
+        target-abi: [armeabi-v7a, arm64-v8a, x86, x86_64]
+
+    runs-on: ${{ matrix.os }}
+
+    steps:
+      - run:  brew install tree file
+
+      - run:  tree --version
+      - run:  file --version
+      - run:  make --version
+
+      - uses: actions/checkout@v2
+
+      - name: build for ${{ matrix.target-abi }}
+        run: |
+          COLOR_GREEN='\033[0;32m'        # Green
+          COLOR_PURPLE='\033[0;35m'       # Purple
+          COLOR_OFF='\033[0m'             # Reset
+
+          run() {
+            printf '%b\n' "$COLOR_PURPLE==>$COLOR_OFF $COLOR_GREEN$*$COLOR_OFF"
+            eval "$*"
+          }
+
+          BUILD_MACHINE_OS_TYPE=$(uname | tr A-Z a-z)
+          BUILD_MACHINE_OS_ARCH=$(uname -m)
+
+          export ANDROID_NDK_HOME="$ANDROID_NDK_LATEST_HOME"
+
+          env | sed -n '/^ANDROID_/p'
+
+          ANDROID_NDK_VERS=$(grep "Pkg.Revision" "$ANDROID_NDK_HOME/source.properties" | cut -d " " -f3)
+          ANDROID_NDK_BASE=$ANDROID_NDK_HOME/toolchains/llvm/prebuilt/$BUILD_MACHINE_OS_TYPE-$BUILD_MACHINE_OS_ARCH
+          ANDROID_NDK_BIND=$ANDROID_NDK_BASE/bin
+          SYSROOT=$ANDROID_NDK_BASE/sysroot
+
+          printf '%s = %s\n' ANDROID_NDK_HOME "$ANDROID_NDK_HOME"
+          printf '%s = %s\n' ANDROID_NDK_BIND "$ANDROID_NDK_BIND"
+          printf '%s = %s\n' ANDROID_NDK_VERS "$ANDROID_NDK_VERS"
+          printf '%s\n'
+
+          export CPPFLAGS="--sysroot $SYSROOT"
+          export   CFLAGS="--sysroot $SYSROOT -fpic"
+          export  LDFLAGS="--sysroot $SYSROOT"
+
+          case ${{ matrix.target-abi }} in
+            armeabi-v7a) CC=armv7a-linux-androideabi21-clang ;;
+            arm64-v8a)   CC=aarch64-linux-android21-clang    ;;
+            x86)         CC=i686-linux-android21-clang       ;;
+            x86_64)      CC=x86_64-linux-android21-clang     ;;
+          esac
+
+          AR=llvm-ar
+
+          export PATH="$ANDROID_NDK_BIND:$PATH"
+
+          printf '%b\n' "$COLOR_PURPLE==>$COLOR_OFF ${COLOR_GREEN}show PATH$COLOR_OFF"
+          printf '%s\n' "$PATH" | tr ':' '\n'
+          printf '%s\n'
+
+          run make clean install PREFIX=$PWD/install.d CC="$CC" CPPFLAGS="'$CPPFLAGS'" CFLAGS="'$CFLAGS'" AR="$AR" V=1
+
+      - run:  tree install.d
+
+      - run:  |
+          file install.d/lib/libdeflate.so
+          case ${{ matrix.target-abi }} in
+            armeabi-v7a) file install.d/lib/libdeflate.so     | grep 'ELF 32-bit LSB shared object, ARM, EABI5'   ;;
+            arm64-v8a)   file install.d/lib/libdeflate.so     | grep 'ELF 64-bit LSB shared object, ARM aarch64,' ;;
+            x86)         file install.d/lib/libdeflate.so     | grep 'ELF 32-bit LSB shared object, Intel 80386,' ;;
+            x86_64)      file install.d/lib/libdeflate.so     | grep 'ELF 64-bit LSB shared object, x86-64,'      ;;
+          esac
+
+      - run:  |
+          file install.d/bin/libdeflate-gzip
+          case ${{ matrix.target-abi }} in
+            armeabi-v7a) file install.d/bin/libdeflate-gzip   | grep 'ELF 32-bit LSB pie executable, ARM, EABI5'   ;;
+            arm64-v8a)   file install.d/bin/libdeflate-gzip   | grep 'ELF 64-bit LSB pie executable, ARM aarch64,' ;;
+            x86)         file install.d/bin/libdeflate-gzip   | grep 'ELF 32-bit LSB pie executable, Intel 80386,' ;;
+            x86_64)      file install.d/bin/libdeflate-gzip   | grep 'ELF 64-bit LSB pie executable, x86-64,'      ;;
+          esac
+
+      - run:  |
+          file install.d/bin/libdeflate-gunzip
+          case ${{ matrix.target-abi }} in
+            armeabi-v7a) file install.d/bin/libdeflate-gunzip | grep 'ELF 32-bit LSB pie executable, ARM, EABI5'   ;;
+            arm64-v8a)   file install.d/bin/libdeflate-gunzip | grep 'ELF 64-bit LSB pie executable, ARM aarch64,' ;;
+            x86)         file install.d/bin/libdeflate-gunzip | grep 'ELF 32-bit LSB pie executable, Intel 80386,' ;;
+            x86_64)      file install.d/bin/libdeflate-gunzip | grep 'ELF 64-bit LSB pie executable, x86-64,'      ;;
+          esac

Makefile

@@ -89,37 +89,59 @@ PROG_SUFFIX        :=
 PROG_CFLAGS        :=
 HARD_LINKS         := 1
 
-# Compiling for Windows with MinGW?
-ifneq ($(findstring -mingw,$(shell $(CC) -dumpmachine 2>/dev/null)),)
+TARGET_MACHINE     := $(shell $(CC) -dumpmachine 2>/dev/null)
+
+# Compiling for Windows with MinGW or LLVM?
+ifneq ($(findstring -mingw,$(TARGET_MACHINE))$(findstring -windows-gnu,$(TARGET_MACHINE)),)
     STATIC_LIB_SUFFIX  := static.lib
     SHARED_LIB         := libdeflate.dll
     SHARED_LIB_SYMLINK :=
     SHARED_LIB_CFLAGS  :=
     SHARED_LIB_LDFLAGS := -Wl,--out-implib,libdeflate.lib \
-                          -Wl,--output-def,libdeflate.def \
-                          -Wl,--add-stdcall-alias
+                          -Wl,--output-def,libdeflate.def
+    # Only if not LLVM
+    ifeq ($(findstring -windows-gnu,$(TARGET_MACHINE)),)
+        SHARED_LIB_LDFLAGS += -Wl,--add-stdcall-alias
+    endif
+
     PROG_SUFFIX        := .exe
     PROG_CFLAGS        := -static -municode
     HARD_LINKS         :=
     override CFLAGS    := $(CFLAGS) $(call cc-option,-Wno-pedantic-ms-format)
 
     # If AR was not already overridden, then derive it from $(CC).
-    # Note that CC may take different forms, e.g. "cc", "gcc",
-    # "x86_64-w64-mingw32-gcc", or "x86_64-w64-mingw32-gcc-6.3.1".
+    # Note that CC may take different forms, e.g. "cc", "gcc", "clang",
+    # "x86_64-w64-mingw32-gcc", or "x86_64-w64-mingw32-gcc-6.3.1", or
+    # "x86_64-w64-mingw32-clang".
     # On Windows it may also have a .exe extension.
     ifeq ($(AR),ar)
         AR := $(shell echo $(CC) | \
-                sed -E 's/g?cc(-?[0-9]+(\.[0-9]+)*)?(\.exe)?$$/ar\3/')
+                sed -E 's/(g?cc|clang)(-?[0-9]+(\.[0-9]+)*)?(\.exe)?$$/ar\4/')
     endif
 
-# macOS?
-else ifeq ($(shell uname),Darwin)
+# Compiling for macOS?
+else ifneq ($(findstring -darwin,$(TARGET_MACHINE)),)
    SHARED_LIB         := libdeflate.$(SOVERSION).dylib
    SHARED_LIB_SYMLINK := libdeflate.dylib
    SHARED_LIB_CFLAGS  := -fPIC
-   SHARED_LIB_LDFLAGS := -install_name $(SHARED_LIB)
+   SHARED_LIB_LDFLAGS := -install_name $(LIBDIR)/$(SHARED_LIB)
 
-# Linux, FreeBSD, etc.
+# Compiling for Android?
+else ifneq ($(findstring -android,$(TARGET_MACHINE)),)
+   SHARED_LIB         := libdeflate.so
+   SHARED_LIB_SYMLINK :=
+   SHARED_LIB_CFLAGS  := -fPIC
+   SHARED_LIB_LDFLAGS := -Wl,-soname=$(SHARED_LIB)
+
+# Compiling for Haiku?
+else ifneq ($(findstring -haiku,$(TARGET_MACHINE)),)
+   SHARED_LIB         := libdeflate.so.$(SOVERSION)
+   SHARED_LIB_SYMLINK := libdeflate.so
+   SHARED_LIB_CFLAGS  := -fPIC
+   SHARED_LIB_LDFLAGS := -Wl,-soname=$(SHARED_LIB)
+   HARD_LINKS         :=
+
+# Compiling for Linux, FreeBSD, etc.
 else
    SHARED_LIB         := libdeflate.so.$(SOVERSION)
    SHARED_LIB_SYMLINK := libdeflate.so
@@ -333,8 +355,13 @@ install:all $(PKGCONFBASE)
 	install -m644 libdeflate.h $(DESTDIR)$(INCDIR)
 	install -m755 gzip$(PROG_SUFFIX) \
 		$(DESTDIR)$(BINDIR)/libdeflate-gzip$(PROG_SUFFIX)
-	ln -f $(DESTDIR)$(BINDIR)/libdeflate-gzip$(PROG_SUFFIX)		\
-	      $(DESTDIR)$(BINDIR)/libdeflate-gunzip$(PROG_SUFFIX)
+	if [ -n "$(HARD_LINKS)" ]; then					\
+		ln -f $(DESTDIR)$(BINDIR)/libdeflate-gzip$(PROG_SUFFIX)	\
+		      $(DESTDIR)$(BINDIR)/libdeflate-gunzip$(PROG_SUFFIX); \
+	else								\
+		ln -sf libdeflate-gzip$(PROG_SUFFIX)			\
+		       $(DESTDIR)$(BINDIR)/libdeflate-gunzip$(PROG_SUFFIX); \
+	fi
 	if [ -n "$(SHARED_LIB_SYMLINK)" ]; then				\
 		ln -sf $(SHARED_LIB)					\
 		       $(DESTDIR)$(LIBDIR)/$(SHARED_LIB_SYMLINK);	\

NEWS.md

@@ -1,5 +1,54 @@
 # libdeflate release notes
 
+## Version 1.10
+
+* Added an additional check to the decompressor to make it quickly detect
+  certain bad inputs and not try to generate an unbounded amount of output.
+
+  Note: this was only a problem when decompressing with an unknown output size,
+  which isn't the recommended use case of libdeflate.  However,
+  `libdeflate-gunzip` has to do this, and it would run out of memory as it would
+  keep trying to allocate a larger output buffer.
+
+* Fixed a build error on Solaris.
+
+* Cleaned up a few things in the compression code.
+
+## Version 1.9
+
+* Made many improvements to the compression algorithms, and rebalanced the
+  compression levels:
+
+  * Heuristics were implemented which significantly improve the compression
+    ratio on data where short matches aren't useful, such as DNA sequencing
+    data.  This applies to all compression levels, but primarily to levels 1-9.
+
+  * Level 1 was made much faster, though it often compresses slightly worse than
+    before (but still better than zlib).
+
+  * Levels 8-9 were also made faster, though they often compress slightly worse
+    than before (but still better than zlib).  On some data, levels 8-9 are much
+    faster and compress much better than before; this change addressed an issue
+    where levels 8-9 did poorly on certain files.  The algorithm used by levels
+    8-9 is now more similar to that of levels 6-7 than to that of levels 10-12.
+
+  * Levels 2-3, 7, and 10-12 were strengthened slightly.
+
+  * Levels 4-6 were also strengthened slightly, but some of this improvement was
+    traded off to speed them up slightly as well.
+
+  * Levels 1-9 had their per-compressor memory usage greatly reduced.
+
+  As always, compression ratios will vary depending on the input data, and
+  compression speeds will vary depending on the input data and target platform.
+
+* `make install` will now install a pkg-config file for libdeflate.
+
+* The Makefile now supports the `DISABLE_SHARED` parameter to disable building
+  the shared library.
+
+* Improved the Android build support in the Makefile.
+
 ## Version 1.8
 
 * Added `-t` (test) option to `libdeflate-gunzip`.

common/compiler_gcc.h

@@ -122,15 +122,30 @@
 #    endif
 
      /*
-      * Determine whether CRC32 intrinsics are supported.
+      * Determine whether ARM CRC32 intrinsics are supported.
       *
-      * With gcc r274827 or later (gcc 10.1+, 9.3+, or 8.4+), or with clang,
-      * they work as expected.  (Well, not quite.  There's still a bug, but we
-      * have to work around it later when including arm_acle.h.)
+      * This support has been affected by several gcc bugs, which we must avoid
+      * by only allowing gcc versions that have the corresponding fixes.  First,
+      * gcc commit 943766d37ae4 ("[arm] Fix use of CRC32 intrinsics with Armv8-a
+      * and hard-float"), i.e. gcc 8.4+, 9.3+, 10.1+, or 11+, is needed.
+      * Second, gcc commit c1cdabe3aab8 ("arm: reorder assembler architecture
+      * directives [PR101723]"), i.e. gcc 9.5+, 10.4+, 11.3+, or 12+, is needed
+      * when binutils is 2.34 or later, due to
+      * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104439.  We use the second
+      * set of prerequisites, as they are stricter and we have no way to detect
+      * the binutils version in C source without requiring a configure script.
+      *
+      * Yet another gcc bug makes arm_acle.h sometimes not define the crc
+      * functions even when the corresponding builtins are available.  However,
+      * we work around this later when including arm_acle.h.
+      *
+      * Things are a bit easier with clang -- we can just check whether the
+      * crc builtins are available.  However, clang's arm_acle.h is broken in
+      * the same way as gcc's, which we work around later in the same way.
       */
-#    if GCC_PREREQ(10, 1) || \
-        (GCC_PREREQ(9, 3) && !GCC_PREREQ(10, 0)) || \
-        (GCC_PREREQ(8, 4) && !GCC_PREREQ(9, 0)) || \
+#    if GCC_PREREQ(11, 3) || \
+        (GCC_PREREQ(10, 4) && !GCC_PREREQ(11, 0)) || \
+        (GCC_PREREQ(9, 5) && !GCC_PREREQ(10, 0)) || \
         (defined(__clang__) && __has_builtin(__builtin_arm_crc32b))
 #      define COMPILER_SUPPORTS_CRC32_TARGET_INTRINSICS 1
 #    endif
@@ -199,3 +214,22 @@ typedef char  __v64qi __attribute__((__vector_size__(64)));
 #define bsr64(n)	(63 - __builtin_clzll(n))
 #define bsf32(n)	__builtin_ctz(n)
 #define bsf64(n)	__builtin_ctzll(n)
+
+#if defined(__arm__) && \
+	(__ARM_ARCH >= 7 || (__ARM_ARCH == 6 && defined(__ARM_ARCH_6T2__)))
+static forceinline unsigned int
+rbit32(unsigned int v)
+{
+	__asm__("rbit %0, %1\n" : "=r" (v) : "r" (v));
+	return v;
+}
+#define rbit32 rbit32
+#elif defined(__aarch64__)
+static forceinline unsigned int
+rbit32(unsigned int v)
+{
+	__asm__("rbit %w0, %w1\n" : "=r" (v) : "r" (v));
+	return v;
+}
+#define rbit32 rbit32
+#endif /* __aarch64__ */

lib/arm/cpu_features.c

@@ -26,13 +26,8 @@
  */
 
 /*
- * ARM processors don't have a standard way for unprivileged programs to detect
- * processor features.  But, on Linux we can read the AT_HWCAP and AT_HWCAP2
- * values from /proc/self/auxv.
- *
- * Ideally we'd use the C library function getauxval(), but it's not guaranteed
- * to be available: it was only added to glibc in 2.16, and in Android it was
- * added to API level 18 for ARM and level 21 for AArch64.
+ * ARM CPUs don't have a standard way for unprivileged programs to detect CPU
+ * features.  But an OS-specific way can be used when available.
  */
 
 #include "../cpu_features_common.h" /* must be included first */
@@ -40,6 +35,16 @@
 
 #if ARM_CPU_FEATURES_ENABLED
 
+#ifdef __linux__
+/*
+ * On Linux, arm32 and arm64 CPU features can be detected by reading the
+ * AT_HWCAP and AT_HWCAP2 values from /proc/self/auxv.
+ *
+ * Ideally we'd use the C library function getauxval(), but it's not guaranteed
+ * to be available: it was only added to glibc in 2.16, and in Android it was
+ * added to API level 18 for arm32 and level 21 for arm64.
+ */
+
 #include <errno.h>
 #include <fcntl.h>
 #include <string.h>
@@ -48,8 +53,6 @@
 #define AT_HWCAP	16
 #define AT_HWCAP2	26
 
-volatile u32 _cpu_features = 0;
-
 static void scan_auxv(unsigned long *hwcap, unsigned long *hwcap2)
 {
 	int fd;
@@ -92,13 +95,7 @@ out:
 	close(fd);
 }
 
-static const struct cpu_feature arm_cpu_feature_table[] = {
-	{ARM_CPU_FEATURE_NEON,		"neon"},
-	{ARM_CPU_FEATURE_PMULL,		"pmull"},
-	{ARM_CPU_FEATURE_CRC32,		"crc32"},
-};
-
-void setup_cpu_features(void)
+static u32 get_arm_cpu_features(void)
 {
 	u32 features = 0;
 	unsigned long hwcap = 0;
@@ -123,6 +120,56 @@ void setup_cpu_features(void)
 	if (hwcap & (1 << 7))	/* HWCAP_CRC32 */
 		features |= ARM_CPU_FEATURE_CRC32;
 #endif
+	return features;
+}
+
+#elif defined(__APPLE__)
+/* On Apple platforms, arm64 CPU features can be detected via sysctlbyname(). */
+
+#include <sys/types.h>
+#include <sys/sysctl.h>
+
+static const struct {
+	const char *name;
+	u32 feature;
+} feature_sysctls[] = {
+	{ "hw.optional.neon",		ARM_CPU_FEATURE_NEON },
+	{ "hw.optional.AdvSIMD",	ARM_CPU_FEATURE_NEON },
+	{ "hw.optional.arm.FEAT_PMULL",	ARM_CPU_FEATURE_PMULL },
+	{ "hw.optional.armv8_crc32",	ARM_CPU_FEATURE_CRC32 },
+};
+
+static u32 get_arm_cpu_features(void)
+{
+	u32 features = 0;
+	size_t i;
+
+	for (i = 0; i < ARRAY_LEN(feature_sysctls); i++) {
+		const char *name = feature_sysctls[i].name;
+		u32 val = 0;
+		size_t valsize = sizeof(val);
+
+		if (sysctlbyname(name, &val, &valsize, NULL, 0) == 0 &&
+		    valsize == sizeof(val) && val == 1)
+			features |= feature_sysctls[i].feature;
+	}
+	return features;
+}
+#else
+#error "unhandled case"
+#endif
+
+static const struct cpu_feature arm_cpu_feature_table[] = {
+	{ARM_CPU_FEATURE_NEON,		"neon"},
+	{ARM_CPU_FEATURE_PMULL,		"pmull"},
+	{ARM_CPU_FEATURE_CRC32,		"crc32"},
+};
+
+volatile u32 _cpu_features = 0;
+
+void setup_cpu_features(void)
+{
+	u32 features = get_arm_cpu_features();
 
 	disable_cpu_features_for_testing(&features, arm_cpu_feature_table,
 					 ARRAY_LEN(arm_cpu_feature_table));

lib/arm/cpu_features.h

@@ -8,7 +8,8 @@
 #include "../lib_common.h"
 
 #if (defined(__arm__) || defined(__aarch64__)) && \
-	defined(__linux__) && \
+	(defined(__linux__) || \
+	 (defined(__aarch64__) && defined(__APPLE__))) && \
 	COMPILER_SUPPORTS_TARGET_FUNCTION_ATTRIBUTE && \
 	!defined(FREESTANDING)
 #  define ARM_CPU_FEATURES_ENABLED 1

lib/arm/crc32_impl.h

@@ -80,13 +80,17 @@ crc32_arm(u32 remainder, const u8 *p, size_t size)
 		size--;
 	}
 
-	while (size >= 32) {
+	while (size >= 64) {
 		remainder = __crc32d(remainder, le64_bswap(*((u64 *)p + 0)));
 		remainder = __crc32d(remainder, le64_bswap(*((u64 *)p + 1)));
 		remainder = __crc32d(remainder, le64_bswap(*((u64 *)p + 2)));
 		remainder = __crc32d(remainder, le64_bswap(*((u64 *)p + 3)));
-		p += 32;
-		size -= 32;
+		remainder = __crc32d(remainder, le64_bswap(*((u64 *)p + 4)));
+		remainder = __crc32d(remainder, le64_bswap(*((u64 *)p + 5)));
+		remainder = __crc32d(remainder, le64_bswap(*((u64 *)p + 6)));
+		remainder = __crc32d(remainder, le64_bswap(*((u64 *)p + 7)));
+		p += 64;
+		size -= 64;
 	}
 
 	while (size >= 8) {

lib/bt_matchfinder.h

@@ -1,8 +1,6 @@
 /*
  * bt_matchfinder.h - Lempel-Ziv matchfinding with a hash table of binary trees
  *
- * Originally public domain; changes after 2016-09-07 are copyrighted.
- *
  * Copyright 2016 Eric Biggers
  *
  * Permission is hereby granted, free of charge, to any person
@@ -101,11 +99,7 @@ struct bt_matchfinder {
 	 * 'child_tab[pos * 2]' and 'child_tab[pos * 2 + 1]', respectively.  */
 	mf_pos_t child_tab[2UL * MATCHFINDER_WINDOW_SIZE];
 
-}
-#ifdef _aligned_attribute
-_aligned_attribute(MATCHFINDER_MEM_ALIGNMENT)
-#endif
-;
+} MATCHFINDER_ALIGNED;
 
 /* Prepare the matchfinder for a new input buffer.  */
 static forceinline void
@@ -138,7 +132,7 @@ bt_right_child(struct bt_matchfinder *mf, s32 node)
 }
 
 /* The minimum permissible value of 'max_len' for bt_matchfinder_get_matches()
- * and bt_matchfinder_skip_position().  There must be sufficiently many bytes
+ * and bt_matchfinder_skip_byte().  There must be sufficiently many bytes
  * remaining to load a 32-bit integer from the *next* position.  */
 #define BT_MATCHFINDER_REQUIRED_NBYTES	5
 
@@ -152,7 +146,6 @@ bt_matchfinder_advance_one_byte(struct bt_matchfinder * const restrict mf,
 				const u32 nice_len,
 				const u32 max_search_depth,
 				u32 * const restrict next_hashes,
-				u32 * const restrict best_len_ret,
 				struct lz_match * restrict lz_matchptr,
 				const bool record_matches)
 {
@@ -218,7 +211,6 @@ bt_matchfinder_advance_one_byte(struct bt_matchfinder * const restrict mf,
 	if (cur_node <= cutoff) {
 		*pending_lt_ptr = MATCHFINDER_INITVAL;
 		*pending_gt_ptr = MATCHFINDER_INITVAL;
-		*best_len_ret = best_len;
 		return lz_matchptr;
 	}
 
@@ -241,7 +233,6 @@ bt_matchfinder_advance_one_byte(struct bt_matchfinder * const restrict mf,
 				if (len >= nice_len) {
 					*pending_lt_ptr = *bt_left_child(mf, cur_node);
 					*pending_gt_ptr = *bt_right_child(mf, cur_node);
-					*best_len_ret = best_len;
 					return lz_matchptr;
 				}
 			}
@@ -266,7 +257,6 @@ bt_matchfinder_advance_one_byte(struct bt_matchfinder * const restrict mf,
 		if (cur_node <= cutoff || !--depth_remaining) {
 			*pending_lt_ptr = MATCHFINDER_INITVAL;
 			*pending_gt_ptr = MATCHFINDER_INITVAL;
-			*best_len_ret = best_len;
 			return lz_matchptr;
 		}
 	}
@@ -295,12 +285,6 @@ bt_matchfinder_advance_one_byte(struct bt_matchfinder * const restrict mf,
  *	The precomputed hash codes for the sequence beginning at @in_next.
  *	These will be used and then updated with the precomputed hashcodes for
  *	the sequence beginning at @in_next + 1.
- * @best_len_ret
- *	If a match of length >= 4 was found, then the length of the longest such
- *	match is written here; otherwise 3 is written here.  (Note: this is
- *	redundant with the 'struct lz_match' array, but this is easier for the
- *	compiler to optimize when inlined and the caller immediately does a
- *	check against 'best_len'.)
  * @lz_matchptr
  *	An array in which this function will record the matches.  The recorded
  *	matches will be sorted by strictly increasing length and (non-strictly)
@@ -318,7 +302,6 @@ bt_matchfinder_get_matches(struct bt_matchfinder *mf,
 			   u32 nice_len,
 			   u32 max_search_depth,
 			   u32 next_hashes[2],
-			   u32 *best_len_ret,
 			   struct lz_match *lz_matchptr)
 {
 	return bt_matchfinder_advance_one_byte(mf,
@@ -328,7 +311,6 @@ bt_matchfinder_get_matches(struct bt_matchfinder *mf,
 					       nice_len,
 					       max_search_depth,
 					       next_hashes,
-					       best_len_ret,
 					       lz_matchptr,
 					       true);
 }
@@ -340,14 +322,13 @@ bt_matchfinder_get_matches(struct bt_matchfinder *mf,
  * must do hashing and tree re-rooting.
  */
 static forceinline void
-bt_matchfinder_skip_position(struct bt_matchfinder *mf,
-			     const u8 *in_base,
-			     ptrdiff_t cur_pos,
-			     u32 nice_len,
-			     u32 max_search_depth,
-			     u32 next_hashes[2])
+bt_matchfinder_skip_byte(struct bt_matchfinder *mf,
+			 const u8 *in_base,
+			 ptrdiff_t cur_pos,
+			 u32 nice_len,
+			 u32 max_search_depth,
+			 u32 next_hashes[2])
 {
-	u32 best_len;
 	bt_matchfinder_advance_one_byte(mf,
 					in_base,
 					cur_pos,
@@ -355,7 +336,6 @@ bt_matchfinder_skip_position(struct bt_matchfinder *mf,
 					nice_len,
 					max_search_depth,
 					next_hashes,
-					&best_len,
 					NULL,
 					false);
 }

lib/decompress_template.h

@@ -43,7 +43,7 @@ FUNCNAME(struct libdeflate_decompressor * restrict d,
 	const u8 * const in_end = in_next + in_nbytes;
 	bitbuf_t bitbuf = 0;
 	unsigned bitsleft = 0;
-	size_t overrun_count = 0;
+	size_t overread_count = 0;
 	unsigned i;
 	unsigned is_final_block;
 	unsigned block_type;

lib/deflate_compress.h

@@ -3,8 +3,10 @@
 
 #include "lib_common.h"
 
-/* DEFLATE compression is private to deflate_compress.c, but we do need to be
- * able to query the compression level for zlib and gzip header generation.  */
+/*
+ * DEFLATE compression is private to deflate_compress.c, but we do need to be
+ * able to query the compression level for zlib and gzip header generation.
+ */
 
 struct libdeflate_compressor;
 

lib/deflate_constants.h

@@ -14,11 +14,11 @@
 #define DEFLATE_MIN_MATCH_LEN			3
 #define DEFLATE_MAX_MATCH_LEN			258
 
-/* Minimum and maximum supported match offsets (in bytes)  */
-#define DEFLATE_MIN_MATCH_OFFSET		1
+/* Maximum supported match offset (in bytes) */
 #define DEFLATE_MAX_MATCH_OFFSET		32768
 
-#define DEFLATE_MAX_WINDOW_SIZE			32768
+/* log2 of DEFLATE_MAX_MATCH_OFFSET */
+#define DEFLATE_WINDOW_ORDER			15
 
 /* Number of symbols in each Huffman code.  Note: for the literal/length
  * and offset codes, these are actually the maximum values; a given block
@@ -33,7 +33,7 @@
 /* Division of symbols in the literal/length code  */
 #define DEFLATE_NUM_LITERALS			256
 #define DEFLATE_END_OF_BLOCK			256
-#define DEFLATE_NUM_LEN_SYMS			31
+#define DEFLATE_FIRST_LEN_SYM			257
 
 /* Maximum codeword length, in bits, within each Huffman code  */
 #define DEFLATE_MAX_PRE_CODEWORD_LEN		7
@@ -56,11 +56,4 @@
 #define DEFLATE_MAX_EXTRA_LENGTH_BITS		5
 #define DEFLATE_MAX_EXTRA_OFFSET_BITS		14
 
-/* The maximum number of bits in which a match can be represented.  This
- * is the absolute worst case, which assumes the longest possible Huffman
- * codewords and the maximum numbers of extra bits.  */
-#define DEFLATE_MAX_MATCH_BITS	\
-	(DEFLATE_MAX_LITLEN_CODEWORD_LEN + DEFLATE_MAX_EXTRA_LENGTH_BITS + \
-	DEFLATE_MAX_OFFSET_CODEWORD_LEN + DEFLATE_MAX_EXTRA_OFFSET_BITS)
-
 #endif /* LIB_DEFLATE_CONSTANTS_H */

lib/deflate_decompress.c

@@ -98,11 +98,6 @@
 #define LITLEN_ENOUGH		1334	/* enough 288 10 15	*/
 #define OFFSET_ENOUGH		402	/* enough 32 8 15	*/
 
-/*
- * Type for codeword lengths.
- */
-typedef u8 len_t;
-
 /*
  * The main DEFLATE decompressor structure.  Since this implementation only
  * supports full buffer decompression, this structure does not store the entire
@@ -121,12 +116,12 @@ struct libdeflate_decompressor {
 	 */
 
 	union {
-		len_t precode_lens[DEFLATE_NUM_PRECODE_SYMS];
+		u8 precode_lens[DEFLATE_NUM_PRECODE_SYMS];
 
 		struct {
-			len_t lens[DEFLATE_NUM_LITLEN_SYMS +
-				   DEFLATE_NUM_OFFSET_SYMS +
-				   DEFLATE_MAX_LENS_OVERRUN];
+			u8 lens[DEFLATE_NUM_LITLEN_SYMS +
+				DEFLATE_NUM_OFFSET_SYMS +
+				DEFLATE_MAX_LENS_OVERRUN];
 
 			u32 precode_decode_table[PRECODE_ENOUGH];
 		} l;
@@ -204,25 +199,27 @@ typedef machine_word_t bitbuf_t;
  *
  * If we would overread the input buffer, we just don't read anything, leaving
  * the bits zeroed but marking them filled.  This simplifies the decompressor
- * because it removes the need to distinguish between real overreads and
- * overreads that occur only because of the decompressor's own lookahead.
+ * because it removes the need to always be able to distinguish between real
+ * overreads and overreads caused only by the decompressor's own lookahead.
  *
- * The disadvantage is that real overreads are not detected immediately.
- * However, this is safe because the decompressor is still guaranteed to make
- * forward progress when presented never-ending 0 bits.  In an existing block
- * output will be getting generated, whereas new blocks can only be uncompressed
- * (since the type code for uncompressed blocks is 0), for which we check for
- * previous overread.  But even if we didn't check, uncompressed blocks would
- * fail to validate because LEN would not equal ~NLEN.  So the decompressor will
- * eventually either detect that the output buffer is full, or detect invalid
- * input, or finish the final block.
+ * We do still keep track of the number of bytes that have been overread, for
+ * two reasons.  First, it allows us to determine the exact number of bytes that
+ * were consumed once the stream ends or an uncompressed block is reached.
+ * Second, it allows us to stop early if the overread amount gets so large (more
+ * than sizeof bitbuf) that it can only be caused by a real overread.  (The
+ * second part is arguably unneeded, since libdeflate is buffer-based; given
+ * infinite zeroes, it will eventually either completely fill the output buffer
+ * or return an error.  However, we do it to be slightly more friendly to the
+ * not-recommended use case of decompressing with an unknown output size.)
  */
 #define FILL_BITS_BYTEWISE()					\
 do {								\
-	if (likely(in_next != in_end))				\
+	if (likely(in_next != in_end)) {			\
 		bitbuf |= (bitbuf_t)*in_next++ << bitsleft;	\
-	else							\
-		overrun_count++;				\
+	} else {						\
+		overread_count++;				\
+		SAFETY_CHECK(overread_count <= sizeof(bitbuf));	\
+	}							\
 	bitsleft += 8;						\
 } while (bitsleft <= BITBUF_NBITS - 8)
 
@@ -307,16 +304,16 @@ if (!HAVE_BITS(n)) {						\
  */
 #define ALIGN_INPUT()							\
 do {									\
-	SAFETY_CHECK(overrun_count <= (bitsleft >> 3));			\
-	in_next -= (bitsleft >> 3) - overrun_count;			\
-	overrun_count = 0;						\
+	SAFETY_CHECK(overread_count <= (bitsleft >> 3));		\
+	in_next -= (bitsleft >> 3) - overread_count;			\
+	overread_count = 0;						\
 	bitbuf = 0;							\
 	bitsleft = 0;							\
 } while(0)
 
 /*
  * Read a 16-bit value from the input.  This must have been preceded by a call
- * to ALIGN_INPUT(), and the caller must have already checked for overrun.
+ * to ALIGN_INPUT(), and the caller must have already checked for overread.
  */
 #define READ_U16() (tmp16 = get_unaligned_le16(in_next), in_next += 2, tmp16)
 
@@ -554,7 +551,7 @@ static const u32 offset_decode_results[DEFLATE_NUM_OFFSET_SYMS] = {
  */
 static bool
 build_decode_table(u32 decode_table[],
-		   const len_t lens[],
+		   const u8 lens[],
 		   const unsigned num_syms,
 		   const u32 decode_results[],
 		   const unsigned table_bits,

lib/gzip_compress.c

@@ -1,8 +1,6 @@
 /*
  * gzip_compress.c - compress with a gzip wrapper
  *
- * Originally public domain; changes after 2016-09-07 are copyrighted.
- *
  * Copyright 2016 Eric Biggers
  *
  * Permission is hereby granted, free of charge, to any person

lib/gzip_decompress.c

@@ -1,8 +1,6 @@
 /*
  * gzip_decompress.c - decompress with a gzip wrapper
  *
- * Originally public domain; changes after 2016-09-07 are copyrighted.
- *
  * Copyright 2016 Eric Biggers
  *
  * Permission is hereby granted, free of charge, to any person

lib/hc_matchfinder.h

@@ -1,8 +1,6 @@
 /*
  * hc_matchfinder.h - Lempel-Ziv matchfinding with a hash table of linked lists
  *
- * Originally public domain; changes after 2016-09-07 are copyrighted.
- *
  * Copyright 2016 Eric Biggers
  *
  * Permission is hereby granted, free of charge, to any person
@@ -75,7 +73,7 @@
  * chain for length 3+ matches, the algorithm just checks for one close length 3
  * match, then focuses on finding length 4+ matches.
  *
- * The longest_match() and skip_positions() functions are inlined into the
+ * The longest_match() and skip_bytes() functions are inlined into the
  * compressors that use them.  This isn't just about saving the overhead of a
  * function call.  These functions are intended to be called from the inner
  * loops of compressors, where giving the compiler more control over register
@@ -131,11 +129,7 @@ struct hc_matchfinder {
 	 * the node for the sequence with position 'pos' is 'next_tab[pos]'.  */
 	mf_pos_t next_tab[MATCHFINDER_WINDOW_SIZE];
 
-}
-#ifdef _aligned_attribute
-  _aligned_attribute(MATCHFINDER_MEM_ALIGNMENT)
-#endif
-;
+} MATCHFINDER_ALIGNED;
 
 /* Prepare the matchfinder for a new input buffer.  */
 static forceinline void
@@ -164,9 +158,9 @@ hc_matchfinder_slide_window(struct hc_matchfinder *mf)
  *	Location of a pointer which points to the place in the input data the
  *	matchfinder currently stores positions relative to.  This may be updated
  *	by this function.
- * @cur_pos
- *	The current position in the input buffer relative to @in_base (the
- *	position of the sequence being matched against).
+ * @in_next
+ *	Pointer to the next position in the input buffer, i.e. the sequence
+ *	being matched against.
  * @best_len
  *	Require a match longer than this length.
  * @max_len
@@ -353,26 +347,24 @@ out:
  *	Location of a pointer which points to the place in the input data the
  *	matchfinder currently stores positions relative to.  This may be updated
  *	by this function.
- * @cur_pos
- *	The current position in the input buffer relative to @in_base.
- * @end_pos
- *	The end position of the input buffer, relative to @in_base.
+ * @in_next
+ *	Pointer to the next position in the input buffer.
+ * @in_end
+ *	Pointer to the end of the input buffer.
+ * @count
+ *	The number of bytes to advance.  Must be > 0.
  * @next_hashes
  *	The precomputed hash codes for the sequence beginning at @in_next.
  *	These will be used and then updated with the precomputed hashcodes for
  *	the sequence beginning at @in_next + @count.
- * @count
- *	The number of bytes to advance.  Must be > 0.
- *
- * Returns @in_next + @count.
  */
-static forceinline const u8 *
-hc_matchfinder_skip_positions(struct hc_matchfinder * const restrict mf,
-			      const u8 ** const restrict in_base_p,
-			      const u8 *in_next,
-			      const u8 * const in_end,
-			      const u32 count,
-			      u32 * const restrict next_hashes)
+static forceinline void
+hc_matchfinder_skip_bytes(struct hc_matchfinder * const restrict mf,
+			  const u8 ** const restrict in_base_p,
+			  const u8 *in_next,
+			  const u8 * const in_end,
+			  const u32 count,
+			  u32 * const restrict next_hashes)
 {
 	u32 cur_pos;
 	u32 hash3, hash4;
@@ -380,7 +372,7 @@ hc_matchfinder_skip_positions(struct hc_matchfinder * const restrict mf,
 	u32 remaining = count;
 
 	if (unlikely(count + 5 > in_end - in_next))
-		return &in_next[count];
+		return;
 
 	cur_pos = in_next - *in_base_p;
 	hash3 = next_hashes[0];
@@ -405,8 +397,6 @@ hc_matchfinder_skip_positions(struct hc_matchfinder * const restrict mf,
 	prefetchw(&mf->hash4_tab[hash4]);
 	next_hashes[0] = hash3;
 	next_hashes[1] = hash4;
-
-	return in_next;
 }
 
 #endif /* LIB_HC_MATCHFINDER_H */

lib/ht_matchfinder.h

@@ -0,0 +1,234 @@
+/*
+ * ht_matchfinder.h - Lempel-Ziv matchfinding with a hash table
+ *
+ * Copyright 2022 Eric Biggers
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ *
+ * ---------------------------------------------------------------------------
+ *
+ * This is a Hash Table (ht) matchfinder.
+ *
+ * This is a variant of the Hash Chains (hc) matchfinder that is optimized for
+ * very fast compression.  The ht_matchfinder stores the hash chains inline in
+ * the hash table, whereas the hc_matchfinder stores them in a separate array.
+ * Storing the hash chains inline is the faster method when max_search_depth
+ * (the maximum chain length) is very small.  It is not appropriate when
+ * max_search_depth is larger, as then it uses too much memory.
+ *
+ * Due to its focus on speed, the ht_matchfinder doesn't support length 3
+ * matches.  It also doesn't allow max_search_depth to vary at runtime; it is
+ * fixed at build time as HT_MATCHFINDER_BUCKET_SIZE.
+ *
+ * See hc_matchfinder.h for more information.
+ */
+
+#ifndef LIB_HT_MATCHFINDER_H
+#define LIB_HT_MATCHFINDER_H
+
+#include "matchfinder_common.h"
+
+#define HT_MATCHFINDER_HASH_ORDER	15
+#define HT_MATCHFINDER_BUCKET_SIZE	2
+
+#define HT_MATCHFINDER_MIN_MATCH_LEN	4
+/* Minimum value of max_len for ht_matchfinder_longest_match() */
+#define HT_MATCHFINDER_REQUIRED_NBYTES	5
+
+struct ht_matchfinder {
+	mf_pos_t hash_tab[1UL << HT_MATCHFINDER_HASH_ORDER]
+			 [HT_MATCHFINDER_BUCKET_SIZE];
+} MATCHFINDER_ALIGNED;
+
+static forceinline void
+ht_matchfinder_init(struct ht_matchfinder *mf)
+{
+	STATIC_ASSERT(sizeof(*mf) % MATCHFINDER_SIZE_ALIGNMENT == 0);
+
+	matchfinder_init((mf_pos_t *)mf, sizeof(*mf));
+}
+
+static forceinline void
+ht_matchfinder_slide_window(struct ht_matchfinder *mf)
+{
+	matchfinder_rebase((mf_pos_t *)mf, sizeof(*mf));
+}
+
+/* Note: max_len must be >= HT_MATCHFINDER_REQUIRED_NBYTES */
+static forceinline u32
+ht_matchfinder_longest_match(struct ht_matchfinder * const restrict mf,
+			     const u8 ** const restrict in_base_p,
+			     const u8 * const restrict in_next,
+			     const u32 max_len,
+			     const u32 nice_len,
+			     u32 * const restrict next_hash,
+			     u32 * const restrict offset_ret)
+{
+	u32 best_len = 0;
+	const u8 *best_matchptr = in_next;
+	u32 cur_pos = in_next - *in_base_p;
+	const u8 *in_base;
+	mf_pos_t cutoff;
+	u32 hash;
+	u32 seq;
+	mf_pos_t cur_node;
+	const u8 *matchptr;
+#if HT_MATCHFINDER_BUCKET_SIZE > 1
+	mf_pos_t to_insert;
+	u32 len;
+#endif
+#if HT_MATCHFINDER_BUCKET_SIZE > 2
+	int i;
+#endif
+
+	/* This is assumed throughout this function. */
+	STATIC_ASSERT(HT_MATCHFINDER_MIN_MATCH_LEN == 4);
+
+	if (cur_pos == MATCHFINDER_WINDOW_SIZE) {
+		ht_matchfinder_slide_window(mf);
+		*in_base_p += MATCHFINDER_WINDOW_SIZE;
+		cur_pos = 0;
+	}
+	in_base = *in_base_p;
+	cutoff = cur_pos - MATCHFINDER_WINDOW_SIZE;
+
+	hash = *next_hash;
+	STATIC_ASSERT(HT_MATCHFINDER_REQUIRED_NBYTES == 5);
+	*next_hash = lz_hash(get_unaligned_le32(in_next + 1),
+			     HT_MATCHFINDER_HASH_ORDER);
+	seq = load_u32_unaligned(in_next);
+	prefetchw(&mf->hash_tab[*next_hash]);
+#if HT_MATCHFINDER_BUCKET_SIZE == 1
+	/* Hand-unrolled version for BUCKET_SIZE == 1 */
+	cur_node = mf->hash_tab[hash][0];
+	mf->hash_tab[hash][0] = cur_pos;
+	if (cur_node <= cutoff)
+		goto out;
+	matchptr = &in_base[cur_node];
+	if (load_u32_unaligned(matchptr) == seq) {
+		best_len = lz_extend(in_next, matchptr, 4, max_len);
+		best_matchptr = matchptr;
+	}
+#elif HT_MATCHFINDER_BUCKET_SIZE == 2
+	/*
+	 * Hand-unrolled version for BUCKET_SIZE == 2.  The logic here also
+	 * differs slightly in that it copies the first entry to the second even
+	 * if nice_len is reached on the first, as this can be slightly faster.
+	 */
+	cur_node = mf->hash_tab[hash][0];
+	mf->hash_tab[hash][0] = cur_pos;
+	if (cur_node <= cutoff)
+		goto out;
+	matchptr = &in_base[cur_node];
+
+	to_insert = cur_node;
+	cur_node = mf->hash_tab[hash][1];
+	mf->hash_tab[hash][1] = to_insert;
+
+	if (load_u32_unaligned(matchptr) == seq) {
+		best_len = lz_extend(in_next, matchptr, 4, max_len);
+		best_matchptr = matchptr;
+		if (cur_node <= cutoff || best_len >= nice_len)
+			goto out;
+		matchptr = &in_base[cur_node];
+		if (load_u32_unaligned(matchptr) == seq &&
+		    load_u32_unaligned(matchptr + best_len - 3) ==
+		    load_u32_unaligned(in_next + best_len - 3)) {
+			len = lz_extend(in_next, matchptr, 4, max_len);
+			if (len > best_len) {
+				best_len = len;
+				best_matchptr = matchptr;
+			}
+		}
+	} else {
+		if (cur_node <= cutoff)
+			goto out;
+		matchptr = &in_base[cur_node];
+		if (load_u32_unaligned(matchptr) == seq) {
+			best_len = lz_extend(in_next, matchptr, 4, max_len);
+			best_matchptr = matchptr;
+		}
+	}
+#else
+	/* Generic version for HT_MATCHFINDER_BUCKET_SIZE > 2 */
+	to_insert = cur_pos;
+	for (i = 0; i < HT_MATCHFINDER_BUCKET_SIZE; i++) {
+		cur_node = mf->hash_tab[hash][i];
+		mf->hash_tab[hash][i] = to_insert;
+		if (cur_node <= cutoff)
+			goto out;
+		matchptr = &in_base[cur_node];
+		if (load_u32_unaligned(matchptr) == seq) {
+			len = lz_extend(in_next, matchptr, 4, max_len);
+			if (len > best_len) {
+				best_len = len;
+				best_matchptr = matchptr;
+				if (best_len >= nice_len)
+					goto out;
+			}
+		}
+		to_insert = cur_node;
+	}
+#endif
+out:
+	*offset_ret = in_next - best_matchptr;
+	return best_len;
+}
+
+static forceinline void
+ht_matchfinder_skip_bytes(struct ht_matchfinder * const restrict mf,
+			  const u8 ** const restrict in_base_p,
+			  const u8 *in_next,
+			  const u8 * const in_end,
+			  const u32 count,
+			  u32 * const restrict next_hash)
+{
+	s32 cur_pos = in_next - *in_base_p;
+	u32 hash;
+	u32 remaining = count;
+	int i;
+
+	if (unlikely(count + HT_MATCHFINDER_REQUIRED_NBYTES > in_end - in_next))
+		return;
+
+	if (cur_pos + count - 1 >= MATCHFINDER_WINDOW_SIZE) {
+		ht_matchfinder_slide_window(mf);
+		*in_base_p += MATCHFINDER_WINDOW_SIZE;
+		cur_pos -= MATCHFINDER_WINDOW_SIZE;
+	}
+
+	hash = *next_hash;
+	do {
+		for (i = HT_MATCHFINDER_BUCKET_SIZE - 1; i > 0; i--)
+			mf->hash_tab[hash][i] = mf->hash_tab[hash][i - 1];
+		mf->hash_tab[hash][0] = cur_pos;
+
+		hash = lz_hash(get_unaligned_le32(++in_next),
+			       HT_MATCHFINDER_HASH_ORDER);
+		cur_pos++;
+	} while (--remaining);
+
+	prefetchw(&mf->hash_tab[hash]);
+	*next_hash = hash;
+}
+
+#endif /* LIB_HT_MATCHFINDER_H */

lib/matchfinder_common.h

@@ -28,11 +28,14 @@ typedef s16 mf_pos_t;
 #undef matchfinder_init
 #undef matchfinder_rebase
 #ifdef _aligned_attribute
+#  define MATCHFINDER_ALIGNED _aligned_attribute(MATCHFINDER_MEM_ALIGNMENT)
 #  if defined(__arm__) || defined(__aarch64__)
 #    include "arm/matchfinder_impl.h"
 #  elif defined(__i386__) || defined(__x86_64__)
 #    include "x86/matchfinder_impl.h"
 #  endif
+#else
+#  define MATCHFINDER_ALIGNED
 #endif
 
 /*

lib/zlib_compress.c

@@ -1,8 +1,6 @@
 /*
  * zlib_compress.c - compress with a zlib wrapper
  *
- * Originally public domain; changes after 2016-09-07 are copyrighted.
- *
  * Copyright 2016 Eric Biggers
  *
  * Permission is hereby granted, free of charge, to any person

lib/zlib_decompress.c

@@ -1,8 +1,6 @@
 /*
  * zlib_decompress.c - decompress with a zlib wrapper
  *
- * Originally public domain; changes after 2016-09-07 are copyrighted.
- *
  * Copyright 2016 Eric Biggers
  *
  * Permission is hereby granted, free of charge, to any person

libdeflate.h

@@ -10,8 +10,8 @@ extern "C" {
 #endif
 
 #define LIBDEFLATE_VERSION_MAJOR	1
-#define LIBDEFLATE_VERSION_MINOR	8
-#define LIBDEFLATE_VERSION_STRING	"1.8"
+#define LIBDEFLATE_VERSION_MINOR	10
+#define LIBDEFLATE_VERSION_STRING	"1.10"
 
 #include <stddef.h>
 #include <stdint.h>
@@ -31,7 +31,7 @@ extern "C" {
 #  define LIBDEFLATEEXPORT
 #endif
 
-#if defined(_WIN32) && !defined(_WIN64)
+#if defined(_WIN32) && !defined(_WIN64) && defined(LIBDEFLATE_DLL)
 #  define LIBDEFLATEAPI_ABI	__stdcall
 #else
 #  define LIBDEFLATEAPI_ABI

programs/gzip.c

@@ -38,6 +38,12 @@
 #  include <utime.h>
 #endif
 
+#define GZIP_MIN_HEADER_SIZE	10
+#define GZIP_FOOTER_SIZE	8
+#define GZIP_MIN_OVERHEAD	(GZIP_MIN_HEADER_SIZE + GZIP_FOOTER_SIZE)
+#define GZIP_ID1		0x1F
+#define GZIP_ID2		0x8B
+
 struct options {
 	bool to_stdout;
 	bool decompress;
@@ -48,13 +54,13 @@ struct options {
 	const tchar *suffix;
 };
 
-static const tchar *const optstring = T("1::2::3::4::5::6::7::8::9::cdfhknS:tV");
+static const tchar *const optstring = T("1::2::3::4::5::6::7::8::9::cdfhknqS:tV");
 
 static void
 show_usage(FILE *fp)
 {
 	fprintf(fp,
-"Usage: %"TS" [-LEVEL] [-cdfhkV] [-S SUF] FILE...\n"
+"Usage: %"TS" [-LEVEL] [-cdfhkqtV] [-S SUF] FILE...\n"
 "Compress or decompress the specified FILEs.\n"
 "\n"
 "Options:\n"
@@ -63,9 +69,12 @@ show_usage(FILE *fp)
 "  -12       slowest (best) compression\n"
 "  -c        write to standard output\n"
 "  -d        decompress\n"
-"  -f        overwrite existing output files\n"
+"  -f        overwrite existing output files; (de)compress hard-linked files;\n"
+"            allow reading/writing compressed data from/to terminal;\n"
+"            with gunzip -c, pass through non-gzipped data\n"
 "  -h        print this help\n"
 "  -k        don't delete input files\n"
+"  -q        suppress warnings\n"
 "  -S SUF    use suffix SUF instead of .gz\n"
 "  -t        test file integrity\n"
 "  -V        show version and legal information\n",
@@ -192,15 +201,19 @@ do_decompress(struct libdeflate_decompressor *decompressor,
 	size_t compressed_size = in->mmap_size;
 	void *uncompressed_data = NULL;
 	size_t uncompressed_size;
+	size_t max_uncompressed_size;
 	size_t actual_in_nbytes;
 	size_t actual_out_nbytes;
 	enum libdeflate_result result;
 	int ret = 0;
 
-	if (compressed_size < sizeof(u32)) {
-	       msg("%"TS": not in gzip format", in->name);
-	       ret = -1;
-	       goto out;
+	if (compressed_size < GZIP_MIN_OVERHEAD ||
+	    compressed_data[0] != GZIP_ID1 ||
+	    compressed_data[1] != GZIP_ID2) {
+		if (options->force)
+			return full_write(out, compressed_data, compressed_size);
+		msg("%"TS": not in gzip format", in->name);
+		return -1;
 	}
 
 	/*
@@ -214,8 +227,23 @@ do_decompress(struct libdeflate_decompressor *decompressor,
 	if (uncompressed_size == 0)
 		uncompressed_size = 1;
 
+	/*
+	 * DEFLATE cannot expand data more than 1032x, so there's no need to
+	 * ever allocate a buffer more than 1032 times larger than the
+	 * compressed data.  This is a fail-safe, albeit not a very good one, if
+	 * ISIZE becomes corrupted on a small file.  (The 1032x number comes
+	 * from each 2 bits generating a 258-byte match.  This is a hard upper
+	 * bound; the real upper bound is slightly smaller due to overhead.)
+	 */
+	if (compressed_size <= SIZE_MAX / 1032)
+		max_uncompressed_size = compressed_size * 1032;
+	else
+		max_uncompressed_size = SIZE_MAX;
+
 	do {
 		if (uncompressed_data == NULL) {
+			uncompressed_size = MIN(uncompressed_size,
+						max_uncompressed_size);
 			uncompressed_data = xmalloc(uncompressed_size);
 			if (uncompressed_data == NULL) {
 				msg("%"TS": file is probably too large to be "
@@ -234,6 +262,11 @@ do_decompress(struct libdeflate_decompressor *decompressor,
 						       &actual_out_nbytes);
 
 		if (result == LIBDEFLATE_INSUFFICIENT_SPACE) {
+			if (uncompressed_size >= max_uncompressed_size) {
+				msg("Bug in libdeflate_gzip_decompress_ex(): data expanded too much!");
+				ret = -1;
+				goto out;
+			}
 			if (uncompressed_size * 2 <= uncompressed_size) {
 				msg("%"TS": file corrupt or too large to be "
 				    "processed by this program", in->name);
@@ -256,7 +289,7 @@ do_decompress(struct libdeflate_decompressor *decompressor,
 		if (actual_in_nbytes == 0 ||
 		    actual_in_nbytes > compressed_size ||
 		    actual_out_nbytes > uncompressed_size) {
-			msg("Bug in libdeflate_gzip_decompress_ex()!");
+			msg("Bug in libdeflate_gzip_decompress_ex(): impossible actual_nbytes value!");
 			ret = -1;
 			goto out;
 		}
@@ -285,15 +318,15 @@ stat_file(struct file_stream *in, stat_t *stbuf, bool allow_hard_links)
 	}
 
 	if (!S_ISREG(stbuf->st_mode) && !in->is_standard_stream) {
-		msg("%"TS" is %s -- skipping",
-		    in->name, S_ISDIR(stbuf->st_mode) ? "a directory" :
-							"not a regular file");
+		warn("%"TS" is %s -- skipping",
+		     in->name, S_ISDIR(stbuf->st_mode) ? "a directory" :
+							 "not a regular file");
 		return -2;
 	}
 
 	if (stbuf->st_nlink > 1 && !allow_hard_links) {
-		msg("%"TS" has multiple hard links -- skipping "
-		    "(use -f to process anyway)", in->name);
+		warn("%"TS" has multiple hard links -- skipping (use -f to process anyway)",
+		     in->name);
 		return -2;
 	}
 
@@ -384,9 +417,8 @@ decompress_file(struct libdeflate_decompressor *decompressor, const tchar *path,
 				if (!options->to_stdout)
 					newpath = (tchar *)path;
 			} else if (!options->to_stdout) {
-				msg("\"%"TS"\" does not end with the %"TS" "
-				    "suffix -- skipping",
-				    path, options->suffix);
+				warn("\"%"TS"\" does not end with the %"TS" suffix -- skipping",
+				     path, options->suffix);
 				return -2;
 			}
 		} else if (!options->to_stdout) {
@@ -582,6 +614,9 @@ tmain(int argc, tchar *argv[])
 			 *  option as a no-op.
 			 */
 			break;
+		case 'q':
+			suppress_warnings = true;
+			break;
 		case 'S':
 			options.suffix = toptarg;
 			if (options.suffix[0] == T('\0')) {
@@ -646,13 +681,17 @@ tmain(int argc, tchar *argv[])
 		libdeflate_free_compressor(c);
 	}
 
-	/*
-	 * If ret=0, there were no warnings or errors.  Exit with status 0.
-	 * If ret=2, there was at least one warning.  Exit with status 2.
-	 * Else, there was at least one error.  Exit with status 1.
-	 */
-	if (ret != 0 && ret != 2)
-		ret = 1;
-
-	return ret;
+	switch (ret) {
+	case 0:
+		/* No warnings or errors */
+		return 0;
+	case 2:
+		/* At least one warning, but no errors */
+		if (suppress_warnings)
+			return 0;
+		return 2;
+	default:
+		/* At least one error */
+		return 1;
+	}
 }

programs/prog_util.c

@@ -56,6 +56,9 @@
 /* The invocation name of the program (filename component only) */
 const tchar *prog_invocation_name;
 
+/* Whether to suppress warning messages or not */
+bool suppress_warnings;
+
 static void
 do_msg(const char *format, bool with_errno, va_list va)
 {
@@ -93,6 +96,20 @@ msg_errno(const char *format, ...)
 	va_end(va);
 }
 
+
+/* Same as msg(), but do nothing if 'suppress_warnings' has been set. */
+void
+warn(const char *format, ...)
+{
+	if (!suppress_warnings) {
+		va_list va;
+
+		va_start(va, format);
+		do_msg(format, false, va);
+		va_end(va);
+	}
+}
+
 /* malloc() wrapper */
 void *
 xmalloc(size_t size)
@@ -226,8 +243,8 @@ retry:
 		}
 		if (!overwrite) {
 			if (!isatty(STDERR_FILENO) || !isatty(STDIN_FILENO)) {
-				msg("%"TS" already exists; use -f to overwrite",
-				    strm->name);
+				warn("%"TS" already exists; use -f to overwrite",
+				     strm->name);
 				ret = -2; /* warning only */
 				goto err;
 			}

programs/prog_util.h

@@ -137,9 +137,11 @@ int wmain(int argc, wchar_t **argv);
 #endif /* !_WIN32 */
 
 extern const tchar *prog_invocation_name;
+extern bool suppress_warnings;
 
 void _printf(1, 2) msg(const char *fmt, ...);
 void _printf(1, 2) msg_errno(const char *fmt, ...);
+void _printf(1, 2) warn(const char *fmt, ...);
 
 void *xmalloc(size_t size);
 

programs/test_overread.c

@@ -0,0 +1,95 @@
+/*
+ * test_overread.c
+ *
+ * Test that the decompressor doesn't produce an unbounded amount of output if
+ * it runs out of input, even when implicit zeroes appended to the input would
+ * continue producing output (as is the case when the input ends during a
+ * DYNAMIC_HUFFMAN block where a literal has an all-zeroes codeword).
+ *
+ * This is a regression test for commit 3f21ec9d6121 ("deflate_decompress: error
+ * out if overread count gets too large").
+ */
+
+#include "test_util.h"
+
+static void
+generate_test_input(struct output_bitstream *os)
+{
+	int i;
+
+	put_bits(os, 0, 1);	/* BFINAL: 0 */
+	put_bits(os, 2, 2);	/* BTYPE: DYNAMIC_HUFFMAN */
+
+	/*
+	 * Write the Huffman codes.
+	 *
+	 * Litlen code:
+	 *	litlensym_0   (0)		len=1 codeword=0
+	 *	litlensym_256 (end-of-block)	len=1 codeword=1
+	 * Offset code:
+	 *	offsetsym_0 (unused)		len=1 codeword=0
+	 *
+	 * Litlen and offset codeword lengths:
+	 *	[0]	 = 1	presym_1
+	 *	[1..255] = 0	presym_{18,18}
+	 *	[256]	 = 1	presym_1
+	 *	[257]	 = 1	presym_1
+	 *
+	 * Precode:
+	 *	presym_1	len=1 codeword=0
+	 *	presym_18	len=1 codeword=1
+	 */
+	put_bits(os, 0, 5);	/* num_litlen_syms: 0 + 257 */
+	put_bits(os, 0, 5);	/* num_offset_syms: 0 + 1 */
+	put_bits(os, 14, 4);	/* num_explicit_precode_lens: 14 + 4 */
+	/*
+	 * Precode codeword lengths: order is
+	 * [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15]
+	 */
+	put_bits(os, 0, 3);		/* presym_16: len=0 */
+	put_bits(os, 0, 3);		/* presym_17: len=0 */
+	put_bits(os, 1, 3);		/* presym_18: len=1 */
+	for (i = 0; i < 14; i++)	/* presym_{0,...,14}: len=0 */
+		put_bits(os, 0, 3);
+	put_bits(os, 1, 3);		/* presym_1: len=1 */
+
+	/* Litlen and offset codeword lengths */
+	put_bits(os, 0, 1);		/* presym_1 */
+	put_bits(os, 1, 1);		/* presym_18 ... */
+	put_bits(os, 117, 7);		/* ... 11 + 117 zeroes */
+	put_bits(os, 1, 1);		/* presym_18 ... */
+	put_bits(os, 116, 7);		/* ... 11 + 116 zeroes */
+	put_bits(os, 0, 1);		/* presym_1 */
+	put_bits(os, 0, 1);		/* presym_1 */
+
+	/* Implicit zeroes would generate endless literals from here. */
+
+	ASSERT(flush_bits(os));
+}
+
+int
+tmain(int argc, tchar *argv[])
+{
+	u8 cdata[16];
+	u8 udata[256];
+	struct output_bitstream os =
+		{ .next = cdata, .end = cdata + sizeof(cdata) };
+	struct libdeflate_decompressor *d;
+	enum libdeflate_result res;
+	size_t actual_out_nbytes;
+
+	begin_program(argv);
+
+	generate_test_input(&os);
+	d = libdeflate_alloc_decompressor();
+	ASSERT(d != NULL);
+
+	res = libdeflate_deflate_decompress(d, cdata, os.next - cdata,
+					    udata, sizeof(udata),
+					    &actual_out_nbytes);
+	/* Before the fix, the result was LIBDEFLATE_INSUFFICIENT_SPACE here. */
+	ASSERT(res == LIBDEFLATE_BAD_DATA);
+
+	libdeflate_free_decompressor(d);
+	return 0;
+}

scripts/afl-fuzz/.gitignore

@@ -0,0 +1 @@
+*/fuzz

scripts/afl-fuzz/Makefile

@@ -1,7 +1,6 @@
 SRC := $(wildcard */*.c)
 EXE := $(SRC:.c=)
 
-CFLAGS := -O2 -s
 LDLIBS := -ldeflate
 LDFLAGS := -L../..
 CPPFLAGS := -I../..

scripts/afl-fuzz/deflate_compress/fuzz.c

@@ -12,15 +12,22 @@ int main(int argc, char **argv)
 	int ret;
 	int fd = open(argv[1], O_RDONLY);
 	struct stat stbuf;
+	unsigned char level;
 	assert(fd >= 0);
 	ret = fstat(fd, &stbuf);
 	assert(!ret);
 
-	char in[stbuf.st_size];
+	if (stbuf.st_size == 0)
+		return 0;
+	ret = read(fd, &level, 1);
+	assert(ret == 1);
+	level %= 13;
+
+	char in[stbuf.st_size - 1];
 	ret = read(fd, in, sizeof in);
 	assert(ret == sizeof in);
 
-	c = libdeflate_alloc_compressor(6);
+	c = libdeflate_alloc_compressor(level);
 	d = libdeflate_alloc_decompressor();
 
 	char out[sizeof(in)];

scripts/afl-fuzz/fuzz.sh

@@ -0,0 +1,148 @@
+#!/bin/bash
+
+set -e -u -o pipefail
+
+cd "$(dirname "$0")"
+
+read -r -a AVAILABLE_TARGETS < <(echo */fuzz.c | sed 's@/fuzz.c@@g')
+
+usage()
+{
+	cat << EOF
+Usage: $0 [OPTION]... [TARGET]...
+
+Fuzz libdeflate with afl-fuzz.
+
+Options:
+   --asan          Enable AddressSanitizer
+   --no-resume     Don't resume existing afl-fuzz session; start a new one
+   --ubsan         Enable UndefinedBehaviorSanitizer
+
+Available targets: ${AVAILABLE_TARGETS[*]}
+EOF
+}
+
+die()
+{
+	echo "$*" 1>&2
+	exit 1
+}
+
+asan=false
+ubsan=false
+may_resume=true
+
+longopts_array=(
+asan
+help
+no-resume
+ubsan
+)
+longopts=$(echo "${longopts_array[@]}" | tr ' ' ',')
+
+if ! options=$(getopt -o "" -l "$longopts" -- "$@"); then
+	usage 1>&2
+	exit 1
+fi
+eval set -- "$options"
+while (( $# >= 0 )); do
+	case "$1" in
+	--asan)
+		asan=true
+		;;
+	--help)
+		usage
+		exit 0
+		;;
+	--no-resume)
+		may_resume=false
+		;;
+	--ubsan)
+		ubsan=true
+		;;
+	--)
+		shift
+		break
+		;;
+	*)
+		echo 1>&2 "Invalid option: \"$1\""
+		usage 1>&2
+		exit 1
+	esac
+	shift
+done
+
+if $asan && $ubsan; then
+	die "--asan and --ubsan are mutually exclusive"
+fi
+
+if ! type -P afl-fuzz > /dev/null; then
+	die "afl-fuzz is not installed"
+fi
+
+if (( $# == 0 )); then
+	targets=("${AVAILABLE_TARGETS[@]}")
+else
+	for target; do
+		found=false
+		for t in "${AVAILABLE_TARGETS[@]}"; do
+			if [ "$target" = "$t" ]; then
+				found=true
+			fi
+		done
+		if ! $found; then
+			echo 1>&2 "Unknown target '$target'"
+			echo 1>&2 "Available targets: ${AVAILABLE_TARGETS[*]}"
+			exit 1
+		fi
+	done
+	targets=("$@")
+fi
+if (( ${#targets[@]} > 1 )) && ! type -P urxvt > /dev/null; then
+	die "urxvt is not installed"
+fi
+
+afl_opts=""
+if $asan; then
+	export AFL_USE_ASAN=1
+	export CFLAGS="-O2 -m32"
+	export CC=afl-clang
+	afl_opts+=" -m 800"
+elif $ubsan; then
+	export CFLAGS="-fsanitize=undefined -fno-sanitize-recover=undefined"
+	export CC=afl-gcc
+else
+	export AFL_HARDEN=1
+	export CFLAGS="-O2"
+	export CC=afl-clang-fast
+fi
+
+sudo sh -c "echo core > /proc/sys/kernel/core_pattern"
+sudo sh -c "echo performance | tee /sys/devices/system/cpu/cpu*/cpufreq/scaling_governor"
+
+NPROC=$(getconf _NPROCESSORS_ONLN)
+
+make "-j$NPROC" -C ../../ libdeflate.a
+make "-j$NPROC" -B
+
+for dir in "${targets[@]}"; do
+	cp -vaT "$dir" "/tmp/$dir"
+	indir=/tmp/$dir/inputs
+	outdir=/tmp/$dir/outputs
+	if [ -e "$outdir" ]; then
+		if $may_resume; then
+			indir="-"
+		else
+			rm -rf "${outdir:?}"/*
+		fi
+	else
+		mkdir "$outdir"
+	fi
+	cmd="afl-fuzz -i $indir -o $outdir -T $dir $afl_opts -- /tmp/$dir/fuzz @@"
+	if (( ${#targets[@]} > 1 )); then
+		urxvt -e bash -c "$cmd" &
+	else
+		$cmd
+	fi
+done
+wait

scripts/afl-fuzz/prepare_for_fuzz.sh

@@ -1,14 +0,0 @@
-#!/bin/sh
-
-set -e
-
-make -C ../../ clean
-make clean
-AFL_HARDEN=1 make CC=afl-gcc -C ../../
-AFL_HARDEN=1 make CC=afl-gcc
-
-for dir in $(find . -mindepth 1 -maxdepth 1 -type d); do
-	rm -rf /tmp/$dir
-	cp -va $dir /tmp/$dir
-	mkdir -p /tmp/$dir/outputs
-done

scripts/deflate_benchmarks.sh

@@ -0,0 +1,117 @@
+#!/bin/bash
+
+set -eu -o pipefail
+topdir="$(dirname "$0")/.."
+tmpfile=$(mktemp)
+trap 'rm -f $tmpfile' EXIT
+
+run_benchmark()
+{
+	local best_ctime=1000000000
+	local i
+
+	for i in $(seq "$NUM_ITERATIONS"); do
+		"$@" > "$tmpfile"
+		csize=$(awk '/Compressed/{print $4}' "$tmpfile")
+		ctime=$(awk '/Compression time/{print $3}' "$tmpfile")
+		if (( ctime <  best_ctime )); then
+			best_ctime=$ctime
+		fi
+		: "$i" # make shellcheck happy
+	done
+	CSIZE=$csize
+	CTIME=$best_ctime
+}
+
+multifile()
+{
+	local file results cmd best em
+
+	NUM_ITERATIONS=1
+
+	echo "File | zlib -6 | zlib -9 | libdeflate -6 | libdeflate -9 | libdeflate -12"
+	echo "-----|---------|---------|---------------|---------------|---------------"
+
+	for file in "$@"; do
+		echo -n "$(basename "$file")"
+		results=()
+		cmd=("$topdir/benchmark" -s"$(stat -c "%s" "$file")" "$file")
+		run_benchmark "${cmd[@]}" -Y -6
+		results+=("$CSIZE")
+		run_benchmark "${cmd[@]}" -Y -6
+		results+=("$CSIZE")
+		run_benchmark "${cmd[@]}" -6
+		results+=("$CSIZE")
+		run_benchmark "${cmd[@]}" -9
+		results+=("$CSIZE")
+		run_benchmark "${cmd[@]}" -12
+		results+=("$CSIZE")
+		best=2000000000
+		for result in "${results[@]}"; do
+			if (( result < best)); then
+				best=$result
+			fi
+		done
+		for result in "${results[@]}"; do
+			if (( result == best )); then
+				em="**"
+			else
+				em=""
+			fi
+			echo -n " | ${em}${result}${em}"
+		done
+		echo
+	done
+}
+
+single_file()
+{
+	local file=$1
+	local usize args
+	local include_old=false
+
+	usize=$(stat -c "%s" "$file")
+	: ${NUM_ITERATIONS:=3}
+
+	if [ -e "$topdir/benchmark-old" ]; then
+		include_old=true
+	fi
+	echo -n "Level | libdeflate (new) "
+	if $include_old; then
+		echo -n "| libdeflate (old) "
+	fi
+	echo "| zlib"
+	echo -n "------|------------------"
+	if $include_old; then
+		echo -n "|------------------"
+	fi
+	echo "|-----"
+	for level in {1..12}; do
+		echo -n "$level"
+		args=("$file" -s "$usize" "-$level")
+
+		run_benchmark "$topdir/benchmark" "${args[@]}"
+		echo -n " | $CSIZE / $CTIME"
+
+		if $include_old; then
+			run_benchmark "$topdir/benchmark-old" "${args[@]}"
+			echo -n " | $CSIZE / $CTIME"
+		fi
+
+		if (( level > 9 )); then
+			echo -n " | N/A"
+		else
+			run_benchmark "$topdir/benchmark" "${args[@]}" -Y
+			echo -n " | $CSIZE / $CTIME"
+		fi
+		echo
+	done
+}
+
+if (( $# > 1 )); then
+	multifile "$@"
+elif (( $# == 1 )); then
+	single_file "$@"
+else
+	echo 1>&2 "Usage: $0 FILE..."
+fi

scripts/gen_crc32_table.c

@@ -1,8 +1,6 @@
 /*
  * gen_crc32_table.c - a program for CRC-32 table generation
  *
- * Originally public domain; changes after 2016-09-07 are copyrighted.
- *
  * Copyright 2016 Eric Biggers
  *
  * Permission is hereby granted, free of charge, to any person

scripts/gen_default_litlen_costs.py

@@ -0,0 +1,44 @@
+#!/usr/bin/env python3
+#
+# This script computes the default litlen symbol costs for the near-optimal
+# parser.
+
+from math import log2
+
+BIT_COST = 16 # Must match BIT_COST in deflate_compress.c
+NUM_LEN_SLOTS = 29
+
+print("""static const struct {
+	u8 used_lits_to_lit_cost[257];
+	u8 len_sym_cost;
+} default_litlen_costs[] = {""")
+MATCH_PROBS = [0.25, 0.50, 0.75]
+for i, match_prob in enumerate(MATCH_PROBS):
+    len_prob = match_prob / NUM_LEN_SLOTS
+    len_sym_cost = int(-log2(len_prob) * BIT_COST)
+    if i == 0:
+        print('\t{', end='')
+    print(f' /* match_prob = {match_prob} */')
+    print('\t\t.used_lits_to_lit_cost = {')
+
+    j = 0
+    for num_used_literals in range(0, 257):
+        if num_used_literals == 0:
+            num_used_literals = 1
+        lit_prob = (1 - match_prob) / num_used_literals
+        lit_cost = int(-log2(lit_prob) * BIT_COST)
+        if j == 0:
+            print('\t\t\t', end='')
+        if j == 7 or num_used_literals == 256:
+            print(f'{lit_cost},')
+            j = 0
+        else:
+            print(f'{lit_cost}, ', end='')
+            j += 1
+    print('\t\t},')
+    print(f'\t\t.len_sym_cost = {len_sym_cost},')
+    if i < len(MATCH_PROBS) - 1:
+        print('\t}, {', end='')
+    else:
+        print('\t},')
+print('};')

scripts/gen_offset_slot_map.py

@@ -0,0 +1,41 @@
+#!/usr/bin/env python3
+#
+# This script generates the deflate_offset_slot[] array, which is a condensed
+# map from offsets to offset slots.
+
+DEFLATE_OFFSET_SLOT_BASE = [
+	1    , 2    , 3    , 4     , 5     , 7     , 9     , 13    ,
+	17   , 25   , 33   , 49    , 65    , 97    , 129   , 193   ,
+	257  , 385  , 513  , 769   , 1025  , 1537  , 2049  , 3073  ,
+	4097 , 6145 , 8193 , 12289 , 16385 , 24577 ,
+]
+
+DEFLATE_EXTRA_OFFSET_BITS = [
+	0    , 0    , 0    , 0     , 1     , 1     , 2     , 2     ,
+	3    , 3    , 4    , 4     , 5     , 5     , 6     , 6     ,
+	7    , 7    , 8    , 8     , 9     , 9     , 10    , 10    ,
+	11   , 11   , 12   , 12    , 13    , 13    ,
+]
+
+offset_slot_map = [0] * 512
+
+for offset_slot, offset_base in enumerate(DEFLATE_OFFSET_SLOT_BASE):
+    num_extra_bits = DEFLATE_EXTRA_OFFSET_BITS[offset_slot]
+    offset_end = offset_base + (1 << num_extra_bits)
+    if offset_base <= 256:
+        for offset in range(offset_base, offset_end):
+            offset_slot_map[offset] = offset_slot
+    else:
+        for offset in range(offset_base, offset_end, 128):
+            offset_slot_map[256 + ((offset - 1) >> 7)] = offset_slot
+
+print('static const u8 deflate_offset_slot_map[512] = {')
+for i in range(0, len(offset_slot_map), 16):
+    print('\t', end='')
+    for j, v in enumerate(offset_slot_map[i:i+16]):
+        print(f'{v},', end='')
+        if j == 15:
+            print('')
+        else:
+            print(' ', end='')
+print('};')

scripts/gzip_tests.sh

@@ -34,6 +34,7 @@ begin_test() {
 	CURRENT_TEST="$1"
 	rm -rf -- "${TMPDIR:?}"/*
 	cp "$TESTDATA" file
+	chmod +w file
 }
 
 gzip() {
@@ -224,6 +225,16 @@ gzip -f file.gz
 cmp file.gz.gz c.gz
 
 
+begin_test 'gunzip -f -c passes through non-gzip data'
+echo hello > file
+cp file orig
+gunzip -f -c file > foo
+cmp file foo
+gzip file
+gunzip -f -c file.gz > foo
+cmp foo orig
+
+
 begin_test 'Decompressing unsuffixed file only works with -c'
 gzip file && mv file.gz file
 assert_skipped gunzip file
@@ -483,6 +494,12 @@ for contents in "${bad_files[@]}"; do
 done
 
 
+begin_test '-q (quiet) option works'
+mkdir dir
+gunzip -q dir &> output || true
+[ ! -s output ]
+
+
 begin_test 'Version information'
 gzip -V | grep -q Copyright
 gunzip -V | grep -q Copyright

scripts/produce_gzip_benchmark_table.sh

@@ -1,37 +0,0 @@
-#!/bin/bash
-
-set -eu -o pipefail
-topdir="$(dirname "$0")/.."
-
-do_benchmark() {
-	"$topdir/benchmark" -g -s "$(stat -c %s "$file")" "$@" "$file" \
-		| grep Compressed | cut -f 4 -d ' '
-}
-
-echo "File | zlib -6 | zlib -9 | libdeflate -6 | libdeflate -9 | libdeflate -12"
-echo "-----|---------|---------|---------------|---------------|---------------"
-
-for file in "$@"; do
-	echo -n "$(basename "$file")"
-	results=()
-	results+=("$(do_benchmark -Y -6)")
-	results+=("$(do_benchmark -Y -9)")
-	results+=("$(do_benchmark -6)")
-	results+=("$(do_benchmark -9)")
-	results+=("$(do_benchmark -12)")
-	best=2000000000
-	for result in "${results[@]}"; do
-		if (( result < best)); then
-			best=$result
-		fi
-	done
-	for result in "${results[@]}"; do
-		if (( result == best )); then
-			em="**"
-		else
-			em=""
-		fi
-		echo -n " | ${em}${result}${em}"
-	done
-	echo
-done