]>
Commit | Line | Data |
---|---|---|
b9790b34 | 1 | /* jhash.h: Jenkins hash support. |
2 | * | |
3 | * Copyright (C) 1996 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 | * lookup2.c, by Bob Jenkins, December 1996, Public Domain. | |
10 | * hash(), hash2(), hash3, and mix() are externally useful functions. | |
11 | * Routines to test the hash are included if SELF_TEST is defined. | |
12 | * You can use this free for any purpose. It has no warranty. | |
13 | * | |
14 | * Copyright (C) 2003 David S. Miller (davem@redhat.com) | |
15 | * | |
16 | * I've modified Bob's hash to be useful in the Linux kernel, and | |
17 | * any bugs present are surely my fault. -DaveM | |
18 | */ | |
19 | ||
20 | #include "zebra.h" | |
21 | #include "jhash.h" | |
22 | ||
23 | /* The golden ration: an arbitrary value */ | |
24 | #define JHASH_GOLDEN_RATIO 0x9e3779b9 | |
25 | ||
26 | /* NOTE: Arguments are modified. */ | |
27 | #define __jhash_mix(a, b, c) \ | |
28 | { \ | |
29 | a -= b; a -= c; a ^= (c>>13); \ | |
30 | b -= c; b -= a; b ^= (a<<8); \ | |
31 | c -= a; c -= b; c ^= (b>>13); \ | |
32 | a -= b; a -= c; a ^= (c>>12); \ | |
33 | b -= c; b -= a; b ^= (a<<16); \ | |
34 | c -= a; c -= b; c ^= (b>>5); \ | |
35 | a -= b; a -= c; a ^= (c>>3); \ | |
36 | b -= c; b -= a; b ^= (a<<10); \ | |
37 | c -= a; c -= b; c ^= (b>>15); \ | |
38 | } | |
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 | u_int32_t | |
24873f0c | 45 | jhash (const void *key, u_int32_t length, u_int32_t initval) |
b9790b34 | 46 | { |
47 | u_int32_t a, b, c, len; | |
24873f0c | 48 | const u_int8_t *k = key; |
b9790b34 | 49 | |
50 | len = length; | |
51 | a = b = JHASH_GOLDEN_RATIO; | |
52 | c = initval; | |
53 | ||
54 | while (len >= 12) | |
55 | { | |
56 | a += | |
57 | (k[0] + ((u_int32_t) k[1] << 8) + ((u_int32_t) k[2] << 16) + | |
58 | ((u_int32_t) k[3] << 24)); | |
59 | b += | |
60 | (k[4] + ((u_int32_t) k[5] << 8) + ((u_int32_t) k[6] << 16) + | |
61 | ((u_int32_t) k[7] << 24)); | |
62 | c += | |
63 | (k[8] + ((u_int32_t) k[9] << 8) + ((u_int32_t) k[10] << 16) + | |
64 | ((u_int32_t) k[11] << 24)); | |
65 | ||
66 | __jhash_mix (a, b, c); | |
67 | ||
68 | k += 12; | |
69 | len -= 12; | |
70 | } | |
71 | ||
72 | c += length; | |
73 | switch (len) | |
74 | { | |
75 | case 11: | |
76 | c += ((u_int32_t) k[10] << 24); | |
77 | case 10: | |
78 | c += ((u_int32_t) k[9] << 16); | |
79 | case 9: | |
80 | c += ((u_int32_t) k[8] << 8); | |
81 | case 8: | |
82 | b += ((u_int32_t) k[7] << 24); | |
83 | case 7: | |
84 | b += ((u_int32_t) k[6] << 16); | |
85 | case 6: | |
86 | b += ((u_int32_t) k[5] << 8); | |
87 | case 5: | |
88 | b += k[4]; | |
89 | case 4: | |
90 | a += ((u_int32_t) k[3] << 24); | |
91 | case 3: | |
92 | a += ((u_int32_t) k[2] << 16); | |
93 | case 2: | |
94 | a += ((u_int32_t) k[1] << 8); | |
95 | case 1: | |
96 | a += k[0]; | |
97 | }; | |
98 | ||
99 | __jhash_mix (a, b, c); | |
100 | ||
101 | return c; | |
102 | } | |
103 | ||
104 | /* A special optimized version that handles 1 or more of u_int32_ts. | |
105 | * The length parameter here is the number of u_int32_ts in the key. | |
106 | */ | |
107 | u_int32_t | |
1f9a9fff | 108 | jhash2 (const u_int32_t *k, u_int32_t length, u_int32_t initval) |
b9790b34 | 109 | { |
110 | u_int32_t a, b, c, len; | |
111 | ||
112 | a = b = JHASH_GOLDEN_RATIO; | |
113 | c = initval; | |
114 | len = length; | |
115 | ||
116 | while (len >= 3) | |
117 | { | |
118 | a += k[0]; | |
119 | b += k[1]; | |
120 | c += k[2]; | |
121 | __jhash_mix (a, b, c); | |
122 | k += 3; | |
123 | len -= 3; | |
124 | } | |
125 | ||
126 | c += length * 4; | |
127 | ||
128 | switch (len) | |
129 | { | |
130 | case 2: | |
131 | b += k[1]; | |
132 | case 1: | |
133 | a += k[0]; | |
134 | }; | |
135 | ||
136 | __jhash_mix (a, b, c); | |
137 | ||
138 | return c; | |
139 | } | |
140 | ||
141 | ||
142 | /* A special ultra-optimized versions that knows they are hashing exactly | |
143 | * 3, 2 or 1 word(s). | |
144 | * | |
145 | * NOTE: In partilar the "c += length; __jhash_mix(a,b,c);" normally | |
146 | * done at the end is not done here. | |
147 | */ | |
148 | u_int32_t | |
149 | jhash_3words (u_int32_t a, u_int32_t b, u_int32_t c, u_int32_t initval) | |
150 | { | |
151 | a += JHASH_GOLDEN_RATIO; | |
152 | b += JHASH_GOLDEN_RATIO; | |
153 | c += initval; | |
154 | ||
155 | __jhash_mix (a, b, c); | |
156 | ||
157 | return c; | |
158 | } | |
159 | ||
160 | u_int32_t | |
161 | jhash_2words (u_int32_t a, u_int32_t b, u_int32_t initval) | |
162 | { | |
163 | return jhash_3words (a, b, 0, initval); | |
164 | } | |
165 | ||
166 | u_int32_t | |
167 | jhash_1word (u_int32_t a, u_int32_t initval) | |
168 | { | |
169 | return jhash_3words (a, 0, 0, initval); | |
170 | } |