Dogcows Code - chaz/yoink/blob - src/moof/hash.cc

   1
   2 /*]  Copyright (c) 2009-2011, Charles McGarvey  [*****************************
   3 **]  All rights reserved.
   4 *
   5 * Distributable under the terms and conditions of the 2-clause BSD license;
   6 * see the file COPYING for a complete text of the license.
   7 *
   8 *****************************************************************************/
   9
  10 #include "hash.hh"
  11
  12
  13 namespace moof {
  14
  15
  16 // MurmurHash2, by Austin Appleby
  17 // http://murmurhash.googlepages.com/
  18
  19 // This function is in the public domain.
  20
  21 // Note - This code makes a few assumptions about how your machine behaves -
  22
  23 // 1. We can read a 4-byte value from any address without crashing
  24 // 2. sizeof(int) == 4
  25
  26 // And it has a few limitations -
  27
  28 // 1. It will not work incrementally.
  29 // 2. It will not produce the same results on little-endian and big-endian
  30 //    machines.
  31
  32 unsigned
  33 hash_function::operator()(const void* key, int len, unsigned int seed) const
  34 {
  35         // 'm' and 'r' are mixing constants generated offline.
  36         // They're not really 'magic', they just happen to work well.
  37
  38         const unsigned int m = 0x5bd1e995;
  39         const int r = 24;
  40
  41         // Initialize the hash to a 'random' value
  42
  43         unsigned int h = seed ^ len;
  44
  45         // Mix 4 bytes at a time into the hash
  46
  47         const unsigned char* data = (const unsigned char*)key;
  48
  49         while (len >= 4)
  50         {
  51                 unsigned int k = *(unsigned int*)data;
  52
  53                 k *= m;
  54                 k ^= k >> r;
  55                 k *= m;
  56
  57                 h *= m;
  58                 h ^= k;
  59
  60                 data += 4;
  61                 len -= 4;
  62         }
  63
  64         // Handle the last few bytes of the input array
  65
  66         switch (len)
  67         {
  68         case 3: h ^= data[2] << 16;
  69         case 2: h ^= data[1] << 8;
  70         case 1: h ^= data[0];
  71                 h *= m;
  72         };
  73
  74         // Do a few final mixes of the hash to ensure the last few
  75         // bytes are well-incorporated.
  76
  77         h ^= h >> 13;
  78         h *= m;
  79         h ^= h >> 15;
  80
  81         return h;
  82 }
  83
  84
  85 } // namespace moof
  86