/* * Copyright 2006 Bob Jenkins * * Derived from public domain source, see * : * * "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 "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]; /* FALLTHROUGH */ case 2: b += input[1]; /* FALLTHROUGH */ 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; /* FALLTHROUGH */ case 11: c += ((uint32_t)input[10]) << 16; /* FALLTHROUGH */ case 10: c += ((uint32_t)input[9]) << 8; /* FALLTHROUGH */ case 9: c += ((uint32_t)input[8]); /* FALLTHROUGH */ case 8: b += ((uint32_t)input[7]) << 24; /* FALLTHROUGH */ case 7: b += ((uint32_t)input[6]) << 16; /* FALLTHROUGH */ case 6: b += ((uint32_t)input[5]) << 8; /* FALLTHROUGH */ case 5: b += ((uint32_t)input[4]); /* FALLTHROUGH */ case 4: a += ((uint32_t)input[3]) << 24; /* FALLTHROUGH */ case 3: a += ((uint32_t)input[2]) << 16; /* FALLTHROUGH */ case 2: a += ((uint32_t)input[1]) << 8; /* FALLTHROUGH */ 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