LCOV - code coverage report
Current view: top level - drivers/net/bnxt/tf_core - lookup3.h (source / functions) Hit Total Coverage
Test: Code coverage Lines: 0 19 0.0 %
Date: 2024-01-22 15:35:40 Functions: 0 1 0.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 6 0.0 %

           Branch data     Line data    Source code
       1                 :            : /* SPDX-License-Identifier: BSD-3-Clause
       2                 :            :  *
       3                 :            :  * Based on lookup3.c, by Bob Jenkins, May 2006, Public Domain.
       4                 :            :  * http://www.burtleburtle.net/bob/c/lookup3.c
       5                 :            :  *
       6                 :            :  * These functions for producing 32-bit hashes for has table lookup.
       7                 :            :  * hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
       8                 :            :  * are externally useful functions. Routines to test the hash are included
       9                 :            :  * if SELF_TEST is defined. You can use this free for any purpose. It is in
      10                 :            :  * the public domain. It has no warranty.
      11                 :            :  */
      12                 :            : 
      13                 :            : #ifndef _LOOKUP3_H_
      14                 :            : #define _LOOKUP3_H_
      15                 :            : 
      16                 :            : #define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
      17                 :            : 
      18                 :            : /** -------------------------------------------------------------------------
      19                 :            :  * This is reversible, so any information in (a,b,c) before mix() is
      20                 :            :  * still in (a,b,c) after mix().
      21                 :            :  *
      22                 :            :  * If four pairs of (a,b,c) inputs are run through mix(), or through
      23                 :            :  * mix() in reverse, there are at least 32 bits of the output that
      24                 :            :  * are sometimes the same for one pair and different for another pair.
      25                 :            :  * This was tested for:
      26                 :            :  *   pairs that differed by one bit, by two bits, in any combination
      27                 :            :  *   of top bits of (a,b,c), or in any combination of bottom bits of
      28                 :            :  *   (a,b,c).
      29                 :            :  *   "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
      30                 :            :  *   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
      31                 :            :  *   is commonly produced by subtraction) look like a single 1-bit
      32                 :            :  *   difference.
      33                 :            :  *   the base values were pseudorandom, all zero but one bit set, or
      34                 :            :  *   all zero plus a counter that starts at zero.
      35                 :            :  *
      36                 :            :  * Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
      37                 :            :  * satisfy this are
      38                 :            :  *     4  6  8 16 19  4
      39                 :            :  *     9 15  3 18 27 15
      40                 :            :  *    14  9  3  7 17  3
      41                 :            :  * Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
      42                 :            :  * for "differ" defined as + with a one-bit base and a two-bit delta.  I
      43                 :            :  * used http://burtleburtle.net/bob/hash/avalanche.html to choose
      44                 :            :  * the operations, constants, and arrangements of the variables.
      45                 :            :  *
      46                 :            :  * This does not achieve avalanche.  There are input bits of (a,b,c)
      47                 :            :  * that fail to affect some output bits of (a,b,c), especially of a.  The
      48                 :            :  * most thoroughly mixed value is c, but it doesn't really even achieve
      49                 :            :  * avalanche in c.
      50                 :            :  *
      51                 :            :  * This allows some parallelism.  Read-after-writes are good at doubling
      52                 :            :  * the number of bits affected, so the goal of mixing pulls in the opposite
      53                 :            :  * direction as the goal of parallelism.  I did what I could.  Rotates
      54                 :            :  * seem to cost as much as shifts on every machine I could lay my hands
      55                 :            :  * on, and rotates are much kinder to the top and bottom bits, so I used
      56                 :            :  * rotates.
      57                 :            :  * --------------------------------------------------------------------------
      58                 :            :  */
      59                 :            : #define mix(a, b, c) \
      60                 :            : { \
      61                 :            :         (a) -= (c); (a) ^= rot((c), 4);  (c) += b; \
      62                 :            :         (b) -= (a); (b) ^= rot((a), 6);  (a) += c; \
      63                 :            :         (c) -= (b); (c) ^= rot((b), 8);  (b) += a; \
      64                 :            :         (a) -= (c); (a) ^= rot((c), 16); (c) += b; \
      65                 :            :         (b) -= (a); (b) ^= rot((a), 19); (a) += c; \
      66                 :            :         (c) -= (b); (c) ^= rot((b), 4);  (b) += a; \
      67                 :            : }
      68                 :            : 
      69                 :            : /** --------------------------------------------------------------------------
      70                 :            :  * final -- final mixing of 3 32-bit values (a,b,c) into c
      71                 :            :  *
      72                 :            :  * Pairs of (a,b,c) values differing in only a few bits will usually
      73                 :            :  * produce values of c that look totally different.  This was tested for
      74                 :            :  *  pairs that differed by one bit, by two bits, in any combination
      75                 :            :  *   of top bits of (a,b,c), or in any combination of bottom bits of
      76                 :            :  *   (a,b,c).
      77                 :            :  *   "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
      78                 :            :  *   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
      79                 :            :  *   is commonly produced by subtraction) look like a single 1-bit
      80                 :            :  *   difference.
      81                 :            :  *   the base values were pseudorandom, all zero but one bit set, or
      82                 :            :  *   all zero plus a counter that starts at zero.
      83                 :            :  *
      84                 :            :  * These constants passed:
      85                 :            :  *  14 11 25 16 4 14 24
      86                 :            :  *  12 14 25 16 4 14 24
      87                 :            :  * and these came close:
      88                 :            :  *   4  8 15 26 3 22 24
      89                 :            :  *  10  8 15 26 3 22 24
      90                 :            :  *  11  8 15 26 3 22 24
      91                 :            :  * --------------------------------------------------------------------------
      92                 :            :  */
      93                 :            : #define final(a, b, c) \
      94                 :            : { \
      95                 :            :         (c) ^= (b); (c) -= rot((b), 14); \
      96                 :            :         (a) ^= (c); (a) -= rot((c), 11); \
      97                 :            :         (b) ^= (a); (b) -= rot((a), 25); \
      98                 :            :         (c) ^= (b); (c) -= rot((b), 16); \
      99                 :            :         (a) ^= (c); (a) -= rot((c), 4);  \
     100                 :            :         (b) ^= (a); (b) -= rot((a), 14); \
     101                 :            :         (c) ^= (b); (c) -= rot((b), 24); \
     102                 :            : }
     103                 :            : 
     104                 :            : /** --------------------------------------------------------------------
     105                 :            :  *  This works on all machines.  To be useful, it requires
     106                 :            :  *  -- that the key be an array of uint32_t's, and
     107                 :            :  *  -- that the length be the number of uint32_t's in the key
     108                 :            : 
     109                 :            :  *  The function hashword() is identical to hashlittle() on little-endian
     110                 :            :  *  machines, and identical to hashbig() on big-endian machines,
     111                 :            :  *  except that the length has to be measured in uint32_ts rather than in
     112                 :            :  *  bytes. hashlittle() is more complicated than hashword() only because
     113                 :            :  *  hashlittle() has to dance around fitting the key bytes into registers.
     114                 :            :  *
     115                 :            :  *  Input Parameters:
     116                 :            :  *       key: an array of uint32_t values
     117                 :            :  *       length: the length of the key, in uint32_ts
     118                 :            :  *       initval: the previous hash, or an arbitrary value
     119                 :            :  * --------------------------------------------------------------------
     120                 :            :  */
     121                 :          0 : static inline uint32_t hashword(const uint32_t *k,
     122                 :            :                                 size_t length,
     123                 :            :                                 uint32_t initval) {
     124                 :            :         uint32_t a, b, c;
     125                 :          0 :         int index = length - 1;
     126                 :            : 
     127                 :            :         /* Set up the internal state */
     128                 :          0 :         a = 0xdeadbeef + (((uint32_t)length) << 2) + initval;
     129                 :            :         b = a;
     130                 :            :         c = a;
     131                 :            : 
     132                 :            :         /*-------------------------------------------- handle most of the key */
     133         [ #  # ]:          0 :         while (length > 3) {
     134                 :          0 :                 a += k[index];
     135                 :          0 :                 b += k[index - 1];
     136                 :          0 :                 c += k[index - 2];
     137                 :          0 :                 mix(a, b, c);
     138                 :          0 :                 length -= 3;
     139                 :          0 :                 index -= 3;
     140                 :            :         }
     141                 :            : 
     142                 :            :         /*-------------------------------------- handle the last 3 uint32_t's */
     143   [ #  #  #  # ]:          0 :         switch (length) {             /* all the case statements fall through */
     144                 :          0 :         case 3:
     145                 :          0 :                 c += k[index - 2];
     146                 :            :                 /* Falls through. */
     147                 :          0 :         case 2:
     148                 :          0 :                 b += k[index - 1];
     149                 :            :                 /* Falls through. */
     150                 :          0 :         case 1:
     151                 :          0 :                 a += k[index];
     152                 :          0 :                 final(a, b, c);
     153                 :            :                 /* Falls through. */
     154                 :            :         case 0:     /* case 0: nothing left to add */
     155                 :            :                 break;
     156                 :            :         }
     157                 :            :         /*------------------------------------------------- report the result */
     158                 :          0 :         return c;
     159                 :            : }
     160                 :            : #endif /* _LOOKUP3_H_ */

Generated by: LCOV version 1.14