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 14259 : uint32_t jhash(const void *key, uint32_t length, uint32_t initval)
63 : {
64 14259 : uint32_t a, b, c, len;
65 14259 : const uint8_t *k = key;
66 :
67 14259 : len = length;
68 14259 : a = b = JHASH_GOLDEN_RATIO;
69 14259 : c = initval;
70 :
71 14996 : while (len >= 12) {
72 737 : a += (k[0] + ((uint32_t)k[1] << 8) + ((uint32_t)k[2] << 16)
73 737 : + ((uint32_t)k[3] << 24));
74 737 : b += (k[4] + ((uint32_t)k[5] << 8) + ((uint32_t)k[6] << 16)
75 737 : + ((uint32_t)k[7] << 24));
76 737 : c += (k[8] + ((uint32_t)k[9] << 8) + ((uint32_t)k[10] << 16)
77 737 : + ((uint32_t)k[11] << 24));
78 :
79 737 : __jhash_mix(a, b, c);
80 :
81 737 : k += 12;
82 737 : len -= 12;
83 : }
84 :
85 14259 : c += length;
86 14259 : switch (len) {
87 30 : case 11:
88 30 : c += ((uint32_t)k[10] << 24);
89 100 : fallthrough;
90 100 : case 10:
91 100 : c += ((uint32_t)k[9] << 16);
92 141 : fallthrough;
93 141 : case 9:
94 141 : c += ((uint32_t)k[8] << 8);
95 13492 : fallthrough;
96 13492 : case 8:
97 13492 : b += ((uint32_t)k[7] << 24);
98 13500 : fallthrough;
99 13500 : case 7:
100 13500 : b += ((uint32_t)k[6] << 16);
101 13574 : fallthrough;
102 13574 : case 6:
103 13574 : b += ((uint32_t)k[5] << 8);
104 13618 : fallthrough;
105 13618 : case 5:
106 13618 : b += k[4];
107 13882 : fallthrough;
108 13882 : case 4:
109 13882 : a += ((uint32_t)k[3] << 24);
110 13920 : fallthrough;
111 13920 : case 3:
112 13920 : a += ((uint32_t)k[2] << 16);
113 13922 : fallthrough;
114 13922 : case 2:
115 13922 : a += ((uint32_t)k[1] << 8);
116 13930 : fallthrough;
117 13930 : case 1:
118 13930 : a += k[0];
119 : }
120 :
121 14259 : __jhash_mix(a, b, c);
122 :
123 14259 : 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 220 : uint32_t jhash2(const uint32_t *k, uint32_t length, uint32_t initval)
130 : {
131 220 : uint32_t a, b, c, len;
132 :
133 220 : a = b = JHASH_GOLDEN_RATIO;
134 220 : c = initval;
135 220 : len = length;
136 :
137 986 : while (len >= 3) {
138 766 : a += k[0];
139 766 : b += k[1];
140 766 : c += k[2];
141 766 : __jhash_mix(a, b, c);
142 766 : k += 3;
143 766 : len -= 3;
144 : }
145 :
146 220 : c += length * 4;
147 :
148 220 : switch (len) {
149 0 : case 2:
150 0 : b += k[1];
151 38 : fallthrough;
152 38 : case 1:
153 38 : a += k[0];
154 : }
155 :
156 220 : __jhash_mix(a, b, c);
157 :
158 220 : 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 1686 : uint32_t jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval)
169 : {
170 1686 : a += JHASH_GOLDEN_RATIO;
171 1686 : b += JHASH_GOLDEN_RATIO;
172 1686 : c += initval;
173 :
174 1686 : __jhash_mix(a, b, c);
175 :
176 1686 : return c;
177 : }
178 :
179 356 : uint32_t jhash_2words(uint32_t a, uint32_t b, uint32_t initval)
180 : {
181 356 : return jhash_3words(a, b, 0, initval);
182 : }
183 :
184 679 : uint32_t jhash_1word(uint32_t a, uint32_t initval)
185 : {
186 679 : return jhash_3words(a, 0, 0, initval);
187 : }
|
