From owner-svn-src-all@FreeBSD.ORG Tue Jun 9 21:29:17 2009 Return-Path: Delivered-To: svn-src-all@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 1AC0E1065673; Tue, 9 Jun 2009 21:29:17 +0000 (UTC) (envelope-from kmacy@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:4f8:fff6::2c]) by mx1.freebsd.org (Postfix) with ESMTP id D47DA8FC14; Tue, 9 Jun 2009 21:29:16 +0000 (UTC) (envelope-from kmacy@FreeBSD.org) Received: from svn.freebsd.org (localhost [127.0.0.1]) by svn.freebsd.org (8.14.3/8.14.3) with ESMTP id n59LTGGZ084415; Tue, 9 Jun 2009 21:29:16 GMT (envelope-from kmacy@svn.freebsd.org) Received: (from kmacy@localhost) by svn.freebsd.org (8.14.3/8.14.3/Submit) id n59LTGYo084414; Tue, 9 Jun 2009 21:29:16 GMT (envelope-from kmacy@svn.freebsd.org) Message-Id: <200906092129.n59LTGYo084414@svn.freebsd.org> From: Kip Macy Date: Tue, 9 Jun 2009 21:29:16 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org X-SVN-Group: head MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Cc: Subject: svn commit: r193860 - head/sys/libkern X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 09 Jun 2009 21:29:17 -0000 Author: kmacy Date: Tue Jun 9 21:29:16 2009 New Revision: 193860 URL: http://svn.freebsd.org/changeset/base/193860 Log: add explanatory header license Modified: head/sys/libkern/jenkins.h Modified: head/sys/libkern/jenkins.h ============================================================================== --- head/sys/libkern/jenkins.h Tue Jun 9 21:27:11 2009 (r193859) +++ head/sys/libkern/jenkins.h Tue Jun 9 21:29:16 2009 (r193860) @@ -5,6 +5,42 @@ * $FreeBSD$ */ +/* +------------------------------------------------------------------------------- + lookup3.c, by Bob Jenkins, May 2006, Public Domain. + + These are functions for producing 32-bit hashes for hash table lookup. + hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() + are externally useful functions. Routines to test the hash are included + if SELF_TEST is defined. You can use this free for any purpose. It's in + the public domain. It has no warranty. + + You probably want to use hashlittle(). hashlittle() and hashbig() + hash byte arrays. hashlittle() is is faster than hashbig() on + little-endian machines. Intel and AMD are little-endian machines. + On second thought, you probably want hashlittle2(), which is identical to + hashlittle() except it returns two 32-bit hashes for the price of one. + You could implement hashbig2() if you wanted but I haven't bothered here. + + If you want to find a hash of, say, exactly 7 integers, do + a = i1; b = i2; c = i3; + mix(a,b,c); + a += i4; b += i5; c += i6; + mix(a,b,c); + a += i7; + final(a,b,c); + then use c as the hash value. If you have a variable length array of + 4-byte integers to hash, use hashword(). If you have a byte array (like + a character string), use hashlittle(). If you have several byte arrays, or + a mix of things, see the comments above hashlittle(). + + Why is this so big? I read 12 bytes at a time into 3 4-byte integers, + then mix those integers. This is fast (you can do a lot more thorough + mixing with 12*3 instructions on 3 integers than you can with 3 instructions + on 1 byte), but shoehorning those bytes into integers efficiently is messy. +------------------------------------------------------------------------------- +*/ + #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) /*