InfiniSQL  v0.1.2-alpha
Massive Scale Transaction Processing
 All Classes Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Public Member Functions | Static Public Member Functions | Static Private Member Functions | Private Attributes | Static Private Attributes | List of all members
SpookyHash Class Reference

#include <spooky.h>

Public Member Functions

void Init (uint64 seed1, uint64 seed2)
 
void Update (const void *message, size_t length)
 
void Final (uint64 *hash1, uint64 *hash2)
 

Static Public Member Functions

static void Hash128 (const void *message, size_t length, uint64 *hash1, uint64 *hash2)
 
static uint64 Hash64 (const void *message, size_t length, uint64 seed)
 
static uint32 Hash32 (const void *message, size_t length, uint32 seed)
 
static INLINE uint64 Rot64 (uint64 x, int k)
 
static INLINE void Mix (const uint64 *data, uint64 &s0, uint64 &s1, uint64 &s2, uint64 &s3, uint64 &s4, uint64 &s5, uint64 &s6, uint64 &s7, uint64 &s8, uint64 &s9, uint64 &s10, uint64 &s11)
 
static INLINE void EndPartial (uint64 &h0, uint64 &h1, uint64 &h2, uint64 &h3, uint64 &h4, uint64 &h5, uint64 &h6, uint64 &h7, uint64 &h8, uint64 &h9, uint64 &h10, uint64 &h11)
 
static INLINE void End (uint64 &h0, uint64 &h1, uint64 &h2, uint64 &h3, uint64 &h4, uint64 &h5, uint64 &h6, uint64 &h7, uint64 &h8, uint64 &h9, uint64 &h10, uint64 &h11)
 
static INLINE void ShortMix (uint64 &h0, uint64 &h1, uint64 &h2, uint64 &h3)
 
static INLINE void ShortEnd (uint64 &h0, uint64 &h1, uint64 &h2, uint64 &h3)
 

Static Private Member Functions

static void Short (const void *message, size_t length, uint64 *hash1, uint64 *hash2)
 

Private Attributes

uint64 m_data [2 *sc_numVars]
 
uint64 m_state [sc_numVars]
 
size_t m_length
 
uint8 m_remainder
 

Static Private Attributes

static const size_t sc_numVars = 12
 
static const size_t sc_blockSize = sc_numVars*8
 
static const size_t sc_bufSize = 2*sc_blockSize
 
static const uint64 sc_const = 0xdeadbeefdeadbeefLL
 

Detailed Description

Definition at line 57 of file spooky.h.

Member Function Documentation

static INLINE void SpookyHash::End ( uint64 &  h0,
uint64 &  h1,
uint64 &  h2,
uint64 &  h3,
uint64 &  h4,
uint64 &  h5,
uint64 &  h6,
uint64 &  h7,
uint64 &  h8,
uint64 &  h9,
uint64 &  h10,
uint64 &  h11 
)
inlinestatic

Definition at line 270 of file spooky.h.

References EndPartial().

Referenced by Final(), and Hash128().

