Mercurial > jdk8-mips64-public > hotspot / file comparison

comparison: src/share/vm/classfile/altHashing.cpp

src/share/vm/classfile/altHashing.cpp

changeset 10008
fd3484fadbe3
parent 9351
bae7d3cdf6af
child 10009
8adf45218add
equal deleted inserted replaced
10007:cb1e375e88a9 10008:fd3484fadbe3
1 /* 1 /*
2 * Copyright (c) 2012, 2018, Oracle and/or its affiliates. All rights reserved. 2 * Copyright (c) 2012, 2020, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 * 4 *
5 * This code is free software; you can redistribute it and/or modify it 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 6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. 7 * published by the Free Software Foundation.
20 * or visit www.oracle.com if you need additional information or have any 20 * or visit www.oracle.com if you need additional information or have any
21 * questions. 21 * questions.
22 * 22 *
23 */ 23 */
24 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 * SipHash reference C implementation
31 *
32 * Copyright (c) 2016 Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
33 *
34 * To the extent possible under law, the author(s) have dedicated all copyright
35 * and related and neighboring rights to this software to the public domain
36 * worldwide. This software is distributed without any warranty.
37 *
38 * You should have received a copy of the CC0 Public Domain Dedication along
39 * with this software. If not, see
40 * <http://creativecommons.org/publicdomain/zero/1.0/>.
41 */
42
25 #include "precompiled.hpp" 43 #include "precompiled.hpp"
26 #include "classfile/altHashing.hpp" 44 #include "classfile/altHashing.hpp"
27 #include "classfile/symbolTable.hpp"
28 #include "classfile/systemDictionary.hpp" 45 #include "classfile/systemDictionary.hpp"
29 #include "oops/markOop.hpp" 46 #include "oops/markOop.hpp"
30 #include "runtime/thread.hpp" 47 #include "runtime/os.hpp"
31 48
32 // Get the hash code of the classes mirror if it exists, otherwise just 49 // Get the hash code of the classes mirror if it exists, otherwise just
33 // return a random number, which is one of the possible hash code used for 50 // return a random number, which is one of the possible hash code used for
34 // objects. We don't want to call the synchronizer hash code to install 51 // objects. We don't want to call the synchronizer hash code to install
35 // this value because it may safepoint. 52 // this value because it may safepoint.
37 intptr_t hc = k->java_mirror()->mark()->hash(); 54 intptr_t hc = k->java_mirror()->mark()->hash();
38 return hc != markOopDesc::no_hash ? hc : os::random(); 55 return hc != markOopDesc::no_hash ? hc : os::random();
39 } 56 }
40 57
41 // Seed value used for each alternative hash calculated. 58 // Seed value used for each alternative hash calculated.
42 juint AltHashing::compute_seed() { 59 uint64_t AltHashing::compute_seed() {
43 jlong nanos = os::javaTimeNanos(); 60 uint64_t nanos = os::javaTimeNanos();
44 jlong now = os::javaTimeMillis(); 61 uint64_t now = os::javaTimeMillis();
45 int SEED_MATERIAL[8] = { 62 uint32_t SEED_MATERIAL[8] = {
46 (int) object_hash(SystemDictionary::String_klass()), 63 (uint32_t) object_hash(SystemDictionary::String_klass()),
47 (int) object_hash(SystemDictionary::System_klass()), 64 (uint32_t) object_hash(SystemDictionary::System_klass()),
48 (int) os::random(), // current thread isn't a java thread 65 (uint32_t) os::random(), // current thread isn't a java thread
49 (int) (((julong)nanos) >> 32), 66 (uint32_t) (((uint64_t)nanos) >> 32),
50 (int) nanos, 67 (uint32_t) nanos,
51 (int) (((julong)now) >> 32), 68 (uint32_t) (((uint64_t)now) >> 32),
52 (int) now, 69 (uint32_t) now,
53 (int) (os::javaTimeNanos() >> 2) 70 (uint32_t) (os::javaTimeNanos() >> 2)
54 }; 71 };
55 72
56 return murmur3_32(SEED_MATERIAL, 8); 73 return halfsiphash_64(SEED_MATERIAL, 8);
57 } 74 }
58 75
59 76 // utility function copied from java/lang/Integer
60 // Murmur3 hashing for Symbol 77 static uint32_t Integer_rotateLeft(uint32_t i, int distance) {
61 juint AltHashing::murmur3_32(juint seed, const jbyte* data, int len) { 78 return (i << distance) | (i >> (32 - distance));
62 juint h1 = seed; 79 }
80
81 static void halfsiphash_rounds(uint32_t v[4], int rounds) {
82 while (rounds-- > 0) {
83 v[0] += v[1];
84 v[1] = Integer_rotateLeft(v[1], 5);
85 v[1] ^= v[0];
86 v[0] = Integer_rotateLeft(v[0], 16);
87 v[2] += v[3];
88 v[3] = Integer_rotateLeft(v[3], 8);
89 v[3] ^= v[2];
90 v[0] += v[3];
91 v[3] = Integer_rotateLeft(v[3], 7);
92 v[3] ^= v[0];
93 v[2] += v[1];
94 v[1] = Integer_rotateLeft(v[1], 13);
95 v[1] ^= v[2];
96 v[2] = Integer_rotateLeft(v[2], 16);
97 }
98 }
99
100 static void halfsiphash_adddata(uint32_t v[4], uint32_t newdata, int rounds) {
101 v[3] ^= newdata;
102 halfsiphash_rounds(v, rounds);
103 v[0] ^= newdata;
104 }
105
106 static void halfsiphash_init32(uint32_t v[4], uint64_t seed) {
107 v[0] = seed & 0xffffffff;
108 v[1] = seed >> 32;
109 v[2] = 0x6c796765 ^ v[0];
110 v[3] = 0x74656462 ^ v[1];
111 }
112
113 static void halfsiphash_init64(uint32_t v[4], uint64_t seed) {
114 halfsiphash_init32(v, seed);
115 v[1] ^= 0xee;
116 }
117
118 static uint64_t halfsiphash_finish64(uint32_t v[4], int rounds) {
119 uint64_t rv;
120 v[2] ^= 0xee;
121 halfsiphash_rounds(v, rounds);
122 rv = v[1] ^ v[3];
123 v[1] ^= 0xdd;
124 halfsiphash_rounds(v, rounds);
125 rv |= (uint64_t)(v[1] ^ v[3]) << 32;
126 return rv;
127 }
128
129 // HalfSipHash-2-4 (64-bit output) for Symbols
130 uint64_t AltHashing::halfsiphash_64(uint64_t seed, const int8_t* data, int len) {
131 uint32_t v[4];
132 uint32_t newdata;
133 int off = 0;
63 int count = len; 134 int count = len;
64 int offset = 0; 135
65 136 halfsiphash_init64(v, seed);
66 // body 137 // body
67 while (count >= 4) { 138 while (count >= 4) {
68 juint k1 = (data[offset] & 0x0FF) 139 // Avoid sign extension with 0x0ff
69 | (data[offset + 1] & 0x0FF) << 8 140 newdata = (data[off] & 0x0FF)
70 | (data[offset + 2] & 0x0FF) << 16 141 | (data[off + 1] & 0x0FF) << 8
71 | data[offset + 3] << 24; 142 | (data[off + 2] & 0x0FF) << 16
143 | data[off + 3] << 24;
72 144
73 count -= 4; 145 count -= 4;
74 offset += 4; 146 off += 4;
75 147
76 k1 *= 0xcc9e2d51; 148 halfsiphash_adddata(v, newdata, 2);
77 k1 = Integer_rotateLeft(k1, 15);
78 k1 *= 0x1b873593;
79
80 h1 ^= k1;
81 h1 = Integer_rotateLeft(h1, 13);
82 h1 = h1 * 5 + 0xe6546b64;
83 } 149 }
84 150
85 // tail 151 // tail
152 newdata = ((uint32_t)len) << 24; // (Byte.SIZE / Byte.SIZE);
86 153
87 if (count > 0) { 154 if (count > 0) {
88 juint k1 = 0;
89
90 switch (count) { 155 switch (count) {
91 case 3: 156 case 3:
92 k1 ^= (data[offset + 2] & 0xff) << 16; 157 newdata |= (data[off + 2] & 0x0ff) << 16;
93 // fall through 158 // fall through
94 case 2: 159 case 2:
95 k1 ^= (data[offset + 1] & 0xff) << 8; 160 newdata |= (data[off + 1] & 0x0ff) << 8;
96 // fall through 161 // fall through
97 case 1: 162 case 1:
98 k1 ^= (data[offset] & 0xff); 163 newdata |= (data[off] & 0x0ff);
99 // fall through 164 // fall through
100 default: 165 }
101 k1 *= 0xcc9e2d51; 166 }
102 k1 = Integer_rotateLeft(k1, 15); 167
103 k1 *= 0x1b873593; 168 halfsiphash_adddata(v, newdata, 2);
104 h1 ^= k1;
105 }
106 }
107 169
108 // finalization 170 // finalization
109 h1 ^= len; 171 return halfsiphash_finish64(v, 4);
110 172 }
111 // finalization mix force all bits of a hash block to avalanche 173
112 h1 ^= h1 >> 16; 174 // HalfSipHash-2-4 (64-bit output) for Strings
113 h1 *= 0x85ebca6b; 175 uint64_t AltHashing::halfsiphash_64(uint64_t seed, const uint16_t* data, int len) {
114 h1 ^= h1 >> 13; 176 uint32_t v[4];
115 h1 *= 0xc2b2ae35; 177 uint32_t newdata;
116 h1 ^= h1 >> 16;
117
118 return h1;
119 }
120
121 // Murmur3 hashing for Strings
122 juint AltHashing::murmur3_32(juint seed, const jchar* data, int len) {
123 juint h1 = seed;
124
125 int off = 0; 178 int off = 0;
126 int count = len; 179 int count = len;
127 180
181 halfsiphash_init64(v, seed);
182
128 // body 183 // body
129 while (count >= 2) { 184 while (count >= 2) {
130 jchar d1 = data[off++] & 0xFFFF; 185 uint16_t d1 = data[off++] & 0x0FFFF;
131 jchar d2 = data[off++]; 186 uint16_t d2 = data[off++];
132 juint k1 = (d1 | d2 << 16); 187 newdata = (d1 | d2 << 16);
133 188
134 count -= 2; 189 count -= 2;
135 190
136 k1 *= 0xcc9e2d51; 191 halfsiphash_adddata(v, newdata, 2);
137 k1 = Integer_rotateLeft(k1, 15);
138 k1 *= 0x1b873593;
139
140 h1 ^= k1;
141 h1 = Integer_rotateLeft(h1, 13);
142 h1 = h1 * 5 + 0xe6546b64;
143 } 192 }
144 193
145 // tail 194 // tail
146 195 newdata = ((uint32_t)len * 2) << 24; // (Character.SIZE / Byte.SIZE);
147 if (count > 0) { 196 if (count > 0) {
148 juint k1 = (juint)data[off]; 197 newdata |= (uint32_t)data[off];
149 198 }
150 k1 *= 0xcc9e2d51; 199 halfsiphash_adddata(v, newdata, 2);
151 k1 = Integer_rotateLeft(k1, 15);
152 k1 *= 0x1b873593;
153 h1 ^= k1;
154 }
155 200
156 // finalization 201 // finalization
157 h1 ^= len * 2; // (Character.SIZE / Byte.SIZE); 202 return halfsiphash_finish64(v, 4);
158 203 }
159 // finalization mix force all bits of a hash block to avalanche 204
160 h1 ^= h1 >> 16; 205 // HalfSipHash-2-4 (64-bit output) for integers (used to create seed)
161 h1 *= 0x85ebca6b; 206 uint64_t AltHashing::halfsiphash_64(uint64_t seed, const uint32_t* data, int len) {
162 h1 ^= h1 >> 13; 207 uint32_t v[4];
163 h1 *= 0xc2b2ae35;
164 h1 ^= h1 >> 16;
165
166 return h1;
167 }
168
169 // Hash used for the seed.
170 juint AltHashing::murmur3_32(juint seed, const int* data, int len) {
171 juint h1 = seed;
172 208
173 int off = 0; 209 int off = 0;
174 int end = len; 210 int end = len;
175 211
212 halfsiphash_init64(v, seed);
213
176 // body 214 // body
177 while (off < end) { 215 while (off < end) {
178 juint k1 = (juint)data[off++]; 216 halfsiphash_adddata(v, (uint32_t)data[off++], 2);
179
180 k1 *= 0xcc9e2d51;
181 k1 = Integer_rotateLeft(k1, 15);
182 k1 *= 0x1b873593;
183
184 h1 ^= k1;
185 h1 = Integer_rotateLeft(h1, 13);
186 h1 = h1 * 5 + 0xe6546b64;
187 } 217 }
188 218
189 // tail (always empty, as body is always 32-bit chunks) 219 // tail (always empty, as body is always 32-bit chunks)
190 220
191 // finalization 221 // finalization
192 222 halfsiphash_adddata(v, ((uint32_t)len * 4) << 24, 2); // (Integer.SIZE / Byte.SIZE);
193 h1 ^= len * 4; // (Integer.SIZE / Byte.SIZE); 223 return halfsiphash_finish64(v, 4);
194 224 }
195 // finalization mix force all bits of a hash block to avalanche 225
196 h1 ^= h1 >> 16; 226 // HalfSipHash-2-4 (64-bit output) for integers (used to create seed)
197 h1 *= 0x85ebca6b; 227 uint64_t AltHashing::halfsiphash_64(const uint32_t* data, int len) {
198 h1 ^= h1 >> 13; 228 return halfsiphash_64((uint64_t)0, data, len);
199 h1 *= 0xc2b2ae35;
200 h1 ^= h1 >> 16;
201
202 return h1;
203 }
204
205 juint AltHashing::murmur3_32(const int* data, int len) {
206 return murmur3_32(0, data, len);
207 } 229 }
208 230
209 #ifndef PRODUCT 231 #ifndef PRODUCT
210 // Overloaded versions for internal test. 232 void AltHashing::testHalfsiphash_64_ByteArray() {
211 juint AltHashing::murmur3_32(const jbyte* data, int len) { 233 // printf("testHalfsiphash_64_CharArray\n");
212 return murmur3_32(0, data, len); 234 const int factor = 4;
213 } 235
214 236 int8_t vector[256];
215 juint AltHashing::murmur3_32(const jchar* data, int len) { 237 int8_t hashes[factor * 256];
216 return murmur3_32(0, data, len); 238
217 } 239 for (int i = 0; i < 256; i++) {
218 240 vector[i] = (int8_t) i;
219 // Internal test for alternate hashing. Translated from JDK version 241 }
220 // test/sun/misc/Hashing.java 242
221 static const jbyte ONE_BYTE[] = { (jbyte) 0x80}; 243 // Hash subranges {}, {0}, {0,1}, {0,1,2}, ..., {0,...,255}
222 static const jbyte TWO_BYTE[] = { (jbyte) 0x80, (jbyte) 0x81}; 244 for (int i = 0; i < 256; i++) {
223 static const jchar ONE_CHAR[] = { (jchar) 0x8180}; 245 uint64_t hash = AltHashing::halfsiphash_64(256 - i, vector, i);
224 static const jbyte THREE_BYTE[] = { (jbyte) 0x80, (jbyte) 0x81, (jbyte) 0x82}; 246 hashes[i * factor] = (int8_t) hash;
225 static const jbyte FOUR_BYTE[] = { (jbyte) 0x80, (jbyte) 0x81, (jbyte) 0x82, (jbyte) 0x83}; 247 hashes[i * factor + 1] = (int8_t)(hash >> 8);
226 static const jchar TWO_CHAR[] = { (jchar) 0x8180, (jchar) 0x8382}; 248 hashes[i * factor + 2] = (int8_t)(hash >> 16);
227 static const jint ONE_INT[] = { (jint) 0x83828180}; 249 hashes[i * factor + 3] = (int8_t)(hash >> 24);
228 static const jbyte SIX_BYTE[] = { (jbyte) 0x80, (jbyte) 0x81, (jbyte) 0x82, (jbyte) 0x83, (jbyte) 0x84, (jbyte) 0x85}; 250 }
229 static const jchar THREE_CHAR[] = { (jchar) 0x8180, (jchar) 0x8382, (jchar) 0x8584}; 251
230 static const jbyte EIGHT_BYTE[] = { 252 // hash to get const result.
231 (jbyte) 0x80, (jbyte) 0x81, (jbyte) 0x82, 253 uint64_t final_hash = AltHashing::halfsiphash_64(0, hashes, factor*256);
232 (jbyte) 0x83, (jbyte) 0x84, (jbyte) 0x85, 254
233 (jbyte) 0x86, (jbyte) 0x87}; 255 // Value found using reference implementation for the hashes array.
234 static const jchar FOUR_CHAR[] = { 256 // halfsiphash((const uint8_t*)hashes, factor*256, (const uint8_t *)&k,
235 (jchar) 0x8180, (jchar) 0x8382, 257 // (uint8_t*)&reference, 8);
236 (jchar) 0x8584, (jchar) 0x8786}; 258
237 259 static const uint64_t HALFSIPHASH_64_BYTE_CHECK_VALUE = 0x15a7911e30917ee8;
238 static const jint TWO_INT[] = { (jint) 0x83828180, (jint) 0x87868584}; 260
239 261 assert (HALFSIPHASH_64_BYTE_CHECK_VALUE == final_hash,
240 static const juint MURMUR3_32_X86_CHECK_VALUE = 0xB0F57EE3; 262 err_msg(
241 263 "Calculated hash result not as expected. Expected " UINT64_FORMAT " got " UINT64_FORMAT,
242 void AltHashing::testMurmur3_32_ByteArray() { 264 HALFSIPHASH_64_BYTE_CHECK_VALUE,
243 // printf("testMurmur3_32_ByteArray\n"); 265 final_hash));
244 266 }
245 jbyte vector[256]; 267
246 jbyte hashes[4 * 256]; 268 void AltHashing::testHalfsiphash_64_CharArray() {
247 269 // printf("testHalfsiphash_64_CharArray\n");
248 for (int i = 0; i < 256; i++) { 270 const int factor = 2;
249 vector[i] = (jbyte) i; 271
250 } 272 uint16_t vector[256];
251 273 uint16_t hashes[factor * 256];
252 // Hash subranges {}, {0}, {0,1}, {0,1,2}, ..., {0,...,255} 274
253 for (int i = 0; i < 256; i++) { 275 for (int i = 0; i < 256; i++) {
254 juint hash = murmur3_32(256 - i, vector, i); 276 vector[i] = (uint16_t) i;
255 hashes[i * 4] = (jbyte) hash; 277 }
256 hashes[i * 4 + 1] = (jbyte)(hash >> 8); 278
257 hashes[i * 4 + 2] = (jbyte)(hash >> 16); 279 // Hash subranges {}, {0}, {0,1}, {0,1,2}, ..., {0,...,255}
258 hashes[i * 4 + 3] = (jbyte)(hash >> 24); 280 for (int i = 0; i < 256; i++) {
259 } 281 uint64_t hash = AltHashing::halfsiphash_64(256 - i, vector, i);
260 282 hashes[i * factor] = (uint16_t) hash;
261 // hash to get const result. 283 hashes[i * factor + 1] = (uint16_t)(hash >> 16);
262 juint final_hash = murmur3_32(hashes, 4*256); 284 }
263 285
264 assert (MURMUR3_32_X86_CHECK_VALUE == final_hash, 286 // hash to get const result.
265 err_msg( 287 uint64_t final_hash = AltHashing::halfsiphash_64(0, hashes, factor*256);
266 "Calculated hash result not as expected. Expected %08X got %08X\n", 288
267 MURMUR3_32_X86_CHECK_VALUE, 289 // Value found using reference implementation for the hashes array.
268 final_hash)); 290 // halfsiphash((const uint8_t*)hashes, 2*factor*256, (const uint8_t *)&k,
269 } 291 // (uint8_t*)&reference, 8);
270 292 static const uint64_t HALFSIPHASH_64_CHAR_CHECK_VALUE = 0xf392d8a6a9e24103;
271 void AltHashing::testEquivalentHashes() { 293
272 juint jbytes, jchars, ints; 294 assert(HALFSIPHASH_64_CHAR_CHECK_VALUE == final_hash,
273 295 err_msg(
274 // printf("testEquivalentHashes\n"); 296 "Calculated hash result not as expected. Expected " UINT64_FORMAT " got " UINT64_FORMAT,
275 297 HALFSIPHASH_64_CHAR_CHECK_VALUE,
276 jbytes = murmur3_32(TWO_BYTE, 2); 298 final_hash));
277 jchars = murmur3_32(ONE_CHAR, 1); 299 }
278 assert (jbytes == jchars, 300
279 err_msg("Hashes did not match. b:%08x != c:%08x\n", jbytes, jchars)); 301 // Test against sample hashes published with the reference implementation:
280 302 // https://github.com/veorq/SipHash
281 jbytes = murmur3_32(FOUR_BYTE, 4); 303 void AltHashing::testHalfsiphash_64_FromReference() {
282 jchars = murmur3_32(TWO_CHAR, 2); 304 // printf("testHalfsiphash_64_FromReference\n");
283 ints = murmur3_32(ONE_INT, 1); 305
284 assert ((jbytes == jchars) && (jbytes == ints), 306 const uint64_t seed = 0x0706050403020100;
285 err_msg("Hashes did not match. b:%08x != c:%08x != i:%08x\n", jbytes, jchars, ints)); 307 const uint64_t results[16] = {
286 308 0xc83cb8b9591f8d21, 0xa12ee55b178ae7d5,
287 jbytes = murmur3_32(SIX_BYTE, 6); 309 0x8c85e4bc20e8feed, 0x99c7f5ae9f1fc77b,
288 jchars = murmur3_32(THREE_CHAR, 3); 310 0xb5f37b5fd2aa3673, 0xdba7ee6f0a2bf51b,
289 assert (jbytes == jchars, 311 0xf1a63fae45107470, 0xb516001efb5f922d,
290 err_msg("Hashes did not match. b:%08x != c:%08x\n", jbytes, jchars)); 312 0x6c6211d8469d7028, 0xdc7642ec407ad686,
291 313 0x4caec8671cc8385b, 0x5ab1dc27adf3301e,
292 jbytes = murmur3_32(EIGHT_BYTE, 8); 314 0x3e3ea94bc0a8eaa9, 0xe150f598795a4402,
293 jchars = murmur3_32(FOUR_CHAR, 4); 315 0x1d5ff142f992a4a1, 0x60e426bf902876d6
294 ints = murmur3_32(TWO_INT, 2); 316 };
295 assert ((jbytes == jchars) && (jbytes == ints), 317 uint32_t vector[16];
296 err_msg("Hashes did not match. b:%08x != c:%08x != i:%08x\n", jbytes, jchars, ints)); 318
297 } 319 for (int i = 0; i < 16; i++)
298 320 vector[i] = 0x03020100 + i * 0x04040404;
299 // Returns true if the alternate hashcode is correct 321
322 for (int i = 0; i < 16; i++) {
323 uint64_t hash = AltHashing::halfsiphash_64(seed, vector, i);
324 assert(results[i] == hash,
325 err_msg(
326 "Calculated hash result not as expected. Round %d: "
327 "Expected " UINT64_FORMAT_X " got " UINT64_FORMAT_X "\n",
328 i,
329 results[i],
330 hash));
331 }
332 }
333
300 void AltHashing::test_alt_hash() { 334 void AltHashing::test_alt_hash() {
301 testMurmur3_32_ByteArray(); 335 testHalfsiphash_64_ByteArray();
302 testEquivalentHashes(); 336 testHalfsiphash_64_CharArray();
337 testHalfsiphash_64_FromReference();
303 } 338 }
304 #endif // PRODUCT 339 #endif // PRODUCT

Mercurial Repository: jdk8-mips64-public/hotspot

mercurial