1 /*
2 american fuzzy lop - hashing function
3 -------------------------------------
4
5 The hash32() function is a variant of MurmurHash3, a good
6 non-cryptosafe hashing function developed by Austin Appleby.
7
8 For simplicity, this variant does *NOT* accept buffer lengths
9 that are not divisible by 8 bytes. The 32-bit version is otherwise
10 similar to the original; the 64-bit one is a custom hack with
11 mostly-unproven properties.
12
13 Austin's original code is public domain.
14
15 Other code written and maintained by Michal Zalewski <lcamtuf@google.com>
16
17 Copyright 2016 Google Inc. All rights reserved.
18
19 Licensed under the Apache License, Version 2.0 (the "License");
20 you may not use this file except in compliance with the License.
21 You may obtain a copy of the License at:
22
23 http://www.apache.org/licenses/LICENSE-2.0
24
25 */
26
27 #ifndef _HAVE_HASH_H
28 #define _HAVE_HASH_H
29
30 #include "types.h"
31
32 #ifdef __x86_64__
33
34 #define ROL64(_x, _r) ((((u64)(_x)) << (_r)) | (((u64)(_x)) >> (64 - (_r))))
35
hash32(const void * key,u32 len,u32 seed)36 static inline u32 hash32(const void* key, u32 len, u32 seed) {
37
38 const u64* data = (u64*)key;
39 u64 h1 = seed ^ len;
40
41 len >>= 3;
42
43 while (len--) {
44
45 u64 k1 = *data++;
46
47 k1 *= 0x87c37b91114253d5ULL;
48 k1 = ROL64(k1, 31);
49 k1 *= 0x4cf5ad432745937fULL;
50
51 h1 ^= k1;
52 h1 = ROL64(h1, 27);
53 h1 = h1 * 5 + 0x52dce729;
54
55 }
56
57 h1 ^= h1 >> 33;
58 h1 *= 0xff51afd7ed558ccdULL;
59 h1 ^= h1 >> 33;
60 h1 *= 0xc4ceb9fe1a85ec53ULL;
61 h1 ^= h1 >> 33;
62
63 return h1;
64
65 }
66
67 #else
68
69 #define ROL32(_x, _r) ((((u32)(_x)) << (_r)) | (((u32)(_x)) >> (32 - (_r))))
70
hash32(const void * key,u32 len,u32 seed)71 static inline u32 hash32(const void* key, u32 len, u32 seed) {
72
73 const u32* data = (u32*)key;
74 u32 h1 = seed ^ len;
75
76 len >>= 2;
77
78 while (len--) {
79
80 u32 k1 = *data++;
81
82 k1 *= 0xcc9e2d51;
83 k1 = ROL32(k1, 15);
84 k1 *= 0x1b873593;
85
86 h1 ^= k1;
87 h1 = ROL32(h1, 13);
88 h1 = h1 * 5 + 0xe6546b64;
89
90 }
91
92 h1 ^= h1 >> 16;
93 h1 *= 0x85ebca6b;
94 h1 ^= h1 >> 13;
95 h1 *= 0xc2b2ae35;
96 h1 ^= h1 >> 16;
97
98 return h1;
99
100 }
101
102 #endif /* ^__x86_64__ */
103
104 #endif /* !_HAVE_HASH_H */
105