LLVM 20.0.0git
Hash.cpp
Go to the documentation of this file.
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
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.
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.
57 uint32_t Hash = 0xb170a1bf;
58
59 ArrayRef<char> Buffer(Str.begin(), Str.end());
60
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.
81 JamCRC JC(/*Init=*/0U);
82 JC.update(Buf);
83 return JC.getCRC();
84}
uint64_t Size
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
iterator end() const
Definition: ArrayRef.h:154
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
const T * data() const
Definition: ArrayRef.h:162
ArrayRef< T > slice(size_t N, size_t M) const
slice(n, m) - Chop off the first N elements of the array, and keep M elements in the array.
Definition: ArrayRef.h:195
uint32_t getCRC() const
Definition: CRC.h:52
void update(ArrayRef< uint8_t > Data)
Definition: CRC.cpp:103
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
LLVM Value Representation.
Definition: Value.h:74
uint32_t hashStringV1(StringRef Str)
Definition: Hash.cpp:20
uint32_t hashBufferV8(ArrayRef< uint8_t > Data)
Definition: Hash.cpp:80
uint32_t hashStringV2(StringRef Str)
Definition: Hash.cpp:56
detail::packed_endian_specific_integral< uint32_t, llvm::endianness::little, unaligned > ulittle32_t
Definition: Endian.h:285
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18