hash.c revision 7a272c6b0de3b8c0ad018b9896e287da19c43bef
7a272c6b0de3b8c0ad018b9896e287da19c43befAutomatic Updater * Copyright (C) 2004-2007, 2009 Internet Systems Consortium, Inc. ("ISC")
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * Copyright (C) 2003 Internet Software Consortium.
ec5347e2c775f027573ce5648b910361aa926c01Automatic Updater * Permission to use, copy, modify, and/or distribute this software for any
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * purpose with or without fee is hereby granted, provided that the above
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * copyright notice and this permission notice appear in all copies.
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * THE SOFTWARE IS PROVIDED "AS IS" AND ISC DISCLAIMS ALL WARRANTIES WITH
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * AND FITNESS. IN NO EVENT SHALL ISC BE LIABLE FOR ANY SPECIAL, DIRECT,
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
dafcb997e390efa4423883dafd100c975c4095d6Mark Andrews * PERFORMANCE OF THIS SOFTWARE.
7a272c6b0de3b8c0ad018b9896e287da19c43befAutomatic Updater/* $Id: hash.c,v 1.15 2009/05/06 23:47:50 tbox Exp $ */
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * Some portion of this code was derived from universal hash function
7a272c6b0de3b8c0ad018b9896e287da19c43befAutomatic Updater * libraries of Rice University.
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein\section license UH Universal Hashing Library
1e107b3d7b54de5022c3328423164e533afcc15eMark AndrewsCopyright ((c)) 2002, Rice University
1e107b3d7b54de5022c3328423164e533afcc15eMark AndrewsAll rights reserved.
1e107b3d7b54de5022c3328423164e533afcc15eMark AndrewsRedistribution and use in source and binary forms, with or without
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsmodification, are permitted provided that the following conditions are
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * Redistributions of source code must retain the above copyright
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews notice, this list of conditions and the following disclaimer.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * Redistributions in binary form must reproduce the above
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews copyright notice, this list of conditions and the following
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews disclaimer in the documentation and/or other materials provided
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews with the distribution.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * Neither the name of Rice University (RICE) nor the names of its
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews contributors may be used to endorse or promote products derived
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews from this software without specific prior written permission.
1e107b3d7b54de5022c3328423164e533afcc15eMark AndrewsThis software is provided by RICE and the contributors on an "as is"
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsbasis, without any representations or warranties of any kind, express
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsor implied including, but not limited to, representations or
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewswarranties of non-infringement, merchantability or fitness for a
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsparticular purpose. In no event shall RICE or contributors be liable
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsfor any direct, indirect, incidental, special, exemplary, or
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsconsequential damages (including, but not limited to, procurement of
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewssubstitute goods or services; loss of use, data, or profits; or
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsbusiness interruption) however caused and on any theory of liability,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewswhether in contract, strict liability, or tort (including negligence
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsor otherwise) arising in any way out of the use of this software, even
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsif advised of the possibility of such damage.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews#define HASH_MAGIC ISC_MAGIC('H', 'a', 's', 'h')
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews#define VALID_HASH(h) ISC_MAGIC_VALID((h), HASH_MAGIC)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * A large 32-bit prime number that specifies the range of the hash output.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * Types of random seed and hash accumulator. Perhaps they can be system
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * dependent.
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein/*% isc hash structure */
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews unsigned int magic;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein unsigned int limit; /*%< upper limit of key length */
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein size_t vectorlen; /*%< size of the vector below */
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein hash_random_t *rndvector; /*%< random vector for universal hashing */
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsstatic unsigned char maptolower[] = {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x20, 0x21, 0x22, 0x23, 0x24, 0x25, 0x26, 0x27,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x28, 0x29, 0x2a, 0x2b, 0x2c, 0x2d, 0x2e, 0x2f,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x30, 0x31, 0x32, 0x33, 0x34, 0x35, 0x36, 0x37,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x38, 0x39, 0x3a, 0x3b, 0x3c, 0x3d, 0x3e, 0x3f,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x40, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x78, 0x79, 0x7a, 0x5b, 0x5c, 0x5d, 0x5e, 0x5f,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x60, 0x61, 0x62, 0x63, 0x64, 0x65, 0x66, 0x67,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x68, 0x69, 0x6a, 0x6b, 0x6c, 0x6d, 0x6e, 0x6f,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x70, 0x71, 0x72, 0x73, 0x74, 0x75, 0x76, 0x77,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x78, 0x79, 0x7a, 0x7b, 0x7c, 0x7d, 0x7e, 0x7f,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x80, 0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x88, 0x89, 0x8a, 0x8b, 0x8c, 0x8d, 0x8e, 0x8f,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x90, 0x91, 0x92, 0x93, 0x94, 0x95, 0x96, 0x97,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0x98, 0x99, 0x9a, 0x9b, 0x9c, 0x9d, 0x9e, 0x9f,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0xa0, 0xa1, 0xa2, 0xa3, 0xa4, 0xa5, 0xa6, 0xa7,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0xa8, 0xa9, 0xaa, 0xab, 0xac, 0xad, 0xae, 0xaf,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0xb0, 0xb1, 0xb2, 0xb3, 0xb4, 0xb5, 0xb6, 0xb7,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0xb8, 0xb9, 0xba, 0xbb, 0xbc, 0xbd, 0xbe, 0xbf,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0xc0, 0xc1, 0xc2, 0xc3, 0xc4, 0xc5, 0xc6, 0xc7,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0xc8, 0xc9, 0xca, 0xcb, 0xcc, 0xcd, 0xce, 0xcf,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0xd0, 0xd1, 0xd2, 0xd3, 0xd4, 0xd5, 0xd6, 0xd7,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0xd8, 0xd9, 0xda, 0xdb, 0xdc, 0xdd, 0xde, 0xdf,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0xe0, 0xe1, 0xe2, 0xe3, 0xe4, 0xe5, 0xe6, 0xe7,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0xe8, 0xe9, 0xea, 0xeb, 0xec, 0xed, 0xee, 0xef,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 0xf0, 0xf1, 0xf2, 0xf3, 0xf4, 0xf5, 0xf6, 0xf7,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_hash_ctxcreate(isc_mem_t *mctx, isc_entropy_t *entropy,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * Overflow check. Since our implementation only does a modulo
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * operation at the last stage of hash calculation, the accumulator
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * must not overflow.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 1 << (((sizeof(hash_accum_t) - sizeof(hash_random_t))) * 8);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * We need a lock.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * From here down, no failures will/can occur.
be2c2c29a88db96bd51f11d671ec207f0b6b0d45Mark Andrews RUNTIME_CHECK(isc_mutex_init(&createlock) == ISC_R_SUCCESS);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_hash_create(isc_mem_t *mctx, isc_entropy_t *entropy, size_t limit) {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews RUNTIME_CHECK(isc_once_do(&once, initialize_lock) == ISC_R_SUCCESS);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews result = isc_hash_ctxcreate(mctx, entropy, limit, &hash);
7a272c6b0de3b8c0ad018b9896e287da19c43befAutomatic Updater result = isc_entropy_getdata(hctx->entropy,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews unsigned int i, copylen;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews unsigned char *p;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews for (i = 0; i < hctx->vectorlen; i += copylen, p += copylen) {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_hash_ctxattach(isc_hash_t *hctx, isc_hash_t **hctxp) {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_mem_put(mctx, hctx->rndvector, hctx->vectorlen);
5d7849ad7ffc6d08870dbfbc8d6bfffd90007488Tatuya JINMEI 神明達哉 memcpy(canary0, hctx + 1, sizeof(canary0));
5d7849ad7ffc6d08870dbfbc8d6bfffd90007488Tatuya JINMEI 神明達哉 memcpy(canary1, hctx + 1, sizeof(canary1));
5d7849ad7ffc6d08870dbfbc8d6bfffd90007488Tatuya JINMEI 神明達哉 INSIST(memcmp(canary0, canary1, sizeof(canary0)) == 0);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews unsigned int refs;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews unsigned int refs;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsstatic inline unsigned int
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewshash_calc(isc_hash_t *hctx, const unsigned char *key, unsigned int keylen,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews unsigned int i = 0;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews /* Make it sure that the hash context is initialized. */
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews for (i = 0; i < keylen; i++)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews for (i = 0; i < keylen; i++)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews partial_sum += maptolower[key[i]] * (hash_accum_t)p[i];
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews return ((unsigned int)(partial_sum % PRIME32));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_hash_ctxcalc(isc_hash_t *hctx, const unsigned char *key,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews unsigned int keylen, isc_boolean_t case_sensitive)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews return (hash_calc(hctx, key, keylen, case_sensitive));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_hash_calc(const unsigned char *key, unsigned int keylen,