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      * Holds references to things that can't be initialized until after VM
 211      * is fully booted.
 212      */
 213     private static class Holder {
 214 
 215         /**
 216          * Access to {@code String.hash32()}
 217          */
 218         static final JavaLangAccess LANG_ACCESS;
 219 
 220         static {
 221             LANG_ACCESS = SharedSecrets.getJavaLangAccess();
 222             if (null == LANG_ACCESS) {
 223                 throw new Error("Shared secrets not initialized");
 224             }
 225         }
 226     }
 227 
 228     /**
 229      * Return a 32 bit hash value for the specified string. The algorithm is
 230      * unspecified but will be consistent within a VM instance.
 231      *
 232      * @param string String to be hashed.
 233      * @return hash value of the string.
 234      */
 235     public static int stringHash32(String string) {
 236         return Holder.LANG_ACCESS.getStringHash32(string);
 237     }
 238 
 239     /**
 240      * Return a non-zero 32-bit pseudo random value. The {@code instance} object
 241      * may be used as part of the value.
 242      *
 243      * @param instance an object to use if desired in choosing value.
 244      * @return a non-zero 32-bit pseudo random value.
 245      */
 246     public static int randomHashSeed(Object instance) {
 247         int seed;
 248         if (sun.misc.VM.isBooted()) {
 249             seed = ThreadLocalRandom.current().nextInt();
 250         } else {
 251             // lower quality "random" seed value--still better than zero and not
 252             // not practically reversible.
 253             int hashing_seed[] = {
 254                 System.identityHashCode(Hashing.class),
 255                 System.identityHashCode(instance),
 256                 System.identityHashCode(Thread.currentThread()),
 257                 (int) Thread.currentThread().getId(),
 258                 (int) (System.currentTimeMillis() >>> 2), // resolution is poor
 259                 (int) (System.nanoTime() >>> 5), // resolution is poor
 260                 (int) (Runtime.getRuntime().freeMemory() >>> 4) // alloc min
 261             };
 262 
 263             seed = murmur3_32(hashing_seed);
 264         }
 265 
 266         // force to non-zero.
 267         return (0 != seed) ? seed : 1;
 268     }
 269 }