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 by Michal Zalewski 16 17 Copyright 2016 Google Inc. All rights reserved. 18 Copyright 2019-2024 AFLplusplus Project. All rights reserved. 19 20 Licensed under the Apache License, Version 2.0 (the "License"); 21 you may not use this file except in compliance with the License. 22 You may obtain a copy of the License at: 23 24 https://www.apache.org/licenses/LICENSE-2.0 25 26 */ 27 28 #ifndef _HAVE_HASH_H 29 #define _HAVE_HASH_H 30 31 #include "types.h" 32 33 u32 hash32(u8 *key, u32 len, u32 seed); 34 u64 hash64(u8 *key, u32 len, u64 seed); 35 36 #if 0 37 38 The following code is disabled because xxh3 is 30% faster 39 40 #ifdef __x86_64__ 41 42 #define ROL64(_x, _r) ((((u64)(_x)) << (_r)) | (((u64)(_x)) >> (64 - (_r)))) 43 44 static inline u32 hash32(u8 *key, u32 len, u32 seed) { 45 46 const u64 *data = (u64 *)key; 47 u64 h1 = seed ^ len; 48 49 len >>= 3; 50 51 while (len--) { 52 53 u64 k1 = *data++; 54 55 k1 *= 0x87c37b91114253d5ULL; 56 k1 = ROL64(k1, 31); 57 k1 *= 0x4cf5ad432745937fULL; 58 59 h1 ^= k1; 60 h1 = ROL64(h1, 27); 61 h1 = h1 * 5 + 0x52dce729; 62 63 } 64 65 h1 ^= h1 >> 33; 66 h1 *= 0xff51afd7ed558ccdULL; 67 h1 ^= h1 >> 33; 68 h1 *= 0xc4ceb9fe1a85ec53ULL; 69 h1 ^= h1 >> 33; 70 71 return h1; 72 73 } 74 75 #else 76 77 #define ROL32(_x, _r) ((((u32)(_x)) << (_r)) | (((u32)(_x)) >> (32 - (_r)))) 78 79 static inline u32 hash32(const void *key, u32 len, u32 seed) { 80 81 const u32 *data = (u32 *)key; 82 u32 h1 = seed ^ len; 83 84 len >>= 2; 85 86 while (len--) { 87 88 u32 k1 = *data++; 89 90 k1 *= 0xcc9e2d51; 91 k1 = ROL32(k1, 15); 92 k1 *= 0x1b873593; 93 94 h1 ^= k1; 95 h1 = ROL32(h1, 13); 96 h1 = h1 * 5 + 0xe6546b64; 97 98 } 99 100 h1 ^= h1 >> 16; 101 h1 *= 0x85ebca6b; 102 h1 ^= h1 >> 13; 103 h1 *= 0xc2b2ae35; 104 h1 ^= h1 >> 16; 105 106 return h1; 107 108 } 109 110 #endif /* ^__x86_64__ */ 111 #endif 112 113 #endif /* !_HAVE_HASH_H */ 114 115