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 | 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 | |
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 | * @param seed |
78 | * An optional hash seed (defaults to 0). |
79 | * |
80 | * @returns |
81 | * The jenkins hash for this data. |
82 | */ |
83 | __attribute__((overloadable)) |
84 | static inline uint32_t |
85 | os_hash_jenkins(const void *data, size_t length, uint32_t seed) |
86 | { |
87 | return os_hash_jenkins_finish(hash: os_hash_jenkins_update(data, length, hash: seed)); |
88 | } |
89 | |
90 | __attribute__((overloadable)) |
91 | static inline uint32_t |
92 | os_hash_jenkins(const void *data, size_t length) |
93 | { |
94 | return os_hash_jenkins(data, length, seed: 0); |
95 | } |
96 | |
97 | /*! |
98 | * @function os_hash_kernel_pointer |
99 | * |
100 | * @brief |
101 | * Hashes a pointer from a zone. |
102 | * |
103 | * @discussion |
104 | * This is a really cheap and fast hash that will behave well for pointers |
105 | * allocated by the kernel. |
106 | * |
107 | * This should be not used for untrusted pointer values from userspace, |
108 | * or cases when the pointer is somehow under the control of userspace. |
109 | * |
110 | * This hash function utilizes knowledge about the span of the kernel |
111 | * address space and inherent alignment of zalloc/kalloc. |
112 | * |
113 | * @param pointer |
114 | * The pointer to hash. |
115 | * |
116 | * @returns |
117 | * The hash for this pointer. |
118 | */ |
119 | static inline uint32_t |
120 | os_hash_kernel_pointer(const void *pointer) |
121 | { |
122 | uintptr_t key = (uintptr_t)pointer >> 4; |
123 | key *= 0x5052acdb; |
124 | return (uint32_t)key ^ __builtin_bswap32((uint32_t)key); |
125 | } |
126 | |
127 | __END_DECLS |
128 | |
129 | #endif // PRIVATE |
130 | #endif // _OS_HASH_H_ |
131 | |