1 /*
2 * Copyright (c) 2012, 2025, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 /*
26 * halfsiphash code adapted from reference implementation
27 * (https://github.com/veorq/SipHash/blob/master/halfsiphash.c)
28 * which is distributed with the following copyright:
29 */
30
31 /*
32 SipHash reference C implementation
33
34 Copyright (c) 2016 Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
35
36 To the extent possible under law, the author(s) have dedicated all copyright
37 and related and neighboring rights to this software to the public domain
38 worldwide. This software is distributed without any warranty.
39
40 You should have received a copy of the CC0 Public Domain Dedication along
41 with
42 this software. If not, see
43 <http://creativecommons.org/publicdomain/zero/1.0/>.
44 */
45
46 #include "classfile/altHashing.hpp"
47 #include "classfile/vmClasses.hpp"
48 #include "oops/klass.inline.hpp"
49 #include "oops/markWord.hpp"
50 #include "oops/oop.inline.hpp"
51 #include "runtime/os.hpp"
52
53 // Get the hash code of the classes mirror if it exists, otherwise just
54 // return a random number, which is one of the possible hash code used for
55 // objects. We don't want to call the synchronizer hash code to install
56 // this value because it may safepoint.
57 static intptr_t object_hash(Klass* k) {
58 intptr_t hc = k->java_mirror()->mark().hash();
59 return hc != markWord::no_hash ? hc : os::random();
60 }
61
62 // Seed value used for each alternative hash calculated.
63 uint64_t AltHashing::compute_seed() {
64 uint64_t nanos = os::javaTimeNanos();
65 uint64_t now = os::javaTimeMillis();
66 uint32_t SEED_MATERIAL[8] = {
67 (uint32_t) object_hash(vmClasses::String_klass()),
68 (uint32_t) object_hash(vmClasses::System_klass()),
69 (uint32_t) os::random(), // current thread isn't a java thread
70 (uint32_t) (((uint64_t)nanos) >> 32),
71 (uint32_t) nanos,
72 (uint32_t) (((uint64_t)now) >> 32),
73 (uint32_t) now,
74 (uint32_t) (os::javaTimeNanos() >> 2)
75 };
76
77 return halfsiphash_64(SEED_MATERIAL, 8);
78 }
79
80 // utility function copied from java/lang/Integer
81 static uint32_t Integer_rotateLeft(uint32_t i, int distance) {
82 return (i << distance) | (i >> (32 - distance));
83 }
84
85 static void halfsiphash_rounds(uint32_t v[4], int rounds) {
86 while (rounds-- > 0) {
87 v[0] += v[1];
88 v[1] = Integer_rotateLeft(v[1], 5);
89 v[1] ^= v[0];
90 v[0] = Integer_rotateLeft(v[0], 16);
91 v[2] += v[3];
92 v[3] = Integer_rotateLeft(v[3], 8);
93 v[3] ^= v[2];
94 v[0] += v[3];
95 v[3] = Integer_rotateLeft(v[3], 7);
96 v[3] ^= v[0];
97 v[2] += v[1];
98 v[1] = Integer_rotateLeft(v[1], 13);
99 v[1] ^= v[2];
100 v[2] = Integer_rotateLeft(v[2], 16);
101 }
102 }
103
104 static void halfsiphash_adddata(uint32_t v[4], uint32_t newdata, int rounds) {
105 v[3] ^= newdata;
106 halfsiphash_rounds(v, rounds);
107 v[0] ^= newdata;
108 }
109
110 static void halfsiphash_init32(uint32_t v[4], uint64_t seed) {
111 v[0] = seed & 0xffffffff;
112 v[1] = (uint32_t)(seed >> 32);
113 v[2] = 0x6c796765 ^ v[0];
114 v[3] = 0x74656462 ^ v[1];
115 }
116
117 static void halfsiphash_init64(uint32_t v[4], uint64_t seed) {
118 halfsiphash_init32(v, seed);
119 v[1] ^= 0xee;
120 }
121
122 static uint32_t halfsiphash_finish32(uint32_t v[4], int rounds) {
123 v[2] ^= 0xff;
124 halfsiphash_rounds(v, rounds);
125 return (v[1] ^ v[3]);
126 }
127
128 static uint64_t halfsiphash_finish64(uint32_t v[4], int rounds) {
129 uint64_t rv;
130 v[2] ^= 0xee;
131 halfsiphash_rounds(v, rounds);
132 rv = v[1] ^ v[3];
133 v[1] ^= 0xdd;
134 halfsiphash_rounds(v, rounds);
135 rv |= (uint64_t)(v[1] ^ v[3]) << 32;
136 return rv;
137 }
138
139 // HalfSipHash-2-4 (32-bit output) for Symbols
140 uint32_t AltHashing::halfsiphash_32(uint64_t seed, const void* in, int len) {
141
142 const unsigned char* data = (const unsigned char*)in;
143 uint32_t v[4];
144 uint32_t newdata;
145 int off = 0;
146 int count = len;
147
148 halfsiphash_init32(v, seed);
149
150 // body
151 while (count >= 4) {
152
153 // Avoid sign extension with 0x0ff
154 newdata = (data[off] & 0x0FF)
155 | (data[off + 1] & 0x0FF) << 8
156 | (data[off + 2] & 0x0FF) << 16
157 | data[off + 3] << 24;
158
159 count -= 4;
160 off += 4;
161
162 halfsiphash_adddata(v, newdata, 2);
163 }
164
165 // tail
166 newdata = ((uint32_t)len) << 24; // (Byte.SIZE / Byte.SIZE);
167
168 if (count > 0) {
169 switch (count) {
170 case 3:
171 newdata |= (data[off + 2] & 0x0ff) << 16;
172 // fall through
173 case 2:
174 newdata |= (data[off + 1] & 0x0ff) << 8;
175 // fall through
176 case 1:
177 newdata |= (data[off] & 0x0ff);
178 // fall through
179 }
180 }
181
182 halfsiphash_adddata(v, newdata, 2);
183
184 // finalization
185 return halfsiphash_finish32(v, 4);
186 }
187
188 // HalfSipHash-2-4 (32-bit output) for Strings
189 uint32_t AltHashing::halfsiphash_32(uint64_t seed, const uint16_t* data, int len) {
190 uint32_t v[4];
191 uint32_t newdata;
192 int off = 0;
193 int count = len;
194
195 halfsiphash_init32(v, seed);
196
197 // body
198 while (count >= 2) {
199 uint16_t d1 = data[off++] & 0x0FFFF;
200 uint16_t d2 = data[off++];
201 newdata = (d1 | d2 << 16);
202
203 count -= 2;
204
205 halfsiphash_adddata(v, newdata, 2);
206 }
207
208 // tail
209 newdata = ((uint32_t)len * 2) << 24; // (Character.SIZE / Byte.SIZE);
210 if (count > 0) {
211 newdata |= (uint32_t)data[off];
212 }
213 halfsiphash_adddata(v, newdata, 2);
214
215 // finalization
216 return halfsiphash_finish32(v, 4);
217 }
218
219 // HalfSipHash-2-4 (64-bit output) for integers (used to create seed)
220 uint64_t AltHashing::halfsiphash_64(uint64_t seed, const uint32_t* data, int len) {
221 uint32_t v[4];
222
223 int off = 0;
224 int end = len;
225
226 halfsiphash_init64(v, seed);
227
228 // body
229 while (off < end) {
230 halfsiphash_adddata(v, (uint32_t)data[off++], 2);
231 }
232
233 // tail (always empty, as body is always 32-bit chunks)
234
235 // finalization
236 halfsiphash_adddata(v, ((uint32_t)len * 4) << 24, 2); // (Integer.SIZE / Byte.SIZE);
237 return halfsiphash_finish64(v, 4);
238 }
239
240 // HalfSipHash-2-4 (64-bit output) for integers (used to create seed)
241 uint64_t AltHashing::halfsiphash_64(const uint32_t* data, int len) {
242 return halfsiphash_64((uint64_t)0, data, len);
243 }