Rev 5270 | Show entire file | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 5270 | Rev 6934 | ||
---|---|---|---|
Line 30... | Line 30... | ||
30 | #define GOLDEN_RATIO_PRIME GOLDEN_RATIO_PRIME_64 |
30 | #define GOLDEN_RATIO_PRIME GOLDEN_RATIO_PRIME_64 |
31 | #else |
31 | #else |
32 | #error Wordsize not 32 or 64 |
32 | #error Wordsize not 32 or 64 |
33 | #endif |
33 | #endif |
Line -... | Line 34... | ||
- | 34 | ||
- | 35 | /* |
|
- | 36 | * The above primes are actively bad for hashing, since they are |
|
- | 37 | * too sparse. The 32-bit one is mostly ok, the 64-bit one causes |
|
- | 38 | * real problems. Besides, the "prime" part is pointless for the |
|
- | 39 | * multiplicative hash. |
|
- | 40 | * |
|
- | 41 | * Although a random odd number will do, it turns out that the golden |
|
- | 42 | * ratio phi = (sqrt(5)-1)/2, or its negative, has particularly nice |
|
- | 43 | * properties. |
|
- | 44 | * |
|
- | 45 | * These are the negative, (1 - phi) = (phi^2) = (3 - sqrt(5))/2. |
|
- | 46 | * (See Knuth vol 3, section 6.4, exercise 9.) |
|
- | 47 | */ |
|
- | 48 | #define GOLDEN_RATIO_32 0x61C88647 |
|
- | 49 | #define GOLDEN_RATIO_64 0x61C8864680B583EBull |
|
34 | 50 | ||
35 | static __always_inline u64 hash_64(u64 val, unsigned int bits) |
51 | static __always_inline u64 hash_64(u64 val, unsigned int bits) |
36 | { |
52 | { |
Line 37... | Line 53... | ||
37 | u64 hash = val; |
53 | u64 hash = val; |
38 | 54 | ||
39 | #if defined(CONFIG_ARCH_HAS_FAST_MULTIPLIER) && BITS_PER_LONG == 64 |
55 | #if BITS_PER_LONG == 64 |
40 | hash = hash * GOLDEN_RATIO_PRIME_64; |
56 | hash = hash * GOLDEN_RATIO_64; |
41 | #else |
57 | #else |
42 | /* Sigh, gcc can't optimise this alone like it does for 32 bits. */ |
58 | /* Sigh, gcc can't optimise this alone like it does for 32 bits. */ |
43 | u64 n = hash; |
59 | u64 n = hash; |