blob: 5a561b82ab0d2a0bc7c94e955021bebe582f511d [file] [log] [blame]
 /* * Copyright 2023 Google LLC * * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. */ #include "src/core/SkChecksum.h" // wyhash, a fast and good hash function, from https://github.com/wangyi-fudan/wyhash // likely and unlikely macros #if defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__clang__) #define _likely_(x) __builtin_expect(x, 1) #define _unlikely_(x) __builtin_expect(x, 0) #else #define _likely_(x) (x) #define _unlikely_(x) (x) #endif // 128bit multiply function static inline void _wymum(uint64_t* A, uint64_t* B) { #if defined(__SIZEOF_INT128__) __uint128_t r = *A; r *= *B; *A = (uint64_t)r; *B = (uint64_t)(r >> 64); #elif defined(_MSC_VER) && defined(_M_X64) *A = _umul128(*A, *B, B); #else uint64_t ha = *A >> 32, hb = *B >> 32, la = (uint32_t)*A, lb = (uint32_t)*B, hi, lo; uint64_t rh = ha * hb, rm0 = ha * lb, rm1 = hb * la, rl = la * lb, t = rl + (rm0 << 32), c = t < rl; lo = t + (rm1 << 32); c += lo < t; hi = rh + (rm0 >> 32) + (rm1 >> 32) + c; *A = lo; *B = hi; #endif } // multiply and xor mix function, aka MUM static inline uint64_t _wymix(uint64_t A, uint64_t B) { _wymum(&A, &B); return A ^ B; } // read functions static inline uint64_t _wyr8(const uint8_t* p) { uint64_t v; memcpy(&v, p, 8); return v; } static inline uint64_t _wyr4(const uint8_t* p) { uint32_t v; memcpy(&v, p, 4); return v; } static inline uint64_t _wyr3(const uint8_t* p, size_t k) { return (((uint64_t)p[0]) << 16) | (((uint64_t)p[k >> 1]) << 8) | p[k - 1]; } // wyhash main function static inline uint64_t wyhash(const void* key, size_t len, uint64_t seed, const uint64_t* secret) { const uint8_t* p = (const uint8_t*)key; seed ^= _wymix(seed ^ secret[0], secret[1]); uint64_t a, b; if (_likely_(len <= 16)) { if (_likely_(len >= 4)) { a = (_wyr4(p) << 32) | _wyr4(p + ((len >> 3) << 2)); b = (_wyr4(p + len - 4) << 32) | _wyr4(p + len - 4 - ((len >> 3) << 2)); } else if (_likely_(len > 0)) { a = _wyr3(p, len); b = 0; } else a = b = 0; } else { size_t i = len; if (_unlikely_(i > 48)) { uint64_t see1 = seed, see2 = seed; do { seed = _wymix(_wyr8(p) ^ secret[1], _wyr8(p + 8) ^ seed); see1 = _wymix(_wyr8(p + 16) ^ secret[2], _wyr8(p + 24) ^ see1); see2 = _wymix(_wyr8(p + 32) ^ secret[3], _wyr8(p + 40) ^ see2); p += 48; i -= 48; } while (_likely_(i > 48)); seed ^= see1 ^ see2; } while (_unlikely_(i > 16)) { seed = _wymix(_wyr8(p) ^ secret[1], _wyr8(p + 8) ^ seed); i -= 16; p += 16; } a = _wyr8(p + i - 16); b = _wyr8(p + i - 8); } a ^= secret[1]; b ^= seed; _wymum(&a, &b); return _wymix(a ^ secret[0] ^ len, b ^ secret[1]); } // the default secret parameters static const uint64_t _wyp[4] = { 0xa0761d6478bd642full, 0xe7037ed1a0b428dbull, 0x8ebc6af09c88c6e3ull, 0x589965cc75374cc3ull}; namespace SkChecksum { uint32_t Hash32(const void *data, size_t bytes, uint32_t seed) { return static_cast(wyhash(data, bytes, seed, _wyp)); } uint64_t Hash64(const void *data, size_t bytes, uint64_t seed) { return wyhash(data, bytes, seed, _wyp); } } // namespace SkChecksum