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 | return val * GOLDEN_RATIO_32; |

63 | } |

64 | |

65 | #ifndef HAVE_ARCH_HASH_32 |

66 | #define hash_32 hash_32_generic |

67 | #endif |

68 | static inline u32 hash_32_generic(u32 val, unsigned int bits) |

69 | { |

70 | /* High bits are more random, so use them. */ |

71 | 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 | 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 | 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 | 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 */ |

105 |