[zlib] Re-land Introducing ANZAC++ hash

Since 2015 Chromium's zlib used a hardware accelerated hashing function
(i.e. CRC32) to insert symbols in the dictionary during compression.

As it was suggested by Noel Gordon, turns out that a portable hash can
actually outperform it, yielding an average gain of 30% to 40% faster* compression while keeping similar compression ratios**.

In these days, such gains are equivalent to more than 3 generations
of silicon.

The new hashing function is called ANZAC++ and can be technically
considered a multiplicative hash (i.e. multiply-add-shift-mask).

Aside being faster, it is also portable and doesn't depend on crypto
extensions to perform (i.e. will work on RISC-V and Armv7).

This patch will use ANZAC as default hashing, plus performs a huge cleanup.

* Average gains: m1(31.3%), RPL_e(39.7%), RPL_p(39.4%),
Cascade(39%), ICX(+38%), SPR(41.9%).

** Average compression ratio loss is 0.1% for the snappy data
corpus.

To Sheriffs: Please don't revert this CL when it breaks any test. Please disable or add failure expectation for the test and I will
fix it ASAP.

Bug: 1070655, 1381000
Change-Id: I961e3fa197181763d555659aa8368832852b037f
Reviewed-on: https://chromium-review.googlesource.com/c/chromium/src/+/4906724
Reviewed-by: Russ Hamilton <behamilton@google.com>
Reviewed-by: Yoav Weiss <yoavweiss@chromium.org>
Reviewed-by: Daniel Murphy <dmurph@chromium.org>
Reviewed-by: Kent Tamura <tkent@chromium.org>
Reviewed-by: Alan Screen <awscreen@chromium.org>
Reviewed-by: Hans Wennborg <hans@chromium.org>
Commit-Queue: Adenilson Cavalcanti <cavalcantii@chromium.org>
Cr-Commit-Position: refs/heads/main@{#1205982}
NOKEYCHECK=True
GitOrigin-RevId: a44021dc678e48efca821d35df53122c4c385e92

2 files changed, 18 insertions, 89 deletions

diff --git a/contrib/optimizations/insert_string.h b/contrib/optimizations/insert_string.h
index c6a296a..260b826 100644
--- a/contrib/optimizations/insert_string.h
+++ b/contrib/optimizations/insert_string.h
@@ -16,64 +16,7 @@
 #endif
 #endif
 
-#include "cpu_features.h"
-
-// clang-format off
-#if defined(CRC32_SIMD_SSE42_PCLMUL)
-  #include <smmintrin.h>  /* Required to make MSVC bot build pass. */
-
-  #if defined(__clang__) || defined(__GNUC__)
-    #define TARGET_CPU_WITH_CRC __attribute__((target("sse4.2")))
-  #else
-    #define TARGET_CPU_WITH_CRC
-  #endif
-
-  /* CRC32C uint32_t */
-  #define _cpu_crc32c_hash_u32 _mm_crc32_u32
-
-#elif defined(CRC32_ARMV8_CRC32)
-  #if defined(__clang__)
-    #define __crc32cw __builtin_arm_crc32cw
-  #elif defined(__GNUC__)
-    #define __crc32cw __builtin_aarch64_crc32cw
-  #endif
-
-  #if defined(__aarch64__) && defined(__clang__)
-    #define TARGET_CPU_WITH_CRC __attribute__((target("crc")))
-  #elif defined(__aarch64__) && defined(__GNUC__)
-    #define TARGET_CPU_WITH_CRC __attribute__((target("+crc")))
-  #elif defined(__clang__) // !defined(__aarch64__)
-    #define TARGET_CPU_WITH_CRC __attribute__((target("armv8-a,crc")))
-  #endif  // defined(__aarch64__)
-
-  /* CRC32C uint32_t */
-  #define _cpu_crc32c_hash_u32 __crc32cw
-
-#endif
-// clang-format on
-
-#if defined(TARGET_CPU_WITH_CRC)
-
-TARGET_CPU_WITH_CRC
-local INLINE Pos insert_string_simd(deflate_state* const s, const Pos str) {
-  Pos ret;
-  unsigned val, h = 0;
-
-  zmemcpy(&val, &s->window[str], sizeof(val));
-
-  if (s->level >= 6)
-    val &= 0xFFFFFF;
-
-  /* Compute hash from the CRC32C of |val|. */
-  h = _cpu_crc32c_hash_u32(h, val);
-
-  ret = s->head[h & s->hash_mask];
-  s->head[h & s->hash_mask] = str;
-  s->prev[str & s->w_mask] = ret;
-  return ret;
-}
-
-#endif // TARGET_CPU_WITH_CRC
+#include <stdint.h>
 
 /**
  * Some applications need to match zlib DEFLATE output exactly [3]. Use the
@@ -107,10 +50,23 @@ local INLINE Pos insert_string_simd(deflate_state* const s, const Pos str) {
  *    characters and the first MIN_MATCH bytes of str are valid (except for
  *    the last MIN_MATCH-1 bytes of the input file).
  */
-local INLINE Pos insert_string_c(deflate_state* const s, const Pos str) {
+local INLINE Pos insert_string(deflate_state* const s, const Pos str) {
   Pos ret;
-
+/* insert_string dictionary insertion: ANZAC++ hasher
+ * significantly improves data compression speed.
+ *
+ * Note: the generated compressed output is a valid DEFLATE stream, but will
+ * differ from canonical zlib output.
+ */
+#if defined(USE_ZLIB_RABIN_KARP_ROLLING_HASH)
   UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH - 1)]);
