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