Subversion Repositories Kolibri OS

Rev

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;