[ceph.git] / ceph / src / seastar / dpdk / drivers / net / sfc / base / efx_hash.c

/* SPDX-License-Identifier: BSD-3-Clause
 *
 * Copyright 2006 Bob Jenkins
 *
 * Derived from public domain source, see
 *     <http://burtleburtle.net/bob/c/lookup3.c>:
 *
 * "lookup3.c, by Bob Jenkins, May 2006, Public Domain.
 *
 *  These are functions for producing 32-bit hashes for hash table lookup...
 *  ...You can use this free for any purpose.  It's in the public domain.
 *  It has no warranty."
 *
 * Copyright (c) 2014-2018 Solarflare Communications Inc.
 * All rights reserved.
 */

#include "efx.h"
#include "efx_impl.h"

/* Hash initial value */
#define	EFX_HASH_INITIAL_VALUE	0xdeadbeef

/*
 * Rotate a 32-bit value left
 *
 * Allow platform to provide an intrinsic or optimised routine and
 * fall-back to a simple shift based implementation.
 */
#if EFSYS_HAS_ROTL_DWORD

#define	EFX_HASH_ROTATE(_value, _shift)					\
	EFSYS_ROTL_DWORD(_value, _shift)

#else

#define	EFX_HASH_ROTATE(_value, _shift)					\
	(((_value) << (_shift)) | ((_value) >> (32 - (_shift))))

#endif

/* Mix three 32-bit values reversibly */
#define	EFX_HASH_MIX(_a, _b, _c)					\
	do {								\
		_a -= _c;						\
		_a ^= EFX_HASH_ROTATE(_c, 4);				\
		_c += _b;						\
		_b -= _a;						\
		_b ^= EFX_HASH_ROTATE(_a, 6);				\
		_a += _c;						\
		_c -= _b;						\
		_c ^= EFX_HASH_ROTATE(_b, 8);				\
		_b += _a;						\
		_a -= _c;						\
		_a ^= EFX_HASH_ROTATE(_c, 16);				\
		_c += _b;						\
		_b -= _a;						\
		_b ^= EFX_HASH_ROTATE(_a, 19);				\
		_a += _c;						\
		_c -= _b;						\
		_c ^= EFX_HASH_ROTATE(_b, 4);				\
		_b += _a;						\
	_NOTE(CONSTANTCONDITION)					\
	} while (B_FALSE)

/* Final mixing of three 32-bit values into one (_c) */
#define	EFX_HASH_FINALISE(_a, _b, _c)					\
	do {								\
		_c ^= _b;						\
		_c -= EFX_HASH_ROTATE(_b, 14);				\
		_a ^= _c;						\
		_a -= EFX_HASH_ROTATE(_c, 11);				\
		_b ^= _a;						\
		_b -= EFX_HASH_ROTATE(_a, 25);				\
		_c ^= _b;						\
		_c -= EFX_HASH_ROTATE(_b, 16);				\
		_a ^= _c;						\
		_a -= EFX_HASH_ROTATE(_c, 4);				\
		_b ^= _a;						\
		_b -= EFX_HASH_ROTATE(_a, 14);				\
		_c ^= _b;						\
		_c -= EFX_HASH_ROTATE(_b, 24);				\
	_NOTE(CONSTANTCONDITION)					\
	} while (B_FALSE)


/* Produce a 32-bit hash from 32-bit aligned input */
	__checkReturn		uint32_t
efx_hash_dwords(
	__in_ecount(count)	uint32_t const *input,
	__in			size_t count,
	__in			uint32_t init)
{
	uint32_t a;
	uint32_t b;
	uint32_t c;

	/* Set up the initial internal state */
	a = b = c = EFX_HASH_INITIAL_VALUE +
		(((uint32_t)count) * sizeof (uint32_t)) + init;

	/* Handle all but the last three dwords of the input */
	while (count > 3) {
		a += input[0];
		b += input[1];
		c += input[2];
		EFX_HASH_MIX(a, b, c);

		count -= 3;
		input += 3;
	}

	/* Handle the left-overs */
	switch (count) {
	case 3:
		c += input[2];
		/* Fall-through */
	case 2:
		b += input[1];
		/* Fall-through */
	case 1:
		a += input[0];
		EFX_HASH_FINALISE(a, b, c);
		break;

	case 0:
		/* Should only get here if count parameter was zero */
		break;
	}

	return (c);
}

