/src/frr/lib/jhash.c

Source
/* jhash.h: Jenkins hash support.
 *
 * Copyright (C) 1996 Bob Jenkins (bob_jenkins@burtleburtle.net)
 *
 * http://burtleburtle.net/bob/hash/
 *
 * These are the credits from Bob's sources:
 *
 * lookup2.c, by Bob Jenkins, December 1996, Public Domain.
 * hash(), hash2(), hash3, and mix() are externally useful functions.
 * Routines to test the hash are included if SELF_TEST is defined.
 * You can use this free for any purpose.  It has no warranty.
 *
 * Copyright (C) 2003 David S. Miller (davem@redhat.com)
 *
 * I've modified Bob's hash to be useful in the Linux kernel, and
 * any bugs present are surely my fault.  -DaveM
 */

#include "zebra.h"
#include "jhash.h"

/* The golden ration: an arbitrary value */
#define JHASH_GOLDEN_RATIO  0x9e3779b9

/* NOTE: Arguments are modified. */
#define __jhash_mix(a, b, c)                                                   \
  {                                                                      \
    a -= b;                                                        \
    a -= c;                                                        \
    a ^= (c >> 13);                                                \
    b -= c;                                                        \
    b -= a;                                                        \
    b ^= (a << 8);                                                 \
    c -= a;                                                        \
    c -= b;                                                        \
    c ^= (b >> 13);                                                \
    a -= b;                                                        \
    a -= c;                                                        \
    a ^= (c >> 12);                                                \
    b -= c;                                                        \
    b -= a;                                                        \
    b ^= (a << 16);                                                \
    c -= a;                                                        \
    c -= b;                                                        \
    c ^= (b >> 5);                                                 \
    a -= b;                                                        \
    a -= c;                                                        \
    a ^= (c >> 3);                                                 \
    b -= c;                                                        \
    b -= a;                                                        \
    b ^= (a << 10);                                                \
    c -= a;                                                        \
    c -= b;                                                        \
    c ^= (b >> 15);                                                \
  }

/* The most generic version, hashes an arbitrary sequence
 * of bytes.  No alignment or length assumptions are made about
 * the input key.
 */
uint32_t jhash(const void *key, uint32_t length, uint32_t initval)
  __attribute__((no_sanitize("unsigned-integer-overflow")))
{
  uint32_t a, b, c, len;
  const uint8_t *k = key;

  len = length;
  a = b = JHASH_GOLDEN_RATIO;
  c = initval;

  while (len >= 12) {
    a += (k[0] + ((uint32_t)k[1] << 8) + ((uint32_t)k[2] << 16)
          + ((uint32_t)k[3] << 24));
    b += (k[4] + ((uint32_t)k[5] << 8) + ((uint32_t)k[6] << 16)
          + ((uint32_t)k[7] << 24));
    c += (k[8] + ((uint32_t)k[9] << 8) + ((uint32_t)k[10] << 16)
          + ((uint32_t)k[11] << 24));

    __jhash_mix(a, b, c);

    k += 12;
    len -= 12;
  }

  c += length;
  switch (len) {
  case 11:
    c += ((uint32_t)k[10] << 24);
  /* fallthru */
  case 10:
    c += ((uint32_t)k[9] << 16);
  /* fallthru */
  case 9:
    c += ((uint32_t)k[8] << 8);
  /* fallthru */
  case 8:
    b += ((uint32_t)k[7] << 24);
  /* fallthru */
  case 7:
    b += ((uint32_t)k[6] << 16);
  /* fallthru */
  case 6:
    b += ((uint32_t)k[5] << 8);
  /* fallthru */
  case 5:
    b += k[4];
  /* fallthru */
  case 4:
    a += ((uint32_t)k[3] << 24);
  /* fallthru */
  case 3:
    a += ((uint32_t)k[2] << 16);
  /* fallthru */
  case 2:
    a += ((uint32_t)k[1] << 8);
  /* fallthru */
  case 1:
    a += k[0];
  }

  __jhash_mix(a, b, c);

  return c;
}

/* A special optimized version that handles 1 or more of uint32_ts.
 * The length parameter here is the number of uint32_ts in the key.
 */
uint32_t jhash2(const uint32_t *k, uint32_t length, uint32_t initval)
  __attribute__((no_sanitize("unsigned-integer-overflow")))
{
  uint32_t a, b, c, len;

  a = b = JHASH_GOLDEN_RATIO;
  c = initval;
  len = length;

  while (len >= 3) {
    a += k[0];
    b += k[1];
    c += k[2];
    __jhash_mix(a, b, c);
    k += 3;
    len -= 3;
  }

  c += length * 4;

  switch (len) {
  case 2:
    b += k[1];
  /* fallthru */
  case 1:
    a += k[0];
  }

  __jhash_mix(a, b, c);

  return c;
}


/* A special ultra-optimized versions that knows they are hashing exactly
 * 3, 2 or 1 word(s).
 *
 * NOTE: In partilar the "c += length; __jhash_mix(a,b,c);" normally
 *       done at the end is not done here.
 */
uint32_t jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval)
  __attribute__((no_sanitize("unsigned-integer-overflow")))
{
  a += JHASH_GOLDEN_RATIO;
  b += JHASH_GOLDEN_RATIO;
  c += initval;

  __jhash_mix(a, b, c);

  return c;
}

uint32_t jhash_2words(uint32_t a, uint32_t b, uint32_t initval)
{
  return jhash_3words(a, b, 0, initval);
}

uint32_t jhash_1word(uint32_t a, uint32_t initval)
{
  return jhash_3words(a, 0, 0, initval);
}

