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 16584 : uint32_t jhash(const void *key, uint32_t length, uint32_t initval)
63 : {
64 16584 : uint32_t a, b, c, len;
65 16584 : const uint8_t *k = key;
66 :
67 16584 : len = length;
68 16584 : a = b = JHASH_GOLDEN_RATIO;
69 16584 : c = initval;
70 :
71 17263 : while (len >= 12) {
72 679 : a += (k[0] + ((uint32_t)k[1] << 8) + ((uint32_t)k[2] << 16)
73 679 : + ((uint32_t)k[3] << 24));
74 679 : b += (k[4] + ((uint32_t)k[5] << 8) + ((uint32_t)k[6] << 16)
75 679 : + ((uint32_t)k[7] << 24));
76 679 : c += (k[8] + ((uint32_t)k[9] << 8) + ((uint32_t)k[10] << 16)
77 679 : + ((uint32_t)k[11] << 24));
78 :
79 679 : __jhash_mix(a, b, c);
80 :
81 679 : k += 12;
82 679 : len -= 12;
83 : }
84 :
85 16584 : c += length;
86 16584 : switch (len) {
87 12 : case 11:
88 12 : c += ((uint32_t)k[10] << 24);
89 : /* fallthru */
90 135 : case 10:
91 135 : c += ((uint32_t)k[9] << 16);
92 : /* fallthru */
93 192 : case 9:
94 192 : c += ((uint32_t)k[8] << 8);
95 : /* fallthru */
96 16119 : case 8:
97 16119 : b += ((uint32_t)k[7] << 24);
98 : /* fallthru */
99 16119 : case 7:
100 16119 : b += ((uint32_t)k[6] << 16);
101 : /* fallthru */
102 16123 : case 6:
103 16123 : b += ((uint32_t)k[5] << 8);
104 : /* fallthru */
105 16123 : case 5:
106 16123 : b += k[4];
107 : /* fallthru */
108 16296 : case 4:
109 16296 : a += ((uint32_t)k[3] << 24);
110 : /* fallthru */
111 16312 : case 3:
112 16312 : a += ((uint32_t)k[2] << 16);
113 : /* fallthru */
114 16312 : case 2:
115 16312 : a += ((uint32_t)k[1] << 8);
116 : /* fallthru */
117 16312 : case 1:
118 16312 : a += k[0];
119 : }
120 :
121 16584 : __jhash_mix(a, b, c);
122 :
123 16584 : 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 296 : uint32_t jhash2(const uint32_t *k, uint32_t length, uint32_t initval)
130 : {
131 296 : uint32_t a, b, c, len;
132 :
133 296 : a = b = JHASH_GOLDEN_RATIO;
134 296 : c = initval;
135 296 : len = length;
136 :
137 1480 : while (len >= 3) {
138 1184 : a += k[0];
139 1184 : b += k[1];
140 1184 : c += k[2];
141 1184 : __jhash_mix(a, b, c);
142 1184 : k += 3;
143 1184 : len -= 3;
144 : }
145 :
146 296 : c += length * 4;
147 :
148 296 : 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 296 : __jhash_mix(a, b, c);
157 :
158 296 : 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 1500 : uint32_t jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval)
169 : {
170 1500 : a += JHASH_GOLDEN_RATIO;
171 1500 : b += JHASH_GOLDEN_RATIO;
172 1500 : c += initval;
173 :
174 1500 : __jhash_mix(a, b, c);
175 :
176 1500 : return c;
177 : }
178 :
179 592 : uint32_t jhash_2words(uint32_t a, uint32_t b, uint32_t initval)
180 : {
181 592 : return jhash_3words(a, b, 0, initval);
182 : }
183 :
184 316 : uint32_t jhash_1word(uint32_t a, uint32_t initval)
185 : {
186 316 : return jhash_3words(a, 0, 0, initval);
187 : }
|
