svn commit: r193860 - head/sys/libkern

Kip Macy kmacy at FreeBSD.org
Tue Jun 9 21:29:17 UTC 2009


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))))
 
 /*


More information about the svn-src-all mailing list