]>
Commit | Line | Data |
---|---|---|
b4c522fa IB |
1 | /** |
2 | * Compiler implementation of the D programming language | |
3 | * http://dlang.org | |
4 | * | |
a3b38b77 | 5 | * Copyright: Copyright (C) 1999-2021 by The D Language Foundation, All Rights Reserved |
b4c522fa IB |
6 | * Authors: Martin Nowak, Walter Bright, http://www.digitalmars.com |
7 | * License: $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost License 1.0) | |
8 | * Source: $(DMDSRC root/_hash.h) | |
9 | */ | |
10 | ||
11 | #pragma once | |
12 | ||
f9ab59ff | 13 | #include "dsystem.h" // uint{8|16|32}_t |
b4c522fa IB |
14 | |
15 | // MurmurHash2 was written by Austin Appleby, and is placed in the public | |
16 | // domain. The author hereby disclaims copyright to this source code. | |
17 | // https://sites.google.com/site/murmurhash/ | |
18 | static inline uint32_t calcHash(const uint8_t *data, size_t len) | |
19 | { | |
20 | // 'm' and 'r' are mixing constants generated offline. | |
21 | // They're not really 'magic', they just happen to work well. | |
22 | ||
23 | const uint32_t m = 0x5bd1e995; | |
24 | const int r = 24; | |
25 | ||
26 | // Initialize the hash to a 'random' value | |
27 | ||
28 | uint32_t h = (uint32_t)len; | |
29 | ||
30 | // Mix 4 bytes at a time into the hash | |
31 | ||
32 | while(len >= 4) | |
33 | { | |
34 | uint32_t k = data[3] << 24 | data[2] << 16 | data[1] << 8 | data[0]; | |
35 | ||
36 | k *= m; | |
37 | k ^= k >> r; | |
38 | k *= m; | |
39 | ||
40 | h *= m; | |
41 | h ^= k; | |
42 | ||
43 | data += 4; | |
44 | len -= 4; | |
45 | } | |
46 | ||
47 | // Handle the last few bytes of the input array | |
48 | ||
49 | switch(len & 3) | |
50 | { | |
51 | case 3: h ^= data[2] << 16; /* fall through */ | |
52 | case 2: h ^= data[1] << 8; /* fall through */ | |
53 | case 1: h ^= data[0]; | |
54 | h *= m; | |
55 | } | |
56 | ||
57 | // Do a few final mixes of the hash to ensure the last few | |
58 | // bytes are well-incorporated. | |
59 | ||
60 | h ^= h >> 13; | |
61 | h *= m; | |
62 | h ^= h >> 15; | |
63 | ||
64 | return h; | |
65 | } | |
66 | ||
67 | static inline uint32_t calcHash(const char *data, size_t len) | |
68 | { | |
69 | return calcHash((const uint8_t *)data, len); | |
70 | } | |
71 | ||
72 | // combine and mix two words (boost::hash_combine) | |
73 | static inline size_t mixHash(size_t h, size_t k) | |
74 | { | |
75 | return h ^ (k + 0x9e3779b9 + (h << 6) + (h >> 2)); | |
76 | } |