GCS  0.2.3
gu_spooky.h
1 // Copyright (C) 2012 Codership Oy <info@codership.com>
2 
13 #ifndef _gu_spooky_h_
14 #define _gu_spooky_h_
15 
16 #include "gu_types.h"
17 #include "gu_byteswap.h"
18 
19 #ifdef __cplusplus
20 extern "C" {
21 #endif
22 
23 #include <string.h> // for memcpy()
24 
26 #define _spooky_numVars 12
27 #define _spooky_blockSize 96 /* (_spooky_numVars * 8) */
28 #define _spooky_bufSize 192 /* (_spooky_blockSize * 2) */
29 static uint64_t const _spooky_const = GU_ULONG_LONG(0xDEADBEEFDEADBEEF);
30 
31 //
32 // This is used if the input is 96 bytes long or longer.
33 //
34 // The internal state is fully overwritten every 96 bytes.
35 // Every input bit appears to cause at least 128 bits of entropy
36 // before 96 other bytes are combined, when run forward or backward
37 // For every input bit,
38 // Two inputs differing in just that input bit
39 // Where "differ" means xor or subtraction
40 // And the base value is random
41 // When run forward or backwards one Mix
42 // I tried 3 pairs of each; they all differed by at least 212 bits.
43 //
44 static GU_FORCE_INLINE void _spooky_mix(
45  const uint64_t *data,
46  uint64_t* s0, uint64_t* s1, uint64_t* s2, uint64_t* s3,
47  uint64_t* s4, uint64_t* s5, uint64_t* s6, uint64_t* s7,
48  uint64_t* s8, uint64_t* s9, uint64_t* sA, uint64_t* sB)
49 {
50  *s0 += gu_le64(data[0]); *s2 ^= *sA; *sB ^= *s0; *s0 =GU_ROTL64(*s0,11); *sB += *s1;
51  *s1 += gu_le64(data[1]); *s3 ^= *sB; *s0 ^= *s1; *s1 =GU_ROTL64(*s1,32); *s0 += *s2;
52  *s2 += gu_le64(data[2]); *s4 ^= *s0; *s1 ^= *s2; *s2 =GU_ROTL64(*s2,43); *s1 += *s3;
53  *s3 += gu_le64(data[3]); *s5 ^= *s1; *s2 ^= *s3; *s3 =GU_ROTL64(*s3,31); *s2 += *s4;
54  *s4 += gu_le64(data[4]); *s6 ^= *s2; *s3 ^= *s4; *s4 =GU_ROTL64(*s4,17); *s3 += *s5;
55  *s5 += gu_le64(data[5]); *s7 ^= *s3; *s4 ^= *s5; *s5 =GU_ROTL64(*s5,28); *s4 += *s6;
56  *s6 += gu_le64(data[6]); *s8 ^= *s4; *s5 ^= *s6; *s6 =GU_ROTL64(*s6,39); *s5 += *s7;
57  *s7 += gu_le64(data[7]); *s9 ^= *s5; *s6 ^= *s7; *s7 =GU_ROTL64(*s7,57); *s6 += *s8;
58  *s8 += gu_le64(data[8]); *sA ^= *s6; *s7 ^= *s8; *s8 =GU_ROTL64(*s8,55); *s7 += *s9;
59  *s9 += gu_le64(data[9]); *sB ^= *s7; *s8 ^= *s9; *s9 =GU_ROTL64(*s9,54); *s8 += *sA;
60  *sA += gu_le64(data[10]); *s0 ^= *s8; *s9 ^= *sA; *sA =GU_ROTL64(*sA,22); *s9 += *sB;
61  *sB += gu_le64(data[11]); *s1 ^= *s9; *sA ^= *sB; *sB =GU_ROTL64(*sB,46); *sA += *s0;
62 }
63 
64 //
65 // Mix all 12 inputs together so that h0, h1 are a hash of them all.
66 //
67 // For two inputs differing in just the input bits
68 // Where "differ" means xor or subtraction
69 // And the base value is random, or a counting value starting at that bit
70 // The final result will have each bit of h0, h1 flip
71 // For every input bit,
72 // with probability 50 +- .3%
73 // For every pair of input bits,
74 // with probability 50 +- 3%
75 //
76 // This does not rely on the last Mix() call having already mixed some.
77 // Two iterations was almost good enough for a 64-bit result, but a
78 // 128-bit result is reported, so End() does three iterations.
79 //
80 static GU_FORCE_INLINE void _spooky_end_part(
81  uint64_t* h0, uint64_t* h1, uint64_t* h2, uint64_t* h3,
82  uint64_t* h4, uint64_t* h5, uint64_t* h6, uint64_t* h7,
83  uint64_t* h8, uint64_t* h9, uint64_t* h10,uint64_t* h11)
84 {
85  *h11+= *h1; *h2 ^= *h11; *h1 = GU_ROTL64(*h1,44);
86  *h0 += *h2; *h3 ^= *h0; *h2 = GU_ROTL64(*h2,15);
87  *h1 += *h3; *h4 ^= *h1; *h3 = GU_ROTL64(*h3,34);
88  *h2 += *h4; *h5 ^= *h2; *h4 = GU_ROTL64(*h4,21);
89  *h3 += *h5; *h6 ^= *h3; *h5 = GU_ROTL64(*h5,38);
90  *h4 += *h6; *h7 ^= *h4; *h6 = GU_ROTL64(*h6,33);
91  *h5 += *h7; *h8 ^= *h5; *h7 = GU_ROTL64(*h7,10);
92  *h6 += *h8; *h9 ^= *h6; *h8 = GU_ROTL64(*h8,13);
93  *h7 += *h9; *h10^= *h7; *h9 = GU_ROTL64(*h9,38);
94  *h8 += *h10; *h11^= *h8; *h10= GU_ROTL64(*h10,53);
95  *h9 += *h11; *h0 ^= *h9; *h11= GU_ROTL64(*h11,42);
96  *h10+= *h0; *h1 ^= *h10; *h0 = GU_ROTL64(*h0,54);
97 }
98 
99 static GU_FORCE_INLINE void _spooky_end(
100  uint64_t* h0, uint64_t* h1, uint64_t* h2, uint64_t* h3,
101  uint64_t* h4, uint64_t* h5, uint64_t* h6, uint64_t* h7,
102  uint64_t* h8, uint64_t* h9, uint64_t* h10,uint64_t* h11)
103 {
104 #if 0
105  _spooky_end_part(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
106  _spooky_end_part(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
107  _spooky_end_part(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
108 #endif
109  int i;
110  for (i = 0; i < 3; i++)
111  {
112  _spooky_end_part(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
113  }
114 }
115 
116 //
117 // The goal is for each bit of the input to expand into 128 bits of
118 // apparent entropy before it is fully overwritten.
119 // n trials both set and cleared at least m bits of h0 h1 h2 h3
120 // n: 2 m: 29
121 // n: 3 m: 46
122 // n: 4 m: 57
123 // n: 5 m: 107
124 // n: 6 m: 146
125 // n: 7 m: 152
126 // when run forwards or backwards
127 // for all 1-bit and 2-bit diffs
128 // with diffs defined by either xor or subtraction
129 // with a base of all zeros plus a counter, or plus another bit, or random
130 //
131 static GU_FORCE_INLINE void _spooky_short_mix(uint64_t* h0, uint64_t* h1,
132  uint64_t* h2, uint64_t* h3)
133 {
134  *h2 = GU_ROTL64(*h2,50); *h2 += *h3; *h0 ^= *h2;
135  *h3 = GU_ROTL64(*h3,52); *h3 += *h0; *h1 ^= *h3;
136  *h0 = GU_ROTL64(*h0,30); *h0 += *h1; *h2 ^= *h0;
137  *h1 = GU_ROTL64(*h1,41); *h1 += *h2; *h3 ^= *h1;
138  *h2 = GU_ROTL64(*h2,54); *h2 += *h3; *h0 ^= *h2;
139  *h3 = GU_ROTL64(*h3,48); *h3 += *h0; *h1 ^= *h3;
140  *h0 = GU_ROTL64(*h0,38); *h0 += *h1; *h2 ^= *h0;
141  *h1 = GU_ROTL64(*h1,37); *h1 += *h2; *h3 ^= *h1;
142  *h2 = GU_ROTL64(*h2,62); *h2 += *h3; *h0 ^= *h2;
143  *h3 = GU_ROTL64(*h3,34); *h3 += *h0; *h1 ^= *h3;
144  *h0 = GU_ROTL64(*h0,5); *h0 += *h1; *h2 ^= *h0;
145  *h1 = GU_ROTL64(*h1,36); *h1 += *h2; *h3 ^= *h1;
146 }
147 
148 //
149 // Mix all 4 inputs together so that h0, h1 are a hash of them all.
150 //
151 // For two inputs differing in just the input bits
152 // Where "differ" means xor or subtraction
153 // And the base value is random, or a counting value starting at that bit
154 // The final result will have each bit of h0, h1 flip
155 // For every input bit,
156 // with probability 50 +- .3% (it is probably better than that)
157 // For every pair of input bits,
158 // with probability 50 +- .75% (the worst case is approximately that)
159 //
160 static GU_FORCE_INLINE void _spooky_short_end(uint64_t* h0, uint64_t* h1,
161  uint64_t* h2, uint64_t* h3)
162 {
163  *h3 ^= *h2; *h2 = GU_ROTL64(*h2,15); *h3 += *h2;
164  *h0 ^= *h3; *h3 = GU_ROTL64(*h3,52); *h0 += *h3;
165  *h1 ^= *h0; *h0 = GU_ROTL64(*h0,26); *h1 += *h0;
166  *h2 ^= *h1; *h1 = GU_ROTL64(*h1,51); *h2 += *h1;
167  *h3 ^= *h2; *h2 = GU_ROTL64(*h2,28); *h3 += *h2;
168  *h0 ^= *h3; *h3 = GU_ROTL64(*h3,9); *h0 += *h3;
169  *h1 ^= *h0; *h0 = GU_ROTL64(*h0,47); *h1 += *h0;
170  *h2 ^= *h1; *h1 = GU_ROTL64(*h1,54); *h2 += *h1;
171  *h3 ^= *h2; *h2 = GU_ROTL64(*h2,32); *h3 += *h2;
172  *h0 ^= *h3; *h3 = GU_ROTL64(*h3,25); *h0 += *h3;
173  *h1 ^= *h0; *h0 = GU_ROTL64(*h0,63); *h1 += *h0;
174 }
175 
176 //
177 // short hash ... it could be used on any message,
178 // but it's used by Spooky just for short messages.
179 //
180 static GU_INLINE void gu_spooky_short_host(
181  const void* const message,
182  size_t const length,
183  uint64_t* const hash)
184 {
185  union
186  {
187  const uint8_t* p8;
188  uint32_t* p32;
189  uint64_t* p64;
190 #if !GU_ALLOW_UNALIGNED_READS
191  size_t i;
192 #endif /* !GU_ALLOW_UNALIGNED_READS */
193  } u;
194 
195  u.p8 = (const uint8_t *)message;
196 
197 #if !GU_ALLOW_UNALIGNED_READS
198  if (u.i & 0x7)
199  {
200  uint64_t buf[_spooky_numVars << 1];
201  memcpy(buf, message, length);
202  u.p64 = buf;
203  }
204 #endif /* !GU_ALLOW_UNALIGNED_READS */
205 
206  size_t remainder = length & 0x1F; /* length%32 */
207 
208  /* author version : */
209  // uint64_t a = gu_le64(*hash[0]);
210  // uint64_t b = gu_le64(*hash[1]);
211  /* consistent seed version: */
212  uint64_t a = 0;
213  uint64_t b = 0;
214  uint64_t c = _spooky_const;
215  uint64_t d = _spooky_const;
216 
217  if (length > 15)
218  {
219  const uint64_t *end = u.p64 + ((length >> 5) << 2); /* (length/32)*4 */
220 
221  // handle all complete sets of 32 bytes
222  for (; u.p64 < end; u.p64 += 4)
223  {
224  c += gu_le64(u.p64[0]);
225  d += gu_le64(u.p64[1]);
226  _spooky_short_mix(&a, &b, &c, &d);
227  a += gu_le64(u.p64[2]);
228  b += gu_le64(u.p64[3]);
229  }
230 
231  //Handle the case of 16+ remaining bytes.
232  if (remainder >= 16)
233  {
234  c += gu_le64(u.p64[0]);
235  d += gu_le64(u.p64[1]);
236  _spooky_short_mix(&a, &b, &c, &d);
237  u.p64 += 2;
238  remainder -= 16;
239  }
240  }
241 
242  // Handle the last 0..15 bytes, and its length
243  d = ((uint64_t)length) << 56;
244  switch (remainder)
245  {
246  case 15:
247  d += ((uint64_t)u.p8[14]) << 48;
248  case 14:
249  d += ((uint64_t)u.p8[13]) << 40;
250  case 13:
251  d += ((uint64_t)u.p8[12]) << 32;
252  case 12:
253  d += gu_le32(u.p32[2]);
254  c += gu_le64(u.p64[0]);
255  break;
256  case 11:
257  d += ((uint64_t)u.p8[10]) << 16;
258  case 10:
259  d += ((uint64_t)u.p8[9]) << 8;
260  case 9:
261  d += (uint64_t)u.p8[8];
262  case 8:
263  c += gu_le64(u.p64[0]);
264  break;
265  case 7:
266  c += ((uint64_t)u.p8[6]) << 48;
267  case 6:
268  c += ((uint64_t)u.p8[5]) << 40;
269  case 5:
270  c += ((uint64_t)u.p8[4]) << 32;
271  case 4:
272  c += gu_le32(u.p32[0]);
273  break;
274  case 3:
275  c += ((uint64_t)u.p8[2]) << 16;
276  case 2:
277  c += ((uint64_t)u.p8[1]) << 8;
278  case 1:
279  c += (uint64_t)u.p8[0];
280  break;
281  case 0:
282  c += _spooky_const;
283  d += _spooky_const;
284  }
285 
286  _spooky_short_end(&a, &b, &c, &d);
287 
288  // @note - in native-endian order!
289  hash[0] = a;
290  hash[1] = b;
291 }
292 
293 static GU_FORCE_INLINE void gu_spooky_short(
294  const void* message,
295  size_t length,
296  void* const hash)
297 {
298  uint64_t* const u64 = (uint64_t*)hash;
299  gu_spooky_short_host(message, length, u64);
300  u64[0] = gu_le64(u64[0]);
301  u64[1] = gu_le64(u64[1]);
302 }
303 
304 // do the whole hash in one call
305 static GU_INLINE void gu_spooky_inline (
306  const void* const message,
307  size_t const length,
308  uint64_t* const hash)
309 {
310 #ifdef GU_USE_SPOOKY_SHORT
311  if (length < _spooky_bufSize)
312  {
313  gu_spooky_short_base (message, length, hash);
314  return;
315  }
316 #endif /* GU_USE_SPOOKY_SHORT */
317 
318  uint64_t h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11;
319  uint64_t buf[_spooky_numVars];
320  uint64_t* end;
321 
322  union
323  {
324  const uint8_t* p8;
325  uint64_t* p64;
326 #if !GU_ALLOW_UNALIGNED_READS
327  size_t i;
328 #endif /* !GU_ALLOW_UNALIGNED_READS */
329  } u;
330 
331  size_t remainder;
332 
333  /* this is how the author wants it: a possibility for different seeds
334  h0=h3=h6=h9 = gu_le64(hash[0]);
335  h1=h4=h7=h10 = gu_le64(hash[1]);
336  * this is how we want it - constant seed */
337  h0=h3=h6=h9 = 0;
338  h1=h4=h7=h10 = 0;
339  h2=h5=h8=h11 = _spooky_const;
340 
341  u.p8 = (const uint8_t*) message;
342  end = u.p64 + (length/_spooky_blockSize)*_spooky_numVars;
343 
344  // handle all whole _spooky_blockSize blocks of bytes
345 #if !GU_ALLOW_UNALIGNED_READS
346  if ((u.i & 0x7) == 0)
347  {
348 #endif /* !GU_ALLOW_UNALIGNED_READS */
349  while (u.p64 < end)
350  {
351  _spooky_mix(u.p64, &h0,&h1,&h2,&h3,&h4,&h5,&h6,&h7,&h8,&h9,&h10,&h11);
352  u.p64 += _spooky_numVars;
353  }
354 #if !GU_ALLOW_UNALIGNED_READS
355  }
356  else
357  {
358  while (u.p64 < end)
359  {
360  memcpy(buf, u.p64, _spooky_blockSize);
361  _spooky_mix(buf, &h0,&h1,&h2,&h3,&h4,&h5,&h6,&h7,&h8,&h9,&h10,&h11);
362  u.p64 += _spooky_numVars;
363  }
364  }
365 #endif /* !GU_ALLOW_UNALIGNED_READS */
366 
367  // handle the last partial block of _spooky_blockSize bytes
368  remainder = (length - ((const uint8_t*)end - (const uint8_t*)message));
369  memcpy(buf, end, remainder);
370  memset(((uint8_t*)buf) + remainder, 0, _spooky_blockSize - remainder);
371  ((uint8_t*)buf)[_spooky_blockSize - 1] = remainder;
372  _spooky_mix(buf, &h0,&h1,&h2,&h3,&h4,&h5,&h6,&h7,&h8,&h9,&h10,&h11);
373 
374  // do some final mixing
375  _spooky_end(&h0,&h1,&h2,&h3,&h4,&h5,&h6,&h7,&h8,&h9,&h10,&h11);
376 
378  hash[0] = h0;
379  hash[1] = h1;
380 }
381 
382 /* As is apparent from the gu_spooky_inline(), Spooky hash is enormous.
383  * Since it has advantage only on long messages, it makes sense to make it
384  * a regular function to avoid code bloat.
385  * WARNING: does not do final endian conversion! */
386 extern void
387 gu_spooky128_host (const void* const msg, size_t const len, uint64_t* res);
388 
389 /* returns hash in the canonical byte order, as a byte array */
390 static GU_FORCE_INLINE void
391 gu_spooky128 (const void* const msg, size_t const len, void* const res)
392 {
393  uint64_t* const r = (uint64_t*)res;
394  gu_spooky128_host (msg, len, r);
395  r[0] = gu_le64(r[0]);
396  r[1] = gu_le64(r[1]);
397 }
398 
399 /* returns hash as an integer, in host byte-order */
400 static GU_FORCE_INLINE uint64_t
401 gu_spooky64 (const void* const msg, size_t const len)
402 {
403  uint64_t res[2];
404  gu_spooky128_host (msg, len, res);
405  return res[0];
406 }
407 
408 /* returns hash as an integer, in host byte-order */
409 static GU_FORCE_INLINE uint32_t
410 gu_spooky32 (const void* const msg, size_t const len)
411 {
412  uint64_t res[2];
413  gu_spooky128_host (msg, len, res);
414  return (uint32_t)res[0];
415 }
416 
417 #ifdef __cplusplus
418 }
419 #endif
420 
421 #endif /* _gu_spooky_h_ */