endian: add constant versions.
[ccan] / ccan / hash / hash.h
1 /* CC0 (Public domain) - see LICENSE file for details */
2 #ifndef CCAN_HASH_H
3 #define CCAN_HASH_H
4 #include "config.h"
5 #include <stdint.h>
6 #include <stdlib.h>
7 #include <ccan/build_assert/build_assert.h>
8
9 /* Stolen mostly from: lookup3.c, by Bob Jenkins, May 2006, Public Domain.
10  * 
11  * http://burtleburtle.net/bob/c/lookup3.c
12  */
13
14 /**
15  * hash - fast hash of an array for internal use
16  * @p: the array or pointer to first element
17  * @num: the number of elements to hash
18  * @base: the base number to roll into the hash (usually 0)
19  *
20  * The memory region pointed to by p is combined with the base to form
21  * a 32-bit hash.
22  *
23  * This hash will have different results on different machines, so is
24  * only useful for internal hashes (ie. not hashes sent across the
25  * network or saved to disk).
26  *
27  * It may also change with future versions: it could even detect at runtime
28  * what the fastest hash to use is.
29  *
30  * See also: hash64, hash_stable.
31  *
32  * Example:
33  *      #include <ccan/hash/hash.h>
34  *      #include <err.h>
35  *      #include <stdio.h>
36  *      #include <string.h>
37  *
38  *      // Simple demonstration: idential strings will have the same hash, but
39  *      // two different strings will probably not.
40  *      int main(int argc, char *argv[])
41  *      {
42  *              uint32_t hash1, hash2;
43  *
44  *              if (argc != 3)
45  *                      err(1, "Usage: %s <string1> <string2>", argv[0]);
46  *
47  *              hash1 = hash(argv[1], strlen(argv[1]), 0);
48  *              hash2 = hash(argv[2], strlen(argv[2]), 0);
49  *              printf("Hash is %s\n", hash1 == hash2 ? "same" : "different");
50  *              return 0;
51  *      }
52  */
53 #define hash(p, num, base) hash_any((p), (num)*sizeof(*(p)), (base))
54
55 /**
56  * hash_stable - hash of an array for external use
57  * @p: the array or pointer to first element
58  * @num: the number of elements to hash
59  * @base: the base number to roll into the hash (usually 0)
60  *
61  * The array of simple integer types pointed to by p is combined with
62  * the base to form a 32-bit hash.
63  *
64  * This hash will have the same results on different machines, so can
65  * be used for external hashes (ie. hashes sent across the network or
66  * saved to disk).  The results will not change in future versions of
67  * this module.
68  *
69  * Note that it is only legal to hand an array of simple integer types
70  * to this hash (ie. char, uint16_t, int64_t, etc).  In these cases,
71  * the same values will have the same hash result, even though the
72  * memory representations of integers depend on the machine
73  * endianness.
74  *
75  * See also:
76  *      hash64_stable
77  *
78  * Example:
79  *      #include <ccan/hash/hash.h>
80  *      #include <err.h>
81  *      #include <stdio.h>
82  *      #include <string.h>
83  *
84  *      int main(int argc, char *argv[])
85  *      {
86  *              if (argc != 2)
87  *                      err(1, "Usage: %s <string-to-hash>", argv[0]);
88  *
89  *              printf("Hash stable result is %u\n",
90  *                     hash_stable(argv[1], strlen(argv[1]), 0));
91  *              return 0;
92  *      }
93  */
94 #define hash_stable(p, num, base)                                       \
95         (BUILD_ASSERT_OR_ZERO(sizeof(*(p)) == 8 || sizeof(*(p)) == 4    \
96                               || sizeof(*(p)) == 2 || sizeof(*(p)) == 1) + \
97          sizeof(*(p)) == 8 ? hash_stable_64((p), (num), (base))         \
98          : sizeof(*(p)) == 4 ? hash_stable_32((p), (num), (base))       \
99          : sizeof(*(p)) == 2 ? hash_stable_16((p), (num), (base))       \
100          : hash_stable_8((p), (num), (base)))
101
102 /**
103  * hash_u32 - fast hash an array of 32-bit values for internal use
104  * @key: the array of uint32_t
105  * @num: the number of elements to hash
106  * @base: the base number to roll into the hash (usually 0)
107  *
108  * The array of uint32_t pointed to by @key is combined with the base
109  * to form a 32-bit hash.  This is 2-3 times faster than hash() on small
110  * arrays, but the advantage vanishes over large hashes.
111  *
112  * This hash will have different results on different machines, so is
113  * only useful for internal hashes (ie. not hashes sent across the
114  * network or saved to disk).
115  */
116 uint32_t hash_u32(const uint32_t *key, size_t num, uint32_t base);
117
118 /**
119  * hash_string - very fast hash of an ascii string
120  * @str: the nul-terminated string
121  *
122  * The string is hashed, using a hash function optimized for ASCII and
123  * similar strings.  It's weaker than the other hash functions.
124  *
125  * This hash may have different results on different machines, so is
126  * only useful for internal hashes (ie. not hashes sent across the
127  * network or saved to disk).  The results will be different from the
128  * other hash functions in this module, too.
129  */
130 static inline uint32_t hash_string(const char *string)
131 {
132         /* This is Karl Nelson <kenelson@ece.ucdavis.edu>'s X31 hash.
133          * It's a little faster than the (much better) lookup3 hash(): 56ns vs
134          * 84ns on my 2GHz Intel Core Duo 2 laptop for a 10 char string. */
135         uint32_t ret;
136
137         for (ret = 0; *string; string++)
138                 ret = (ret << 5) - ret + *string;
139
140         return ret;
141 }
142
143 /**
144  * hash64 - fast 64-bit hash of an array for internal use
145  * @p: the array or pointer to first element
146  * @num: the number of elements to hash
147  * @base: the 64-bit base number to roll into the hash (usually 0)
148  *
149  * The memory region pointed to by p is combined with the base to form
150  * a 64-bit hash.
151  *
152  * This hash will have different results on different machines, so is
153  * only useful for internal hashes (ie. not hashes sent across the
154  * network or saved to disk).
155  *
156  * It may also change with future versions: it could even detect at runtime
157  * what the fastest hash to use is.
158  *
159  * See also: hash.
160  *
161  * Example:
162  *      #include <ccan/hash/hash.h>
163  *      #include <err.h>
164  *      #include <stdio.h>
165  *      #include <string.h>
166  *
167  *      // Simple demonstration: idential strings will have the same hash, but
168  *      // two different strings will probably not.
169  *      int main(int argc, char *argv[])
170  *      {
171  *              uint64_t hash1, hash2;
172  *
173  *              if (argc != 3)
174  *                      err(1, "Usage: %s <string1> <string2>", argv[0]);
175  *
176  *              hash1 = hash64(argv[1], strlen(argv[1]), 0);
177  *              hash2 = hash64(argv[2], strlen(argv[2]), 0);
178  *              printf("Hash is %s\n", hash1 == hash2 ? "same" : "different");
179  *              return 0;
180  *      }
181  */
182 #define hash64(p, num, base) hash64_any((p), (num)*sizeof(*(p)), (base))
183
184 /**
185  * hash64_stable - 64 bit hash of an array for external use
186  * @p: the array or pointer to first element
187  * @num: the number of elements to hash
188  * @base: the base number to roll into the hash (usually 0)
189  *
190  * The array of simple integer types pointed to by p is combined with
191  * the base to form a 64-bit hash.
192  *
193  * This hash will have the same results on different machines, so can
194  * be used for external hashes (ie. hashes sent across the network or
195  * saved to disk).  The results will not change in future versions of
196  * this module.
197  *
198  * Note that it is only legal to hand an array of simple integer types
199  * to this hash (ie. char, uint16_t, int64_t, etc).  In these cases,
200  * the same values will have the same hash result, even though the
201  * memory representations of integers depend on the machine
202  * endianness.
203  *
204  * See also:
205  *      hash_stable
206  *
207  * Example:
208  *      #include <ccan/hash/hash.h>
209  *      #include <err.h>
210  *      #include <stdio.h>
211  *      #include <string.h>
212  *
213  *      int main(int argc, char *argv[])
214  *      {
215  *              if (argc != 2)
216  *                      err(1, "Usage: %s <string-to-hash>", argv[0]);
217  *
218  *              printf("Hash stable result is %llu\n",
219  *                     (long long)hash64_stable(argv[1], strlen(argv[1]), 0));
220  *              return 0;
221  *      }
222  */
223 #define hash64_stable(p, num, base)                                     \
224         (BUILD_ASSERT_OR_ZERO(sizeof(*(p)) == 8 || sizeof(*(p)) == 4    \
225                               || sizeof(*(p)) == 2 || sizeof(*(p)) == 1) + \
226          sizeof(*(p)) == 8 ? hash64_stable_64((p), (num), (base))       \
227          : sizeof(*(p)) == 4 ? hash64_stable_32((p), (num), (base))     \
228          : sizeof(*(p)) == 2 ? hash64_stable_16((p), (num), (base))     \
229          : hash64_stable_8((p), (num), (base)))
230
231
232 /**
233  * hashl - fast 32/64-bit hash of an array for internal use
234  * @p: the array or pointer to first element
235  * @num: the number of elements to hash
236  * @base: the base number to roll into the hash (usually 0)
237  *
238  * This is either hash() or hash64(), on 32/64 bit long machines.
239  */
240 #define hashl(p, num, base)                                             \
241         (BUILD_ASSERT_OR_ZERO(sizeof(long) == sizeof(uint32_t)          \
242                               || sizeof(long) == sizeof(uint64_t)) +    \
243         (sizeof(long) == sizeof(uint64_t)                               \
244          ? hash64((p), (num), (base)) : hash((p), (num), (base))))
245
246 /* Our underlying operations. */
247 uint32_t hash_any(const void *key, size_t length, uint32_t base);
248 uint32_t hash_stable_64(const void *key, size_t n, uint32_t base);
249 uint32_t hash_stable_32(const void *key, size_t n, uint32_t base);
250 uint32_t hash_stable_16(const void *key, size_t n, uint32_t base);
251 uint32_t hash_stable_8(const void *key, size_t n, uint32_t base);
252 uint64_t hash64_any(const void *key, size_t length, uint64_t base);
253 uint64_t hash64_stable_64(const void *key, size_t n, uint64_t base);
254 uint64_t hash64_stable_32(const void *key, size_t n, uint64_t base);
255 uint64_t hash64_stable_16(const void *key, size_t n, uint64_t base);
256 uint64_t hash64_stable_8(const void *key, size_t n, uint64_t base);
257
258 /**
259  * hash_pointer - hash a pointer for internal use
260  * @p: the pointer value to hash
261  * @base: the base number to roll into the hash (usually 0)
262  *
263  * The pointer p (not what p points to!) is combined with the base to form
264  * a 32-bit hash.
265  *
266  * This hash will have different results on different machines, so is
267  * only useful for internal hashes (ie. not hashes sent across the
268  * network or saved to disk).
269  *
270  * Example:
271  *      #include <ccan/hash/hash.h>
272  *
273  *      // Code to keep track of memory regions.
274  *      struct region {
275  *              struct region *chain;
276  *              void *start;
277  *              unsigned int size;
278  *      };
279  *      // We keep a simple hash table.
280  *      static struct region *region_hash[128];
281  *
282  *      static void add_region(struct region *r)
283  *      {
284  *              unsigned int h = hash_pointer(r->start, 0);
285  *
286  *              r->chain = region_hash[h];
287  *              region_hash[h] = r->chain;
288  *      }
289  *
290  *      static struct region *find_region(const void *start)
291  *      {
292  *              struct region *r;
293  *
294  *              for (r = region_hash[hash_pointer(start, 0)]; r; r = r->chain)
295  *                      if (r->start == start)
296  *                              return r;
297  *              return NULL;
298  *      }
299  */
300 static inline uint32_t hash_pointer(const void *p, uint32_t base)
301 {
302         if (sizeof(p) % sizeof(uint32_t) == 0) {
303                 /* This convoluted union is the right way of aliasing. */
304                 union {
305                         uint32_t a[sizeof(p) / sizeof(uint32_t)];
306                         const void *p;
307                 } u;
308                 u.p = p;
309                 return hash_u32(u.a, sizeof(p) / sizeof(uint32_t), base);
310         } else
311                 return hash(&p, 1, base);
312 }
313 #endif /* HASH_H */