274  {
275  EndPartial(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
276  EndPartial(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
277  EndPartial(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
278  }

Here is the call graph for this function:

Here is the caller graph for this function:

static INLINE void SpookyHash::EndPartial ( uint64 &  h0,
uint64 &  h1,
uint64 &  h2,
uint64 &  h3,
uint64 &  h4,
uint64 &  h5,
uint64 &  h6,
uint64 &  h7,
uint64 &  h8,
uint64 &  h9,
uint64 &  h10,
uint64 &  h11 
)
inlinestatic

Definition at line 227 of file spooky.h.

References Rot64().

Referenced by End().

231  {
232  h11+= h1;
233  h2 ^= h11;
234  h1 = Rot64(h1,44);
235  h0 += h2;
236  h3 ^= h0;
237  h2 = Rot64(h2,15);
238  h1 += h3;
239  h4 ^= h1;
240  h3 = Rot64(h3,34);
241  h2 += h4;
242  h5 ^= h2;
243  h4 = Rot64(h4,21);
244  h3 += h5;
245  h6 ^= h3;
246  h5 = Rot64(h5,38);
247  h4 += h6;
248  h7 ^= h4;
249  h6 = Rot64(h6,33);
250  h5 += h7;
251  h8 ^= h5;
252  h7 = Rot64(h7,10);
253  h6 += h8;
254  h9 ^= h6;
255  h8 = Rot64(h8,13);
256  h7 += h9;
257  h10^= h7;
258  h9 = Rot64(h9,38);
259  h8 += h10;
260  h11^= h8;
261  h10= Rot64(h10,53);
262  h9 += h11;
263  h0 ^= h9;
264  h11= Rot64(h11,42);
265  h10+= h0;
266  h1 ^= h10;
267  h0 = Rot64(h0,54);
268  }

Here is the call graph for this function:

Here is the caller graph for this function:

void SpookyHash::Final ( uint64 *  hash1,
uint64 *  hash2 
)

Definition at line 331 of file spooky.cc.

References End(), m_data, m_length, m_remainder, m_state, Mix(), sc_blockSize, sc_bufSize, sc_numVars, and Short().

332 {
333  // init the variables
334  if (m_length < sc_bufSize)
335  {
336  Short(m_data, m_length, hash1, hash2);
337  return;
338  }
339 
340  const uint64 *data = (const uint64 *)m_data;
341  uint8 remainder = m_remainder;
342 
343  uint64 h0 = m_state[0];
344  uint64 h1 = m_state[1];
345  uint64 h2 = m_state[2];
346  uint64 h3 = m_state[3];
347  uint64 h4 = m_state[4];
348  uint64 h5 = m_state[5];
349  uint64 h6 = m_state[6];
350  uint64 h7 = m_state[7];
351  uint64 h8 = m_state[8];
352  uint64 h9 = m_state[9];
353  uint64 h10 = m_state[10];
354  uint64 h11 = m_state[11];
355 
356  if (remainder >= sc_blockSize)
357  {
358  // m_data can contain two blocks; handle any whole first block
359  Mix(data, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
360  data += sc_numVars;
361  remainder -= sc_blockSize;
362  }
363 
364  // mix in the last partial block, and the length mod sc_blockSize
365  memset(&((uint8 *)data)[remainder], 0, (sc_blockSize-remainder));
366 
367  ((uint8 *)data)[sc_blockSize-1] = remainder;
368  Mix(data, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
369 
370  // do some final mixing
371  End(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
372 
373  *hash1 = h0;
374  *hash2 = h1;
375 }

Here is the call graph for this function:

void SpookyHash::Hash128 ( const void *  message,
size_t  length,
uint64 *  hash1,
uint64 *  hash2 
)
static

Definition at line 150 of file spooky.cc.

References ALLOW_UNALIGNED_READS, End(), Mix(), sc_blockSize, sc_bufSize, sc_const, sc_numVars, and Short().

Referenced by Hash32(), and Hash64().

155 {
156  if (length < sc_bufSize)
157  {
158  Short(message, length, hash1, hash2);
159  return;
160  }
161 
162  uint64 h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11;
163  uint64 buf[sc_numVars];
164  uint64 *end;
165  union
166  {
167  const uint8 *p8;
168  uint64 *p64;
169  size_t i;
170  } u;
171  size_t remainder;
172 
173  h0=h3=h6=h9 = *hash1;
174  h1=h4=h7=h10 = *hash2;
175  h2=h5=h8=h11 = sc_const;
176 
177  u.p8 = (const uint8 *)message;
178  end = u.p64 + (length/sc_blockSize)*sc_numVars;
179 
180  // handle all whole sc_blockSize blocks of bytes
181  if (ALLOW_UNALIGNED_READS || ((u.i & 0x7) == 0))
182  {
183  while (u.p64 < end)
184  {
185  Mix(u.p64, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
186  u.p64 += sc_numVars;
187  }
188  }
189  else
190  {
191  while (u.p64 < end)
192  {
193  memcpy(buf, u.p64, sc_blockSize);
194  Mix(buf, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
195  u.p64 += sc_numVars;
196  }
197  }
198 
199  // handle the last partial block of sc_blockSize bytes
200  remainder = (length - ((const uint8 *)end-(const uint8 *)message));
201  memcpy(buf, end, remainder);
202  memset(((uint8 *)buf)+remainder, 0, sc_blockSize-remainder);
203  ((uint8 *)buf)[sc_blockSize-1] = remainder;
204  Mix(buf, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
205 
206  // do some final mixing
207  End(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
208  *hash1 = h0;
209  *hash2 = h1;
210 }

Here is the call graph for this function:

Here is the caller graph for this function:

static uint32 SpookyHash::Hash32 ( const void *  message,
size_t  length,
uint32  seed 
)
inlinestatic

Definition at line 85 of file spooky.h.

References Hash128().

89  {
90  uint64 hash1 = seed, hash2 = seed;
91  Hash128(message, length, &hash1, &hash2);
92  return (uint32)hash1;
93  }

Here is the call graph for this function:

static uint64 SpookyHash::Hash64 ( const void *  message,
size_t  length,
uint64  seed 
)
inlinestatic

Definition at line 72 of file spooky.h.

References Hash128().

Referenced by Transaction::getengine(), Transaction::getEngineid(), and getPartitionid().

76  {
77  uint64 hash1 = seed;
78  Hash128(message, length, &hash1, &seed);
79  return hash1;
80  }

Here is the call graph for this function:

Here is the caller graph for this function:

void SpookyHash::Init ( uint64  seed1,
uint64  seed2 
)

Definition at line 215 of file spooky.cc.

References m_length, m_remainder, and m_state.

216 {
217  m_length = 0;
218  m_remainder = 0;
219  m_state[0] = seed1;
220  m_state[1] = seed2;
221 }
static INLINE void SpookyHash::Mix ( const uint64 *  data,
uint64 &  s0,
uint64 &  s1,
uint64 &  s2,
uint64 &  s3,
uint64 &  s4,
uint64 &  s5,
uint64 &  s6,
uint64 &  s7,
uint64 &  s8,
uint64 &  s9,
uint64 &  s10,
uint64 &  s11 
)
inlinestatic

Definition at line 143 of file spooky.h.

References Rot64().

Referenced by Final(), Hash128(), and Update().

148  {
149  s0 += data[0];
150  s2 ^= s10;
151  s11 ^= s0;
152  s0 = Rot64(s0,11);
153  s11 += s1;
154  s1 += data[1];
155  s3 ^= s11;
156  s0 ^= s1;
157  s1 = Rot64(s1,32);
158  s0 += s2;
159  s2 += data[2];
160  s4 ^= s0;
161  s1 ^= s2;
162  s2 = Rot64(s2,43);
163  s1 += s3;
164  s3 += data[3];
165  s5 ^= s1;
166  s2 ^= s3;
167  s3 = Rot64(s3,31);
168  s2 += s4;
169  s4 += data[4];
170  s6 ^= s2;
171  s3 ^= s4;
172  s4 = Rot64(s4,17);
173  s3 += s5;
174  s5 += data[5];
175  s7 ^= s3;
176  s4 ^= s5;
177  s5 = Rot64(s5,28);
178  s4 += s6;
179  s6 += data[6];
180  s8 ^= s4;
181  s5 ^= s6;
182  s6 = Rot64(s6,39);
183  s5 += s7;
184  s7 += data[7];
185  s9 ^= s5;
186  s6 ^= s7;
187  s7 = Rot64(s7,57);
188  s6 += s8;
189  s8 += data[8];
190  s10 ^= s6;
191  s7 ^= s8;
192  s8 = Rot64(s8,55);
193  s7 += s9;
194  s9 += data[9];
195  s11 ^= s7;
196  s8 ^= s9;
197  s9 = Rot64(s9,54);
198  s8 += s10;
199  s10 += data[10];
200  s0 ^= s8;
201  s9 ^= s10;
202  s10 = Rot64(s10,22);
203  s9 += s11;
204  s11 += data[11];
205  s1 ^= s9;
206  s10 ^= s11;
207  s11 = Rot64(s11,46);
208  s10 += s0;
209  }

Here is the call graph for this function:

Here is the caller graph for this function:

static INLINE uint64 SpookyHash::Rot64 ( uint64  x,
int  k 
)
inlinestatic

Definition at line 125 of file spooky.h.

Referenced by EndPartial(), Mix(), ShortEnd(), and ShortMix().

126  {
127  return (x << k) | (x >> (64 - k));
128  }

Here is the caller graph for this function:

void SpookyHash::Short ( const void *  message,
size_t  length,
uint64 *  hash1,
uint64 *  hash2 
)
staticprivate

Definition at line 27 of file spooky.cc.

References ALLOW_UNALIGNED_READS, sc_const, sc_numVars, ShortEnd(), and ShortMix().

Referenced by Final(), and Hash128().

32 {
33  uint64 buf[2*sc_numVars];
34  union
35  {
36  const uint8 *p8;
37  uint32 *p32;
38  uint64 *p64;
39  size_t i;
40  } u;
41 
42  u.p8 = (const uint8 *)message;
43 
44  if (!ALLOW_UNALIGNED_READS && (u.i & 0x7))
45  {
46  memcpy(buf, message, length);
47  u.p64 = buf;
48  }
49 
50  size_t remainder = length%32;
51  uint64 a=*hash1;
52  uint64 b=*hash2;
53  uint64 c=sc_const;
54  uint64 d=sc_const;
55 
56  if (length > 15)
57  {
58  const uint64 *end = u.p64 + (length/32)*4;
59 
60  // handle all complete sets of 32 bytes
61  for (; u.p64 < end; u.p64 += 4)
62  {
63  c += u.p64[0];
64  d += u.p64[1];
65  ShortMix(a,b,c,d);
66  a += u.p64[2];
67  b += u.p64[3];
68  }
69 
70  //Handle the case of 16+ remaining bytes.
71  if (remainder >= 16)
72  {
73  c += u.p64[0];
74  d += u.p64[1];
75  ShortMix(a,b,c,d);
76  u.p64 += 2;
77  remainder -= 16;
78  }
79  }
80 
81  // Handle the last 0..15 bytes, and its length
82  d = ((uint64)length) << 56;
83 
84  switch (remainder)
85  {
86  case 15:
87  d += ((uint64)u.p8[14]) << 48;
88 
89  case 14:
90  d += ((uint64)u.p8[13]) << 40;
91 
92  case 13:
93  d += ((uint64)u.p8[12]) << 32;
94 
95  case 12:
96  d += u.p32[2];
97  c += u.p64[0];
98  break;
99 
100  case 11:
101  d += ((uint64)u.p8[10]) << 16;
102 
103  case 10:
104  d += ((uint64)u.p8[9]) << 8;
105 
106  case 9:
107  d += (uint64)u.p8[8];
108 
109  case 8:
110  c += u.p64[0];
111  break;
112 
113  case 7:
114  c += ((uint64)u.p8[6]) << 48;
115 
116  case 6:
117  c += ((uint64)u.p8[5]) << 40;
118 
119  case 5:
120  c += ((uint64)u.p8[4]) << 32;
121 
122  case 4:
123  c += u.p32[0];
124  break;
125 
126  case 3:
127  c += ((uint64)u.p8[2]) << 16;
128 
129  case 2:
130  c += ((uint64)u.p8[1]) << 8;
131 
132  case 1:
133  c += (uint64)u.p8[0];
134  break;
135 
136  case 0:
137  c += sc_const;
138  d += sc_const;
139  }
140 
141  ShortEnd(a,b,c,d);
142  *hash1 = a;
143  *hash2 = b;
144 }

Here is the call graph for this function:

Here is the caller graph for this function:

static INLINE void SpookyHash::ShortEnd ( uint64 &  h0,
uint64 &  h1,
uint64 &  h2,
uint64 &  h3 
)
inlinestatic

Definition at line 347 of file spooky.h.

References Rot64().

Referenced by Short().

348  {
349  h3 ^= h2;
350  h2 = Rot64(h2,15);
351  h3 += h2;
352  h0 ^= h3;
353  h3 = Rot64(h3,52);
354  h0 += h3;
355  h1 ^= h0;
356  h0 = Rot64(h0,26);
357  h1 += h0;
358  h2 ^= h1;
359  h1 = Rot64(h1,51);
360  h2 += h1;
361  h3 ^= h2;
362  h2 = Rot64(h2,28);
363  h3 += h2;
364  h0 ^= h3;
365  h3 = Rot64(h3,9);
366  h0 += h3;
367  h1 ^= h0;
368  h0 = Rot64(h0,47);
369  h1 += h0;
370  h2 ^= h1;
371  h1 = Rot64(h1,54);
372  h2 += h1;
373  h3 ^= h2;
374  h2 = Rot64(h2,32);
375  h3 += h2;
376  h0 ^= h3;
377  h3 = Rot64(h3,25);
378  h0 += h3;
379  h1 ^= h0;
380  h0 = Rot64(h0,63);
381  h1 += h0;
382  }

Here is the call graph for this function:

Here is the caller graph for this function:

static INLINE void SpookyHash::ShortMix ( uint64 &  h0,
uint64 &  h1,
uint64 &  h2,
uint64 &  h3 
)
inlinestatic

Definition at line 295 of file spooky.h.

References Rot64().

Referenced by Short().

296  {
297  h2 = Rot64(h2,50);
298  h2 += h3;
299  h0 ^= h2;
300  h3 = Rot64(h3,52);
301  h3 += h0;
302  h1 ^= h3;
303  h0 = Rot64(h0,30);
304  h0 += h1;
305  h2 ^= h0;
306  h1 = Rot64(h1,41);
307  h1 += h2;
308  h3 ^= h1;
309  h2 = Rot64(h2,54);
310  h2 += h3;
311  h0 ^= h2;
312  h3 = Rot64(h3,48);
313  h3 += h0;
314  h1 ^= h3;
315  h0 = Rot64(h0,38);
316  h0 += h1;
317  h2 ^= h0;
318  h1 = Rot64(h1,37);
319  h1 += h2;
320  h3 ^= h1;
321  h2 = Rot64(h2,62);
322  h2 += h3;
323  h0 ^= h2;
324  h3 = Rot64(h3,34);
325  h3 += h0;
326  h1 ^= h3;
327  h0 = Rot64(h0,5);
328  h0 += h1;
329  h2 ^= h0;
330  h1 = Rot64(h1,36);
331  h1 += h2;
332  h3 ^= h1;
333  }

Here is the call graph for this function:

Here is the caller graph for this function:

void SpookyHash::Update ( const void *  message,
size_t  length 
)

Definition at line 225 of file spooky.cc.

References ALLOW_UNALIGNED_READS, m_data, m_length, m_remainder, m_state, Mix(), sc_blockSize, sc_bufSize, sc_const, and sc_numVars.

226 {
227  uint64 h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11;
228  size_t newLength = length + m_remainder;
229  uint8 remainder;
230  union
231  {
232  const uint8 *p8;
233  uint64 *p64;
234  size_t i;
235  } u;
236  const uint64 *end;
237 
238  // Is this message fragment too short? If it is, stuff it away.
239  if (newLength < sc_bufSize)
240  {
241  memcpy(&((uint8 *)m_data)[m_remainder], message, length);
242  m_length = length + m_length;
243  m_remainder = (uint8)newLength;
244  return;
245  }
246 
247  // init the variables
248  if (m_length < sc_bufSize)
249  {
250  h0=h3=h6=h9 = m_state[0];
251  h1=h4=h7=h10 = m_state[1];
252  h2=h5=h8=h11 = sc_const;
253  }
254  else
255  {
256  h0 = m_state[0];
257  h1 = m_state[1];
258  h2 = m_state[2];
259  h3 = m_state[3];
260  h4 = m_state[4];
261  h5 = m_state[5];
262  h6 = m_state[6];
263  h7 = m_state[7];
264  h8 = m_state[8];
265  h9 = m_state[9];
266  h10 = m_state[10];
267  h11 = m_state[11];
268  }
269 
270  m_length = length + m_length;
271 
272  // if we've got anything stuffed away, use it now
273  if (m_remainder)
274  {
275  uint8 prefix = sc_bufSize-m_remainder;
276  memcpy(&(((uint8 *)m_data)[m_remainder]), message, prefix);
277  u.p64 = m_data;
278  Mix(u.p64, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
279  Mix(&u.p64[sc_numVars], h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
280  u.p8 = ((const uint8 *)message) + prefix;
281  length -= prefix;
282  }
283  else
284  {
285  u.p8 = (const uint8 *)message;
286  }
287 
288  // handle all whole blocks of sc_blockSize bytes
289  end = u.p64 + (length/sc_blockSize)*sc_numVars;
290  remainder = (uint8)(length-((const uint8 *)end-u.p8));
291 
292  if (ALLOW_UNALIGNED_READS || (u.i & 0x7) == 0)
293  {
294  while (u.p64 < end)
295  {
296  Mix(u.p64, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
297  u.p64 += sc_numVars;
298  }
299  }
300  else
301  {
302  while (u.p64 < end)
303  {
304  memcpy(m_data, u.p8, sc_blockSize);
305  Mix(m_data, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
306  u.p64 += sc_numVars;
307  }
308  }
309 
310  // stuff away the last few bytes
311  m_remainder = remainder;
312  memcpy(m_data, end, remainder);
313 
314  // stuff away the variables
315  m_state[0] = h0;
316  m_state[1] = h1;
317  m_state[2] = h2;
318  m_state[3] = h3;
319  m_state[4] = h4;
320  m_state[5] = h5;
321  m_state[6] = h6;
322  m_state[7] = h7;
323  m_state[8] = h8;
324  m_state[9] = h9;
325  m_state[10] = h10;
326  m_state[11] = h11;
327 }

Here is the call graph for this function:

Member Data Documentation

uint64 SpookyHash::m_data[2 *sc_numVars]
private

Definition at line 416 of file spooky.h.

Referenced by Final(), and Update().

size_t SpookyHash::m_length
private

Definition at line 418 of file spooky.h.

Referenced by Final(), Init(), and Update().

uint8 SpookyHash::m_remainder
private

Definition at line 419 of file spooky.h.

Referenced by Final(), Init(), and Update().

uint64 SpookyHash::m_state[sc_numVars]
private

Definition at line 417 of file spooky.h.

Referenced by Final(), Init(), and Update().

const size_t SpookyHash::sc_blockSize = sc_numVars*8
staticprivate

Definition at line 402 of file spooky.h.

Referenced by Final(), Hash128(), and Update().

const size_t SpookyHash::sc_bufSize = 2*sc_blockSize
staticprivate

Definition at line 405 of file spooky.h.

Referenced by Final(), Hash128(), and Update().

const uint64 SpookyHash::sc_const = 0xdeadbeefdeadbeefLL
staticprivate

Definition at line 414 of file spooky.h.

Referenced by Hash128(), Short(), and Update().

const size_t SpookyHash::sc_numVars = 12
staticprivate

Definition at line 399 of file spooky.h.

Referenced by Final(), Hash128(), Short(), and Update().

The documentation for this class was generated from the following files: