include/Hash.hpp

   1 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file. See the AUTHORS file for names of contributors.
   4
   5 #include <cstring>
   6
   7 namespace scx {
   8
   9 typedef unsigned int uint32_t;
  10
  11 inline uint32_t DecodeFixed32(const char* ptr) {
  12   if (true) { //port::kLittleEndian
  13     // Load the raw bytes
  14     uint32_t result;
  15     memcpy(&result, ptr, sizeof(result));  // gcc optimizes this to a plain load
  16     return result;
  17   } else {
  18     return ((static_cast<uint32_t>(ptr[0]))
  19             | (static_cast<uint32_t>(ptr[1]) << 8)
  20             | (static_cast<uint32_t>(ptr[2]) << 16)
  21             | (static_cast<uint32_t>(ptr[3]) << 24));
  22   }
  23 }
  24
  25 uint32_t Hash(const char* data, size_t n, uint32_t seed) {
  26   // Similar to murmur hash
  27   const uint32_t m = 0xc6a4a793;
  28   const uint32_t r = 24;
  29   const char* limit = data + n;
  30   uint32_t h = seed ^ (n * m);
  31
  32   // Pick up four bytes at a time
  33   while (data + 4 <= limit) {
  34     uint32_t w = DecodeFixed32(data);
  35     data += 4;
  36     h += w;
  37     h *= m;
  38     h ^= (h >> 16);
  39   }
  40
  41   // Pick up remaining bytes
  42   switch (limit - data) {
  43     case 3:
  44       h += data[2] << 16;
  45       // fall through
  46     case 2:
  47       h += data[1] << 8;
  48       // fall through
  49     case 1:
  50       h += data[0];
  51       h *= m;
  52       h ^= (h >> r);
  53       break;
  54   }
  55   return h;
  56 }
  57
  58
  59 }