diff options
Diffstat (limited to 'drivers/net/sfc/base/efx_hash.c')
| -rw-r--r-- | drivers/net/sfc/base/efx_hash.c | 328 |
1 files changed, 328 insertions, 0 deletions
diff --git a/drivers/net/sfc/base/efx_hash.c b/drivers/net/sfc/base/efx_hash.c new file mode 100644 index 00000000..3cc0d200 --- /dev/null +++ b/drivers/net/sfc/base/efx_hash.c @@ -0,0 +1,328 @@ +/* + * 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 "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 |