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