Messages in this thread | | | Date | Thu, 11 May 2006 00:35:56 -0700 | From | Andrew Morton <> | Subject | Re: [PATCH-RFC] Improve randomness of hash_long on 64bit. |
| |
NeilBrown <neilb@suse.de> wrote: > > I'm still bothered by the poor showing on hash_long on 64bit > on number that differ only in the 3rd or 4th byte (as IP addresses might > on a little-endian host). > I hacked around the problem in net/sunrpc/svcauth_unix.c until this > issue got resolved, but it never did. So I am pushing again. > > The problem is that the bit-spares prime that is close to the > golden ratio isn't really close enough. > > I propose 'fixing' it by using hash_u32 on the upper and lower halfs > of a 64bit value. This is slightly less efficient, but most code would > probably be happy calling hash_u32 anyway.
We end up with
static inline u32 hash_u32(u32 val, unsigned int bits) { u32 hash = val;
/* On some cpus multiply is faster, on others gcc will do shifts */ hash *= GOLDEN_RATIO_PRIME_32;
/* High bits are more random, so use them. */ return hash >> (32 - bits); }
static inline u32 hash_u64(u64 val, unsigned int bits) { u32 hi = val >> 32; return hash_u32(hash_u32(val, 32) ^ hi, bits); }
So if one does
hash_u64(foo, 44)
we have a negative shift distance. - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |