efx_hash.c revision 300607
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 * 13300607Sarybchik * Copyright (c) 2014-2016 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 300607 2016-05-24 12:16:57Z arybchik $"); 44283514Sarybchik 45283514Sarybchik#include "efx.h" 46283514Sarybchik#include "efx_impl.h" 47283514Sarybchik 48283514Sarybchik/* Hash initial value */ 49283514Sarybchik#define EFX_HASH_INITIAL_VALUE 0xdeadbeef 50283514Sarybchik 51283514Sarybchik/* 52283514Sarybchik * Rotate a 32-bit value left 53283514Sarybchik * 54283514Sarybchik * Allow platform to provide an intrinsic or optimised routine and 55283514Sarybchik * fall-back to a simple shift based implementation. 56283514Sarybchik */ 57283514Sarybchik#if EFSYS_HAS_ROTL_DWORD 58283514Sarybchik 59283514Sarybchik#define EFX_HASH_ROTATE(_value, _shift) \ 60283514Sarybchik EFSYS_ROTL_DWORD(_value, _shift) 61283514Sarybchik 62283514Sarybchik#else 63283514Sarybchik 64283514Sarybchik#define EFX_HASH_ROTATE(_value, _shift) \ 65283514Sarybchik (((_value) << (_shift)) | ((_value) >> (32 - (_shift)))) 66283514Sarybchik 67283514Sarybchik#endif 68283514Sarybchik 69283514Sarybchik/* Mix three 32-bit values reversibly */ 70283514Sarybchik#define EFX_HASH_MIX(_a, _b, _c) \ 71283514Sarybchik do { \ 72283514Sarybchik _a -= _c; \ 73283514Sarybchik _a ^= EFX_HASH_ROTATE(_c, 4); \ 74283514Sarybchik _c += _b; \ 75283514Sarybchik _b -= _a; \ 76283514Sarybchik _b ^= EFX_HASH_ROTATE(_a, 6); \ 77283514Sarybchik _a += _c; \ 78283514Sarybchik _c -= _b; \ 79283514Sarybchik _c ^= EFX_HASH_ROTATE(_b, 8); \ 80283514Sarybchik _b += _a; \ 81283514Sarybchik _a -= _c; \ 82283514Sarybchik _a ^= EFX_HASH_ROTATE(_c, 16); \ 83283514Sarybchik _c += _b; \ 84283514Sarybchik _b -= _a; \ 85283514Sarybchik _b ^= EFX_HASH_ROTATE(_a, 19); \ 86283514Sarybchik _a += _c; \ 87283514Sarybchik _c -= _b; \ 88283514Sarybchik _c ^= EFX_HASH_ROTATE(_b, 4); \ 89283514Sarybchik _b += _a; \ 90283514Sarybchik _NOTE(CONSTANTCONDITION) \ 91283514Sarybchik } while (B_FALSE) 92283514Sarybchik 93283514Sarybchik/* Final mixing of three 32-bit values into one (_c) */ 94283514Sarybchik#define EFX_HASH_FINALISE(_a, _b, _c) \ 95283514Sarybchik do { \ 96283514Sarybchik _c ^= _b; \ 97283514Sarybchik _c -= EFX_HASH_ROTATE(_b, 14); \ 98283514Sarybchik _a ^= _c; \ 99283514Sarybchik _a -= EFX_HASH_ROTATE(_c, 11); \ 100283514Sarybchik _b ^= _a; \ 101283514Sarybchik _b -= EFX_HASH_ROTATE(_a, 25); \ 102283514Sarybchik _c ^= _b; \ 103283514Sarybchik _c -= EFX_HASH_ROTATE(_b, 16); \ 104283514Sarybchik _a ^= _c; \ 105283514Sarybchik _a -= EFX_HASH_ROTATE(_c, 4); \ 106283514Sarybchik _b ^= _a; \ 107283514Sarybchik _b -= EFX_HASH_ROTATE(_a, 14); \ 108283514Sarybchik _c ^= _b; \ 109283514Sarybchik _c -= EFX_HASH_ROTATE(_b, 24); \ 110283514Sarybchik _NOTE(CONSTANTCONDITION) \ 111283514Sarybchik } while (B_FALSE) 112283514Sarybchik 113283514Sarybchik 114283514Sarybchik/* Produce a 32-bit hash from 32-bit aligned input */ 115283514Sarybchik __checkReturn uint32_t 116283514Sarybchikefx_hash_dwords( 117283514Sarybchik __in_ecount(count) uint32_t const *input, 118283514Sarybchik __in size_t count, 119283514Sarybchik __in uint32_t init) 120283514Sarybchik{ 121283514Sarybchik uint32_t a; 122283514Sarybchik uint32_t b; 123283514Sarybchik uint32_t c; 124283514Sarybchik 125283514Sarybchik /* Set up the initial internal state */ 126283514Sarybchik a = b = c = EFX_HASH_INITIAL_VALUE + 127283514Sarybchik (((uint32_t)count) * sizeof (uint32_t)) + init; 128283514Sarybchik 129283514Sarybchik /* Handle all but the last three dwords of the input */ 130283514Sarybchik while (count > 3) { 131283514Sarybchik a += input[0]; 132283514Sarybchik b += input[1]; 133283514Sarybchik c += input[2]; 134283514Sarybchik EFX_HASH_MIX(a, b, c); 135283514Sarybchik 136283514Sarybchik count -= 3; 137283514Sarybchik input += 3; 138283514Sarybchik } 139283514Sarybchik 140283514Sarybchik /* Handle the left-overs */ 141283514Sarybchik switch (count) { 142283514Sarybchik case 3: 143283514Sarybchik c += input[2]; 144283514Sarybchik /* Fall-through */ 145283514Sarybchik case 2: 146283514Sarybchik b += input[1]; 147283514Sarybchik /* Fall-through */ 148283514Sarybchik case 1: 149283514Sarybchik a += input[0]; 150283514Sarybchik EFX_HASH_FINALISE(a, b, c); 151283514Sarybchik break; 152283514Sarybchik 153283514Sarybchik case 0: 154283514Sarybchik /* Should only get here if count parameter was zero */ 155283514Sarybchik break; 156283514Sarybchik } 157283514Sarybchik 158283514Sarybchik return (c); 159283514Sarybchik} 160283514Sarybchik 161283514Sarybchik#if EFSYS_IS_BIG_ENDIAN 162283514Sarybchik 163283514Sarybchik/* Produce a 32-bit hash from arbitrarily aligned input */ 164283514Sarybchik __checkReturn uint32_t 165283514Sarybchikefx_hash_bytes( 166283514Sarybchik __in_ecount(length) uint8_t const *input, 167283514Sarybchik __in size_t length, 168283514Sarybchik __in uint32_t init) 169283514Sarybchik{ 170283514Sarybchik uint32_t a; 171283514Sarybchik uint32_t b; 172283514Sarybchik uint32_t c; 173283514Sarybchik 174283514Sarybchik /* Set up the initial internal state */ 175283514Sarybchik a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init; 176283514Sarybchik 177283514Sarybchik /* Handle all but the last twelve bytes of the input */ 178283514Sarybchik while (length > 12) { 179283514Sarybchik a += ((uint32_t)input[0]) << 24; 180283514Sarybchik a += ((uint32_t)input[1]) << 16; 181283514Sarybchik a += ((uint32_t)input[2]) << 8; 182283514Sarybchik a += ((uint32_t)input[3]); 183283514Sarybchik b += ((uint32_t)input[4]) << 24; 184283514Sarybchik b += ((uint32_t)input[5]) << 16; 185283514Sarybchik b += ((uint32_t)input[6]) << 8; 186283514Sarybchik b += ((uint32_t)input[7]); 187283514Sarybchik c += ((uint32_t)input[8]) << 24; 188283514Sarybchik c += ((uint32_t)input[9]) << 16; 189283514Sarybchik c += ((uint32_t)input[10]) << 8; 190283514Sarybchik c += ((uint32_t)input[11]); 191283514Sarybchik EFX_HASH_MIX(a, b, c); 192283514Sarybchik length -= 12; 193283514Sarybchik input += 12; 194283514Sarybchik } 195283514Sarybchik 196283514Sarybchik /* Handle the left-overs */ 197283514Sarybchik switch (length) { 198283514Sarybchik case 12: 199283514Sarybchik c += ((uint32_t)input[11]); 200283514Sarybchik /* Fall-through */ 201283514Sarybchik case 11: 202283514Sarybchik c += ((uint32_t)input[10]) << 8; 203283514Sarybchik /* Fall-through */ 204283514Sarybchik case 10: 205283514Sarybchik c += ((uint32_t)input[9]) << 16; 206283514Sarybchik /* Fall-through */ 207283514Sarybchik case 9: 208283514Sarybchik c += ((uint32_t)input[8]) << 24; 209283514Sarybchik /* Fall-through */ 210283514Sarybchik case 8: 211283514Sarybchik b += ((uint32_t)input[7]); 212283514Sarybchik /* Fall-through */ 213283514Sarybchik case 7: 214283514Sarybchik b += ((uint32_t)input[6]) << 8; 215283514Sarybchik /* Fall-through */ 216283514Sarybchik case 6: 217283514Sarybchik b += ((uint32_t)input[5]) << 16; 218283514Sarybchik /* Fall-through */ 219283514Sarybchik case 5: 220283514Sarybchik b += ((uint32_t)input[4]) << 24; 221283514Sarybchik /* Fall-through */ 222283514Sarybchik case 4: 223283514Sarybchik a += ((uint32_t)input[3]); 224283514Sarybchik /* Fall-through */ 225283514Sarybchik case 3: 226283514Sarybchik a += ((uint32_t)input[2]) << 8; 227283514Sarybchik /* Fall-through */ 228283514Sarybchik case 2: 229283514Sarybchik a += ((uint32_t)input[1]) << 16; 230283514Sarybchik /* Fall-through */ 231283514Sarybchik case 1: 232283514Sarybchik a += ((uint32_t)input[0]) << 24; 233283514Sarybchik EFX_HASH_FINALISE(a, b, c); 234283514Sarybchik break; 235283514Sarybchik 236283514Sarybchik case 0: 237283514Sarybchik /* Should only get here if length parameter was zero */ 238283514Sarybchik break; 239283514Sarybchik } 240283514Sarybchik 241283514Sarybchik return (c); 242283514Sarybchik} 243283514Sarybchik 244283514Sarybchik#elif EFSYS_IS_LITTLE_ENDIAN 245283514Sarybchik 246283514Sarybchik/* Produce a 32-bit hash from arbitrarily aligned input */ 247283514Sarybchik __checkReturn uint32_t 248283514Sarybchikefx_hash_bytes( 249283514Sarybchik __in_ecount(length) uint8_t const *input, 250283514Sarybchik __in size_t length, 251283514Sarybchik __in uint32_t init) 252283514Sarybchik{ 253283514Sarybchik uint32_t a; 254283514Sarybchik uint32_t b; 255283514Sarybchik uint32_t c; 256283514Sarybchik 257283514Sarybchik /* Set up the initial internal state */ 258283514Sarybchik a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init; 259283514Sarybchik 260283514Sarybchik /* Handle all but the last twelve bytes of the input */ 261283514Sarybchik while (length > 12) { 262283514Sarybchik a += ((uint32_t)input[0]); 263283514Sarybchik a += ((uint32_t)input[1]) << 8; 264283514Sarybchik a += ((uint32_t)input[2]) << 16; 265283514Sarybchik a += ((uint32_t)input[3]) << 24; 266283514Sarybchik b += ((uint32_t)input[4]); 267283514Sarybchik b += ((uint32_t)input[5]) << 8; 268283514Sarybchik b += ((uint32_t)input[6]) << 16; 269283514Sarybchik b += ((uint32_t)input[7]) << 24; 270283514Sarybchik c += ((uint32_t)input[8]); 271283514Sarybchik c += ((uint32_t)input[9]) << 8; 272283514Sarybchik c += ((uint32_t)input[10]) << 16; 273283514Sarybchik c += ((uint32_t)input[11]) << 24; 274283514Sarybchik EFX_HASH_MIX(a, b, c); 275283514Sarybchik length -= 12; 276283514Sarybchik input += 12; 277283514Sarybchik } 278283514Sarybchik 279283514Sarybchik /* Handle the left-overs */ 280283514Sarybchik switch (length) { 281283514Sarybchik case 12: 282283514Sarybchik c += ((uint32_t)input[11]) << 24; 283283514Sarybchik /* Fall-through */ 284283514Sarybchik case 11: 285283514Sarybchik c += ((uint32_t)input[10]) << 16; 286283514Sarybchik /* Fall-through */ 287283514Sarybchik case 10: 288283514Sarybchik c += ((uint32_t)input[9]) << 8; 289283514Sarybchik /* Fall-through */ 290283514Sarybchik case 9: 291283514Sarybchik c += ((uint32_t)input[8]); 292283514Sarybchik /* Fall-through */ 293283514Sarybchik case 8: 294283514Sarybchik b += ((uint32_t)input[7]) << 24; 295283514Sarybchik /* Fall-through */ 296283514Sarybchik case 7: 297283514Sarybchik b += ((uint32_t)input[6]) << 16; 298283514Sarybchik /* Fall-through */ 299283514Sarybchik case 6: 300283514Sarybchik b += ((uint32_t)input[5]) << 8; 301283514Sarybchik /* Fall-through */ 302283514Sarybchik case 5: 303283514Sarybchik b += ((uint32_t)input[4]); 304283514Sarybchik /* Fall-through */ 305283514Sarybchik case 4: 306283514Sarybchik a += ((uint32_t)input[3]) << 24; 307283514Sarybchik /* Fall-through */ 308283514Sarybchik case 3: 309283514Sarybchik a += ((uint32_t)input[2]) << 16; 310283514Sarybchik /* Fall-through */ 311283514Sarybchik case 2: 312283514Sarybchik a += ((uint32_t)input[1]) << 8; 313283514Sarybchik /* Fall-through */ 314283514Sarybchik case 1: 315283514Sarybchik a += ((uint32_t)input[0]); 316283514Sarybchik EFX_HASH_FINALISE(a, b, c); 317283514Sarybchik break; 318283514Sarybchik 319283514Sarybchik case 0: 320283514Sarybchik /* Should only get here if length parameter was zero */ 321283514Sarybchik break; 322283514Sarybchik } 323283514Sarybchik 324283514Sarybchik return (c); 325283514Sarybchik} 326283514Sarybchik 327283514Sarybchik#else 328283514Sarybchik 329283514Sarybchik#error "Neither of EFSYS_IS_{BIG,LITTLE}_ENDIAN is set" 330283514Sarybchik 331283514Sarybchik#endif 332