#if EFSYS_IS_BIG_ENDIAN

/* Produce a 32-bit hash from arbitrarily aligned input */
	__checkReturn		uint32_t
efx_hash_bytes(
	__in_ecount(length)	uint8_t const *input,
	__in			size_t length,
	__in			uint32_t init)
{
	uint32_t a;
	uint32_t b;
	uint32_t c;

	/* Set up the initial internal state */
	a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init;

	/* Handle all but the last twelve bytes of the input */
	while (length > 12) {
		a += ((uint32_t)input[0]) << 24;
		a += ((uint32_t)input[1]) << 16;
		a += ((uint32_t)input[2]) << 8;
		a += ((uint32_t)input[3]);
		b += ((uint32_t)input[4]) << 24;
		b += ((uint32_t)input[5]) << 16;
		b += ((uint32_t)input[6]) << 8;
		b += ((uint32_t)input[7]);
		c += ((uint32_t)input[8]) << 24;
		c += ((uint32_t)input[9]) << 16;
		c += ((uint32_t)input[10]) << 8;
		c += ((uint32_t)input[11]);
		EFX_HASH_MIX(a, b, c);
		length -= 12;
		input += 12;
	}

	/* Handle the left-overs */
	switch (length) {
	case 12:
		c += ((uint32_t)input[11]);
		/* Fall-through */
	case 11:
		c += ((uint32_t)input[10]) << 8;
		/* Fall-through */
	case 10:
		c += ((uint32_t)input[9]) << 16;
		/* Fall-through */
	case 9:
		c += ((uint32_t)input[8]) << 24;
		/* Fall-through */
	case 8:
		b += ((uint32_t)input[7]);
		/* Fall-through */
	case 7:
		b += ((uint32_t)input[6]) << 8;
		/* Fall-through */
	case 6:
		b += ((uint32_t)input[5]) << 16;
		/* Fall-through */
	case 5:
		b += ((uint32_t)input[4]) << 24;
		/* Fall-through */
	case 4:
		a += ((uint32_t)input[3]);
		/* Fall-through */
	case 3:
		a += ((uint32_t)input[2]) << 8;
		/* Fall-through */
	case 2:
		a += ((uint32_t)input[1]) << 16;
		/* Fall-through */
	case 1:
		a += ((uint32_t)input[0]) << 24;
		EFX_HASH_FINALISE(a, b, c);
		break;

	case 0:
		/* Should only get here if length parameter was zero */
		break;
	}

	return (c);
}

#elif EFSYS_IS_LITTLE_ENDIAN

/* Produce a 32-bit hash from arbitrarily aligned input */
	__checkReturn		uint32_t
