| 1 | /* jhash.h: Jenkins hash support. |
| 2 | * |
| 3 | * Copyright (C) 2006. Bob Jenkins (bob_jenkins@burtleburtle.net) |
| 4 | * |
| 5 | * http://burtleburtle.net/bob/hash/ |
| 6 | * |
| 7 | * These are the credits from Bob's sources: |
| 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 | * hashword(), 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 | * Copyright (C) 2009-2010 Jozsef Kadlecsik (kadlec@blackhole.kfki.hu) |
| 18 | * |
| 19 | * I've modified Bob's hash to be useful in the Linux kernel, and |
| 20 | * any bugs present are my fault. |
| 21 | * Jozsef |
| 22 | */ |
| 23 | |
| 24 | #ifndef QEMU_JHASH_H |
| 25 | #define QEMU_JHASH_H |
| 26 | |
| 27 | #include "qemu/bitops.h" |
| 28 | |
| 29 | /* |
| 30 | * hashtable relation copy from linux kernel jhash |
| 31 | */ |
| 32 | |
| 33 | /* __jhash_mix -- mix 3 32-bit values reversibly. */ |
| 34 | #define __jhash_mix(a, b, c) \ |
| 35 | { \ |
| 36 | a -= c; a ^= rol32(c, 4); c += b; \ |
| 37 | b -= a; b ^= rol32(a, 6); a += c; \ |
| 38 | c -= b; c ^= rol32(b, 8); b += a; \ |
| 39 | a -= c; a ^= rol32(c, 16); c += b; \ |
| 40 | b -= a; b ^= rol32(a, 19); a += c; \ |
| 41 | c -= b; c ^= rol32(b, 4); b += a; \ |
| 42 | } |
| 43 | |
| 44 | /* __jhash_final - final mixing of 3 32-bit values (a,b,c) into c */ |
| 45 | #define __jhash_final(a, b, c) \ |
| 46 | { \ |
| 47 | c ^= b; c -= rol32(b, 14); \ |
| 48 | a ^= c; a -= rol32(c, 11); \ |
| 49 | b ^= a; b -= rol32(a, 25); \ |
| 50 | c ^= b; c -= rol32(b, 16); \ |
| 51 | a ^= c; a -= rol32(c, 4); \ |
| 52 | b ^= a; b -= rol32(a, 14); \ |
| 53 | c ^= b; c -= rol32(b, 24); \ |
| 54 | } |
| 55 | |
| 56 | /* An arbitrary initial parameter */ |
| 57 | #define JHASH_INITVAL 0xdeadbeef |
| 58 | |
| 59 | #endif /* QEMU_JHASH_H */ |