xref: /dpdk/drivers/common/sfc_efx/base/efx_hash.c (revision 672386c1e9e1f64f7aa3b1360ad22dc737ea8d72)

/* SPDX-License-Identifier: BSD-3-Clause
 *
 * Copyright(c) 2019-2021 Xilinx, Inc.
 * Copyright(c) 2014-2019 Solarflare Communications Inc.
 *
 * 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."
 */

#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