Use XXH3 for cache, hash table hashing

XXH3 is faster than both our CRC32c implementation as well
as DJB hash for hash table hashing, so meh, let's switch to
it.

6 files changed, 47 insertions, 64 deletions

diff --git a/CMake/FindXXHASH.cmake b/CMake/FindXXHASH.cmake
new file mode 100644
index 000000000..46d6fbd60
--- /dev/null
+++ b/CMake/FindXXHASH.cmake
@@ -0,0 +1,25 @@
+# - Try to find XXHASH
+# Once done, this will define
+#
+#  XXHASH_FOUND - system has XXHASH
+#  XXHASH_INCLUDE_DIRS - the XXHASH include directories
+#  XXHASH_LIBRARIES - the XXHASH library
+find_package(PkgConfig)
+
+pkg_check_modules(XXHASH_PKGCONF libxxhash)
+
+find_path(XXHASH_INCLUDE_DIRS
+  NAMES xxhash.h
+  PATHS ${XXHASH_PKGCONF_INCLUDE_DIRS}
+)
+
+
+find_library(XXHASH_LIBRARIES
+  NAMES xxhash
+  PATHS ${XXHASH_PKGCONF_LIBRARY_DIRS}
+)
+
+include(FindPackageHandleStandardArgs)
+find_package_handle_standard_args(XXHASH DEFAULT_MSG XXHASH_INCLUDE_DIRS XXHASH_LIBRARIES)
+
+mark_as_advanced(XXHASH_INCLUDE_DIRS XXHASH_LIBRARIES)
diff --git a/CMakeLists.txt b/CMakeLists.txt
index e149a4c28..0685ec2f4 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -135,6 +135,7 @@ if (SECCOMP_FOUND)
 endif()
 
 find_package(GCRYPT REQUIRED)
+find_package(XXHASH REQUIRED)
 
 # Mount()ing and stat()ing and friends
 check_symbol_exists(statfs sys/vfs.h HAVE_VFS_H)
diff --git a/apt-pkg/CMakeLists.txt b/apt-pkg/CMakeLists.txt
index 7e51b1775..5c97493af 100644
--- a/apt-pkg/CMakeLists.txt
+++ b/apt-pkg/CMakeLists.txt
@@ -49,6 +49,7 @@ target_include_directories(apt-pkg
                                    $<$<BOOL:${SYSTEMD_FOUND}>:${SYSTEMD_INCLUDE_DIRS}>
                                    ${ICONV_INCLUDE_DIRS}
                                    $<$<BOOL:${GCRYPT_FOUND}>:${GCRYPT_INCLUDE_DIRS}>
+                                   $<$<BOOL:${XXHASH_FOUND}>:${XXHASH_INCLUDE_DIRS}>
 )
 
 target_link_libraries(apt-pkg
@@ -63,6 +64,7 @@ target_link_libraries(apt-pkg
                              $<$<BOOL:${SYSTEMD_FOUND}>:${SYSTEMD_LIBRARIES}>
                              ${ICONV_LIBRARIES}
                              $<$<BOOL:${GCRYPT_FOUND}>:${GCRYPT_LIBRARIES}>
+                             $<$<BOOL:${XXHASH_FOUND}>:${XXHASH_LIBRARIES}>
 )
 set_target_properties(apt-pkg PROPERTIES VERSION ${MAJOR}.${MINOR})
 set_target_properties(apt-pkg PROPERTIES SOVERSION ${MAJOR})
diff --git a/apt-pkg/pkgcache.cc b/apt-pkg/pkgcache.cc
index 64c97811a..458860b0a 100644
--- a/apt-pkg/pkgcache.cc
+++ b/apt-pkg/pkgcache.cc
@@ -31,7 +31,6 @@
 #include <apt-pkg/strutl.h>
 #include <apt-pkg/version.h>
 
-#include <zlib.h>
 #include <algorithm>
 #include <sstream>
 #include <string>
@@ -39,6 +38,7 @@
 #include <stddef.h>
 #include <string.h>
 #include <sys/stat.h>
+#include <xxhash.h>
 
 #include <apti18n.h>
 									/*}}}*/
@@ -213,79 +213,35 @@ map_id_t pkgCache::sHash(StringView Str) const
       Hash = 33 * Hash + tolower_ascii_unsafe(*I);
    return Hash % HeaderP->GetHashTableSize();
 }
