<div>Ken,</div>
<div> </div>
<div>You are right, I forgot these were unsigned long's. Also, was there analysis done to pick 59 as the prime multiplier ?</div>
<div><br clear="all">-srinivas<br><br><br></div>
<div class="gmail_quote">On Fri, Jul 9, 2010 at 10:47 AM, Ken Keys <span dir="ltr"><<a href="mailto:kkeys@caida.org">kkeys@caida.org</a>></span> wrote:<br>
<blockquote style="BORDER-LEFT: #ccc 1px solid; MARGIN: 0px 0px 0px 0.8ex; PADDING-LEFT: 1ex" class="gmail_quote">
<div>
<div></div>
<div class="h5">On Fri, Jul 09, 2010 at 12:26:45AM -0700, Srinivas Krishnan wrote:<br>> I was wondering if some one could explain the 2 hash functions used in<br>> crl_dnsstat.c. At first it struck as purely multiplicative hashing way. But<br>
> running through the possible math for make_key_flowstats<br>><br>> it seems like the second term in the hash function (f->ip_proto << 16) +<br>> (f->src.s_addr * 59) + (f->dst.s_addr); could potentially cause overflows<br>
> when returning values as the return value is only 32 bits long.<br>><br>> Am I missing something ?<br>><br>> -srinivas<br><br></div></div>If arithmetic on unsigned values would cause an overflow, it just<br>
truncates the high bits instead. So some information (less than 6<br>bits) is lost for the hash, but there's no error.<br><br>I don't have an analysis handy, but I suspect that attempting<br>to preserve that information would not improve the uniqueness<br>
of the hash value enough to justify the extra computational cost.<br><font color="#888888"><br>--<br>Ken Keys<br><a href="mailto:kkeys@caida.org">kkeys@caida.org</a><br>CoralReef: <a href="http://www.caida.org/tools/measurement/coralreef/" target="_blank">http://www.caida.org/tools/measurement/coralreef/</a><br>
</font></blockquote></div><br>