New hash functions according to benchmarks posted yesterday. (The IPv6

version has not been benchmarked yet due to insufficient test data.)
Now ipa_hash() returns a uniformely distributed 16-bit value.

2 files changed, 5 insertions, 3 deletions

diff --git a/lib/ipv4.h b/lib/ipv4.h
index c37ea803..4ae3e952 100644
--- a/lib/ipv4.h
+++ b/lib/ipv4.h
@@ -61,10 +61,12 @@ typedef u32 ip_addr;
 int ipv4_classify(u32);
 u32 ipv4_class_mask(u32);
 
-/* FIXME: Is this hash function uniformly distributed over standard routing tables? */
 static inline unsigned ipv4_hash(u32 a)
 {
-  return a ^ (a >> 16) ^ (a >> 24);
+  /* Returns a 16-bit value */
+  a ^= a >> 16;
+  a ^= a << 10;
+  return a & 0xffff;
 }
 
 #endif
diff --git a/lib/ipv6.h b/lib/ipv6.h
index 1cf52a93..b8d2e9f5 100644
--- a/lib/ipv6.h
+++ b/lib/ipv6.h
@@ -59,7 +59,7 @@ void ipv6_ntoh(ip_addr *);
 static inline unsigned ipv6_hash(ip_addr *a)
 {
   u32 x = _I0(*a) ^ _I1(*a) ^ _I2(*a) ^ _I3(*a);
-  return x ^ (x >> 16) ^ (x >> 8);
+  return (x ^ (x >> 16) ^ (x >> 8)) & 0xffff;
 }
 
 #endif