From 1460eebf2abe913df964e031eff081a57f043697 Mon Sep 17 00:00:00 2001
From: Julian Andres Klode <julian.klode@canonical.com>
Date: Sun, 13 Dec 2020 21:07:03 +0100
Subject: 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.
---
 apt-pkg/CMakeLists.txt |  2 ++
 apt-pkg/pkgcache.cc    | 74 ++++++++++----------------------------------------
 apt-pkg/pkgcachegen.h  |  8 ++----
 3 files changed, 20 insertions(+), 64 deletions(-)

(limited to 'apt-pkg')

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;
       }
    };
 
-- 
cgit v1.2.3