1 /* SPDX-License-Identifier: LGPL-2.1-only */
2 /*
3 * This code was taken from http://ccodearchive.net/info/hash.html
4 * The original file was modified to remove unwanted code
5 * and some changes to fit the current build environment
6 */
7 /*
8 -------------------------------------------------------------------------------
9 lookup3.c, by Bob Jenkins, May 2006, Public Domain.
10
11 These are functions for producing 32-bit hashes for hash table lookup.
12 hash_word(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
13 are externally useful functions. Routines to test the hash are included
14 if SELF_TEST is defined. You can use this free for any purpose. It's in
15 the public domain. It has no warranty.
16
17 You probably want to use hashlittle(). hashlittle() and hashbig()
18 hash byte arrays. hashlittle() is is faster than hashbig() on
19 little-endian machines. Intel and AMD are little-endian machines.
20 On second thought, you probably want hashlittle2(), which is identical to
21 hashlittle() except it returns two 32-bit hashes for the price of one.
22 You could implement hashbig2() if you wanted but I haven't bothered here.
23
24 If you want to find a hash of, say, exactly 7 integers, do
25 a = i1; b = i2; c = i3;
26 mix(a,b,c);
27 a += i4; b += i5; c += i6;
28 mix(a,b,c);
29 a += i7;
30 final(a,b,c);
31 then use c as the hash value. If you have a variable length array of
32 4-byte integers to hash, use hash_word(). If you have a byte array (like
33 a character string), use hashlittle(). If you have several byte arrays, or
34 a mix of things, see the comments above hashlittle().
35
36 Why is this so big? I read 12 bytes at a time into 3 4-byte integers,
37 then mix those integers. This is fast (you can do a lot more thorough
38 mixing with 12*3 instructions on 3 integers than you can with 3 instructions
39 on 1 byte), but shoehorning those bytes into integers efficiently is messy.
40 -------------------------------------------------------------------------------
41 */
42 #include <netlink/hash.h>
43
44 #if HAVE_LITTLE_ENDIAN
45 #define HASH_LITTLE_ENDIAN 1
46 #define HASH_BIG_ENDIAN 0
47 #elif HAVE_BIG_ENDIAN
48 #define HASH_LITTLE_ENDIAN 0
49 #define HASH_BIG_ENDIAN 1
50 #else
51 #error Unknown endian
52 #endif
53
54 #define hashsize(n) ((uint32_t)1<<(n))
55 #define hashmask(n) (hashsize(n)-1)
56 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
57
58 /*
59 -------------------------------------------------------------------------------
60 mix -- mix 3 32-bit values reversibly.
61
62 This is reversible, so any information in (a,b,c) before mix() is
63 still in (a,b,c) after mix().
64
65 If four pairs of (a,b,c) inputs are run through mix(), or through
66 mix() in reverse, there are at least 32 bits of the output that
67 are sometimes the same for one pair and different for another pair.
68 This was tested for:
69 * pairs that differed by one bit, by two bits, in any combination
70 of top bits of (a,b,c), or in any combination of bottom bits of
71 (a,b,c).
72 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
73 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
74 is commonly produced by subtraction) look like a single 1-bit
75 difference.
76 * the base values were pseudorandom, all zero but one bit set, or
77 all zero plus a counter that starts at zero.
78
79 Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
80 satisfy this are
81 4 6 8 16 19 4
82 9 15 3 18 27 15
83 14 9 3 7 17 3
84 Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
85 for "differ" defined as + with a one-bit base and a two-bit delta. I
86 used http://burtleburtle.net/bob/hash/avalanche.html to choose
87 the operations, constants, and arrangements of the variables.
88
89 This does not achieve avalanche. There are input bits of (a,b,c)
90 that fail to affect some output bits of (a,b,c), especially of a. The
91 most thoroughly mixed value is c, but it doesn't really even achieve
92 avalanche in c.
93
94 This allows some parallelism. Read-after-writes are good at doubling
95 the number of bits affected, so the goal of mixing pulls in the opposite
96 direction as the goal of parallelism. I did what I could. Rotates
97 seem to cost as much as shifts on every machine I could lay my hands
98 on, and rotates are much kinder to the top and bottom bits, so I used
99 rotates.
100 -------------------------------------------------------------------------------
101 */
102 #define mix(a,b,c) \
103 { \
104 a -= c; a ^= rot(c, 4); c += b; \
105 b -= a; b ^= rot(a, 6); a += c; \
106 c -= b; c ^= rot(b, 8); b += a; \
107 a -= c; a ^= rot(c,16); c += b; \
108 b -= a; b ^= rot(a,19); a += c; \
109 c -= b; c ^= rot(b, 4); b += a; \
110 }
111
112 /*
113 -------------------------------------------------------------------------------
114 final -- final mixing of 3 32-bit values (a,b,c) into c
115
116 Pairs of (a,b,c) values differing in only a few bits will usually
117 produce values of c that look totally different. This was tested for
118 * pairs that differed by one bit, by two bits, in any combination
119 of top bits of (a,b,c), or in any combination of bottom bits of
120 (a,b,c).
121 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
122 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
123 is commonly produced by subtraction) look like a single 1-bit
124 difference.
125 * the base values were pseudorandom, all zero but one bit set, or
126 all zero plus a counter that starts at zero.
127
128 These constants passed:
129 14 11 25 16 4 14 24
130 12 14 25 16 4 14 24
131 and these came close:
132 4 8 15 26 3 22 24
133 10 8 15 26 3 22 24
134 11 8 15 26 3 22 24
135 -------------------------------------------------------------------------------
136 */
137 #define final(a,b,c) \
138 { \
139 c ^= b; c -= rot(b,14); \
140 a ^= c; a -= rot(c,11); \
141 b ^= a; b -= rot(a,25); \
142 c ^= b; c -= rot(b,16); \
143 a ^= c; a -= rot(c,4); \
144 b ^= a; b -= rot(a,14); \
145 c ^= b; c -= rot(b,24); \
146 }
147
148 /*
149 -------------------------------------------------------------------------------
150 hashlittle() -- hash a variable-length key into a 32-bit value
151 k : the key (the unaligned variable-length array of bytes)
152 length : the length of the key, counting by bytes
153 val2 : IN: can be any 4-byte value OUT: second 32 bit hash.
154 Returns a 32-bit value. Every bit of the key affects every bit of
155 the return value. Two keys differing by one or two bits will have
156 totally different hash values. Note that the return value is better
157 mixed than val2, so use that first.
158
159 The best hash table sizes are powers of 2. There is no need to do
160 mod a prime (mod is sooo slow!). If you need less than 32 bits,
161 use a bitmask. For example, if you need only 10 bits, do
162 h = (h & hashmask(10));
163 In which case, the hash table should have hashsize(10) elements.
164
165 If you are hashing n strings (uint8_t **)k, do it like this:
166 for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
167
168 By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this
169 code any way you wish, private, educational, or commercial. It's free.
170
171 Use for hash table lookup, or anything where one collision in 2^^32 is
172 acceptable. Do NOT use for cryptographic purposes.
173 -------------------------------------------------------------------------------
174 */
175
hashlittle(const void * key,size_t length,uint32_t * val2)176 static uint32_t hashlittle( const void *key, size_t length, uint32_t *val2 )
177 {
178 uint32_t a,b,c; /* internal state */
179 union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */
180
181 /* Set up the internal state */
182 a = b = c = 0xdeadbeef + ((uint32_t)length) + *val2;
183
184 u.ptr = key;
185 if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
186 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
187 const uint8_t *k8;
188
189 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
190 while (length > 12)
191 {
192 a += k[0];
193 b += k[1];
194 c += k[2];
195 mix(a,b,c);
196 length -= 12;
197 k += 3;
198 }
199
200 /*----------------------------- handle the last (probably partial) block */
201 /*
202 * "k[2]&0xffffff" actually reads beyond the end of the string, but
203 * then masks off the part it's not allowed to read. Because the
204 * string is aligned, the masked-off tail is in the same word as the
205 * rest of the string. Every machine with memory protection I've seen
206 * does it on word boundaries, so is OK with this. But VALGRIND will
207 * still catch it and complain. The masking trick does make the hash
208 * noticably faster for short strings (like English words).
209 *
210 * Not on my testing with gcc 4.5 on an intel i5 CPU, at least --RR.
211 */
212 #if 0
213 switch(length)
214 {
215 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
216 case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
217 case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
218 case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
219 case 8 : b+=k[1]; a+=k[0]; break;
220 case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
221 case 6 : b+=k[1]&0xffff; a+=k[0]; break;
222 case 5 : b+=k[1]&0xff; a+=k[0]; break;
223 case 4 : a+=k[0]; break;
224 case 3 : a+=k[0]&0xffffff; break;
225 case 2 : a+=k[0]&0xffff; break;
226 case 1 : a+=k[0]&0xff; break;
227 case 0 : return c; /* zero length strings require no mixing */
228 }
229
230 #else /* make valgrind happy */
231
232 k8 = (const uint8_t *)k;
233 switch(length)
234 {
235 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
236 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
237 case 10: c+=((uint32_t)k8[9])<<8; /* fall through */
238 case 9 : c+=k8[8]; /* fall through */
239 case 8 : b+=k[1]; a+=k[0]; break;
240 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
241 case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */
242 case 5 : b+=k8[4]; /* fall through */
243 case 4 : a+=k[0]; break;
244 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
245 case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */
246 case 1 : a+=k8[0]; break;
247 case 0 : return c;
248 }
249
250 #endif /* !valgrind */
251
252 } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
253 const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
254 const uint8_t *k8;
255
256 /*--------------- all but last block: aligned reads and different mixing */
257 while (length > 12)
258 {
259 a += k[0] + (((uint32_t)k[1])<<16);
260 b += k[2] + (((uint32_t)k[3])<<16);
261 c += k[4] + (((uint32_t)k[5])<<16);
262 mix(a,b,c);
263 length -= 12;
264 k += 6;
265 }
266
267 /*----------------------------- handle the last (probably partial) block */
268 k8 = (const uint8_t *)k;
269 switch(length)
270 {
271 case 12: c+=k[4]+(((uint32_t)k[5])<<16);
272 b+=k[2]+(((uint32_t)k[3])<<16);
273 a+=k[0]+(((uint32_t)k[1])<<16);
274 break;
275 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
276 case 10: c+=k[4];
277 b+=k[2]+(((uint32_t)k[3])<<16);
278 a+=k[0]+(((uint32_t)k[1])<<16);
279 break;
280 case 9 : c+=k8[8]; /* fall through */
281 case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
282 a+=k[0]+(((uint32_t)k[1])<<16);
283 break;
284 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
285 case 6 : b+=k[2];
286 a+=k[0]+(((uint32_t)k[1])<<16);
287 break;
288 case 5 : b+=k8[4]; /* fall through */
289 case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
290 break;
291 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
292 case 2 : a+=k[0];
293 break;
294 case 1 : a+=k8[0];
295 break;
296 case 0 : return c; /* zero length requires no mixing */
297 }
298
299 } else { /* need to read the key one byte at a time */
300 const uint8_t *k = (const uint8_t *)key;
301
302 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
303 while (length > 12)
304 {
305 a += k[0];
306 a += ((uint32_t)k[1])<<8;
307 a += ((uint32_t)k[2])<<16;
308 a += ((uint32_t)k[3])<<24;
309 b += k[4];
310 b += ((uint32_t)k[5])<<8;
311 b += ((uint32_t)k[6])<<16;
312 b += ((uint32_t)k[7])<<24;
313 c += k[8];
314 c += ((uint32_t)k[9])<<8;
315 c += ((uint32_t)k[10])<<16;
316 c += ((uint32_t)k[11])<<24;
317 mix(a,b,c);
318 length -= 12;
319 k += 12;
320 }
321
322 /*-------------------------------- last block: affect all 32 bits of (c) */
323 switch(length) /* all the case statements fall through */
324 {
325 case 12: c+=((uint32_t)k[11])<<24; /* fall through */
326 case 11: c+=((uint32_t)k[10])<<16; /* fall through */
327 case 10: c+=((uint32_t)k[9])<<8; /* fall through */
328 case 9 : c+=k[8]; /* fall through */
329 case 8 : b+=((uint32_t)k[7])<<24; /* fall through */
330 case 7 : b+=((uint32_t)k[6])<<16; /* fall through */
331 case 6 : b+=((uint32_t)k[5])<<8; /* fall through */
332 case 5 : b+=k[4]; /* fall through */
333 case 4 : a+=((uint32_t)k[3])<<24; /* fall through */
334 case 3 : a+=((uint32_t)k[2])<<16; /* fall through */
335 case 2 : a+=((uint32_t)k[1])<<8; /* fall through */
336 case 1 : a+=k[0];
337 break;
338 case 0 : return c;
339 }
340 }
341
342 final(a,b,c);
343 *val2 = b;
344 return c;
345 }
346
347 /*
348 * hashbig():
349 * This is the same as hash_word() on big-endian machines. It is different
350 * from hashlittle() on all machines. hashbig() takes advantage of
351 * big-endian byte ordering.
352 */
hashbig(const void * key,size_t length,uint32_t * val2)353 static uint32_t hashbig( const void *key, size_t length, uint32_t *val2)
354 {
355 uint32_t a,b,c;
356 union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */
357
358 /* Set up the internal state */
359 a = b = c = 0xdeadbeef + ((uint32_t)length) + *val2;
360
361 u.ptr = key;
362 if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) {
363 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
364 const uint8_t *k8;
365
366 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
367 while (length > 12)
368 {
369 a += k[0];
370 b += k[1];
371 c += k[2];
372 mix(a,b,c);
373 length -= 12;
374 k += 3;
375 }
376
377 /*----------------------------- handle the last (probably partial) block */
378 /*
379 * "k[2]<<8" actually reads beyond the end of the string, but
380 * then shifts out the part it's not allowed to read. Because the
381 * string is aligned, the illegal read is in the same word as the
382 * rest of the string. Every machine with memory protection I've seen
383 * does it on word boundaries, so is OK with this. But VALGRIND will
384 * still catch it and complain. The masking trick does make the hash
385 * noticably faster for short strings (like English words).
386 *
387 * Not on my testing with gcc 4.5 on an intel i5 CPU, at least --RR.
388 */
389 #if 0
390 switch(length)
391 {
392 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
393 case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break;
394 case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break;
395 case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break;
396 case 8 : b+=k[1]; a+=k[0]; break;
397 case 7 : b+=k[1]&0xffffff00; a+=k[0]; break;
398 case 6 : b+=k[1]&0xffff0000; a+=k[0]; break;
399 case 5 : b+=k[1]&0xff000000; a+=k[0]; break;
400 case 4 : a+=k[0]; break;
401 case 3 : a+=k[0]&0xffffff00; break;
402 case 2 : a+=k[0]&0xffff0000; break;
403 case 1 : a+=k[0]&0xff000000; break;
404 case 0 : return c; /* zero length strings require no mixing */
405 }
406
407 #else /* make valgrind happy */
408
409 k8 = (const uint8_t *)k;
410 switch(length) /* all the case statements fall through */
411 {
412 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
413 case 11: c+=((uint32_t)k8[10])<<8; /* fall through */
414 case 10: c+=((uint32_t)k8[9])<<16; /* fall through */
415 case 9 : c+=((uint32_t)k8[8])<<24; /* fall through */
416 case 8 : b+=k[1]; a+=k[0]; break;
417 case 7 : b+=((uint32_t)k8[6])<<8; /* fall through */
418 case 6 : b+=((uint32_t)k8[5])<<16; /* fall through */
419 case 5 : b+=((uint32_t)k8[4])<<24; /* fall through */
420 case 4 : a+=k[0]; break;
421 case 3 : a+=((uint32_t)k8[2])<<8; /* fall through */
422 case 2 : a+=((uint32_t)k8[1])<<16; /* fall through */
423 case 1 : a+=((uint32_t)k8[0])<<24; break;
424 case 0 : return c;
425 }
426
427 #endif /* !VALGRIND */
428
429 } else { /* need to read the key one byte at a time */
430 const uint8_t *k = (const uint8_t *)key;
431
432 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
433 while (length > 12)
434 {
435 a += ((uint32_t)k[0])<<24;
436 a += ((uint32_t)k[1])<<16;
437 a += ((uint32_t)k[2])<<8;
438 a += ((uint32_t)k[3]);
439 b += ((uint32_t)k[4])<<24;
440 b += ((uint32_t)k[5])<<16;
441 b += ((uint32_t)k[6])<<8;
442 b += ((uint32_t)k[7]);
443 c += ((uint32_t)k[8])<<24;
444 c += ((uint32_t)k[9])<<16;
445 c += ((uint32_t)k[10])<<8;
446 c += ((uint32_t)k[11]);
447 mix(a,b,c);
448 length -= 12;
449 k += 12;
450 }
451
452 /*-------------------------------- last block: affect all 32 bits of (c) */
453 switch(length) /* all the case statements fall through */
454 {
455 case 12: c+=k[11]; /* fall through */
456 case 11: c+=((uint32_t)k[10])<<8; /* fall through */
457 case 10: c+=((uint32_t)k[9])<<16; /* fall through */
458 case 9 : c+=((uint32_t)k[8])<<24; /* fall through */
459 case 8 : b+=k[7]; /* fall through */
460 case 7 : b+=((uint32_t)k[6])<<8; /* fall through */
461 case 6 : b+=((uint32_t)k[5])<<16; /* fall through */
462 case 5 : b+=((uint32_t)k[4])<<24; /* fall through */
463 case 4 : a+=k[3]; /* fall through */
464 case 3 : a+=((uint32_t)k[2])<<8; /* fall through */
465 case 2 : a+=((uint32_t)k[1])<<16; /* fall through */
466 case 1 : a+=((uint32_t)k[0])<<24; /* fall through */
467 break;
468 case 0 : return c;
469 }
470 }
471
472 final(a,b,c);
473 *val2 = b;
474 return c;
475 }
476
nl_hash_any(const void * key,size_t length,uint32_t base)477 uint32_t nl_hash_any(const void *key, size_t length, uint32_t base)
478 {
479 if (HASH_BIG_ENDIAN)
480 return hashbig(key, length, &base);
481 else
482 return hashlittle(key, length, &base);
483 }
484