1 /* 2 * Copyright (c) 2012, 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. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 package sun.misc; 26 27 import java.util.concurrent.ThreadLocalRandom; 28 29 /** 30 * Hashing utilities. 31 * 32 * Little endian implementations of Murmur3 hashing. 33 */ 34 public class Hashing { 35 36 /** 37 * Static utility methods only. 38 */ 39 private Hashing() { 40 throw new Error("No instances"); 41 } 42 43 public static int murmur3_32(byte[] data) { 44 return murmur3_32(0, data, 0, data.length); 45 } 46 47 public static int murmur3_32(int seed, byte[] data) { 48 return murmur3_32(seed, data, 0, data.length); 49 } 50 51 @SuppressWarnings("fallthrough") 52 public static int murmur3_32(int seed, byte[] data, int offset, int len) { 53 int h1 = seed; 54 int count = len; 55 56 // body 57 while (count >= 4) { 58 int k1 = (data[offset] & 0x0FF) 59 | (data[offset + 1] & 0x0FF) << 8 60 | (data[offset + 2] & 0x0FF) << 16 61 | data[offset + 3] << 24; 62 63 count -= 4; 64 offset += 4; 65 66 k1 *= 0xcc9e2d51; 67 k1 = Integer.rotateLeft(k1, 15); 68 k1 *= 0x1b873593; 69 70 h1 ^= k1; 71 h1 = Integer.rotateLeft(h1, 13); 72 h1 = h1 * 5 + 0xe6546b64; 73 } 74 75 // tail 76 77 if (count > 0) { 78 int k1 = 0; 79 80 switch (count) { 81 case 3: 82 k1 ^= (data[offset + 2] & 0xff) << 16; 83 // fall through 84 case 2: 85 k1 ^= (data[offset + 1] & 0xff) << 8; 86 // fall through 87 case 1: 88 k1 ^= (data[offset] & 0xff); 89 // fall through 90 default: 91 k1 *= 0xcc9e2d51; 92 k1 = Integer.rotateLeft(k1, 15); 93 k1 *= 0x1b873593; 94 h1 ^= k1; 95 } 96 } 97 98 // finalization 99 100 h1 ^= len; 101 102 // finalization mix force all bits of a hash block to avalanche 103 h1 ^= h1 >>> 16; 104 h1 *= 0x85ebca6b; 105 h1 ^= h1 >>> 13; 106 h1 *= 0xc2b2ae35; 107 h1 ^= h1 >>> 16; 108 109 return h1; 110 } 111 112 public static int murmur3_32(char[] data) { 113 return murmur3_32(0, data, 0, data.length); 114 } 115 116 public static int murmur3_32(int seed, char[] data) { 117 return murmur3_32(seed, data, 0, data.length); 118 } 119 120 public static int murmur3_32(int seed, char[] data, int offset, int len) { 121 int h1 = seed; 122 123 int off = offset; 124 int count = len; 125 126 // body 127 while (count >= 2) { 128 int k1 = (data[off++] & 0xFFFF) | (data[off++] << 16); 129 130 count -= 2; 131 132 k1 *= 0xcc9e2d51; 133 k1 = Integer.rotateLeft(k1, 15); 134 k1 *= 0x1b873593; 135 136 h1 ^= k1; 137 h1 = Integer.rotateLeft(h1, 13); 138 h1 = h1 * 5 + 0xe6546b64; 139 } 140 141 // tail 142 143 if (count > 0) { 144 int k1 = data[off]; 145 146 k1 *= 0xcc9e2d51; 147 k1 = Integer.rotateLeft(k1, 15); 148 k1 *= 0x1b873593; 149 h1 ^= k1; 150 } 151 152 // finalization 153 154 h1 ^= len * (Character.SIZE / Byte.SIZE); 155 156 // finalization mix force all bits of a hash block to avalanche 157 h1 ^= h1 >>> 16; 158 h1 *= 0x85ebca6b; 159 h1 ^= h1 >>> 13; 160 h1 *= 0xc2b2ae35; 161 h1 ^= h1 >>> 16; 162 163 return h1; 164 } 165 166 public static int murmur3_32(int[] data) { 167 return murmur3_32(0, data, 0, data.length); 168 } 169 170 public static int murmur3_32(int seed, int[] data) { 171 return murmur3_32(seed, data, 0, data.length); 172 } 173 174 public static int murmur3_32(int seed, int[] data, int offset, int len) { 175 int h1 = seed; 176 177 int off = offset; 178 int end = offset + len; 179 180 // body 181 while (off < end) { 182 int k1 = data[off++]; 183 184 k1 *= 0xcc9e2d51; 185 k1 = Integer.rotateLeft(k1, 15); 186 k1 *= 0x1b873593; 187 188 h1 ^= k1; 189 h1 = Integer.rotateLeft(h1, 13); 190 h1 = h1 * 5 + 0xe6546b64; 191 } 192 193 // tail (always empty, as body is always 32-bit chunks) 194 195 // finalization 196 197 h1 ^= len * (Integer.SIZE / Byte.SIZE); 198 199 // finalization mix force all bits of a hash block to avalanche 200 h1 ^= h1 >>> 16; 201 h1 *= 0x85ebca6b; 202 h1 ^= h1 >>> 13; 203 h1 *= 0xc2b2ae35; 204 h1 ^= h1 >>> 16; 205 206 return h1; 207 } 208 209 /** 210 * Holds references to things that can't be initialized until after VM 211 * is fully booted. 212 */ 213 private static class Holder { 214 215 /** 216 * Access to {@code String.hash32()} 217 */ 218 static final JavaLangAccess LANG_ACCESS; 219 220 static { 221 LANG_ACCESS = SharedSecrets.getJavaLangAccess(); 222 if (null == LANG_ACCESS) { 223 throw new Error("Shared secrets not initialized"); 224 } 225 } 226 } 227 228 /** 229 * Return a 32 bit hash value for the specified string. The algorithm is 230 * unspecified but will be consistent within a VM instance. 231 * 232 * @param string String to be hashed. 233 * @return hash value of the string. 234 */ 235 public static int stringHash32(String string) { 236 return Holder.LANG_ACCESS.getStringHash32(string); 237 } 238 239 /** 240 * Return a non-zero 32-bit pseudo random value. The {@code instance} object 241 * may be used as part of the value. 242 * 243 * @param instance an object to use if desired in choosing value. 244 * @return a non-zero 32-bit pseudo random value. 245 */ 246 public static int randomHashSeed(Object instance) { 247 int seed; 248 if (sun.misc.VM.isBooted()) { 249 seed = ThreadLocalRandom.current().nextInt(); 250 } else { 251 // lower quality "random" seed value--still better than zero and not 252 // not practically reversible. 253 int hashing_seed[] = { 254 System.identityHashCode(Hashing.class), 255 System.identityHashCode(instance), 256 System.identityHashCode(Thread.currentThread()), 257 (int) Thread.currentThread().getId(), 258 (int) (System.currentTimeMillis() >>> 2), // resolution is poor 259 (int) (System.nanoTime() >>> 5), // resolution is poor 260 (int) (Runtime.getRuntime().freeMemory() >>> 4) // alloc min 261 }; 262 263 seed = murmur3_32(hashing_seed); 264 } 265 266 // force to non-zero. 267 return (0 != seed) ? seed : 1; 268 } 269 }