Inside Bitcoin

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
11namespace leveldb {
12
13uint32_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