efx_hash.c revision 284555
1/*- 2 * Copyright 2006 Bob Jenkins 3 * 4 * Derived from public domain source, see 5 * <http://burtleburtle.net/bob/c/lookup3.c>: 6 * 7 * "lookup3.c, by Bob Jenkins, May 2006, Public Domain. 8 * 9 * These are functions for producing 32-bit hashes for hash table lookup... 10 * ...You can use this free for any purpose. It's in the public domain. 11 * It has no warranty." 12 * 13 * Copyright (c) 2014-2015 Solarflare Communications Inc. 14 * All rights reserved. 15 * 16 * Redistribution and use in source and binary forms, with or without 17 * modification, are permitted provided that the following conditions are met: 18 * 19 * 1. Redistributions of source code must retain the above copyright notice, 20 * this list of conditions and the following disclaimer. 21 * 2. Redistributions in binary form must reproduce the above copyright notice, 22 * this list of conditions and the following disclaimer in the documentation 23 * and/or other materials provided with the distribution. 24 * 25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 26 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, 27 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 28 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 29 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 30 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 31 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; 32 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 33 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 34 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, 35 * EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 36 * 37 * The views and conclusions contained in the software and documentation are 38 * those of the authors and should not be interpreted as representing official 39 * policies, either expressed or implied, of the FreeBSD Project. 40 */ 41 42#include <sys/cdefs.h> 43__FBSDID("$FreeBSD: stable/10/sys/dev/sfxge/common/efx_hash.c 284555 2015-06-18 15:46:39Z arybchik $"); 44 45#include "efsys.h" 46#include "efx.h" 47#include "efx_types.h" 48#include "efx_impl.h" 49 50/* Hash initial value */ 51#define EFX_HASH_INITIAL_VALUE 0xdeadbeef 52 53/* 54 * Rotate a 32-bit value left 55 * 56 * Allow platform to provide an intrinsic or optimised routine and 57 * fall-back to a simple shift based implementation. 58 */ 59#if EFSYS_HAS_ROTL_DWORD 60 61#define EFX_HASH_ROTATE(_value, _shift) \ 62 EFSYS_ROTL_DWORD(_value, _shift) 63 64#else 65 66#define EFX_HASH_ROTATE(_value, _shift) \ 67 (((_value) << (_shift)) | ((_value) >> (32 - (_shift)))) 68 69#endif 70 71/* Mix three 32-bit values reversibly */ 72#define EFX_HASH_MIX(_a, _b, _c) \ 73 do { \ 74 _a -= _c; \ 75 _a ^= EFX_HASH_ROTATE(_c, 4); \ 76 _c += _b; \ 77 _b -= _a; \ 78 _b ^= EFX_HASH_ROTATE(_a, 6); \ 79 _a += _c; \ 80 _c -= _b; \ 81 _c ^= EFX_HASH_ROTATE(_b, 8); \ 82 _b += _a; \ 83 _a -= _c; \ 84 _a ^= EFX_HASH_ROTATE(_c, 16); \ 85 _c += _b; \ 86 _b -= _a; \ 87 _b ^= EFX_HASH_ROTATE(_a, 19); \ 88 _a += _c; \ 89 _c -= _b; \ 90 _c ^= EFX_HASH_ROTATE(_b, 4); \ 91 _b += _a; \ 92 _NOTE(CONSTANTCONDITION) \ 93 } while (B_FALSE) 94 95/* Final mixing of three 32-bit values into one (_c) */ 96#define EFX_HASH_FINALISE(_a, _b, _c) \ 97 do { \ 98 _c ^= _b; \ 99 _c -= EFX_HASH_ROTATE(_b, 14); \ 100 _a ^= _c; \ 101 _a -= EFX_HASH_ROTATE(_c, 11); \ 102 _b ^= _a; \ 103 _b -= EFX_HASH_ROTATE(_a, 25); \ 104 _c ^= _b; \ 105 _c -= EFX_HASH_ROTATE(_b, 16); \ 106 _a ^= _c; \ 107 _a -= EFX_HASH_ROTATE(_c, 4); \ 108 _b ^= _a; \ 109 _b -= EFX_HASH_ROTATE(_a, 14); \ 110 _c ^= _b; \ 111 _c -= EFX_HASH_ROTATE(_b, 24); \ 112 _NOTE(CONSTANTCONDITION) \ 113 } while (B_FALSE) 114 115 116/* Produce a 32-bit hash from 32-bit aligned input */ 117 __checkReturn uint32_t 118efx_hash_dwords( 119 __in_ecount(count) uint32_t const *input, 120 __in size_t count, 121 __in uint32_t init) 122{ 123 uint32_t a; 124 uint32_t b; 125 uint32_t c; 126 127 /* Set up the initial internal state */ 128 a = b = c = EFX_HASH_INITIAL_VALUE + 129 (((uint32_t)count) * sizeof (uint32_t)) + init; 130 131 /* Handle all but the last three dwords of the input */ 132 while (count > 3) { 133 a += input[0]; 134 b += input[1]; 135 c += input[2]; 136 EFX_HASH_MIX(a, b, c); 137 138 count -= 3; 139 input += 3; 140 } 141 142 /* Handle the left-overs */ 143 switch (count) { 144 case 3: 145 c += input[2]; 146 /* Fall-through */ 147 case 2: 148 b += input[1]; 149 /* Fall-through */ 150 case 1: 151 a += input[0]; 152 EFX_HASH_FINALISE(a, b, c); 153 break; 154 155 case 0: 156 /* Should only get here if count parameter was zero */ 157 break; 158 } 159 160 return (c); 161} 162 163#if EFSYS_IS_BIG_ENDIAN 164 165/* Produce a 32-bit hash from arbitrarily aligned input */ 166 __checkReturn uint32_t 167efx_hash_bytes( 168 __in_ecount(length) uint8_t const *input, 169 __in size_t length, 170 __in uint32_t init) 171{ 172 uint32_t a; 173 uint32_t b; 174 uint32_t c; 175 176 /* Set up the initial internal state */ 177 a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init; 178 179 /* Handle all but the last twelve bytes of the input */ 180 while (length > 12) { 181 a += ((uint32_t)input[0]) << 24; 182 a += ((uint32_t)input[1]) << 16; 183 a += ((uint32_t)input[2]) << 8; 184 a += ((uint32_t)input[3]); 185 b += ((uint32_t)input[4]) << 24; 186 b += ((uint32_t)input[5]) << 16; 187 b += ((uint32_t)input[6]) << 8; 188 b += ((uint32_t)input[7]); 189 c += ((uint32_t)input[8]) << 24; 190 c += ((uint32_t)input[9]) << 16; 191 c += ((uint32_t)input[10]) << 8; 192 c += ((uint32_t)input[11]); 193 EFX_HASH_MIX(a, b, c); 194 length -= 12; 195 input += 12; 196 } 197 198 /* Handle the left-overs */ 199 switch (length) { 200 case 12: 201 c += ((uint32_t)input[11]); 202 /* Fall-through */ 203 case 11: 204 c += ((uint32_t)input[10]) << 8; 205 /* Fall-through */ 206 case 10: 207 c += ((uint32_t)input[9]) << 16; 208 /* Fall-through */ 209 case 9: 210 c += ((uint32_t)input[8]) << 24; 211 /* Fall-through */ 212 case 8: 213 b += ((uint32_t)input[7]); 214 /* Fall-through */ 215 case 7: 216 b += ((uint32_t)input[6]) << 8; 217 /* Fall-through */ 218 case 6: 219 b += ((uint32_t)input[5]) << 16; 220 /* Fall-through */ 221 case 5: 222 b += ((uint32_t)input[4]) << 24; 223 /* Fall-through */ 224 case 4: 225 a += ((uint32_t)input[3]); 226 /* Fall-through */ 227 case 3: 228 a += ((uint32_t)input[2]) << 8; 229 /* Fall-through */ 230 case 2: 231 a += ((uint32_t)input[1]) << 16; 232 /* Fall-through */ 233 case 1: 234 a += ((uint32_t)input[0]) << 24; 235 EFX_HASH_FINALISE(a, b, c); 236 break; 237 238 case 0: 239 /* Should only get here if length parameter was zero */ 240 break; 241 } 242 243 return (c); 244} 245 246#elif EFSYS_IS_LITTLE_ENDIAN 247 248/* Produce a 32-bit hash from arbitrarily aligned input */ 249 __checkReturn uint32_t 250efx_hash_bytes( 251 __in_ecount(length) uint8_t const *input, 252 __in size_t length, 253 __in uint32_t init) 254{ 255 uint32_t a; 256 uint32_t b; 257 uint32_t c; 258 259 /* Set up the initial internal state */ 260 a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init; 261 262 /* Handle all but the last twelve bytes of the input */ 263 while (length > 12) { 264 a += ((uint32_t)input[0]); 265 a += ((uint32_t)input[1]) << 8; 266 a += ((uint32_t)input[2]) << 16; 267 a += ((uint32_t)input[3]) << 24; 268 b += ((uint32_t)input[4]); 269 b += ((uint32_t)input[5]) << 8; 270 b += ((uint32_t)input[6]) << 16; 271 b += ((uint32_t)input[7]) << 24; 272 c += ((uint32_t)input[8]); 273 c += ((uint32_t)input[9]) << 8; 274 c += ((uint32_t)input[10]) << 16; 275 c += ((uint32_t)input[11]) << 24; 276 EFX_HASH_MIX(a, b, c); 277 length -= 12; 278 input += 12; 279 } 280 281 /* Handle the left-overs */ 282 switch (length) { 283 case 12: 284 c += ((uint32_t)input[11]) << 24; 285 /* Fall-through */ 286 case 11: 287 c += ((uint32_t)input[10]) << 16; 288 /* Fall-through */ 289 case 10: 290 c += ((uint32_t)input[9]) << 8; 291 /* Fall-through */ 292 case 9: 293 c += ((uint32_t)input[8]); 294 /* Fall-through */ 295 case 8: 296 b += ((uint32_t)input[7]) << 24; 297 /* Fall-through */ 298 case 7: 299 b += ((uint32_t)input[6]) << 16; 300 /* Fall-through */ 301 case 6: 302 b += ((uint32_t)input[5]) << 8; 303 /* Fall-through */ 304 case 5: 305 b += ((uint32_t)input[4]); 306 /* Fall-through */ 307 case 4: 308 a += ((uint32_t)input[3]) << 24; 309 /* Fall-through */ 310 case 3: 311 a += ((uint32_t)input[2]) << 16; 312 /* Fall-through */ 313 case 2: 314 a += ((uint32_t)input[1]) << 8; 315 /* Fall-through */ 316 case 1: 317 a += ((uint32_t)input[0]); 318 EFX_HASH_FINALISE(a, b, c); 319 break; 320 321 case 0: 322 /* Should only get here if length parameter was zero */ 323 break; 324 } 325 326 return (c); 327} 328 329#else 330 331#error "Neither of EFSYS_IS_{BIG,LITTLE}_ENDIAN is set" 332 333#endif 334