Thrill  0.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
siphash.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * tlx/siphash.hpp
3  *
4  * SipHash Implementations borrowed under Public Domain license from
5  * https://github.com/floodyberry/siphash
6  *
7  * Part of tlx - http://panthema.net/tlx
8  *
9  * Copyright (C) 2017 Timo Bingmann <[email protected]>
10  *
11  * All rights reserved. Published under the Boost Software License, Version 1.0
12  ******************************************************************************/
13 
14 #ifndef TLX_SIPHASH_HEADER
15 #define TLX_SIPHASH_HEADER
16 
18 
19 #include <cstdint>
20 #include <cstdlib>
21 
22 #if defined(_MSC_VER)
23 
24 #include <intrin.h>
25 
26 #define ROTL64(a, b) _rotl64(a, b)
27 
28 #if (_MSC_VER > 1200) || defined(_mm_free)
29 #define __SSE2__
30 #endif
31 
32 #else // !defined(_MSC_VER)
33 
34 #define ROTL64(a, b) (((a) << (b)) | ((a) >> (64 - b)))
35 
36 #endif // !defined(_MSC_VER)
37 
38 #if defined(__SSE2__)
39 #include <emmintrin.h>
40 #endif
41 
42 namespace tlx {
43 
44 static inline
45 uint64_t siphash_plain(const uint8_t key[16], const uint8_t* m, size_t len) {
46 
47  uint64_t v0, v1, v2, v3;
48  uint64_t mi, k0, k1;
49  uint64_t last7;
50  size_t i, blocks;
51 
52  k0 = *reinterpret_cast<const uint64_t*>(key + 0);
53  k1 = *reinterpret_cast<const uint64_t*>(key + 8);
54  v0 = k0 ^ 0x736f6d6570736575ull;
55  v1 = k1 ^ 0x646f72616e646f6dull;
56  v2 = k0 ^ 0x6c7967656e657261ull;
57  v3 = k1 ^ 0x7465646279746573ull;
58 
59  last7 = (uint64_t)(len & 0xff) << 56;
60 
61 #define sipcompress() \
62  v0 += v1; v2 += v3; \
63  v1 = ROTL64(v1, 13); \
64  v3 = ROTL64(v3, 16); \
65  v1 ^= v0; v3 ^= v2; \
66  v0 = ROTL64(v0, 32); \
67  v2 += v1; v0 += v3; \
68  v1 = ROTL64(v1, 17); \
69  v3 = ROTL64(v3, 21); \
70  v1 ^= v2; v3 ^= v0; \
71  v2 = ROTL64(v2, 32);
72 
73  for (i = 0, blocks = (len & ~7); i < blocks; i += 8) {
74  mi = *reinterpret_cast<const uint64_t*>(m + i);
75  v3 ^= mi;
76  sipcompress();
77  sipcompress();
78  v0 ^= mi;
79  }
80 
81  switch (len - blocks) {
82  case 7:
83  last7 |= (uint64_t)m[i + 6] << 48;
85  case 6:
86  last7 |= (uint64_t)m[i + 5] << 40;
88  case 5:
89  last7 |= (uint64_t)m[i + 4] << 32;
91  case 4:
92  last7 |= (uint64_t)m[i + 3] << 24;
94  case 3:
95  last7 |= (uint64_t)m[i + 2] << 16;
97  case 2:
98  last7 |= (uint64_t)m[i + 1] << 8;
100  case 1:
101  last7 |= (uint64_t)m[i + 0];
103  case 0:
104  default:;
105  }
106 
107  v3 ^= last7;
108  sipcompress();
109  sipcompress();
110  v0 ^= last7;
111  v2 ^= 0xff;
112  sipcompress();
113  sipcompress();
114  sipcompress();
115  sipcompress();
116 
117 #undef sipcompress
118 
119  return v0 ^ v1 ^ v2 ^ v3;
120 }
121 
122 /******************************************************************************/
123 // SSE2 vectorization
124 
125 #if defined(__SSE2__)
126 
127 union siphash_packedelem64 {
128  uint64_t u[2];
129  __m128i v;
130 };
131 
132 /* 0,2,1,3 */
133 static const siphash_packedelem64 siphash_init[2] = {
134  {
135  { 0x736f6d6570736575ull, 0x6c7967656e657261ull }
136  },
137  {
138  { 0x646f72616e646f6dull, 0x7465646279746573ull }
139  }
140 };
141 
142 static const siphash_packedelem64 siphash_final = {
143  { 0x0000000000000000ull, 0x00000000000000ffull }
144 };
145 
146 static inline
147 uint64_t siphash_sse2(const uint8_t key[16], const uint8_t* m, size_t len) {
148 
149  __m128i k, v02, v20, v13, v11, v33, mi;
150  uint64_t last7;
151  uint32_t lo, hi;
152  size_t i, blocks;
153 
154  k = _mm_loadu_si128((const __m128i*)(key + 0));
155  v02 = siphash_init[0].v;
156  v13 = siphash_init[1].v;
157  v02 = _mm_xor_si128(v02, _mm_unpacklo_epi64(k, k));
158  v13 = _mm_xor_si128(v13, _mm_unpackhi_epi64(k, k));
159 
160  last7 = (uint64_t)(len & 0xff) << 56;
161 
162 #define sipcompress() \
163  v11 = v13; \
164  v33 = _mm_shuffle_epi32(v13, _MM_SHUFFLE(1, 0, 3, 2)); \
165  v11 = _mm_or_si128(_mm_slli_epi64(v11, 13), _mm_srli_epi64(v11, 64 - 13)); \
166  v02 = _mm_add_epi64(v02, v13); \
167  v33 = _mm_shufflelo_epi16(v33, _MM_SHUFFLE(2, 1, 0, 3)); \
168  v13 = _mm_unpacklo_epi64(v11, v33); \
169  v13 = _mm_xor_si128(v13, v02); \
170  v20 = _mm_shuffle_epi32(v02, _MM_SHUFFLE(0, 1, 3, 2)); \
171  v11 = v13; \
172  v33 = _mm_shuffle_epi32(v13, _MM_SHUFFLE(1, 0, 3, 2)); \
173  v11 = _mm_or_si128(_mm_slli_epi64(v11, 17), _mm_srli_epi64(v11, 64 - 17)); \
174  v20 = _mm_add_epi64(v20, v13); \
175  v33 = _mm_or_si128(_mm_slli_epi64(v33, 21), _mm_srli_epi64(v33, 64 - 21)); \
176  v13 = _mm_unpacklo_epi64(v11, v33); \
177  v02 = _mm_shuffle_epi32(v20, _MM_SHUFFLE(0, 1, 3, 2)); \
178  v13 = _mm_xor_si128(v13, v20);
179 
180  for (i = 0, blocks = (len & ~7); i < blocks; i += 8) {
181  mi = _mm_loadl_epi64((const __m128i*)(m + i));
182  v13 = _mm_xor_si128(v13, _mm_slli_si128(mi, 8));
183  sipcompress();
184  sipcompress();
185  v02 = _mm_xor_si128(v02, mi);
186  }
187 
188  switch (len - blocks) {
189  case 7:
190  last7 |= (uint64_t)m[i + 6] << 48;
192  case 6:
193  last7 |= (uint64_t)m[i + 5] << 40;
195  case 5:
196  last7 |= (uint64_t)m[i + 4] << 32;
198  case 4:
199  last7 |= (uint64_t)m[i + 3] << 24;
201  case 3:
202  last7 |= (uint64_t)m[i + 2] << 16;
204  case 2:
205  last7 |= (uint64_t)m[i + 1] << 8;
207  case 1:
208  last7 |= (uint64_t)m[i + 0];
210  case 0:
211  default:;
212  }
213 
214  mi = _mm_unpacklo_epi32(
215  _mm_cvtsi32_si128((uint32_t)last7), _mm_cvtsi32_si128((uint32_t)(last7 >> 32)));
216  v13 = _mm_xor_si128(v13, _mm_slli_si128(mi, 8));
217  sipcompress();
218  sipcompress();
219  v02 = _mm_xor_si128(v02, mi);
220  v02 = _mm_xor_si128(v02, siphash_final.v);
221  sipcompress();
222  sipcompress();
223  sipcompress();
224  sipcompress();
225 
226  v02 = _mm_xor_si128(v02, v13);
227  v02 = _mm_xor_si128(v02, _mm_shuffle_epi32(v02, _MM_SHUFFLE(1, 0, 3, 2)));
228  lo = _mm_cvtsi128_si32(v02);
229  hi = _mm_cvtsi128_si32(_mm_srli_si128(v02, 4));
230 
231 #undef sipcompress
232 
233  return ((uint64_t)hi << 32) | lo;
234 }
235 
236 #endif // defined(__SSE2__)
237 
238 /******************************************************************************/
239 // Switch between available implementations
240 
241 static inline
242 uint64_t siphash(const uint8_t key[16], const uint8_t* msg, size_t size) {
243 #if defined(__SSE2__)
244  return siphash_sse2(key, msg, size);
245 #else
246  return siphash_plain(key, msg, size);
247 #endif
248 }
249 
250 static inline
251 uint64_t siphash(const uint8_t* msg, size_t size) {
252  const unsigned char key[16] = {
253  0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
254  };
255  return siphash(key, msg, size);
256 }
257 
258 template <typename Type>
259 static inline
260 uint64_t siphash(const Type& value) {
261  return siphash(reinterpret_cast<const uint8_t*>(&value), sizeof(value));
262 }
263 
264 #undef ROTL64
265 
266 } // namespace tlx
267 
268 #endif // !TLX_SIPHASH_HEADER
269 
270 /******************************************************************************/
Type
VFS object type.
Definition: file_io.hpp:52
#define sipcompress()
int value
Definition: gen_data.py:41
static uint64_t siphash(const uint8_t key[16], const uint8_t *msg, size_t size)
Definition: siphash.hpp:242
static uint64_t siphash_plain(const uint8_t key[16], const uint8_t *m, size_t len)
Definition: siphash.hpp:45
#define TLX_ATTRIBUTE_FALLTHROUGH