GCS  0.2.3
gu_hash.h
1 // Copyright (C) 2012 Codership Oy <info@codership.com>
2 
22 #ifndef _gu_hash_h_
23 #define _gu_hash_h_
24 
25 #ifdef __cplusplus
26 extern "C" {
27 #endif
28 
29 #include "gu_fnv.h"
30 #include "gu_mmh3.h"
31 #include "gu_spooky.h"
32 
33 /*
34  * General purpose globally consistent _fast_ hash, if in doubt use that.
35  */
36 
37 /* This is to hash multipart message */
38 #define gu_hash_t gu_mmh128_ctx_t
39 #define gu_hash_init(_hash) gu_mmh128_init(_hash)
40 #define gu_hash_append(_hash, _msg, _len) gu_mmh128_append(_hash, _msg, _len)
41 #define gu_hash_get128(_hash, _res) gu_mmh128_get(_hash, _res)
42 #define gu_hash_get64(_hash) gu_mmh128_get64(_hash)
43 #define gu_hash_get32(_hash) gu_mmh128_get32(_hash)
44 
45 /* This is to hash a whole message in one go */
46 #define gu_hash128(_msg, _len, _res) gu_mmh128(_msg, _len, _res)
47 #define gu_hash64(_msg, _len) gu_mmh128_64(_msg, _len)
48 #define gu_hash32(_msg, _len) gu_mmh128_32(_msg, _len)
49 
50 /*
51  * Hash optimized for speed, can't do multipart messages, but should still
52  * be usable as global identifier
53  */
54 
55 #define GU_SHORT64_LIMIT 16
56 #define GU_MEDIUM64_LIMIT 512
57 
58 static GU_INLINE void
59 gu_fast_hash128 (const void* const msg, size_t const len, void* const res)
60 {
61  if (len < GU_MEDIUM64_LIMIT)
62  {
63  gu_mmh128 (msg, len, res);
64  }
65  else
66  {
67  gu_spooky128 (msg, len, res);
68  }
69 }
70 
71 static GU_FORCE_INLINE uint64_t
72 gu_fast_hash64_short (const void* const msg, size_t const len)
73 {
74  uint64_t res = GU_FNV64_SEED;
75  gu_fnv64a_internal (msg, len, &res);
76  /* mix to improve avalanche effect */
77  res *= GU_ROTL64(res, 56);
78  return res ^ GU_ROTL64(res, 43);
79 }
80 
81 #define gu_fast_hash64_medium gu_mmh128_64
82 #define gu_fast_hash64_long gu_spooky64
83 
84 static GU_INLINE uint64_t
85 gu_fast_hash64 (const void* const msg, size_t const len)
86 {
87  if (len < GU_SHORT64_LIMIT)
88  {
89  return gu_fast_hash64_short (msg, len);
90  }
91  else if (len < GU_MEDIUM64_LIMIT)
92  {
93  return gu_fast_hash64_medium (msg, len);
94  }
95  else
96  {
97  return gu_fast_hash64_long (msg, len);
98  }
99 }
100 
101 #define gu_fast_hash32_short gu_mmh32
102 #define gu_fast_hash32_medium gu_mmh128_32
103 #define gu_fast_hash32_long gu_spooky32
104 
105 #define GU_SHORT32_LIMIT 32
106 #define GU_MEDIUM32_LIMIT 512
107 
108 static GU_INLINE uint32_t
109 gu_fast_hash32 (const void* const msg, size_t const len)
110 {
111  if (len < GU_SHORT32_LIMIT)
112  {
113  return gu_fast_hash32_short (msg, len);
114  }
115  else if (len < GU_MEDIUM32_LIMIT)
116  {
117  return gu_fast_hash32_medium (msg, len);
118  }
119  else
120  {
121  return gu_fast_hash32_long (msg, len);
122  }
123 }
124 
125 /*
126  * Platform-optimized hashes only for local hash tables, don't produce globally
127  * consistent results. No 128-bit version for obvious reasons.
128  *
129  * Resulting gu_table_hash() will be the fastest hash function returning size_t
130  */
131 
132 #if GU_WORDSIZE == 64
133 
134 #define gu_table_hash gu_fast_hash64 /* size_t is normally 64-bit here */
135 
136 #elif GU_WORDSIZE == 32
137 
138 /* on 32-bit platform MurmurHash32 is only insignificantly slower than FNV32a
139  * on messages < 10 bytes but produces far better hash. */
140 #define gu_table_hash gu_mmh32 /* size_t is normally 32-bit here */
141 
142 #else /* GU_WORDSIZE neither 64 nor 32 bits */
143 # error Unsupported wordsize!
144 #endif
145 
146 #ifdef __cplusplus
147 }
148 #endif
149 
150 #endif /* _gu_hash_h_ */
151