From d88d7166a80060ff3bbd4acc598abd1495765413 Mon Sep 17 00:00:00 2001
From: Rafael Espindola <rafael.espindola@gmail.com>
Date: Wed, 14 Sep 2016 11:32:57 +0000
Subject: [PATCH] Use murmurhash2 instead of fnv.

It is substantially faster by processing 8 bytes at a time.

llvm-svn: 281454
---
 lld/ELF/Config.h           |  2 +-
 lld/ELF/Driver.cpp         |  2 +-
 lld/ELF/OutputSections.cpp | 65 ++++++++++++++++++++++++++++++++++++++--------
 lld/ELF/OutputSections.h   |  5 ++--
 lld/ELF/Writer.cpp         |  4 +--
 5 files changed, 61 insertions(+), 17 deletions(-)

diff --git a/lld/ELF/Config.h b/lld/ELF/Config.h
index 410d910..b182b77 100644
--- a/lld/ELF/Config.h
+++ b/lld/ELF/Config.h
@@ -31,7 +31,7 @@ enum ELFKind {
 };
 
 // For --build-id.
-enum class BuildIdKind { None, Fnv1, Md5, Sha1, Hexstring, Uuid };
+enum class BuildIdKind { None, Fast, Md5, Sha1, Hexstring, Uuid };
 
 // For --discard-{all,locals,none}.
 enum class DiscardPolicy { Default, All, Locals, None };
diff --git a/lld/ELF/Driver.cpp b/lld/ELF/Driver.cpp
index a741b67..8f5f543c 100644
--- a/lld/ELF/Driver.cpp
+++ b/lld/ELF/Driver.cpp
@@ -472,7 +472,7 @@ void LinkerDriver::readConfigs(opt::InputArgList &Args) {
 
   // Parse --build-id or --build-id=<style>.
   if (Args.hasArg(OPT_build_id))
-    Config->BuildId = BuildIdKind::Fnv1;
+    Config->BuildId = BuildIdKind::Fast;
   if (auto *Arg = Args.getLastArg(OPT_build_id_eq)) {
     StringRef S = Arg->getValue();
     if (S == "md5") {
diff --git a/lld/ELF/OutputSections.cpp b/lld/ELF/OutputSections.cpp
index 43db5c4..14709ea 100644
--- a/lld/ELF/OutputSections.cpp
+++ b/lld/ELF/OutputSections.cpp
@@ -1691,16 +1691,59 @@ template <class ELFT> void BuildIdSection<ELFT>::writeTo(uint8_t *Buf) {
   HashBuf = Buf + 16;
 }
 
+static uint64_t murmurHash64A(const void *Key, int Len) {
+  uint64_t Seed = 0;
+  const uint64_t M = 0xc6a4a7935bd1e995LLU;
+  const int R = 47;
+
+  uint64_t H = Seed ^ (Len * M);
+
+  const uint64_t *Data = (const uint64_t *)Key;
+  const uint64_t *End = Data + (Len / 8);
+
+  while (Data != End) {
+    uint64_t K = *Data++;
+
+    K *= M;
+    K ^= K >> R;
+    K *= M;
+
+    H ^= K;
+    H *= M;
+  }
+
+  const unsigned char *Data2 = (const unsigned char *)Data;
+  switch (Len & 7) {
+  case 7:
+    H ^= uint64_t(Data2[6]) << 48;
+  case 6:
+    H ^= uint64_t(Data2[5]) << 40;
+  case 5:
+    H ^= uint64_t(Data2[4]) << 32;
+  case 4:
+    H ^= uint64_t(Data2[3]) << 24;
+  case 3:
+    H ^= uint64_t(Data2[2]) << 16;
+  case 2:
+    H ^= uint64_t(Data2[1]) << 8;
+  case 1:
+    H ^= uint64_t(Data2[0]);
+    H *= M;
+  };
+
+  H ^= H >> R;
+  H *= M;
+  H ^= H >> R;
+
+  return H;
+}
+
 template <class ELFT>
-void BuildIdFnv1<ELFT>::writeBuildId(ArrayRef<uint8_t> Buf) {
+void BuildIdFastHash<ELFT>::writeBuildId(ArrayRef<uint8_t> Buf) {
   const endianness E = ELFT::TargetEndianness;
 
-  // 64-bit FNV-1 hash
-  uint64_t Hash = 0xcbf29ce484222325;
-  for (uint8_t B : Buf) {
-    Hash *= 0x100000001b3;
-    Hash ^= B;
-  }
+  // 64-bit murmur2 hash
+  uint64_t Hash = murmurHash64A(Buf.data(), Buf.size());
   write64<E>(this->HashBuf, Hash);
 }
 
@@ -2038,10 +2081,10 @@ template class BuildIdSection<ELF32BE>;
 template class BuildIdSection<ELF64LE>;
 template class BuildIdSection<ELF64BE>;
 
-template class BuildIdFnv1<ELF32LE>;
-template class BuildIdFnv1<ELF32BE>;
-template class BuildIdFnv1<ELF64LE>;
-template class BuildIdFnv1<ELF64BE>;
+template class BuildIdFastHash<ELF32LE>;
+template class BuildIdFastHash<ELF32BE>;
+template class BuildIdFastHash<ELF64LE>;
+template class BuildIdFastHash<ELF64BE>;
 
 template class BuildIdMd5<ELF32LE>;
 template class BuildIdMd5<ELF32BE>;
diff --git a/lld/ELF/OutputSections.h b/lld/ELF/OutputSections.h
index e1634ee..bf799e2 100644
--- a/lld/ELF/OutputSections.h
+++ b/lld/ELF/OutputSections.h
@@ -711,9 +711,10 @@ protected:
   uint8_t *HashBuf = nullptr;
 };
 
-template <class ELFT> class BuildIdFnv1 final : public BuildIdSection<ELFT> {
+template <class ELFT>
+class BuildIdFastHash final : public BuildIdSection<ELFT> {
 public:
-  BuildIdFnv1() : BuildIdSection<ELFT>(8) {}
+  BuildIdFastHash() : BuildIdSection<ELFT>(8) {}
   void writeBuildId(ArrayRef<uint8_t> Buf) override;
 };
 
diff --git a/lld/ELF/Writer.cpp b/lld/ELF/Writer.cpp
index a73286a..c728a73 100644
--- a/lld/ELF/Writer.cpp
+++ b/lld/ELF/Writer.cpp
@@ -150,8 +150,8 @@ template <class ELFT> void elf::writeResult() {
   if (needsInterpSection<ELFT>())
     Interp.reset(new InterpSection<ELFT>);
 
-  if (Config->BuildId == BuildIdKind::Fnv1)
-    BuildId.reset(new BuildIdFnv1<ELFT>);
+  if (Config->BuildId == BuildIdKind::Fast)
+    BuildId.reset(new BuildIdFastHash<ELFT>);
   else if (Config->BuildId == BuildIdKind::Md5)
     BuildId.reset(new BuildIdMd5<ELFT>);
   else if (Config->BuildId == BuildIdKind::Sha1)
-- 
2.7.4