]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |