1 /* SPDX-License-Identifier: BSD-3-Clause 2 * 3 * Copyright(c) 2019-2021 Xilinx, Inc. 4 * Copyright(c) 2014-2019 Solarflare Communications Inc. 5 * 6 * Copyright 2006 Bob Jenkins 7 * 8 * Derived from public domain source, see 9 * <http://burtleburtle.net/bob/c/lookup3.c>: 10 * 11 * "lookup3.c, by Bob Jenkins, May 2006, Public Domain. 12 * 13 * These are functions for producing 32-bit hashes for hash table lookup... 14 * ...You can use this free for any purpose. It's in the public domain. 15 * It has no warranty." 16 */ 17 18 #include "efx.h" 19 #include "efx_impl.h" 20 21 /* Hash initial value */ 22 #define EFX_HASH_INITIAL_VALUE 0xdeadbeef 23 24 /* 25 * Rotate a 32-bit value left 26 * 27 * Allow platform to provide an intrinsic or optimised routine and 28 * fall-back to a simple shift based implementation. 29 */ 30 #if EFSYS_HAS_ROTL_DWORD 31 32 #define EFX_HASH_ROTATE(_value, _shift) \ 33 EFSYS_ROTL_DWORD(_value, _shift) 34 35 #else 36 37 #define EFX_HASH_ROTATE(_value, _shift) \ 38 (((_value) << (_shift)) | ((_value) >> (32 - (_shift)))) 39 40 #endif 41 42 /* Mix three 32-bit values reversibly */ 43 #define EFX_HASH_MIX(_a, _b, _c) \ 44 do { \ 45 _a -= _c; \ 46 _a ^= EFX_HASH_ROTATE(_c, 4); \ 47 _c += _b; \ 48 _b -= _a; \ 49 _b ^= EFX_HASH_ROTATE(_a, 6); \ 50 _a += _c; \ 51 _c -= _b; \ 52 _c ^= EFX_HASH_ROTATE(_b, 8); \ 53 _b += _a; \ 54 _a -= _c; \ 55 _a ^= EFX_HASH_ROTATE(_c, 16); \ 56 _c += _b; \ 57 _b -= _a; \ 58 _b ^= EFX_HASH_ROTATE(_a, 19); \ 59 _a += _c; \ 60 _c -= _b; \ 61 _c ^= EFX_HASH_ROTATE(_b, 4); \ 62 _b += _a; \ 63 _NOTE(CONSTANTCONDITION) \ 64 } while (B_FALSE) 65 66 /* Final mixing of three 32-bit values into one (_c) */ 67 #define EFX_HASH_FINALISE(_a, _b, _c) \ 68 do { \ 69 _c ^= _b; \ 70 _c -= EFX_HASH_ROTATE(_b, 14); \ 71 _a ^= _c; \ 72 _a -= EFX_HASH_ROTATE(_c, 11); \ 73 _b ^= _a; \ 74 _b -= EFX_HASH_ROTATE(_a, 25); \ 75 _c ^= _b; \ 76 _c -= EFX_HASH_ROTATE(_b, 16); \ 77 _a ^= _c; \ 78 _a -= EFX_HASH_ROTATE(_c, 4); \ 79 _b ^= _a; \ 80 _b -= EFX_HASH_ROTATE(_a, 14); \ 81 _c ^= _b; \ 82 _c -= EFX_HASH_ROTATE(_b, 24); \ 83 _NOTE(CONSTANTCONDITION) \ 84 } while (B_FALSE) 85 86 87 /* Produce a 32-bit hash from 32-bit aligned input */ 88 __checkReturn uint32_t 89 efx_hash_dwords( 90 __in_ecount(count) uint32_t const *input, 91 __in size_t count, 92 __in uint32_t init) 93 { 94 uint32_t a; 95 uint32_t b; 96 uint32_t c; 97 98 /* Set up the initial internal state */ 99 a = b = c = EFX_HASH_INITIAL_VALUE + 100 (((uint32_t)count) * sizeof (uint32_t)) + init; 101 102 /* Handle all but the last three dwords of the input */ 103 while (count > 3) { 104 a += input[0]; 105 b += input[1]; 106 c += input[2]; 107 EFX_HASH_MIX(a, b, c); 108 109 count -= 3; 110 input += 3; 111 } 112 113 /* Handle the left-overs */ 114 switch (count) { 115 case 3: 116 c += input[2]; 117 /* Fall-through */ 118 case 2: 119 b += input[1]; 120 /* Fall-through */ 121 case 1: 122 a += input[0]; 123 EFX_HASH_FINALISE(a, b, c); 124 break; 125 126 case 0: 127 /* Should only get here if count parameter was zero */ 128 break; 129 } 130 131 return (c); 132 } 133 134 #if EFSYS_IS_BIG_ENDIAN 135 136 /* Produce a 32-bit hash from arbitrarily aligned input */ 137 __checkReturn uint32_t 138 efx_hash_bytes( 139 __in_ecount(length) uint8_t const *input, 140 __in size_t length, 141 __in uint32_t init) 142 { 143 uint32_t a; 144 uint32_t b; 145 uint32_t c; 146 147 /* Set up the initial internal state */ 148 a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init; 149 150 /* Handle all but the last twelve bytes of the input */ 151 while (length > 12) { 152 a += ((uint32_t)input[0]) << 24; 153 a += ((uint32_t)input[1]) << 16; 154 a += ((uint32_t)input[2]) << 8; 155 a += ((uint32_t)input[3]); 156 b += ((uint32_t)input[4]) << 24; 157 b += ((uint32_t)input[5]) << 16; 158 b += ((uint32_t)input[6]) << 8; 159 b += ((uint32_t)input[7]); 160 c += ((uint32_t)input[8]) << 24; 161 c += ((uint32_t)input[9]) << 16; 162 c += ((uint32_t)input[10]) << 8; 163 c += ((uint32_t)input[11]); 164 EFX_HASH_MIX(a, b, c); 165 length -= 12; 166 input += 12; 167 } 168 169 /* Handle the left-overs */ 170 switch (length) { 171 case 12: 172 c += ((uint32_t)input[11]); 173 /* Fall-through */ 174 case 11: 175 c += ((uint32_t)input[10]) << 8; 176 /* Fall-through */ 177 case 10: 178 c += ((uint32_t)input[9]) << 16; 179 /* Fall-through */ 180 case 9: 181 c += ((uint32_t)input[8]) << 24; 182 /* Fall-through */ 183 case 8: 184 b += ((uint32_t)input[7]); 185 /* Fall-through */ 186 case 7: 187 b += ((uint32_t)input[6]) << 8; 188 /* Fall-through */ 189 case 6: 190 b += ((uint32_t)input[5]) << 16; 191 /* Fall-through */ 192 case 5: 193 b += ((uint32_t)input[4]) << 24; 194 /* Fall-through */ 195 case 4: 196 a += ((uint32_t)input[3]); 197 /* Fall-through */ 198 case 3: 199 a += ((uint32_t)input[2]) << 8; 200 /* Fall-through */ 201 case 2: 202 a += ((uint32_t)input[1]) << 16; 203 /* Fall-through */ 204 case 1: 205 a += ((uint32_t)input[0]) << 24; 206 EFX_HASH_FINALISE(a, b, c); 207 break; 208 209 case 0: 210 /* Should only get here if length parameter was zero */ 211 break; 212 } 213 214 return (c); 215 } 216 217 #elif EFSYS_IS_LITTLE_ENDIAN 218 219 /* Produce a 32-bit hash from arbitrarily aligned input */ 220 __checkReturn uint32_t 221 efx_hash_bytes( 222 __in_ecount(length) uint8_t const *input, 223 __in size_t length, 224 __in uint32_t init) 225 { 226 uint32_t a; 227 uint32_t b; 228 uint32_t c; 229 230 /* Set up the initial internal state */ 231 a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init; 232 233 /* Handle all but the last twelve bytes of the input */ 234 while (length > 12) { 235 a += ((uint32_t)input[0]); 236 a += ((uint32_t)input[1]) << 8; 237 a += ((uint32_t)input[2]) << 16; 238 a += ((uint32_t)input[3]) << 24; 239 b += ((uint32_t)input[4]); 240 b += ((uint32_t)input[5]) << 8; 241 b += ((uint32_t)input[6]) << 16; 242 b += ((uint32_t)input[7]) << 24; 243 c += ((uint32_t)input[8]); 244 c += ((uint32_t)input[9]) << 8; 245 c += ((uint32_t)input[10]) << 16; 246 c += ((uint32_t)input[11]) << 24; 247 EFX_HASH_MIX(a, b, c); 248 length -= 12; 249 input += 12; 250 } 251 252 /* Handle the left-overs */ 253 switch (length) { 254 case 12: 255 c += ((uint32_t)input[11]) << 24; 256 /* Fall-through */ 257 case 11: 258 c += ((uint32_t)input[10]) << 16; 259 /* Fall-through */ 260 case 10: 261 c += ((uint32_t)input[9]) << 8; 262 /* Fall-through */ 263 case 9: 264 c += ((uint32_t)input[8]); 265 /* Fall-through */ 266 case 8: 267 b += ((uint32_t)input[7]) << 24; 268 /* Fall-through */ 269 case 7: 270 b += ((uint32_t)input[6]) << 16; 271 /* Fall-through */ 272 case 6: 273 b += ((uint32_t)input[5]) << 8; 274 /* Fall-through */ 275 case 5: 276 b += ((uint32_t)input[4]); 277 /* Fall-through */ 278 case 4: 279 a += ((uint32_t)input[3]) << 24; 280 /* Fall-through */ 281 case 3: 282 a += ((uint32_t)input[2]) << 16; 283 /* Fall-through */ 284 case 2: 285 a += ((uint32_t)input[1]) << 8; 286 /* Fall-through */ 287 case 1: 288 a += ((uint32_t)input[0]); 289 EFX_HASH_FINALISE(a, b, c); 290 break; 291 292 case 0: 293 /* Should only get here if length parameter was zero */ 294 break; 295 } 296 297 return (c); 298 } 299 300 #else 301 302 #error "Neither of EFSYS_IS_{BIG,LITTLE}_ENDIAN is set" 303 304 #endif 305