efx_hash_bytes(
	__in_ecount(length)	uint8_t const *input,
	__in			size_t length,
	__in			uint32_t init)
{
	uint32_t a;
	uint32_t b;
	uint32_t c;

	/* Set up the initial internal state */
	a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init;

	/* Handle all but the last twelve bytes of the input */
	while (length > 12) {
		a += ((uint32_t)input[0]);
		a += ((uint32_t)input[1]) << 8;
		a += ((uint32_t)input[2]) << 16;
		a += ((uint32_t)input[3]) << 24;
		b += ((uint32_t)input[4]);
		b += ((uint32_t)input[5]) << 8;
		b += ((uint32_t)input[6]) << 16;
		b += ((uint32_t)input[7]) << 24;
		c += ((uint32_t)input[8]);
		c += ((uint32_t)input[9]) << 8;
		c += ((uint32_t)input[10]) << 16;
		c += ((uint32_t)input[11]) << 24;
		EFX_HASH_MIX(a, b, c);
		length -= 12;
		input += 12;
	}

	/* Handle the left-overs */
	switch (length) {
	case 12:
		c += ((uint32_t)input[11]) << 24;
		/* Fall-through */
	case 11:
		c += ((uint32_t)input[10]) << 16;
		/* Fall-through */
	case 10:
		c += ((uint32_t)input[9]) << 8;
		/* Fall-through */
	case 9:
		c += ((uint32_t)input[8]);
		/* Fall-through */
	case 8:
		b += ((uint32_t)input[7]) << 24;
		/* Fall-through */
	case 7:
		b += ((uint32_t)input[6]) << 16;
		/* Fall-through */
	case 6:
		b += ((uint32_t)input[5]) << 8;
		/* Fall-through */
	case 5:
		b += ((uint32_t)input[4]);
		/* Fall-through */
	case 4:
		a += ((uint32_t)input[3]) << 24;
		/* Fall-through */
	case 3:
		a += ((uint32_t)input[2]) << 16;
		/* Fall-through */
	case 2:
		a += ((uint32_t)input[1]) << 8;
		/* Fall-through */
	case 1:
		a += ((uint32_t)input[0]);
		EFX_HASH_FINALISE(a, b, c);
		break;

	case 0:
		/* Should only get here if length parameter was zero */
		break;
	}

	return (c);
}

#else

#error "Neither of EFSYS_IS_{BIG,LITTLE}_ENDIAN is set"

