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 9 #include "llvm/DebugInfo/PDB/Native/Hash.h" 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. hashStringV1(StringRef Str)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. hashStringV2(StringRef Str)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 * 1664525U + 1013904223U; 77 } 78 79 // Corresponds to `SigForPbCb` in langapi/shared/crc32.h. hashBufferV8(ArrayRef<uint8_t> Buf)80uint32_t pdb::hashBufferV8(ArrayRef<uint8_t> Buf) { 81 JamCRC JC(/*Init=*/0U); 82 JC.update(Buf); 83 return JC.getCRC(); 84 } 85