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