]>
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. */ | |
d62a17ae | 27 | #define __jhash_mix(a, b, c) \ |
28 | { \ | |
29 | a -= b; \ | |
30 | a -= c; \ | |
31 | a ^= (c >> 13); \ | |
32 | b -= c; \ | |
33 | b -= a; \ | |
34 | b ^= (a << 8); \ | |
35 | c -= a; \ | |
36 | c -= b; \ | |
37 | c ^= (b >> 13); \ | |
38 | a -= b; \ | |
39 | a -= c; \ | |
40 | a ^= (c >> 12); \ | |
41 | b -= c; \ | |
42 | b -= a; \ | |
43 | b ^= (a << 16); \ | |
44 | c -= a; \ | |
45 | c -= b; \ | |
46 | c ^= (b >> 5); \ | |
47 | a -= b; \ | |
48 | a -= c; \ | |
49 | a ^= (c >> 3); \ | |
50 | b -= c; \ | |
51 | b -= a; \ | |
52 | b ^= (a << 10); \ | |
53 | c -= a; \ | |
54 | c -= b; \ | |
55 | c ^= (b >> 15); \ | |
56 | } | |
b9790b34 | 57 | |
58 | /* The most generic version, hashes an arbitrary sequence | |
59 | * of bytes. No alignment or length assumptions are made about | |
60 | * the input key. | |
61 | */ | |
d7c0a89a | 62 | uint32_t jhash(const void *key, uint32_t length, uint32_t initval) |
b9790b34 | 63 | { |
d7c0a89a QY |
64 | uint32_t a, b, c, len; |
65 | const uint8_t *k = key; | |
d62a17ae | 66 | |
67 | len = length; | |
68 | a = b = JHASH_GOLDEN_RATIO; | |
69 | c = initval; | |
70 | ||
71 | while (len >= 12) { | |
d7c0a89a QY |
72 | a += (k[0] + ((uint32_t)k[1] << 8) + ((uint32_t)k[2] << 16) |
73 | + ((uint32_t)k[3] << 24)); | |
74 | b += (k[4] + ((uint32_t)k[5] << 8) + ((uint32_t)k[6] << 16) | |
75 | + ((uint32_t)k[7] << 24)); | |
76 | c += (k[8] + ((uint32_t)k[9] << 8) + ((uint32_t)k[10] << 16) | |
77 | + ((uint32_t)k[11] << 24)); | |
d62a17ae | 78 | |
79 | __jhash_mix(a, b, c); | |
80 | ||
81 | k += 12; | |
82 | len -= 12; | |
83 | } | |
84 | ||
85 | c += length; | |
86 | switch (len) { | |
87 | case 11: | |
d7c0a89a | 88 | c += ((uint32_t)k[10] << 24); |
d62a17ae | 89 | /* fallthru */ |
90 | case 10: | |
d7c0a89a | 91 | c += ((uint32_t)k[9] << 16); |
d62a17ae | 92 | /* fallthru */ |
93 | case 9: | |
d7c0a89a | 94 | c += ((uint32_t)k[8] << 8); |
d62a17ae | 95 | /* fallthru */ |
96 | case 8: | |
d7c0a89a | 97 | b += ((uint32_t)k[7] << 24); |
d62a17ae | 98 | /* fallthru */ |
99 | case 7: | |
d7c0a89a | 100 | b += ((uint32_t)k[6] << 16); |
d62a17ae | 101 | /* fallthru */ |
102 | case 6: | |
d7c0a89a | 103 | b += ((uint32_t)k[5] << 8); |
d62a17ae | 104 | /* fallthru */ |
105 | case 5: | |
106 | b += k[4]; | |
107 | /* fallthru */ | |
108 | case 4: | |
d7c0a89a | 109 | a += ((uint32_t)k[3] << 24); |
d62a17ae | 110 | /* fallthru */ |
111 | case 3: | |
d7c0a89a | 112 | a += ((uint32_t)k[2] << 16); |
d62a17ae | 113 | /* fallthru */ |
114 | case 2: | |
d7c0a89a | 115 | a += ((uint32_t)k[1] << 8); |
d62a17ae | 116 | /* fallthru */ |
117 | case 1: | |
118 | a += k[0]; | |
5b94ec50 | 119 | } |
d62a17ae | 120 | |
121 | __jhash_mix(a, b, c); | |
122 | ||
123 | return c; | |
b9790b34 | 124 | } |
125 | ||
d7c0a89a QY |
126 | /* A special optimized version that handles 1 or more of uint32_ts. |
127 | * The length parameter here is the number of uint32_ts in the key. | |
b9790b34 | 128 | */ |
d7c0a89a | 129 | uint32_t jhash2(const uint32_t *k, uint32_t length, uint32_t initval) |
b9790b34 | 130 | { |
d7c0a89a | 131 | uint32_t a, b, c, len; |
d62a17ae | 132 | |
133 | a = b = JHASH_GOLDEN_RATIO; | |
134 | c = initval; | |
135 | len = length; | |
136 | ||
137 | while (len >= 3) { | |
138 | a += k[0]; | |
139 | b += k[1]; | |
140 | c += k[2]; | |
141 | __jhash_mix(a, b, c); | |
142 | k += 3; | |
143 | len -= 3; | |
144 | } | |
145 | ||
146 | c += length * 4; | |
147 | ||
148 | switch (len) { | |
149 | case 2: | |
150 | b += k[1]; | |
151 | /* fallthru */ | |
152 | case 1: | |
153 | a += k[0]; | |
5b94ec50 | 154 | } |
d62a17ae | 155 | |
156 | __jhash_mix(a, b, c); | |
157 | ||
158 | return c; | |
b9790b34 | 159 | } |
160 | ||
161 | ||
162 | /* A special ultra-optimized versions that knows they are hashing exactly | |
163 | * 3, 2 or 1 word(s). | |
164 | * | |
165 | * NOTE: In partilar the "c += length; __jhash_mix(a,b,c);" normally | |
166 | * done at the end is not done here. | |
167 | */ | |
d7c0a89a | 168 | uint32_t jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval) |
b9790b34 | 169 | { |
d62a17ae | 170 | a += JHASH_GOLDEN_RATIO; |
171 | b += JHASH_GOLDEN_RATIO; | |
172 | c += initval; | |
b9790b34 | 173 | |
d62a17ae | 174 | __jhash_mix(a, b, c); |
b9790b34 | 175 | |
d62a17ae | 176 | return c; |
b9790b34 | 177 | } |
178 | ||
d7c0a89a | 179 | uint32_t jhash_2words(uint32_t a, uint32_t b, uint32_t initval) |
b9790b34 | 180 | { |
d62a17ae | 181 | return jhash_3words(a, b, 0, initval); |
b9790b34 | 182 | } |
183 | ||
d7c0a89a | 184 | uint32_t jhash_1word(uint32_t a, uint32_t initval) |
b9790b34 | 185 | { |
d62a17ae | 186 | return jhash_3words(a, 0, 0, initval); |
b9790b34 | 187 | } |