API tools faq
paste
Guest User

Untitled

a guest
Jul 7th, 2013
51
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 12.47 KB | None | 0 0
raw download clone embed print report
  1.  
  2. #define __STDC_CONSTANT_MACROS
  3.  
  4. #include <cassert>
  5. #include <climits>
  6. #include <cstddef>
  7. #include <memory.h>
  8. extern "C"
  9. {
  10. #include <stdint.h>
  11. }
  12.  
  13. #if defined (__GLIBC__)
  14. # include <endian.h>
  15. # if (__BYTE_ORDER == __BIG_ENDIAN)
  16. # define SPOOKY_BIG_ENDIAN 1
  17. # endif
  18. #elif (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || defined(_BIG_ENDIAN)) && !(defined(__LITTLE_ENDIAN__) || defined(__LITTLE_ENDIAN) || defined(_LITTLE_ENDIAN))
  19. # define SPOOKY_BIG_ENDIAN 1
  20. #elif defined(__sparc) || defined(__sparc__) \
  21. || defined(__ppc__) || defined(_POWER) || defined(__powerpc__) || defined(_ARCH_PPC) || defined(__PPC__) || defined(__PPC) || defined(PPC) || defined(__powerpc__) || defined(__powerpc) || defined(powerpc) \
  22. || defined(__hpux) || defined(__hppa) \
  23. || defined(_MIPSEB) || defined(__s390__)
  24. # define SPOOKY_BIG_ENDIAN 1
  25. #else
  26. # define SPOOKY_BIG_ENDIAN 0
  27. #endif
  28.  
  29. template <typename spooky_word, bool allow_unaligned_reads, bool little_endian>
  30. class SpookyHash
  31. {
  32. public:
  33. //
  34. // SpookyHash: hash a single message in one call, produce 128-bit output
  35. //
  36. template<size_t hash_size>
  37. static inline void Hash(
  38. const void *message, // message to hash
  39. size_t length, // length of message in bytes
  40. spooky_word *hash) // in/out: in seed 2, out hash value 2
  41. {
  42. if(allow_unaligned_reads)
  43. _Hash<hash_size, 8>(message, length, hash);
  44. else
  45. {
  46. switch((uintptr_t)message & 7)
  47. {
  48. case 1:
  49. case 3:
  50. case 5:
  51. case 7:
  52. _Hash<hash_size, 1>(message, length, hash);
  53. break;
  54. case 2:
  55. case 6:
  56. if(sizeof(spooky_word) >= 2)
  57. _Hash<hash_size, 2>(message, length, hash);
  58. else
  59. _Hash<hash_size, sizeof(spooky_word)>(message, length, hash);
  60. break;
  61. case 4:
  62. if(sizeof(spooky_word) >= 4)
  63. _Hash<hash_size, 4>(message, length, hash);
  64. else
  65. _Hash<hash_size, sizeof(spooky_word)>(message, length, hash);
  66. break;
  67. break;
  68. case 0:
  69. if(sizeof(spooky_word) >= 8)
  70. _Hash<hash_size, 8>(message, length, hash);
  71. else
  72. _Hash<hash_size, sizeof(spooky_word)>(message, length, hash);
  73. break;
  74. }
  75. }
  76. }
  77.  
  78. private:
  79. template<size_t hash_size, size_t access_size>
  80. static void _Hash(
  81. const void *message, // message to hash
  82. size_t length, // length of message in bytes
  83. spooky_word *hash); // in/out: in seed 2, out hash value 2
  84.  
  85. //
  86. // left rotate a 64-bit value by k bytes
  87. //
  88. static inline spooky_word Rot(spooky_word x, int k)
  89. {
  90. return (x << k) | (x >> (word_bits - k));
  91. }
  92.  
  93. static inline spooky_word Bswap(spooky_word x)
  94. {
  95. switch(sizeof(spooky_word))
  96. {
  97. case 1:
  98. return x;
  99. case 2:
  100. return ((x << 8) & 0xff00) |
  101. ((x >> 8) & 0x00ff);
  102. case 4:
  103. return ((x << 24) & 0xff000000) |
  104. ((x << 8) & 0x00ff0000) |
  105. ((x >> 8) & 0x0000ff00) |
  106. ((x >> 24) & 0x000000ff);
  107. case 8:
  108. return ((x << 56) & 0xff00000000000000) |
  109. ((x << 40) & 0x00ff000000000000) |
  110. ((x << 24) & 0x0000ff0000000000) |
  111. ((x << 8) & 0x000000ff00000000) |
  112. ((x >> 8) & 0x00000000ff000000) |
  113. ((x >> 24) & 0x0000000000ff0000) |
  114. ((x >> 40) & 0x000000000000ff00) |
  115. ((x >> 56) & 0x00000000000000ff);
  116. }
  117. }
  118.  
  119. static inline spooky_word Read(spooky_word x)
  120. {
  121. if(( little_endian && SPOOKY_BIG_ENDIAN) ||
  122. (!little_endian && !SPOOKY_BIG_ENDIAN))
  123. return Bswap(x);
  124. else
  125. return x;
  126. }
  127. //
  128. template<size_t access_size>
  129. static inline void Mix(
  130. const spooky_word *data,
  131. spooky_word &s0, spooky_word &s1, spooky_word &s2, spooky_word &s3,
  132. spooky_word &s4, spooky_word &s5, spooky_word &s6, spooky_word &s7,
  133. spooky_word &s8, spooky_word &s9, spooky_word &s10,spooky_word &s11)
  134. {
  135. s0 += Read(data[0]); s2 ^= s10; s11 ^= s0; s0 = Rot(s0,shift0); s11 += s1;
  136. s1 += Read(data[1]); s3 ^= s11; s0 ^= s1; s1 = Rot(s1,shift1); s0 += s2;
  137. s2 += Read(data[2]); s4 ^= s0; s1 ^= s2; s2 = Rot(s2,shift2); s1 += s3;
  138. s3 += Read(data[3]); s5 ^= s1; s2 ^= s3; s3 = Rot(s3,shift3); s2 += s4;
  139. s4 += Read(data[4]); s6 ^= s2; s3 ^= s4; s4 = Rot(s4,shift4); s3 += s5;
  140. s5 += Read(data[5]); s7 ^= s3; s4 ^= s5; s5 = Rot(s5,shift5); s4 += s6;
  141. s6 += Read(data[6]); s8 ^= s4; s5 ^= s6; s6 = Rot(s6,shift6); s5 += s7;
  142. s7 += Read(data[7]); s9 ^= s5; s6 ^= s7; s7 = Rot(s7,shift7); s6 += s8;
  143. s8 += Read(data[8]); s10 ^= s6; s7 ^= s8; s8 = Rot(s8,shift8); s7 += s9;
  144. s9 += Read(data[9]); s11 ^= s7; s8 ^= s9; s9 = Rot(s9,shift9); s8 += s10;
  145. s10 += Read(data[10]); s0 ^= s8; s9 ^= s10; s10 = Rot(s10,shift10); s9 += s11;
  146. s11 += Read(data[11]); s1 ^= s9; s10 ^= s11; s11 = Rot(s11,shift11); s10 += s0;
  147. }
  148.  
  149. //
  150. // Mix all 12 inputs together so that h0, h1 are a hash of them all.
  151. //
  152. static inline void EndPartial(
  153. spooky_word &h0, spooky_word &h1, spooky_word &h2, spooky_word &h3,
  154. spooky_word &h4, spooky_word &h5, spooky_word &h6, spooky_word &h7,
  155. spooky_word &h8, spooky_word &h9, spooky_word &h10,spooky_word &h11)
  156. {
  157. h11+= h1; h2 ^= h11; h1 = Rot(h1, shift12);
  158. h0 += h2; h3 ^= h0; h2 = Rot(h2, shift13);
  159. h1 += h3; h4 ^= h1; h3 = Rot(h3, shift14);
  160. h2 += h4; h5 ^= h2; h4 = Rot(h4, shift15);
  161. h3 += h5; h6 ^= h3; h5 = Rot(h5, shift16);
  162. h4 += h6; h7 ^= h4; h6 = Rot(h6, shift17);
  163. h5 += h7; h8 ^= h5; h7 = Rot(h7, shift18);
  164. h6 += h8; h9 ^= h6; h8 = Rot(h8, shift19);
  165. h7 += h9; h10^= h7; h9 = Rot(h9, shift20);
  166. h8 += h10; h11^= h8; h10= Rot(h10,shift21);
  167. h9 += h11; h0 ^= h9; h11= Rot(h11,shift22);
  168. h10+= h0; h1 ^= h10; h0 = Rot(h0, shift23);
  169. }
  170.  
  171. static inline void End(
  172. const spooky_word *data,
  173. spooky_word &h0, spooky_word &h1, spooky_word &h2, spooky_word &h3,
  174. spooky_word &h4, spooky_word &h5, spooky_word &h6, spooky_word &h7,
  175. spooky_word &h8, spooky_word &h9, spooky_word &h10,spooky_word &h11)
  176. {
  177. h0 += Read(data[0]); h1 += Read(data[1]); h2 += Read(data[2]); h3 += Read(data[3]);
  178. h4 += Read(data[4]); h5 += Read(data[5]); h6 += Read(data[6]); h7 += Read(data[7]);
  179. h8 += Read(data[8]); h9 += Read(data[9]); h10 += Read(data[10]); h11 += Read(data[11]);
  180. EndPartial(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
  181. EndPartial(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
  182. EndPartial(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
  183. }
  184.  
  185. // number of spooky_word's in internal state
  186. static const size_t sc_numVars = 12;
  187.  
  188. static const size_t word_bits = sizeof(spooky_word) * CHAR_BIT;
  189.  
  190. // size of the internal state
  191. static const size_t sc_blockSize = sc_numVars*sizeof(spooky_word);
  192.  
  193. //
  194. // sc_const: a constant which:
  195. // * is not zero
  196. // * is odd
  197. // * is a not-very-regular mix of 1's and 0's
  198. // * does not need any other special mathematical properties
  199. //
  200. static const spooky_word sc_const = (spooky_word)UINT64_C(0xdeadbeefdeadbeef);
  201.  
  202. static const int shift0 = word_bits == 64 ? 11 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
  203. static const int shift1 = word_bits == 64 ? 32 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
  204. static const int shift2 = word_bits == 64 ? 43 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
  205. static const int shift3 = word_bits == 64 ? 31 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
  206. static const int shift4 = word_bits == 64 ? 17 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
  207. static const int shift5 = word_bits == 64 ? 28 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
  208. static const int shift6 = word_bits == 64 ? 39 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
  209. static const int shift7 = word_bits == 64 ? 57 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
  210. static const int shift8 = word_bits == 64 ? 55 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
  211. static const int shift9 = word_bits == 64 ? 54 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
  212. static const int shift10 = word_bits == 64 ? 22 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
  213. static const int shift11 = word_bits == 64 ? 46 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
  214. static const int shift12 = word_bits == 64 ? 44 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
  215. static const int shift13 = word_bits == 64 ? 15 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
  216. static const int shift14 = word_bits == 64 ? 34 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
  217. static const int shift15 = word_bits == 64 ? 21 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
  218. static const int shift16 = word_bits == 64 ? 38 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
  219. static const int shift17 = word_bits == 64 ? 33 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
  220. static const int shift18 = word_bits == 64 ? 10 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
  221. static const int shift19 = word_bits == 64 ? 13 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
  222. static const int shift20 = word_bits == 64 ? 38 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
  223. static const int shift21 = word_bits == 64 ? 53 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
  224. static const int shift22 = word_bits == 64 ? 42 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
  225. static const int shift23 = word_bits == 64 ? 54 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
  226. };
  227.  
  228.  
  229. // do the whole hash in one call
  230. template <typename spooky_word, bool allow_unaligned_reads, bool little_endian>
  231. template<size_t hash_size, size_t access_size>
  232. void SpookyHash<spooky_word, allow_unaligned_reads, little_endian>::_Hash(
  233. const void *message,
  234. size_t length,
  235. spooky_word *hash)
  236. {
  237. assert(hash_size > 0 && sc_numVars <= sc_numVars);
  238. spooky_word h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11;
  239. spooky_word buf[sc_numVars];
  240. const uint8_t *end;
  241. const uint8_t *p;
  242. size_t remainder;
  243.  
  244. h0=h3=h6=h9 = hash[0];
  245. h1=h4=h7=h10 = hash_size > 1 ? hash[1] : hash[0];
  246. h2=h5=h8=h11 = sc_const;
  247.  
  248. p = (const uint8_t *)message;
  249. end = p + length - length % sc_blockSize;
  250.  
  251. // handle all whole sc_blockSize blocks of bytes
  252. while(p < end)
  253. {
  254. if(allow_unaligned_reads || sizeof(spooky_word) <= access_size)
  255. {
  256. Mix<access_size>((spooky_word*)p, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
  257. }
  258. else
  259. {
  260. for(unsigned i=0; i<sc_blockSize; ++i)
  261. ((uint8_t*)buf)[i] = p[i];
  262. Mix<access_size>(buf, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
  263. }
  264. p += sc_blockSize;
  265. }
  266.  
  267. // handle the last partial block of sc_blockSize bytes
  268. remainder = (length - (end - (const uint8_t *)message));
  269. buf[0] = buf[1] = buf[2] = buf[3] = buf[4] = buf[5] = 0;
  270. buf[6] = buf[7] = buf[8] = buf[9] = buf[10] = buf[11] = 0;
  271. memcpy(buf, end, remainder);
  272. ((uint8_t *)buf)[sc_blockSize-1] = remainder;
  273.  
  274. // do some final mixing
  275. End(buf, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
  276. hash[0] = h0;
  277. if(hash_size > 1)
  278. hash[1] = h1;
  279. if(hash_size > 2)
  280. hash[2] = h2;
  281. if(hash_size > 3)
  282. hash[3] = h3;
  283. if(hash_size > 4)
  284. hash[4] = h4;
  285. if(hash_size > 5)
  286. hash[5] = h5;
  287. if(hash_size > 6)
  288. hash[6] = h6;
  289. if(hash_size > 7)
  290. hash[7] = h7;
  291. if(hash_size > 8)
  292. hash[8] = h8;
  293. if(hash_size > 9)
  294. hash[9] = h9;
  295. if(hash_size > 10)
  296. hash[10] = h10;
  297. if(hash_size > 11)
  298. hash[11] = h11;
  299. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!