Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define __STDC_CONSTANT_MACROS
- #include <cassert>
- #include <climits>
- #include <cstddef>
- #include <memory.h>
- extern "C"
- {
- #include <stdint.h>
- }
- #if defined (__GLIBC__)
- # include <endian.h>
- # if (__BYTE_ORDER == __BIG_ENDIAN)
- # define SPOOKY_BIG_ENDIAN 1
- # endif
- #elif (defined(__BIG_ENDIAN__) || defined(__BIG_ENDIAN) || defined(_BIG_ENDIAN)) && !(defined(__LITTLE_ENDIAN__) || defined(__LITTLE_ENDIAN) || defined(_LITTLE_ENDIAN))
- # define SPOOKY_BIG_ENDIAN 1
- #elif defined(__sparc) || defined(__sparc__) \
- || defined(__ppc__) || defined(_POWER) || defined(__powerpc__) || defined(_ARCH_PPC) || defined(__PPC__) || defined(__PPC) || defined(PPC) || defined(__powerpc__) || defined(__powerpc) || defined(powerpc) \
- || defined(__hpux) || defined(__hppa) \
- || defined(_MIPSEB) || defined(__s390__)
- # define SPOOKY_BIG_ENDIAN 1
- #else
- # define SPOOKY_BIG_ENDIAN 0
- #endif
- template <typename spooky_word, bool allow_unaligned_reads, bool little_endian>
- class SpookyHash
- {
- public:
- //
- // SpookyHash: hash a single message in one call, produce 128-bit output
- //
- template<size_t hash_size>
- static inline void Hash(
- const void *message, // message to hash
- size_t length, // length of message in bytes
- spooky_word *hash) // in/out: in seed 2, out hash value 2
- {
- if(allow_unaligned_reads)
- _Hash<hash_size, 8>(message, length, hash);
- else
- {
- switch((uintptr_t)message & 7)
- {
- case 1:
- case 3:
- case 5:
- case 7:
- _Hash<hash_size, 1>(message, length, hash);
- break;
- case 2:
- case 6:
- if(sizeof(spooky_word) >= 2)
- _Hash<hash_size, 2>(message, length, hash);
- else
- _Hash<hash_size, sizeof(spooky_word)>(message, length, hash);
- break;
- case 4:
- if(sizeof(spooky_word) >= 4)
- _Hash<hash_size, 4>(message, length, hash);
- else
- _Hash<hash_size, sizeof(spooky_word)>(message, length, hash);
- break;
- break;
- case 0:
- if(sizeof(spooky_word) >= 8)
- _Hash<hash_size, 8>(message, length, hash);
- else
- _Hash<hash_size, sizeof(spooky_word)>(message, length, hash);
- break;
- }
- }
- }
- private:
- template<size_t hash_size, size_t access_size>
- static void _Hash(
- const void *message, // message to hash
- size_t length, // length of message in bytes
- spooky_word *hash); // in/out: in seed 2, out hash value 2
- //
- // left rotate a 64-bit value by k bytes
- //
- static inline spooky_word Rot(spooky_word x, int k)
- {
- return (x << k) | (x >> (word_bits - k));
- }
- static inline spooky_word Bswap(spooky_word x)
- {
- switch(sizeof(spooky_word))
- {
- case 1:
- return x;
- case 2:
- return ((x << 8) & 0xff00) |
- ((x >> 8) & 0x00ff);
- case 4:
- return ((x << 24) & 0xff000000) |
- ((x << 8) & 0x00ff0000) |
- ((x >> 8) & 0x0000ff00) |
- ((x >> 24) & 0x000000ff);
- case 8:
- return ((x << 56) & 0xff00000000000000) |
- ((x << 40) & 0x00ff000000000000) |
- ((x << 24) & 0x0000ff0000000000) |
- ((x << 8) & 0x000000ff00000000) |
- ((x >> 8) & 0x00000000ff000000) |
- ((x >> 24) & 0x0000000000ff0000) |
- ((x >> 40) & 0x000000000000ff00) |
- ((x >> 56) & 0x00000000000000ff);
- }
- }
- static inline spooky_word Read(spooky_word x)
- {
- if(( little_endian && SPOOKY_BIG_ENDIAN) ||
- (!little_endian && !SPOOKY_BIG_ENDIAN))
- return Bswap(x);
- else
- return x;
- }
- //
- template<size_t access_size>
- static inline void Mix(
- const spooky_word *data,
- spooky_word &s0, spooky_word &s1, spooky_word &s2, spooky_word &s3,
- spooky_word &s4, spooky_word &s5, spooky_word &s6, spooky_word &s7,
- spooky_word &s8, spooky_word &s9, spooky_word &s10,spooky_word &s11)
- {
- s0 += Read(data[0]); s2 ^= s10; s11 ^= s0; s0 = Rot(s0,shift0); s11 += s1;
- s1 += Read(data[1]); s3 ^= s11; s0 ^= s1; s1 = Rot(s1,shift1); s0 += s2;
- s2 += Read(data[2]); s4 ^= s0; s1 ^= s2; s2 = Rot(s2,shift2); s1 += s3;
- s3 += Read(data[3]); s5 ^= s1; s2 ^= s3; s3 = Rot(s3,shift3); s2 += s4;
- s4 += Read(data[4]); s6 ^= s2; s3 ^= s4; s4 = Rot(s4,shift4); s3 += s5;
- s5 += Read(data[5]); s7 ^= s3; s4 ^= s5; s5 = Rot(s5,shift5); s4 += s6;
- s6 += Read(data[6]); s8 ^= s4; s5 ^= s6; s6 = Rot(s6,shift6); s5 += s7;
- s7 += Read(data[7]); s9 ^= s5; s6 ^= s7; s7 = Rot(s7,shift7); s6 += s8;
- s8 += Read(data[8]); s10 ^= s6; s7 ^= s8; s8 = Rot(s8,shift8); s7 += s9;
- s9 += Read(data[9]); s11 ^= s7; s8 ^= s9; s9 = Rot(s9,shift9); s8 += s10;
- s10 += Read(data[10]); s0 ^= s8; s9 ^= s10; s10 = Rot(s10,shift10); s9 += s11;
- s11 += Read(data[11]); s1 ^= s9; s10 ^= s11; s11 = Rot(s11,shift11); s10 += s0;
- }
- //
- // Mix all 12 inputs together so that h0, h1 are a hash of them all.
- //
- static inline void EndPartial(
- spooky_word &h0, spooky_word &h1, spooky_word &h2, spooky_word &h3,
- spooky_word &h4, spooky_word &h5, spooky_word &h6, spooky_word &h7,
- spooky_word &h8, spooky_word &h9, spooky_word &h10,spooky_word &h11)
- {
- h11+= h1; h2 ^= h11; h1 = Rot(h1, shift12);
- h0 += h2; h3 ^= h0; h2 = Rot(h2, shift13);
- h1 += h3; h4 ^= h1; h3 = Rot(h3, shift14);
- h2 += h4; h5 ^= h2; h4 = Rot(h4, shift15);
- h3 += h5; h6 ^= h3; h5 = Rot(h5, shift16);
- h4 += h6; h7 ^= h4; h6 = Rot(h6, shift17);
- h5 += h7; h8 ^= h5; h7 = Rot(h7, shift18);
- h6 += h8; h9 ^= h6; h8 = Rot(h8, shift19);
- h7 += h9; h10^= h7; h9 = Rot(h9, shift20);
- h8 += h10; h11^= h8; h10= Rot(h10,shift21);
- h9 += h11; h0 ^= h9; h11= Rot(h11,shift22);
- h10+= h0; h1 ^= h10; h0 = Rot(h0, shift23);
- }
- static inline void End(
- const spooky_word *data,
- spooky_word &h0, spooky_word &h1, spooky_word &h2, spooky_word &h3,
- spooky_word &h4, spooky_word &h5, spooky_word &h6, spooky_word &h7,
- spooky_word &h8, spooky_word &h9, spooky_word &h10,spooky_word &h11)
- {
- h0 += Read(data[0]); h1 += Read(data[1]); h2 += Read(data[2]); h3 += Read(data[3]);
- h4 += Read(data[4]); h5 += Read(data[5]); h6 += Read(data[6]); h7 += Read(data[7]);
- h8 += Read(data[8]); h9 += Read(data[9]); h10 += Read(data[10]); h11 += Read(data[11]);
- EndPartial(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
- EndPartial(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
- EndPartial(h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
- }
- // number of spooky_word's in internal state
- static const size_t sc_numVars = 12;
- static const size_t word_bits = sizeof(spooky_word) * CHAR_BIT;
- // size of the internal state
- static const size_t sc_blockSize = sc_numVars*sizeof(spooky_word);
- //
- // sc_const: a constant which:
- // * is not zero
- // * is odd
- // * is a not-very-regular mix of 1's and 0's
- // * does not need any other special mathematical properties
- //
- static const spooky_word sc_const = (spooky_word)UINT64_C(0xdeadbeefdeadbeef);
- static const int shift0 = word_bits == 64 ? 11 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
- static const int shift1 = word_bits == 64 ? 32 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
- static const int shift2 = word_bits == 64 ? 43 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
- static const int shift3 = word_bits == 64 ? 31 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
- static const int shift4 = word_bits == 64 ? 17 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
- static const int shift5 = word_bits == 64 ? 28 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
- static const int shift6 = word_bits == 64 ? 39 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
- static const int shift7 = word_bits == 64 ? 57 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
- static const int shift8 = word_bits == 64 ? 55 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
- static const int shift9 = word_bits == 64 ? 54 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
- static const int shift10 = word_bits == 64 ? 22 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
- static const int shift11 = word_bits == 64 ? 46 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
- static const int shift12 = word_bits == 64 ? 44 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
- static const int shift13 = word_bits == 64 ? 15 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
- static const int shift14 = word_bits == 64 ? 34 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
- static const int shift15 = word_bits == 64 ? 21 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
- static const int shift16 = word_bits == 64 ? 38 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
- static const int shift17 = word_bits == 64 ? 33 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
- static const int shift18 = word_bits == 64 ? 10 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
- static const int shift19 = word_bits == 64 ? 13 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
- static const int shift20 = word_bits == 64 ? 38 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
- static const int shift21 = word_bits == 64 ? 53 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
- static const int shift22 = word_bits == 64 ? 42 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
- static const int shift23 = word_bits == 64 ? 54 : word_bits == 32 ? 5 : word_bits == 16 ? 3 : 1;
- };
- // do the whole hash in one call
- template <typename spooky_word, bool allow_unaligned_reads, bool little_endian>
- template<size_t hash_size, size_t access_size>
- void SpookyHash<spooky_word, allow_unaligned_reads, little_endian>::_Hash(
- const void *message,
- size_t length,
- spooky_word *hash)
- {
- assert(hash_size > 0 && sc_numVars <= sc_numVars);
- spooky_word h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11;
- spooky_word buf[sc_numVars];
- const uint8_t *end;
- const uint8_t *p;
- size_t remainder;
- h0=h3=h6=h9 = hash[0];
- h1=h4=h7=h10 = hash_size > 1 ? hash[1] : hash[0];
- h2=h5=h8=h11 = sc_const;
- p = (const uint8_t *)message;
- end = p + length - length % sc_blockSize;
- // handle all whole sc_blockSize blocks of bytes
- while(p < end)
- {
- if(allow_unaligned_reads || sizeof(spooky_word) <= access_size)
- {
- Mix<access_size>((spooky_word*)p, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
- }
- else
- {
- for(unsigned i=0; i<sc_blockSize; ++i)
- ((uint8_t*)buf)[i] = p[i];
- Mix<access_size>(buf, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
- }
- p += sc_blockSize;
- }
- // handle the last partial block of sc_blockSize bytes
- remainder = (length - (end - (const uint8_t *)message));
- buf[0] = buf[1] = buf[2] = buf[3] = buf[4] = buf[5] = 0;
- buf[6] = buf[7] = buf[8] = buf[9] = buf[10] = buf[11] = 0;
- memcpy(buf, end, remainder);
- ((uint8_t *)buf)[sc_blockSize-1] = remainder;
- // do some final mixing
- End(buf, h0,h1,h2,h3,h4,h5,h6,h7,h8,h9,h10,h11);
- hash[0] = h0;
- if(hash_size > 1)
- hash[1] = h1;
- if(hash_size > 2)
- hash[2] = h2;
- if(hash_size > 3)
- hash[3] = h3;
- if(hash_size > 4)
- hash[4] = h4;
- if(hash_size > 5)
- hash[5] = h5;
- if(hash_size > 6)
- hash[6] = h6;
- if(hash_size > 7)
- hash[7] = h7;
- if(hash_size > 8)
- hash[8] = h8;
- if(hash_size > 9)
- hash[9] = h9;
- if(hash_size > 10)
- hash[10] = h10;
- if(hash_size > 11)
- hash[11] = h11;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement