Changeset View
Changeset View
Standalone View
Standalone View
head/sys/dev/sfxge/common/efx_hash.c
Property | Old Value | New Value |
---|---|---|
svn:eol-style | null | native \ No newline at end of property |
svn:keywords | null | FreeBSD=%H \ No newline at end of property |
svn:mime-type | null | text/plain \ No newline at end of property |
/*- | |||||
* 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-2015 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> | |||||
__FBSDID("$FreeBSD$"); | |||||
#include "efsys.h" | |||||
#include "efx.h" | |||||
#include "efx_types.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 |