contrib/llvm/lib/DebugInfo/PDB/Native/Hash.cpp

   1 //===- Hash.cpp - PDB Hash Functions --------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/DebugInfo/PDB/Native/Hash.h"
  11 #include "llvm/ADT/ArrayRef.h"
  12 #include "llvm/Support/Endian.h"
  13 #include "llvm/Support/JamCRC.h"
  14 #include <cstdint>
  15
  16 using namespace llvm;
  17 using namespace llvm::support;
  18
  19 // Corresponds to `Hasher::lhashPbCb` in PDB/include/misc.h.
  20 // Used for name hash table and TPI/IPI hashes.
  21 uint32_t pdb::hashStringV1(StringRef Str) {
  22   uint32_t Result = 0;
  23   uint32_t Size = Str.size();
  24
  25   ArrayRef<ulittle32_t> Longs(reinterpret_cast<const ulittle32_t *>(Str.data()),
  26                               Size / 4);
  27
  28   for (auto Value : Longs)
  29     Result ^= Value;
  30
  31   const uint8_t *Remainder = reinterpret_cast<const uint8_t *>(Longs.end());
  32   uint32_t RemainderSize = Size % 4;
  33
  34   // Maximum of 3 bytes left.  Hash a 2 byte word if possible, then hash the
  35   // possibly remaining 1 byte.
  36   if (RemainderSize >= 2) {
  37     uint16_t Value = *reinterpret_cast<const ulittle16_t *>(Remainder);
  38     Result ^= static_cast<uint32_t>(Value);
  39     Remainder += 2;
  40     RemainderSize -= 2;
  41   }
  42
  43   // hash possible odd byte
  44   if (RemainderSize == 1) {
  45     Result ^= *(Remainder++);
  46   }
  47
  48   const uint32_t toLowerMask = 0x20202020;
  49   Result |= toLowerMask;
  50   Result ^= (Result >> 11);
  51
  52   return Result ^ (Result >> 16);
  53 }
  54
  55 // Corresponds to `HasherV2::HashULONG` in PDB/include/misc.h.
  56 // Used for name hash table.
  57 uint32_t pdb::hashStringV2(StringRef Str) {
  58   uint32_t Hash = 0xb170a1bf;
  59
  60   ArrayRef<char> Buffer(Str.begin(), Str.end());
  61
  62   ArrayRef<ulittle32_t> Items(
  63       reinterpret_cast<const ulittle32_t *>(Buffer.data()),
  64       Buffer.size() / sizeof(ulittle32_t));
  65   for (ulittle32_t Item : Items) {
  66     Hash += Item;
  67     Hash += (Hash << 10);
  68     Hash ^= (Hash >> 6);
  69   }
  70   Buffer = Buffer.slice(Items.size() * sizeof(ulittle32_t));
  71   for (uint8_t Item : Buffer) {
  72     Hash += Item;
  73     Hash += (Hash << 10);
  74     Hash ^= (Hash >> 6);
  75   }
  76
  77   return Hash * 1664525U + 1013904223U;
  78 }
  79
  80 // Corresponds to `SigForPbCb` in langapi/shared/crc32.h.
  81 uint32_t pdb::hashBufferV8(ArrayRef<uint8_t> Buf) {
  82   JamCRC JC(/*Init=*/0U);
  83   JC.update(makeArrayRef<char>(reinterpret_cast<const char *>(Buf.data()),
  84                                Buf.size()));
  85   return JC.getCRC();
  86 }