1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews/*
a1cf2291a974b55e9ba6aaa6fa97c1caf5367903Tinderbox User * Copyright (C) 2003-2007, 2009, 2013-2017 Internet Systems Consortium, Inc. ("ISC")
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews *
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 */
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein/*! \file
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 Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark AndrewsCopyright ((c)) 2002, Rice University
1e107b3d7b54de5022c3328423164e533afcc15eMark AndrewsAll rights reserved.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark AndrewsRedistribution and use in source and binary forms, with or without
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsmodification, are permitted provided that the following conditions are
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsmet:
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * Redistributions of source code must retain the above copyright
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews notice, this list of conditions and the following disclaimer.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
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
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 Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
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*/
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
a8f061d5c61bbdbe922cbb0adb70ae81770b52cbMark Andrews#include <config.h>
a8f061d5c61bbdbe922cbb0adb70ae81770b52cbMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews#include <isc/entropy.h>
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews#include <isc/hash.h>
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews#include <isc/mem.h>
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews#include <isc/magic.h>
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews#include <isc/mutex.h>
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews#include <isc/once.h>
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews#include <isc/random.h>
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews#include <isc/refcount.h>
d19fc9d988171a1a7ff87d200b86c9aa657aa3beMark Andrews#include <isc/string.h>
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews#include <isc/util.h>
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
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
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein/*%
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * A large 32-bit prime number that specifies the range of the hash output.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews */
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews#define PRIME32 0xFFFFFFFB /* 2^32 - 5 */
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein/*@{*/
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein/*%
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * Types of random seed and hash accumulator. Perhaps they can be system
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * dependent.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews */
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewstypedef isc_uint32_t hash_accum_t;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewstypedef isc_uint16_t hash_random_t;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein/*@}*/
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein/*% isc hash structure */
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsstruct isc_hash {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews unsigned int magic;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_mem_t *mctx;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_mutex_t lock;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_boolean_t initialized;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_refcount_t refcnt;
ab023a65562e62b85a824509d829b6fad87e00b1Rob Austein isc_entropy_t *entropy; /*%< entropy source */
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 */
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews};
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
be2c2c29a88db96bd51f11d671ec207f0b6b0d45Mark Andrewsstatic isc_mutex_t createlock;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsstatic isc_once_t once = ISC_ONCE_INIT;
a00f9e2f50675bd43cc6a9fe2669709162a2ccb4Evan Hunt
a00f9e2f50675bd43cc6a9fe2669709162a2ccb4Evan HuntLIBISC_EXTERNAL_DATA isc_hash_t *isc_hashctx = NULL;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
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 Andrews 0xf8, 0xf9, 0xfa, 0xfb, 0xfc, 0xfd, 0xfe, 0xff
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews};
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_result_t
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_hash_ctxcreate(isc_mem_t *mctx, isc_entropy_t *entropy,
c3c8823fed039b3a2b8e5ca8bc2f3301d1dd840eMark Andrews size_t limit, isc_hash_t **hctxp)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews{
18d0b5e54be891a1aa938c165b6d439859121ec8Mark Andrews isc_result_t result;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_hash_t *hctx;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews size_t vlen;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hash_random_t *rv;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hash_accum_t overflow_limit;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews REQUIRE(mctx != NULL);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews REQUIRE(hctxp != NULL && *hctxp == NULL);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews /*
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 */
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews overflow_limit =
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews 1 << (((sizeof(hash_accum_t) - sizeof(hash_random_t))) * 8);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (overflow_limit < (limit + 1) * 0xff)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews return (ISC_R_RANGE);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx = isc_mem_get(mctx, sizeof(isc_hash_t));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (hctx == NULL)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews return (ISC_R_NOMEMORY);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews vlen = sizeof(hash_random_t) * (limit + 1);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews rv = isc_mem_get(mctx, vlen);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (rv == NULL) {
18d0b5e54be891a1aa938c165b6d439859121ec8Mark Andrews result = ISC_R_NOMEMORY;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews goto errout;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews }
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews /*
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * We need a lock.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews */
18d0b5e54be891a1aa938c165b6d439859121ec8Mark Andrews result = isc_mutex_init(&hctx->lock);
18d0b5e54be891a1aa938c165b6d439859121ec8Mark Andrews if (result != ISC_R_SUCCESS)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews goto errout;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews /*
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews * From here down, no failures will/can occur.
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews */
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx->magic = HASH_MAGIC;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx->mctx = NULL;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_mem_attach(mctx, &hctx->mctx);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx->initialized = ISC_FALSE;
18d0b5e54be891a1aa938c165b6d439859121ec8Mark Andrews result = isc_refcount_init(&hctx->refcnt, 1);
18d0b5e54be891a1aa938c165b6d439859121ec8Mark Andrews if (result != ISC_R_SUCCESS)
18d0b5e54be891a1aa938c165b6d439859121ec8Mark Andrews goto cleanup_lock;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx->entropy = NULL;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx->limit = limit;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx->vectorlen = vlen;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx->rndvector = rv;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (entropy != NULL)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_entropy_attach(entropy, &hctx->entropy);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews *hctxp = hctx;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews return (ISC_R_SUCCESS);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
18d0b5e54be891a1aa938c165b6d439859121ec8Mark Andrews cleanup_lock:
18d0b5e54be891a1aa938c165b6d439859121ec8Mark Andrews DESTROYLOCK(&hctx->lock);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews errout:
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_mem_put(mctx, hctx, sizeof(isc_hash_t));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (rv != NULL)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_mem_put(mctx, rv, vlen);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
18d0b5e54be891a1aa938c165b6d439859121ec8Mark Andrews return (result);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews}
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsstatic void
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsinitialize_lock(void) {
be2c2c29a88db96bd51f11d671ec207f0b6b0d45Mark Andrews RUNTIME_CHECK(isc_mutex_init(&createlock) == ISC_R_SUCCESS);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews}
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_result_t
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_hash_create(isc_mem_t *mctx, isc_entropy_t *entropy, size_t limit) {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_result_t result = ISC_R_SUCCESS;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews REQUIRE(mctx != NULL);
a00f9e2f50675bd43cc6a9fe2669709162a2ccb4Evan Hunt INSIST(isc_hashctx == NULL);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews RUNTIME_CHECK(isc_once_do(&once, initialize_lock) == ISC_R_SUCCESS);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
be2c2c29a88db96bd51f11d671ec207f0b6b0d45Mark Andrews LOCK(&createlock);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
a00f9e2f50675bd43cc6a9fe2669709162a2ccb4Evan Hunt if (isc_hashctx == NULL)
a00f9e2f50675bd43cc6a9fe2669709162a2ccb4Evan Hunt result = isc_hash_ctxcreate(mctx, entropy, limit,
a00f9e2f50675bd43cc6a9fe2669709162a2ccb4Evan Hunt &isc_hashctx);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
be2c2c29a88db96bd51f11d671ec207f0b6b0d45Mark Andrews UNLOCK(&createlock);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews return (result);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews}
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsvoid
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_hash_ctxinit(isc_hash_t *hctx) {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews LOCK(&hctx->lock);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (hctx->initialized == ISC_TRUE)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews goto out;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
b99bfa184bc9375421b5df915eea7dfac6a68a99Evan Hunt if (hctx->entropy != NULL) {
307d2084502eddc7ce921e5ce439aec3531d90e0Tatuya JINMEI 神明達哉 isc_result_t result;
307d2084502eddc7ce921e5ce439aec3531d90e0Tatuya JINMEI 神明達哉
7a272c6b0de3b8c0ad018b9896e287da19c43befAutomatic Updater result = isc_entropy_getdata(hctx->entropy,
c3c8823fed039b3a2b8e5ca8bc2f3301d1dd840eMark Andrews hctx->rndvector,
c3c8823fed039b3a2b8e5ca8bc2f3301d1dd840eMark Andrews (unsigned int)hctx->vectorlen,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews NULL, 0);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews INSIST(result == ISC_R_SUCCESS);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews } else {
3f40de5598aaf9fa1aa90d6eb82350152bc66ec8Mark Andrews isc_uint32_t pr;
c3c8823fed039b3a2b8e5ca8bc2f3301d1dd840eMark Andrews size_t i, copylen;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews unsigned char *p;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews p = (unsigned char *)hctx->rndvector;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews for (i = 0; i < hctx->vectorlen; i += copylen, p += copylen) {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_random_get(&pr);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (i + sizeof(pr) <= hctx->vectorlen)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews copylen = sizeof(pr);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews else
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews copylen = hctx->vectorlen - i;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
e851ea826066ac5a5b01c2c23218faa0273a12e8Evan Hunt memmove(p, &pr, copylen);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews }
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews INSIST(p == (unsigned char *)hctx->rndvector +
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx->vectorlen);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews }
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx->initialized = ISC_TRUE;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews out:
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews UNLOCK(&hctx->lock);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews}
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsvoid
b454c0319685041db3f3e8fd7671e1b364fd20c5Evan Huntisc_hash_init(void) {
a00f9e2f50675bd43cc6a9fe2669709162a2ccb4Evan Hunt INSIST(isc_hashctx != NULL && VALID_HASH(isc_hashctx));
7a272c6b0de3b8c0ad018b9896e287da19c43befAutomatic Updater
a00f9e2f50675bd43cc6a9fe2669709162a2ccb4Evan Hunt isc_hash_ctxinit(isc_hashctx);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews}
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsvoid
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_hash_ctxattach(isc_hash_t *hctx, isc_hash_t **hctxp) {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews REQUIRE(VALID_HASH(hctx));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews REQUIRE(hctxp != NULL && *hctxp == NULL);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_refcount_increment(&hctx->refcnt, NULL);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews *hctxp = hctx;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews}
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsstatic void
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsdestroy(isc_hash_t **hctxp) {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_hash_t *hctx;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_mem_t *mctx;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews REQUIRE(hctxp != NULL && *hctxp != NULL);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx = *hctxp;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews *hctxp = NULL;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews LOCK(&hctx->lock);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_refcount_destroy(&hctx->refcnt);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews mctx = hctx->mctx;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (hctx->entropy != NULL)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_entropy_detach(&hctx->entropy);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (hctx->rndvector != NULL)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_mem_put(mctx, hctx->rndvector, hctx->vectorlen);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews UNLOCK(&hctx->lock);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews DESTROYLOCK(&hctx->lock);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews memset(hctx, 0, sizeof(isc_hash_t));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_mem_put(mctx, hctx, sizeof(isc_hash_t));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_mem_detach(&mctx);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews}
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsvoid
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_hash_ctxdetach(isc_hash_t **hctxp) {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_hash_t *hctx;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews unsigned int refs;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews REQUIRE(hctxp != NULL && VALID_HASH(*hctxp));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hctx = *hctxp;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_refcount_decrement(&hctx->refcnt, &refs);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (refs == 0)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews destroy(&hctx);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews *hctxp = NULL;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews}
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsvoid
b454c0319685041db3f3e8fd7671e1b364fd20c5Evan Huntisc_hash_destroy(void) {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews unsigned int refs;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
a00f9e2f50675bd43cc6a9fe2669709162a2ccb4Evan Hunt INSIST(isc_hashctx != NULL && VALID_HASH(isc_hashctx));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
a00f9e2f50675bd43cc6a9fe2669709162a2ccb4Evan Hunt isc_refcount_decrement(&isc_hashctx->refcnt, &refs);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews INSIST(refs == 0);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
a00f9e2f50675bd43cc6a9fe2669709162a2ccb4Evan Hunt destroy(&isc_hashctx);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews}
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsstatic inline unsigned int
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewshash_calc(isc_hash_t *hctx, const unsigned char *key, unsigned int keylen,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_boolean_t case_sensitive)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews{
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hash_accum_t partial_sum = 0;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews hash_random_t *p = hctx->rndvector;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews unsigned int i = 0;
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews /* Make it sure that the hash context is initialized. */
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (hctx->initialized == ISC_FALSE)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_hash_ctxinit(hctx);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews if (case_sensitive) {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews for (i = 0; i < keylen; i++)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews partial_sum += key[i] * (hash_accum_t)p[i];
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews } else {
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews for (i = 0; i < keylen; i++)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews partial_sum += maptolower[key[i]] * (hash_accum_t)p[i];
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews }
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews partial_sum += p[i];
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews return ((unsigned int)(partial_sum % PRIME32));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews}
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsunsigned int
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_hash_ctxcalc(isc_hash_t *hctx, const unsigned char *key,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews unsigned int keylen, isc_boolean_t case_sensitive)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews{
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews REQUIRE(hctx != NULL && VALID_HASH(hctx));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews REQUIRE(keylen <= hctx->limit);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews return (hash_calc(hctx, key, keylen, case_sensitive));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews}
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsunsigned int
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrewsisc_hash_calc(const unsigned char *key, unsigned int keylen,
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews isc_boolean_t case_sensitive)
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews{
a00f9e2f50675bd43cc6a9fe2669709162a2ccb4Evan Hunt INSIST(isc_hashctx != NULL && VALID_HASH(isc_hashctx));
a00f9e2f50675bd43cc6a9fe2669709162a2ccb4Evan Hunt REQUIRE(keylen <= isc_hashctx->limit);
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews
a00f9e2f50675bd43cc6a9fe2669709162a2ccb4Evan Hunt return (hash_calc(isc_hashctx, key, keylen, case_sensitive));
1e107b3d7b54de5022c3328423164e533afcc15eMark Andrews}
ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman
ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaramanvoid
caa252e5adf952d8981c7dacd28c5d2296ff5896Evan Huntisc__hash_setvec(const isc_uint16_t *vec) {
ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman int i;
ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman hash_random_t *p;
ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman
a00f9e2f50675bd43cc6a9fe2669709162a2ccb4Evan Hunt if (isc_hashctx == NULL)
ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman return;
ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman
a00f9e2f50675bd43cc6a9fe2669709162a2ccb4Evan Hunt p = isc_hashctx->rndvector;
ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman for (i = 0; i < 256; i++) {
ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman p[i] = vec[i];
ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman }
ce376a81fa674d240197628ceb6113a4fa5a1ab3Mukund Sivaraman}
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman
9da98335c185c39591150ccb4e307adc4cea44bcMukund Sivaramanstatic isc_uint32_t fnv_offset_basis;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaramanstatic isc_once_t fnv_once = ISC_ONCE_INIT;
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaramanstatic isc_boolean_t fnv_initialized = ISC_FALSE;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaramanstatic void
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaramanfnv_initialize(void) {
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman /*
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.
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman */
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman while (fnv_offset_basis == 0) {
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman isc_random_get(&fnv_offset_basis);
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman }
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman fnv_initialized = ISC_TRUE;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman}
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman
93c211afc97e7a072c12ef346581065e4065ff15Evan Huntconst void *
93c211afc97e7a072c12ef346581065e4065ff15Evan Huntisc_hash_get_initializer(void) {
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman if (ISC_UNLIKELY(!fnv_initialized))
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman RUNTIME_CHECK(isc_once_do(&fnv_once, fnv_initialize) == ISC_R_SUCCESS);
93c211afc97e7a072c12ef346581065e4065ff15Evan Hunt
93c211afc97e7a072c12ef346581065e4065ff15Evan Hunt return (&fnv_offset_basis);
93c211afc97e7a072c12ef346581065e4065ff15Evan Hunt}
93c211afc97e7a072c12ef346581065e4065ff15Evan Hunt
93c211afc97e7a072c12ef346581065e4065ff15Evan Huntvoid
93c211afc97e7a072c12ef346581065e4065ff15Evan Huntisc_hash_set_initializer(const void *initializer) {
93c211afc97e7a072c12ef346581065e4065ff15Evan Hunt REQUIRE(initializer != NULL);
93c211afc97e7a072c12ef346581065e4065ff15Evan Hunt
93c211afc97e7a072c12ef346581065e4065ff15Evan Hunt /*
93c211afc97e7a072c12ef346581065e4065ff15Evan Hunt * Ensure that fnv_initialize() is not called after
93c211afc97e7a072c12ef346581065e4065ff15Evan Hunt * isc_hash_set_initializer() is called.
93c211afc97e7a072c12ef346581065e4065ff15Evan Hunt */
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman if (ISC_UNLIKELY(!fnv_initialized))
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman RUNTIME_CHECK(isc_once_do(&fnv_once, fnv_initialize) == ISC_R_SUCCESS);
93c211afc97e7a072c12ef346581065e4065ff15Evan Hunt
93c211afc97e7a072c12ef346581065e4065ff15Evan Hunt fnv_offset_basis = *((const unsigned int *) initializer);
93c211afc97e7a072c12ef346581065e4065ff15Evan Hunt}
93c211afc97e7a072c12ef346581065e4065ff15Evan Hunt
9da98335c185c39591150ccb4e307adc4cea44bcMukund Sivaramanisc_uint32_t
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaramanisc_hash_function(const void *data, size_t length,
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman isc_boolean_t case_sensitive,
9da98335c185c39591150ccb4e307adc4cea44bcMukund Sivaraman const isc_uint32_t *previous_hashp)
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman{
9da98335c185c39591150ccb4e307adc4cea44bcMukund Sivaraman isc_uint32_t hval;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman const unsigned char *bp;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman const unsigned char *be;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman
ce786900292468e465fb74df8712a625ce10e103Mukund Sivaraman REQUIRE(length == 0 || data != NULL);
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman if (ISC_UNLIKELY(!fnv_initialized))
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman RUNTIME_CHECK(isc_once_do(&fnv_once, fnv_initialize) == ISC_R_SUCCESS);
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman
9da98335c185c39591150ccb4e307adc4cea44bcMukund Sivaraman hval = ISC_UNLIKELY(previous_hashp != NULL) ?
9da98335c185c39591150ccb4e307adc4cea44bcMukund Sivaraman *previous_hashp : fnv_offset_basis;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman
614ce1b65ff9ef158aa5a19a9acf2edb99170963Mukund Sivaraman if (length == 0)
614ce1b65ff9ef158aa5a19a9acf2edb99170963Mukund Sivaraman return (hval);
614ce1b65ff9ef158aa5a19a9acf2edb99170963Mukund Sivaraman
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman bp = (const unsigned char *) data;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman be = bp + length;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman /*
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman * Fowler-Noll-Vo FNV-1a hash function.
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman *
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 Sivaraman */
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman if (case_sensitive) {
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman while (bp <= be - 4) {
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman hval ^= bp[0];
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman hval *= 16777619;
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman hval ^= bp[1];
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman hval *= 16777619;
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman hval ^= bp[2];
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman hval *= 16777619;
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman hval ^= bp[3];
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman hval *= 16777619;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman bp += 4;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman }
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman while (bp < be) {
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman hval ^= *bp++;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman hval *= 16777619;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman }
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman } else {
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman while (bp <= be - 4) {
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman hval ^= maptolower[bp[0]];
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman hval *= 16777619;
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman hval ^= maptolower[bp[1]];
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman hval *= 16777619;
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman hval ^= maptolower[bp[2]];
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman hval *= 16777619;
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman hval ^= maptolower[bp[3]];
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman hval *= 16777619;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman bp += 4;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman }
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman while (bp < be) {
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman hval ^= maptolower[*bp++];
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman hval *= 16777619;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman }
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman }
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman return (hval);
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman}
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman
9da98335c185c39591150ccb4e307adc4cea44bcMukund Sivaramanisc_uint32_t
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaramanisc_hash_function_reverse(const void *data, size_t length,
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman isc_boolean_t case_sensitive,
9da98335c185c39591150ccb4e307adc4cea44bcMukund Sivaraman const isc_uint32_t *previous_hashp)
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman{
9da98335c185c39591150ccb4e307adc4cea44bcMukund Sivaraman isc_uint32_t hval;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman const unsigned char *bp;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman const unsigned char *be;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman
ce786900292468e465fb74df8712a625ce10e103Mukund Sivaraman REQUIRE(length == 0 || data != NULL);
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman if (ISC_UNLIKELY(!fnv_initialized))
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman RUNTIME_CHECK(isc_once_do(&fnv_once, fnv_initialize) == ISC_R_SUCCESS);
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman
9da98335c185c39591150ccb4e307adc4cea44bcMukund Sivaraman hval = ISC_UNLIKELY(previous_hashp != NULL) ?
9da98335c185c39591150ccb4e307adc4cea44bcMukund Sivaraman *previous_hashp : fnv_offset_basis;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman
614ce1b65ff9ef158aa5a19a9acf2edb99170963Mukund Sivaraman if (length == 0)
614ce1b65ff9ef158aa5a19a9acf2edb99170963Mukund Sivaraman return (hval);
614ce1b65ff9ef158aa5a19a9acf2edb99170963Mukund Sivaraman
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman bp = (const unsigned char *) data;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman be = bp + length;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman /*
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman * Fowler-Noll-Vo FNV-1a hash function.
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman *
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 Sivaraman */
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman if (case_sensitive) {
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman while (be >= bp + 4) {
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman be -= 4;
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman hval ^= be[3];
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman hval *= 16777619;
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman hval ^= be[2];
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman hval *= 16777619;
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman hval ^= be[1];
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman hval *= 16777619;
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman hval ^= be[0];
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman hval *= 16777619;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman }
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman while (--be >= bp) {
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman hval ^= *be;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman hval *= 16777619;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman }
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman } else {
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman while (be >= bp + 4) {
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman be -= 4;
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman hval ^= maptolower[be[3]];
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman hval *= 16777619;
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman hval ^= maptolower[be[2]];
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman hval *= 16777619;
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman hval ^= maptolower[be[1]];
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman hval *= 16777619;
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman hval ^= maptolower[be[0]];
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman hval *= 16777619;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman }
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman while (--be >= bp) {
16f43564c6875e2bedd346c18c494933ad51e4faMukund Sivaraman hval ^= maptolower[*be];
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman hval *= 16777619;
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman }
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman }
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman return (hval);
5d79b60fc5e4dad4f04da39570517d20a2425f8bMukund Sivaraman}