API tools faq
paste
Advertisement
Guest User

Untitled

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