Use murmurhash2 instead of fnv.
It is substantially faster by processing 8 bytes at a time.
llvm-svn: 281454
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 @@
};
// 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 @@
// 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 @@
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<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 @@
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 @@
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)