1: /*************************************************************************
2: * (C) 2009 AITNET ltd - Sofia/Bulgaria - <misho@aitbg.com>
3: * by Michael Pounov <misho@openbsd-bg.org>
4: *
5: * $Author: misho $
6: * $Id: hash.c,v 1.2 2011/04/28 20:28:20 misho Exp $
7: *
8: **************************************************************************
9: The ELWIX and AITNET software is distributed under the following
10: terms:
11:
12: All of the documentation and software included in the ELWIX and AITNET
13: Releases is copyrighted by ELWIX - Sofia/Bulgaria <info@elwix.org>
14:
15: Copyright 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
16: by Michael Pounov <misho@elwix.org>. All rights reserved.
17:
18: Redistribution and use in source and binary forms, with or without
19: modification, are permitted provided that the following conditions
20: are met:
21: 1. Redistributions of source code must retain the above copyright
22: notice, this list of conditions and the following disclaimer.
23: 2. Redistributions in binary form must reproduce the above copyright
24: notice, this list of conditions and the following disclaimer in the
25: documentation and/or other materials provided with the distribution.
26: 3. All advertising materials mentioning features or use of this software
27: must display the following acknowledgement:
28: This product includes software developed by Michael Pounov <misho@elwix.org>
29: ELWIX - Embedded LightWeight unIX and its contributors.
30: 4. Neither the name of AITNET nor the names of its contributors
31: may be used to endorse or promote products derived from this software
32: without specific prior written permission.
33:
34: THIS SOFTWARE IS PROVIDED BY AITNET AND CONTRIBUTORS ``AS IS'' AND
35: ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
36: IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
37: ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
38: FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
39: DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
40: OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
41: HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
42: LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
43: OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
44: SUCH DAMAGE.
45: */
46: #include "global.h"
47:
48:
49: /*
50: * hash_varchar() Compute index hash by variable length string
51: * @csStr = Input data buffer
52: * @nStrLen = Length of data buffer
53: * @nVer = Version of algorythm; 0 - original, 1 - AITNET variant
54: * return: Hash value
55: */
56: inline u_int
57: hash_varchar(const char *csStr, int nStrLen, int nVer)
58: {
59: register u_int n, hash = 0;
60: register int i;
61:
62: assert(csStr);
63:
64: for (i = 0; i < nStrLen; i++) {
65: n = 2 * hash + csStr[i];
66: if (!nVer) {
67: if (hash & 0x80000000)
68: n ^= 0xC0A0A0D5; // Polynom CRC-32 aviation
69: } else {
70: if (n & 1) // Misho ;) patch for better avalanche!!!
71: n ^= 0xC0A0A0D5; // Polynom CRC-32 aviation
72: }
73: hash = n;
74: }
75:
76: return hash;
77: }
78:
79: /*
80: * hash_bernstein() Compute index hash by Bernstein
81: * @csStr = Input data buffer
82: * @nStrLen = Length of data buffer
83: * @nVer = Version of algorythm; 0 - Bernstein, 1 - DJBX33A variant
84: * return: Hash value
85: */
86: inline u_int
87: hash_bernstein(const char *csStr, int nStrLen, int nVer)
88: {
89: register u_int hash = 5381;
90: register int i;
91:
92: assert(csStr);
93:
94: for (i = 0; i < nStrLen; i++)
95: if (!nVer)
96: hash = ((hash << 5) + hash) + csStr[i];
97: else
98: hash = hash * 33 + csStr[i]; // DJBX33A
99:
100: return hash;
101: }
102:
103: /*
104: * hash_fnv1() Compute index hash by FNV-1
105: * @csStr = Input data buffer
106: * @nStrLen = Length of data buffer
107: * @nVer = Version of algorythm; 0 - FNV-1, 1 - FNV-1a (best avalanche)
108: * return: Hash value
109: */
110: inline u_int
111: hash_fnv1(const char *csStr, int nStrLen, int nVer)
112: {
113: register u_int hash = 0x811c9dc5; // 2166136261
114: register int i;
115:
116: assert(csStr);
117:
118: for (i = 0; i < nStrLen; i++)
119: if (!nVer) { // FNV-1
120: hash *= 16777619;
121: hash ^= csStr[i];
122: } else { // FNV-1a
123: hash ^= csStr[i];
124: hash *= 16777619;
125: }
126:
127: return hash;
128: }
129:
130: /*
131: * hash_jenkins() Compute index hash by Jenkins (one-at-a-time)
132: * @csStr = Input data buffer
133: * @nStrLen = Length of data buffer
134: * return: Hash value
135: */
136: inline u_int
137: hash_jenkins(const char *csStr, int nStrLen)
138: {
139: register u_int hash = 0;
140: register int i;
141:
142: assert(csStr);
143:
144: for (i = 0; i < nStrLen; i++) {
145: hash += csStr[i];
146: hash += (hash << 10);
147: hash ^= (hash >> 6);
148: }
149: hash += (hash << 3);
150: hash ^= (hash >> 11);
151: hash += (hash << 15);
152:
153: return hash;
154: }
155:
156: /*
157: * hash_reddragon() Compute index hash by Red Dragon
158: * @csStr = Input data buffer
159: * @nStrLen = Length of data buffer
160: * return: Hash value
161: */
162: inline u_int
163: hash_reddragon(const char *csStr, int nStrLen)
164: {
165: register u_int g, hash;
166: register int i;
167:
168: assert(csStr);
169:
170: for (hash = 0, i = 0; i < nStrLen; i++) {
171: hash = (hash << 4) + csStr[i];
172: if ((g = hash & 0xF0000000)) {
173: hash ^= g >> 24;
174: hash ^= g;
175: }
176: }
177:
178: return hash;
179: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>