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 namespace leveldb {
12 13 uint32_t Hash(const char* data, size_t n, uint32_t seed) {
14 // Similar to murmur hash
15 const uint32_t m = 0xc6a4a793;
16 const uint32_t r = 24;
17 const char* limit = data + n;
18 uint32_t h = seed ^ (n * m);
19 20 // Pick up four bytes at a time
21 while (limit - data >= 4) {
22 uint32_t w = DecodeFixed32(data);
23 data += 4;
24 h += w;
25 h *= m;
26 h ^= (h >> 16);
27 }
28 29 // Pick up remaining bytes
30 switch (limit - data) {
31 case 3:
32 h += static_cast<uint8_t>(data[2]) << 16;
33 [[fallthrough]];
34 case 2:
35 h += static_cast<uint8_t>(data[1]) << 8;
36 [[fallthrough]];
37 case 1:
38 h += static_cast<uint8_t>(data[0]);
39 h *= m;
40 h ^= (h >> r);
41 break;
42 }
43 return h;
44 }
45 46 } // namespace leveldb
47