1 /*-
2  * See the file LICENSE for redistribution information.
3  *
4  * Copyright (c) 1996, 1997
5  *	Sleepycat Software.  All rights reserved.
6  */
7 /*
8  * Copyright (c) 1990, 1993
9  *	Margo Seltzer.  All rights reserved.
10  */
11 /*
12  * Copyright (c) 1990, 1993
13  *	The Regents of the University of California.  All rights reserved.
14  *
15  * This code is derived from software contributed to Berkeley by
16  * Margo Seltzer.
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 the University of
29  *	California, Berkeley and its contributors.
30  * 4. Neither the name of the University 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 THE REGENTS 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 /*
47  * Copyright (c) 1998 by Sun Microsystems, Inc.
48  * All rights reserved.
49  */
50 
51 #include "config.h"
52 
53 #ifndef NO_SYSTEM_INCLUDES
54 #include <sys/types.h>
55 #endif
56 
57 #include "db_int.h"
58 #include "db_page.h"
59 #include "hash.h"
60 
61 /*
62  * __ham_func2 --
63  *	Phong Vo's linear congruential hash.
64  *
65  * PUBLIC: u_int32_t __ham_func2 __P((const void *, u_int32_t));
66  */
67 #define	DCHARHASH(h, c)	((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
68 
69 u_int32_t
70 __ham_func2(key, len)
71 	const void *key;
72 	u_int32_t len;
73 {
74 	const u_int8_t *e, *k;
75 	u_int32_t h;
76 	u_int8_t c;
77 
78 	k = key;
79 	e = k + len;
80 	for (h = 0; k != e;) {
81 		c = *k++;
82 		if (!c && k > e)
83 			break;
84 		DCHARHASH(h, c);
85 	}
86 	return (h);
87 }
88 
89 /*
90  * __ham_func3 --
91  *	Ozan Yigit's original sdbm hash.
92  *
93  * Ugly, but fast.  Break the string up into 8 byte units.  On the first time
94  * through the loop get the "leftover bytes" (strlen % 8).  On every other
95  * iteration, perform 8 HASHC's so we handle all 8 bytes.  Essentially, this
96  * saves us 7 cmp & branch instructions.
97  *
98  * PUBLIC: u_int32_t __ham_func3 __P((const void *, u_int32_t));
99  */
100 u_int32_t
101 __ham_func3(key, len)
102 	const void *key;
103 	u_int32_t len;
104 {
105 	const u_int8_t *k;
106 	u_int32_t n, loop;
107 
108 	if (len == 0)
109 		return (0);
110 
111 #define	HASHC	n = *k++ + 65599 * n
112 	n = 0;
113 	k = key;
114 
115 	loop = (len + 8 - 1) >> 3;
116 	switch (len & (8 - 1)) {
117 	case 0:
118 		do {
119 			HASHC;
120 			/* FALLTHROUGH */
121 	case 7:
122 			HASHC;
123 			/* FALLTHROUGH */
124 	case 6:
125 			HASHC;
126 			/* FALLTHROUGH */
127 	case 5:
128 			HASHC;
129 			/* FALLTHROUGH */
130 	case 4:
131 			HASHC;
132 			/* FALLTHROUGH */
133 	case 3:
134 			HASHC;
135 			/* FALLTHROUGH */
136 	case 2:
137 			HASHC;
138 			/* FALLTHROUGH */
139 	case 1:
140 			HASHC;
141 		} while (--loop);
142 	}
143 	return (n);
144 }
145 
146 /*
147  * __ham_func4 --
148  *	Chris Torek's hash function.  Although this function performs only
149  *	slightly worse than __ham_func5 on strings, it performs horribly on
150  *	numbers.
151  *
152  * PUBLIC: u_int32_t __ham_func4 __P((const void *, u_int32_t));
153  */
154 u_int32_t
155 __ham_func4(key, len)
156 	const void *key;
157 	u_int32_t len;
158 {
159 	const u_int8_t *k;
160 	u_int32_t h, loop;
161 
162 	if (len == 0)
163 		return (0);
164 
165 #define	HASH4a	h = (h << 5) - h + *k++;
166 #define	HASH4b	h = (h << 5) + h + *k++;
167 #define	HASH4	HASH4b
168 	h = 0;
169 	k = key;
170 
171 	loop = (len + 8 - 1) >> 3;
172 	switch (len & (8 - 1)) {
173 	case 0:
174 		do {
175 			HASH4;
176 			/* FALLTHROUGH */
177 	case 7:
178 			HASH4;
179 			/* FALLTHROUGH */
180 	case 6:
181 			HASH4;
182 			/* FALLTHROUGH */
183 	case 5:
184 			HASH4;
185 			/* FALLTHROUGH */
186 	case 4:
187 			HASH4;
188 			/* FALLTHROUGH */
189 	case 3:
190 			HASH4;
191 			/* FALLTHROUGH */
192 	case 2:
193 			HASH4;
194 			/* FALLTHROUGH */
195 	case 1:
196 			HASH4;
197 		} while (--loop);
198 	}
199 	return (h);
200 }
201 
202 /*
203  * Fowler/Noll/Vo hash
204  *
205  * The basis of the hash algorithm was taken from an idea sent by email to the
206  * IEEE Posix P1003.2 mailing list from Phong Vo (kpv@research.att.com) and
207  * Glenn Fowler (gsf@research.att.com).  Landon Curt Noll (chongo@toad.com)
208  * later improved on their algorithm.
209  *
210  * The magic is in the interesting relationship between the special prime
211  * 16777619 (2^24 + 403) and 2^32 and 2^8.
212  *
213  * This hash produces the fewest collisions of any function that we've seen so
214  * far, and works well on both numbers and strings.
215  *
216  * PUBLIC: u_int32_t __ham_func5 __P((const void *, u_int32_t));
217  */
218 u_int32_t
219 __ham_func5(key, len)
220 	const void *key;
221 	u_int32_t len;
222 {
223 	const u_int8_t *k, *e;
224         u_int32_t h;
225 
226 	k = key;
227 	e = k + len;
228         for (h = 0; k < e; ++k) {
229                 h *= 16777619;
230                 h ^= *k;
231         }
232         return (h);
233 }
234