1//===--- SipHash.h - An implementation of SipHash -------------------------===//
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 is a header-only implementation of SipHash. It lacks library
10// dependencies so it can be used from LLVM and compiler-rt.
11//
12//===----------------------------------------------------------------------===//
13
14#include <stddef.h>
15#include <stdint.h>
16
17// Lightly adapted from the SipHash reference C implementation:
18// https://github.com/veorq/SipHash
19// by Jean-Philippe Aumasson and Daniel J. Bernstein
20
21#define ROTL(x, b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b))))
22
23#define U32TO8_LE(p, v) \
24 (p)[0] = (uint8_t)((v)); \
25 (p)[1] = (uint8_t)((v) >> 8); \
26 (p)[2] = (uint8_t)((v) >> 16); \
27 (p)[3] = (uint8_t)((v) >> 24);
28
29#define U64TO8_LE(p, v) \
30 U32TO8_LE((p), (uint32_t)((v))); \
31 U32TO8_LE((p) + 4, (uint32_t)((v) >> 32));
32
33#define U8TO64_LE(p) \
34 (((uint64_t)((p)[0])) | ((uint64_t)((p)[1]) << 8) | \
35 ((uint64_t)((p)[2]) << 16) | ((uint64_t)((p)[3]) << 24) | \
36 ((uint64_t)((p)[4]) << 32) | ((uint64_t)((p)[5]) << 40) | \
37 ((uint64_t)((p)[6]) << 48) | ((uint64_t)((p)[7]) << 56))
38
39#define SIPROUND \
40 do { \
41 v0 += v1; \
42 v1 = ROTL(v1, 13); \
43 v1 ^= v0; \
44 v0 = ROTL(v0, 32); \
45 v2 += v3; \
46 v3 = ROTL(v3, 16); \
47 v3 ^= v2; \
48 v0 += v3; \
49 v3 = ROTL(v3, 21); \
50 v3 ^= v0; \
51 v2 += v1; \
52 v1 = ROTL(v1, 17); \
53 v1 ^= v2; \
54 v2 = ROTL(v2, 32); \
55 } while (0)
56
57namespace {
58
59/// Computes a SipHash value
60///
61/// \param in: pointer to input data (read-only)
62/// \param inlen: input data length in bytes (any size_t value)
63/// \param k: reference to the key data 16-byte array (read-only)
64/// \returns output data, must be 8 or 16 bytes
65///
66template <int cROUNDS, int dROUNDS, size_t outlen>
67void siphash(const unsigned char *in, uint64_t inlen,
68 const unsigned char (&k)[16], unsigned char (&out)[outlen]) {
69
70 const unsigned char *ni = (const unsigned char *)in;
71 const unsigned char *kk = (const unsigned char *)k;
72
73 static_assert(outlen == 8 || outlen == 16, "result should be 8 or 16 bytes");
74
75 uint64_t v0 = UINT64_C(0x736f6d6570736575);
76 uint64_t v1 = UINT64_C(0x646f72616e646f6d);
77 uint64_t v2 = UINT64_C(0x6c7967656e657261);
78 uint64_t v3 = UINT64_C(0x7465646279746573);
79 uint64_t k0 = U8TO64_LE(kk);
80 uint64_t k1 = U8TO64_LE(kk + 8);
81 uint64_t m;
82 int i;
83 const unsigned char *end = ni + inlen - (inlen % sizeof(uint64_t));
84 const int left = inlen & 7;
85 uint64_t b = ((uint64_t)inlen) << 56;
86 v3 ^= k1;
87 v2 ^= k0;
88 v1 ^= k1;
89 v0 ^= k0;
90
91 if (outlen == 16)
92 v1 ^= 0xee;
93
94 for (; ni != end; ni += 8) {
95 m = U8TO64_LE(ni);
96 v3 ^= m;
97
98 for (i = 0; i < cROUNDS; ++i)
99 SIPROUND;
100
101 v0 ^= m;
102 }
103
104 switch (left) {
105 case 7:
106 b |= ((uint64_t)ni[6]) << 48;
107 [[fallthrough]];
108 case 6:
109 b |= ((uint64_t)ni[5]) << 40;
110 [[fallthrough]];
111 case 5:
112 b |= ((uint64_t)ni[4]) << 32;
113 [[fallthrough]];
114 case 4:
115 b |= ((uint64_t)ni[3]) << 24;
116 [[fallthrough]];
117 case 3:
118 b |= ((uint64_t)ni[2]) << 16;
119 [[fallthrough]];
120 case 2:
121 b |= ((uint64_t)ni[1]) << 8;
122 [[fallthrough]];
123 case 1:
124 b |= ((uint64_t)ni[0]);
125 break;
126 case 0:
127 break;
128 }
129
130 v3 ^= b;
131
132 for (i = 0; i < cROUNDS; ++i)
133 SIPROUND;
134
135 v0 ^= b;
136
137 if (outlen == 16)
138 v2 ^= 0xee;
139 else
140 v2 ^= 0xff;
141
142 for (i = 0; i < dROUNDS; ++i)
143 SIPROUND;
144
145 b = v0 ^ v1 ^ v2 ^ v3;
146 U64TO8_LE(out, b);
147
148 if (outlen == 8)
149 return;
150
151 v1 ^= 0xdd;
152
153 for (i = 0; i < dROUNDS; ++i)
154 SIPROUND;
155
156 b = v0 ^ v1 ^ v2 ^ v3;
157 U64TO8_LE(out + 8, b);
158}
159
160} // end anonymous namespace
161