LLVM  14.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 
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.
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 }
llvm::Check::Size
@ Size
Definition: FileCheck.h:73
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::pdb::hashStringV2
uint32_t hashStringV2(StringRef Str)
Definition: Hash.cpp:56
llvm::JamCRC::update
void update(ArrayRef< uint8_t > Data)
Definition: CRC.cpp:103
llvm::support::detail::packed_endian_specific_integral
Definition: Endian.h:206
llvm::JamCRC
Definition: CRC.h:45
llvm::ArrayRef::data
const T * data() const
Definition: ArrayRef.h:162
CRC.h
llvm::ArrayRef::slice
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
llvm::support::ulittle32_t
detail::packed_endian_specific_integral< uint32_t, little, unaligned > ulittle32_t
Definition: Endian.h:272
ArrayRef.h
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
uint32_t
uint16_t
llvm::JamCRC::getCRC
uint32_t getCRC() const
Definition: CRC.h:52
llvm::support
Definition: Endian.h:25
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::pdb::hashBufferV8
uint32_t hashBufferV8(ArrayRef< uint8_t > Data)
Definition: Hash.cpp:80
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
Hash.h
Endian.h
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
llvm::pdb::hashStringV1
uint32_t hashStringV1(StringRef Str)
Definition: Hash.cpp:20