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
10#include "llvm/DebugInfo/PDB/Raw/Hash.h"
11
12#include "llvm/ADT/ArrayRef.h"
13#include "llvm/Support/Endian.h"
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 * 1664525L + 1013904223L;
77}
78
79static const uint32_t V8HashTable[] = {
80    0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA, 0x076DC419, 0x706AF48F,
81    0xE963A535, 0x9E6495A3, 0x0EDB8832, 0x79DCB8A4, 0xE0D5E91E, 0x97D2D988,
82    0x09B64C2B, 0x7EB17CBD, 0xE7B82D07, 0x90BF1D91, 0x1DB71064, 0x6AB020F2,
83    0xF3B97148, 0x84BE41DE, 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7,
84    0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F, 0x63066CD9,
85    0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E, 0xD56041E4, 0xA2677172,
86    0x3C03E4D1, 0x4B04D447, 0xD20D85FD, 0xA50AB56B, 0x35B5A8FA, 0x42B2986C,
87    0xDBBBC9D6, 0xACBCF940, 0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59,
88    0x26D930AC, 0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423,
89    0xCFBA9599, 0xB8BDA50F, 0x2802B89E, 0x5F058808, 0xC60CD9B2, 0xB10BE924,
90    0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D, 0x76DC4190, 0x01DB7106,
91    0x98D220BC, 0xEFD5102A, 0x71B18589, 0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433,
92    0x7807C9A2, 0x0F00F934, 0x9609A88E, 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D,
93    0x91646C97, 0xE6635C01, 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E,
94    0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6, 0x12B7E950,
95    0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49, 0x8CD37CF3, 0xFBD44C65,
96    0x4DB26158, 0x3AB551CE, 0xA3BC0074, 0xD4BB30E2, 0x4ADFA541, 0x3DD895D7,
97    0xA4D1C46D, 0xD3D6F4FB, 0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0,
98    0x44042D73, 0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9, 0x5005713C, 0x270241AA,
99    0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409, 0xCE61E49F,
100    0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4, 0x59B33D17, 0x2EB40D81,
101    0xB7BD5C3B, 0xC0BA6CAD, 0xEDB88320, 0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A,
102    0xEAD54739, 0x9DD277AF, 0x04DB2615, 0x73DC1683, 0xE3630B12, 0x94643B84,
103    0x0D6D6A3E, 0x7A6A5AA8, 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1,
104    0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D, 0x806567CB,
105    0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0, 0x10DA7A5A, 0x67DD4ACC,
106    0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43, 0x60B08ED5, 0xD6D6A3E8, 0xA1D1937E,
107    0x38D8C2C4, 0x4FDFF252, 0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B,
108    0xD80D2BDA, 0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55,
109    0x316E8EEF, 0x4669BE79, 0xCB61B38C, 0xBC66831A, 0x256FD2A0, 0x5268E236,
110    0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F, 0xC5BA3BBE, 0xB2BD0B28,
111    0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7, 0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D,
112    0x9B64C2B0, 0xEC63F226, 0x756AA39C, 0x026D930A, 0x9C0906A9, 0xEB0E363F,
113    0x72076785, 0x05005713, 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38,
114    0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4, 0xF1D4E242,
115    0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B, 0x6FB077E1, 0x18B74777,
116    0x88085AE6, 0xFF0F6A70, 0x66063BCA, 0x11010B5C, 0x8F659EFF, 0xF862AE69,
117    0x616BFFD3, 0x166CCF45, 0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2,
118    0xA7672661, 0xD06016F7, 0x4969474D, 0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC,
119    0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F, 0x30B5FFE9,
120    0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6, 0xBAD03605, 0xCDD70693,
121    0x54DE5729, 0x23D967BF, 0xB3667A2E, 0xC4614AB8, 0x5D681B02, 0x2A6F2B94,
122    0xB40BBE37, 0xC30C8EA1, 0x5A05DF1B, 0x2D02EF8D,
123};
124
125// Corresponds to `SigForPbCb` in langapi/shared/crc32.h.
126uint32_t pdb::hashBufferV8(ArrayRef<uint8_t> Buf) {
127  uint32_t Hash = 0;
128  for (uint8_t Byte : Buf)
129    Hash = (Hash >> 8) ^ V8HashTable[(Hash & 0xff) ^ Byte];
130  return Hash;
131}
132