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 * Return a non-zero 32-bit pseudo random value. The {@code instance} object 211 * may be used as part of the value. 212 * 213 * @param instance an object to use if desired in choosing value. 214 * @return a non-zero 32-bit pseudo random value. 215 */ 216 public static int randomHashSeed(Object instance) { 217 int seed; 218 if (sun.misc.VM.isBooted()) { 219 seed = ThreadLocalRandom.current().nextInt(); 220 } else { 221 // lower quality "random" seed value--still better than zero and not 222 // not practically reversible. 223 int hashing_seed[] = { 224 System.identityHashCode(Hashing.class), 225 System.identityHashCode(instance), 226 System.identityHashCode(Thread.currentThread()), 227 (int) Thread.currentThread().getId(), 228 (int) (System.currentTimeMillis() >>> 2), // resolution is poor 229 (int) (System.nanoTime() >>> 5), // resolution is poor 230 (int) (Runtime.getRuntime().freeMemory() >>> 4) // alloc min 231 }; 232 233 seed = murmur3_32(hashing_seed); 234 } 235 236 // force to non-zero. 237 return (0 != seed) ? seed : 1; 238 } 239 }