ceph/src/rocksdb/util/hash.cc

   1 //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
   2 //  This source code is licensed under the BSD-style license found in the
   3 //  LICENSE file in the root directory of this source tree. An additional grant
   4 //  of patent rights can be found in the PATENTS file in the same 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
  14 namespace rocksdb {
  15
  16 // This function may intentionally do a left shift on a -ve number
  17 #if __clang_major__ > 3 || (__clang_major__ == 3 && __clang_minor__ >= 9)
  18 __attribute__((__no_sanitize__("undefined")))
  19 #elif __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 9)
  20 __attribute__((__no_sanitize_undefined__))
  21 #endif
  22 uint32_t Hash(const char* data, size_t n, uint32_t seed) {
  23   // Similar to murmur hash
  24   const uint32_t m = 0xc6a4a793;
  25   const uint32_t r = 24;
  26   const char* limit = data + n;
  27   uint32_t h = static_cast<uint32_t>(seed ^ (n * m));
  28
  29   // Pick up four bytes at a time
  30   while (data + 4 <= limit) {
  31     uint32_t w = DecodeFixed32(data);
  32     data += 4;
  33     h += w;
  34     h *= m;
  35     h ^= (h >> 16);
  36   }
  37
  38   // Pick up remaining bytes
  39   switch (limit - data) {
  40     // Note: It would be better if this was cast to unsigned char, but that
  41     // would be a disk format change since we previously didn't have any cast
  42     // at all (so gcc used signed char).
  43     // To understand the difference between shifting unsigned and signed chars,
  44     // let's use 250 as an example. unsigned char will be 250, while signed char
  45     // will be -6. Bit-wise, they are equivalent: 11111010. However, when
  46     // converting negative number (signed char) to int, it will be converted
  47     // into negative int (of equivalent value, which is -6), while converting
  48     // positive number (unsigned char) will be converted to 250. Bitwise,
  49     // this looks like this:
  50     // signed char 11111010 -> int 11111111111111111111111111111010
  51     // unsigned char 11111010 -> int 00000000000000000000000011111010
  52     case 3:
  53       h += static_cast<uint32_t>(static_cast<signed char>(data[2]) << 16);
  54     // fall through
  55     case 2:
  56       h += static_cast<uint32_t>(static_cast<signed char>(data[1]) << 8);
  57     // fall through
  58     case 1:
  59       h += static_cast<uint32_t>(static_cast<signed char>(data[0]));
  60       h *= m;
  61       h ^= (h >> r);
  62       break;
  63   }
  64   return h;
  65 }
  66
  67 }  // namespace rocksdb