1 /*
   2  * Copyright (c) 2017, 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.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 /**
  25  * @test
  26  * @modules jdk.incubator.vector
  27  */
  28 
  29 import jdk.incubator.vector.ByteVector;
  30 import jdk.incubator.vector.IntVector;
  31 import jdk.incubator.vector.Vector.Shape;
  32 import jdk.incubator.vector.Vector.Species;
  33 import jdk.incubator.vector.Vector;
  34 
  35 import java.nio.charset.StandardCharsets;
  36 import java.util.Arrays;
  37 import java.util.Properties;
  38 import java.util.SplittableRandom;
  39 
  40 import static java.util.stream.Collectors.joining;
  41 
  42 public class VectorHash {
  43 
  44     public static void main(String[] args) {
  45         Properties p = System.getProperties();
  46         p.forEach((k, v) -> {
  47             byte[] bk = k.toString().getBytes(StandardCharsets.UTF_8);
  48             byte[] bv = v.toString().getBytes(StandardCharsets.UTF_8);
  49             assertHashCode(bk);
  50             assertHashCode(bv);
  51         });
  52 
  53         String letters = new SplittableRandom().ints(1024, 'A', 'Z' + 1).
  54                 mapToObj(c -> Character.toString((char) c)).collect(joining());
  55         assertHashCode(letters.getBytes(StandardCharsets.UTF_8));
  56     }
  57 
  58     static void assertHashCode(byte[] b) {
  59         int expected = Arrays.hashCode(b);
  60         assertEquals(hashCodeUnrollExplicit(b), expected);
  61         assertEquals(hashCodeUnrollConstants(b), expected);
  62         assertEquals(hashCodeVector64(b), expected);
  63         assertEquals(hashCodeVector128(b), expected);
  64         assertEquals(hashCodeVector512Shift(b), expected);
  65     }
  66 
  67     static void assertEquals(Object a, Object b) {
  68         if (!a.equals(b)) throw new AssertionError();
  69     }
  70 
  71     static int hashCodeUnrollExplicit(byte[] a) {
  72         if (a == null)
  73             return 0;
  74 
  75         int h = 1;
  76         int i = 0;
  77         for (; i < (a.length & ~(8 - 1)); i += 8) {
  78             h = h * 31 * 31 * 31 * 31 * 31 * 31 * 31 * 31 +
  79                 a[i + 0] * 31 * 31 * 31 * 31 * 31 * 31 * 31 +
  80                 a[i + 1] * 31 * 31 * 31 * 31 * 31 * 31 +
  81                 a[i + 2] * 31 * 31 * 31 * 31 * 31 +
  82                 a[i + 3] * 31 * 31 * 31 * 31 +
  83                 a[i + 4] * 31 * 31 * 31 +
  84                 a[i + 5] * 31 * 31 +
  85                 a[i + 6] * 31 +
  86                 a[i + 7];
  87         }
  88 
  89         for (; i < a.length; i++) {
  90             h = 31 * h + a[i];
  91         }
  92         return h;
  93     }
  94 
  95     static int hashCodeUnrollConstants(byte[] a) {
  96         if (a == null)
  97             return 0;
  98 
  99         int h = 1;
 100         int i = 0;
 101         for (; i < (a.length & ~(8 - 1)); i += 8) {
 102             h = h * COEFF_31_TO_8 +
 103                 a[i + 0] * H_COEFF_8.get(0) +
 104                 a[i + 1] * H_COEFF_8.get(1) +
 105                 a[i + 2] * H_COEFF_8.get(2) +
 106                 a[i + 3] * H_COEFF_8.get(3) +
 107                 a[i + 4] * H_COEFF_8.get(4) +
 108                 a[i + 5] * H_COEFF_8.get(5) +
 109                 a[i + 6] * H_COEFF_8.get(6) +
 110                 a[i + 7] * H_COEFF_8.get(7);
 111         }
 112 
 113         for (; i < a.length; i++) {
 114             h = 31 * h + a[i];
 115         }
 116         return h;
 117     }
 118 
 119     static int hashCodeVector64(byte[] a) {
 120         int h = 1;
 121         int i = 0;
 122         for (; i < (a.length & ~(BYTE_64_SPECIES.length() - 1)); i += BYTE_64_SPECIES.length()) {
 123             ByteVector b = ByteVector.fromArray(BYTE_64_SPECIES, a, i);
 124             IntVector x = (IntVector) b.cast(INT_256_SPECIES);
 125             h = h * COEFF_31_TO_8 + x.mul(H_COEFF_8).addAll();
 126         }
 127 
 128         for (; i < a.length; i++) {
 129             h = 31 * h + a[i];
 130         }
 131         return h;
 132     }
 133 
 134     static int hashCodeVector128(byte[] a) {
 135         int h = 1;
 136         int i = 0;
 137         for (; i < (a.length & ~(BYTE_128_SPECIES.length() - 1)); i += BYTE_128_SPECIES.length()) {
 138             ByteVector b = ByteVector.fromArray(BYTE_128_SPECIES, a, i);
 139             IntVector x = (IntVector) b.cast(INT_512_SPECIES);
 140             h = h * COEFF_31_TO_16 + x.mul(H_COEFF_16).addAll();
 141         }
 142 
 143         for (; i < a.length; i++) {
 144             h = 31 * h + a[i];
 145         }
 146         return h;
 147     }
 148 
 149     static int hashCodeVector512Shift(byte[] a) {
 150         return hashCodeVectorGenericShift(a,
 151                                           BYTE_128_SPECIES,
 152                                           BYTE_512_SPECIES,
 153                                           INT_512_SPECIES,
 154                                           COEFF_31_TO_16,
 155                                           H_COEFF_16);
 156     }
 157 
 158     static int hashCodeVectorGenericShift(
 159             byte[] a,
 160             Species<Byte> bytesForIntsSpecies,
 161             Species<Byte> byteSpecies, Species<Integer> intSpecies,
 162             int top_h_coeff,
 163             IntVector v_h_coeff) {
 164         assert bytesForIntsSpecies.length() == intSpecies.length();
 165 
 166         int h = 1;
 167         int i = 0;
 168         for (; i < (a.length & ~(byteSpecies.length() - 1)); i += byteSpecies.length()) {
 169             ByteVector b = ByteVector.fromArray(byteSpecies, a, i);
 170 
 171             for (int j = 0; j < byteSpecies.length() / intSpecies.length(); j++) {
 172                 // Reduce the size of the byte vector and then cast to int
 173                 IntVector x = (IntVector)(b.reshape(bytesForIntsSpecies)).cast(intSpecies);
 174 
 175                 h = h * top_h_coeff + x.mul(v_h_coeff).addAll();
 176 
 177                 b = b.shiftEL(intSpecies.length());
 178             }
 179         }
 180 
 181         for (; i < a.length; i++) {
 182             h = 31 * h + a[i];
 183         }
 184         return h;
 185     }
 186 
 187     static final Species<Integer> INT_512_SPECIES = IntVector.SPECIES_512;
 188     static final Species<Integer> INT_256_SPECIES = IntVector.SPECIES_256;
 189     static final int COEFF_31_TO_16;
 190     static final IntVector H_COEFF_16;
 191 
 192     static final Species<Byte> BYTE_512_SPECIES = ByteVector.SPECIES_512;
 193     static final Species<Byte> BYTE_128_SPECIES = ByteVector.SPECIES_128;
 194     static final Species<Byte> BYTE_64_SPECIES = ByteVector.SPECIES_64;
 195     static final int COEFF_31_TO_8;
 196     static final IntVector H_COEFF_8;
 197 
 198     static {
 199         int[] a = new int[INT_256_SPECIES.length()];
 200         a[a.length - 1] = 1;
 201         for (int i = 1; i < a.length; i++) {
 202             a[a.length - 1 - i] = a[a.length - 1 - i + 1] * 31;
 203         }
 204 
 205         COEFF_31_TO_8 = a[0] * 31;
 206         H_COEFF_8 = IntVector.fromArray(INT_256_SPECIES, a, 0);
 207 
 208 
 209         a = new int[INT_512_SPECIES.length()];
 210         a[a.length - 1] = 1;
 211         for (int i = 1; i < a.length; i++) {
 212             a[a.length - 1 - i] = a[a.length - 1 - i + 1] * 31;
 213         }
 214 
 215         COEFF_31_TO_16 = a[0] * 31;
 216         H_COEFF_16 = IntVector.fromArray(INT_512_SPECIES, a, 0);
 217     }
 218 }