]>
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) \
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); \
40 /* The most generic version, hashes an arbitrary sequence
41 * of bytes. No alignment or length assumptions are made about
45 jhash (const void *key
, u_int32_t length
, u_int32_t initval
)
47 u_int32_t a
, b
, c
, len
;
48 const u_int8_t
*k
= key
;
51 a
= b
= JHASH_GOLDEN_RATIO
;
57 (k
[0] + ((u_int32_t
) k
[1] << 8) + ((u_int32_t
) k
[2] << 16) +
58 ((u_int32_t
) k
[3] << 24));
60 (k
[4] + ((u_int32_t
) k
[5] << 8) + ((u_int32_t
) k
[6] << 16) +
61 ((u_int32_t
) k
[7] << 24));
63 (k
[8] + ((u_int32_t
) k
[9] << 8) + ((u_int32_t
) k
[10] << 16) +
64 ((u_int32_t
) k
[11] << 24));
66 __jhash_mix (a
, b
, c
);
76 c
+= ((u_int32_t
) k
[10] << 24);
79 c
+= ((u_int32_t
) k
[9] << 16);
82 c
+= ((u_int32_t
) k
[8] << 8);
85 b
+= ((u_int32_t
) k
[7] << 24);
88 b
+= ((u_int32_t
) k
[6] << 16);
91 b
+= ((u_int32_t
) k
[5] << 8);
97 a
+= ((u_int32_t
) k
[3] << 24);
100 a
+= ((u_int32_t
) k
[2] << 16);
103 a
+= ((u_int32_t
) k
[1] << 8);
109 __jhash_mix (a
, b
, c
);
114 /* A special optimized version that handles 1 or more of u_int32_ts.
115 * The length parameter here is the number of u_int32_ts in the key.
118 jhash2 (const u_int32_t
*k
, u_int32_t length
, u_int32_t initval
)
120 u_int32_t a
, b
, c
, len
;
122 a
= b
= JHASH_GOLDEN_RATIO
;
131 __jhash_mix (a
, b
, c
);
147 __jhash_mix (a
, b
, c
);
153 /* A special ultra-optimized versions that knows they are hashing exactly
156 * NOTE: In partilar the "c += length; __jhash_mix(a,b,c);" normally
157 * done at the end is not done here.
160 jhash_3words (u_int32_t a
, u_int32_t b
, u_int32_t c
, u_int32_t initval
)
162 a
+= JHASH_GOLDEN_RATIO
;
163 b
+= JHASH_GOLDEN_RATIO
;
166 __jhash_mix (a
, b
, c
);
172 jhash_2words (u_int32_t a
, u_int32_t b
, u_int32_t initval
)
174 return jhash_3words (a
, b
, 0, initval
);
178 jhash_1word (u_int32_t a
, u_int32_t initval
)
180 return jhash_3words (a
, 0, 0, initval
);