41 #include <netlink/hash.h>
43 #if HAVE_LITTLE_ENDIAN
44 #define HASH_LITTLE_ENDIAN 1
45 #define HASH_BIG_ENDIAN 0
47 #define HASH_LITTLE_ENDIAN 0
48 #define HASH_BIG_ENDIAN 1
53 #define hashsize(n) ((uint32_t)1<<(n))
54 #define hashmask(n) (hashsize(n)-1)
55 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
103 a -= c; a ^= rot(c, 4); c += b; \
104 b -= a; b ^= rot(a, 6); a += c; \
105 c -= b; c ^= rot(b, 8); b += a; \
106 a -= c; a ^= rot(c,16); c += b; \
107 b -= a; b ^= rot(a,19); a += c; \
108 c -= b; c ^= rot(b, 4); b += a; \
136 #define final(a,b,c) \
138 c ^= b; c -= rot(b,14); \
139 a ^= c; a -= rot(c,11); \
140 b ^= a; b -= rot(a,25); \
141 c ^= b; c -= rot(b,16); \
142 a ^= c; a -= rot(c,4); \
143 b ^= a; b -= rot(a,14); \
144 c ^= b; c -= rot(b,24); \
175 static uint32_t hashlittle(
const void *key,
size_t length, uint32_t *val2 )
178 union {
const void *ptr;
size_t i; } u;
181 a = b = c = 0xdeadbeef + ((uint32_t)length) + *val2;
184 if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
185 const uint32_t *k = (
const uint32_t *)key;
214 case 12: c+=k[2]; b+=k[1]; a+=k[0];
break;
215 case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0];
break;
216 case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0];
break;
217 case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0];
break;
218 case 8 : b+=k[1]; a+=k[0];
break;
219 case 7 : b+=k[1]&0xffffff; a+=k[0];
break;
220 case 6 : b+=k[1]&0xffff; a+=k[0];
break;
221 case 5 : b+=k[1]&0xff; a+=k[0];
break;
222 case 4 : a+=k[0];
break;
223 case 3 : a+=k[0]&0xffffff;
break;
224 case 2 : a+=k[0]&0xffff;
break;
225 case 1 : a+=k[0]&0xff;
break;
231 k8 = (
const uint8_t *)k;
234 case 12: c+=k[2]; b+=k[1]; a+=k[0];
break;
235 case 11: c+=((uint32_t)k8[10])<<16;
236 case 10: c+=((uint32_t)k8[9])<<8;
238 case 8 : b+=k[1]; a+=k[0];
break;
239 case 7 : b+=((uint32_t)k8[6])<<16;
240 case 6 : b+=((uint32_t)k8[5])<<8;
242 case 4 : a+=k[0];
break;
243 case 3 : a+=((uint32_t)k8[2])<<16;
244 case 2 : a+=((uint32_t)k8[1])<<8;
245 case 1 : a+=k8[0];
break;
251 }
else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
252 const uint16_t *k = (
const uint16_t *)key;
258 a += k[0] + (((uint32_t)k[1])<<16);
259 b += k[2] + (((uint32_t)k[3])<<16);
260 c += k[4] + (((uint32_t)k[5])<<16);
267 k8 = (
const uint8_t *)k;
270 case 12: c+=k[4]+(((uint32_t)k[5])<<16);
271 b+=k[2]+(((uint32_t)k[3])<<16);
272 a+=k[0]+(((uint32_t)k[1])<<16);
274 case 11: c+=((uint32_t)k8[10])<<16;
276 b+=k[2]+(((uint32_t)k[3])<<16);
277 a+=k[0]+(((uint32_t)k[1])<<16);
280 case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
281 a+=k[0]+(((uint32_t)k[1])<<16);
283 case 7 : b+=((uint32_t)k8[6])<<16;
285 a+=k[0]+(((uint32_t)k[1])<<16);
288 case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
290 case 3 : a+=((uint32_t)k8[2])<<16;
299 const uint8_t *k = (
const uint8_t *)key;
305 a += ((uint32_t)k[1])<<8;
306 a += ((uint32_t)k[2])<<16;
307 a += ((uint32_t)k[3])<<24;
309 b += ((uint32_t)k[5])<<8;
310 b += ((uint32_t)k[6])<<16;
311 b += ((uint32_t)k[7])<<24;
313 c += ((uint32_t)k[9])<<8;
314 c += ((uint32_t)k[10])<<16;
315 c += ((uint32_t)k[11])<<24;
324 case 12: c+=((uint32_t)k[11])<<24;
325 case 11: c+=((uint32_t)k[10])<<16;
326 case 10: c+=((uint32_t)k[9])<<8;
328 case 8 : b+=((uint32_t)k[7])<<24;
329 case 7 : b+=((uint32_t)k[6])<<16;
330 case 6 : b+=((uint32_t)k[5])<<8;
332 case 4 : a+=((uint32_t)k[3])<<24;
333 case 3 : a+=((uint32_t)k[2])<<16;
334 case 2 : a+=((uint32_t)k[1])<<8;
352 static uint32_t hashbig(
const void *key,
size_t length, uint32_t *val2)
355 union {
const void *ptr;
size_t i; } u;
358 a = b = c = 0xdeadbeef + ((uint32_t)length) + *val2;
361 if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) {
362 const uint32_t *k = (
const uint32_t *)key;
391 case 12: c+=k[2]; b+=k[1]; a+=k[0];
break;
392 case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0];
break;
393 case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0];
break;
394 case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0];
break;
395 case 8 : b+=k[1]; a+=k[0];
break;
396 case 7 : b+=k[1]&0xffffff00; a+=k[0];
break;
397 case 6 : b+=k[1]&0xffff0000; a+=k[0];
break;
398 case 5 : b+=k[1]&0xff000000; a+=k[0];
break;
399 case 4 : a+=k[0];
break;
400 case 3 : a+=k[0]&0xffffff00;
break;
401 case 2 : a+=k[0]&0xffff0000;
break;
402 case 1 : a+=k[0]&0xff000000;
break;
408 k8 = (
const uint8_t *)k;
411 case 12: c+=k[2]; b+=k[1]; a+=k[0];
break;
412 case 11: c+=((uint32_t)k8[10])<<8;
413 case 10: c+=((uint32_t)k8[9])<<16;
414 case 9 : c+=((uint32_t)k8[8])<<24;
415 case 8 : b+=k[1]; a+=k[0];
break;
416 case 7 : b+=((uint32_t)k8[6])<<8;
417 case 6 : b+=((uint32_t)k8[5])<<16;
418 case 5 : b+=((uint32_t)k8[4])<<24;
419 case 4 : a+=k[0];
break;
420 case 3 : a+=((uint32_t)k8[2])<<8;
421 case 2 : a+=((uint32_t)k8[1])<<16;
422 case 1 : a+=((uint32_t)k8[0])<<24;
break;
429 const uint8_t *k = (
const uint8_t *)key;
434 a += ((uint32_t)k[0])<<24;
435 a += ((uint32_t)k[1])<<16;
436 a += ((uint32_t)k[2])<<8;
437 a += ((uint32_t)k[3]);
438 b += ((uint32_t)k[4])<<24;
439 b += ((uint32_t)k[5])<<16;
440 b += ((uint32_t)k[6])<<8;
441 b += ((uint32_t)k[7]);
442 c += ((uint32_t)k[8])<<24;
443 c += ((uint32_t)k[9])<<16;
444 c += ((uint32_t)k[10])<<8;
445 c += ((uint32_t)k[11]);
455 case 11: c+=((uint32_t)k[10])<<8;
456 case 10: c+=((uint32_t)k[9])<<16;
457 case 9 : c+=((uint32_t)k[8])<<24;
459 case 7 : b+=((uint32_t)k[6])<<8;
460 case 6 : b+=((uint32_t)k[5])<<16;
461 case 5 : b+=((uint32_t)k[4])<<24;
463 case 3 : a+=((uint32_t)k[2])<<8;
464 case 2 : a+=((uint32_t)k[1])<<16;
465 case 1 : a+=((uint32_t)k[0])<<24;
476 uint32_t nl_hash_any(
const void *key,
size_t length, uint32_t base)
479 return hashbig(key, length, &base);
481 return hashlittle(key, length, &base);