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-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