API tools faq
paste
View difference between Paste ID: zrqthX9c and pFixUxjf
SHOW: | | - or go back to the newest paste.
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
}
        

    


            


                                


        

            



                
    

        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!