1/*	$NetBSD: hash.c,v 1.1.1.1 2009/12/13 16:54:14 kardel Exp $	*/
2
3/*
4 * Copyright (C) 2004-2007, 2009  Internet Systems Consortium, Inc. ("ISC")
5 * Copyright (C) 2003  Internet Software Consortium.
6 *
7 * Permission to use, copy, modify, and/or distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
10 *
11 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
12 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
13 * AND FITNESS.  IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
14 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
15 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
16 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
17 * PERFORMANCE OF THIS SOFTWARE.
18 */
19
20/* Id: hash.c,v 1.13.332.3 2009/05/07 23:47:12 tbox Exp */
21
22/*! \file
23 * Some portion of this code was derived from universal hash function
24 * libraries of Rice University.
25\section license UH Universal Hashing Library
26
27Copyright ((c)) 2002, Rice University
28All rights reserved.
29
30Redistribution and use in source and binary forms, with or without
31modification, are permitted provided that the following conditions are
32met:
33
34    * Redistributions of source code must retain the above copyright
35    notice, this list of conditions and the following disclaimer.
36
37    * Redistributions in binary form must reproduce the above
38    copyright notice, this list of conditions and the following
39    disclaimer in the documentation and/or other materials provided
40    with the distribution.
41
42    * Neither the name of Rice University (RICE) nor the names of its
43    contributors may be used to endorse or promote products derived
44    from this software without specific prior written permission.
45
46
47This software is provided by RICE and the contributors on an "as is"
48basis, without any representations or warranties of any kind, express
49or implied including, but not limited to, representations or
50warranties of non-infringement, merchantability or fitness for a
51particular purpose. In no event shall RICE or contributors be liable
52for any direct, indirect, incidental, special, exemplary, or
53consequential damages (including, but not limited to, procurement of
54substitute goods or services; loss of use, data, or profits; or
55business interruption) however caused and on any theory of liability,
56whether in contract, strict liability, or tort (including negligence
57or otherwise) arising in any way out of the use of this software, even
58if advised of the possibility of such damage.
59*/
60
61#include <config.h>
62
63#include <isc/entropy.h>
64#include <isc/hash.h>
65#include <isc/mem.h>
66#include <isc/magic.h>
67#include <isc/mutex.h>
68#include <isc/once.h>
69#include <isc/random.h>
70#include <isc/refcount.h>
71#include <isc/string.h>
72#include <isc/util.h>
73
74#define HASH_MAGIC		ISC_MAGIC('H', 'a', 's', 'h')
75#define VALID_HASH(h)		ISC_MAGIC_VALID((h), HASH_MAGIC)
76
77/*%
78 * A large 32-bit prime number that specifies the range of the hash output.
79 */
80#define PRIME32 0xFFFFFFFB              /* 2^32 -  5 */
81
82/*@{*/
83/*%
84 * Types of random seed and hash accumulator.  Perhaps they can be system
85 * dependent.
86 */
87typedef isc_uint32_t hash_accum_t;
88typedef isc_uint16_t hash_random_t;
89/*@}*/
90
91/*% isc hash structure */
92struct isc_hash {
93	unsigned int	magic;
94	isc_mem_t	*mctx;
95	isc_mutex_t	lock;
96	isc_boolean_t	initialized;
97	isc_refcount_t	refcnt;
98	isc_entropy_t	*entropy; /*%< entropy source */
99	unsigned int	limit;	/*%< upper limit of key length */
100	size_t		vectorlen; /*%< size of the vector below */
101	hash_random_t	*rndvector; /*%< random vector for universal hashing */
102};
103
104static isc_mutex_t createlock;
105static isc_once_t once = ISC_ONCE_INIT;
106static isc_hash_t *hash = NULL;
107
108static unsigned char maptolower[] = {
109	0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
110	0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
111	0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
112	0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
113	0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
114	0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
115	0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
116	0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
117	0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
118	0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
119	0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
120	0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f,
121	0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
122	0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
123	0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
124	0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
125	0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
126	0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
127	0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
128	0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
129	0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
130	0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
131	0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
132	0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
133	0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
134	0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
135	0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
136	0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
137	0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
138	0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
139	0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
140	0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff
141};
142
143isc_result_t
144isc_hash_ctxcreate(isc_mem_t *mctx, isc_entropy_t *entropy,
145		   unsigned int limit, isc_hash_t **hctxp)
146{
147	isc_result_t result;
148	isc_hash_t *hctx;
149	size_t vlen;
150	hash_random_t *rv;
151	hash_accum_t overflow_limit;
152
153	REQUIRE(mctx != NULL);
154	REQUIRE(hctxp != NULL && *hctxp == NULL);
155
156	/*
157	 * Overflow check.  Since our implementation only does a modulo
158	 * operation at the last stage of hash calculation, the accumulator
159	 * must not overflow.
160	 */
161	overflow_limit =
162		1 << (((sizeof(hash_accum_t) - sizeof(hash_random_t))) * 8);
163	if (overflow_limit < (limit + 1) * 0xff)
164		return (ISC_R_RANGE);
165
166	hctx = isc_mem_get(mctx, sizeof(isc_hash_t));
167	if (hctx == NULL)
168		return (ISC_R_NOMEMORY);
169
170	vlen = sizeof(hash_random_t) * (limit + 1);
171	rv = isc_mem_get(mctx, vlen);
172	if (rv == NULL) {
173		result = ISC_R_NOMEMORY;
174		goto errout;
175	}
176
177	/*
178	 * We need a lock.
179	 */
180	result = isc_mutex_init(&hctx->lock);
181	if (result != ISC_R_SUCCESS)
182		goto errout;
183
184	/*
185	 * From here down, no failures will/can occur.
186	 */
187	hctx->magic = HASH_MAGIC;
188	hctx->mctx = NULL;
189	isc_mem_attach(mctx, &hctx->mctx);
190	hctx->initialized = ISC_FALSE;
191	result = isc_refcount_init(&hctx->refcnt, 1);
192	if (result != ISC_R_SUCCESS)
193		goto cleanup_lock;
194	hctx->entropy = NULL;
195	hctx->limit = limit;
196	hctx->vectorlen = vlen;
197	hctx->rndvector = rv;
198
199	if (entropy != NULL)
200		isc_entropy_attach(entropy, &hctx->entropy);
201
202	*hctxp = hctx;
203	return (ISC_R_SUCCESS);
204
205 cleanup_lock:
206	DESTROYLOCK(&hctx->lock);
207 errout:
208	isc_mem_put(mctx, hctx, sizeof(isc_hash_t));
209	if (rv != NULL)
210		isc_mem_put(mctx, rv, vlen);
211
212	return (result);
213}
214
215static void
216initialize_lock(void) {
217	RUNTIME_CHECK(isc_mutex_init(&createlock) == ISC_R_SUCCESS);
218}
219
220isc_result_t
221isc_hash_create(isc_mem_t *mctx, isc_entropy_t *entropy, size_t limit) {
222	isc_result_t result = ISC_R_SUCCESS;
223
224	REQUIRE(mctx != NULL);
225	INSIST(hash == NULL);
226
227	RUNTIME_CHECK(isc_once_do(&once, initialize_lock) == ISC_R_SUCCESS);
228
229	LOCK(&createlock);
230
231	if (hash == NULL)
232		result = isc_hash_ctxcreate(mctx, entropy, limit, &hash);
233
234	UNLOCK(&createlock);
235
236	return (result);
237}
238
239void
240isc_hash_ctxinit(isc_hash_t *hctx) {
241	isc_result_t result;
242
243	LOCK(&hctx->lock);
244
245	if (hctx->initialized == ISC_TRUE)
246		goto out;
247
248	if (hctx->entropy) {
249		result = isc_entropy_getdata(hctx->entropy,
250					     hctx->rndvector, hctx->vectorlen,
251					     NULL, 0);
252		INSIST(result == ISC_R_SUCCESS);
253	} else {
254		isc_uint32_t pr;
255		unsigned int i, copylen;
256		unsigned char *p;
257
258		p = (unsigned char *)hctx->rndvector;
259		for (i = 0; i < hctx->vectorlen; i += copylen, p += copylen) {
260			isc_random_get(&pr);
261			if (i + sizeof(pr) <= hctx->vectorlen)
262				copylen = sizeof(pr);
263			else
264				copylen = hctx->vectorlen - i;
265
266			memcpy(p, &pr, copylen);
267		}
268		INSIST(p == (unsigned char *)hctx->rndvector +
269		       hctx->vectorlen);
270	}
271
272	hctx->initialized = ISC_TRUE;
273
274 out:
275	UNLOCK(&hctx->lock);
276}
277
278void
279isc_hash_init() {
280	INSIST(hash != NULL && VALID_HASH(hash));
281
282	isc_hash_ctxinit(hash);
283}
284
285void
286isc_hash_ctxattach(isc_hash_t *hctx, isc_hash_t **hctxp) {
287	REQUIRE(VALID_HASH(hctx));
288	REQUIRE(hctxp != NULL && *hctxp == NULL);
289
290	isc_refcount_increment(&hctx->refcnt, NULL);
291	*hctxp = hctx;
292}
293
294static void
295destroy(isc_hash_t **hctxp) {
296	isc_hash_t *hctx;
297	isc_mem_t *mctx;
298
299	REQUIRE(hctxp != NULL && *hctxp != NULL);
300	hctx = *hctxp;
301	*hctxp = NULL;
302
303	LOCK(&hctx->lock);
304
305	isc_refcount_destroy(&hctx->refcnt);
306
307	mctx = hctx->mctx;
308	if (hctx->entropy != NULL)
309		isc_entropy_detach(&hctx->entropy);
310	if (hctx->rndvector != NULL)
311		isc_mem_put(mctx, hctx->rndvector, hctx->vectorlen);
312
313	UNLOCK(&hctx->lock);
314
315	DESTROYLOCK(&hctx->lock);
316
317	memset(hctx, 0, sizeof(isc_hash_t));
318	isc_mem_put(mctx, hctx, sizeof(isc_hash_t));
319	isc_mem_detach(&mctx);
320}
321
322void
323isc_hash_ctxdetach(isc_hash_t **hctxp) {
324	isc_hash_t *hctx;
325	unsigned int refs;
326
327	REQUIRE(hctxp != NULL && VALID_HASH(*hctxp));
328	hctx = *hctxp;
329
330	isc_refcount_decrement(&hctx->refcnt, &refs);
331	if (refs == 0)
332		destroy(&hctx);
333
334	*hctxp = NULL;
335}
336
337void
338isc_hash_destroy() {
339	unsigned int refs;
340
341	INSIST(hash != NULL && VALID_HASH(hash));
342
343	isc_refcount_decrement(&hash->refcnt, &refs);
344	INSIST(refs == 0);
345
346	destroy(&hash);
347}
348
349static inline unsigned int
350hash_calc(isc_hash_t *hctx, const unsigned char *key, unsigned int keylen,
351	  isc_boolean_t case_sensitive)
352{
353	hash_accum_t partial_sum = 0;
354	hash_random_t *p = hctx->rndvector;
355	unsigned int i = 0;
356
357	/* Make it sure that the hash context is initialized. */
358	if (hctx->initialized == ISC_FALSE)
359		isc_hash_ctxinit(hctx);
360
361	if (case_sensitive) {
362		for (i = 0; i < keylen; i++)
363			partial_sum += key[i] * (hash_accum_t)p[i];
364	} else {
365		for (i = 0; i < keylen; i++)
366			partial_sum += maptolower[key[i]] * (hash_accum_t)p[i];
367	}
368
369	partial_sum += p[i];
370
371	return ((unsigned int)(partial_sum % PRIME32));
372}
373
374unsigned int
375isc_hash_ctxcalc(isc_hash_t *hctx, const unsigned char *key,
376		 unsigned int keylen, isc_boolean_t case_sensitive)
377{
378	REQUIRE(hctx != NULL && VALID_HASH(hctx));
379	REQUIRE(keylen <= hctx->limit);
380
381	return (hash_calc(hctx, key, keylen, case_sensitive));
382}
383
384unsigned int
385isc_hash_calc(const unsigned char *key, unsigned int keylen,
386	      isc_boolean_t case_sensitive)
387{
388	INSIST(hash != NULL && VALID_HASH(hash));
389	REQUIRE(keylen <= hash->limit);
390
391	return (hash_calc(hash, key, keylen, case_sensitive));
392}
393