2 * Copyright (C) 2004, 2006 Internet Systems Consortium, Inc. ("ISC")
3 * Copyright (C) 2003 Internet Software Consortium.
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
9 * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
10 * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
11 * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
12 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
13 * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
14 * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
15 * PERFORMANCE OF THIS SOFTWARE.
18 /* $Id: hash.c,v 1.2.2.4.2.3 2006/01/04 00:37:22 marka Exp $ */
21 * Some portion of this code was derived from universal hash function
22 * libraries of Rice University.
25 /* "UH Universal Hashing Library"
27 Copyright ((c)) 2002, Rice University
30 Redistribution and use in source and binary forms, with or without
31 modification, are permitted provided that the following conditions are
34 * Redistributions of source code must retain the above copyright
35 notice, this list of conditions and the following disclaimer.
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.
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.
47 This software is provided by RICE and the contributors on an "as is"
48 basis, without any representations or warranties of any kind, express
49 or implied including, but not limited to, representations or
50 warranties of non-infringement, merchantability or fitness for a
51 particular purpose. In no event shall RICE or contributors be liable
52 for any direct, indirect, incidental, special, exemplary, or
53 consequential damages (including, but not limited to, procurement of
54 substitute goods or services; loss of use, data, or profits; or
55 business interruption) however caused and on any theory of liability,
56 whether in contract, strict liability, or tort (including negligence
57 or otherwise) arising in any way out of the use of this software, even
58 if advised of the possibility of such damage.
63 #include <isc/entropy.h>
66 #include <isc/magic.h>
67 #include <isc/mutex.h>
69 #include <isc/random.h>
70 #include <isc/refcount.h>
71 #include <isc/string.h>
74 #define HASH_MAGIC ISC_MAGIC('H', 'a', 's', 'h')
75 #define VALID_HASH(h) ISC_MAGIC_VALID((h), HASH_MAGIC)
78 * A large 32-bit prime number that specifies the range of the hash output.
80 #define PRIME32 0xFFFFFFFB /* 2^32 - 5 */
83 * Types of random seed and hash accumulator. Perhaps they can be system
86 typedef isc_uint32_t hash_accum_t;
87 typedef isc_uint16_t hash_random_t;
93 isc_boolean_t initialized;
94 isc_refcount_t refcnt;
95 isc_entropy_t *entropy; /* entropy source */
96 unsigned int limit; /* upper limit of key length */
97 size_t vectorlen; /* size of the vector below */
98 hash_random_t *rndvector; /* random vector for universal hashing */
101 static isc_mutex_t createlock;
102 static isc_once_t once = ISC_ONCE_INIT;
103 static isc_hash_t *hash = NULL;
105 static unsigned char maptolower[] = {
106 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
107 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
108 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
109 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
110 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
111 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
112 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
113 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
114 0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
115 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
116 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
117 0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f,
118 0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
119 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
120 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
121 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
122 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
123 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
124 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
125 0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
126 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
127 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
128 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
129 0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
130 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
131 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
132 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
133 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
134 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
135 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
136 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
137 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff
141 isc_hash_ctxcreate(isc_mem_t *mctx, isc_entropy_t *entropy,
142 unsigned int limit, isc_hash_t **hctxp)
148 hash_accum_t overflow_limit;
150 REQUIRE(mctx != NULL);
151 REQUIRE(hctxp != NULL && *hctxp == NULL);
154 * Overflow check. Since our implementation only does a modulo
155 * operation at the last stage of hash calculation, the accumulator
159 1 << (((sizeof(hash_accum_t) - sizeof(hash_random_t))) * 8);
160 if (overflow_limit < (limit + 1) * 0xff)
161 return (ISC_R_RANGE);
163 hctx = isc_mem_get(mctx, sizeof(isc_hash_t));
165 return (ISC_R_NOMEMORY);
167 vlen = sizeof(hash_random_t) * (limit + 1);
168 rv = isc_mem_get(mctx, vlen);
170 ret = ISC_R_NOMEMORY;
177 if (isc_mutex_init(&hctx->lock) != ISC_R_SUCCESS) {
178 ret = ISC_R_UNEXPECTED;
183 * From here down, no failures will/can occur.
185 hctx->magic = HASH_MAGIC;
187 isc_mem_attach(mctx, &hctx->mctx);
188 hctx->initialized = ISC_FALSE;
189 isc_refcount_init(&hctx->refcnt, 1);
190 hctx->entropy = NULL;
192 hctx->vectorlen = vlen;
193 hctx->rndvector = rv;
196 isc_entropy_attach(entropy, &hctx->entropy);
199 return (ISC_R_SUCCESS);
202 isc_mem_put(mctx, hctx, sizeof(isc_hash_t));
204 isc_mem_put(mctx, rv, vlen);
210 initialize_lock(void) {
211 RUNTIME_CHECK(isc_mutex_init(&createlock) == ISC_R_SUCCESS);
215 isc_hash_create(isc_mem_t *mctx, isc_entropy_t *entropy, size_t limit) {
216 isc_result_t result = ISC_R_SUCCESS;
218 REQUIRE(mctx != NULL);
219 INSIST(hash == NULL);
221 RUNTIME_CHECK(isc_once_do(&once, initialize_lock) == ISC_R_SUCCESS);
226 result = isc_hash_ctxcreate(mctx, entropy, limit, &hash);
234 isc_hash_ctxinit(isc_hash_t *hctx) {
239 if (hctx->initialized == ISC_TRUE)
243 result = isc_entropy_getdata(hctx->entropy,
244 hctx->rndvector, hctx->vectorlen,
246 INSIST(result == ISC_R_SUCCESS);
249 unsigned int i, copylen;
252 p = (unsigned char *)hctx->rndvector;
253 for (i = 0; i < hctx->vectorlen; i += copylen, p += copylen) {
255 if (i + sizeof(pr) <= hctx->vectorlen)
256 copylen = sizeof(pr);
258 copylen = hctx->vectorlen - i;
260 memcpy(p, &pr, copylen);
262 INSIST(p == (unsigned char *)hctx->rndvector +
266 hctx->initialized = ISC_TRUE;
274 INSIST(hash != NULL && VALID_HASH(hash));
276 isc_hash_ctxinit(hash);
280 isc_hash_ctxattach(isc_hash_t *hctx, isc_hash_t **hctxp) {
281 REQUIRE(VALID_HASH(hctx));
282 REQUIRE(hctxp != NULL && *hctxp == NULL);
284 isc_refcount_increment(&hctx->refcnt, NULL);
289 destroy(isc_hash_t **hctxp) {
293 REQUIRE(hctxp != NULL && *hctxp != NULL);
299 isc_refcount_destroy(&hctx->refcnt);
302 if (hctx->entropy != NULL)
303 isc_entropy_detach(&hctx->entropy);
304 if (hctx->rndvector != NULL)
305 isc_mem_put(mctx, hctx->rndvector, hctx->vectorlen);
309 DESTROYLOCK(&hctx->lock);
311 memset(hctx, 0, sizeof(isc_hash_t));
312 isc_mem_put(mctx, hctx, sizeof(isc_hash_t));
313 isc_mem_detach(&mctx);
317 isc_hash_ctxdetach(isc_hash_t **hctxp) {
321 REQUIRE(hctxp != NULL && VALID_HASH(*hctxp));
324 isc_refcount_decrement(&hctx->refcnt, &refs);
335 INSIST(hash != NULL && VALID_HASH(hash));
337 isc_refcount_decrement(&hash->refcnt, &refs);
343 static inline unsigned int
344 hash_calc(isc_hash_t *hctx, const unsigned char *key, unsigned int keylen,
345 isc_boolean_t case_sensitive)
347 hash_accum_t partial_sum = 0;
348 hash_random_t *p = hctx->rndvector;
351 /* Make it sure that the hash context is initialized. */
352 if (hctx->initialized == ISC_FALSE)
353 isc_hash_ctxinit(hctx);
355 if (case_sensitive) {
356 for (i = 0; i < keylen; i++)
357 partial_sum += key[i] * (hash_accum_t)p[i];
359 for (i = 0; i < keylen; i++)
360 partial_sum += maptolower[key[i]] * (hash_accum_t)p[i];
365 return ((unsigned int)(partial_sum % PRIME32));
369 isc_hash_ctxcalc(isc_hash_t *hctx, const unsigned char *key,
370 unsigned int keylen, isc_boolean_t case_sensitive)
372 REQUIRE(hctx != NULL && VALID_HASH(hctx));
373 REQUIRE(keylen <= hctx->limit);
375 return (hash_calc(hctx, key, keylen, case_sensitive));
379 isc_hash_calc(const unsigned char *key, unsigned int keylen,
380 isc_boolean_t case_sensitive)
382 INSIST(hash != NULL && VALID_HASH(hash));
383 REQUIRE(keylen <= hash->limit);
385 return (hash_calc(hash, key, keylen, case_sensitive));