[Coral-dev] dnsstat hash functions

[Ken Keys]

On Fri, Jul 09, 2010 at 12:26:45AM -0700, Srinivas Krishnan wrote:
> I was wondering if some one could explain the 2 hash functions used in
> crl_dnsstat.c. At first it struck as purely multiplicative hashing way. But
> running through the possible math for make_key_flowstats
> 
> it seems like the second term in the hash function (f->ip_proto << 16) +
> (f->src.s_addr * 59) + (f->dst.s_addr);   could potentially cause overflows
> when returning values as the return value is only 32 bits long.
> 
> Am I missing something ?
> 
> -srinivas

If arithmetic on unsigned values would cause an overflow, it just
truncates the high bits instead.  So some information (less than 6
bits) is lost for the hash, but there's no error.

I don't have an analysis handy, but I suspect that attempting
to preserve that information would not improve the uniqueness
of the hash value enough to justify the extra computational cost.

-- 
Ken Keys
kkeys at caida.org
CoralReef:  http://www.caida.org/tools/measurement/coralreef/