Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 1 | #ifndef _LINUX_HASH_H |
| 2 | #define _LINUX_HASH_H |
Matthew Wilcox | 4e70148 | 2008-02-06 01:36:14 -0800 | [diff] [blame] | 3 | /* Fast hashing routine for ints, longs and pointers. |
Nadia Yvette Chambers | 6d49e35 | 2012-12-06 10:39:54 +0100 | [diff] [blame] | 4 | (C) 2002 Nadia Yvette Chambers, IBM */ |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 5 | |
Matthew Wilcox | 4e70148 | 2008-02-06 01:36:14 -0800 | [diff] [blame] | 6 | #include <asm/types.h> |
Masami Hiramatsu | 65c1055 | 2013-03-14 20:52:30 +0900 | [diff] [blame] | 7 | #include <linux/compiler.h> |
Matthew Wilcox | 4e70148 | 2008-02-06 01:36:14 -0800 | [diff] [blame] | 8 | |
George Spelvin | ef703f4 | 2016-05-26 23:00:23 -0400 | [diff] [blame^] | 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 | */ |
Matthew Wilcox | 4e70148 | 2008-02-06 01:36:14 -0800 | [diff] [blame] | 14 | #if BITS_PER_LONG == 32 |
George Spelvin | ef703f4 | 2016-05-26 23:00:23 -0400 | [diff] [blame^] | 15 | #define GOLDEN_RATIO_PRIME GOLDEN_RATIO_32 |
Matthew Wilcox | 4e70148 | 2008-02-06 01:36:14 -0800 | [diff] [blame] | 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) |
George Spelvin | ef703f4 | 2016-05-26 23:00:23 -0400 | [diff] [blame^] | 19 | #define GOLDEN_RATIO_PRIME GOLDEN_RATIO_64 |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 20 | #else |
Matthew Wilcox | 4e70148 | 2008-02-06 01:36:14 -0800 | [diff] [blame] | 21 | #error Wordsize not 32 or 64 |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 22 | #endif |
| 23 | |
Linus Torvalds | 689de1d | 2016-05-02 12:46:42 -0700 | [diff] [blame] | 24 | /* |
George Spelvin | ef703f4 | 2016-05-26 23:00:23 -0400 | [diff] [blame^] | 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 |
Linus Torvalds | 689de1d | 2016-05-02 12:46:42 -0700 | [diff] [blame] | 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 |
George Spelvin | ef703f4 | 2016-05-26 23:00:23 -0400 | [diff] [blame^] | 35 | * properties. (See Knuth vol 3, section 6.4, exercise 9.) |
Linus Torvalds | 689de1d | 2016-05-02 12:46:42 -0700 | [diff] [blame] | 36 | * |
George Spelvin | ef703f4 | 2016-05-26 23:00:23 -0400 | [diff] [blame^] | 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. |
Linus Torvalds | 689de1d | 2016-05-02 12:46:42 -0700 | [diff] [blame] | 40 | */ |
| 41 | #define GOLDEN_RATIO_32 0x61C88647 |
| 42 | #define GOLDEN_RATIO_64 0x61C8864680B583EBull |
| 43 | |
George Spelvin | ef703f4 | 2016-05-26 23:00:23 -0400 | [diff] [blame^] | 44 | |
| 45 | static inline u32 __hash_32(u32 val) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 46 | { |
George Spelvin | ef703f4 | 2016-05-26 23:00:23 -0400 | [diff] [blame^] | 47 | return val * GOLDEN_RATIO_32; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 48 | } |
Matthew Wilcox | 4e70148 | 2008-02-06 01:36:14 -0800 | [diff] [blame] | 49 | |
| 50 | static inline u32 hash_32(u32 val, unsigned int bits) |
| 51 | { |
Matthew Wilcox | 4e70148 | 2008-02-06 01:36:14 -0800 | [diff] [blame] | 52 | /* High bits are more random, so use them. */ |
George Spelvin | ef703f4 | 2016-05-26 23:00:23 -0400 | [diff] [blame^] | 53 | return __hash_32(val) >> (32 - bits); |
| 54 | } |
| 55 | |
| 56 | static __always_inline u32 hash_64(u64 val, unsigned int bits) |
| 57 | { |
| 58 | #if BITS_PER_LONG == 64 |
| 59 | /* 64x64-bit multiply is efficient on all 64-bit processors */ |
| 60 | return val * GOLDEN_RATIO_64 >> (64 - bits); |
| 61 | #else |
| 62 | /* Hash 64 bits using only 32x32-bit multiply. */ |
| 63 | return hash_32((u32)val ^ __hash_32(val >> 32), bits); |
| 64 | #endif |
Matthew Wilcox | 4e70148 | 2008-02-06 01:36:14 -0800 | [diff] [blame] | 65 | } |
| 66 | |
George Spelvin | 92d5677 | 2016-05-26 22:22:01 -0400 | [diff] [blame] | 67 | static inline u32 hash_ptr(const void *ptr, unsigned int bits) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 68 | { |
| 69 | return hash_long((unsigned long)ptr, bits); |
| 70 | } |
Pavel Emelyanov | b14f243 | 2012-08-08 21:52:28 +0000 | [diff] [blame] | 71 | |
George Spelvin | ef703f4 | 2016-05-26 23:00:23 -0400 | [diff] [blame^] | 72 | /* This really should be called fold32_ptr; it does no hashing to speak of. */ |
Pavel Emelyanov | b14f243 | 2012-08-08 21:52:28 +0000 | [diff] [blame] | 73 | static inline u32 hash32_ptr(const void *ptr) |
| 74 | { |
| 75 | unsigned long val = (unsigned long)ptr; |
| 76 | |
| 77 | #if BITS_PER_LONG == 64 |
| 78 | val ^= (val >> 32); |
| 79 | #endif |
| 80 | return (u32)val; |
| 81 | } |
Francesco Fusco | 71ae8aa | 2013-12-12 16:09:05 +0100 | [diff] [blame] | 82 | |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 83 | #endif /* _LINUX_HASH_H */ |