efx_hash.c revision 283514
1283514Sarybchik/*- 2283514Sarybchik * Copyright 2006 Bob Jenkins 3283514Sarybchik * 4283514Sarybchik * Derived from public domain source, see 5283514Sarybchik * <http://burtleburtle.net/bob/c/lookup3.c>: 6283514Sarybchik * 7283514Sarybchik * "lookup3.c, by Bob Jenkins, May 2006, Public Domain. 8283514Sarybchik * 9283514Sarybchik * These are functions for producing 32-bit hashes for hash table lookup... 10283514Sarybchik * ...You can use this free for any purpose. It's in the public domain. 11283514Sarybchik * It has no warranty." 12283514Sarybchik * 13283514Sarybchik * Copyright (c) 2014-2015 Solarflare Communications Inc. 14283514Sarybchik * All rights reserved. 15283514Sarybchik * 16283514Sarybchik * Redistribution and use in source and binary forms, with or without 17283514Sarybchik * modification, are permitted provided that the following conditions are met: 18283514Sarybchik * 19283514Sarybchik * 1. Redistributions of source code must retain the above copyright notice, 20283514Sarybchik * this list of conditions and the following disclaimer. 21283514Sarybchik * 2. Redistributions in binary form must reproduce the above copyright notice, 22283514Sarybchik * this list of conditions and the following disclaimer in the documentation 23283514Sarybchik * and/or other materials provided with the distribution. 24283514Sarybchik * 25283514Sarybchik * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 26283514Sarybchik * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 27283514Sarybchik * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 28283514Sarybchik * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 29283514Sarybchik * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 30283514Sarybchik * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 31283514Sarybchik * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; 32283514Sarybchik * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 33283514Sarybchik * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 34283514Sarybchik * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, 35283514Sarybchik * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 36283514Sarybchik * 37283514Sarybchik * The views and conclusions contained in the software and documentation are 38283514Sarybchik * those of the authors and should not be interpreted as representing official 39283514Sarybchik * policies, either expressed or implied, of the FreeBSD Project. 40283514Sarybchik */ 41283514Sarybchik 42283514Sarybchik#include <sys/cdefs.h> 43283514Sarybchik__FBSDID("$FreeBSD: head/sys/dev/sfxge/common/efx_hash.c 283514 2015-05-25 08:34:55Z arybchik $"); 44283514Sarybchik 45283514Sarybchik#include "efsys.h" 46283514Sarybchik#include "efx.h" 47283514Sarybchik#include "efx_types.h" 48283514Sarybchik#include "efx_impl.h" 49283514Sarybchik 50283514Sarybchik/* Hash initial value */ 51283514Sarybchik#define EFX_HASH_INITIAL_VALUE 0xdeadbeef 52283514Sarybchik 53283514Sarybchik/* 54283514Sarybchik * Rotate a 32-bit value left 55283514Sarybchik * 56283514Sarybchik * Allow platform to provide an intrinsic or optimised routine and 57283514Sarybchik * fall-back to a simple shift based implementation. 58283514Sarybchik */ 59283514Sarybchik#if EFSYS_HAS_ROTL_DWORD 60283514Sarybchik 61283514Sarybchik#define EFX_HASH_ROTATE(_value, _shift) \ 62283514Sarybchik EFSYS_ROTL_DWORD(_value, _shift) 63283514Sarybchik 64283514Sarybchik#else 65283514Sarybchik 66283514Sarybchik#define EFX_HASH_ROTATE(_value, _shift) \ 67283514Sarybchik (((_value) << (_shift)) | ((_value) >> (32 - (_shift)))) 68283514Sarybchik 69283514Sarybchik#endif 70283514Sarybchik 71283514Sarybchik/* Mix three 32-bit values reversibly */ 72283514Sarybchik#define EFX_HASH_MIX(_a, _b, _c) \ 73283514Sarybchik do { \ 74283514Sarybchik _a -= _c; \ 75283514Sarybchik _a ^= EFX_HASH_ROTATE(_c, 4); \ 76283514Sarybchik _c += _b; \ 77283514Sarybchik _b -= _a; \ 78283514Sarybchik _b ^= EFX_HASH_ROTATE(_a, 6); \ 79283514Sarybchik _a += _c; \ 80283514Sarybchik _c -= _b; \ 81283514Sarybchik _c ^= EFX_HASH_ROTATE(_b, 8); \ 82283514Sarybchik _b += _a; \ 83283514Sarybchik _a -= _c; \ 84283514Sarybchik _a ^= EFX_HASH_ROTATE(_c, 16); \ 85283514Sarybchik _c += _b; \ 86283514Sarybchik _b -= _a; \ 87283514Sarybchik _b ^= EFX_HASH_ROTATE(_a, 19); \ 88283514Sarybchik _a += _c; \ 89283514Sarybchik _c -= _b; \ 90283514Sarybchik _c ^= EFX_HASH_ROTATE(_b, 4); \ 91283514Sarybchik _b += _a; \ 92283514Sarybchik _NOTE(CONSTANTCONDITION) \ 93283514Sarybchik } while (B_FALSE) 94283514Sarybchik 95283514Sarybchik/* Final mixing of three 32-bit values into one (_c) */ 96283514Sarybchik#define EFX_HASH_FINALISE(_a, _b, _c) \ 97283514Sarybchik do { \ 98283514Sarybchik _c ^= _b; \ 99283514Sarybchik _c -= EFX_HASH_ROTATE(_b, 14); \ 100283514Sarybchik _a ^= _c; \ 101283514Sarybchik _a -= EFX_HASH_ROTATE(_c, 11); \ 102283514Sarybchik _b ^= _a; \ 103283514Sarybchik _b -= EFX_HASH_ROTATE(_a, 25); \ 104283514Sarybchik _c ^= _b; \ 105283514Sarybchik _c -= EFX_HASH_ROTATE(_b, 16); \ 106283514Sarybchik _a ^= _c; \ 107283514Sarybchik _a -= EFX_HASH_ROTATE(_c, 4); \ 108283514Sarybchik _b ^= _a; \ 109283514Sarybchik _b -= EFX_HASH_ROTATE(_a, 14); \ 110283514Sarybchik _c ^= _b; \ 111283514Sarybchik _c -= EFX_HASH_ROTATE(_b, 24); \ 112283514Sarybchik _NOTE(CONSTANTCONDITION) \ 113283514Sarybchik } while (B_FALSE) 114283514Sarybchik 115283514Sarybchik 116283514Sarybchik/* Produce a 32-bit hash from 32-bit aligned input */ 117283514Sarybchik __checkReturn uint32_t 118283514Sarybchikefx_hash_dwords( 119283514Sarybchik __in_ecount(count) uint32_t const *input, 120283514Sarybchik __in size_t count, 121283514Sarybchik __in uint32_t init) 122283514Sarybchik{ 123283514Sarybchik uint32_t a; 124283514Sarybchik uint32_t b; 125283514Sarybchik uint32_t c; 126283514Sarybchik 127283514Sarybchik /* Set up the initial internal state */ 128283514Sarybchik a = b = c = EFX_HASH_INITIAL_VALUE + 129283514Sarybchik (((uint32_t)count) * sizeof (uint32_t)) + init; 130283514Sarybchik 131283514Sarybchik /* Handle all but the last three dwords of the input */ 132283514Sarybchik while (count > 3) { 133283514Sarybchik a += input[0]; 134283514Sarybchik b += input[1]; 135283514Sarybchik c += input[2]; 136283514Sarybchik EFX_HASH_MIX(a, b, c); 137283514Sarybchik 138283514Sarybchik count -= 3; 139283514Sarybchik input += 3; 140283514Sarybchik } 141283514Sarybchik 142283514Sarybchik /* Handle the left-overs */ 143283514Sarybchik switch (count) { 144283514Sarybchik case 3: 145283514Sarybchik c += input[2]; 146283514Sarybchik /* Fall-through */ 147283514Sarybchik case 2: 148283514Sarybchik b += input[1]; 149283514Sarybchik /* Fall-through */ 150283514Sarybchik case 1: 151283514Sarybchik a += input[0]; 152283514Sarybchik EFX_HASH_FINALISE(a, b, c); 153283514Sarybchik break; 154283514Sarybchik 155283514Sarybchik case 0: 156283514Sarybchik /* Should only get here if count parameter was zero */ 157283514Sarybchik break; 158283514Sarybchik } 159283514Sarybchik 160283514Sarybchik return (c); 161283514Sarybchik} 162283514Sarybchik 163283514Sarybchik#if EFSYS_IS_BIG_ENDIAN 164283514Sarybchik 165283514Sarybchik/* Produce a 32-bit hash from arbitrarily aligned input */ 166283514Sarybchik __checkReturn uint32_t 167283514Sarybchikefx_hash_bytes( 168283514Sarybchik __in_ecount(length) uint8_t const *input, 169283514Sarybchik __in size_t length, 170283514Sarybchik __in uint32_t init) 171283514Sarybchik{ 172283514Sarybchik uint32_t a; 173283514Sarybchik uint32_t b; 174283514Sarybchik uint32_t c; 175283514Sarybchik 176283514Sarybchik /* Set up the initial internal state */ 177283514Sarybchik a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init; 178283514Sarybchik 179283514Sarybchik /* Handle all but the last twelve bytes of the input */ 180283514Sarybchik while (length > 12) { 181283514Sarybchik a += ((uint32_t)input[0]) << 24; 182283514Sarybchik a += ((uint32_t)input[1]) << 16; 183283514Sarybchik a += ((uint32_t)input[2]) << 8; 184283514Sarybchik a += ((uint32_t)input[3]); 185283514Sarybchik b += ((uint32_t)input[4]) << 24; 186283514Sarybchik b += ((uint32_t)input[5]) << 16; 187283514Sarybchik b += ((uint32_t)input[6]) << 8; 188283514Sarybchik b += ((uint32_t)input[7]); 189283514Sarybchik c += ((uint32_t)input[8]) << 24; 190283514Sarybchik c += ((uint32_t)input[9]) << 16; 191283514Sarybchik c += ((uint32_t)input[10]) << 8; 192283514Sarybchik c += ((uint32_t)input[11]); 193283514Sarybchik EFX_HASH_MIX(a, b, c); 194283514Sarybchik length -= 12; 195283514Sarybchik input += 12; 196283514Sarybchik } 197283514Sarybchik 198283514Sarybchik /* Handle the left-overs */ 199283514Sarybchik switch (length) { 200283514Sarybchik case 12: 201283514Sarybchik c += ((uint32_t)input[11]); 202283514Sarybchik /* Fall-through */ 203283514Sarybchik case 11: 204283514Sarybchik c += ((uint32_t)input[10]) << 8; 205283514Sarybchik /* Fall-through */ 206283514Sarybchik case 10: 207283514Sarybchik c += ((uint32_t)input[9]) << 16; 208283514Sarybchik /* Fall-through */ 209283514Sarybchik case 9: 210283514Sarybchik c += ((uint32_t)input[8]) << 24; 211283514Sarybchik /* Fall-through */ 212283514Sarybchik case 8: 213283514Sarybchik b += ((uint32_t)input[7]); 214283514Sarybchik /* Fall-through */ 215283514Sarybchik case 7: 216283514Sarybchik b += ((uint32_t)input[6]) << 8; 217283514Sarybchik /* Fall-through */ 218283514Sarybchik case 6: 219283514Sarybchik b += ((uint32_t)input[5]) << 16; 220283514Sarybchik /* Fall-through */ 221283514Sarybchik case 5: 222283514Sarybchik b += ((uint32_t)input[4]) << 24; 223283514Sarybchik /* Fall-through */ 224283514Sarybchik case 4: 225283514Sarybchik a += ((uint32_t)input[3]); 226283514Sarybchik /* Fall-through */ 227283514Sarybchik case 3: 228283514Sarybchik a += ((uint32_t)input[2]) << 8; 229283514Sarybchik /* Fall-through */ 230283514Sarybchik case 2: 231283514Sarybchik a += ((uint32_t)input[1]) << 16; 232283514Sarybchik /* Fall-through */ 233283514Sarybchik case 1: 234283514Sarybchik a += ((uint32_t)input[0]) << 24; 235283514Sarybchik EFX_HASH_FINALISE(a, b, c); 236283514Sarybchik break; 237283514Sarybchik 238283514Sarybchik case 0: 239283514Sarybchik /* Should only get here if length parameter was zero */ 240283514Sarybchik break; 241283514Sarybchik } 242283514Sarybchik 243283514Sarybchik return (c); 244283514Sarybchik} 245283514Sarybchik 246283514Sarybchik#elif EFSYS_IS_LITTLE_ENDIAN 247283514Sarybchik 248283514Sarybchik/* Produce a 32-bit hash from arbitrarily aligned input */ 249283514Sarybchik __checkReturn uint32_t 250283514Sarybchikefx_hash_bytes( 251283514Sarybchik __in_ecount(length) uint8_t const *input, 252283514Sarybchik __in size_t length, 253283514Sarybchik __in uint32_t init) 254283514Sarybchik{ 255283514Sarybchik uint32_t a; 256283514Sarybchik uint32_t b; 257283514Sarybchik uint32_t c; 258283514Sarybchik 259283514Sarybchik /* Set up the initial internal state */ 260283514Sarybchik a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init; 261283514Sarybchik 262283514Sarybchik /* Handle all but the last twelve bytes of the input */ 263283514Sarybchik while (length > 12) { 264283514Sarybchik a += ((uint32_t)input[0]); 265283514Sarybchik a += ((uint32_t)input[1]) << 8; 266283514Sarybchik a += ((uint32_t)input[2]) << 16; 267283514Sarybchik a += ((uint32_t)input[3]) << 24; 268283514Sarybchik b += ((uint32_t)input[4]); 269283514Sarybchik b += ((uint32_t)input[5]) << 8; 270283514Sarybchik b += ((uint32_t)input[6]) << 16; 271283514Sarybchik b += ((uint32_t)input[7]) << 24; 272283514Sarybchik c += ((uint32_t)input[8]); 273283514Sarybchik c += ((uint32_t)input[9]) << 8; 274283514Sarybchik c += ((uint32_t)input[10]) << 16; 275283514Sarybchik c += ((uint32_t)input[11]) << 24; 276283514Sarybchik EFX_HASH_MIX(a, b, c); 277283514Sarybchik length -= 12; 278283514Sarybchik input += 12; 279283514Sarybchik } 280283514Sarybchik 281283514Sarybchik /* Handle the left-overs */ 282283514Sarybchik switch (length) { 283283514Sarybchik case 12: 284283514Sarybchik c += ((uint32_t)input[11]) << 24; 285283514Sarybchik /* Fall-through */ 286283514Sarybchik case 11: 287283514Sarybchik c += ((uint32_t)input[10]) << 16; 288283514Sarybchik /* Fall-through */ 289283514Sarybchik case 10: 290283514Sarybchik c += ((uint32_t)input[9]) << 8; 291283514Sarybchik /* Fall-through */ 292283514Sarybchik case 9: 293283514Sarybchik c += ((uint32_t)input[8]); 294283514Sarybchik /* Fall-through */ 295283514Sarybchik case 8: 296283514Sarybchik b += ((uint32_t)input[7]) << 24; 297283514Sarybchik /* Fall-through */ 298283514Sarybchik case 7: 299283514Sarybchik b += ((uint32_t)input[6]) << 16; 300283514Sarybchik /* Fall-through */ 301283514Sarybchik case 6: 302283514Sarybchik b += ((uint32_t)input[5]) << 8; 303283514Sarybchik /* Fall-through */ 304283514Sarybchik case 5: 305283514Sarybchik b += ((uint32_t)input[4]); 306283514Sarybchik /* Fall-through */ 307283514Sarybchik case 4: 308283514Sarybchik a += ((uint32_t)input[3]) << 24; 309283514Sarybchik /* Fall-through */ 310283514Sarybchik case 3: 311283514Sarybchik a += ((uint32_t)input[2]) << 16; 312283514Sarybchik /* Fall-through */ 313283514Sarybchik case 2: 314283514Sarybchik a += ((uint32_t)input[1]) << 8; 315283514Sarybchik /* Fall-through */ 316283514Sarybchik case 1: 317283514Sarybchik a += ((uint32_t)input[0]); 318283514Sarybchik EFX_HASH_FINALISE(a, b, c); 319283514Sarybchik break; 320283514Sarybchik 321283514Sarybchik case 0: 322283514Sarybchik /* Should only get here if length parameter was zero */ 323283514Sarybchik break; 324283514Sarybchik } 325283514Sarybchik 326283514Sarybchik return (c); 327283514Sarybchik} 328283514Sarybchik 329283514Sarybchik#else 330283514Sarybchik 331283514Sarybchik#error "Neither of EFSYS_IS_{BIG,LITTLE}_ENDIAN is set" 332283514Sarybchik 333283514Sarybchik#endif 334