ceph/src/rocksdb/util/hash.cc

   1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
   2 //  This source code is licensed under both the GPLv2 (found in the
   3 //  COPYING file in the root directory) and Apache 2.0 License
   4 //  (found in the LICENSE.Apache file in the root directory).
   5 //
   6 // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
   7 // Use of this source code is governed by a BSD-style license that can be
   8 // found in the LICENSE file. See the AUTHORS file for names of contributors.
   9
  10 #include <string.h>
  11 #include "util/coding.h"
  12 #include "util/hash.h"
  13 #include "util/util.h"
  14
  15 namespace rocksdb {
  16
  17 uint32_t Hash(const char* data, size_t n, uint32_t seed) {
  18   // Similar to murmur hash
  19   const uint32_t m = 0xc6a4a793;
  20   const uint32_t r = 24;
  21   const char* limit = data + n;
  22   uint32_t h = static_cast<uint32_t>(seed ^ (n * m));
  23
  24   // Pick up four bytes at a time
  25   while (data + 4 <= limit) {
  26     uint32_t w = DecodeFixed32(data);
  27     data += 4;
  28     h += w;
  29     h *= m;
  30     h ^= (h >> 16);
  31   }
  32
  33   // Pick up remaining bytes
  34   switch (limit - data) {
  35     // Note: The original hash implementation used data[i] << shift, which
  36     // promotes the char to int and then performs the shift. If the char is
  37     // negative, the shift is undefined behavior in C++. The hash algorithm is
  38     // part of the format definition, so we cannot change it; to obtain the same
  39     // behavior in a legal way we just cast to uint32_t, which will do
  40     // sign-extension. To guarantee compatibility with architectures where chars
  41     // are unsigned we first cast the char to int8_t.
  42     case 3:
  43       h += static_cast<uint32_t>(static_cast<int8_t>(data[2])) << 16;
  44       FALLTHROUGH_INTENDED;
  45     case 2:
  46       h += static_cast<uint32_t>(static_cast<int8_t>(data[1])) << 8;
  47       FALLTHROUGH_INTENDED;
  48     case 1:
  49       h += static_cast<uint32_t>(static_cast<int8_t>(data[0]));
  50       h *= m;
  51       h ^= (h >> r);
  52       break;
  53   }
  54   return h;
  55 }
  56
  57 }  // namespace rocksdb