From owner-freebsd-hackers@FreeBSD.ORG  Sun Jun  3 12:43:50 2012
Return-Path: <owner-freebsd-hackers@FreeBSD.ORG>
Delivered-To: freebsd-hackers@freebsd.org
Received: from mx1.freebsd.org (mx1.freebsd.org [69.147.83.52])
	by hub.freebsd.org (Postfix) with ESMTP id 95F20106566B
	for <freebsd-hackers@freebsd.org>; Sun,  3 Jun 2012 12:43:50 +0000 (UTC)
	(envelope-from gleb.kurtsou@gmail.com)
Received: from mail-lpp01m010-f54.google.com (mail-lpp01m010-f54.google.com
	[209.85.215.54])
	by mx1.freebsd.org (Postfix) with ESMTP id 0F05F8FC08
	for <freebsd-hackers@freebsd.org>; Sun,  3 Jun 2012 12:43:49 +0000 (UTC)
Received: by laai10 with SMTP id i10so3119553laa.13
	for <freebsd-hackers@freebsd.org>; Sun, 03 Jun 2012 05:43:48 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113;
	h=date:from:to:cc:subject:message-id:references:mime-version
	:content-type:content-disposition:in-reply-to:user-agent;
	bh=pQB8jcinzTj/b3ovAtz9UniQK1z4qbtBgozlFbBgWcE=;
	b=sFV4Xnpa8X8xEMWWPJiKHRL/1y2fT6UMyNiBARp4t1SF8LT3DkcB4hbVRuPZrPsWrf
	XQcCKBX8xQ8PEM8ydFfJvIdpE7DTPLh5qI/pO1DsvtpQuNBIPRBsaHZ3MAXPblsylWRX
	L6EnVsrdsQ6HmuLjDq1MivNOMX+HqGNEpel1AUJ5Ql0Of5vluqWaQoHCNEbTeyMyai1w
	i8VXYkhBlguyNc0ODyqRf20uh53sTTHJo6CWR3RXt3kHqRJZod6hbk4LIkm7EDsQA2IK
	GsniD39Ln4rxy5efadPVrgwMJTyuCzgQBahIR3PA7sU1XW8slwwSmwDjPi0nONUEiea+
	S1/w==
Received: by 10.152.104.171 with SMTP id gf11mr9189863lab.5.1338727428703;
	Sun, 03 Jun 2012 05:43:48 -0700 (PDT)
Received: from localhost ([78.157.92.5])
	by mx.google.com with ESMTPS id xx8sm12647568lab.10.2012.06.03.05.43.46
	(version=SSLv3 cipher=OTHER); Sun, 03 Jun 2012 05:43:46 -0700 (PDT)
Date: Sun, 3 Jun 2012 15:43:42 +0300
From: Gleb Kurtsou <gleb.kurtsou@gmail.com>
To: enrico d'urso <e.durso@live.com>
Message-ID: <20120603124342.GA1225@reks>
References: <DUB116-W41324220EB6A5F7FD8B06A97090@phx.gbl>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
In-Reply-To: <DUB116-W41324220EB6A5F7FD8B06A97090@phx.gbl>
User-Agent: Mutt/1.5.21 (2010-09-15)
Cc: freebsd-hackers@freebsd.org
Subject: Re: [Hash function Ipv4]
X-BeenThere: freebsd-hackers@freebsd.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: Technical Discussions relating to FreeBSD
	<freebsd-hackers.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>, 
	<mailto:freebsd-hackers-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-hackers>
List-Post: <mailto:freebsd-hackers@freebsd.org>
List-Help: <mailto:freebsd-hackers-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>,
	<mailto:freebsd-hackers-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Sun, 03 Jun 2012 12:43:50 -0000

On (02/06/2012 20:14), enrico d'urso wrote:
> 
> Hi,
> I'm looking for an Hash function for Ipv4 addresses.
> 
> What are good ones?

Have you tried good general purpose hash functions like murmur3 or
cityhash?

Another option is to use "hash" function that is bijection on integers
and exploit this fact in data structure, e.g. by using hash array mapped
trie or another prefix tree.

The easiest way to build such function is Feistel network on top of
general purpose hash function as round function. Li and Ri will be most
and less significant 16 bits of ipv4 address accordingly. At least 3
Fiestel rounds required. Play with function to achieve better
performance/distribution.

https://en.wikipedia.org/wiki/Feistel_cipher

Reduced round and block size RC5 also looks very attractive, but it's
patented :(

Thanks,
Gleb.