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