1//===----------------------------------------------------------------------===//
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/Transforms/Utils/KCFIHash.h"
10#include "llvm/Support/Endian.h"
11#include "llvm/Support/ErrorHandling.h"
12
13using namespace llvm;
14using namespace support;
15
16// xxHash64 is a deprecated pre-xxh3 hash, retained here only as the default
17// KCFI type-ID hash for ABI compatibility.
18
19static uint64_t rotl64(uint64_t X, size_t R) {
20 return (X << R) | (X >> (64 - R));
21}
22
23constexpr uint64_t PRIME64_1 = 11400714785074694791ULL;
24constexpr uint64_t PRIME64_2 = 14029467366897019727ULL;
25constexpr uint64_t PRIME64_3 = 1609587929392839161ULL;
26constexpr uint64_t PRIME64_4 = 9650029242287828579ULL;
27constexpr uint64_t PRIME64_5 = 2870177450012600261ULL;
28
29static uint64_t round(uint64_t Acc, uint64_t Input) {
30 Acc += Input * PRIME64_2;
31 Acc = rotl64(X: Acc, R: 31);
32 Acc *= PRIME64_1;
33 return Acc;
34}
35
36static uint64_t mergeRound(uint64_t Acc, uint64_t Val) {
37 Val = round(Acc: 0, Input: Val);
38 Acc ^= Val;
39 Acc = Acc * PRIME64_1 + PRIME64_4;
40 return Acc;
41}
42
43static uint64_t avalanche(uint64_t H) {
44 H ^= H >> 33;
45 H *= PRIME64_2;
46 H ^= H >> 29;
47 H *= PRIME64_3;
48 H ^= H >> 32;
49 return H;
50}
51
52static uint64_t xxHash64(const uint8_t *P, size_t Len) {
53 const uint8_t *const BEnd = P + Len;
54 uint64_t H64;
55
56 if (Len >= 32) {
57 const uint8_t *const Limit = BEnd - 32;
58 uint64_t V1 = PRIME64_1 + PRIME64_2;
59 uint64_t V2 = PRIME64_2;
60 uint64_t V3 = 0;
61 uint64_t V4 = -PRIME64_1;
62
63 do {
64 V1 = round(Acc: V1, Input: endian::read64le(P));
65 P += 8;
66 V2 = round(Acc: V2, Input: endian::read64le(P));
67 P += 8;
68 V3 = round(Acc: V3, Input: endian::read64le(P));
69 P += 8;
70 V4 = round(Acc: V4, Input: endian::read64le(P));
71 P += 8;
72 } while (P <= Limit);
73
74 H64 = rotl64(X: V1, R: 1) + rotl64(X: V2, R: 7) + rotl64(X: V3, R: 12) + rotl64(X: V4, R: 18);
75 H64 = mergeRound(Acc: H64, Val: V1);
76 H64 = mergeRound(Acc: H64, Val: V2);
77 H64 = mergeRound(Acc: H64, Val: V3);
78 H64 = mergeRound(Acc: H64, Val: V4);
79 } else {
80 H64 = PRIME64_5;
81 }
82
83 H64 += (uint64_t)Len;
84
85 while (reinterpret_cast<uintptr_t>(P) + 8 <=
86 reinterpret_cast<uintptr_t>(BEnd)) {
87 H64 ^= round(Acc: 0, Input: endian::read64le(P));
88 H64 = rotl64(X: H64, R: 27) * PRIME64_1 + PRIME64_4;
89 P += 8;
90 }
91
92 if (reinterpret_cast<uintptr_t>(P) + 4 <= reinterpret_cast<uintptr_t>(BEnd)) {
93 H64 ^= (uint64_t)endian::read32le(P) * PRIME64_1;
94 H64 = rotl64(X: H64, R: 23) * PRIME64_2 + PRIME64_3;
95 P += 4;
96 }
97
98 while (P < BEnd) {
99 H64 ^= (*P) * PRIME64_5;
100 H64 = rotl64(X: H64, R: 11) * PRIME64_1;
101 ++P;
102 }
103
104 return avalanche(H: H64);
105}
106
107KCFIHashAlgorithm llvm::parseKCFIHashAlgorithm(StringRef Name) {
108 if (Name == "FNV-1a")
109 return KCFIHashAlgorithm::FNV1a;
110 // Default to xxHash64 for backward compatibility
111 return KCFIHashAlgorithm::xxHash64;
112}
113
114StringRef llvm::stringifyKCFIHashAlgorithm(KCFIHashAlgorithm Algorithm) {
115 switch (Algorithm) {
116 case KCFIHashAlgorithm::xxHash64:
117 return "xxHash64";
118 case KCFIHashAlgorithm::FNV1a:
119 return "FNV-1a";
120 }
121 llvm_unreachable("Unknown KCFI hash algorithm");
122}
123
124uint32_t llvm::getKCFITypeID(StringRef MangledTypeName,
125 KCFIHashAlgorithm Algorithm) {
126 switch (Algorithm) {
127 case KCFIHashAlgorithm::xxHash64:
128 // Use lower 32 bits of xxHash64
129 return static_cast<uint32_t>(
130 xxHash64(P: reinterpret_cast<const uint8_t *>(MangledTypeName.data()),
131 Len: MangledTypeName.size()));
132 case KCFIHashAlgorithm::FNV1a:
133 // FNV-1a hash (32-bit)
134 uint32_t Hash = 2166136261u; // FNV offset basis
135 for (unsigned char C : MangledTypeName) {
136 Hash ^= C;
137 Hash *= 16777619u; // FNV prime
138 }
139 return Hash;
140 }
141 llvm_unreachable("Unknown KCFI hash algorithm");
142}
143