lib/DebugInfo/PDB/Native/Hash.cpp

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