672386c1e9
Bump copyright year to 2021. Signed-off-by: Andrew Rybchenko <andrew.rybchenko@oktetlabs.ru>
305 lines
6.6 KiB
C
305 lines
6.6 KiB
C
/* 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
|