drivers/net/sfc/base/efx_hash.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  *
   3  * Copyright 2006 Bob Jenkins
   4  *
   5  * Derived from public domain source, see
   6  *     <http://burtleburtle.net/bob/c/lookup3.c>:
   7  *
   8  * "lookup3.c, by Bob Jenkins, May 2006, Public Domain.
   9  *
  10  *  These are functions for producing 32-bit hashes for hash table lookup...
  11  *  ...You can use this free for any purpose.  It's in the public domain.
  12  *  It has no warranty."
  13  *
  14  * Copyright (c) 2014-2018 Solarflare Communications Inc.
  15  * All rights reserved.
  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