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 <string.h>
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 (limit - data >= 4) {
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