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-2016 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#include "efx.h" 44#include "efx_impl.h" 45 46/* Hash initial value */ 47#define EFX_HASH_INITIAL_VALUE 0xdeadbeef 48 49/* 50 * Rotate a 32-bit value left 51 * 52 * Allow platform to provide an intrinsic or optimised routine and 53 * fall-back to a simple shift based implementation. 54 */ 55#if EFSYS_HAS_ROTL_DWORD 56 57#define EFX_HASH_ROTATE(_value, _shift) \ 58 EFSYS_ROTL_DWORD(_value, _shift) 59 60#else 61 62#define EFX_HASH_ROTATE(_value, _shift) \ 63 (((_value) << (_shift)) | ((_value) >> (32 - (_shift)))) 64 65#endif 66 67/* Mix three 32-bit values reversibly */ 68#define EFX_HASH_MIX(_a, _b, _c) \ 69 do { \ 70 _a -= _c; \ 71 _a ^= EFX_HASH_ROTATE(_c, 4); \ 72 _c += _b; \ 73 _b -= _a; \ 74 _b ^= EFX_HASH_ROTATE(_a, 6); \ 75 _a += _c; \ 76 _c -= _b; \ 77 _c ^= EFX_HASH_ROTATE(_b, 8); \ 78 _b += _a; \ 79 _a -= _c; \ 80 _a ^= EFX_HASH_ROTATE(_c, 16); \ 81 _c += _b; \ 82 _b -= _a; \ 83 _b ^= EFX_HASH_ROTATE(_a, 19); \ 84 _a += _c; \ 85 _c -= _b; \ 86 _c ^= EFX_HASH_ROTATE(_b, 4); \ 87 _b += _a; \ 88 _NOTE(CONSTANTCONDITION) \ 89 } while (B_FALSE) 90 91/* Final mixing of three 32-bit values into one (_c) */ 92#define EFX_HASH_FINALISE(_a, _b, _c) \ 93 do { \ 94 _c ^= _b; \ 95 _c -= EFX_HASH_ROTATE(_b, 14); \ 96 _a ^= _c; \ 97 _a -= EFX_HASH_ROTATE(_c, 11); \ 98 _b ^= _a; \ 99 _b -= EFX_HASH_ROTATE(_a, 25); \ 100 _c ^= _b; \ 101 _c -= EFX_HASH_ROTATE(_b, 16); \ 102 _a ^= _c; \ 103 _a -= EFX_HASH_ROTATE(_c, 4); \ 104 _b ^= _a; \ 105 _b -= EFX_HASH_ROTATE(_a, 14); \ 106 _c ^= _b; \ 107 _c -= EFX_HASH_ROTATE(_b, 24); \ 108 _NOTE(CONSTANTCONDITION) \ 109 } while (B_FALSE) 110 111/* Produce a 32-bit hash from 32-bit aligned input */ 112 __checkReturn uint32_t 113efx_hash_dwords( 114 __in_ecount(count) uint32_t const *input, 115 __in size_t count, 116 __in uint32_t init) 117{ 118 uint32_t a; 119 uint32_t b; 120 uint32_t c; 121 122 /* Set up the initial internal state */ 123 a = b = c = EFX_HASH_INITIAL_VALUE + 124 (((uint32_t)count) * sizeof (uint32_t)) + init; 125 126 /* Handle all but the last three dwords of the input */ 127 while (count > 3) { 128 a += input[0]; 129 b += input[1]; 130 c += input[2]; 131 EFX_HASH_MIX(a, b, c); 132 133 count -= 3; 134 input += 3; 135 } 136 137 /* Handle the left-overs */ 138 switch (count) { 139 case 3: 140 c += input[2]; 141 /* Fall-through */ 142 case 2: 143 b += input[1]; 144 /* Fall-through */ 145 case 1: 146 a += input[0]; 147 EFX_HASH_FINALISE(a, b, c); 148 break; 149 150 case 0: 151 /* Should only get here if count parameter was zero */ 152 break; 153 } 154 155 return (c); 156} 157 158#if EFSYS_IS_BIG_ENDIAN 159 160/* Produce a 32-bit hash from arbitrarily aligned input */ 161 __checkReturn uint32_t 162efx_hash_bytes( 163 __in_ecount(length) uint8_t const *input, 164 __in size_t length, 165 __in uint32_t init) 166{ 167 uint32_t a; 168 uint32_t b; 169 uint32_t c; 170 171 /* Set up the initial internal state */ 172 a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init; 173 174 /* Handle all but the last twelve bytes of the input */ 175 while (length > 12) { 176 a += ((uint32_t)input[0]) << 24; 177 a += ((uint32_t)input[1]) << 16; 178 a += ((uint32_t)input[2]) << 8; 179 a += ((uint32_t)input[3]); 180 b += ((uint32_t)input[4]) << 24; 181 b += ((uint32_t)input[5]) << 16; 182 b += ((uint32_t)input[6]) << 8; 183 b += ((uint32_t)input[7]); 184 c += ((uint32_t)input[8]) << 24; 185 c += ((uint32_t)input[9]) << 16; 186 c += ((uint32_t)input[10]) << 8; 187 c += ((uint32_t)input[11]); 188 EFX_HASH_MIX(a, b, c); 189 length -= 12; 190 input += 12; 191 } 192 193 /* Handle the left-overs */ 194 switch (length) { 195 case 12: 196 c += ((uint32_t)input[11]); 197 /* Fall-through */ 198 case 11: 199 c += ((uint32_t)input[10]) << 8; 200 /* Fall-through */ 201 case 10: 202 c += ((uint32_t)input[9]) << 16; 203 /* Fall-through */ 204 case 9: 205 c += ((uint32_t)input[8]) << 24; 206 /* Fall-through */ 207 case 8: 208 b += ((uint32_t)input[7]); 209 /* Fall-through */ 210 case 7: 211 b += ((uint32_t)input[6]) << 8; 212 /* Fall-through */ 213 case 6: 214 b += ((uint32_t)input[5]) << 16; 215 /* Fall-through */ 216 case 5: 217 b += ((uint32_t)input[4]) << 24; 218 /* Fall-through */ 219 case 4: 220 a += ((uint32_t)input[3]); 221 /* Fall-through */ 222 case 3: 223 a += ((uint32_t)input[2]) << 8; 224 /* Fall-through */ 225 case 2: 226 a += ((uint32_t)input[1]) << 16; 227 /* Fall-through */ 228 case 1: 229 a += ((uint32_t)input[0]) << 24; 230 EFX_HASH_FINALISE(a, b, c); 231 break; 232 233 case 0: 234 /* Should only get here if length parameter was zero */ 235 break; 236 } 237 238 return (c); 239} 240 241#elif EFSYS_IS_LITTLE_ENDIAN 242 243/* Produce a 32-bit hash from arbitrarily aligned input */ 244 __checkReturn uint32_t 245efx_hash_bytes( 246 __in_ecount(length) uint8_t const *input, 247 __in size_t length, 248 __in uint32_t init) 249{ 250 uint32_t a; 251 uint32_t b; 252 uint32_t c; 253 254 /* Set up the initial internal state */ 255 a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init; 256 257 /* Handle all but the last twelve bytes of the input */ 258 while (length > 12) { 259 a += ((uint32_t)input[0]); 260 a += ((uint32_t)input[1]) << 8; 261 a += ((uint32_t)input[2]) << 16; 262 a += ((uint32_t)input[3]) << 24; 263 b += ((uint32_t)input[4]); 264 b += ((uint32_t)input[5]) << 8; 265 b += ((uint32_t)input[6]) << 16; 266 b += ((uint32_t)input[7]) << 24; 267 c += ((uint32_t)input[8]); 268 c += ((uint32_t)input[9]) << 8; 269 c += ((uint32_t)input[10]) << 16; 270 c += ((uint32_t)input[11]) << 24; 271 EFX_HASH_MIX(a, b, c); 272 length -= 12; 273 input += 12; 274 } 275 276 /* Handle the left-overs */ 277 switch (length) { 278 case 12: 279 c += ((uint32_t)input[11]) << 24; 280 /* Fall-through */ 281 case 11: 282 c += ((uint32_t)input[10]) << 16; 283 /* Fall-through */ 284 case 10: 285 c += ((uint32_t)input[9]) << 8; 286 /* Fall-through */ 287 case 9: 288 c += ((uint32_t)input[8]); 289 /* Fall-through */ 290 case 8: 291 b += ((uint32_t)input[7]) << 24; 292 /* Fall-through */ 293 case 7: 294 b += ((uint32_t)input[6]) << 16; 295 /* Fall-through */ 296 case 6: 297 b += ((uint32_t)input[5]) << 8; 298 /* Fall-through */ 299 case 5: 300 b += ((uint32_t)input[4]); 301 /* Fall-through */ 302 case 4: 303 a += ((uint32_t)input[3]) << 24; 304 /* Fall-through */ 305 case 3: 306 a += ((uint32_t)input[2]) << 16; 307 /* Fall-through */ 308 case 2: 309 a += ((uint32_t)input[1]) << 8; 310 /* Fall-through */ 311 case 1: 312 a += ((uint32_t)input[0]); 313 EFX_HASH_FINALISE(a, b, c); 314 break; 315 316 case 0: 317 /* Should only get here if length parameter was zero */ 318 break; 319 } 320 321 return (c); 322} 323 324#else 325 326#error "Neither of EFSYS_IS_{BIG,LITTLE}_ENDIAN is set" 327 328#endif 329