1 /*
2 * Copyright (c) 2012, 2017, 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 #include "precompiled.hpp"
26 #include "classfile/altHashing.hpp"
27 #include "classfile/symbolTable.hpp"
28 #include "classfile/systemDictionary.hpp"
29 #include "oops/markOop.hpp"
30 #include "oops/oop.inline.hpp"
31 #include "runtime/thread.hpp"
32
33 // Get the hash code of the classes mirror if it exists, otherwise just
34 // return a random number, which is one of the possible hash code used for
35 // objects. We don't want to call the synchronizer hash code to install
36 // this value because it may safepoint.
37 static intptr_t object_hash(Klass* k) {
38 intptr_t hc = k->java_mirror()->mark()->hash();
39 return hc != markOopDesc::no_hash ? hc : os::random();
40 }
41
42 // Seed value used for each alternative hash calculated.
43 juint AltHashing::compute_seed() {
44 jlong nanos = os::javaTimeNanos();
45 jlong now = os::javaTimeMillis();
46 jint SEED_MATERIAL[8] = {
47 (jint) object_hash(SystemDictionary::String_klass()),
48 (jint) object_hash(SystemDictionary::System_klass()),
49 (jint) os::random(), // current thread isn't a java thread
50 (jint) (((julong)nanos) >> 32),
51 (jint) nanos,
52 (jint) (((julong)now) >> 32),
53 (jint) now,
54 (jint) (os::javaTimeNanos() >> 2)
55 };
56
57 return murmur3_32(SEED_MATERIAL, 8);
58 }
59
60
61 // Murmur3 hashing for Symbol
62 juint AltHashing::murmur3_32(juint seed, const jbyte* data, int len) {
63 juint h1 = seed;
64 int count = len;
65 int offset = 0;
66
67 // body
68 while (count >= 4) {
69 juint k1 = (data[offset] & 0x0FF)
70 | (data[offset + 1] & 0x0FF) << 8
71 | (data[offset + 2] & 0x0FF) << 16
72 | data[offset + 3] << 24;
73
74 count -= 4;
75 offset += 4;
76
77 k1 *= 0xcc9e2d51;
78 k1 = Integer_rotateLeft(k1, 15);
79 k1 *= 0x1b873593;
80
81 h1 ^= k1;
82 h1 = Integer_rotateLeft(h1, 13);
83 h1 = h1 * 5 + 0xe6546b64;
84 }
85
86 // tail
87
88 if (count > 0) {
89 juint k1 = 0;
90
91 switch (count) {
92 case 3:
93 k1 ^= (data[offset + 2] & 0xff) << 16;
94 // fall through
95 case 2:
96 k1 ^= (data[offset + 1] & 0xff) << 8;
97 // fall through
98 case 1:
99 k1 ^= (data[offset] & 0xff);
100 // fall through
101 default:
102 k1 *= 0xcc9e2d51;
103 k1 = Integer_rotateLeft(k1, 15);
104 k1 *= 0x1b873593;
105 h1 ^= k1;
106 }
107 }
108
109 // finalization
110 h1 ^= len;
111
112 // finalization mix force all bits of a hash block to avalanche
113 h1 ^= h1 >> 16;
114 h1 *= 0x85ebca6b;
115 h1 ^= h1 >> 13;
116 h1 *= 0xc2b2ae35;
117 h1 ^= h1 >> 16;
118
119 return h1;
120 }
121
122 // Murmur3 hashing for Strings
123 juint AltHashing::murmur3_32(juint seed, const jchar* data, int len) {
124 juint h1 = seed;
125
126 int off = 0;
127 int count = len;
128
129 // body
130 while (count >= 2) {
131 jchar d1 = data[off++] & 0xFFFF;
132 jchar d2 = data[off++];
133 juint k1 = (d1 | d2 << 16);
134
135 count -= 2;
136
137 k1 *= 0xcc9e2d51;
138 k1 = Integer_rotateLeft(k1, 15);
139 k1 *= 0x1b873593;
140
141 h1 ^= k1;
142 h1 = Integer_rotateLeft(h1, 13);
143 h1 = h1 * 5 + 0xe6546b64;
144 }
145
146 // tail
147
148 if (count > 0) {
149 juint k1 = (juint)data[off];
150
151 k1 *= 0xcc9e2d51;
152 k1 = Integer_rotateLeft(k1, 15);
153 k1 *= 0x1b873593;
154 h1 ^= k1;
155 }
156
157 // finalization
158 h1 ^= len * 2; // (Character.SIZE / Byte.SIZE);
159
160 // finalization mix force all bits of a hash block to avalanche
161 h1 ^= h1 >> 16;
162 h1 *= 0x85ebca6b;
163 h1 ^= h1 >> 13;
164 h1 *= 0xc2b2ae35;
165 h1 ^= h1 >> 16;
166
167 return h1;
168 }
169
170 // Hash used for the seed.
171 juint AltHashing::murmur3_32(juint seed, const jint* data, int len) {
172 juint h1 = seed;
173
174 int off = 0;
175 int end = len;
176
177 // body
178 while (off < end) {
179 juint k1 = (juint)data[off++];
180
181 k1 *= 0xcc9e2d51;
182 k1 = Integer_rotateLeft(k1, 15);
183 k1 *= 0x1b873593;
184
185 h1 ^= k1;
186 h1 = Integer_rotateLeft(h1, 13);
187 h1 = h1 * 5 + 0xe6546b64;
188 }
189
190 // tail (always empty, as body is always 32-bit chunks)
191
192 // finalization
193
194 h1 ^= len * 4; // (Integer.SIZE / Byte.SIZE);
195
196 // finalization mix force all bits of a hash block to avalanche
197 h1 ^= h1 >> 16;
198 h1 *= 0x85ebca6b;
199 h1 ^= h1 >> 13;
200 h1 *= 0xc2b2ae35;
201 h1 ^= h1 >> 16;
202
203 return h1;
204 }
205
206 juint AltHashing::murmur3_32(const jint* data, int len) {
207 return murmur3_32(0, data, len);
208 }