hash.h 2.0 KB

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