blob: 61188ece2dcb8598daf4e2e7a2cbe8c76681f44c [file] [log] [blame]
Rui Ueyama170988f2016-06-08 23:11:14 +00001//===- 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
Adrian McCarthy6b6b8c42017-01-25 22:38:55 +000010#include "llvm/DebugInfo/PDB/Native/Hash.h"
Rui Ueyama170988f2016-06-08 23:11:14 +000011#include "llvm/ADT/ArrayRef.h"
12#include "llvm/Support/Endian.h"
David Majnemer1d3dcb02016-12-18 00:41:15 +000013#include "llvm/Support/JamCRC.h"
Eugene Zelenko4fcfc192017-06-30 23:06:03 +000014#include <cstdint>
Rui Ueyama170988f2016-06-08 23:11:14 +000015
16using namespace llvm;
17using namespace llvm::support;
18
19// Corresponds to `Hasher::lhashPbCb` in PDB/include/misc.h.
20// Used for name hash table and TPI/IPI hashes.
Rui Ueyamaf05f3602016-06-08 23:15:09 +000021uint32_t pdb::hashStringV1(StringRef Str) {
Rui Ueyama170988f2016-06-08 23:11:14 +000022 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.
Rui Ueyamaf05f3602016-06-08 23:15:09 +000057uint32_t pdb::hashStringV2(StringRef Str) {
Rui Ueyama170988f2016-06-08 23:11:14 +000058 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
David Majnemerb7477b52016-12-18 20:10:50 +000077 return Hash * 1664525U + 1013904223U;
Rui Ueyama170988f2016-06-08 23:11:14 +000078}
Rui Ueyama5c7248c2016-06-16 13:48:16 +000079
Rui Ueyama5c7248c2016-06-16 13:48:16 +000080// Corresponds to `SigForPbCb` in langapi/shared/crc32.h.
81uint32_t pdb::hashBufferV8(ArrayRef<uint8_t> Buf) {
David Majnemer1d3dcb02016-12-18 00:41:15 +000082 JamCRC JC(/*Init=*/0U);
83 JC.update(makeArrayRef<char>(reinterpret_cast<const char *>(Buf.data()),
84 Buf.size()));
85 return JC.getCRC();
Rui Ueyama5c7248c2016-06-16 13:48:16 +000086}