Annotation of libelwix/src/hash.c, revision 1.1.1.1
1.1 misho 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.4 2012/08/29 09:00:44 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, 2012, 2013
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: *
52: * @csStr = Input data buffer
53: * @nStrLen = Length of data buffer
54: * @nVer = Version of algorythm; 0 - original, 1 - AITNET variant
55: * return: Hash value
56: */
57: inline u_int
58: hash_varchar(const char *csStr, int nStrLen, int nVer)
59: {
60: register u_int n, hash = 0;
61: register int i;
62:
63: assert(csStr);
64:
65: for (i = 0; i < nStrLen; i++) {
66: n = 2 * hash + csStr[i];
67: if (!nVer) {
68: if (hash & 0x80000000)
69: n ^= POLY_CRC32; /* Polynom CRC-32 aviation */
70: } else {
71: if (n & 1) /* Misho ;) patch for better avalanche!!! */
72: n ^= POLY_CRC32; /* Polynom CRC-32 aviation */
73: }
74: hash = n;
75: }
76:
77: return hash;
78: }
79:
80: /*
81: * hash_bernstein() - Compute index hash by Bernstein
82: *
83: * @csStr = Input data buffer
84: * @nStrLen = Length of data buffer
85: * @nVer = Version of algorythm; 0 - Bernstein, 1 - DJBX33A variant
86: * return: Hash value
87: */
88: inline u_int
89: hash_bernstein(const char *csStr, int nStrLen, int nVer)
90: {
91: register u_int hash = INIT_BERNSTEIN;
92: register int i;
93:
94: assert(csStr);
95:
96: for (i = 0; i < nStrLen; i++)
97: if (!nVer)
98: hash = ((hash << 5) + hash) + csStr[i];
99: else
100: hash = hash * 33 + csStr[i]; /* DJBX33A */
101:
102: return hash;
103: }
104:
105: /*
106: * hash_fnv1() - Compute index hash by FNV-1
107: *
108: * @csStr = Input data buffer
109: * @nStrLen = Length of data buffer
110: * @nVer = Version of algorythm; 0 - FNV-1, 1 - FNV-1a (best avalanche)
111: * return: Hash value
112: */
113: inline u_int
114: hash_fnv1(const char *csStr, int nStrLen, int nVer)
115: {
116: register u_int hash = INIT_FNV1;
117: register int i;
118:
119: assert(csStr);
120:
121: for (i = 0; i < nStrLen; i++)
122: if (!nVer) { /* FNV-1 */
123: hash *= POLY_FNV1;
124: hash ^= csStr[i];
125: } else { /* FNV-1a */
126: hash ^= csStr[i];
127: hash *= POLY_FNV1;
128: }
129:
130: return hash;
131: }
132:
133: /*
134: * hash_jenkins() - Compute index hash by Jenkins (one-at-a-time)
135: *
136: * @csStr = Input data buffer
137: * @nStrLen = Length of data buffer
138: * return: Hash value
139: */
140: inline u_int
141: hash_jenkins(const char *csStr, int nStrLen)
142: {
143: register u_int hash = 0;
144: register int i;
145:
146: assert(csStr);
147:
148: for (i = 0; i < nStrLen; i++) {
149: hash += csStr[i];
150: hash += (hash << 10);
151: hash ^= (hash >> 6);
152: }
153: hash += (hash << 3);
154: hash ^= (hash >> 11);
155: hash += (hash << 15);
156:
157: return hash;
158: }
159:
160: /*
161: * hash_reddragon() - Compute index hash by Red Dragon
162: *
163: * @csStr = Input data buffer
164: * @nStrLen = Length of data buffer
165: * return: Hash value
166: */
167: inline u_int
168: hash_reddragon(const char *csStr, int nStrLen)
169: {
170: register u_int g, hash;
171: register int i;
172:
173: assert(csStr);
174:
175: for (hash = 0, i = 0; i < nStrLen; i++) {
176: hash = (hash << 4) + csStr[i];
177: if ((g = hash & 0xF0000000)) {
178: hash ^= g >> 24;
179: hash ^= g;
180: }
181: }
182:
183: return hash;
184: }
185:
186: /*
187: * hash_jenkins32() - Fast Jenkins hash function
188: *
189: * @buf = Input buffer
190: * @len = Length of buffer
191: * @prevhash = Previous hash, if participate in continuing hash
192: * return: Hash value
193: */
194: u_int
195: hash_jenkins32(const u_int *buf, int len, u_int prevhash)
196: {
197: register u_int a, b, c;
198:
199: assert(buf);
200:
201: a = b = c = INIT_JENKINS32 + (((u_int) len) << 2) + prevhash;
202:
203: while (len > 3) {
204: a += buf[0];
205: b += buf[1];
206: c += buf[2];
207: MIX32(a, b, c);
208: len -= 3;
209: buf += 3;
210: }
211:
212: switch (len) {
213: case 3:
214: c += buf[2];
215: case 2:
216: b += buf[1];
217: case 1:
218: a += buf[0];
219: FINAL32(a, b, c);
220: case 0:
221: break;
222: }
223:
224: return c;
225: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to hash.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / libelwix / src