1 | // Copyright (c) 2018 Kenton Varda and contributors |
2 | // Licensed under the MIT License: |
3 | // |
4 | // Permission is hereby granted, free of charge, to any person obtaining a copy |
5 | // of this software and associated documentation files (the "Software"), to deal |
6 | // in the Software without restriction, including without limitation the rights |
7 | // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
8 | // copies of the Software, and to permit persons to whom the Software is |
9 | // furnished to do so, subject to the following conditions: |
10 | // |
11 | // The above copyright notice and this permission notice shall be included in |
12 | // all copies or substantial portions of the Software. |
13 | // |
14 | // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
15 | // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
16 | // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
17 | // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
18 | // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
19 | // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN |
20 | // THE SOFTWARE. |
21 | |
22 | #include "hash.h" |
23 | |
24 | namespace kj { |
25 | namespace _ { // private |
26 | |
27 | uint HashCoder::operator*(ArrayPtr<const byte> s) const { |
28 | // murmur2 adapted from libc++ source code. |
29 | // |
30 | // TODO(perf): Use CityHash or FarmHash on 64-bit machines? They seem optimized for x86-64; what |
31 | // about ARM? Ask Vlad for advice. |
32 | |
33 | constexpr uint m = 0x5bd1e995; |
34 | constexpr uint r = 24; |
35 | uint h = s.size(); |
36 | const byte* data = s.begin(); |
37 | uint len = s.size(); |
38 | for (; len >= 4; data += 4, len -= 4) { |
39 | uint k; |
40 | memcpy(&k, data, sizeof(k)); |
41 | k *= m; |
42 | k ^= k >> r; |
43 | k *= m; |
44 | h *= m; |
45 | h ^= k; |
46 | } |
47 | switch (len) { |
48 | case 3: |
49 | h ^= data[2] << 16; |
50 | // fallthrough |
51 | case 2: |
52 | h ^= data[1] << 8; |
53 | // fallthrough |
54 | case 1: |
55 | h ^= data[0]; |
56 | h *= m; |
57 | } |
58 | h ^= h >> 13; |
59 | h *= m; |
60 | h ^= h >> 15; |
61 | return h; |
62 | } |
63 | |
64 | } // namespace _ (private) |
65 | } // namespace kj |
66 | |