1 /*
2 * Copyright 2023 Google LLC
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7 #include "src/core/SkChecksum.h"
8
9 #include <cstring>
10
11 // wyhash, a fast and good hash function, from https://github.com/wangyi-fudan/wyhash
12
13 // likely and unlikely macros
14 #if defined(__GNUC__) || defined(__INTEL_COMPILER) || defined(__clang__)
15 #define _likely_(x) __builtin_expect(x, 1)
16 #define _unlikely_(x) __builtin_expect(x, 0)
17 #else
18 #define _likely_(x) (x)
19 #define _unlikely_(x) (x)
20 #endif
21
22 // 128bit multiply function
_wymum(uint64_t * A,uint64_t * B)23 static inline void _wymum(uint64_t* A, uint64_t* B) {
24 #if defined(__SIZEOF_INT128__)
25 __uint128_t r = *A;
26 r *= *B;
27 *A = (uint64_t)r;
28 *B = (uint64_t)(r >> 64);
29 #elif defined(_MSC_VER) && defined(_M_X64)
30 *A = _umul128(*A, *B, B);
31 #else
32 uint64_t ha = *A >> 32, hb = *B >> 32, la = (uint32_t)*A, lb = (uint32_t)*B, hi, lo;
33 uint64_t rh = ha * hb, rm0 = ha * lb, rm1 = hb * la, rl = la * lb, t = rl + (rm0 << 32),
34 c = t < rl;
35 lo = t + (rm1 << 32);
36 c += lo < t;
37 hi = rh + (rm0 >> 32) + (rm1 >> 32) + c;
38 *A = lo;
39 *B = hi;
40 #endif
41 }
42
43 // multiply and xor mix function, aka MUM
_wymix(uint64_t A,uint64_t B)44 static inline uint64_t _wymix(uint64_t A, uint64_t B) {
45 _wymum(&A, &B);
46 return A ^ B;
47 }
48
49 // read functions
_wyr8(const uint8_t * p)50 static inline uint64_t _wyr8(const uint8_t* p) {
51 uint64_t v;
52 memcpy(&v, p, 8);
53 return v;
54 }
55
_wyr4(const uint8_t * p)56 static inline uint64_t _wyr4(const uint8_t* p) {
57 uint32_t v;
58 memcpy(&v, p, 4);
59 return v;
60 }
61
_wyr3(const uint8_t * p,size_t k)62 static inline uint64_t _wyr3(const uint8_t* p, size_t k) {
63 return (((uint64_t)p[0]) << 16) | (((uint64_t)p[k >> 1]) << 8) | p[k - 1];
64 }
65
66 // wyhash main function
wyhash(const void * key,size_t len,uint64_t seed,const uint64_t * secret)67 static inline uint64_t wyhash(const void* key, size_t len, uint64_t seed, const uint64_t* secret) {
68 const uint8_t* p = (const uint8_t*)key;
69 seed ^= _wymix(seed ^ secret[0], secret[1]);
70 uint64_t a, b;
71 if (_likely_(len <= 16)) {
72 if (_likely_(len >= 4)) {
73 a = (_wyr4(p) << 32) | _wyr4(p + ((len >> 3) << 2));
74 b = (_wyr4(p + len - 4) << 32) | _wyr4(p + len - 4 - ((len >> 3) << 2));
75 } else if (_likely_(len > 0)) {
76 a = _wyr3(p, len);
77 b = 0;
78 } else
79 a = b = 0;
80 } else {
81 size_t i = len;
82 if (_unlikely_(i > 48)) {
83 uint64_t see1 = seed, see2 = seed;
84 do {
85 seed = _wymix(_wyr8(p) ^ secret[1], _wyr8(p + 8) ^ seed);
86 see1 = _wymix(_wyr8(p + 16) ^ secret[2], _wyr8(p + 24) ^ see1);
87 see2 = _wymix(_wyr8(p + 32) ^ secret[3], _wyr8(p + 40) ^ see2);
88 p += 48;
89 i -= 48;
90 } while (_likely_(i > 48));
91 seed ^= see1 ^ see2;
92 }
93 while (_unlikely_(i > 16)) {
94 seed = _wymix(_wyr8(p) ^ secret[1], _wyr8(p + 8) ^ seed);
95 i -= 16;
96 p += 16;
97 }
98 a = _wyr8(p + i - 16);
99 b = _wyr8(p + i - 8);
100 }
101 a ^= secret[1];
102 b ^= seed;
103 _wymum(&a, &b);
104 return _wymix(a ^ secret[0] ^ len, b ^ secret[1]);
105 }
106
107 // the default secret parameters
108 static const uint64_t _wyp[4] = {
109 0xa0761d6478bd642full, 0xe7037ed1a0b428dbull, 0x8ebc6af09c88c6e3ull, 0x589965cc75374cc3ull};
110
111 namespace SkChecksum {
112
Hash32(const void * data,size_t bytes,uint32_t seed)113 uint32_t Hash32(const void *data, size_t bytes, uint32_t seed) {
114 return static_cast<uint32_t>(wyhash(data, bytes, seed, _wyp));
115 }
116
Hash64(const void * data,size_t bytes,uint64_t seed)117 uint64_t Hash64(const void *data, size_t bytes, uint64_t seed) {
118 return wyhash(data, bytes, seed, _wyp);
119 }
120
121 } // namespace SkChecksum
122