Home | History | Annotate | Line # | Download | only in Native 
      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.
     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 * 1664525U + 1013904223U;
     77 }
     78 
     79 // Corresponds to `SigForPbCb` in langapi/shared/crc32.h.
     80 uint32_t pdb::hashBufferV8(ArrayRef<uint8_t> Buf) {
     81   JamCRC JC(/*Init=*/0U);
     82   JC.update(Buf);
     83   return JC.getCRC();
     84 }
     85