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
15using namespace llvm;
16using namespace llvm::support;
17
18// Corresponds to `Hasher::lhashPbCb` in PDB/include/misc.h.
19// Used for name hash table and TPI/IPI hashes.
20uint32_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.
56uint32_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.
80uint32_t pdb::hashBufferV8(ArrayRef<uint8_t> Buf) {
81  JamCRC JC(/*Init=*/0U);
82  JC.update(Buf);
83  return JC.getCRC();
84}
85