hash.c++ (2033B)
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 KJ_FALLTHROUGH; 51 case 2: 52 h ^= data[1] << 8; 53 KJ_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