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 }