LLVM  6.0.0svn
Hash.cpp
Go to the documentation of this file.
1 //===- 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 
11 #include "llvm/ADT/ArrayRef.h"
12 #include "llvm/Support/Endian.h"
13 #include "llvm/Support/JamCRC.h"
14 #include <cstdint>
15 
16 using namespace llvm;
17 using namespace llvm::support;
18 
19 // Corresponds to `Hasher::lhashPbCb` in PDB/include/misc.h.
20 // Used for name hash table and TPI/IPI hashes.
22  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.
58  uint32_t Hash = 0xb170a1bf;
59 
60  ArrayRef<char> Buffer(Str.begin(), Str.end());
61 
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 
77  return Hash * 1664525U + 1013904223U;
78 }
79 
80 // Corresponds to `SigForPbCb` in langapi/shared/crc32.h.
82  JamCRC JC(/*Init=*/0U);
83  JC.update(makeArrayRef<char>(reinterpret_cast<const char *>(Buf.data()),
84  Buf.size()));
85  return JC.getCRC();
86 }
uint32_t getCRC() const
Definition: JamCRC.h:42
uint32_t hashBufferV8(ArrayRef< uint8_t > Data)
Definition: Hash.cpp:81
uint32_t hashStringV2(StringRef Str)
Definition: Hash.cpp:57
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE size_t size() const
size - Get the string size.
Definition: StringRef.h:138
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE const char * data() const
data - Get a pointer to the start of the string (which may not be null terminated).
Definition: StringRef.h:128
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
uint32_t hashStringV1(StringRef Str)
Definition: Hash.cpp:21
detail::packed_endian_specific_integral< uint32_t, little, unaligned > ulittle32_t
Definition: Endian.h:271
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
const T * data() const
Definition: ArrayRef.h:146
iterator begin() const
Definition: StringRef.h:106
LLVM Value Representation.
Definition: Value.h:73
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
void update(ArrayRef< char > Data)
Definition: JamCRC.cpp:92
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
iterator end() const
Definition: StringRef.h:108