Rui Ueyama | 170988f | 2016-06-08 23:11:14 +0000 | [diff] [blame] | 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" |
David Majnemer | 1d3dcb0 | 2016-12-18 00:41:15 +0000 | [diff] [blame] | 14 | #include "llvm/Support/JamCRC.h" |
Rui Ueyama | 170988f | 2016-06-08 23:11:14 +0000 | [diff] [blame] | 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. |
Rui Ueyama | f05f360 | 2016-06-08 23:15:09 +0000 | [diff] [blame] | 21 | uint32_t pdb::hashStringV1(StringRef Str) { |
Rui Ueyama | 170988f | 2016-06-08 23:11:14 +0000 | [diff] [blame] | 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. |
Rui Ueyama | f05f360 | 2016-06-08 23:15:09 +0000 | [diff] [blame] | 57 | uint32_t pdb::hashStringV2(StringRef Str) { |
Rui Ueyama | 170988f | 2016-06-08 23:11:14 +0000 | [diff] [blame] | 58 | 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 Majnemer | b7477b5 | 2016-12-18 20:10:50 +0000 | [diff] [blame^] | 77 | return Hash * 1664525U + 1013904223U; |
Rui Ueyama | 170988f | 2016-06-08 23:11:14 +0000 | [diff] [blame] | 78 | } |
Rui Ueyama | 5c7248c | 2016-06-16 13:48:16 +0000 | [diff] [blame] | 79 | |
Rui Ueyama | 5c7248c | 2016-06-16 13:48:16 +0000 | [diff] [blame] | 80 | // Corresponds to `SigForPbCb` in langapi/shared/crc32.h. |
| 81 | uint32_t pdb::hashBufferV8(ArrayRef<uint8_t> Buf) { |
David Majnemer | 1d3dcb0 | 2016-12-18 00:41:15 +0000 | [diff] [blame] | 82 | JamCRC JC(/*Init=*/0U); |
| 83 | JC.update(makeArrayRef<char>(reinterpret_cast<const char *>(Buf.data()), |
| 84 | Buf.size())); |
| 85 | return JC.getCRC(); |
Rui Ueyama | 5c7248c | 2016-06-16 13:48:16 +0000 | [diff] [blame] | 86 | } |