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 "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
 114 /* Produce a 32-bit hash from 32-bit aligned input */
 115         __checkReturn           uint32_t
 116 efx_hash_dwords(
 117         __in_ecount(count)      uint32_t const *input,
 118         __in                    size_t count,
 119         __in                    uint32_t init)
 120 {
 121         uint32_t a;
 122         uint32_t b;
 123         uint32_t c;
 124
 125         /* Set up the initial internal state */
 126         a = b = c = EFX_HASH_INITIAL_VALUE +
 127                 (((uint32_t)count) * sizeof (uint32_t)) + init;
 128
 129         /* Handle all but the last three dwords of the input */
 130         while (count > 3) {
 131                 a += input[0];
 132                 b += input[1];
 133                 c += input[2];
 134                 EFX_HASH_MIX(a, b, c);
 135
 136                 count -= 3;
 137                 input += 3;
 138         }
 139
 140         /* Handle the left-overs */
 141         switch (count) {
 142         case 3:
 143                 c += input[2];
 144                 /* Fall-through */
 145         case 2:
 146                 b += input[1];
 147                 /* Fall-through */
 148         case 1:
 149                 a += input[0];
 150                 EFX_HASH_FINALISE(a, b, c);
 151                 break;
 152
 153         case 0:
 154                 /* Should only get here if count parameter was zero */
 155                 break;
 156         }
 157
 158         return (c);
 159 }
 160
 161 #if EFSYS_IS_BIG_ENDIAN
 162
 163 /* Produce a 32-bit hash from arbitrarily aligned input */
 164         __checkReturn           uint32_t
 165 efx_hash_bytes(
 166         __in_ecount(length)     uint8_t const *input,
 167         __in                    size_t length,
 168         __in                    uint32_t init)
 169 {
 170         uint32_t a;
 171         uint32_t b;
 172         uint32_t c;
 173
 174         /* Set up the initial internal state */
 175         a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init;
 176
 177         /* Handle all but the last twelve bytes of the input */
 178         while (length > 12) {
 179                 a += ((uint32_t)input[0]) << 24;
 180                 a += ((uint32_t)input[1]) << 16;
 181                 a += ((uint32_t)input[2]) << 8;
 182                 a += ((uint32_t)input[3]);
 183                 b += ((uint32_t)input[4]) << 24;
 184                 b += ((uint32_t)input[5]) << 16;
 185                 b += ((uint32_t)input[6]) << 8;
 186                 b += ((uint32_t)input[7]);
 187                 c += ((uint32_t)input[8]) << 24;
 188                 c += ((uint32_t)input[9]) << 16;
 189                 c += ((uint32_t)input[10]) << 8;
 190                 c += ((uint32_t)input[11]);
 191                 EFX_HASH_MIX(a, b, c);
 192                 length -= 12;
 193                 input += 12;
 194         }
 195
 196         /* Handle the left-overs */
 197         switch (length) {
 198         case 12:
 199                 c += ((uint32_t)input[11]);
 200                 /* Fall-through */
 201         case 11:
 202                 c += ((uint32_t)input[10]) << 8;
 203                 /* Fall-through */
 204         case 10:
 205                 c += ((uint32_t)input[9]) << 16;
 206                 /* Fall-through */
 207         case 9:
 208                 c += ((uint32_t)input[8]) << 24;
 209                 /* Fall-through */
 210         case 8:
 211                 b += ((uint32_t)input[7]);
 212                 /* Fall-through */
 213         case 7:
 214                 b += ((uint32_t)input[6]) << 8;
 215                 /* Fall-through */
 216         case 6:
 217                 b += ((uint32_t)input[5]) << 16;
 218                 /* Fall-through */
 219         case 5:
 220                 b += ((uint32_t)input[4]) << 24;
 221                 /* Fall-through */
 222         case 4:
 223                 a += ((uint32_t)input[3]);
 224                 /* Fall-through */
 225         case 3:
 226                 a += ((uint32_t)input[2]) << 8;
 227                 /* Fall-through */
 228         case 2:
 229                 a += ((uint32_t)input[1]) << 16;
 230                 /* Fall-through */
 231         case 1:
 232                 a += ((uint32_t)input[0]) << 24;
 233                 EFX_HASH_FINALISE(a, b, c);
 234                 break;
 235
 236         case 0:
 237                 /* Should only get here if length parameter was zero */
 238                 break;
 239         }
 240
 241         return (c);
 242 }
 243
 244 #elif EFSYS_IS_LITTLE_ENDIAN
 245
 246 /* Produce a 32-bit hash from arbitrarily aligned input */
 247         __checkReturn           uint32_t
 248 efx_hash_bytes(
 249         __in_ecount(length)     uint8_t const *input,
 250         __in                    size_t length,
 251         __in                    uint32_t init)
 252 {
 253         uint32_t a;
 254         uint32_t b;
 255         uint32_t c;
 256
 257         /* Set up the initial internal state */
 258         a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init;
 259
 260         /* Handle all but the last twelve bytes of the input */
 261         while (length > 12) {
 262                 a += ((uint32_t)input[0]);
 263                 a += ((uint32_t)input[1]) << 8;
 264                 a += ((uint32_t)input[2]) << 16;
 265                 a += ((uint32_t)input[3]) << 24;
 266                 b += ((uint32_t)input[4]);
 267                 b += ((uint32_t)input[5]) << 8;
 268                 b += ((uint32_t)input[6]) << 16;
 269                 b += ((uint32_t)input[7]) << 24;
 270                 c += ((uint32_t)input[8]);
 271                 c += ((uint32_t)input[9]) << 8;
 272                 c += ((uint32_t)input[10]) << 16;
 273                 c += ((uint32_t)input[11]) << 24;
 274                 EFX_HASH_MIX(a, b, c);
 275                 length -= 12;
 276                 input += 12;
 277         }
 278
 279         /* Handle the left-overs */
 280         switch (length) {
 281         case 12:
 282                 c += ((uint32_t)input[11]) << 24;
 283                 /* Fall-through */
 284         case 11:
 285                 c += ((uint32_t)input[10]) << 16;
 286                 /* Fall-through */
 287         case 10:
 288                 c += ((uint32_t)input[9]) << 8;
 289                 /* Fall-through */
 290         case 9:
 291                 c += ((uint32_t)input[8]);
 292                 /* Fall-through */
 293         case 8:
 294                 b += ((uint32_t)input[7]) << 24;
 295                 /* Fall-through */
 296         case 7:
 297                 b += ((uint32_t)input[6]) << 16;
 298                 /* Fall-through */
 299         case 6:
 300                 b += ((uint32_t)input[5]) << 8;
 301                 /* Fall-through */
 302         case 5:
 303                 b += ((uint32_t)input[4]);
 304                 /* Fall-through */
 305         case 4:
 306                 a += ((uint32_t)input[3]) << 24;
 307                 /* Fall-through */
 308         case 3:
 309                 a += ((uint32_t)input[2]) << 16;
 310                 /* Fall-through */
 311         case 2:
 312                 a += ((uint32_t)input[1]) << 8;
 313                 /* Fall-through */
 314         case 1:
 315                 a += ((uint32_t)input[0]);
 316                 EFX_HASH_FINALISE(a, b, c);
 317                 break;
 318
 319         case 0:
 320                 /* Should only get here if length parameter was zero */
 321                 break;
 322         }
 323
 324         return (c);
 325 }
 326
 327 #else
 328
 329 #error "Neither of EFSYS_IS_{BIG,LITTLE}_ENDIAN is set"
 330
 331 #endif