Line	Count	Source
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	1.19M	#define JHASH_GOLDEN_RATIO 0x9e3779b9
25
26		/* NOTE: Arguments are modified. */
27		#define __jhash_mix(a, b, c) \
28	990k	{ \
29	990k	a -= b; \
30	990k	a -= c; \
31	990k	a ^= (c >> 13); \
32	990k	b -= c; \
33	990k	b -= a; \
34	990k	b ^= (a << 8); \
35	990k	c -= a; \
36	990k	c -= b; \
37	990k	c ^= (b >> 13); \
38	990k	a -= b; \
39	990k	a -= c; \
40	990k	a ^= (c >> 12); \
41	990k	b -= c; \
42	990k	b -= a; \
43	990k	b ^= (a << 16); \
44	990k	c -= a; \
45	990k	c -= b; \
46	990k	c ^= (b >> 5); \
47	990k	a -= b; \
48	990k	a -= c; \
49	990k	a ^= (c >> 3); \
50	990k	b -= c; \
51	990k	b -= a; \
52	990k	b ^= (a << 10); \
53	990k	c -= a; \
54	990k	c -= b; \
55	990k	c ^= (b >> 15); \
56	990k	}
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		uint32_t jhash(const void *key, uint32_t length, uint32_t initval)
63		__attribute__((no_sanitize("unsigned-integer-overflow")))
64	397k	{
65	397k	uint32_t a, b, c, len;
66	397k	const uint8_t *k = key;
67
68	397k	len = length;
69	397k	a = b = JHASH_GOLDEN_RATIO;
70	397k	c = initval;
71
72	500k	while (len >= 12) {
73	103k	a += (k[0] + ((uint32_t)k[1] << 8) + ((uint32_t)k[2] << 16)
74	103k	+ ((uint32_t)k[3] << 24));
75	103k	b += (k[4] + ((uint32_t)k[5] << 8) + ((uint32_t)k[6] << 16)
76	103k	+ ((uint32_t)k[7] << 24));
77	103k	c += (k[8] + ((uint32_t)k[9] << 8) + ((uint32_t)k[10] << 16)
78	103k	+ ((uint32_t)k[11] << 24));
79
80	103k	__jhash_mix(a, b, c);
81
82	103k	k += 12;
83	103k	len -= 12;
84	103k	}
85
86	397k	c += length;
87	397k	switch (len) {
88	43.3k	case 11:
89	43.3k	c += ((uint32_t)k[10] << 24);
90		/* fallthru */
91	50.6k	case 10:
92	50.6k	c += ((uint32_t)k[9] << 16);
93		/* fallthru */
94	294k	case 9:
95	294k	c += ((uint32_t)k[8] << 8);
96		/* fallthru */
97	318k	case 8:
98	318k	b += ((uint32_t)k[7] << 24);
99		/* fallthru */
100	318k	case 7:
101	318k	b += ((uint32_t)k[6] << 16);
102		/* fallthru */
103	318k	case 6:
104	318k	b += ((uint32_t)k[5] << 8);
105		/* fallthru */
106	319k	case 5:
107	319k	b += k[4];
108		/* fallthru */
109	372k	case 4:
110	372k	a += ((uint32_t)k[3] << 24);
111		/* fallthru */
112	374k	case 3:
113	374k	a += ((uint32_t)k[2] << 16);
114		/* fallthru */
115	375k	case 2:
116	375k	a += ((uint32_t)k[1] << 8);
117		/* fallthru */
118	376k	case 1:
119	376k	a += k[0];
120	397k	}
121
122	397k	__jhash_mix(a, b, c);
123
124	397k	return c;
125	397k	}
126
127		/* A special optimized version that handles 1 or more of uint32_ts.
128		* The length parameter here is the number of uint32_ts in the key.
129		*/
130		uint32_t jhash2(const uint32_t *k, uint32_t length, uint32_t initval)
131		__attribute__((no_sanitize("unsigned-integer-overflow")))
132	164k	{
133	164k	uint32_t a, b, c, len;
134
135	164k	a = b = JHASH_GOLDEN_RATIO;
136	164k	c = initval;
137	164k	len = length;
138
139	175k	while (len >= 3) {
140	10.9k	a += k[0];
141	10.9k	b += k[1];
142	10.9k	c += k[2];
143	10.9k	__jhash_mix(a, b, c);
144	10.9k	k += 3;
145	10.9k	len -= 3;
146	10.9k	}
147
148	164k	c += length * 4;
149
150	164k	switch (len) {
151	164k	case 2:
152	164k	b += k[1];
153		/* fallthru */
154	164k	case 1:
155	164k	a += k[0];
156	164k	}
157
158	164k	__jhash_mix(a, b, c);
159
160	164k	return c;
161	164k	}
162
163
164		/* A special ultra-optimized versions that knows they are hashing exactly
165		* 3, 2 or 1 word(s).
166		*
167		* NOTE: In partilar the "c += length; __jhash_mix(a,b,c);" normally
168		* done at the end is not done here.
169		*/
170		uint32_t jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval)
171		__attribute__((no_sanitize("unsigned-integer-overflow")))
172	314k	{
173	314k	a += JHASH_GOLDEN_RATIO;
174	314k	b += JHASH_GOLDEN_RATIO;
175	314k	c += initval;
176
177	314k	__jhash_mix(a, b, c);
178
179	314k	return c;
180	314k	}
181
182		uint32_t jhash_2words(uint32_t a, uint32_t b, uint32_t initval)
183	17.6k	{
184	17.6k	return jhash_3words(a, b, 0, initval);
185	17.6k	}
186
187		uint32_t jhash_1word(uint32_t a, uint32_t initval)
188	285k	{
189	285k	return jhash_3words(a, 0, 0, initval);
190	285k	}

Coverage Report

Created: 2026-01-21 06:59