1 /* 2 * Copyright (c) 2012, 2025, 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 /* 26 * halfsiphash code adapted from reference implementation 27 * (https://github.com/veorq/SipHash/blob/master/halfsiphash.c) 28 * which is distributed with the following copyright: 29 */ 30 31 /* 32 SipHash reference C implementation 33 34 Copyright (c) 2016 Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com> 35 36 To the extent possible under law, the author(s) have dedicated all copyright 37 and related and neighboring rights to this software to the public domain 38 worldwide. This software is distributed without any warranty. 39 40 You should have received a copy of the CC0 Public Domain Dedication along 41 with 42 this software. If not, see 43 <http://creativecommons.org/publicdomain/zero/1.0/>. 44 */ 45 46 #include "classfile/altHashing.hpp" 47 #include "classfile/vmClasses.hpp" 48 #include "oops/klass.inline.hpp" 49 #include "oops/markWord.hpp" 50 #include "oops/oop.inline.hpp" 51 #include "runtime/os.hpp" 52 53 // Get the hash code of the classes mirror if it exists, otherwise just 54 // return a random number, which is one of the possible hash code used for 55 // objects. We don't want to call the synchronizer hash code to install 56 // this value because it may safepoint. 57 static intptr_t object_hash(Klass* k) { 58 if (UseCompactObjectHeaders) { 59 return os::random(); 60 } 61 intptr_t hc = k->java_mirror()->mark().hash(); 62 return hc != markWord::no_hash ? hc : os::random(); 63 } 64 65 // Seed value used for each alternative hash calculated. 66 uint64_t AltHashing::compute_seed() { 67 uint64_t nanos = os::javaTimeNanos(); 68 uint64_t now = os::javaTimeMillis(); 69 uint32_t SEED_MATERIAL[8] = { 70 (uint32_t) object_hash(vmClasses::String_klass()), 71 (uint32_t) object_hash(vmClasses::System_klass()), 72 (uint32_t) os::random(), // current thread isn't a java thread 73 (uint32_t) (((uint64_t)nanos) >> 32), 74 (uint32_t) nanos, 75 (uint32_t) (((uint64_t)now) >> 32), 76 (uint32_t) now, 77 (uint32_t) (os::javaTimeNanos() >> 2) 78 }; 79 80 return halfsiphash_64(SEED_MATERIAL, 8); 81 } 82 83 // utility function copied from java/lang/Integer 84 static uint32_t Integer_rotateLeft(uint32_t i, int distance) { 85 return (i << distance) | (i >> (32 - distance)); 86 } 87 88 static void halfsiphash_rounds(uint32_t v[4], int rounds) { 89 while (rounds-- > 0) { 90 v[0] += v[1]; 91 v[1] = Integer_rotateLeft(v[1], 5); 92 v[1] ^= v[0]; 93 v[0] = Integer_rotateLeft(v[0], 16); 94 v[2] += v[3]; 95 v[3] = Integer_rotateLeft(v[3], 8); 96 v[3] ^= v[2]; 97 v[0] += v[3]; 98 v[3] = Integer_rotateLeft(v[3], 7); 99 v[3] ^= v[0]; 100 v[2] += v[1]; 101 v[1] = Integer_rotateLeft(v[1], 13); 102 v[1] ^= v[2]; 103 v[2] = Integer_rotateLeft(v[2], 16); 104 } 105 } 106 107 static void halfsiphash_adddata(uint32_t v[4], uint32_t newdata, int rounds) { 108 v[3] ^= newdata; 109 halfsiphash_rounds(v, rounds); 110 v[0] ^= newdata; 111 } 112 113 static void halfsiphash_init32(uint32_t v[4], uint64_t seed) { 114 v[0] = seed & 0xffffffff; 115 v[1] = (uint32_t)(seed >> 32); 116 v[2] = 0x6c796765 ^ v[0]; 117 v[3] = 0x74656462 ^ v[1]; 118 } 119 120 static void halfsiphash_init64(uint32_t v[4], uint64_t seed) { 121 halfsiphash_init32(v, seed); 122 v[1] ^= 0xee; 123 } 124 125 static uint32_t halfsiphash_finish32(uint32_t v[4], int rounds) { 126 v[2] ^= 0xff; 127 halfsiphash_rounds(v, rounds); 128 return (v[1] ^ v[3]); 129 } 130 131 static uint64_t halfsiphash_finish64(uint32_t v[4], int rounds) { 132 uint64_t rv; 133 v[2] ^= 0xee; 134 halfsiphash_rounds(v, rounds); 135 rv = v[1] ^ v[3]; 136 v[1] ^= 0xdd; 137 halfsiphash_rounds(v, rounds); 138 rv |= (uint64_t)(v[1] ^ v[3]) << 32; 139 return rv; 140 } 141 142 // HalfSipHash-2-4 (32-bit output) for Symbols 143 uint32_t AltHashing::halfsiphash_32(uint64_t seed, const void* in, int len) { 144 145 const unsigned char* data = (const unsigned char*)in; 146 uint32_t v[4]; 147 uint32_t newdata; 148 int off = 0; 149 int count = len; 150 151 halfsiphash_init32(v, seed); 152 153 // body 154 while (count >= 4) { 155 156 // Avoid sign extension with 0x0ff 157 newdata = (data[off] & 0x0FF) 158 | (data[off + 1] & 0x0FF) << 8 159 | (data[off + 2] & 0x0FF) << 16 160 | data[off + 3] << 24; 161 162 count -= 4; 163 off += 4; 164 165 halfsiphash_adddata(v, newdata, 2); 166 } 167 168 // tail 169 newdata = ((uint32_t)len) << 24; // (Byte.SIZE / Byte.SIZE); 170 171 if (count > 0) { 172 switch (count) { 173 case 3: 174 newdata |= (data[off + 2] & 0x0ff) << 16; 175 // fall through 176 case 2: 177 newdata |= (data[off + 1] & 0x0ff) << 8; 178 // fall through 179 case 1: 180 newdata |= (data[off] & 0x0ff); 181 // fall through 182 } 183 } 184 185 halfsiphash_adddata(v, newdata, 2); 186 187 // finalization 188 return halfsiphash_finish32(v, 4); 189 } 190 191 // HalfSipHash-2-4 (32-bit output) for Strings 192 uint32_t AltHashing::halfsiphash_32(uint64_t seed, const uint16_t* data, int len) { 193 uint32_t v[4]; 194 uint32_t newdata; 195 int off = 0; 196 int count = len; 197 198 halfsiphash_init32(v, seed); 199 200 // body 201 while (count >= 2) { 202 uint16_t d1 = data[off++] & 0x0FFFF; 203 uint16_t d2 = data[off++]; 204 newdata = (d1 | d2 << 16); 205 206 count -= 2; 207 208 halfsiphash_adddata(v, newdata, 2); 209 } 210 211 // tail 212 newdata = ((uint32_t)len * 2) << 24; // (Character.SIZE / Byte.SIZE); 213 if (count > 0) { 214 newdata |= (uint32_t)data[off]; 215 } 216 halfsiphash_adddata(v, newdata, 2); 217 218 // finalization 219 return halfsiphash_finish32(v, 4); 220 } 221 222 // HalfSipHash-2-4 (64-bit output) for integers (used to create seed) 223 uint64_t AltHashing::halfsiphash_64(uint64_t seed, const uint32_t* data, int len) { 224 uint32_t v[4]; 225 226 int off = 0; 227 int end = len; 228 229 halfsiphash_init64(v, seed); 230 231 // body 232 while (off < end) { 233 halfsiphash_adddata(v, (uint32_t)data[off++], 2); 234 } 235 236 // tail (always empty, as body is always 32-bit chunks) 237 238 // finalization 239 halfsiphash_adddata(v, ((uint32_t)len * 4) << 24, 2); // (Integer.SIZE / Byte.SIZE); 240 return halfsiphash_finish64(v, 4); 241 } 242 243 // HalfSipHash-2-4 (64-bit output) for integers (used to create seed) 244 uint64_t AltHashing::halfsiphash_64(const uint32_t* data, int len) { 245 return halfsiphash_64((uint64_t)0, data, len); 246 }