Commit | Line | Data |
---|---|---|
bf0720af JA |
1 | #ifndef _LINUX_JHASH_H |
2 | #define _LINUX_JHASH_H | |
3 | ||
4 | /* jhash.h: Jenkins hash support. | |
5 | * | |
40502e47 | 6 | * Copyright (C) 2006. Bob Jenkins (bob_jenkins@burtleburtle.net) |
bf0720af JA |
7 | * |
8 | * http://burtleburtle.net/bob/hash/ | |
9 | * | |
10 | * These are the credits from Bob's sources: | |
11 | * | |
40502e47 | 12 | * lookup3.c, by Bob Jenkins, May 2006, Public Domain. |
bf0720af | 13 | * |
40502e47 JA |
14 | * These are functions for producing 32-bit hashes for hash table lookup. |
15 | * hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() | |
16 | * are externally useful functions. Routines to test the hash are included | |
17 | * if SELF_TEST is defined. You can use this free for any purpose. It's in | |
18 | * the public domain. It has no warranty. | |
19 | * | |
20 | * Copyright (C) 2009 Jozsef Kadlecsik (kadlec@blackhole.kfki.hu) | |
bf0720af JA |
21 | * |
22 | * I've modified Bob's hash to be useful in the Linux kernel, and | |
40502e47 | 23 | * any bugs present are my fault. Jozsef |
bf0720af JA |
24 | */ |
25 | ||
40502e47 JA |
26 | #define __rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) |
27 | ||
28 | /* __jhash_mix - mix 3 32-bit values reversibly. */ | |
29 | #define __jhash_mix(a,b,c) \ | |
30 | { \ | |
31 | a -= c; a ^= __rot(c, 4); c += b; \ | |
32 | b -= a; b ^= __rot(a, 6); a += c; \ | |
33 | c -= b; c ^= __rot(b, 8); b += a; \ | |
34 | a -= c; a ^= __rot(c,16); c += b; \ | |
35 | b -= a; b ^= __rot(a,19); a += c; \ | |
36 | c -= b; c ^= __rot(b, 4); b += a; \ | |
37 | } | |
38 | ||
39 | /* __jhash_final - final mixing of 3 32-bit values (a,b,c) into c */ | |
40 | #define __jhash_final(a,b,c) \ | |
bf0720af | 41 | { \ |
40502e47 JA |
42 | c ^= b; c -= __rot(b,14); \ |
43 | a ^= c; a -= __rot(c,11); \ | |
44 | b ^= a; b -= __rot(a,25); \ | |
45 | c ^= b; c -= __rot(b,16); \ | |
46 | a ^= c; a -= __rot(c,4); \ | |
47 | b ^= a; b -= __rot(a,14); \ | |
48 | c ^= b; c -= __rot(b,24); \ | |
bf0720af JA |
49 | } |
50 | ||
51 | /* The golden ration: an arbitrary value */ | |
40502e47 | 52 | #define JHASH_GOLDEN_RATIO 0xdeadbeef |
bf0720af JA |
53 | |
54 | /* The most generic version, hashes an arbitrary sequence | |
55 | * of bytes. No alignment or length assumptions are made about | |
40502e47 | 56 | * the input key. The result depends on endianness. |
bf0720af JA |
57 | */ |
58 | static inline u32 jhash(const void *key, u32 length, u32 initval) | |
59 | { | |
40502e47 | 60 | u32 a,b,c; |
bf0720af JA |
61 | const u8 *k = key; |
62 | ||
40502e47 JA |
63 | /* Set up the internal state */ |
64 | a = b = c = JHASH_GOLDEN_RATIO + length + initval; | |
bf0720af | 65 | |
40502e47 JA |
66 | /* all but the last block: affect some 32 bits of (a,b,c) */ |
67 | while (length > 12) { | |
68 | a += (k[0] + ((u32)k[1]<<8) + ((u32)k[2]<<16) + ((u32)k[3]<<24)); | |
69 | b += (k[4] + ((u32)k[5]<<8) + ((u32)k[6]<<16) + ((u32)k[7]<<24)); | |
70 | c += (k[8] + ((u32)k[9]<<8) + ((u32)k[10]<<16) + ((u32)k[11]<<24)); | |
71 | __jhash_mix(a, b, c); | |
72 | length -= 12; | |
bf0720af | 73 | k += 12; |
bf0720af JA |
74 | } |
75 | ||
dae2f95b | 76 | /* Last block: affect all 32 bits of (c) */ |
40502e47 | 77 | switch (length) { |
dae2f95b JA |
78 | case 12: c += (u32)k[11]<<24; /* fall through */ |
79 | case 11: c += (u32)k[10]<<16; /* fall through */ | |
80 | case 10: c += (u32)k[9]<<8; /* fall through */ | |
81 | case 9: c += k[8]; /* fall through */ | |
82 | case 8: b += (u32)k[7]<<24; /* fall through */ | |
83 | case 7: b += (u32)k[6]<<16; /* fall through */ | |
84 | case 6: b += (u32)k[5]<<8; /* fall through */ | |
85 | case 5: b += k[4]; /* fall through */ | |
86 | case 4: a += (u32)k[3]<<24; /* fall through */ | |
87 | case 3: a += (u32)k[2]<<16; /* fall through */ | |
88 | case 2: a += (u32)k[1]<<8; /* fall through */ | |
89 | case 1: a += k[0]; | |
90 | __jhash_final(a, b, c); | |
40502e47 JA |
91 | case 0 : |
92 | break; | |
93 | } | |
bf0720af JA |
94 | |
95 | return c; | |
96 | } | |
97 | ||
98 | /* A special optimized version that handles 1 or more of u32s. | |
99 | * The length parameter here is the number of u32s in the key. | |
100 | */ | |
101 | static inline u32 jhash2(u32 *k, u32 length, u32 initval) | |
102 | { | |
40502e47 | 103 | u32 a, b, c; |
bf0720af | 104 | |
40502e47 JA |
105 | /* Set up the internal state */ |
106 | a = b = c = JHASH_GOLDEN_RATIO + (length<<2) + initval; | |
bf0720af | 107 | |
40502e47 JA |
108 | /* handle most of the key */ |
109 | while (length > 3) { | |
bf0720af JA |
110 | a += k[0]; |
111 | b += k[1]; | |
112 | c += k[2]; | |
113 | __jhash_mix(a, b, c); | |
40502e47 JA |
114 | length -= 3; |
115 | k += 3; | |
bf0720af JA |
116 | } |
117 | ||
40502e47 | 118 | /* handle the last 3 u32's */ |
40502e47 | 119 | switch (length) { |
dae2f95b JA |
120 | case 3: c += k[2]; /* fall through */ |
121 | case 2: b += k[1]; /* fall through */ | |
40502e47 JA |
122 | case 1: a += k[0]; |
123 | __jhash_final(a, b, c); | |
124 | case 0: /* case 0: nothing left to add */ | |
125 | break; | |
126 | } | |
bf0720af JA |
127 | |
128 | return c; | |
129 | } | |
130 | ||
bf0720af JA |
131 | /* A special ultra-optimized versions that knows they are hashing exactly |
132 | * 3, 2 or 1 word(s). | |
bf0720af JA |
133 | */ |
134 | static inline u32 jhash_3words(u32 a, u32 b, u32 c, u32 initval) | |
135 | { | |
40502e47 JA |
136 | a += JHASH_GOLDEN_RATIO + initval; |
137 | b += JHASH_GOLDEN_RATIO + initval; | |
138 | c += JHASH_GOLDEN_RATIO + initval; | |
bf0720af | 139 | |
40502e47 | 140 | __jhash_final(a, b, c); |
bf0720af JA |
141 | |
142 | return c; | |
143 | } | |
144 | ||
145 | static inline u32 jhash_2words(u32 a, u32 b, u32 initval) | |
146 | { | |
40502e47 | 147 | return jhash_3words(0, a, b, initval); |
bf0720af JA |
148 | } |
149 | ||
150 | static inline u32 jhash_1word(u32 a, u32 initval) | |
151 | { | |
40502e47 | 152 | return jhash_3words(0, 0, a, initval); |
bf0720af JA |
153 | } |
154 | ||
155 | #endif /* _LINUX_JHASH_H */ |