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
24namespace kj {
25namespace _ { // private
26
27uint 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