001 /* 002 * Copyright (c) 2012, Oracle and/or its affiliates. All rights reserved. 003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 004 * 005 * This code is free software; you can redistribute it and/or modify it 006 * under the terms of the GNU General Public License version 2 only, as 007 * published by the Free Software Foundation. Oracle designates this 008 * particular file as subject to the "Classpath" exception as provided 009 * by Oracle in the LICENSE file that accompanied this code. 010 * 011 * This code is distributed in the hope that it will be useful, but WITHOUT 012 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 013 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 014 * version 2 for more details (a copy is included in the LICENSE file that 015 * accompanied this code). 016 * 017 * You should have received a copy of the GNU General Public License version 018 * 2 along with this work; if not, write to the Free Software Foundation, 019 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 020 * 021 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 022 * or visit www.oracle.com if you need additional information or have any 023 * questions. 024 */ 025 package railo.commons.util.mod; 026 027 import java.util.Random; 028 029 import sun.misc.JavaLangAccess; 030 import sun.misc.SharedSecrets; 031 032 /** 033 * Hashing utilities. 034 * 035 * Little endian implementations of Murmur3 hashing. 036 */ 037 public class Hashing { 038 039 /** 040 * Static utility methods only. 041 */ 042 private Hashing() { 043 throw new Error("No instances"); 044 } 045 046 public static int murmur3_32(byte[] data) { 047 return murmur3_32(0, data, 0, data.length); 048 } 049 050 public static int murmur3_32(int seed, byte[] data) { 051 return murmur3_32(seed, data, 0, data.length); 052 } 053 054 @SuppressWarnings("fallthrough") 055 public static int murmur3_32(int seed, byte[] data, int offset, int len) { 056 int h1 = seed; 057 int count = len; 058 059 // body 060 while (count >= 4) { 061 int k1 = (data[offset] & 0x0FF) 062 | (data[offset + 1] & 0x0FF) << 8 063 | (data[offset + 2] & 0x0FF) << 16 064 | data[offset + 3] << 24; 065 066 count -= 4; 067 offset += 4; 068 069 k1 *= 0xcc9e2d51; 070 k1 = Integer.rotateLeft(k1, 15); 071 k1 *= 0x1b873593; 072 073 h1 ^= k1; 074 h1 = Integer.rotateLeft(h1, 13); 075 h1 = h1 * 5 + 0xe6546b64; 076 } 077 078 // tail 079 080 if (count > 0) { 081 int k1 = 0; 082 083 switch (count) { 084 case 3: 085 k1 ^= (data[offset + 2] & 0xff) << 16; 086 // fall through 087 case 2: 088 k1 ^= (data[offset + 1] & 0xff) << 8; 089 // fall through 090 case 1: 091 k1 ^= (data[offset] & 0xff); 092 // fall through 093 default: 094 k1 *= 0xcc9e2d51; 095 k1 = Integer.rotateLeft(k1, 15); 096 k1 *= 0x1b873593; 097 h1 ^= k1; 098 } 099 } 100 101 // finalization 102 103 h1 ^= len; 104 105 // finalization mix force all bits of a hash block to avalanche 106 h1 ^= h1 >>> 16; 107 h1 *= 0x85ebca6b; 108 h1 ^= h1 >>> 13; 109 h1 *= 0xc2b2ae35; 110 h1 ^= h1 >>> 16; 111 112 return h1; 113 } 114 115 public static int murmur3_32(char[] data) { 116 return murmur3_32(0, data, 0, data.length); 117 } 118 119 public static int murmur3_32(int seed, char[] data) { 120 return murmur3_32(seed, data, 0, data.length); 121 } 122 123 public static int murmur3_32(int seed, char[] data, int offset, int len) { 124 int h1 = seed; 125 126 int off = offset; 127 int count = len; 128 129 // body 130 while (count >= 2) { 131 int k1 = (data[off++] & 0xFFFF) | (data[off++] << 16); 132 133 count -= 2; 134 135 k1 *= 0xcc9e2d51; 136 k1 = Integer.rotateLeft(k1, 15); 137 k1 *= 0x1b873593; 138 139 h1 ^= k1; 140 h1 = Integer.rotateLeft(h1, 13); 141 h1 = h1 * 5 + 0xe6546b64; 142 } 143 144 // tail 145 146 if (count > 0) { 147 int k1 = data[off]; 148 149 k1 *= 0xcc9e2d51; 150 k1 = Integer.rotateLeft(k1, 15); 151 k1 *= 0x1b873593; 152 h1 ^= k1; 153 } 154 155 // finalization 156 157 h1 ^= len * (Character.SIZE / Byte.SIZE); 158 159 // finalization mix force all bits of a hash block to avalanche 160 h1 ^= h1 >>> 16; 161 h1 *= 0x85ebca6b; 162 h1 ^= h1 >>> 13; 163 h1 *= 0xc2b2ae35; 164 h1 ^= h1 >>> 16; 165 166 return h1; 167 } 168 169 public static int murmur3_32(int[] data) { 170 return murmur3_32(0, data, 0, data.length); 171 } 172 173 public static int murmur3_32(int seed, int[] data) { 174 return murmur3_32(seed, data, 0, data.length); 175 } 176 177 public static int murmur3_32(int seed, int[] data, int offset, int len) { 178 int h1 = seed; 179 180 int off = offset; 181 int end = offset + len; 182 183 // body 184 while (off < end) { 185 int k1 = data[off++]; 186 187 k1 *= 0xcc9e2d51; 188 k1 = Integer.rotateLeft(k1, 15); 189 k1 *= 0x1b873593; 190 191 h1 ^= k1; 192 h1 = Integer.rotateLeft(h1, 13); 193 h1 = h1 * 5 + 0xe6546b64; 194 } 195 196 // tail (always empty, as body is always 32-bit chunks) 197 198 // finalization 199 200 h1 ^= len * (Integer.SIZE / Byte.SIZE); 201 202 // finalization mix force all bits of a hash block to avalanche 203 h1 ^= h1 >>> 16; 204 h1 *= 0x85ebca6b; 205 h1 ^= h1 >>> 13; 206 h1 *= 0xc2b2ae35; 207 h1 ^= h1 >>> 16; 208 209 return h1; 210 } 211 212 /** 213 * Holds references to things that can't be initialized until after VM 214 * is fully booted. 215 */ 216 private static class Holder { 217 218 /** 219 * Used for generating per-instance hash seeds. 220 * 221 * We try to improve upon the default seeding. 222 */ 223 static final Random SEED_MAKER = new Random( 224 Double.doubleToRawLongBits(Math.random()) 225 ^ System.identityHashCode(Hashing.class) 226 ^ System.currentTimeMillis() 227 ^ System.nanoTime() 228 ^ Runtime.getRuntime().freeMemory()); 229 230 /** 231 * Access to {@code String.hash32()} 232 */ 233 static final JavaLangAccess LANG_ACCESS; 234 235 static { 236 LANG_ACCESS = SharedSecrets.getJavaLangAccess(); 237 if (null == LANG_ACCESS) { 238 throw new Error("Shared secrets not initialized"); 239 } 240 } 241 } 242 243 public static int randomHashSeed(Object instance) { 244 int seed; 245 if (sun.misc.VM.isBooted()) { 246 seed = Holder.SEED_MAKER.nextInt(); 247 } else { 248 // lower quality "random" seed value--still better than zero and not 249 // not practically reversible. 250 int hashing_seed[] = { 251 System.identityHashCode(Hashing.class), 252 System.identityHashCode(instance), 253 System.identityHashCode(Thread.currentThread()), 254 (int) Thread.currentThread().getId(), 255 (int) (System.currentTimeMillis() >>> 2), // resolution is poor 256 (int) (System.nanoTime() >>> 5), // resolution is poor 257 (int) (Runtime.getRuntime().freeMemory() >>> 4) // alloc min 258 }; 259 260 seed = murmur3_32(hashing_seed); 261 } 262 263 // force to non-zero. 264 return (0 != seed) ? seed : 1; 265 } 266 }