Branch data     Line data    Source code

       1                 :            : #ifndef _LINUX_HASH_H
       2                 :            : #define _LINUX_HASH_H
       3                 :            : /* Fast hashing routine for ints,  longs and pointers.
       4                 :            :    (C) 2002 Nadia Yvette Chambers, IBM */
       5                 :            : 
       6                 :            : /*
       7                 :            :  * Knuth recommends primes in approximately golden ratio to the maximum
       8                 :            :  * integer representable by a machine word for multiplicative hashing.
       9                 :            :  * Chuck Lever verified the effectiveness of this technique:
      10                 :            :  * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
      11                 :            :  *
      12                 :            :  * These primes are chosen to be bit-sparse, that is operations on
      13                 :            :  * them can use shifts and additions instead of multiplications for
      14                 :            :  * machines where multiplications are slow.
      15                 :            :  */
      16                 :            : 
      17                 :            : #include <asm/types.h>
      18                 :            : #include <linux/compiler.h>
      19                 :            : 
      20                 :            : /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
      21                 :            : #define GOLDEN_RATIO_PRIME_32 0x9e370001UL
      22                 :            : /*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
      23                 :            : #define GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001UL
      24                 :            : 
      25                 :            : #if BITS_PER_LONG == 32
      26                 :            : #define GOLDEN_RATIO_PRIME GOLDEN_RATIO_PRIME_32
      27                 :            : #define hash_long(val, bits) hash_32(val, bits)
      28                 :            : #elif BITS_PER_LONG == 64
      29                 :            : #define hash_long(val, bits) hash_64(val, bits)
      30                 :            : #define GOLDEN_RATIO_PRIME GOLDEN_RATIO_PRIME_64
      31                 :            : #else
      32                 :            : #error Wordsize not 32 or 64
      33                 :            : #endif
      34                 :            : 
      35                 :            : static __always_inline u64 hash_64(u64 val, unsigned int bits)
      36                 :            : {
      37                 :            :         u64 hash = val;
      38                 :            : 
      39                 :            :         /*  Sigh, gcc can't optimise this alone like it does for 32 bits. */
      40                 :            :         u64 n = hash;
      41                 :          0 :         n <<= 18;
      42                 :          0 :         hash -= n;
      43                 :          0 :         n <<= 33;
      44                 :          0 :         hash -= n;
      45                 :          0 :         n <<= 3;
      46                 :          0 :         hash += n;
      47                 :          0 :         n <<= 3;
      48                 :          0 :         hash -= n;
      49                 :          0 :         n <<= 4;
      50                 :          0 :         hash += n;
      51                 :          0 :         n <<= 2;
      52                 :          0 :         hash += n;
      53                 :            : 
      54                 :            :         /* High bits are more random, so use them. */
      55                 :          0 :         return hash >> (64 - bits);
      56                 :            : }
      57                 :            : 
      58                 :            : static inline u32 hash_32(u32 val, unsigned int bits)
      59                 :            : {
      60                 :            :         /* On some cpus multiply is faster, on others gcc will do shifts */
      61                 :  337291535 :         u32 hash = val * GOLDEN_RATIO_PRIME_32;
      62                 :            : 
      63                 :            :         /* High bits are more random, so use them. */
      64                 :  337291535 :         return hash >> (32 - bits);
      65                 :            : }
      66                 :            : 
      67                 :            : static inline unsigned long hash_ptr(const void *ptr, unsigned int bits)
      68                 :            : {
      69                 :  298271815 :         return hash_long((unsigned long)ptr, bits);
      70                 :            : }
      71                 :            : 
      72                 :            : static inline u32 hash32_ptr(const void *ptr)
      73                 :            : {
      74                 :         33 :         unsigned long val = (unsigned long)ptr;
      75                 :            : 
      76                 :            : #if BITS_PER_LONG == 64
      77                 :            :         val ^= (val >> 32);
      78                 :            : #endif
      79                 :            :         return (u32)val;
      80                 :            : }
      81                 :            : #endif /* _LINUX_HASH_H */