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