dom/canvas/MurmurHash3.cpp

   1 //-----------------------------------------------------------------------------
   2 // MurmurHash3 was written by Austin Appleby, and is placed in the public
   3 // domain. The author hereby disclaims copyright to this source code.
   4
   5 // Note - The x86 and x64 versions do _not_ produce the same results, as the
   6 // algorithms are optimized for their respective platforms. You can still
   7 // compile and run any of them on any platform, but your performance with the
   8 // non-native version will be less than optimal.
   9
  10 #include "MurmurHash3.h"
  11 #include <stdlib.h>
  12
  13 namespace {
  14
  15 //-----------------------------------------------------------------------------
  16 // Platform-specific functions and macros
  17
  18 // Microsoft Visual Studio
  19
  20 #if defined(_MSC_VER)
  21
  22 #  define FORCE_INLINE __forceinline
  23
  24 #  define ROTL32(x, y) _rotl(x, y)
  25 #  define ROTL64(x, y) _rotl64(x, y)
  26
  27 #  define BIG_CONSTANT(x) (x)
  28
  29 // Other compilers
  30
  31 #else  // defined(_MSC_VER)
  32
  33 // We can't do always_inline, becasue -Werror -Wattribute will trigger
  34 // a "might not be able to inline" warning.
  35 //#define       FORCE_INLINE __attribute__((always_inline))
  36 #  define FORCE_INLINE inline
  37
  38 inline uint32_t rotl32(uint32_t x, int8_t r) {
  39   return (x << r) | (x >> (32 - r));
  40 }
  41
  42 inline uint64_t rotl64(uint64_t x, int8_t r) {
  43   return (x << r) | (x >> (64 - r));
  44 }
  45
  46 #  define ROTL32(x, y) rotl32(x, y)
  47 #  define ROTL64(x, y) rotl64(x, y)
  48
  49 #  define BIG_CONSTANT(x) (x##LLU)
  50
  51 #endif  // !defined(_MSC_VER)
  52
  53 //-----------------------------------------------------------------------------
  54 // Block read - if your platform needs to do endian-swapping or can only
  55 // handle aligned reads, do the conversion here
  56
  57 FORCE_INLINE uint32_t getblock(const uint32_t* p, int i) { return p[i]; }
  58
  59 FORCE_INLINE uint64_t getblock(const uint64_t* p, int i) { return p[i]; }
  60
  61 //-----------------------------------------------------------------------------
  62 // Finalization mix - force all bits of a hash block to avalanche
  63
  64 FORCE_INLINE uint32_t fmix(uint32_t h) {
  65   h ^= h >> 16;
  66   h *= 0x85ebca6b;
  67   h ^= h >> 13;
  68   h *= 0xc2b2ae35;
  69   h ^= h >> 16;
  70
  71   return h;
  72 }
  73
  74 //----------
  75
  76 FORCE_INLINE uint64_t fmix(uint64_t k) {
  77   k ^= k >> 33;
  78   k *= BIG_CONSTANT(0xff51afd7ed558ccd);
  79   k ^= k >> 33;
  80   k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
  81   k ^= k >> 33;
  82
  83   return k;
  84 }
  85
  86 }  // unnamed namespace
  87
  88 //-----------------------------------------------------------------------------
  89
  90 void MurmurHash3_x86_32(const void* key, int len, uint32_t seed, void* out) {
  91   const uint8_t* data = (const uint8_t*)key;
  92   const int nblocks = len / 4;
  93
  94   uint32_t h1 = seed;
  95
  96   const uint32_t c1 = 0xcc9e2d51;
  97   const uint32_t c2 = 0x1b873593;
  98
  99   //----------
 100   // body
 101
 102   const uint32_t* blocks = (const uint32_t*)(data + nblocks * 4);
 103
 104   for (int i = -nblocks; i; i++) {
 105     uint32_t k1 = getblock(blocks, i);
 106
 107     k1 *= c1;
 108     k1 = ROTL32(k1, 15);
 109     k1 *= c2;
 110
 111     h1 ^= k1;
 112     h1 = ROTL32(h1, 13);
 113     h1 = h1 * 5 + 0xe6546b64;
 114   }
 115
 116   //----------
 117   // tail
 118
 119   const uint8_t* tail = (const uint8_t*)(data + nblocks * 4);
 120
 121   uint32_t k1 = 0;
 122
 123   switch (len & 3) {
 124     case 3:
 125       k1 ^= tail[2] << 16;
 126     case 2:
 127       k1 ^= tail[1] << 8;
 128     case 1:
 129       k1 ^= tail[0];
 130       k1 *= c1;
 131       k1 = ROTL32(k1, 15);
 132       k1 *= c2;
 133       h1 ^= k1;
 134   }
 135
 136   //----------
 137   // finalization
 138
 139   h1 ^= len;
 140
 141   h1 = fmix(h1);
 142
 143   *(uint32_t*)out = h1;
 144 }
 145
 146 //-----------------------------------------------------------------------------
 147
 148 void MurmurHash3_x86_128(const void* key, const int len, uint32_t seed,
 149                          void* out) {
 150   const uint8_t* data = (const uint8_t*)key;
 151   const int nblocks = len / 16;
 152
 153   uint32_t h1 = seed;
 154   uint32_t h2 = seed;
 155   uint32_t h3 = seed;
 156   uint32_t h4 = seed;
 157
 158   const uint32_t c1 = 0x239b961b;
 159   const uint32_t c2 = 0xab0e9789;
 160   const uint32_t c3 = 0x38b34ae5;
 161   const uint32_t c4 = 0xa1e38b93;
 162
 163   //----------
 164   // body
 165
 166   const uint32_t* blocks = (const uint32_t*)(data + nblocks * 16);
 167
 168   for (int i = -nblocks; i; i++) {
 169     uint32_t k1 = getblock(blocks, i * 4 + 0);
 170     uint32_t k2 = getblock(blocks, i * 4 + 1);
 171     uint32_t k3 = getblock(blocks, i * 4 + 2);
 172     uint32_t k4 = getblock(blocks, i * 4 + 3);
 173
 174     k1 *= c1;
 175     k1 = ROTL32(k1, 15);
 176     k1 *= c2;
 177     h1 ^= k1;
 178
 179     h1 = ROTL32(h1, 19);
 180     h1 += h2;
 181     h1 = h1 * 5 + 0x561ccd1b;
 182
 183     k2 *= c2;
 184     k2 = ROTL32(k2, 16);
 185     k2 *= c3;
 186     h2 ^= k2;
 187
 188     h2 = ROTL32(h2, 17);
 189     h2 += h3;
 190     h2 = h2 * 5 + 0x0bcaa747;
 191
 192     k3 *= c3;
 193     k3 = ROTL32(k3, 17);
 194     k3 *= c4;
 195     h3 ^= k3;
 196
 197     h3 = ROTL32(h3, 15);
 198     h3 += h4;
 199     h3 = h3 * 5 + 0x96cd1c35;
 200
 201     k4 *= c4;
 202     k4 = ROTL32(k4, 18);
 203     k4 *= c1;
 204     h4 ^= k4;
 205
 206     h4 = ROTL32(h4, 13);
 207     h4 += h1;
 208     h4 = h4 * 5 + 0x32ac3b17;
 209   }
 210
 211   //----------
 212   // tail
 213
 214   const uint8_t* tail = (const uint8_t*)(data + nblocks * 16);
 215
 216   uint32_t k1 = 0;
 217   uint32_t k2 = 0;
 218   uint32_t k3 = 0;
 219   uint32_t k4 = 0;
 220
 221   switch (len & 15) {
 222     case 15:
 223       k4 ^= tail[14] << 16;
 224     case 14:
 225       k4 ^= tail[13] << 8;
 226     case 13:
 227       k4 ^= tail[12] << 0;
 228       k4 *= c4;
 229       k4 = ROTL32(k4, 18);
 230       k4 *= c1;
 231       h4 ^= k4;
 232
 233     case 12:
 234       k3 ^= tail[11] << 24;
 235     case 11:
 236       k3 ^= tail[10] << 16;
 237     case 10:
 238       k3 ^= tail[9] << 8;
 239     case 9:
 240       k3 ^= tail[8] << 0;
 241       k3 *= c3;
 242       k3 = ROTL32(k3, 17);
 243       k3 *= c4;
 244       h3 ^= k3;
 245
 246     case 8:
 247       k2 ^= tail[7] << 24;
 248     case 7:
 249       k2 ^= tail[6] << 16;
 250     case 6:
 251       k2 ^= tail[5] << 8;
 252     case 5:
 253       k2 ^= tail[4] << 0;
 254       k2 *= c2;
 255       k2 = ROTL32(k2, 16);
 256       k2 *= c3;
 257       h2 ^= k2;
 258
 259     case 4:
 260       k1 ^= tail[3] << 24;
 261     case 3:
 262       k1 ^= tail[2] << 16;
 263     case 2:
 264       k1 ^= tail[1] << 8;
 265     case 1:
 266       k1 ^= tail[0] << 0;
 267       k1 *= c1;
 268       k1 = ROTL32(k1, 15);
 269       k1 *= c2;
 270       h1 ^= k1;
 271   }
 272
 273   //----------
 274   // finalization
 275
 276   h1 ^= len;
 277   h2 ^= len;
 278   h3 ^= len;
 279   h4 ^= len;
 280
 281   h1 += h2;
 282   h1 += h3;
 283   h1 += h4;
 284   h2 += h1;
 285   h3 += h1;
 286   h4 += h1;
 287
 288   h1 = fmix(h1);
 289   h2 = fmix(h2);
 290   h3 = fmix(h3);
 291   h4 = fmix(h4);
 292
 293   h1 += h2;
 294   h1 += h3;
 295   h1 += h4;
 296   h2 += h1;
 297   h3 += h1;
 298   h4 += h1;
 299
 300   ((uint32_t*)out)[0] = h1;
 301   ((uint32_t*)out)[1] = h2;
 302   ((uint32_t*)out)[2] = h3;
 303   ((uint32_t*)out)[3] = h4;
 304 }
 305
 306 //-----------------------------------------------------------------------------
 307
 308 void MurmurHash3_x64_128(const void* key, const int len, const uint32_t seed,
 309                          void* out) {
 310   const uint8_t* data = (const uint8_t*)key;
 311   const int nblocks = len / 16;
 312
 313   uint64_t h1 = seed;
 314   uint64_t h2 = seed;
 315
 316   const uint64_t c1 = BIG_CONSTANT(0x87c37b91114253d5);
 317   const uint64_t c2 = BIG_CONSTANT(0x4cf5ad432745937f);
 318
 319   //----------
 320   // body
 321
 322   const uint64_t* blocks = (const uint64_t*)(data);
 323
 324   for (int i = 0; i < nblocks; i++) {
 325     uint64_t k1 = getblock(blocks, i * 2 + 0);
 326     uint64_t k2 = getblock(blocks, i * 2 + 1);
 327
 328     k1 *= c1;
 329     k1 = ROTL64(k1, 31);
 330     k1 *= c2;
 331     h1 ^= k1;
 332
 333     h1 = ROTL64(h1, 27);
 334     h1 += h2;
 335     h1 = h1 * 5 + 0x52dce729;
 336
 337     k2 *= c2;
 338     k2 = ROTL64(k2, 33);
 339     k2 *= c1;
 340     h2 ^= k2;
 341
 342     h2 = ROTL64(h2, 31);
 343     h2 += h1;
 344     h2 = h2 * 5 + 0x38495ab5;
 345   }
 346
 347   //----------
 348   // tail
 349
 350   const uint8_t* tail = (const uint8_t*)(data + nblocks * 16);
 351
 352   uint64_t k1 = 0;
 353   uint64_t k2 = 0;
 354
 355   switch (len & 15) {
 356     case 15:
 357       k2 ^= uint64_t(tail[14]) << 48;
 358     case 14:
 359       k2 ^= uint64_t(tail[13]) << 40;
 360     case 13:
 361       k2 ^= uint64_t(tail[12]) << 32;
 362     case 12:
 363       k2 ^= uint64_t(tail[11]) << 24;
 364     case 11:
 365       k2 ^= uint64_t(tail[10]) << 16;
 366     case 10:
 367       k2 ^= uint64_t(tail[9]) << 8;
 368     case 9:
 369       k2 ^= uint64_t(tail[8]) << 0;
 370       k2 *= c2;
 371       k2 = ROTL64(k2, 33);
 372       k2 *= c1;
 373       h2 ^= k2;
 374
 375     case 8:
 376       k1 ^= uint64_t(tail[7]) << 56;
 377     case 7:
 378       k1 ^= uint64_t(tail[6]) << 48;
 379     case 6:
 380       k1 ^= uint64_t(tail[5]) << 40;
 381     case 5:
 382       k1 ^= uint64_t(tail[4]) << 32;
 383     case 4:
 384       k1 ^= uint64_t(tail[3]) << 24;
 385     case 3:
 386       k1 ^= uint64_t(tail[2]) << 16;
 387     case 2:
 388       k1 ^= uint64_t(tail[1]) << 8;
 389     case 1:
 390       k1 ^= uint64_t(tail[0]) << 0;
 391       k1 *= c1;
 392       k1 = ROTL64(k1, 31);
 393       k1 *= c2;
 394       h1 ^= k1;
 395   }
 396
 397   //----------
 398   // finalization
 399
 400   h1 ^= len;
 401   h2 ^= len;
 402
 403   h1 += h2;
 404   h2 += h1;
 405
 406   h1 = fmix(h1);
 407   h2 = fmix(h2);
 408
 409   h1 += h2;
 410   h2 += h1;
 411
 412   ((uint64_t*)out)[0] = h1;
 413   ((uint64_t*)out)[1] = h2;
 414 }
 415
 416 //-----------------------------------------------------------------------------