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    }