Dogcows Code - chaz/yoink/blob - src/Moof/Hash.cc

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