LCOV - code coverage report
Current view: top level - drivers/common/sfc_efx/base - efx_hash.c (source / functions) Hit Total Coverage
Test: Code coverage Lines: 0 66 0.0 %
Date: 2024-01-22 15:55:54 Functions: 0 2 0.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 21 0.0 %

           Branch data     Line data    Source code
       1                 :            : /* SPDX-License-Identifier: BSD-3-Clause
       2                 :            :  *
       3                 :            :  * Copyright(c) 2019-2021 Xilinx, Inc.
       4                 :            :  * Copyright(c) 2014-2019 Solarflare Communications Inc.
       5                 :            :  *
       6                 :            :  * Copyright 2006 Bob Jenkins
       7                 :            :  *
       8                 :            :  * Derived from public domain source, see
       9                 :            :  *     <http://burtleburtle.net/bob/c/lookup3.c>:
      10                 :            :  *
      11                 :            :  * "lookup3.c, by Bob Jenkins, May 2006, Public Domain.
      12                 :            :  *
      13                 :            :  *  These are functions for producing 32-bit hashes for hash table lookup...
      14                 :            :  *  ...You can use this free for any purpose.  It's in the public domain.
      15                 :            :  *  It has no warranty."
      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                 :          0 : 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                 :          0 :         a = b = c = EFX_HASH_INITIAL_VALUE +
     100                 :          0 :                 (((uint32_t)count) * sizeof (uint32_t)) + init;
     101                 :            : 
     102                 :            :         /* Handle all but the last three dwords of the input */
     103         [ #  # ]:          0 :         while (count > 3) {
     104                 :          0 :                 a += input[0];
     105                 :          0 :                 b += input[1];
     106                 :          0 :                 c += input[2];
     107                 :          0 :                 EFX_HASH_MIX(a, b, c);
     108                 :            : 
     109                 :          0 :                 count -= 3;
     110                 :          0 :                 input += 3;
     111                 :            :         }
     112                 :            : 
     113                 :            :         /* Handle the left-overs */
     114   [ #  #  #  # ]:          0 :         switch (count) {
     115                 :          0 :         case 3:
     116                 :          0 :                 c += input[2];
     117                 :            :                 /* Fall-through */
     118                 :          0 :         case 2:
     119                 :          0 :                 b += input[1];
     120                 :            :                 /* Fall-through */
     121                 :          0 :         case 1:
     122                 :          0 :                 a += input[0];
     123                 :          0 :                 EFX_HASH_FINALISE(a, b, c);
     124                 :          0 :                 break;
     125                 :            : 
     126                 :            :         case 0:
     127                 :            :                 /* Should only get here if count parameter was zero */
     128                 :            :                 break;
     129                 :            :         }
     130                 :            : 
     131                 :          0 :         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                 :          0 : 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                 :          0 :         a = b = c = EFX_HASH_INITIAL_VALUE + (uint32_t)length + init;
     232                 :            : 
     233                 :            :         /* Handle all but the last twelve bytes of the input */
     234         [ #  # ]:          0 :         while (length > 12) {
     235                 :          0 :                 a += ((uint32_t)input[0]);
     236                 :          0 :                 a += ((uint32_t)input[1]) << 8;
     237                 :          0 :                 a += ((uint32_t)input[2]) << 16;
     238                 :          0 :                 a += ((uint32_t)input[3]) << 24;
     239                 :          0 :                 b += ((uint32_t)input[4]);
     240                 :          0 :                 b += ((uint32_t)input[5]) << 8;
     241                 :          0 :                 b += ((uint32_t)input[6]) << 16;
     242                 :          0 :                 b += ((uint32_t)input[7]) << 24;
     243                 :          0 :                 c += ((uint32_t)input[8]);
     244                 :          0 :                 c += ((uint32_t)input[9]) << 8;
     245                 :          0 :                 c += ((uint32_t)input[10]) << 16;
     246                 :          0 :                 c += ((uint32_t)input[11]) << 24;
     247                 :          0 :                 EFX_HASH_MIX(a, b, c);
     248                 :          0 :                 length -= 12;
     249                 :          0 :                 input += 12;
     250                 :            :         }
     251                 :            : 
     252                 :            :         /* Handle the left-overs */
     253   [ #  #  #  #  :          0 :         switch (length) {
          #  #  #  #  #  
             #  #  #  # ]
     254                 :          0 :         case 12:
     255                 :          0 :                 c += ((uint32_t)input[11]) << 24;
     256                 :            :                 /* Fall-through */
     257                 :          0 :         case 11:
     258                 :          0 :                 c += ((uint32_t)input[10]) << 16;
     259                 :            :                 /* Fall-through */
     260                 :          0 :         case 10:
     261                 :          0 :                 c += ((uint32_t)input[9]) << 8;
     262                 :            :                 /* Fall-through */
     263                 :          0 :         case 9:
     264                 :          0 :                 c += ((uint32_t)input[8]);
     265                 :            :                 /* Fall-through */
     266                 :          0 :         case 8:
     267                 :          0 :                 b += ((uint32_t)input[7]) << 24;
     268                 :            :                 /* Fall-through */
     269                 :          0 :         case 7:
     270                 :          0 :                 b += ((uint32_t)input[6]) << 16;
     271                 :            :                 /* Fall-through */
     272                 :          0 :         case 6:
     273                 :          0 :                 b += ((uint32_t)input[5]) << 8;
     274                 :            :                 /* Fall-through */
     275                 :          0 :         case 5:
     276                 :          0 :                 b += ((uint32_t)input[4]);
     277                 :            :                 /* Fall-through */
     278                 :          0 :         case 4:
     279                 :          0 :                 a += ((uint32_t)input[3]) << 24;
     280                 :            :                 /* Fall-through */
     281                 :          0 :         case 3:
     282                 :          0 :                 a += ((uint32_t)input[2]) << 16;
     283                 :            :                 /* Fall-through */
     284                 :          0 :         case 2:
     285                 :          0 :                 a += ((uint32_t)input[1]) << 8;
     286                 :            :                 /* Fall-through */
     287                 :          0 :         case 1:
     288                 :          0 :                 a += ((uint32_t)input[0]);
     289                 :          0 :                 EFX_HASH_FINALISE(a, b, c);
     290                 :          0 :                 break;
     291                 :            : 
     292                 :            :         case 0:
     293                 :            :                 /* Should only get here if length parameter was zero */
     294                 :            :                 break;
     295                 :            :         }
     296                 :            : 
     297                 :          0 :         return (c);
     298                 :            : }
     299                 :            : 
     300                 :            : #else
     301                 :            : 
     302                 :            : #error "Neither of EFSYS_IS_{BIG,LITTLE}_ENDIAN is set"
     303                 :            : 
     304                 :            : #endif

Generated by: LCOV version 1.14