LLVM 20.0.0git
SipHash.cpp
Go to the documentation of this file.
1//===--- SipHash.cpp - An ABI-stable string hash --------------------------===//
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// This file implements an ABI-stable string hash based on SipHash, used to
10// compute ptrauth discriminators.
11//
12//===----------------------------------------------------------------------===//
13
15#include "llvm/ADT/ArrayRef.h"
17#include "llvm/ADT/StringRef.h"
19#include "llvm/Support/Debug.h"
20#include "llvm/Support/Endian.h"
21#include <cstdint>
22
23using namespace llvm;
24using namespace support;
25
26#define DEBUG_TYPE "llvm-siphash"
27
28// Lightly adapted from the SipHash reference C implementation:
29// https://github.com/veorq/SipHash
30// by Jean-Philippe Aumasson and Daniel J. Bernstein
31
32#define ROTL(x, b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b))))
33
34#define SIPROUND \
35 do { \
36 v0 += v1; \
37 v1 = ROTL(v1, 13); \
38 v1 ^= v0; \
39 v0 = ROTL(v0, 32); \
40 v2 += v3; \
41 v3 = ROTL(v3, 16); \
42 v3 ^= v2; \
43 v0 += v3; \
44 v3 = ROTL(v3, 21); \
45 v3 ^= v0; \
46 v2 += v1; \
47 v1 = ROTL(v1, 17); \
48 v1 ^= v2; \
49 v2 = ROTL(v2, 32); \
50 } while (0)
51
52namespace {
53
54/// Computes a SipHash value
55///
56/// \param in: pointer to input data (read-only)
57/// \param inlen: input data length in bytes (any size_t value)
58/// \param k: reference to the key data 16-byte array (read-only)
59/// \returns output data, must be 8 or 16 bytes
60///
61template <int cROUNDS, int dROUNDS, size_t outlen>
62void siphash(const unsigned char *in, uint64_t inlen,
63 const unsigned char (&k)[16], unsigned char (&out)[outlen]) {
64
65 const unsigned char *ni = (const unsigned char *)in;
66 const unsigned char *kk = (const unsigned char *)k;
67
68 static_assert(outlen == 8 || outlen == 16, "result should be 8 or 16 bytes");
69
70 uint64_t v0 = UINT64_C(0x736f6d6570736575);
71 uint64_t v1 = UINT64_C(0x646f72616e646f6d);
72 uint64_t v2 = UINT64_C(0x6c7967656e657261);
73 uint64_t v3 = UINT64_C(0x7465646279746573);
75 uint64_t k1 = endian::read64le(kk + 8);
76 uint64_t m;
77 int i;
78 const unsigned char *end = ni + inlen - (inlen % sizeof(uint64_t));
79 const int left = inlen & 7;
80 uint64_t b = ((uint64_t)inlen) << 56;
81 v3 ^= k1;
82 v2 ^= k0;
83 v1 ^= k1;
84 v0 ^= k0;
85
86 if (outlen == 16)
87 v1 ^= 0xee;
88
89 for (; ni != end; ni += 8) {
90 m = endian::read64le(ni);
91 v3 ^= m;
92
93 for (i = 0; i < cROUNDS; ++i)
95
96 v0 ^= m;
97 }
98
99 switch (left) {
100 case 7:
101 b |= ((uint64_t)ni[6]) << 48;
103 case 6:
104 b |= ((uint64_t)ni[5]) << 40;
106 case 5:
107 b |= ((uint64_t)ni[4]) << 32;
109 case 4:
110 b |= ((uint64_t)ni[3]) << 24;
112 case 3:
113 b |= ((uint64_t)ni[2]) << 16;
115 case 2:
116 b |= ((uint64_t)ni[1]) << 8;
118 case 1:
119 b |= ((uint64_t)ni[0]);
120 break;
121 case 0:
122 break;
123 }
124
125 v3 ^= b;
126
127 for (i = 0; i < cROUNDS; ++i)
128 SIPROUND;
129
130 v0 ^= b;
131
132 if (outlen == 16)
133 v2 ^= 0xee;
134 else
135 v2 ^= 0xff;
136
137 for (i = 0; i < dROUNDS; ++i)
138 SIPROUND;
139
140 b = v0 ^ v1 ^ v2 ^ v3;
141 endian::write64le(out, b);
142
143 if (outlen == 8)
144 return;
145
146 v1 ^= 0xdd;
147
148 for (i = 0; i < dROUNDS; ++i)
149 SIPROUND;
150
151 b = v0 ^ v1 ^ v2 ^ v3;
152 endian::write64le(out + 8, b);
153}
154
155} // end anonymous namespace
156
157void llvm::getSipHash_2_4_64(ArrayRef<uint8_t> In, const uint8_t (&K)[16],
158 uint8_t (&Out)[8]) {
159 siphash<2, 4>(In.data(), In.size(), K, Out);
160}
161
162void llvm::getSipHash_2_4_128(ArrayRef<uint8_t> In, const uint8_t (&K)[16],
163 uint8_t (&Out)[16]) {
164 siphash<2, 4>(In.data(), In.size(), K, Out);
165}
166
167/// Compute an ABI-stable 16-bit hash of the given string.
169 static const uint8_t K[16] = {0xb5, 0xd4, 0xc9, 0xeb, 0x79, 0x10, 0x4a, 0x79,
170 0x6f, 0xec, 0x8b, 0x1b, 0x42, 0x87, 0x81, 0xd4};
171
172 uint8_t RawHashBytes[8];
173 getSipHash_2_4_64(arrayRefFromStringRef(Str), K, RawHashBytes);
174 uint64_t RawHash = endian::read64le(RawHashBytes);
175
176 // Produce a non-zero 16-bit discriminator.
177 uint16_t Discriminator = (RawHash % 0xFFFF) + 1;
179 dbgs() << "ptrauth stable hash discriminator: " << utostr(Discriminator)
180 << " (0x"
181 << utohexstr(Discriminator, /*Lowercase=*/false, /*Width=*/4)
182 << ")"
183 << " of: " << Str << "\n");
184 return Discriminator;
185}
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:309
#define LLVM_DEBUG(X)
Definition: Debug.h:101
#define SIPROUND
Definition: SipHash.cpp:34
This file contains some functions that are useful when dealing with strings.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
uint64_t read64le(const void *P)
Definition: Endian.h:428
void write64le(void *P, uint64_t V)
Definition: Endian.h:471
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void getSipHash_2_4_64(ArrayRef< uint8_t > In, const uint8_t(&K)[16], uint8_t(&Out)[8])
Computes a SipHash-2-4 64-bit result.
Definition: SipHash.cpp:157
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
uint16_t getPointerAuthStableSipHash(StringRef S)
Compute a stable non-zero 16-bit hash of the given string.
Definition: SipHash.cpp:168
void getSipHash_2_4_128(ArrayRef< uint8_t > In, const uint8_t(&K)[16], uint8_t(&Out)[16])
Computes a SipHash-2-4 128-bit result.
Definition: SipHash.cpp:162