#endif
Commit	Line	Data
9f95a23c TL	1	/* SPDX-License-Identifier: BSD-3-Clause
9f95a23c TL	2	*
11fdf7f2 TL	3	* Copyright 2006 Bob Jenkins
	4	*
	5	* Derived from public domain source, see
	6	* <http://burtleburtle.net/bob/c/lookup3.c>:
	7	*
	8	* "lookup3.c, by Bob Jenkins, May 2006, Public Domain.
	9	*
	10	* These are functions for producing 32-bit hashes for hash table lookup...
	11	* ...You can use this free for any purpose. It's in the public domain.
	12	* It has no warranty."
	13	*
9f95a23c	14	* Copyright (c) 2014-2018 Solarflare Communications Inc.
11fdf7f2	15	* All rights reserved.
11fdf7f2 TL	16	*/
	17
	18	#include "efx.h"
	19	#include "efx_impl.h"
	20
	21	/* Hash initial value */
	22	#define EFX_HASH_INITIAL_VALUE 0xdeadbeef
	23
	24	/*
	25	* Rotate a 32-bit value left
	26	*
	27	* Allow platform to provide an intrinsic or optimised routine and
	28	* fall-back to a simple shift based implementation.
	29	*/
	30	#if EFSYS_HAS_ROTL_DWORD
	31
	32	#define EFX_HASH_ROTATE(_value, _shift) \
	33	EFSYS_ROTL_DWORD(_value, _shift)
	34
	35	#else
	36
	37	#define EFX_HASH_ROTATE(_value, _shift) \
	38	(((_value) << (_shift)) \| ((_value) >> (32 - (_shift))))
	39
	40	#endif
	41
	42	/* Mix three 32-bit values reversibly */
	43	#define EFX_HASH_MIX(_a, _b, _c) \
	44	do { \
	45	_a -= _c; \
	46	_a ^= EFX_HASH_ROTATE(_c, 4); \
	47	_c += _b; \
	48	_b -= _a; \
	49	_b ^= EFX_HASH_ROTATE(_a, 6); \
	50	_a += _c; \
	51	_c -= _b; \
	52	_c ^= EFX_HASH_ROTATE(_b, 8); \
	53	_b += _a; \
	54	_a -= _c; \
	55	_a ^= EFX_HASH_ROTATE(_c, 16); \
	56	_c += _b; \
	57	_b -= _a; \
	58	_b ^= EFX_HASH_ROTATE(_a, 19); \
	59	_a += _c; \
	60	_c -= _b; \
	61	_c ^= EFX_HASH_ROTATE(_b, 4); \
	62	_b += _a; \
	63	_NOTE(CONSTANTCONDITION) \
	64	} while (B_FALSE)
	65
	66	/* Final mixing of three 32-bit values into one (_c) */
	67	#define EFX_HASH_FINALISE(_a, _b, _c) \
	68	do { \
	69	_c ^= _b; \
	70	_c -= EFX_HASH_ROTATE(_b, 14); \
	71	_a ^= _c; \
	72	_a -= EFX_HASH_ROTATE(_c, 11); \
	73	_b ^= _a; \
	74	_b -= EFX_HASH_ROTATE(_a, 25); \
	75	_c ^= _b; \
	76	_c -= EFX_HASH_ROTATE(_b, 16); \
	77	_a ^= _c; \
	78	_a -= EFX_HASH_ROTATE(_c, 4); \
	79	_b ^= _a; \
80	_b -= EFX_HASH_ROTATE(_a, 14); \
81	_c ^= _b; \
82	_c -= EFX_HASH_ROTATE(_b, 24); \
83	_NOTE(CONSTANTCONDITION) \
84	} while (B_FALSE)
85
86
87	/* Produce a 32-bit hash from 32-bit aligned input */
88	__checkReturn uint32_t
89	efx_hash_dwords(
90	__in_ecount(count) uint32_t const *input,
91	__in size_t count,
92	__in uint32_t init)
93	{
94	uint32_t a;
95	uint32_t b;
96	uint32_t c;
97
98	/* Set up the initial internal state */
99	a = b = c = EFX_HASH_INITIAL_VALUE +
100	(((uint32_t)count) * sizeof (uint32_t)) + init;
101
102	/* Handle all but the last three dwords of the input */
103	while (count > 3) {
104	a += input[0];
105	b += input[1];
106	c += input[2];
107	EFX_HASH_MIX(a, b, c);
108
109	count -= 3;
110	input += 3;
111	}
112
113	/* Handle the left-overs */
114	switch (count) {
115	case 3:
116	c += input[2];
117	/* Fall-through */
118	case 2:
119	b += input[1];
120	/* Fall-through */
121	case 1:
122	a += input[0];
123	EFX_HASH_FINALISE(a, b, c);
124	break;
125
126	case 0:
127	/* Should only get here if count parameter was zero */
128	break;
129	}
130
131	return (c);
132	}
133
134	#if EFSYS_IS_BIG_ENDIAN
135
136	/* Produce a 32-bit hash from arbitrarily aligned input */
137	__checkReturn uint32_t
138	efx_hash_bytes(
139	__in_ecount(length) uint8_t const *input,
140	__in size_t length,
141	__in uint32_t init)
142	{
143	uint32_t a;
144	uint32_t b;
145	uint32_t c;
146
147	/* Set up the initial internal state */
148	a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init;
149
150	/* Handle all but the last twelve bytes of the input */
151	while (length > 12) {
152	a += ((uint32_t)input[0]) << 24;
153	a += ((uint32_t)input[1]) << 16;
154	a += ((uint32_t)input[2]) << 8;
155	a += ((uint32_t)input[3]);
156	b += ((uint32_t)input[4]) << 24;
157	b += ((uint32_t)input[5]) << 16;
158	b += ((uint32_t)input[6]) << 8;
159	b += ((uint32_t)input[7]);
160	c += ((uint32_t)input[8]) << 24;
161	c += ((uint32_t)input[9]) << 16;
162	c += ((uint32_t)input[10]) << 8;
163	c += ((uint32_t)input[11]);
164	EFX_HASH_MIX(a, b, c);
165	length -= 12;
166	input += 12;
167	}
168
169	/* Handle the left-overs */
170	switch (length) {
171	case 12:
172	c += ((uint32_t)input[11]);
173	/* Fall-through */
174	case 11:
175	c += ((uint32_t)input[10]) << 8;
176	/* Fall-through */
177	case 10:
178	c += ((uint32_t)input[9]) << 16;
179	/* Fall-through */
180	case 9:
181	c += ((uint32_t)input[8]) << 24;
182	/* Fall-through */
183	case 8:
184	b += ((uint32_t)input[7]);
185	/* Fall-through */
186	case 7:
187	b += ((uint32_t)input[6]) << 8;
188	/* Fall-through */
189	case 6:
190	b += ((uint32_t)input[5]) << 16;
191	/* Fall-through */
192	case 5:
193	b += ((uint32_t)input[4]) << 24;
194	/* Fall-through */
195	case 4:
196	a += ((uint32_t)input[3]);
197	/* Fall-through */
198	case 3:
199	a += ((uint32_t)input[2]) << 8;
200	/* Fall-through */
201	case 2:
202	a += ((uint32_t)input[1]) << 16;
203	/* Fall-through */
204	case 1:
205	a += ((uint32_t)input[0]) << 24;
206	EFX_HASH_FINALISE(a, b, c);
207	break;
208
209	case 0:
210	/* Should only get here if length parameter was zero */
211	break;
212	}
213
214	return (c);
215	}
216
217	#elif EFSYS_IS_LITTLE_ENDIAN
218
219	/* Produce a 32-bit hash from arbitrarily aligned input */
220	__checkReturn uint32_t
221	efx_hash_bytes(
222	__in_ecount(length) uint8_t const *input,
223	__in size_t length,
224	__in uint32_t init)
225	{
226	uint32_t a;
227	uint32_t b;
228	uint32_t c;
229
230	/* Set up the initial internal state */
231	a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init;
232
233	/* Handle all but the last twelve bytes of the input */
234	while (length > 12) {
235	a += ((uint32_t)input[0]);
236	a += ((uint32_t)input[1]) << 8;
237	a += ((uint32_t)input[2]) << 16;
238	a += ((uint32_t)input[3]) << 24;
239	b += ((uint32_t)input[4]);
240	b += ((uint32_t)input[5]) << 8;
241	b += ((uint32_t)input[6]) << 16;
242	b += ((uint32_t)input[7]) << 24;
243	c += ((uint32_t)input[8]);
244	c += ((uint32_t)input[9]) << 8;
245	c += ((uint32_t)input[10]) << 16;
246	c += ((uint32_t)input[11]) << 24;
247	EFX_HASH_MIX(a, b, c);
248	length -= 12;
249	input += 12;
250	}
251
252	/* Handle the left-overs */
253	switch (length) {
254	case 12:
255	c += ((uint32_t)input[11]) << 24;
256	/* Fall-through */
257	case 11:
258	c += ((uint32_t)input[10]) << 16;
259	/* Fall-through */
260	case 10:
261	c += ((uint32_t)input[9]) << 8;
262	/* Fall-through */
263	case 9:
264	c += ((uint32_t)input[8]);
265	/* Fall-through */
266	case 8:
267	b += ((uint32_t)input[7]) << 24;
268	/* Fall-through */
269	case 7:
270	b += ((uint32_t)input[6]) << 16;
271	/* Fall-through */
272	case 6:
273	b += ((uint32_t)input[5]) << 8;
274	/* Fall-through */
275	case 5:
276	b += ((uint32_t)input[4]);
277	/* Fall-through */
278	case 4:
279	a += ((uint32_t)input[3]) << 24;
280	/* Fall-through */
281	case 3:
282	a += ((uint32_t)input[2]) << 16;
283	/* Fall-through */
284	case 2:
285	a += ((uint32_t)input[1]) << 8;
286	/* Fall-through */
287	case 1:
288	a += ((uint32_t)input[0]);
289	EFX_HASH_FINALISE(a, b, c);
290	break;
291
292	case 0:
293	/* Should only get here if length parameter was zero */
294	break;
295	}
296
297	return (c);
298	}
299
300	#else
301
302	#error "Neither of EFSYS_IS_{BIG,LITTLE}_ENDIAN is set"
303
304	#endif