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; 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
45 802 : jhash (void *key, u_int32_t length, u_int32_t initval)
46 : {
47 : u_int32_t a, b, c, len;
48 802 : u_int8_t *k = key;
49 :
50 802 : len = length;
51 802 : a = b = JHASH_GOLDEN_RATIO;
52 802 : c = initval;
53 :
54 5534 : while (len >= 12)
55 : {
56 3930 : a +=
57 7860 : (k[0] + ((u_int32_t) k[1] << 8) + ((u_int32_t) k[2] << 16) +
58 3930 : ((u_int32_t) k[3] << 24));
59 3930 : b +=
60 7860 : (k[4] + ((u_int32_t) k[5] << 8) + ((u_int32_t) k[6] << 16) +
61 3930 : ((u_int32_t) k[7] << 24));
62 3930 : c +=
63 7860 : (k[8] + ((u_int32_t) k[9] << 8) + ((u_int32_t) k[10] << 16) +
64 3930 : ((u_int32_t) k[11] << 24));
65 :
66 3930 : __jhash_mix (a, b, c);
67 :
68 3930 : k += 12;
69 3930 : len -= 12;
70 : }
71 :
72 802 : c += length;
73 802 : switch (len)
74 : {
75 : case 11:
76 58 : c += ((u_int32_t) k[10] << 24);
77 : case 10:
78 178 : c += ((u_int32_t) k[9] << 16);
79 : case 9:
80 211 : c += ((u_int32_t) k[8] << 8);
81 : case 8:
82 211 : b += ((u_int32_t) k[7] << 24);
83 : case 7:
84 239 : b += ((u_int32_t) k[6] << 16);
85 : case 6:
86 295 : b += ((u_int32_t) k[5] << 8);
87 : case 5:
88 462 : b += k[4];
89 : case 4:
90 494 : a += ((u_int32_t) k[3] << 24);
91 : case 3:
92 531 : a += ((u_int32_t) k[2] << 16);
93 : case 2:
94 552 : a += ((u_int32_t) k[1] << 8);
95 : case 1:
96 650 : a += k[0];
97 : };
98 :
99 802 : __jhash_mix (a, b, c);
100 :
101 802 : 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
108 0 : jhash2 (u_int32_t * k, u_int32_t length, u_int32_t initval)
109 : {
110 : u_int32_t a, b, c, len;
111 :
112 0 : a = b = JHASH_GOLDEN_RATIO;
113 0 : c = initval;
114 0 : len = length;
115 :
116 0 : while (len >= 3)
117 : {
118 0 : a += k[0];
119 0 : b += k[1];
120 0 : c += k[2];
121 0 : __jhash_mix (a, b, c);
122 0 : k += 3;
123 0 : len -= 3;
124 : }
125 :
126 0 : c += length * 4;
127 :
128 0 : switch (len)
129 : {
130 : case 2:
131 0 : b += k[1];
132 : case 1:
133 0 : a += k[0];
134 : };
135 :
136 0 : __jhash_mix (a, b, c);
137 :
138 0 : 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 0 : jhash_3words (u_int32_t a, u_int32_t b, u_int32_t c, u_int32_t initval)
150 : {
151 0 : a += JHASH_GOLDEN_RATIO;
152 0 : b += JHASH_GOLDEN_RATIO;
153 0 : c += initval;
154 :
155 0 : __jhash_mix (a, b, c);
156 :
157 0 : return c;
158 : }
159 :
160 : u_int32_t
161 0 : jhash_2words (u_int32_t a, u_int32_t b, u_int32_t initval)
162 : {
163 0 : return jhash_3words (a, b, 0, initval);
164 : }
165 :
166 : u_int32_t
167 0 : jhash_1word (u_int32_t a, u_int32_t initval)
168 : {
169 0 : return jhash_3words (a, 0, 0, initval);
170 : }
|
