xref: /xnu-12377.41.6/libkern/os/hash.h (revision bbb1b6f9e71b8cdde6e5cd6f4841f207dee3d828)

/*
 * Copyright (c) 2018 Apple Inc. All rights reserved.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
 *
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. The rights granted to you under the License
 * may not be used to create, or enable the creation or redistribution of,
 * unlawful or unlicensed copies of an Apple operating system, or to
 * circumvent, violate, or enable the circumvention or violation of, any
 * terms of an Apple operating system software license agreement.
 *
 * Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this file.
 *
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 *
 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
 */

#ifndef _OS_HASH_H_
#define _OS_HASH_H_
#if PRIVATE

#include <os/base.h>

__BEGIN_DECLS

static inline uint32_t
os_hash_jenkins_update(const void *data, size_t length, uint32_t hash)
{
	const uint8_t *key = (const uint8_t *)data;

	for (size_t i = 0; i < length; i++) {
		hash += key[i];
		hash += (hash << 10);
		hash ^= (hash >> 6);
	}

	return hash;
}

static inline uint32_t
os_hash_jenkins_finish(uint32_t hash)
{
	hash += (hash << 3);
	hash ^= (hash >> 11);
	hash += (hash << 15);

	return hash;
}

/*!
 * @function os_hash_jenkins
 *
 * @brief
 * The original Jenkins "one at a time" hash.
 *
 * @discussion
 * TBD: There may be some value to unrolling here,
 * depending on the architecture.
 *
 * @param data
 * The address of the data to hash.
 *
 * @param length
 * The length of the data to hash
 *
 * @param seed
 * An optional hash seed (defaults to 0).
 *
 * @returns
 * The jenkins hash for this data.
 */
__attribute__((overloadable))
static inline uint32_t
os_hash_jenkins(const void *data, size_t length, uint32_t seed)
{
	return os_hash_jenkins_finish(os_hash_jenkins_update(data, length, seed));
}

__attribute__((overloadable))
static inline uint32_t
os_hash_jenkins(const void *data, size_t length)
{
	return os_hash_jenkins(data, length, 0);
}

/*!
 * @function os_hash_kernel_pointer
 *
 * @brief
 * Hashes a pointer from a zone.
 *
 * @discussion
 * This is a really cheap and fast hash that will behave well for pointers
 * allocated by the kernel.
 *
 * This should be not used for untrusted pointer values from userspace,
 * or cases when the pointer is somehow under the control of userspace.
 *
 * This hash function utilizes knowledge about the span of the kernel
 * address space and inherent alignment of zalloc/kalloc.
 *
 * @param pointer
 * The pointer to hash.
 *
 * @returns
 * The hash for this pointer.
 */
static inline uint32_t
os_hash_kernel_pointer(const void *pointer)
{
	uintptr_t key = (uintptr_t)((intptr_t)pointer << 16) >> 20;
	key *= 0x5052acdb;
	return (uint32_t)key ^ __builtin_bswap32((uint32_t)key);
}

/*!
 * @function os_hash_uint64
 *
 * @brief
 * Hashes a 64 bit number.
 *
 * @discussion
 * This is a really cheap and fast mixer.
 *
 * This should be not used for untrusted values from userspace,
 * or cases when the pointer is somehow under the control of userspace.
 *
 * See https://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html
 *
 * @param u64
 * The value to hash
 *
 * @returns
 * The hash for this integer.
 */
static inline uint32_t
os_hash_uint64(uint64_t u64)
{
	u64 ^= (u64 >> 31);
	u64 *= 0x7fb5d329728ea185ull;
	u64 ^= (u64 >> 27);
	u64 *= 0x81dadef4bc2dd44dull;
	u64 ^= (u64 >> 33);

	return (uint32_t)u64;
}

__END_DECLS

#endif // PRIVATE
#endif // _OS_HASH_H_