altHashing.cpp revision 9056:dc9930a04ab0
1219974Smav/* 2219974Smav * Copyright (c) 2012, 2014, Oracle and/or its affiliates. All rights reserved. 3219974Smav * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4219974Smav * 5219974Smav * This code is free software; you can redistribute it and/or modify it 6219974Smav * under the terms of the GNU General Public License version 2 only, as 7219974Smav * published by the Free Software Foundation. 8219974Smav * 9219974Smav * This code is distributed in the hope that it will be useful, but WITHOUT 10219974Smav * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11219974Smav * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12219974Smav * version 2 for more details (a copy is included in the LICENSE file that 13219974Smav * accompanied this code). 14219974Smav * 15219974Smav * You should have received a copy of the GNU General Public License version 16219974Smav * 2 along with this work; if not, write to the Free Software Foundation, 17219974Smav * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18219974Smav * 19219974Smav * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20219974Smav * or visit www.oracle.com if you need additional information or have any 21219974Smav * questions. 22219974Smav * 23219974Smav */ 24219974Smav 25219974Smav#include "precompiled.hpp" 26219974Smav#include "classfile/altHashing.hpp" 27219974Smav#include "classfile/symbolTable.hpp" 28219974Smav#include "classfile/systemDictionary.hpp" 29219974Smav#include "oops/markOop.hpp" 30219974Smav#include "runtime/thread.hpp" 31219974Smav 32219974Smav// Get the hash code of the classes mirror if it exists, otherwise just 33219974Smav// return a random number, which is one of the possible hash code used for 34219974Smav// objects. We don't want to call the synchronizer hash code to install 35219974Smav// this value because it may safepoint. 36219974Smavintptr_t object_hash(Klass* k) { 37219974Smav intptr_t hc = k->java_mirror()->mark()->hash(); 38219974Smav return hc != markOopDesc::no_hash ? hc : os::random(); 39219974Smav} 40219974Smav 41219974Smav// Seed value used for each alternative hash calculated. 42219974Smavjuint AltHashing::compute_seed() { 43219974Smav jlong nanos = os::javaTimeNanos(); 44219974Smav jlong now = os::javaTimeMillis(); 45219974Smav int SEED_MATERIAL[8] = { 46219974Smav (int) object_hash(SystemDictionary::String_klass()), 47219974Smav (int) object_hash(SystemDictionary::System_klass()), 48219974Smav (int) os::random(), // current thread isn't a java thread 49219974Smav (int) (((julong)nanos) >> 32), 50219974Smav (int) nanos, 51219974Smav (int) (((julong)now) >> 32), 52235874Smav (int) now, 53235874Smav (int) (os::javaTimeNanos() >> 2) 54219974Smav }; 55219974Smav 56219974Smav return murmur3_32(SEED_MATERIAL, 8); 57219974Smav} 58219974Smav 59219974Smav 60235874Smav// Murmur3 hashing for Symbol 61235874Smavjuint AltHashing::murmur3_32(juint seed, const jbyte* data, int len) { 62235874Smav juint h1 = seed; 63235874Smav int count = len; 64235874Smav int offset = 0; 65235874Smav 66235874Smav // body 67235874Smav while (count >= 4) { 68219974Smav juint k1 = (data[offset] & 0x0FF) 69219974Smav | (data[offset + 1] & 0x0FF) << 8 70219974Smav | (data[offset + 2] & 0x0FF) << 16 71219974Smav | data[offset + 3] << 24; 72219974Smav 73219974Smav count -= 4; 74219974Smav offset += 4; 75219974Smav 76219974Smav k1 *= 0xcc9e2d51; 77219974Smav k1 = Integer_rotateLeft(k1, 15); 78219974Smav k1 *= 0x1b873593; 79219974Smav 80219974Smav h1 ^= k1; 81219974Smav h1 = Integer_rotateLeft(h1, 13); 82219974Smav h1 = h1 * 5 + 0xe6546b64; 83219974Smav } 84219974Smav 85219974Smav // tail 86219974Smav 87219974Smav if (count > 0) { 88219974Smav juint k1 = 0; 89219974Smav 90219974Smav switch (count) { 91219974Smav case 3: 92219974Smav k1 ^= (data[offset + 2] & 0xff) << 16; 93219974Smav // fall through 94219974Smav case 2: 95219974Smav k1 ^= (data[offset + 1] & 0xff) << 8; 96219974Smav // fall through 97219974Smav case 1: 98219974Smav k1 ^= (data[offset] & 0xff); 99219974Smav // fall through 100219974Smav default: 101219974Smav k1 *= 0xcc9e2d51; 102219974Smav k1 = Integer_rotateLeft(k1, 15); 103219974Smav k1 *= 0x1b873593; 104219974Smav h1 ^= k1; 105219974Smav } 106219974Smav } 107235874Smav 108235874Smav // finalization 109235874Smav h1 ^= len; 110235874Smav 111235874Smav // finalization mix force all bits of a hash block to avalanche 112235874Smav h1 ^= h1 >> 16; 113235874Smav h1 *= 0x85ebca6b; 114235874Smav h1 ^= h1 >> 13; 115219974Smav h1 *= 0xc2b2ae35; 116219974Smav h1 ^= h1 >> 16; 117219974Smav 118219974Smav return h1; 119219974Smav} 120219974Smav 121219974Smav// Murmur3 hashing for Strings 122219974Smavjuint AltHashing::murmur3_32(juint seed, const jchar* data, int len) { 123219974Smav juint h1 = seed; 124219974Smav 125219974Smav int off = 0; 126219974Smav int count = len; 127219974Smav 128219974Smav // body 129219974Smav while (count >= 2) { 130219974Smav jchar d1 = data[off++] & 0xFFFF; 131219974Smav jchar d2 = data[off++]; 132219974Smav juint k1 = (d1 | d2 << 16); 133219974Smav 134219974Smav count -= 2; 135219974Smav 136219974Smav k1 *= 0xcc9e2d51; 137219974Smav k1 = Integer_rotateLeft(k1, 15); 138219974Smav k1 *= 0x1b873593; 139219974Smav 140219974Smav h1 ^= k1; 141219974Smav h1 = Integer_rotateLeft(h1, 13); 142219974Smav h1 = h1 * 5 + 0xe6546b64; 143219974Smav } 144219974Smav 145219974Smav // tail 146219974Smav 147219974Smav if (count > 0) { 148219974Smav juint k1 = (juint)data[off]; 149219974Smav 150219974Smav k1 *= 0xcc9e2d51; 151219974Smav k1 = Integer_rotateLeft(k1, 15); 152219974Smav k1 *= 0x1b873593; 153219974Smav h1 ^= k1; 154219974Smav } 155219974Smav 156219974Smav // finalization 157219974Smav h1 ^= len * 2; // (Character.SIZE / Byte.SIZE); 158219974Smav 159219974Smav // finalization mix force all bits of a hash block to avalanche 160219974Smav h1 ^= h1 >> 16; 161219974Smav h1 *= 0x85ebca6b; 162219974Smav h1 ^= h1 >> 13; 163219974Smav h1 *= 0xc2b2ae35; 164219974Smav h1 ^= h1 >> 16; 165219974Smav 166219974Smav return h1; 167219974Smav} 168219974Smav 169219974Smav// Hash used for the seed. 170219974Smavjuint AltHashing::murmur3_32(juint seed, const int* data, int len) { 171219974Smav juint h1 = seed; 172219974Smav 173219974Smav int off = 0; 174 int end = len; 175 176 // body 177 while (off < end) { 178 juint k1 = (juint)data[off++]; 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 } 188 189 // tail (always empty, as body is always 32-bit chunks) 190 191 // finalization 192 193 h1 ^= len * 4; // (Integer.SIZE / Byte.SIZE); 194 195 // finalization mix force all bits of a hash block to avalanche 196 h1 ^= h1 >> 16; 197 h1 *= 0x85ebca6b; 198 h1 ^= h1 >> 13; 199 h1 *= 0xc2b2ae35; 200 h1 ^= h1 >> 16; 201 202 return h1; 203} 204 205juint AltHashing::murmur3_32(const int* data, int len) { 206 return murmur3_32(0, data, len); 207} 208 209#ifndef PRODUCT 210// Overloaded versions for internal test. 211juint AltHashing::murmur3_32(const jbyte* data, int len) { 212 return murmur3_32(0, data, len); 213} 214 215juint AltHashing::murmur3_32(const jchar* data, int len) { 216 return murmur3_32(0, data, len); 217} 218 219// Internal test for alternate hashing. Translated from JDK version 220// test/sun/misc/Hashing.java 221static const jbyte ONE_BYTE[] = { (jbyte) 0x80}; 222static const jbyte TWO_BYTE[] = { (jbyte) 0x80, (jbyte) 0x81}; 223static const jchar ONE_CHAR[] = { (jchar) 0x8180}; 224static const jbyte THREE_BYTE[] = { (jbyte) 0x80, (jbyte) 0x81, (jbyte) 0x82}; 225static const jbyte FOUR_BYTE[] = { (jbyte) 0x80, (jbyte) 0x81, (jbyte) 0x82, (jbyte) 0x83}; 226static const jchar TWO_CHAR[] = { (jchar) 0x8180, (jchar) 0x8382}; 227static const jint ONE_INT[] = { 0x83828180}; 228static const jbyte SIX_BYTE[] = { (jbyte) 0x80, (jbyte) 0x81, (jbyte) 0x82, (jbyte) 0x83, (jbyte) 0x84, (jbyte) 0x85}; 229static const jchar THREE_CHAR[] = { (jchar) 0x8180, (jchar) 0x8382, (jchar) 0x8584}; 230static const jbyte EIGHT_BYTE[] = { 231 (jbyte) 0x80, (jbyte) 0x81, (jbyte) 0x82, 232 (jbyte) 0x83, (jbyte) 0x84, (jbyte) 0x85, 233 (jbyte) 0x86, (jbyte) 0x87}; 234static const jchar FOUR_CHAR[] = { 235 (jchar) 0x8180, (jchar) 0x8382, 236 (jchar) 0x8584, (jchar) 0x8786}; 237 238static const jint TWO_INT[] = { 0x83828180, 0x87868584}; 239 240static const juint MURMUR3_32_X86_CHECK_VALUE = 0xB0F57EE3; 241 242void AltHashing::testMurmur3_32_ByteArray() { 243 // printf("testMurmur3_32_ByteArray\n"); 244 245 jbyte vector[256]; 246 jbyte hashes[4 * 256]; 247 248 for (int i = 0; i < 256; i++) { 249 vector[i] = (jbyte) i; 250 } 251 252 // Hash subranges {}, {0}, {0,1}, {0,1,2}, ..., {0,...,255} 253 for (int i = 0; i < 256; i++) { 254 juint hash = murmur3_32(256 - i, vector, i); 255 hashes[i * 4] = (jbyte) hash; 256 hashes[i * 4 + 1] = (jbyte)(hash >> 8); 257 hashes[i * 4 + 2] = (jbyte)(hash >> 16); 258 hashes[i * 4 + 3] = (jbyte)(hash >> 24); 259 } 260 261 // hash to get const result. 262 juint final_hash = murmur3_32(hashes, 4*256); 263 264 assert (MURMUR3_32_X86_CHECK_VALUE == final_hash, 265 "Calculated hash result not as expected. Expected %08X got %08X\n", 266 MURMUR3_32_X86_CHECK_VALUE, 267 final_hash); 268} 269 270void AltHashing::testEquivalentHashes() { 271 juint jbytes, jchars, ints; 272 273 // printf("testEquivalentHashes\n"); 274 275 jbytes = murmur3_32(TWO_BYTE, 2); 276 jchars = murmur3_32(ONE_CHAR, 1); 277 assert (jbytes == jchars, 278 "Hashes did not match. b:%08x != c:%08x\n", jbytes, jchars); 279 280 jbytes = murmur3_32(FOUR_BYTE, 4); 281 jchars = murmur3_32(TWO_CHAR, 2); 282 ints = murmur3_32(ONE_INT, 1); 283 assert ((jbytes == jchars) && (jbytes == ints), 284 "Hashes did not match. b:%08x != c:%08x != i:%08x\n", jbytes, jchars, ints); 285 286 jbytes = murmur3_32(SIX_BYTE, 6); 287 jchars = murmur3_32(THREE_CHAR, 3); 288 assert (jbytes == jchars, 289 "Hashes did not match. b:%08x != c:%08x\n", jbytes, jchars); 290 291 jbytes = murmur3_32(EIGHT_BYTE, 8); 292 jchars = murmur3_32(FOUR_CHAR, 4); 293 ints = murmur3_32(TWO_INT, 2); 294 assert ((jbytes == jchars) && (jbytes == ints), 295 "Hashes did not match. b:%08x != c:%08x != i:%08x\n", jbytes, jchars, ints); 296} 297 298// Returns true if the alternate hashcode is correct 299void AltHashing::test_alt_hash() { 300 testMurmur3_32_ByteArray(); 301 testEquivalentHashes(); 302} 303#endif // PRODUCT 304