+#else
+  uint32_t value;
+  // Validated for little endian archs (i.e. x86, Arm). YMMV for big endian.
+  zmemcpy(&value, &s->window[str], sizeof(value));
+  s->ins_h = ((value * 66521 + 66521) >> 16) & s->hash_mask;
+#endif
+
 #ifdef FASTEST
   ret = s->head[s->ins_h];
 #else
@@ -121,25 +77,4 @@ local INLINE Pos insert_string_c(deflate_state* const s, const Pos str) {
   return ret;
 }
 
-local INLINE Pos insert_string(deflate_state* const s, const Pos str) {
-/* insert_string_simd string dictionary insertion: SIMD crc32c symbol hasher
- * significantly improves data compression speed.
- *
- * Note: the generated compressed output is a valid DEFLATE stream, but will
- * differ from canonical zlib output.
- */
-#if defined(USE_ZLIB_RABIN_KARP_ROLLING_HASH)
-/* So this build-time option can be used to disable the crc32c hash, and use
- * the Rabin-Karp hash instead.
- */ /* FALLTHROUGH Rabin-Karp */
-#elif defined(TARGET_CPU_WITH_CRC) && defined(CRC32_SIMD_SSE42_PCLMUL)
-  if (x86_cpu_enable_simd)
-    return insert_string_simd(s, str);
-#elif defined(TARGET_CPU_WITH_CRC) && defined(CRC32_ARMV8_CRC32)
-  if (arm_cpu_enable_crc32)
-    return insert_string_simd(s, str);
-#endif
-  return insert_string_c(s, str); /* Rabin-Karp */
-}
-
 #endif /* INSERT_STRING_H */
diff --git a/deflate.c b/deflate.c
index 1fa55e5..173ce59 100644
--- a/deflate.c
+++ b/deflate.c
@@ -457,15 +457,9 @@ int ZEXPORT deflateInit2_(z_streamp strm, int level, int method,
     s->w_size = 1 << s->w_bits;
     s->w_mask = s->w_size - 1;
 
+    s->chromium_zlib_hash = 1;
+#if defined(USE_ZLIB_RABIN_KARP_ROLLING_HASH)
     s->chromium_zlib_hash = 0;
-#if !defined(USE_ZLIB_RABIN_KARP_ROLLING_HASH)
-  #if defined(TARGET_CPU_WITH_CRC) && defined(CRC32_SIMD_SSE42_PCLMUL)
-    if (x86_cpu_enable_simd)
-      s->chromium_zlib_hash = 1;
-  #elif defined(TARGET_CPU_WITH_CRC) && defined(CRC32_ARMV8_CRC32)
-    if (arm_cpu_enable_crc32)
-      s->chromium_zlib_hash = 1;
-  #endif
 #endif
 
     s->hash_bits = memLevel + 7;