xref: /freebsd/sys/dev/sfxge/common/efx_hash.c (revision 685dc743)

/*-
 * 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-2016 Solarflare Communications Inc.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * 1. Redistributions of source code must retain the above copyright notice,
 *    this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright notice,
 *    this list of conditions and the following disclaimer in the documentation
 *    and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * The views and conclusions contained in the software and documentation are
 * those of the authors and should not be interpreted as representing official
 * policies, either expressed or implied, of the FreeBSD Project.
 */

#include <sys/cdefs.h>
#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