sys/dev/sfxge/common/efx_hash.c

   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$");
  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
 118 efx_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
 167 efx_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
 250 efx_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