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                 :            : #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                 :     201538 : static inline u32 __hash_32_generic(u32 val)
      61                 :            : {
      62                 :  413216082 :         return val * GOLDEN_RATIO_32;
      63                 :            : }
      64                 :            : 
      65                 :            : #ifndef HAVE_ARCH_HASH_32
      66                 :            : #define hash_32 hash_32_generic
      67                 :            : #endif
      68                 :     201538 : static inline u32 hash_32_generic(u32 val, unsigned int bits)
      69                 :            : {
      70                 :            :         /* High bits are more random, so use them. */
      71                 :   75101424 :         return __hash_32(val) >> (32 - bits);
      72                 :            : }
      73                 :            : 
      74                 :            : #ifndef HAVE_ARCH_HASH_64
      75                 :            : #define hash_64 hash_64_generic
      76                 :            : #endif
      77                 :            : static __always_inline u32 hash_64_generic(u64 val, unsigned int bits)
      78                 :            : {
      79                 :            : #if BITS_PER_LONG == 64
      80                 :            :         /* 64x64-bit multiply is efficient on all 64-bit processors */
      81                 :            :         return val * GOLDEN_RATIO_64 >> (64 - bits);
      82                 :            : #else
      83                 :            :         /* Hash 64 bits using only 32x32-bit multiply. */
      84                 :     201538 :         return hash_32((u32)val ^ __hash_32(val >> 32), bits);
      85                 :            : #endif
      86                 :            : }
      87                 :            : 
      88                 :            : static inline u32 hash_ptr(const void *ptr, unsigned int bits)
      89                 :            : {
      90                 :    2674144 :         return hash_long((unsigned long)ptr, bits);
      91                 :            : }
      92                 :            : 
      93                 :            : /* This really should be called fold32_ptr; it does no hashing to speak of. */
      94                 :            : static inline u32 hash32_ptr(const void *ptr)
      95                 :            : {
      96                 :      25274 :         unsigned long val = (unsigned long)ptr;
      97                 :            : 
      98                 :            : #if BITS_PER_LONG == 64
      99                 :            :         val ^= (val >> 32);
     100                 :            : #endif
     101                 :            :         return (u32)val;
     102                 :            : }
     103                 :            : 
     104                 :            : #endif /* _LINUX_HASH_H */