a1cf2291a974b55e9ba6aaa6fa97c1caf5367903Tinderbox User * Copyright (C) 2003-2007, 2009, 2013-2017 Internet Systems Consortium, Inc. ("ISC")
0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark Andrews * This Source Code Form is subject to the terms of the Mozilla Public
0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark Andrews * License, v. 2.0. If a copy of the MPL was not distributed with this
0c27b3fe77ac1d5094ba3521e8142d9e7973133fMark Andrews * file, You can obtain one at http://mozilla.org/MPL/2.0/.
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 */
c3c8823fed039b3a2b8e5ca8bc2f3301d1dd840eMark Andrews size_t 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 */
a00f9e2f50675bd43cc6a9fe2669709162a2ccb4Evan HuntLIBISC_EXTERNAL_DATA isc_hash_t *isc_hashctx = NULL;
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);
7a272c6b0de3b8c0ad018b9896e287da19c43befAutomatic Updater result = isc_entropy_getdata(hctx->entropy,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews unsigned char *p;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews for (i = 0; i < hctx->vectorlen; i += copylen, p += copylen) {
a00f9e2f50675bd43cc6a9fe2669709162a2ccb4Evan Hunt INSIST(isc_hashctx != NULL && VALID_HASH(isc_hashctx));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_hash_ctxattach(isc_hash_t *hctx, isc_hash_t **hctxp) {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_mem_put(mctx, hctx->rndvector, hctx->vectorlen);
a00f9e2f50675bd43cc6a9fe2669709162a2ccb4Evan Hunt INSIST(isc_hashctx != NULL && VALID_HASH(isc_hashctx));
a00f9e2f50675bd43cc6a9fe2669709162a2ccb4Evan Hunt isc_refcount_decrement(&isc_hashctx->refcnt, &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,
a00f9e2f50675bd43cc6a9fe2669709162a2ccb4Evan Hunt INSIST(isc_hashctx != NULL && VALID_HASH(isc_hashctx));
a00f9e2f50675bd43cc6a9fe2669709162a2ccb4Evan Hunt return (hash_calc(isc_hashctx, key, keylen, case_sensitive));
ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman for (i = 0; i < 256; i++) {
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaramanstatic isc_boolean_t fnv_initialized = ISC_FALSE;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman * This function should not leave fnv_offset_basis set to
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman * 0. Also, after this function has been called, if it is called
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman * again, it should not change fnv_offset_basis.
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman RUNTIME_CHECK(isc_once_do(&fnv_once, fnv_initialize) == ISC_R_SUCCESS);
93c211afc97e7a072c12ef346581065e4065ff15Evan Huntisc_hash_set_initializer(const void *initializer) {
93c211afc97e7a072c12ef346581065e4065ff15Evan Hunt * Ensure that fnv_initialize() is not called after
93c211afc97e7a072c12ef346581065e4065ff15Evan Hunt * isc_hash_set_initializer() is called.
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman RUNTIME_CHECK(isc_once_do(&fnv_once, fnv_initialize) == ISC_R_SUCCESS);
93c211afc97e7a072c12ef346581065e4065ff15Evan Hunt fnv_offset_basis = *((const unsigned int *) initializer);
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaramanisc_hash_function(const void *data, size_t length,
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman RUNTIME_CHECK(isc_once_do(&fnv_once, fnv_initialize) == ISC_R_SUCCESS);
9da98335c185c39591150ccb4e307adc4cea44bcMukund Sivaraman hval = ISC_UNLIKELY(previous_hashp != NULL) ?
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman * Fowler-Noll-Vo FNV-1a hash function.
93c211afc97e7a072c12ef346581065e4065ff15Evan Hunt * NOTE: A random FNV offset basis is used by default to avoid
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman * collision attacks as the hash function is reversible. This
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman * makes the mapping non-deterministic, but the distribution in
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman * the domain is still uniform.
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaramanisc_hash_function_reverse(const void *data, size_t length,
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman RUNTIME_CHECK(isc_once_do(&fnv_once, fnv_initialize) == ISC_R_SUCCESS);
9da98335c185c39591150ccb4e307adc4cea44bcMukund Sivaraman hval = ISC_UNLIKELY(previous_hashp != NULL) ?
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman * Fowler-Noll-Vo FNV-1a hash function.
93c211afc97e7a072c12ef346581065e4065ff15Evan Hunt * NOTE: A random FNV offset basis is used by default to avoid
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman * collision attacks as the hash function is reversible. This
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman * makes the mapping non-deterministic, but the distribution in
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman * the domain is still uniform.