libkern/os/hash.h

   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
  37 /*!
  38  * @function os_hash_jenkins
  39  *
  40  * @brief
  41  * The original Jenkins "one at a time" hash.
  42  *
  43  * @discussion
  44  * TBD: There may be some value to unrolling here,
  45  * depending on the architecture.
  46  *
  47  * @param data
  48  * The address of the data to hash.
  49  *
  50  * @param length
  51  * The length of the data to hash
  52  *
  53  * @returns
  54  * The jenkins hash for this data.
  55  */
  56 static inline uint32_t
  57 os_hash_jenkins(const void *data, size_t length)
  58 {
  59         const uint8_t *key = (const uint8_t *)data;
  60         uint32_t hash = 0;
  61
  62         for (size_t i = 0; i < length; i++) {
  63                 hash += key[i];
  64                 hash += (hash << 10);
  65                 hash ^= (hash >> 6);
  66         }
  67
  68         hash += (hash << 3);
  69         hash ^= (hash >> 11);
  70         hash += (hash << 15);
  71
  72         return hash;
  73 }
  74
  75 /*!
  76  * @function os_hash_kernel_pointer
  77  *
  78  * @brief
  79  * Hashes a pointer from a zone.
  80  *
  81  * @discussion
  82  * This is a really cheap and fast hash that will behave well for pointers
  83  * allocated by the kernel.
  84  *
  85  * This should be not used for untrusted pointer values from userspace,
  86  * or cases when the pointer is somehow under the control of userspace.
  87  *
  88  * This hash function utilizes knowledge about the span of the kernel
  89  * address space and inherent alignment of zalloc/kalloc.
  90  *
  91  * @param pointer
  92  * The pointer to hash.
  93  *
  94  * @returns
  95  * The hash for this pointer.
  96  */
  97 static inline uint32_t
  98 os_hash_kernel_pointer(const void *pointer)
  99 {
 100         uintptr_t key = (uintptr_t)pointer >> 4;
 101         key *= 0x5052acdb;
 102         return (uint32_t)key ^ __builtin_bswap32((uint32_t)key);
 103 }
 104
 105 __END_DECLS
 106
 107 #endif // PRIVATE
 108 #endif // _OS_HASH_H_