]>
git.proxmox.com Git - mirror_frr.git/blob - lib/jhash.c
1 /* jhash.h: Jenkins hash support.
3 * Copyright (C) 1996 Bob Jenkins (bob_jenkins@burtleburtle.net)
5 * http://burtleburtle.net/bob/hash/
7 * These are the credits from Bob's sources:
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.
14 * Copyright (C) 2003 David S. Miller (davem@redhat.com)
16 * I've modified Bob's hash to be useful in the Linux kernel, and
17 * any bugs present are surely my fault. -DaveM
23 /* The golden ration: an arbitrary value */
24 #define JHASH_GOLDEN_RATIO 0x9e3779b9
26 /* NOTE: Arguments are modified. */
27 #define __jhash_mix(a, b, c) \
58 /* The most generic version, hashes an arbitrary sequence
59 * of bytes. No alignment or length assumptions are made about
62 u_int32_t
jhash(const void *key
, u_int32_t length
, u_int32_t initval
)
64 u_int32_t a
, b
, c
, len
;
65 const u_int8_t
*k
= key
;
68 a
= b
= JHASH_GOLDEN_RATIO
;
72 a
+= (k
[0] + ((u_int32_t
)k
[1] << 8) + ((u_int32_t
)k
[2] << 16)
73 + ((u_int32_t
)k
[3] << 24));
74 b
+= (k
[4] + ((u_int32_t
)k
[5] << 8) + ((u_int32_t
)k
[6] << 16)
75 + ((u_int32_t
)k
[7] << 24));
76 c
+= (k
[8] + ((u_int32_t
)k
[9] << 8) + ((u_int32_t
)k
[10] << 16)
77 + ((u_int32_t
)k
[11] << 24));
88 c
+= ((u_int32_t
)k
[10] << 24);
91 c
+= ((u_int32_t
)k
[9] << 16);
94 c
+= ((u_int32_t
)k
[8] << 8);
97 b
+= ((u_int32_t
)k
[7] << 24);
100 b
+= ((u_int32_t
)k
[6] << 16);
103 b
+= ((u_int32_t
)k
[5] << 8);
109 a
+= ((u_int32_t
)k
[3] << 24);
112 a
+= ((u_int32_t
)k
[2] << 16);
115 a
+= ((u_int32_t
)k
[1] << 8);
121 __jhash_mix(a
, b
, c
);
126 /* A special optimized version that handles 1 or more of u_int32_ts.
127 * The length parameter here is the number of u_int32_ts in the key.
129 u_int32_t
jhash2(const u_int32_t
*k
, u_int32_t length
, u_int32_t initval
)
131 u_int32_t a
, b
, c
, len
;
133 a
= b
= JHASH_GOLDEN_RATIO
;
141 __jhash_mix(a
, b
, c
);
156 __jhash_mix(a
, b
, c
);
162 /* A special ultra-optimized versions that knows they are hashing exactly
165 * NOTE: In partilar the "c += length; __jhash_mix(a,b,c);" normally
166 * done at the end is not done here.
168 u_int32_t
jhash_3words(u_int32_t a
, u_int32_t b
, u_int32_t c
, u_int32_t initval
)
170 a
+= JHASH_GOLDEN_RATIO
;
171 b
+= JHASH_GOLDEN_RATIO
;
174 __jhash_mix(a
, b
, c
);
179 u_int32_t
jhash_2words(u_int32_t a
, u_int32_t b
, u_int32_t initval
)
181 return jhash_3words(a
, b
, 0, initval
);
184 u_int32_t
jhash_1word(u_int32_t a
, u_int32_t initval
)
186 return jhash_3words(a
, 0, 0, initval
);