Line data Source code
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; \
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 : }
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 : */
62 12321 : uint32_t jhash(const void *key, uint32_t length, uint32_t initval)
63 : {
64 12321 : uint32_t a, b, c, len;
65 12321 : const uint8_t *k = key;
66 :
67 12321 : len = length;
68 12321 : a = b = JHASH_GOLDEN_RATIO;
69 12321 : c = initval;
70 :
71 12683 : while (len >= 12) {
72 362 : a += (k[0] + ((uint32_t)k[1] << 8) + ((uint32_t)k[2] << 16)
73 362 : + ((uint32_t)k[3] << 24));
74 362 : b += (k[4] + ((uint32_t)k[5] << 8) + ((uint32_t)k[6] << 16)
75 362 : + ((uint32_t)k[7] << 24));
76 362 : c += (k[8] + ((uint32_t)k[9] << 8) + ((uint32_t)k[10] << 16)
77 362 : + ((uint32_t)k[11] << 24));
78 :
79 362 : __jhash_mix(a, b, c);
80 :
81 362 : k += 12;
82 362 : len -= 12;
83 : }
84 :
85 12321 : c += length;
86 12321 : switch (len) {
87 9 : case 11:
88 9 : c += ((uint32_t)k[10] << 24);
89 : /* fallthru */
90 51 : case 10:
91 51 : c += ((uint32_t)k[9] << 16);
92 : /* fallthru */
93 84 : case 9:
94 84 : c += ((uint32_t)k[8] << 8);
95 : /* fallthru */
96 11989 : case 8:
97 11989 : b += ((uint32_t)k[7] << 24);
98 : /* fallthru */
99 11989 : case 7:
100 11989 : b += ((uint32_t)k[6] << 16);
101 : /* fallthru */
102 11992 : case 6:
103 11992 : b += ((uint32_t)k[5] << 8);
104 : /* fallthru */
105 11992 : case 5:
106 11992 : b += k[4];
107 : /* fallthru */
108 12043 : case 4:
109 12043 : a += ((uint32_t)k[3] << 24);
110 : /* fallthru */
111 12055 : case 3:
112 12055 : a += ((uint32_t)k[2] << 16);
113 : /* fallthru */
114 12055 : case 2:
115 12055 : a += ((uint32_t)k[1] << 8);
116 : /* fallthru */
117 12055 : case 1:
118 12055 : a += k[0];
119 : }
120 :
121 12321 : __jhash_mix(a, b, c);
122 :
123 12321 : return c;
124 : }
125 :
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.
128 : */
129 165 : uint32_t jhash2(const uint32_t *k, uint32_t length, uint32_t initval)
130 : {
131 165 : uint32_t a, b, c, len;
132 :
133 165 : a = b = JHASH_GOLDEN_RATIO;
134 165 : c = initval;
135 165 : len = length;
136 :
137 825 : while (len >= 3) {
138 660 : a += k[0];
139 660 : b += k[1];
140 660 : c += k[2];
141 660 : __jhash_mix(a, b, c);
142 660 : k += 3;
143 660 : len -= 3;
144 : }
145 :
146 165 : c += length * 4;
147 :
148 165 : switch (len) {
149 0 : case 2:
150 0 : b += k[1];
151 : /* fallthru */
152 0 : case 1:
153 0 : a += k[0];
154 : }
155 :
156 165 : __jhash_mix(a, b, c);
157 :
158 165 : return c;
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 : */
168 852 : uint32_t jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval)
169 : {
170 852 : a += JHASH_GOLDEN_RATIO;
171 852 : b += JHASH_GOLDEN_RATIO;
172 852 : c += initval;
173 :
174 852 : __jhash_mix(a, b, c);
175 :
176 852 : return c;
177 : }
178 :
179 347 : uint32_t jhash_2words(uint32_t a, uint32_t b, uint32_t initval)
180 : {
181 347 : return jhash_3words(a, b, 0, initval);
182 : }
183 :
184 175 : uint32_t jhash_1word(uint32_t a, uint32_t initval)
185 : {
186 175 : return jhash_3words(a, 0, 0, initval);
187 : }
|
