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 "util/hash.h" |
6 | |
7 | #include <cstring> |
8 | |
9 | #include "util/coding.h" |
10 | |
11 | // The FALLTHROUGH_INTENDED macro can be used to annotate implicit fall-through |
12 | // between switch labels. The real definition should be provided externally. |
13 | // This one is a fallback version for unsupported compilers. |
14 | #ifndef FALLTHROUGH_INTENDED |
15 | #define FALLTHROUGH_INTENDED \ |
16 | do { \ |
17 | } while (0) |
18 | #endif |
19 | |
20 | namespace leveldb { |
21 | |
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 = 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 | case 3: |
41 | h += static_cast<uint8_t>(data[2]) << 16; |
42 | FALLTHROUGH_INTENDED; |
43 | case 2: |
44 | h += static_cast<uint8_t>(data[1]) << 8; |
45 | FALLTHROUGH_INTENDED; |
46 | case 1: |
47 | h += static_cast<uint8_t>(data[0]); |
48 | h *= m; |
49 | h ^= (h >> r); |
50 | break; |
51 | } |
52 | return h; |
53 | } |
54 | |
55 | } // namespace leveldb |
56 | |