-
-#ifdef HAVE_FMV_SSE42_AND_CRC32
-__attribute__((target("sse4.2"))) static uint32_t hash32(uint32_t crc32, const unsigned char *input, size_t size)
-{
-   if (input == nullptr)
-      return 0;
-
-   crc32 ^= 0xffffffffU;
-#ifdef HAVE_FMV_SSE42_AND_CRC32DI
-   while (size >= 8) {
-      crc32 = __builtin_ia32_crc32di(crc32, *(uint64_t *)input);
-      input += 8;
-      size -= 8;
-   }
-
-   if (size >= 4) {
-#else
-   while (size >= 4) {
-#endif
-      crc32 = __builtin_ia32_crc32si(crc32, *(uint32_t *)input);
-      input += 4;
-      size -= 4;
-   }
-
-   if (size >= 2) {
-      crc32 = __builtin_ia32_crc32hi(crc32, *(uint16_t *)input);
-      input += 2;
-      size -= 2;
-   }
-
-   if (size >= 1) {
-      crc32 = __builtin_ia32_crc32qi(crc32, *(uint8_t *)input);
-      input += 1;
-      size -= 1;
-   }
-   crc32 ^= 0xffffffffU;
-   return crc32;
-}
-
-__attribute__((target("default")))
-#endif
-static uint32_t hash32(uint32_t crc32, const unsigned char *input, size_t size)
-{
-   return adler32(crc32, input, size);
-}
-
 uint32_t pkgCache::CacheHash()
 {
    pkgCache::Header header = {};
-   uLong adler = hash32(0L, Z_NULL, 0);
+   XXH3_state_t *state = XXH3_createState();
 
    if (Map.Size() < sizeof(header))
-      return adler;
+      return 0;
+
+   XXH3_64bits_reset(state);
    memcpy(&header, GetMap().Data(), sizeof(header));
 
    header.Dirty = false;
    header.CacheFileSize = 0;
 
-   adler = hash32(adler,
-		  reinterpret_cast<const unsigned char *>(PACKAGE_VERSION),
-		  APT_ARRAY_SIZE(PACKAGE_VERSION));
+   XXH3_64bits_update(state,
+		      reinterpret_cast<const unsigned char *>(PACKAGE_VERSION),
+		      APT_ARRAY_SIZE(PACKAGE_VERSION));
 
-   adler = hash32(adler,
-		  reinterpret_cast<const unsigned char *>(&header),
-		  sizeof(header));
+   XXH3_64bits_update(state,
+		      reinterpret_cast<const unsigned char *>(&header),
+		      sizeof(header));
 
    if (Map.Size() > sizeof(header)) {
-      adler = hash32(adler,
-		     static_cast<const unsigned char *>(GetMap().Data()) + sizeof(header),
-		     GetMap().Size() - sizeof(header));
+      XXH3_64bits_update(state,
+			 static_cast<const unsigned char *>(GetMap().Data()) + sizeof(header),
+			 GetMap().Size() - sizeof(header));
    }
 
-   return adler;
+   return XXH3_64bits_digest(state) & 0xFFFFFFFF;
 }
 									/*}}}*/
 // Cache::FindPkg - Locate a package by name				/*{{{*/
diff --git a/apt-pkg/pkgcachegen.h b/apt-pkg/pkgcachegen.h
index f5b4c80b3..9a88b45e7 100644
--- a/apt-pkg/pkgcachegen.h
+++ b/apt-pkg/pkgcachegen.h
@@ -29,6 +29,8 @@
 #endif
 #include <apt-pkg/string_view.h>
 
+#include <xxhash.h>
+
 class FileFd;
 class pkgSourceList;
 class OpProgress;
@@ -63,11 +65,7 @@ class APT_HIDDEN pkgCacheGenerator					/*{{{*/
    };
    struct hash {
       uint32_t operator()(string_pointer const &that) const {
-	 uint32_t Hash = 5381;
-	 const char * const end = that.data() + that.size;
-	 for (const char *I = that.data(); I != end; ++I)
-	    Hash = 33 * Hash + *I;
-	 return Hash;
+	 return XXH3_64bits(that.data(), that.size) & 0xFFFFFFFF;
       }
    };
 
diff --git a/debian/control b/debian/control
index 0341df538..107f58dcb 100644
--- a/debian/control
+++ b/debian/control
@@ -23,6 +23,7 @@ Build-Depends: cmake (>= 3.4),
                libseccomp-dev (>= 2.4.2) [amd64 arm64 armel armhf i386 mips mips64el mipsel ppc64el s390x hppa powerpc powerpcspe ppc64 x32],
                libsystemd-dev [linux-any],
                libudev-dev [linux-any],
+               libxxhash-dev (>= 0.8),
                libzstd-dev (>= 1.0),
                ninja-build,
                pkg-config,