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