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 114 /* Produce a 32-bit hash from 32-bit aligned input */ 115 __checkReturn uint32_t 116 efx_hash_dwords( 117 __in_ecount(count) uint32_t const *input, 118 __in size_t count, 119 __in uint32_t init) 120 { 121 uint32_t a; 122 uint32_t b; 123 uint32_t c; 124 125 /* Set up the initial internal state */ 126 a = b = c = EFX_HASH_INITIAL_VALUE + 127 (((uint32_t)count) * sizeof (uint32_t)) + init; 128 129 /* Handle all but the last three dwords of the input */ 130 while (count > 3) { 131 a += input[0]; 132 b += input[1]; 133 c += input[2]; 134 EFX_HASH_MIX(a, b, c); 135 136 count -= 3; 137 input += 3; 138 } 139 140 /* Handle the left-overs */ 141 switch (count) { 142 case 3: 143 c += input[2]; 144 /* Fall-through */ 145 case 2: 146 b += input[1]; 147 /* Fall-through */ 148 case 1: 149 a += input[0]; 150 EFX_HASH_FINALISE(a, b, c); 151 break; 152 153 case 0: 154 /* Should only get here if count parameter was zero */ 155 break; 156 } 157 158 return (c); 159 } 160 161 #if EFSYS_IS_BIG_ENDIAN 162 163 /* Produce a 32-bit hash from arbitrarily aligned input */ 164 __checkReturn uint32_t 165 efx_hash_bytes( 166 __in_ecount(length) uint8_t const *input, 167 __in size_t length, 168 __in uint32_t init) 169 { 170 uint32_t a; 171 uint32_t b; 172 uint32_t c; 173 174 /* Set up the initial internal state */ 175 a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init; 176 177 /* Handle all but the last twelve bytes of the input */ 178 while (length > 12) { 179 a += ((uint32_t)input[0]) << 24; 180 a += ((uint32_t)input[1]) << 16; 181 a += ((uint32_t)input[2]) << 8; 182 a += ((uint32_t)input[3]); 183 b += ((uint32_t)input[4]) << 24; 184 b += ((uint32_t)input[5]) << 16; 185 b += ((uint32_t)input[6]) << 8; 186 b += ((uint32_t)input[7]); 187 c += ((uint32_t)input[8]) << 24; 188 c += ((uint32_t)input[9]) << 16; 189 c += ((uint32_t)input[10]) << 8; 190 c += ((uint32_t)input[11]); 191 EFX_HASH_MIX(a, b, c); 192 length -= 12; 193 input += 12; 194 } 195 196 /* Handle the left-overs */ 197 switch (length) { 198 case 12: 199 c += ((uint32_t)input[11]); 200 /* Fall-through */ 201 case 11: 202 c += ((uint32_t)input[10]) << 8; 203 /* Fall-through */ 204 case 10: 205 c += ((uint32_t)input[9]) << 16; 206 /* Fall-through */ 207 case 9: 208 c += ((uint32_t)input[8]) << 24; 209 /* Fall-through */ 210 case 8: 211 b += ((uint32_t)input[7]); 212 /* Fall-through */ 213 case 7: 214 b += ((uint32_t)input[6]) << 8; 215 /* Fall-through */ 216 case 6: 217 b += ((uint32_t)input[5]) << 16; 218 /* Fall-through */ 219 case 5: 220 b += ((uint32_t)input[4]) << 24; 221 /* Fall-through */ 222 case 4: 223 a += ((uint32_t)input[3]); 224 /* Fall-through */ 225 case 3: 226 a += ((uint32_t)input[2]) << 8; 227 /* Fall-through */ 228 case 2: 229 a += ((uint32_t)input[1]) << 16; 230 /* Fall-through */ 231 case 1: 232 a += ((uint32_t)input[0]) << 24; 233 EFX_HASH_FINALISE(a, b, c); 234 break; 235 236 case 0: 237 /* Should only get here if length parameter was zero */ 238 break; 239 } 240 241 return (c); 242 } 243 244 #elif EFSYS_IS_LITTLE_ENDIAN 245 246 /* Produce a 32-bit hash from arbitrarily aligned input */ 247 __checkReturn uint32_t 248 efx_hash_bytes( 249 __in_ecount(length) uint8_t const *input, 250 __in size_t length, 251 __in uint32_t init) 252 { 253 uint32_t a; 254 uint32_t b; 255 uint32_t c; 256 257 /* Set up the initial internal state */ 258 a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init; 259 260 /* Handle all but the last twelve bytes of the input */ 261 while (length > 12) { 262 a += ((uint32_t)input[0]); 263 a += ((uint32_t)input[1]) << 8; 264 a += ((uint32_t)input[2]) << 16; 265 a += ((uint32_t)input[3]) << 24; 266 b += ((uint32_t)input[4]); 267 b += ((uint32_t)input[5]) << 8; 268 b += ((uint32_t)input[6]) << 16; 269 b += ((uint32_t)input[7]) << 24; 270 c += ((uint32_t)input[8]); 271 c += ((uint32_t)input[9]) << 8; 272 c += ((uint32_t)input[10]) << 16; 273 c += ((uint32_t)input[11]) << 24; 274 EFX_HASH_MIX(a, b, c); 275 length -= 12; 276 input += 12; 277 } 278 279 /* Handle the left-overs */ 280 switch (length) { 281 case 12: 282 c += ((uint32_t)input[11]) << 24; 283 /* Fall-through */ 284 case 11: 285 c += ((uint32_t)input[10]) << 16; 286 /* Fall-through */ 287 case 10: 288 c += ((uint32_t)input[9]) << 8; 289 /* Fall-through */ 290 case 9: 291 c += ((uint32_t)input[8]); 292 /* Fall-through */ 293 case 8: 294 b += ((uint32_t)input[7]) << 24; 295 /* Fall-through */ 296 case 7: 297 b += ((uint32_t)input[6]) << 16; 298 /* Fall-through */ 299 case 6: 300 b += ((uint32_t)input[5]) << 8; 301 /* Fall-through */ 302 case 5: 303 b += ((uint32_t)input[4]); 304 /* Fall-through */ 305 case 4: 306 a += ((uint32_t)input[3]) << 24; 307 /* Fall-through */ 308 case 3: 309 a += ((uint32_t)input[2]) << 16; 310 /* Fall-through */ 311 case 2: 312 a += ((uint32_t)input[1]) << 8; 313 /* Fall-through */ 314 case 1: 315 a += ((uint32_t)input[0]); 316 EFX_HASH_FINALISE(a, b, c); 317 break; 318 319 case 0: 320 /* Should only get here if length parameter was zero */ 321 break; 322 } 323 324 return (c); 325 } 326 327 #else 328 329 #error "Neither of EFSYS_IS_{BIG,LITTLE}_ENDIAN is set" 330 331 #endif 332