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 if (UseCompactObjectHeaders) {
59 return os::random();
60 }
61 intptr_t hc = k->java_mirror()->mark().hash();
62 return hc != markWord::no_hash ? hc : os::random();
63 }
64
65 // Seed value used for each alternative hash calculated.
66 uint64_t AltHashing::compute_seed() {
67 uint64_t nanos = os::javaTimeNanos();
68 uint64_t now = os::javaTimeMillis();
69 uint32_t SEED_MATERIAL[8] = {
70 (uint32_t) object_hash(vmClasses::String_klass()),
71 (uint32_t) object_hash(vmClasses::System_klass()),
72 (uint32_t) os::random(), // current thread isn't a java thread
73 (uint32_t) (((uint64_t)nanos) >> 32),
74 (uint32_t) nanos,
75 (uint32_t) (((uint64_t)now) >> 32),
76 (uint32_t) now,
77 (uint32_t) (os::javaTimeNanos() >> 2)
78 };
79
80 return halfsiphash_64(SEED_MATERIAL, 8);
81 }
82
83 // utility function copied from java/lang/Integer
84 static uint32_t Integer_rotateLeft(uint32_t i, int distance) {
85 return (i << distance) | (i >> (32 - distance));
86 }
87
88 static void halfsiphash_rounds(uint32_t v[4], int rounds) {
89 while (rounds-- > 0) {
90 v[0] += v[1];
91 v[1] = Integer_rotateLeft(v[1], 5);
92 v[1] ^= v[0];
93 v[0] = Integer_rotateLeft(v[0], 16);
94 v[2] += v[3];
95 v[3] = Integer_rotateLeft(v[3], 8);
96 v[3] ^= v[2];
97 v[0] += v[3];
98 v[3] = Integer_rotateLeft(v[3], 7);
99 v[3] ^= v[0];
100 v[2] += v[1];
101 v[1] = Integer_rotateLeft(v[1], 13);
102 v[1] ^= v[2];
103 v[2] = Integer_rotateLeft(v[2], 16);
104 }
105 }
106
107 static void halfsiphash_adddata(uint32_t v[4], uint32_t newdata, int rounds) {
108 v[3] ^= newdata;
109 halfsiphash_rounds(v, rounds);
110 v[0] ^= newdata;
111 }
112
113 static void halfsiphash_init32(uint32_t v[4], uint64_t seed) {
114 v[0] = seed & 0xffffffff;
115 v[1] = (uint32_t)(seed >> 32);
116 v[2] = 0x6c796765 ^ v[0];
117 v[3] = 0x74656462 ^ v[1];
118 }
119
120 static void halfsiphash_init64(uint32_t v[4], uint64_t seed) {
121 halfsiphash_init32(v, seed);
122 v[1] ^= 0xee;
123 }
124
125 static uint32_t halfsiphash_finish32(uint32_t v[4], int rounds) {
126 v[2] ^= 0xff;
127 halfsiphash_rounds(v, rounds);
128 return (v[1] ^ v[3]);
129 }
130
131 static uint64_t halfsiphash_finish64(uint32_t v[4], int rounds) {
132 uint64_t rv;
133 v[2] ^= 0xee;
134 halfsiphash_rounds(v, rounds);
135 rv = v[1] ^ v[3];
136 v[1] ^= 0xdd;
137 halfsiphash_rounds(v, rounds);
138 rv |= (uint64_t)(v[1] ^ v[3]) << 32;
139 return rv;
140 }
141
142 // HalfSipHash-2-4 (32-bit output) for Symbols
143 uint32_t AltHashing::halfsiphash_32(uint64_t seed, const void* in, int len) {
144
145 const unsigned char* data = (const unsigned char*)in;
146 uint32_t v[4];
147 uint32_t newdata;
148 int off = 0;
149 int count = len;
150
151 halfsiphash_init32(v, seed);
152
153 // body
154 while (count >= 4) {
155
156 // Avoid sign extension with 0x0ff
157 newdata = (data[off] & 0x0FF)
158 | (data[off + 1] & 0x0FF) << 8
159 | (data[off + 2] & 0x0FF) << 16
160 | data[off + 3] << 24;
161
162 count -= 4;
163 off += 4;
164
165 halfsiphash_adddata(v, newdata, 2);
166 }
167
168 // tail
169 newdata = ((uint32_t)len) << 24; // (Byte.SIZE / Byte.SIZE);
170
171 if (count > 0) {
172 switch (count) {
173 case 3:
174 newdata |= (data[off + 2] & 0x0ff) << 16;
175 // fall through
176 case 2:
177 newdata |= (data[off + 1] & 0x0ff) << 8;
178 // fall through
179 case 1:
180 newdata |= (data[off] & 0x0ff);
181 // fall through
182 }
183 }
184
185 halfsiphash_adddata(v, newdata, 2);
186
187 // finalization
188 return halfsiphash_finish32(v, 4);
189 }
190
191 // HalfSipHash-2-4 (32-bit output) for Strings
192 uint32_t AltHashing::halfsiphash_32(uint64_t seed, const uint16_t* data, int len) {
193 uint32_t v[4];
194 uint32_t newdata;
195 int off = 0;
196 int count = len;
197
198 halfsiphash_init32(v, seed);
199
200 // body
201 while (count >= 2) {
202 uint16_t d1 = data[off++] & 0x0FFFF;
203 uint16_t d2 = data[off++];
204 newdata = (d1 | d2 << 16);
205
206 count -= 2;
207
208 halfsiphash_adddata(v, newdata, 2);
209 }
210
211 // tail
212 newdata = ((uint32_t)len * 2) << 24; // (Character.SIZE / Byte.SIZE);
213 if (count > 0) {
214 newdata |= (uint32_t)data[off];
215 }
216 halfsiphash_adddata(v, newdata, 2);
217
218 // finalization
219 return halfsiphash_finish32(v, 4);
220 }
221
222 // HalfSipHash-2-4 (64-bit output) for integers (used to create seed)
223 uint64_t AltHashing::halfsiphash_64(uint64_t seed, const uint32_t* data, int len) {
224 uint32_t v[4];
225
226 int off = 0;
227 int end = len;
228
229 halfsiphash_init64(v, seed);
230
231 // body
232 while (off < end) {
233 halfsiphash_adddata(v, (uint32_t)data[off++], 2);
234 }
235
236 // tail (always empty, as body is always 32-bit chunks)
237
238 // finalization
239 halfsiphash_adddata(v, ((uint32_t)len * 4) << 24, 2); // (Integer.SIZE / Byte.SIZE);
240 return halfsiphash_finish64(v, 4);
241 }
242
243 // HalfSipHash-2-4 (64-bit output) for integers (used to create seed)
244 uint64_t AltHashing::halfsiphash_64(const uint32_t* data, int len) {
245 return halfsiphash_64((uint64_t)0, data, len);
246 }