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 }