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
 60static 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
 68static 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
 77static __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
 88static 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. */
 94static 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 */

  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
 60static inline u32 __hash_32_generic(u32 val)
 61{
 62	return val * GOLDEN_RATIO_32;
 63}
 64
 65static inline u32 hash_32(u32 val, unsigned int bits)
 
 
 
 66{
 67	/* High bits are more random, so use them. */
 68	return __hash_32(val) >> (32 - bits);
 69}
 70
 71#ifndef HAVE_ARCH_HASH_64
 72#define hash_64 hash_64_generic
 73#endif
 74static __always_inline u32 hash_64_generic(u64 val, unsigned int bits)
 75{
 76#if BITS_PER_LONG == 64
 77	/* 64x64-bit multiply is efficient on all 64-bit processors */
 78	return val * GOLDEN_RATIO_64 >> (64 - bits);
 79#else
 80	/* Hash 64 bits using only 32x32-bit multiply. */
 81	return hash_32((u32)val ^ __hash_32(val >> 32), bits);
 82#endif
 83}
 84
 85static inline u32 hash_ptr(const void *ptr, unsigned int bits)
 86{
 87	return hash_long((unsigned long)ptr, bits);
 88}
 89
 90/* This really should be called fold32_ptr; it does no hashing to speak of. */
 91static inline u32 hash32_ptr(const void *ptr)
 92{
 93	unsigned long val = (unsigned long)ptr;
 94
 95#if BITS_PER_LONG == 64
 96	val ^= (val >> 32);
 97#endif
 98	return (u32)val;
 99}
100
101#endif /* _LINUX_HASH_H */