[apple/xnu.git] / libkern / os / hash.h

/*
 * 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
 *
 * @returns
 * The jenkins hash for this data.
 */
static inline uint32_t
os_hash_jenkins(const void *data, size_t length)
{
	return os_hash_jenkins_finish(os_hash_jenkins_update(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)pointer >> 4;
	key *= 0x5052acdb;
	return (uint32_t)key ^ __builtin_bswap32((uint32_t)key);
}

__END_DECLS

#endif // PRIVATE
#endif // _OS_HASH_H_
Commit	Line	Data
0a7de745 A	1	/*
	2	* Copyright (c) 2018 Apple Inc. All rights reserved.
	3	*
	4	* @APPLE_OSREFERENCE_LICENSE_HEADER_START@
	5	*
	6	* This file contains Original Code and/or Modifications of Original Code
	7	* as defined in and that are subject to the Apple Public Source License
	8	* Version 2.0 (the 'License'). You may not use this file except in
	9	* compliance with the License. The rights granted to you under the License
	10	* may not be used to create, or enable the creation or redistribution of,
	11	* unlawful or unlicensed copies of an Apple operating system, or to
	12	* circumvent, violate, or enable the circumvention or violation of, any
	13	* terms of an Apple operating system software license agreement.
	14	*
	15	* Please obtain a copy of the License at
	16	* http://www.opensource.apple.com/apsl/ and read it before using this file.
	17	*
	18	* The Original Code and all software distributed under the License are
	19	* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
	20	* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
	21	* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
	22	* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
	23	* Please see the License for the specific language governing rights and
	24	* limitations under the License.
	25	*
	26	* @APPLE_OSREFERENCE_LICENSE_HEADER_END@
	27	*/
	28
	29	#ifndef _OS_HASH_H_
	30	#define _OS_HASH_H_
	31	#if PRIVATE
	32
	33	#include <os/base.h>
	34
	35	__BEGIN_DECLS
	36
c3c9b80d A	37	static inline uint32_t
	38	os_hash_jenkins_update(const void *data, size_t length, uint32_t hash)
	39	{
	40	const uint8_t key = (const uint8_t )data;
	41
	42	for (size_t i = 0; i < length; i++) {
	43	hash += key[i];
	44	hash += (hash << 10);
	45	hash ^= (hash >> 6);
	46	}
	47
	48	return hash;
	49	}
	50
	51	static inline uint32_t
	52	os_hash_jenkins_finish(uint32_t hash)
	53	{
	54	hash += (hash << 3);
	55	hash ^= (hash >> 11);
	56	hash += (hash << 15);
	57
	58	return hash;
	59	}
	60
0a7de745 A	61	/*!
	62	* @function os_hash_jenkins
	63	*
	64	* @brief
	65	* The original Jenkins "one at a time" hash.
	66	*
	67	* @discussion
	68	* TBD: There may be some value to unrolling here,
	69	* depending on the architecture.
	70	*
	71	* @param data
	72	* The address of the data to hash.
	73	*
	74	* @param length
	75	* The length of the data to hash
	76	*
	77	* @returns
	78	* The jenkins hash for this data.
	79	*/
	80	static inline uint32_t
	81	os_hash_jenkins(const void *data, size_t length)
	82	{
c3c9b80d	83	return os_hash_jenkins_finish(os_hash_jenkins_update(data, length, 0));
0a7de745 A	84	}
	85
	86	/*!
	87	* @function os_hash_kernel_pointer
	88	*
	89	* @brief
	90	* Hashes a pointer from a zone.
	91	*
	92	* @discussion
	93	* This is a really cheap and fast hash that will behave well for pointers
	94	* allocated by the kernel.
	95	*
	96	* This should be not used for untrusted pointer values from userspace,
	97	* or cases when the pointer is somehow under the control of userspace.
	98	*
	99	* This hash function utilizes knowledge about the span of the kernel
	100	* address space and inherent alignment of zalloc/kalloc.
	101	*
	102	* @param pointer
	103	* The pointer to hash.
	104	*
	105	* @returns
	106	* The hash for this pointer.
	107	*/
	108	static inline uint32_t
	109	os_hash_kernel_pointer(const void *pointer)
	110	{
	111	uintptr_t key = (uintptr_t)pointer >> 4;
	112	key *= 0x5052acdb;
	113	return (uint32_t)key ^ __builtin_bswap32((uint32_t)key);
	114	}
	115
	116	__END_DECLS
	117
	118	#endif // PRIVATE
	119	#endif // _OS_HASH_H_