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" |
| 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. |
| 20 | uint32_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. |
| 56 | uint32_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 | } |