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 } 78 79 static 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. 126 uint32_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
