From owner-freebsd-net Fri May 22 05:27:42 1998 Return-Path: Received: (from majordom@localhost) by hub.freebsd.org (8.8.8/8.8.8) id FAA10317 for freebsd-net-outgoing; Fri, 22 May 1998 05:27:42 -0700 (PDT) (envelope-from owner-freebsd-net@FreeBSD.ORG) Received: from implode.root.com (implode.root.com [198.145.90.17]) by hub.freebsd.org (8.8.8/8.8.8) with ESMTP id FAA10285 for ; Fri, 22 May 1998 05:27:30 -0700 (PDT) (envelope-from root@implode.root.com) Received: from implode.root.com (localhost [127.0.0.1]) by implode.root.com (8.8.5/8.8.5) with ESMTP id FAA00790 for ; Fri, 22 May 1998 05:27:16 -0700 (PDT) Message-Id: <199805221227.FAA00790@implode.root.com> To: freebsd-net@FreeBSD.ORG Subject: hash calculation for IP fast forwarding From: David Greenman Reply-To: dg@root.com Date: Fri, 22 May 1998 05:27:16 -0700 Sender: owner-freebsd-net@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.org As I mentioned recently in freebsd-net, the hash function that the fast IP forwarding code uses is expensive (16 adds, 12 shifts, 6 subtracts, and 6 compares). I think the following will provide a hash with similar quality, but I might be missing something. This assumes that the table is 256 buckets large, but it should work for larger tables as well. Opinions? -DG David Greenman Co-founder/Principal Architect, The FreeBSD Project unsigned int src = 0x91c6115a; /* 198.145.90.17 */ unsigned int dst = 0x01100200; /* 16.1.0.2 */ main() { unsigned int i; i = src ^ dst; i = i ^ (i >> 16); i = i ^ (i >> 8); printf("0x%x,0x%x -> 0x%x\n", src, dst, i & 255); } To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-net" in the body of the message