2 * ngIRCd -- The Next Generation IRC Daemon
3 * Copyright (c)2001,2002 by Alexander Barton (alex@barton.de)
5 * Dieses Programm ist freie Software. Sie koennen es unter den Bedingungen
6 * der GNU General Public License (GPL), wie von der Free Software Foundation
7 * herausgegeben, weitergeben und/oder modifizieren, entweder unter Version 2
8 * der Lizenz oder (wenn Sie es wuenschen) jeder spaeteren Version.
9 * Naehere Informationen entnehmen Sie bitter der Datei COPYING. Eine Liste
10 * der an ngIRCd beteiligten Autoren finden Sie in der Datei AUTHORS.
12 * $Id: hash.c,v 1.2 2002/03/14 15:49:36 alex Exp $
14 * hash.c: Hash-Werte berechnen
27 LOCAL UINT32 jenkins_hash( register UINT8 *k, register UINT32 length, register UINT32 initval);
30 GLOBAL UINT32 Hash( CHAR *String )
32 /* Hash-Wert ueber String berechnen */
33 return jenkins_hash( String, strlen( String ), 42 );
38 * Die hier verwendete Hash-Funktion stammt aus lookup2.c von Bob Jenkins
39 * (URL: <http://burtleburtle.net/bob/c/lookup2.c>). Aus dem Header:
40 * --------------------------------------------------------------------
41 * lookup2.c, by Bob Jenkins, December 1996, Public Domain.
42 * hash(), hash2(), hash3, and mix() are externally useful functions.
43 * Routines to test the hash are included if SELF_TEST is defined.
44 * You can use this free for any purpose. It has no warranty.
45 * --------------------------------------------------------------------
46 * nicht alle seiner Funktionen werden hier genutzt.
50 #define hashsize(n) ((UINT32)1<<(n))
51 #define hashmask(n) (hashsize(n)-1)
55 a -= b; a -= c; a ^= (c>>13); \
56 b -= c; b -= a; b ^= (a<<8); \
57 c -= a; c -= b; c ^= (b>>13); \
58 a -= b; a -= c; a ^= (c>>12); \
59 b -= c; b -= a; b ^= (a<<16); \
60 c -= a; c -= b; c ^= (b>>5); \
61 a -= b; a -= c; a ^= (c>>3); \
62 b -= c; b -= a; b ^= (a<<10); \
63 c -= a; c -= b; c ^= (b>>15); \
67 LOCAL UINT32 jenkins_hash( register UINT8 *k, register UINT32 length, register UINT32 initval)
70 * length: length of the key
71 * initval: the previous hash, or an arbitrary value
74 register UINT32 a,b,c,len;
76 /* Set up the internal state */
78 a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
79 c = initval; /* the previous hash value */
81 /* handle most of the key */
84 a += (k[0] +((UINT32)k[1]<<8) +((UINT32)k[2]<<16) +((UINT32)k[3]<<24));
85 b += (k[4] +((UINT32)k[5]<<8) +((UINT32)k[6]<<16) +((UINT32)k[7]<<24));
86 c += (k[8] +((UINT32)k[9]<<8) +((UINT32)k[10]<<16)+((UINT32)k[11]<<24));
91 /* handle the last 11 bytes */
93 switch(len) /* all the case statements fall through */
95 case 11: c+=((UINT32)k[10]<<24);
96 case 10: c+=((UINT32)k[9]<<16);
97 case 9 : c+=((UINT32)k[8]<<8);
98 /* the first byte of c is reserved for the length */
99 case 8 : b+=((UINT32)k[7]<<24);
100 case 7 : b+=((UINT32)k[6]<<16);
101 case 6 : b+=((UINT32)k[5]<<8);
103 case 4 : a+=((UINT32)k[3]<<24);
104 case 3 : a+=((UINT32)k[2]<<16);
105 case 2 : a+=((UINT32)k[1]<<8);
107 /* case 0: nothing left to add */
111 /* report the result */