/src/frr/lib/jhash.c

Source (jump to first uncovered line)
/* 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 (jump to first uncovered line)
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.30M	#define JHASH_GOLDEN_RATIO 0x9e3779b9
25
26		/* NOTE: Arguments are modified. */
27		#define __jhash_mix(a, b, c) \
28	1.08M	{ \
29	1.08M	a -= b; \
30	1.08M	a -= c; \
31	1.08M	a ^= (c >> 13); \
32	1.08M	b -= c; \
33	1.08M	b -= a; \
34	1.08M	b ^= (a << 8); \
35	1.08M	c -= a; \
36	1.08M	c -= b; \
37	1.08M	c ^= (b >> 13); \
38	1.08M	a -= b; \
39	1.08M	a -= c; \
40	1.08M	a ^= (c >> 12); \
41	1.08M	b -= c; \
42	1.08M	b -= a; \
43	1.08M	b ^= (a << 16); \
44	1.08M	c -= a; \
45	1.08M	c -= b; \
46	1.08M	c ^= (b >> 5); \
47	1.08M	a -= b; \
48	1.08M	a -= c; \
49	1.08M	a ^= (c >> 3); \
50	1.08M	b -= c; \
51	1.08M	b -= a; \
52	1.08M	b ^= (a << 10); \
53	1.08M	c -= a; \
54	1.08M	c -= b; \
55	1.08M	c ^= (b >> 15); \
56	1.08M	}
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	396k	{
65	396k	uint32_t a, b, c, len;
66	396k	const uint8_t *k = key;
67
68	396k	len = length;
69	396k	a = b = JHASH_GOLDEN_RATIO;
70	396k	c = initval;
71
72	515k	while (len >= 12) {
73	118k	a += (k[0] + ((uint32_t)k[1] << 8) + ((uint32_t)k[2] << 16)
74	118k	+ ((uint32_t)k[3] << 24));
75	118k	b += (k[4] + ((uint32_t)k[5] << 8) + ((uint32_t)k[6] << 16)
76	118k	+ ((uint32_t)k[7] << 24));
77	118k	c += (k[8] + ((uint32_t)k[9] << 8) + ((uint32_t)k[10] << 16)
78	118k	+ ((uint32_t)k[11] << 24));
79
80	118k	__jhash_mix(a, b, c);
81
82	118k	k += 12;
83	118k	len -= 12;
84	118k	}
85
86	396k	c += length;
87	396k	switch (len) {
88	29.7k	case 11:
89	29.7k	c += ((uint32_t)k[10] << 24);
90		/* fallthru */
91	37.9k	case 10:
92	37.9k	c += ((uint32_t)k[9] << 16);
93		/* fallthru */
94	287k	case 9:
95	287k	c += ((uint32_t)k[8] << 8);
96		/* fallthru */
97	313k	case 8:
98	313k	b += ((uint32_t)k[7] << 24);
99		/* fallthru */
100	313k	case 7:
101	313k	b += ((uint32_t)k[6] << 16);
102		/* fallthru */
103	313k	case 6:
104	313k	b += ((uint32_t)k[5] << 8);
105		/* fallthru */
106	313k	case 5:
107	313k	b += k[4];
108		/* fallthru */
109	367k	case 4:
110	367k	a += ((uint32_t)k[3] << 24);
111		/* fallthru */
112	368k	case 3:
113	368k	a += ((uint32_t)k[2] << 16);
114		/* fallthru */
115	368k	case 2:
116	368k	a += ((uint32_t)k[1] << 8);
117		/* fallthru */
118	368k	case 1:
119	368k	a += k[0];
120	396k	}
121
122	396k	__jhash_mix(a, b, c);
123
124	396k	return c;
125	396k	}
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	219k	{
133	219k	uint32_t a, b, c, len;
134
135	219k	a = b = JHASH_GOLDEN_RATIO;
136	219k	c = initval;
137	219k	len = length;
138
139	220k	while (len >= 3) {
140	1.13k	a += k[0];
141	1.13k	b += k[1];
142	1.13k	c += k[2];
143	1.13k	__jhash_mix(a, b, c);
144	1.13k	k += 3;
145	1.13k	len -= 3;
146	1.13k	}
147
148	219k	c += length * 4;
149
150	219k	switch (len) {
151	219k	case 2:
152	219k	b += k[1];
153		/* fallthru */
154	219k	case 1:
155	219k	a += k[0];
156	219k	}
157
158	219k	__jhash_mix(a, b, c);
159
160	219k	return c;
161	219k	}
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	346k	{
173	346k	a += JHASH_GOLDEN_RATIO;
174	346k	b += JHASH_GOLDEN_RATIO;
175	346k	c += initval;
176
177	346k	__jhash_mix(a, b, c);
178
179	346k	return c;
180	346k	}
181
182		uint32_t jhash_2words(uint32_t a, uint32_t b, uint32_t initval)
183	0	{
184	0	return jhash_3words(a, b, 0, initval);
185	0	}
186
187		uint32_t jhash_1word(uint32_t a, uint32_t initval)
188	346k	{
189	346k	return jhash_3words(a, 0, 0, initval);
190	346k	}

Coverage Report

Created: 2025-07-14 06:48