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 }