|
1 #ifndef _LINUX_JHASH_H |
|
2 #define _LINUX_JHASH_H |
|
3 |
|
4 /* jhash.h: Jenkins hash support. |
|
5 * |
|
6 * Copyright (C) 1996 Bob Jenkins (bob_jenkins@burtleburtle.net) |
|
7 * |
|
8 * http://burtleburtle.net/bob/hash/ |
|
9 * |
|
10 * These are the credits from Bob's sources: |
|
11 * |
|
12 * lookup2.c, by Bob Jenkins, December 1996, Public Domain. |
|
13 * hash(), hash2(), hash3, and mix() are externally useful functions. |
|
14 * Routines to test the hash are included if SELF_TEST is defined. |
|
15 * You can use this free for any purpose. It has no warranty. |
|
16 * |
|
17 * Copyright (C) 2003 David S. Miller (davem@redhat.com) |
|
18 * |
|
19 * I've modified Bob's hash to be useful in the Linux kernel, and |
|
20 * any bugs present are surely my fault. -DaveM |
|
21 */ |
|
22 |
|
23 /* NOTE: Arguments are modified. */ |
|
24 #define __jhash_mix(a, b, c) \ |
|
25 { \ |
|
26 a -= b; a -= c; a ^= (c>>13); \ |
|
27 b -= c; b -= a; b ^= (a<<8); \ |
|
28 c -= a; c -= b; c ^= (b>>13); \ |
|
29 a -= b; a -= c; a ^= (c>>12); \ |
|
30 b -= c; b -= a; b ^= (a<<16); \ |
|
31 c -= a; c -= b; c ^= (b>>5); \ |
|
32 a -= b; a -= c; a ^= (c>>3); \ |
|
33 b -= c; b -= a; b ^= (a<<10); \ |
|
34 c -= a; c -= b; c ^= (b>>15); \ |
|
35 } |
|
36 |
|
37 /* The golden ration: an arbitrary value */ |
|
38 #define JHASH_GOLDEN_RATIO 0x9e3779b9 |
|
39 |
|
40 /* The most generic version, hashes an arbitrary sequence |
|
41 * of bytes. No alignment or length assumptions are made about |
|
42 * the input key. |
|
43 */ |
|
44 static inline u32 jhash(const void *key, u32 length, u32 initval) |
|
45 { |
|
46 u32 a, b, c, len; |
|
47 const u8 *k = key; |
|
48 |
|
49 len = length; |
|
50 a = b = JHASH_GOLDEN_RATIO; |
|
51 c = initval; |
|
52 |
|
53 while (len >= 12) { |
|
54 a += (k[0] +((u32)k[1]<<8) +((u32)k[2]<<16) +((u32)k[3]<<24)); |
|
55 b += (k[4] +((u32)k[5]<<8) +((u32)k[6]<<16) +((u32)k[7]<<24)); |
|
56 c += (k[8] +((u32)k[9]<<8) +((u32)k[10]<<16)+((u32)k[11]<<24)); |
|
57 |
|
58 __jhash_mix(a,b,c); |
|
59 |
|
60 k += 12; |
|
61 len -= 12; |
|
62 } |
|
63 |
|
64 c += length; |
|
65 switch (len) { |
|
66 case 11: c += ((u32)k[10]<<24); |
|
67 case 10: c += ((u32)k[9]<<16); |
|
68 case 9 : c += ((u32)k[8]<<8); |
|
69 case 8 : b += ((u32)k[7]<<24); |
|
70 case 7 : b += ((u32)k[6]<<16); |
|
71 case 6 : b += ((u32)k[5]<<8); |
|
72 case 5 : b += k[4]; |
|
73 case 4 : a += ((u32)k[3]<<24); |
|
74 case 3 : a += ((u32)k[2]<<16); |
|
75 case 2 : a += ((u32)k[1]<<8); |
|
76 case 1 : a += k[0]; |
|
77 }; |
|
78 |
|
79 __jhash_mix(a,b,c); |
|
80 |
|
81 return c; |
|
82 } |
|
83 |
|
84 /* A special optimized version that handles 1 or more of u32s. |
|
85 * The length parameter here is the number of u32s in the key. |
|
86 */ |
|
87 static inline u32 jhash2(const u32 *k, u32 length, u32 initval) |
|
88 { |
|
89 u32 a, b, c, len; |
|
90 |
|
91 a = b = JHASH_GOLDEN_RATIO; |
|
92 c = initval; |
|
93 len = length; |
|
94 |
|
95 while (len >= 3) { |
|
96 a += k[0]; |
|
97 b += k[1]; |
|
98 c += k[2]; |
|
99 __jhash_mix(a, b, c); |
|
100 k += 3; len -= 3; |
|
101 } |
|
102 |
|
103 c += length * 4; |
|
104 |
|
105 switch (len) { |
|
106 case 2 : b += k[1]; |
|
107 case 1 : a += k[0]; |
|
108 }; |
|
109 |
|
110 __jhash_mix(a,b,c); |
|
111 |
|
112 return c; |
|
113 } |
|
114 |
|
115 |
|
116 /* A special ultra-optimized versions that knows they are hashing exactly |
|
117 * 3, 2 or 1 word(s). |
|
118 * |
|
119 * NOTE: In partilar the "c += length; __jhash_mix(a,b,c);" normally |
|
120 * done at the end is not done here. |
|
121 */ |
|
122 static inline u32 jhash_3words(u32 a, u32 b, u32 c, u32 initval) |
|
123 { |
|
124 a += JHASH_GOLDEN_RATIO; |
|
125 b += JHASH_GOLDEN_RATIO; |
|
126 c += initval; |
|
127 |
|
128 __jhash_mix(a, b, c); |
|
129 |
|
130 return c; |
|
131 } |
|
132 |
|
133 static inline u32 jhash_2words(u32 a, u32 b, u32 initval) |
|
134 { |
|
135 return jhash_3words(a, b, 0, initval); |
|
136 } |
|
137 |
|
138 static inline u32 jhash_1word(u32 a, u32 initval) |
|
139 { |
|
140 return jhash_3words(a, 0, 0, initval); |
|
141 } |
|
142 |
|
143 #endif /* _LINUX_JHASH_H */ |