August 8, 2007 Leave a comment
The hash_long function is found a lot of places in the kernel. Amongst other places it is how PIDs are stored in a table.
The has_long function boils down to
unsigned long hash_long(unsigned long val, unsigned int bits)
unsigned long hash = val * 0x9e370001UL;
return hash >> (32 – bits);
When I stumbled across this I was curious as to where 0x9e370001 came from. After a bit of searching, I found this:
(from “Understanding the Linux Kernel”)
The Magic Constant
You might wonder where the 0xe370001 constant (= 2,654,404,609) comes from. This hash function is based on a multiplication of the index by a suitable large number, so that the result overflows and the value remaining in the 32-bit variable can be considered as the result of a modulus operation. Knuth suggested that good results are obtained when the large multiplier is a prime approximately in golden ration to 2^32 (32 bit being the size of x86 registers). Now, 2,654,404,609 is a prime near to 2^32 * (sqrt(5) -1)/2 that can also be easily multiplied by additions and bit shifts, because it is equal to 2^31 + 2^29 -2^25 -2^19-2^16+1.
In other words, pulled out of Knuth’s and other’s asses.
Do people just sit around thinking about this type of stuff? My guess would be yes. All I know is my new favorite number is now 2,654,404,609.