]>
git.proxmox.com Git - mirror_ubuntu-eoan-kernel.git/blob - include/linux/hash.h
3 /* Fast hashing routine for ints, longs and pointers.
4 (C) 2002 Nadia Yvette Chambers, IBM */
7 #include <linux/compiler.h>
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.
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
21 #error Wordsize not 32 or 64
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.
30 * Chuck Lever verified the effectiveness of this technique:
31 * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
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.)
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.
41 #define GOLDEN_RATIO_32 0x61C88647
42 #define GOLDEN_RATIO_64 0x61C8864680B583EBull
44 #ifdef CONFIG_HAVE_ARCH_HASH
45 /* This header may use the GOLDEN_RATIO_xx constants */
50 * The _generic versions exist only so lib/test_hash.c can compare
51 * the arch-optimized versions with the generic.
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.
57 #ifndef HAVE_ARCH__HASH_32
58 #define __hash_32 __hash_32_generic
60 static inline u32
__hash_32_generic(u32 val
)
62 return val
* GOLDEN_RATIO_32
;
65 #ifndef HAVE_ARCH_HASH_32
66 #define hash_32 hash_32_generic
68 static inline u32
hash_32_generic(u32 val
, unsigned int bits
)
70 /* High bits are more random, so use them. */
71 return __hash_32(val
) >> (32 - bits
);
74 #ifndef HAVE_ARCH_HASH_64
75 #define hash_64 hash_64_generic
77 static __always_inline u32
hash_64_generic(u64 val
, unsigned int bits
)
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
);
83 /* Hash 64 bits using only 32x32-bit multiply. */
84 return hash_32((u32
)val
^ __hash_32(val
>> 32), bits
);
88 static inline u32
hash_ptr(const void *ptr
, unsigned int bits
)
90 return hash_long((unsigned long)ptr
, bits
);
93 /* This really should be called fold32_ptr; it does no hashing to speak of. */
94 static inline u32
hash32_ptr(const void *ptr
)
96 unsigned long val
= (unsigned long)ptr
;
98 #if BITS_PER_LONG == 64
104 #endif /* _LINUX_HASH_H */