Branch data     Line data    Source code

       1                 :            : #ifndef _LINUX_JHASH_H
       2                 :            : #define _LINUX_JHASH_H
       3                 :            : 
       4                 :            : /* jhash.h: Jenkins hash support.
       5                 :            :  *
       6                 :            :  * Copyright (C) 2006. Bob Jenkins (bob_jenkins@burtleburtle.net)
       7                 :            :  *
       8                 :            :  * http://burtleburtle.net/bob/hash/
       9                 :            :  *
      10                 :            :  * These are the credits from Bob's sources:
      11                 :            :  *
      12                 :            :  * lookup3.c, by Bob Jenkins, May 2006, Public Domain.
      13                 :            :  *
      14                 :            :  * These are functions for producing 32-bit hashes for hash table lookup.
      15                 :            :  * hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
      16                 :            :  * are externally useful functions.  Routines to test the hash are included
      17                 :            :  * if SELF_TEST is defined.  You can use this free for any purpose.  It's in
      18                 :            :  * the public domain.  It has no warranty.
      19                 :            :  *
      20                 :            :  * Copyright (C) 2009-2010 Jozsef Kadlecsik (kadlec@netfilter.org)
      21                 :            :  *
      22                 :            :  * I've modified Bob's hash to be useful in the Linux kernel, and
      23                 :            :  * any bugs present are my fault.
      24                 :            :  * Jozsef
      25                 :            :  */
      26                 :            : #include <linux/bitops.h>
      27                 :            : #include <linux/unaligned/packed_struct.h>
      28                 :            : 
      29                 :            : /* Best hash sizes are of power of two */
      30                 :            : #define jhash_size(n)   ((u32)1<<(n))
      31                 :            : /* Mask the hash value, i.e (value & jhash_mask(n)) instead of (value % n) */
      32                 :            : #define jhash_mask(n)   (jhash_size(n)-1)
      33                 :            : 
      34                 :            : /* __jhash_mix -- mix 3 32-bit values reversibly. */
      35                 :            : #define __jhash_mix(a, b, c)                    \
      36                 :            : {                                               \
      37                 :            :         a -= c;  a ^= rol32(c, 4);  c += b;     \
      38                 :            :         b -= a;  b ^= rol32(a, 6);  a += c;     \
      39                 :            :         c -= b;  c ^= rol32(b, 8);  b += a;     \
      40                 :            :         a -= c;  a ^= rol32(c, 16); c += b;     \
      41                 :            :         b -= a;  b ^= rol32(a, 19); a += c;     \
      42                 :            :         c -= b;  c ^= rol32(b, 4);  b += a;     \
      43                 :            : }
      44                 :            : 
      45                 :            : /* __jhash_final - final mixing of 3 32-bit values (a,b,c) into c */
      46                 :            : #define __jhash_final(a, b, c)                  \
      47                 :            : {                                               \
      48                 :            :         c ^= b; c -= rol32(b, 14);              \
      49                 :            :         a ^= c; a -= rol32(c, 11);              \
      50                 :            :         b ^= a; b -= rol32(a, 25);              \
      51                 :            :         c ^= b; c -= rol32(b, 16);              \
      52                 :            :         a ^= c; a -= rol32(c, 4);               \
      53                 :            :         b ^= a; b -= rol32(a, 14);              \
      54                 :            :         c ^= b; c -= rol32(b, 24);              \
      55                 :            : }
      56                 :            : 
      57                 :            : /* An arbitrary initial parameter */
      58                 :            : #define JHASH_INITVAL           0xdeadbeef
      59                 :            : 
      60                 :            : /* jhash - hash an arbitrary key
      61                 :            :  * @k: sequence of bytes as key
      62                 :            :  * @length: the length of the key
      63                 :            :  * @initval: the previous hash, or an arbitray value
      64                 :            :  *
      65                 :            :  * The generic version, hashes an arbitrary sequence of bytes.
      66                 :            :  * No alignment or length assumptions are made about the input key.
      67                 :            :  *
      68                 :            :  * Returns the hash value of the key. The result depends on endianness.
      69                 :            :  */
      70                 :          3 : static inline u32 jhash(const void *key, u32 length, u32 initval)
      71                 :            : {
      72                 :            :         u32 a, b, c;
      73                 :            :         const u8 *k = key;
      74                 :            : 
      75                 :            :         /* Set up the internal state */
      76                 :          3 :         a = b = c = JHASH_INITVAL + length + initval;
      77                 :            : 
      78                 :            :         /* All but the last block: affect some 32 bits of (a,b,c) */
      79                 :          3 :         while (length > 12) {
      80                 :          3 :                 a += __get_unaligned_cpu32(k);
      81                 :          3 :                 b += __get_unaligned_cpu32(k + 4);
      82                 :          3 :                 c += __get_unaligned_cpu32(k + 8);
      83                 :          3 :                 __jhash_mix(a, b, c);
      84                 :          3 :                 length -= 12;
      85                 :          3 :                 k += 12;
      86                 :            :         }
      87                 :            :         /* Last block: affect all 32 bits of (c) */
      88                 :          3 :         switch (length) {
      89                 :          0 :         case 12: c += (u32)k[11]<<24;     /* fall through */
      90                 :          0 :         case 11: c += (u32)k[10]<<16;     /* fall through */
      91                 :          0 :         case 10: c += (u32)k[9]<<8;       /* fall through */
      92                 :          0 :         case 9:  c += k[8];             /* fall through */
      93                 :          0 :         case 8:  b += (u32)k[7]<<24;      /* fall through */
      94                 :          0 :         case 7:  b += (u32)k[6]<<16;      /* fall through */
      95                 :          0 :         case 6:  b += (u32)k[5]<<8;       /* fall through */
      96                 :          0 :         case 5:  b += k[4];             /* fall through */
      97                 :          3 :         case 4:  a += (u32)k[3]<<24;      /* fall through */
      98                 :          3 :         case 3:  a += (u32)k[2]<<16;      /* fall through */
      99                 :          3 :         case 2:  a += (u32)k[1]<<8;       /* fall through */
     100                 :          3 :         case 1:  a += k[0];
     101                 :          3 :                  __jhash_final(a, b, c);
     102                 :            :         case 0: /* Nothing left to add */
     103                 :            :                 break;
     104                 :            :         }
     105                 :            : 
     106                 :          3 :         return c;
     107                 :            : }
     108                 :            : 
     109                 :            : /* jhash2 - hash an array of u32's
     110                 :            :  * @k: the key which must be an array of u32's
     111                 :            :  * @length: the number of u32's in the key
     112                 :            :  * @initval: the previous hash, or an arbitray value
     113                 :            :  *
     114                 :            :  * Returns the hash value of the key.
     115                 :            :  */
     116                 :          3 : static inline u32 jhash2(const u32 *k, u32 length, u32 initval)
     117                 :            : {
     118                 :            :         u32 a, b, c;
     119                 :            : 
     120                 :            :         /* Set up the internal state */
     121                 :          3 :         a = b = c = JHASH_INITVAL + (length<<2) + initval;
     122                 :            : 
     123                 :            :         /* Handle most of the key */
     124                 :          3 :         while (length > 3) {
     125                 :          1 :                 a += k[0];
     126                 :          1 :                 b += k[1];
     127                 :          1 :                 c += k[2];
     128                 :          1 :                 __jhash_mix(a, b, c);
     129                 :          1 :                 length -= 3;
     130                 :          1 :                 k += 3;
     131                 :            :         }
     132                 :            : 
     133                 :            :         /* Handle the last 3 u32's */
     134                 :          3 :         switch (length) {
     135                 :          3 :         case 3: c += k[2];      /* fall through */
     136                 :          3 :         case 2: b += k[1];      /* fall through */
     137                 :          3 :         case 1: a += k[0];
     138                 :          3 :                 __jhash_final(a, b, c);
     139                 :            :         case 0: /* Nothing left to add */
     140                 :            :                 break;
     141                 :            :         }
     142                 :            : 
     143                 :          3 :         return c;
     144                 :            : }
     145                 :            : 
     146                 :            : 
     147                 :            : /* __jhash_nwords - hash exactly 3, 2 or 1 word(s) */
     148                 :          3 : static inline u32 __jhash_nwords(u32 a, u32 b, u32 c, u32 initval)
     149                 :            : {
     150                 :          3 :         a += initval;
     151                 :          3 :         b += initval;
     152                 :          3 :         c += initval;
     153                 :            : 
     154                 :          3 :         __jhash_final(a, b, c);
     155                 :            : 
     156                 :          3 :         return c;
     157                 :            : }
     158                 :            : 
     159                 :            : static inline u32 jhash_3words(u32 a, u32 b, u32 c, u32 initval)
     160                 :            : {
     161                 :          3 :         return __jhash_nwords(a, b, c, initval + JHASH_INITVAL + (3 << 2));
     162                 :            : }
     163                 :            : 
     164                 :            : static inline u32 jhash_2words(u32 a, u32 b, u32 initval)
     165                 :            : {
     166                 :          0 :         return __jhash_nwords(a, b, 0, initval + JHASH_INITVAL + (2 << 2));
     167                 :            : }
     168                 :            : 
     169                 :            : static inline u32 jhash_1word(u32 a, u32 initval)
     170                 :            : {
     171                 :          3 :         return __jhash_nwords(a, 0, 0, initval + JHASH_INITVAL + (1 << 2));
     172                 :            : }
     173                 :            : 
     174                 :            : #endif /* _LINUX_JHASH_H */