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 #include <tlx/math/bswap_le.hpp>
19 #include <tlx/math/rol.hpp>
20 
21 #include <cstdint>
22 #include <cstdlib>
23 
24 #if defined(_MSC_VER)
25 
26 #include <intrin.h>
27 
28 #if (_MSC_VER > 1200) || defined(_mm_free)
29 #define __SSE2__
30 #endif
31 
32 #endif // !defined(_MSC_VER)
33 
34 #if defined(__SSE2__)
35 #include <emmintrin.h>
36 #endif
37 
38 namespace tlx {
39 
40 static inline
41 uint64_t siphash_plain(const uint8_t key[16], const uint8_t* m, size_t len) {
42 
43  uint64_t v0, v1, v2, v3;
44  uint64_t mi, k0, k1;
45  uint64_t last7;
46  size_t i, blocks;
47 
48  k0 = bswap64_le(*reinterpret_cast<const uint64_t*>(key + 0));
49  k1 = bswap64_le(*reinterpret_cast<const uint64_t*>(key + 8));
50  v0 = k0 ^ 0x736f6d6570736575ull;
51  v1 = k1 ^ 0x646f72616e646f6dull;
52  v2 = k0 ^ 0x6c7967656e657261ull;
53  v3 = k1 ^ 0x7465646279746573ull;
54 
55  last7 = static_cast<uint64_t>(len & 0xff) << 56;
56 
57 #define TLX_SIPCOMPRESS() \
58  v0 += v1; v2 += v3; \
59  v1 = rol64(v1, 13); \
60  v3 = rol64(v3, 16); \
61  v1 ^= v0; v3 ^= v2; \
62  v0 = rol64(v0, 32); \
63  v2 += v1; v0 += v3; \
64  v1 = rol64(v1, 17); \
65  v3 = rol64(v3, 21); \
66  v1 ^= v2; v3 ^= v0; \
67  v2 = rol64(v2, 32);
68 
69  for (i = 0, blocks = (len & ~7); i < blocks; i += 8) {
70  mi = bswap64_le(*reinterpret_cast<const uint64_t*>(m + i));
71  v3 ^= mi;
74  v0 ^= mi;
75  }
76 
77  switch (len - blocks) {
78  case 7:
79  last7 |= static_cast<uint64_t>(m[i + 6]) << 48;
81  case 6:
82  last7 |= static_cast<uint64_t>(m[i + 5]) << 40;
84  case 5:
85  last7 |= static_cast<uint64_t>(m[i + 4]) << 32;
87  case 4:
88  last7 |= static_cast<uint64_t>(m[i + 3]) << 24;
90  case 3:
91  last7 |= static_cast<uint64_t>(m[i + 2]) << 16;
93  case 2:
94  last7 |= static_cast<uint64_t>(m[i + 1]) << 8;
96  case 1:
97  last7 |= static_cast<uint64_t>(m[i + 0]);
99  case 0:
100  default:;
101  }
102 
103  v3 ^= last7;
104  TLX_SIPCOMPRESS();
105  TLX_SIPCOMPRESS();
106  v0 ^= last7;
107  v2 ^= 0xff;
108  TLX_SIPCOMPRESS();
109  TLX_SIPCOMPRESS();
110  TLX_SIPCOMPRESS();
111  TLX_SIPCOMPRESS();
112 
113 #undef TLX_SIPCOMPRESS
114 
115  return v0 ^ v1 ^ v2 ^ v3;
116 }
117 
118 /******************************************************************************/
119 // SSE2 vectorization
120 
121 #if defined(__SSE2__)
122 
123 union siphash_packedelem64 {
124  uint64_t u[2];
125  __m128i v;
126 };
127 
128 /* 0,2,1,3 */
129 static const siphash_packedelem64 siphash_init[2] = {
130  {
131  { 0x736f6d6570736575ull, 0x6c7967656e657261ull }
132  },
133  {
134  { 0x646f72616e646f6dull, 0x7465646279746573ull }
135  }
136 };
137 
138 static const siphash_packedelem64 siphash_final = {
139  { 0x0000000000000000ull, 0x00000000000000ffull }
140 };
141 
142 static inline
143 uint64_t siphash_sse2(const uint8_t key[16], const uint8_t* m, size_t len) {
144 
145  __m128i k, v02, v20, v13, v11, v33, mi;
146  uint64_t last7;
147  uint32_t lo, hi;
148  size_t i, blocks;
149 
150  k = _mm_loadu_si128(reinterpret_cast<const __m128i*>(key + 0));
151  v02 = siphash_init[0].v;
152  v13 = siphash_init[1].v;
153  v02 = _mm_xor_si128(v02, _mm_unpacklo_epi64(k, k));
154  v13 = _mm_xor_si128(v13, _mm_unpackhi_epi64(k, k));
155 
156  last7 = static_cast<uint64_t>(len & 0xff) << 56;
157 
158 #define TLX_SIPCOMPRESS() \
159  v11 = v13; \
160  v33 = _mm_shuffle_epi32(v13, _MM_SHUFFLE(1, 0, 3, 2)); \
161  v11 = _mm_or_si128(_mm_slli_epi64(v11, 13), _mm_srli_epi64(v11, 64 - 13)); \
162  v02 = _mm_add_epi64(v02, v13); \
163  v33 = _mm_shufflelo_epi16(v33, _MM_SHUFFLE(2, 1, 0, 3)); \
164  v13 = _mm_unpacklo_epi64(v11, v33); \
165  v13 = _mm_xor_si128(v13, v02); \
166  v20 = _mm_shuffle_epi32(v02, _MM_SHUFFLE(0, 1, 3, 2)); \
167  v11 = v13; \
168  v33 = _mm_shuffle_epi32(v13, _MM_SHUFFLE(1, 0, 3, 2)); \
169  v11 = _mm_or_si128(_mm_slli_epi64(v11, 17), _mm_srli_epi64(v11, 64 - 17)); \
170  v20 = _mm_add_epi64(v20, v13); \
171  v33 = _mm_or_si128(_mm_slli_epi64(v33, 21), _mm_srli_epi64(v33, 64 - 21)); \
172  v13 = _mm_unpacklo_epi64(v11, v33); \
173  v02 = _mm_shuffle_epi32(v20, _MM_SHUFFLE(0, 1, 3, 2)); \
174  v13 = _mm_xor_si128(v13, v20);
175 
176  for (i = 0, blocks = (len & ~7); i < blocks; i += 8) {
177  mi = _mm_loadl_epi64(reinterpret_cast<const __m128i*>(m + i));
178  v13 = _mm_xor_si128(v13, _mm_slli_si128(mi, 8));
179  TLX_SIPCOMPRESS();
180  TLX_SIPCOMPRESS();
181  v02 = _mm_xor_si128(v02, mi);
182  }
183 
184  switch (len - blocks) {
185  case 7:
186  last7 |= static_cast<uint64_t>(m[i + 6]) << 48;
188  case 6:
189  last7 |= static_cast<uint64_t>(m[i + 5]) << 40;
191  case 5:
192  last7 |= static_cast<uint64_t>(m[i + 4]) << 32;
194  case 4:
195  last7 |= static_cast<uint64_t>(m[i + 3]) << 24;
197  case 3:
198  last7 |= static_cast<uint64_t>(m[i + 2]) << 16;
200  case 2:
201  last7 |= static_cast<uint64_t>(m[i + 1]) << 8;
203  case 1:
204  last7 |= static_cast<uint64_t>(m[i + 0]);
206  case 0:
207  default:;
208  }
209 
210  mi = _mm_unpacklo_epi32(
211  _mm_cvtsi32_si128(static_cast<uint32_t>(last7)),
212  _mm_cvtsi32_si128(static_cast<uint32_t>(last7 >> 32)));
213  v13 = _mm_xor_si128(v13, _mm_slli_si128(mi, 8));
214  TLX_SIPCOMPRESS();
215  TLX_SIPCOMPRESS();
216  v02 = _mm_xor_si128(v02, mi);
217  v02 = _mm_xor_si128(v02, siphash_final.v);
218  TLX_SIPCOMPRESS();
219  TLX_SIPCOMPRESS();
220  TLX_SIPCOMPRESS();
221  TLX_SIPCOMPRESS();
222 
223  v02 = _mm_xor_si128(v02, v13);
224  v02 = _mm_xor_si128(v02, _mm_shuffle_epi32(v02, _MM_SHUFFLE(1, 0, 3, 2)));
225  lo = _mm_cvtsi128_si32(v02);
226  hi = _mm_cvtsi128_si32(_mm_srli_si128(v02, 4));
227 
228 #undef TLX_SIPCOMPRESS
229 
230  return (static_cast<uint64_t>(hi) << 32) | lo;
231 }
232 
233 #endif // defined(__SSE2__)
234 
235 /******************************************************************************/
236 // Switch between available implementations
237 
238 static inline
239 uint64_t siphash(const uint8_t key[16], const uint8_t* msg, size_t size) {
240 #if defined(__SSE2__)
241  return siphash_sse2(key, msg, size);
242 #else
243  return siphash_plain(key, msg, size);
244 #endif
245 }
246 
247 static inline
248 uint64_t siphash(const uint8_t* msg, size_t size) {
249  const unsigned char key[16] = {
250  0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
251  };
252  return siphash(key, msg, size);
253 }
254 
255 template <typename Type>
256 static inline
257 uint64_t siphash(const Type& value) {
258  return siphash(reinterpret_cast<const uint8_t*>(&value), sizeof(value));
259 }
260 
261 #undef rol64
262 
263 } // namespace tlx
264 
265 #endif // !TLX_SIPHASH_HEADER
266 
267 /******************************************************************************/
uint64_t ull() const
return the number as an uint64_t (unsigned long long)
Definition: uint_types.hpp:128
Type
VFS object type.
Definition: file_io.hpp:52
#define TLX_ATTRIBUTE_FALLTHROUGH
#define TLX_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:239
static uint64_t siphash_plain(const uint8_t key[16], const uint8_t *m, size_t len)
Definition: siphash.hpp:41