Tweak SimpleFastHash

[aarongreen]

Summary

This change adds a SimpleFastHash64 variant of SimpleFastHash which allows call sites to specify a starting value and get a 64 bit hash in return. This allows a hash to be "resumed" with more data.

A later patch needs this to be able to hash a sequence of module-relative values one at a time, rather than just a region a memory.

[charco]

Can you explain in the summary / commit message why this is needed? How do you intend to use it?

[aarongreen]

In D94510#2511533, @charco wrote:

Can you explain in the summary / commit message why this is needed? How do you intend to use it?

Done. Basically, we are going to want the hash of a sequence of position-independent / DSO-relative PCs rather than just of the whole PC table in one go.

[morehouse]

compiler-rt/lib/fuzzer/FuzzerUtil.cpp

243

Why do we need uint64_t instead of size_t? Using just one or the other seems simpler.

[aarongreen]

Combined two versions of SimpleFastHash into one.

[morehouse]

compiler-rt/lib/fuzzer/FuzzerUtil.h

93

It seems a little silly to have the same value returned and written to *Hash? WDYT about simplifying to:

uint64_t SimpleFastHash(const void *Data, size_t Size, uint64_t Hash = 0)

[aarongreen]

compiler-rt/lib/fuzzer/FuzzerUtil.h

93

That's fine. I have places in later changes like:

uint64_t Hash = Initial;
for (...)
  SimpleFastHash(..., &Hash);

but I can changes those.

[morehouse]

LGTM

[aarongreen]

See comments on D94512 and D94514. This revision no longer descends from D94508 or D94509 as we no longer need fuzzer::ModuleRelativeValues or the changes to FuzzerFork.cpp.

compiler-rt/lib/fuzzer/FuzzerTracePC.h

 struct MemMemTable {
   static const size_t kSize = kSizeT;
   Word MemMemWords[kSize];
   Word EmptyWord;
 
   void Add(const uint8_t *Data, size_t Size) {
     if (Size <= 2) return;
     Size = std::min(Size, Word::GetMaxSize());
-    size_t Idx = SimpleFastHash(Data, Size) % kSize;
+    auto Idx = SimpleFastHash(Data, Size) % kSize;
     MemMemWords[Idx].Set(Data, Size);
   }
   const Word &Get(size_t Idx) {
     for (size_t i = 0; i < kSize; i++) {
       const Word &W = MemMemWords[(Idx + i) % kSize];
       if (W.size()) return W;
     }
     EmptyWord.Set(nullptr, 0);

compiler-rt/lib/fuzzer/FuzzerUtil.h

 }
 
 void DiscardOutput(int Fd);
 
 std::string DisassembleCmd(const std::string &FileName);
 
 std::string SearchRegexCmd(const std::string &Regex);
 
-size_t SimpleFastHash(const uint8_t *Data, size_t Size);
+uint64_t SimpleFastHash(const void *Data, size_t Size, uint64_t Initial = 0);
 
 inline size_t Log(size_t X) {
   return static_cast<size_t>((sizeof(unsigned long long) * 8) - Clzll(X) - 1);
 }
 
 inline size_t PageSize() { return 4096; }
 inline uint8_t *RoundUpByPage(uint8_t *P) {
   uintptr_t X = reinterpret_cast<uintptr_t>(P);
   size_t Mask = PageSize() - 1;
   X = (X + Mask) & ~Mask;

compiler-rt/lib/fuzzer/FuzzerUtil.cpp

unsigned NumberOfCpuCores() {
   if (!N) {
     Printf("WARNING: std::thread::hardware_concurrency not well defined for "
            "your platform. Assuming CPU count of 1.\n");
     N = 1;
   }
   return N;
 }
 
-size_t SimpleFastHash(const uint8_t *Data, size_t Size) {
-  size_t Res = 0;
+uint64_t SimpleFastHash(const void *Data, size_t Size, uint64_t Initial) {
+  uint64_t Res = Initial;
+  const uint8_t *Bytes = static_cast<const uint8_t *>(Data);
   for (size_t i = 0; i < Size; i++)
-    Res = Res * 11 + Data[i];
+    Res = Res * 11 + Bytes[i];
   return Res;
 }
 
 }  // namespace fuzzer