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 intptr_t hc = k->java_mirror()->mark().hash(); 59 return hc != markWord::no_hash ? hc : os::random(); 60 } 61 62 // Seed value used for each alternative hash calculated. 63 uint64_t AltHashing::compute_seed() { 64 uint64_t nanos = os::javaTimeNanos(); 65 uint64_t now = os::javaTimeMillis(); 66 uint32_t SEED_MATERIAL[8] = { 67 (uint32_t) object_hash(vmClasses::String_klass()), 68 (uint32_t) object_hash(vmClasses::System_klass()), 69 (uint32_t) os::random(), // current thread isn't a java thread 70 (uint32_t) (((uint64_t)nanos) >> 32), 71 (uint32_t) nanos, 72 (uint32_t) (((uint64_t)now) >> 32), 73 (uint32_t) now, 74 (uint32_t) (os::javaTimeNanos() >> 2) 75 }; 76 77 return halfsiphash_64(SEED_MATERIAL, 8); 78 } 79 80 // utility function copied from java/lang/Integer 81 static uint32_t Integer_rotateLeft(uint32_t i, int distance) { 82 return (i << distance) | (i >> (32 - distance)); 83 } 84 85 static void halfsiphash_rounds(uint32_t v[4], int rounds) { 86 while (rounds-- > 0) { 87 v[0] += v[1]; 88 v[1] = Integer_rotateLeft(v[1], 5); 89 v[1] ^= v[0]; 90 v[0] = Integer_rotateLeft(v[0], 16); 91 v[2] += v[3]; 92 v[3] = Integer_rotateLeft(v[3], 8); 93 v[3] ^= v[2]; 94 v[0] += v[3]; 95 v[3] = Integer_rotateLeft(v[3], 7); 96 v[3] ^= v[0]; 97 v[2] += v[1]; 98 v[1] = Integer_rotateLeft(v[1], 13); 99 v[1] ^= v[2]; 100 v[2] = Integer_rotateLeft(v[2], 16); 101 } 102 } 103 104 static void halfsiphash_adddata(uint32_t v[4], uint32_t newdata, int rounds) { 105 v[3] ^= newdata; 106 halfsiphash_rounds(v, rounds); 107 v[0] ^= newdata; 108 } 109 110 static void halfsiphash_init32(uint32_t v[4], uint64_t seed) { 111 v[0] = seed & 0xffffffff; 112 v[1] = (uint32_t)(seed >> 32); 113 v[2] = 0x6c796765 ^ v[0]; 114 v[3] = 0x74656462 ^ v[1]; 115 } 116 117 static void halfsiphash_init64(uint32_t v[4], uint64_t seed) { 118 halfsiphash_init32(v, seed); 119 v[1] ^= 0xee; 120 } 121 122 static uint32_t halfsiphash_finish32(uint32_t v[4], int rounds) { 123 v[2] ^= 0xff; 124 halfsiphash_rounds(v, rounds); 125 return (v[1] ^ v[3]); 126 } 127 128 static uint64_t halfsiphash_finish64(uint32_t v[4], int rounds) { 129 uint64_t rv; 130 v[2] ^= 0xee; 131 halfsiphash_rounds(v, rounds); 132 rv = v[1] ^ v[3]; 133 v[1] ^= 0xdd; 134 halfsiphash_rounds(v, rounds); 135 rv |= (uint64_t)(v[1] ^ v[3]) << 32; 136 return rv; 137 } 138 139 // HalfSipHash-2-4 (32-bit output) for Symbols 140 uint32_t AltHashing::halfsiphash_32(uint64_t seed, const void* in, int len) { 141 142 const unsigned char* data = (const unsigned char*)in; 143 uint32_t v[4]; 144 uint32_t newdata; 145 int off = 0; 146 int count = len; 147 148 halfsiphash_init32(v, seed); 149 150 // body 151 while (count >= 4) { 152 153 // Avoid sign extension with 0x0ff 154 newdata = (data[off] & 0x0FF) 155 | (data[off + 1] & 0x0FF) << 8 156 | (data[off + 2] & 0x0FF) << 16 157 | data[off + 3] << 24; 158 159 count -= 4; 160 off += 4; 161 162 halfsiphash_adddata(v, newdata, 2); 163 } 164 165 // tail 166 newdata = ((uint32_t)len) << 24; // (Byte.SIZE / Byte.SIZE); 167 168 if (count > 0) { 169 switch (count) { 170 case 3: 171 newdata |= (data[off + 2] & 0x0ff) << 16; 172 // fall through 173 case 2: 174 newdata |= (data[off + 1] & 0x0ff) << 8; 175 // fall through 176 case 1: 177 newdata |= (data[off] & 0x0ff); 178 // fall through 179 } 180 } 181 182 halfsiphash_adddata(v, newdata, 2); 183 184 // finalization 185 return halfsiphash_finish32(v, 4); 186 } 187 188 // HalfSipHash-2-4 (32-bit output) for Strings 189 uint32_t AltHashing::halfsiphash_32(uint64_t seed, const uint16_t* data, int len) { 190 uint32_t v[4]; 191 uint32_t newdata; 192 int off = 0; 193 int count = len; 194 195 halfsiphash_init32(v, seed); 196 197 // body 198 while (count >= 2) { 199 uint16_t d1 = data[off++] & 0x0FFFF; 200 uint16_t d2 = data[off++]; 201 newdata = (d1 | d2 << 16); 202 203 count -= 2; 204 205 halfsiphash_adddata(v, newdata, 2); 206 } 207 208 // tail 209 newdata = ((uint32_t)len * 2) << 24; // (Character.SIZE / Byte.SIZE); 210 if (count > 0) { 211 newdata |= (uint32_t)data[off]; 212 } 213 halfsiphash_adddata(v, newdata, 2); 214 215 // finalization 216 return halfsiphash_finish32(v, 4); 217 } 218 219 // HalfSipHash-2-4 (64-bit output) for integers (used to create seed) 220 uint64_t AltHashing::halfsiphash_64(uint64_t seed, const uint32_t* data, int len) { 221 uint32_t v[4]; 222 223 int off = 0; 224 int end = len; 225 226 halfsiphash_init64(v, seed); 227 228 // body 229 while (off < end) { 230 halfsiphash_adddata(v, (uint32_t)data[off++], 2); 231 } 232 233 // tail (always empty, as body is always 32-bit chunks) 234 235 // finalization 236 halfsiphash_adddata(v, ((uint32_t)len * 4) << 24, 2); // (Integer.SIZE / Byte.SIZE); 237 return halfsiphash_finish64(v, 4); 238 } 239 240 // HalfSipHash-2-4 (64-bit output) for integers (used to create seed) 241 uint64_t AltHashing::halfsiphash_64(const uint32_t* data, int len) { 242 return halfsiphash_64((uint64_t)0, data, len); 243 }