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             : #include <asm/types.h>
       7             : #include <linux/compiler.h>
       8             : 
       9             : /*
      10             :  * The "GOLDEN_RATIO_PRIME" is used in ifs/btrfs/brtfs_inode.h and
      11             :  * fs/inode.c.  It's not actually prime any more (the previous primes
      12             :  * were actively bad for hashing), but the name remains.
      13             :  */
      14             : #if BITS_PER_LONG == 32
      15             : #define GOLDEN_RATIO_PRIME GOLDEN_RATIO_32
      16             : #define hash_long(val, bits) hash_32(val, bits)
      17             : #elif BITS_PER_LONG == 64
      18             : #define hash_long(val, bits) hash_64(val, bits)
      19             : #define GOLDEN_RATIO_PRIME GOLDEN_RATIO_64
      20             : #else
      21             : #error Wordsize not 32 or 64
      22             : #endif
      23             : 
      24             : /*
      25             :  * This hash multiplies the input by a large odd number and takes the
      26             :  * high bits.  Since multiplication propagates changes to the most
      27             :  * significant end only, it is essential that the high bits of the
      28             :  * product be used for the hash value.
      29             :  *
      30             :  * Chuck Lever verified the effectiveness of this technique:
      31             :  * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
      32             :  *
      33             :  * Although a random odd number will do, it turns out that the golden
      34             :  * ratio phi = (sqrt(5)-1)/2, or its negative, has particularly nice
      35             :  * properties.  (See Knuth vol 3, section 6.4, exercise 9.)
      36             :  *
      37             :  * These are the negative, (1 - phi) = phi**2 = (3 - sqrt(5))/2,
      38             :  * which is very slightly easier to multiply by and makes no
      39             :  * difference to the hash distribution.
      40             :  */
      41             : #define GOLDEN_RATIO_32 0x61C88647
      42             : #define GOLDEN_RATIO_64 0x61C8864680B583EBull
      43             : 
      44             : #ifdef CONFIG_HAVE_ARCH_HASH
      45             : /* This header may use the GOLDEN_RATIO_xx constants */
      46             : #include <asm/hash.h>
      47             : #endif
      48             : 
      49             : /*
      50             :  * The _generic versions exist only so lib/test_hash.c can compare
      51             :  * the arch-optimized versions with the generic.
      52             :  *
      53             :  * Note that if you change these, any <asm/hash.h> that aren't updated
      54             :  * to match need to have their HAVE_ARCH_* define values updated so the
      55             :  * self-test will not false-positive.
      56             :  */
      57             : #ifndef HAVE_ARCH__HASH_32
      58             : #define __hash_32 __hash_32_generic
      59             : #endif
      60             : static inline u32 __hash_32_generic(u32 val)
      61             : {
      62   735181948 :         return val * GOLDEN_RATIO_32;
      63             : }
      64             : 
      65         135 : static inline u32 hash_32(u32 val, unsigned int bits)
      66             : {
      67             :         /* High bits are more random, so use them. */
      68   735181948 :         return __hash_32(val) >> (32 - bits);
      69             : }
      70             : 
      71             : #ifndef HAVE_ARCH_HASH_64
      72             : #define hash_64 hash_64_generic
      73             : #endif
      74             : static __always_inline u32 hash_64_generic(u64 val, unsigned int bits)
      75             : {
      76             : #if BITS_PER_LONG == 64
      77             :         /* 64x64-bit multiply is efficient on all 64-bit processors */
      78    27752174 :         return val * GOLDEN_RATIO_64 >> (64 - bits);
      79             : #else
      80             :         /* Hash 64 bits using only 32x32-bit multiply. */
      81             :         return hash_32((u32)val ^ __hash_32(val >> 32), bits);
      82             : #endif
      83             : }
      84             : 
      85             : static inline u32 hash_ptr(const void *ptr, unsigned int bits)
      86             : {
      87    27752172 :         return hash_long((unsigned long)ptr, bits);
      88             : }
      89             : 
      90             : /* This really should be called fold32_ptr; it does no hashing to speak of. */
      91             : static inline u32 hash32_ptr(const void *ptr)
      92             : {
      93             :         unsigned long val = (unsigned long)ptr;
      94             : 
      95             : #if BITS_PER_LONG == 64
      96             :         val ^= (val >> 32);
      97             : #endif
      98             :         return (u32)val;
      99             : }
     100             : 
     101             : #endif /* _LINUX_HASH_H */