1/*	$NetBSD: hash_func.c,v 1.12 2008/08/26 21:18:38 joerg Exp $	*/
2
3/*-
4 * Copyright (c) 1990, 1993
5 *	The Regents of the University of California.  All rights reserved.
6 *
7 * This code is derived from software contributed to Berkeley by
8 * Margo Seltzer.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 *    notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 *    notice, this list of conditions and the following disclaimer in the
17 *    documentation and/or other materials provided with the distribution.
18 * 3. Neither the name of the University nor the names of its contributors
19 *    may be used to endorse or promote products derived from this software
20 *    without specific prior written permission.
21 *
22 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
23 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
26 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
27 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
28 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
29 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
31 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
32 * SUCH DAMAGE.
33 */
34
35#if HAVE_NBTOOL_CONFIG_H
36#include "nbtool_config.h"
37#endif
38
39#include <sys/cdefs.h>
40__RCSID("$NetBSD: hash_func.c,v 1.12 2008/08/26 21:18:38 joerg Exp $");
41
42#include <sys/types.h>
43
44#include <db.h>
45#include "hash.h"
46#include "page.h"
47#include "extern.h"
48
49#if 0
50static uint32_t hash1(const void *, size_t) __attribute__((__unused__));
51static uint32_t hash2(const void *, size_t) __attribute__((__unused__));
52static uint32_t hash3(const void *, size_t) __attribute__((__unused__));
53#endif
54static uint32_t hash4(const void *, size_t) __attribute__((__unused__));
55
56/* Global default hash function */
57uint32_t (*__default_hash)(const void *, size_t) = hash4;
58#if 0
59/*
60 * HASH FUNCTIONS
61 *
62 * Assume that we've already split the bucket to which this key hashes,
63 * calculate that bucket, and check that in fact we did already split it.
64 *
65 * This came from ejb's hsearch.
66 */
67
68#define PRIME1		37
69#define PRIME2		1048583
70
71static uint32_t
72hash1(const void *keyarg, size_t len)
73{
74	const uint8_t *key;
75	uint32_t h;
76
77	/* Convert string to integer */
78	for (key = keyarg, h = 0; len--;)
79		h = h * PRIME1 ^ (*key++ - ' ');
80	h %= PRIME2;
81	return (h);
82}
83
84/*
85 * Phong's linear congruential hash
86 */
87#define dcharhash(h, c)	((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
88
89static uint32_t
90hash2(const void *keyarg, size_t len)
91{
92	const uint8_t *e, *key;
93	uint32_t h;
94	uint8_t c;
95
96	key = keyarg;
97	e = key + len;
98	for (h = 0; key != e;) {
99		c = *key++;
100		if (!c && key > e)
101			break;
102		dcharhash(h, c);
103	}
104	return (h);
105}
106
107/*
108 * This is INCREDIBLY ugly, but fast.  We break the string up into 8 byte
109 * units.  On the first time through the loop we get the "leftover bytes"
110 * (strlen % 8).  On every other iteration, we perform 8 HASHC's so we handle
111 * all 8 bytes.  Essentially, this saves us 7 cmp & branch instructions.  If
112 * this routine is heavily used enough, it's worth the ugly coding.
113 *
114 * OZ's original sdbm hash
115 */
116static uint32_t
117hash3(const void *keyarg, size_t len)
118{
119	const uint8_t *key;
120	size_t loop;
121	uint32_t h;
122
123#define HASHC   h = *key++ + 65599 * h
124
125	h = 0;
126	key = keyarg;
127	if (len > 0) {
128		loop = (len + 8 - 1) >> 3;
129
130		switch (len & (8 - 1)) {
131		case 0:
132			do {
133				HASHC;
134				/* FALLTHROUGH */
135		case 7:
136				HASHC;
137				/* FALLTHROUGH */
138		case 6:
139				HASHC;
140				/* FALLTHROUGH */
141		case 5:
142				HASHC;
143				/* FALLTHROUGH */
144		case 4:
145				HASHC;
146				/* FALLTHROUGH */
147		case 3:
148				HASHC;
149				/* FALLTHROUGH */
150		case 2:
151				HASHC;
152				/* FALLTHROUGH */
153		case 1:
154				HASHC;
155			} while (--loop);
156		}
157	}
158	return (h);
159}
160#endif
161
162/* Hash function from Chris Torek. */
163static uint32_t
164hash4(const void *keyarg, size_t len)
165{
166	const uint8_t *key;
167	size_t loop;
168	uint32_t h;
169
170#define HASH4a   h = (h << 5) - h + *key++;
171#define HASH4b   h = (h << 5) + h + *key++;
172#define HASH4 HASH4b
173
174	h = 0;
175	key = keyarg;
176	if (len > 0) {
177		loop = (len + 8 - 1) >> 3;
178
179		switch (len & (8 - 1)) {
180		case 0:
181			do {
182				HASH4;
183				/* FALLTHROUGH */
184		case 7:
185				HASH4;
186				/* FALLTHROUGH */
187		case 6:
188				HASH4;
189				/* FALLTHROUGH */
190		case 5:
191				HASH4;
192				/* FALLTHROUGH */
193		case 4:
194				HASH4;
195				/* FALLTHROUGH */
196		case 3:
197				HASH4;
198				/* FALLTHROUGH */
199		case 2:
200				HASH4;
201				/* FALLTHROUGH */
202		case 1:
203				HASH4;
204			} while (--loop);
205		}
206	}
207	return (h);
208}
209