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}