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 
Hash(const char * data,size_t n,uint32_t seed)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