1331400Smav// Copyright (c) 2011 Google, Inc. 2331400Smav// 3331400Smav// Permission is hereby granted, free of charge, to any person obtaining a copy 4331400Smav// of this software and associated documentation files (the "Software"), to deal 5331400Smav// in the Software without restriction, including without limitation the rights 6331400Smav// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 7331400Smav// copies of the Software, and to permit persons to whom the Software is 8331400Smav// furnished to do so, subject to the following conditions: 9331400Smav// 10331400Smav// The above copyright notice and this permission notice shall be included in 11331400Smav// all copies or substantial portions of the Software. 12331400Smav// 13331400Smav// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 14331400Smav// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 15331400Smav// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 16331400Smav// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 17331400Smav// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 18331400Smav// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 19331400Smav// THE SOFTWARE. 20331400Smav 21331400Smav/* 22331400Smav * Copyright (c) 2017 by Delphix. All rights reserved. 23331400Smav */ 24331400Smav 25331400Smav#include <sys/cityhash.h> 26331400Smav 27331400Smav#define HASH_K1 0xb492b66fbe98f273ULL 28331400Smav#define HASH_K2 0x9ae16a3b2f90404fULL 29331400Smav 30331400Smav/* 31331400Smav * Bitwise right rotate. Normally this will compile to a single 32331400Smav * instruction. 33331400Smav */ 34331400Smavstatic inline uint64_t 35331400Smavrotate(uint64_t val, int shift) 36331400Smav{ 37331400Smav // Avoid shifting by 64: doing so yields an undefined result. 38331400Smav return (shift == 0 ? val : (val >> shift) | (val << (64 - shift))); 39331400Smav} 40331400Smav 41331400Smavstatic inline uint64_t 42331400Smavcityhash_helper(uint64_t u, uint64_t v, uint64_t mul) 43331400Smav{ 44331400Smav uint64_t a = (u ^ v) * mul; 45331400Smav a ^= (a >> 47); 46331400Smav uint64_t b = (v ^ a) * mul; 47331400Smav b ^= (b >> 47); 48331400Smav b *= mul; 49331400Smav return (b); 50331400Smav} 51331400Smav 52331400Smavuint64_t 53331400Smavcityhash4(uint64_t w1, uint64_t w2, uint64_t w3, uint64_t w4) 54331400Smav{ 55331400Smav uint64_t mul = HASH_K2 + 64; 56331400Smav uint64_t a = w1 * HASH_K1; 57331400Smav uint64_t b = w2; 58331400Smav uint64_t c = w4 * mul; 59331400Smav uint64_t d = w3 * HASH_K2; 60331400Smav return (cityhash_helper(rotate(a + b, 43) + rotate(c, 30) + d, 61331400Smav a + rotate(b + HASH_K2, 18) + c, mul)); 62331400Smav 63331400Smav} 64