1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/angle/src/third_party/murmurhash/MurmurHash3.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,334 @@
1.4 +//-----------------------------------------------------------------------------
1.5 +// MurmurHash3 was written by Austin Appleby, and is placed in the public
1.6 +// domain. The author hereby disclaims copyright to this source code.
1.7 +
1.8 +// Note - The x86 and x64 versions do _not_ produce the same results, as the
1.9 +// algorithms are optimized for their respective platforms. You can still
1.10 +// compile and run any of them on any platform, but your performance with the
1.11 +// non-native version will be less than optimal.
1.12 +
1.13 +#include "MurmurHash3.h"
1.14 +
1.15 +//-----------------------------------------------------------------------------
1.16 +// Platform-specific functions and macros
1.17 +
1.18 +// Microsoft Visual Studio
1.19 +
1.20 +#if defined(_MSC_VER)
1.21 +
1.22 +#define FORCE_INLINE __forceinline
1.23 +
1.24 +#include <stdlib.h>
1.25 +
1.26 +#define ROTL32(x,y) _rotl(x,y)
1.27 +#define ROTL64(x,y) _rotl64(x,y)
1.28 +
1.29 +#define BIG_CONSTANT(x) (x)
1.30 +
1.31 +// Other compilers
1.32 +
1.33 +#else // defined(_MSC_VER)
1.34 +
1.35 +#define FORCE_INLINE __attribute__((always_inline))
1.36 +
1.37 +inline uint32_t rotl32 ( uint32_t x, int8_t r )
1.38 +{
1.39 + return (x << r) | (x >> (32 - r));
1.40 +}
1.41 +
1.42 +inline uint64_t rotl64 ( uint64_t x, int8_t r )
1.43 +{
1.44 + return (x << r) | (x >> (64 - r));
1.45 +}
1.46 +
1.47 +#define ROTL32(x,y) rotl32(x,y)
1.48 +#define ROTL64(x,y) rotl64(x,y)
1.49 +
1.50 +#define BIG_CONSTANT(x) (x##LLU)
1.51 +
1.52 +#endif // !defined(_MSC_VER)
1.53 +
1.54 +//-----------------------------------------------------------------------------
1.55 +// Block read - if your platform needs to do endian-swapping or can only
1.56 +// handle aligned reads, do the conversion here
1.57 +
1.58 +FORCE_INLINE uint32_t getblock ( const uint32_t * p, int i )
1.59 +{
1.60 + return p[i];
1.61 +}
1.62 +
1.63 +FORCE_INLINE uint64_t getblock ( const uint64_t * p, int i )
1.64 +{
1.65 + return p[i];
1.66 +}
1.67 +
1.68 +//-----------------------------------------------------------------------------
1.69 +// Finalization mix - force all bits of a hash block to avalanche
1.70 +
1.71 +FORCE_INLINE uint32_t fmix ( uint32_t h )
1.72 +{
1.73 + h ^= h >> 16;
1.74 + h *= 0x85ebca6b;
1.75 + h ^= h >> 13;
1.76 + h *= 0xc2b2ae35;
1.77 + h ^= h >> 16;
1.78 +
1.79 + return h;
1.80 +}
1.81 +
1.82 +//----------
1.83 +
1.84 +FORCE_INLINE uint64_t fmix ( uint64_t k )
1.85 +{
1.86 + k ^= k >> 33;
1.87 + k *= BIG_CONSTANT(0xff51afd7ed558ccd);
1.88 + k ^= k >> 33;
1.89 + k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
1.90 + k ^= k >> 33;
1.91 +
1.92 + return k;
1.93 +}
1.94 +
1.95 +//-----------------------------------------------------------------------------
1.96 +
1.97 +void MurmurHash3_x86_32 ( const void * key, int len,
1.98 + uint32_t seed, void * out )
1.99 +{
1.100 + const uint8_t * data = (const uint8_t*)key;
1.101 + const int nblocks = len / 4;
1.102 +
1.103 + uint32_t h1 = seed;
1.104 +
1.105 + const uint32_t c1 = 0xcc9e2d51;
1.106 + const uint32_t c2 = 0x1b873593;
1.107 +
1.108 + //----------
1.109 + // body
1.110 +
1.111 + const uint32_t * blocks = (const uint32_t *)(data + nblocks*4);
1.112 +
1.113 + for(int i = -nblocks; i; i++)
1.114 + {
1.115 + uint32_t k1 = getblock(blocks,i);
1.116 +
1.117 + k1 *= c1;
1.118 + k1 = ROTL32(k1,15);
1.119 + k1 *= c2;
1.120 +
1.121 + h1 ^= k1;
1.122 + h1 = ROTL32(h1,13);
1.123 + h1 = h1*5+0xe6546b64;
1.124 + }
1.125 +
1.126 + //----------
1.127 + // tail
1.128 +
1.129 + const uint8_t * tail = (const uint8_t*)(data + nblocks*4);
1.130 +
1.131 + uint32_t k1 = 0;
1.132 +
1.133 + switch(len & 3)
1.134 + {
1.135 + case 3: k1 ^= tail[2] << 16;
1.136 + case 2: k1 ^= tail[1] << 8;
1.137 + case 1: k1 ^= tail[0];
1.138 + k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
1.139 + };
1.140 +
1.141 + //----------
1.142 + // finalization
1.143 +
1.144 + h1 ^= len;
1.145 +
1.146 + h1 = fmix(h1);
1.147 +
1.148 + *(uint32_t*)out = h1;
1.149 +}
1.150 +
1.151 +//-----------------------------------------------------------------------------
1.152 +
1.153 +void MurmurHash3_x86_128 ( const void * key, const int len,
1.154 + uint32_t seed, void * out )
1.155 +{
1.156 + const uint8_t * data = (const uint8_t*)key;
1.157 + const int nblocks = len / 16;
1.158 +
1.159 + uint32_t h1 = seed;
1.160 + uint32_t h2 = seed;
1.161 + uint32_t h3 = seed;
1.162 + uint32_t h4 = seed;
1.163 +
1.164 + const uint32_t c1 = 0x239b961b;
1.165 + const uint32_t c2 = 0xab0e9789;
1.166 + const uint32_t c3 = 0x38b34ae5;
1.167 + const uint32_t c4 = 0xa1e38b93;
1.168 +
1.169 + //----------
1.170 + // body
1.171 +
1.172 + const uint32_t * blocks = (const uint32_t *)(data + nblocks*16);
1.173 +
1.174 + for(int i = -nblocks; i; i++)
1.175 + {
1.176 + uint32_t k1 = getblock(blocks,i*4+0);
1.177 + uint32_t k2 = getblock(blocks,i*4+1);
1.178 + uint32_t k3 = getblock(blocks,i*4+2);
1.179 + uint32_t k4 = getblock(blocks,i*4+3);
1.180 +
1.181 + k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
1.182 +
1.183 + h1 = ROTL32(h1,19); h1 += h2; h1 = h1*5+0x561ccd1b;
1.184 +
1.185 + k2 *= c2; k2 = ROTL32(k2,16); k2 *= c3; h2 ^= k2;
1.186 +
1.187 + h2 = ROTL32(h2,17); h2 += h3; h2 = h2*5+0x0bcaa747;
1.188 +
1.189 + k3 *= c3; k3 = ROTL32(k3,17); k3 *= c4; h3 ^= k3;
1.190 +
1.191 + h3 = ROTL32(h3,15); h3 += h4; h3 = h3*5+0x96cd1c35;
1.192 +
1.193 + k4 *= c4; k4 = ROTL32(k4,18); k4 *= c1; h4 ^= k4;
1.194 +
1.195 + h4 = ROTL32(h4,13); h4 += h1; h4 = h4*5+0x32ac3b17;
1.196 + }
1.197 +
1.198 + //----------
1.199 + // tail
1.200 +
1.201 + const uint8_t * tail = (const uint8_t*)(data + nblocks*16);
1.202 +
1.203 + uint32_t k1 = 0;
1.204 + uint32_t k2 = 0;
1.205 + uint32_t k3 = 0;
1.206 + uint32_t k4 = 0;
1.207 +
1.208 + switch(len & 15)
1.209 + {
1.210 + case 15: k4 ^= tail[14] << 16;
1.211 + case 14: k4 ^= tail[13] << 8;
1.212 + case 13: k4 ^= tail[12] << 0;
1.213 + k4 *= c4; k4 = ROTL32(k4,18); k4 *= c1; h4 ^= k4;
1.214 +
1.215 + case 12: k3 ^= tail[11] << 24;
1.216 + case 11: k3 ^= tail[10] << 16;
1.217 + case 10: k3 ^= tail[ 9] << 8;
1.218 + case 9: k3 ^= tail[ 8] << 0;
1.219 + k3 *= c3; k3 = ROTL32(k3,17); k3 *= c4; h3 ^= k3;
1.220 +
1.221 + case 8: k2 ^= tail[ 7] << 24;
1.222 + case 7: k2 ^= tail[ 6] << 16;
1.223 + case 6: k2 ^= tail[ 5] << 8;
1.224 + case 5: k2 ^= tail[ 4] << 0;
1.225 + k2 *= c2; k2 = ROTL32(k2,16); k2 *= c3; h2 ^= k2;
1.226 +
1.227 + case 4: k1 ^= tail[ 3] << 24;
1.228 + case 3: k1 ^= tail[ 2] << 16;
1.229 + case 2: k1 ^= tail[ 1] << 8;
1.230 + case 1: k1 ^= tail[ 0] << 0;
1.231 + k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
1.232 + };
1.233 +
1.234 + //----------
1.235 + // finalization
1.236 +
1.237 + h1 ^= len; h2 ^= len; h3 ^= len; h4 ^= len;
1.238 +
1.239 + h1 += h2; h1 += h3; h1 += h4;
1.240 + h2 += h1; h3 += h1; h4 += h1;
1.241 +
1.242 + h1 = fmix(h1);
1.243 + h2 = fmix(h2);
1.244 + h3 = fmix(h3);
1.245 + h4 = fmix(h4);
1.246 +
1.247 + h1 += h2; h1 += h3; h1 += h4;
1.248 + h2 += h1; h3 += h1; h4 += h1;
1.249 +
1.250 + ((uint32_t*)out)[0] = h1;
1.251 + ((uint32_t*)out)[1] = h2;
1.252 + ((uint32_t*)out)[2] = h3;
1.253 + ((uint32_t*)out)[3] = h4;
1.254 +}
1.255 +
1.256 +//-----------------------------------------------------------------------------
1.257 +
1.258 +void MurmurHash3_x64_128 ( const void * key, const int len,
1.259 + const uint32_t seed, void * out )
1.260 +{
1.261 + const uint8_t * data = (const uint8_t*)key;
1.262 + const int nblocks = len / 16;
1.263 +
1.264 + uint64_t h1 = seed;
1.265 + uint64_t h2 = seed;
1.266 +
1.267 + const uint64_t c1 = BIG_CONSTANT(0x87c37b91114253d5);
1.268 + const uint64_t c2 = BIG_CONSTANT(0x4cf5ad432745937f);
1.269 +
1.270 + //----------
1.271 + // body
1.272 +
1.273 + const uint64_t * blocks = (const uint64_t *)(data);
1.274 +
1.275 + for(int i = 0; i < nblocks; i++)
1.276 + {
1.277 + uint64_t k1 = getblock(blocks,i*2+0);
1.278 + uint64_t k2 = getblock(blocks,i*2+1);
1.279 +
1.280 + k1 *= c1; k1 = ROTL64(k1,31); k1 *= c2; h1 ^= k1;
1.281 +
1.282 + h1 = ROTL64(h1,27); h1 += h2; h1 = h1*5+0x52dce729;
1.283 +
1.284 + k2 *= c2; k2 = ROTL64(k2,33); k2 *= c1; h2 ^= k2;
1.285 +
1.286 + h2 = ROTL64(h2,31); h2 += h1; h2 = h2*5+0x38495ab5;
1.287 + }
1.288 +
1.289 + //----------
1.290 + // tail
1.291 +
1.292 + const uint8_t * tail = (const uint8_t*)(data + nblocks*16);
1.293 +
1.294 + uint64_t k1 = 0;
1.295 + uint64_t k2 = 0;
1.296 +
1.297 + switch(len & 15)
1.298 + {
1.299 + case 15: k2 ^= uint64_t(tail[14]) << 48;
1.300 + case 14: k2 ^= uint64_t(tail[13]) << 40;
1.301 + case 13: k2 ^= uint64_t(tail[12]) << 32;
1.302 + case 12: k2 ^= uint64_t(tail[11]) << 24;
1.303 + case 11: k2 ^= uint64_t(tail[10]) << 16;
1.304 + case 10: k2 ^= uint64_t(tail[ 9]) << 8;
1.305 + case 9: k2 ^= uint64_t(tail[ 8]) << 0;
1.306 + k2 *= c2; k2 = ROTL64(k2,33); k2 *= c1; h2 ^= k2;
1.307 +
1.308 + case 8: k1 ^= uint64_t(tail[ 7]) << 56;
1.309 + case 7: k1 ^= uint64_t(tail[ 6]) << 48;
1.310 + case 6: k1 ^= uint64_t(tail[ 5]) << 40;
1.311 + case 5: k1 ^= uint64_t(tail[ 4]) << 32;
1.312 + case 4: k1 ^= uint64_t(tail[ 3]) << 24;
1.313 + case 3: k1 ^= uint64_t(tail[ 2]) << 16;
1.314 + case 2: k1 ^= uint64_t(tail[ 1]) << 8;
1.315 + case 1: k1 ^= uint64_t(tail[ 0]) << 0;
1.316 + k1 *= c1; k1 = ROTL64(k1,31); k1 *= c2; h1 ^= k1;
1.317 + };
1.318 +
1.319 + //----------
1.320 + // finalization
1.321 +
1.322 + h1 ^= len; h2 ^= len;
1.323 +
1.324 + h1 += h2;
1.325 + h2 += h1;
1.326 +
1.327 + h1 = fmix(h1);
1.328 + h2 = fmix(h2);
1.329 +
1.330 + h1 += h2;
1.331 + h2 += h1;
1.332 +
1.333 + ((uint64_t*)out)[0] = h1;
1.334 + ((uint64_t*)out)[1] = h2;
1.335 +}
1.336 +
1.337 +//-----------------------------------------------------------------------------
