coleenp@3865: /*
vkempik@10008:  * Copyright (c) 2012, 2020, Oracle and/or its affiliates. All rights reserved.
coleenp@3865:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
coleenp@3865:  *
coleenp@3865:  * This code is free software; you can redistribute it and/or modify it
coleenp@3865:  * under the terms of the GNU General Public License version 2 only, as
coleenp@3865:  * published by the Free Software Foundation.
coleenp@3865:  *
coleenp@3865:  * This code is distributed in the hope that it will be useful, but WITHOUT
coleenp@3865:  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
coleenp@3865:  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
coleenp@3865:  * version 2 for more details (a copy is included in the LICENSE file that
coleenp@3865:  * accompanied this code).
coleenp@3865:  *
coleenp@3865:  * You should have received a copy of the GNU General Public License version
coleenp@3865:  * 2 along with this work; if not, write to the Free Software Foundation,
coleenp@3865:  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
coleenp@3865:  *
coleenp@3865:  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
coleenp@3865:  * or visit www.oracle.com if you need additional information or have any
coleenp@3865:  * questions.
coleenp@3865:  *
coleenp@3865:  */
coleenp@3865: 
vkempik@10008: /*
vkempik@10008:  * halfsiphash code adapted from reference implementation
vkempik@10008:  * (https://github.com/veorq/SipHash/blob/master/halfsiphash.c)
vkempik@10008:  * which is distributed with the following copyright:
vkempik@10008:  *
vkempik@10008:  * SipHash reference C implementation
vkempik@10008:  *
vkempik@10008:  * Copyright (c) 2016 Jean-Philippe Aumasson <jeanphilippe.aumasson@gmail.com>
vkempik@10008:  *
vkempik@10008:  * To the extent possible under law, the author(s) have dedicated all copyright
vkempik@10008:  * and related and neighboring rights to this software to the public domain
vkempik@10008:  * worldwide. This software is distributed without any warranty.
vkempik@10008:  *
vkempik@10008:  * You should have received a copy of the CC0 Public Domain Dedication along
vkempik@10008:  * with this software. If not, see
vkempik@10008:  * <http://creativecommons.org/publicdomain/zero/1.0/>.
vkempik@10008:  */
vkempik@10008: 
coleenp@3865: #include "precompiled.hpp"
coleenp@3865: #include "classfile/altHashing.hpp"
coleenp@3865: #include "classfile/systemDictionary.hpp"
coleenp@3865: #include "oops/markOop.hpp"
vkempik@10008: #include "runtime/os.hpp"
coleenp@3865: 
coleenp@3865: // Get the hash code of the classes mirror if it exists, otherwise just
coleenp@3865: // return a random number, which is one of the possible hash code used for
coleenp@3865: // objects.  We don't want to call the synchronizer hash code to install
coleenp@3865: // this value because it may safepoint.
coleenp@4037: intptr_t object_hash(Klass* k) {
coleenp@3865:   intptr_t hc = k->java_mirror()->mark()->hash();
coleenp@3865:   return hc != markOopDesc::no_hash ? hc : os::random();
coleenp@3865: }
coleenp@3865: 
coleenp@3865: // Seed value used for each alternative hash calculated.
vkempik@10008: uint64_t AltHashing::compute_seed() {
vkempik@10008:   uint64_t nanos = os::javaTimeNanos();
vkempik@10008:   uint64_t now = os::javaTimeMillis();
vkempik@10008:   uint32_t SEED_MATERIAL[8] = {
vkempik@10008:             (uint32_t) object_hash(SystemDictionary::String_klass()),
vkempik@10008:             (uint32_t) object_hash(SystemDictionary::System_klass()),
vkempik@10008:             (uint32_t) os::random(),  // current thread isn't a java thread
vkempik@10008:             (uint32_t) (((uint64_t)nanos) >> 32),
vkempik@10008:             (uint32_t) nanos,
vkempik@10008:             (uint32_t) (((uint64_t)now) >> 32),
vkempik@10008:             (uint32_t) now,
vkempik@10008:             (uint32_t) (os::javaTimeNanos() >> 2)
coleenp@3865:   };
coleenp@3865: 
vkempik@10008:   return halfsiphash_64(SEED_MATERIAL, 8);
coleenp@3865: }
coleenp@3865: 
vkempik@10008: // utility function copied from java/lang/Integer
vkempik@10008: static uint32_t Integer_rotateLeft(uint32_t i, int distance) {
vkempik@10008:   return (i << distance) | (i >> (32 - distance));
vkempik@10008: }
coleenp@3865: 
vkempik@10008: static void halfsiphash_rounds(uint32_t v[4], int rounds) {
vkempik@10008:   while (rounds-- > 0) {
vkempik@10008:     v[0] += v[1];
vkempik@10008:     v[1] = Integer_rotateLeft(v[1], 5);
vkempik@10008:     v[1] ^= v[0];
vkempik@10008:     v[0] = Integer_rotateLeft(v[0], 16);
vkempik@10008:     v[2] += v[3];
vkempik@10008:     v[3] = Integer_rotateLeft(v[3], 8);
vkempik@10008:     v[3] ^= v[2];
vkempik@10008:     v[0] += v[3];
vkempik@10008:     v[3] = Integer_rotateLeft(v[3], 7);
vkempik@10008:     v[3] ^= v[0];
vkempik@10008:     v[2] += v[1];
vkempik@10008:     v[1] = Integer_rotateLeft(v[1], 13);
vkempik@10008:     v[1] ^= v[2];
vkempik@10008:     v[2] = Integer_rotateLeft(v[2], 16);
vkempik@10008:   }
vkempik@10008:  }
vkempik@10008: 
vkempik@10008: static void halfsiphash_adddata(uint32_t v[4], uint32_t newdata, int rounds) {
vkempik@10008:   v[3] ^= newdata;
vkempik@10008:   halfsiphash_rounds(v, rounds);
vkempik@10008:   v[0] ^= newdata;
vkempik@10008: }
vkempik@10008: 
vkempik@10008: static void halfsiphash_init32(uint32_t v[4], uint64_t seed) {
vkempik@10008:   v[0] = seed & 0xffffffff;
vkempik@10008:   v[1] = seed >> 32;
vkempik@10008:   v[2] = 0x6c796765 ^ v[0];
vkempik@10008:   v[3] = 0x74656462 ^ v[1];
vkempik@10008: }
vkempik@10008: 
vkempik@10008: static void halfsiphash_init64(uint32_t v[4], uint64_t seed) {
vkempik@10008:   halfsiphash_init32(v, seed);
vkempik@10008:   v[1] ^= 0xee;
vkempik@10008: }
vkempik@10008: 
vkempik@10008: static uint64_t halfsiphash_finish64(uint32_t v[4], int rounds) {
vkempik@10008:   uint64_t rv;
vkempik@10008:   v[2] ^= 0xee;
vkempik@10008:   halfsiphash_rounds(v, rounds);
vkempik@10008:   rv = v[1] ^ v[3];
vkempik@10008:   v[1] ^= 0xdd;
vkempik@10008:   halfsiphash_rounds(v, rounds);
vkempik@10008:   rv |= (uint64_t)(v[1] ^ v[3]) << 32;
vkempik@10008:   return rv;
vkempik@10008: }
vkempik@10008: 
vkempik@10008: // HalfSipHash-2-4 (64-bit output) for Symbols
vkempik@10008: uint64_t AltHashing::halfsiphash_64(uint64_t seed, const int8_t* data, int len) {
vkempik@10008:   uint32_t v[4];
vkempik@10008:   uint32_t newdata;
vkempik@10008:   int off = 0;
coleenp@3865:   int count = len;
coleenp@3865: 
vkempik@10008:   halfsiphash_init64(v, seed);
coleenp@3865:   // body
coleenp@3865:   while (count >= 4) {
vkempik@10008:     // Avoid sign extension with 0x0ff
vkempik@10008:     newdata = (data[off] & 0x0FF)
vkempik@10008:         | (data[off + 1] & 0x0FF) << 8
vkempik@10008:         | (data[off + 2] & 0x0FF) << 16
vkempik@10008:         | data[off + 3] << 24;
coleenp@3865: 
coleenp@3865:     count -= 4;
vkempik@10008:     off += 4;
coleenp@3865: 
vkempik@10008:     halfsiphash_adddata(v, newdata, 2);
coleenp@3865:   }
coleenp@3865: 
coleenp@3865:   // tail
vkempik@10008:   newdata = ((uint32_t)len) << 24; // (Byte.SIZE / Byte.SIZE);
coleenp@3865: 
coleenp@3865:   if (count > 0) {
coleenp@3865:     switch (count) {
coleenp@3865:       case 3:
vkempik@10008:         newdata |= (data[off + 2] & 0x0ff) << 16;
coleenp@3865:       // fall through
coleenp@3865:       case 2:
vkempik@10008:         newdata |= (data[off + 1] & 0x0ff) << 8;
coleenp@3865:       // fall through
coleenp@3865:       case 1:
vkempik@10008:         newdata |= (data[off] & 0x0ff);
coleenp@3865:       // fall through
coleenp@3865:     }
coleenp@3865:   }
coleenp@3865: 
vkempik@10008:   halfsiphash_adddata(v, newdata, 2);
vkempik@10008: 
coleenp@3865:   // finalization
vkempik@10008:   return halfsiphash_finish64(v, 4);
coleenp@3865: }
coleenp@3865: 
vkempik@10008: // HalfSipHash-2-4 (64-bit output) for Strings
vkempik@10008: uint64_t AltHashing::halfsiphash_64(uint64_t seed, const uint16_t* data, int len) {
vkempik@10008:   uint32_t v[4];
vkempik@10008:   uint32_t newdata;
coleenp@3865:   int off = 0;
coleenp@3865:   int count = len;
coleenp@3865: 
vkempik@10008:   halfsiphash_init64(v, seed);
vkempik@10008: 
coleenp@3865:   // body
coleenp@3865:   while (count >= 2) {
vkempik@10008:     uint16_t d1 = data[off++] & 0x0FFFF;
vkempik@10008:     uint16_t d2 = data[off++];
vkempik@10008:     newdata = (d1 | d2 << 16);
coleenp@3865: 
coleenp@3865:     count -= 2;
coleenp@3865: 
vkempik@10008:     halfsiphash_adddata(v, newdata, 2);
coleenp@3865:   }
coleenp@3865: 
coleenp@3865:   // tail
vkempik@10008:   newdata = ((uint32_t)len * 2) << 24; // (Character.SIZE / Byte.SIZE);
coleenp@3865:   if (count > 0) {
vkempik@10008:     newdata |= (uint32_t)data[off];
coleenp@3865:   }
vkempik@10008:   halfsiphash_adddata(v, newdata, 2);
coleenp@3865: 
coleenp@3865:   // finalization
vkempik@10008:   return halfsiphash_finish64(v, 4);
coleenp@3865: }
coleenp@3865: 
vkempik@10008: // HalfSipHash-2-4 (64-bit output) for integers (used to create seed)
vkempik@10008: uint64_t AltHashing::halfsiphash_64(uint64_t seed, const uint32_t* data, int len) {
vkempik@10008:   uint32_t v[4];
coleenp@3865: 
coleenp@3865:   int off = 0;
coleenp@3865:   int end = len;
coleenp@3865: 
vkempik@10008:   halfsiphash_init64(v, seed);
vkempik@10008: 
coleenp@3865:   // body
coleenp@3865:   while (off < end) {
vkempik@10008:     halfsiphash_adddata(v, (uint32_t)data[off++], 2);
coleenp@3865:   }
coleenp@3865: 
coleenp@3865:   // tail (always empty, as body is always 32-bit chunks)
coleenp@3865: 
coleenp@3865:   // finalization
vkempik@10008:   halfsiphash_adddata(v, ((uint32_t)len * 4) << 24, 2); // (Integer.SIZE / Byte.SIZE);
vkempik@10008:   return halfsiphash_finish64(v, 4);
coleenp@3865: }
coleenp@3865: 
vkempik@10008: // HalfSipHash-2-4 (64-bit output) for integers (used to create seed)
vkempik@10008: uint64_t AltHashing::halfsiphash_64(const uint32_t* data, int len) {
vkempik@10008:   return halfsiphash_64((uint64_t)0, data, len);
coleenp@3865: }
coleenp@3865: 
coleenp@3865: #ifndef PRODUCT
vkempik@10008:   void AltHashing::testHalfsiphash_64_ByteArray() {
vkempik@10008:     // printf("testHalfsiphash_64_CharArray\n");
vkempik@10008:     const int factor = 4;
coleenp@3865: 
vkempik@10008:     int8_t vector[256];
vkempik@10008:     int8_t hashes[factor * 256];
coleenp@3865: 
vkempik@10008:     for (int i = 0; i < 256; i++) {
vkempik@10008:       vector[i] = (int8_t) i;
vkempik@10008:     }
coleenp@3865: 
vkempik@10008:     // Hash subranges {}, {0}, {0,1}, {0,1,2}, ..., {0,...,255}
vkempik@10008:     for (int i = 0; i < 256; i++) {
vkempik@10008:       uint64_t hash = AltHashing::halfsiphash_64(256 - i, vector, i);
vkempik@10008:       hashes[i * factor] = (int8_t) hash;
vkempik@10008:       hashes[i * factor + 1] = (int8_t)(hash >> 8);
vkempik@10008:       hashes[i * factor + 2] = (int8_t)(hash >> 16);
vkempik@10008:       hashes[i * factor + 3] = (int8_t)(hash >> 24);
vkempik@10008:     }
coleenp@3865: 
vkempik@10008:     // hash to get const result.
vkempik@10008:     uint64_t final_hash = AltHashing::halfsiphash_64(0, hashes, factor*256);
coleenp@3865: 
vkempik@10008:     // Value found using reference implementation for the hashes array.
vkempik@10008:     // halfsiphash((const uint8_t*)hashes, factor*256, (const uint8_t *)&k,
vkempik@10008:     //             (uint8_t*)&reference, 8);
coleenp@3865: 
vkempik@10008:     static const uint64_t HALFSIPHASH_64_BYTE_CHECK_VALUE = 0x15a7911e30917ee8;
coleenp@3865: 
vkempik@10008:     assert (HALFSIPHASH_64_BYTE_CHECK_VALUE == final_hash,
vkempik@10008:       err_msg(
vkempik@10008:           "Calculated hash result not as expected. Expected " UINT64_FORMAT " got " UINT64_FORMAT,
vkempik@10008:           HALFSIPHASH_64_BYTE_CHECK_VALUE,
vkempik@10008:           final_hash));
coleenp@3865:   }
coleenp@3865: 
vkempik@10008:   void AltHashing::testHalfsiphash_64_CharArray() {
vkempik@10008:     // printf("testHalfsiphash_64_CharArray\n");
vkempik@10008:     const int factor = 2;
vkempik@10008: 
vkempik@10008:     uint16_t vector[256];
vkempik@10008:     uint16_t hashes[factor * 256];
vkempik@10008: 
vkempik@10008:     for (int i = 0; i < 256; i++) {
vkempik@10008:       vector[i] = (uint16_t) i;
vkempik@10008:     }
vkempik@10008: 
vkempik@10008:     // Hash subranges {}, {0}, {0,1}, {0,1,2}, ..., {0,...,255}
vkempik@10008:     for (int i = 0; i < 256; i++) {
vkempik@10008:       uint64_t hash = AltHashing::halfsiphash_64(256 - i, vector, i);
vkempik@10008:       hashes[i * factor] = (uint16_t) hash;
vkempik@10008:       hashes[i * factor + 1] = (uint16_t)(hash >> 16);
vkempik@10008:     }
vkempik@10008: 
vkempik@10008:     // hash to get const result.
vkempik@10008:     uint64_t final_hash = AltHashing::halfsiphash_64(0, hashes, factor*256);
vkempik@10008: 
vkempik@10008:     // Value found using reference implementation for the hashes array.
vkempik@10008:     // halfsiphash((const uint8_t*)hashes, 2*factor*256, (const uint8_t *)&k,
vkempik@10008:     //             (uint8_t*)&reference, 8);
vkempik@10008:     static const uint64_t HALFSIPHASH_64_CHAR_CHECK_VALUE = 0xf392d8a6a9e24103;
vkempik@10008: 
vkempik@10008:     assert(HALFSIPHASH_64_CHAR_CHECK_VALUE == final_hash,
vkempik@10008:       err_msg(
vkempik@10008:           "Calculated hash result not as expected. Expected " UINT64_FORMAT " got " UINT64_FORMAT,
vkempik@10008:           HALFSIPHASH_64_CHAR_CHECK_VALUE,
vkempik@10008:           final_hash));
coleenp@3865:   }
coleenp@3865: 
vkempik@10008:   // Test against sample hashes published with the reference implementation:
vkempik@10008:   // https://github.com/veorq/SipHash
vkempik@10008:   void AltHashing::testHalfsiphash_64_FromReference() {
vkempik@10008:     // printf("testHalfsiphash_64_FromReference\n");
coleenp@3865: 
vkempik@10008:     const uint64_t seed = 0x0706050403020100;
vkempik@10008:     const uint64_t results[16] = {
vkempik@10008:               0xc83cb8b9591f8d21, 0xa12ee55b178ae7d5,
vkempik@10008:               0x8c85e4bc20e8feed, 0x99c7f5ae9f1fc77b,
vkempik@10008:               0xb5f37b5fd2aa3673, 0xdba7ee6f0a2bf51b,
vkempik@10008:               0xf1a63fae45107470, 0xb516001efb5f922d,
vkempik@10008:               0x6c6211d8469d7028, 0xdc7642ec407ad686,
vkempik@10008:               0x4caec8671cc8385b, 0x5ab1dc27adf3301e,
vkempik@10008:               0x3e3ea94bc0a8eaa9, 0xe150f598795a4402,
vkempik@10008:               0x1d5ff142f992a4a1, 0x60e426bf902876d6
vkempik@10008:     };
vkempik@10008:     uint32_t vector[16];
coleenp@3865: 
vkempik@10008:     for (int i = 0; i < 16; i++)
vkempik@10008:       vector[i] = 0x03020100 + i * 0x04040404;
coleenp@3865: 
vkempik@10008:     for (int i = 0; i < 16; i++) {
vkempik@10008:       uint64_t hash = AltHashing::halfsiphash_64(seed, vector, i);
vkempik@10008:       assert(results[i] == hash,
vkempik@10008:         err_msg(
vkempik@10008:             "Calculated hash result not as expected. Round %d: "
vkempik@10008:             "Expected " UINT64_FORMAT_X " got " UINT64_FORMAT_X "\n",
vkempik@10008:             i,
vkempik@10008:             results[i],
vkempik@10008:             hash));
vkempik@10008:     }
vkempik@10008:   }
coleenp@3865: 
coleenp@3865: void AltHashing::test_alt_hash() {
vkempik@10008:   testHalfsiphash_64_ByteArray();
vkempik@10008:   testHalfsiphash_64_CharArray();
vkempik@10008:   testHalfsiphash_64_FromReference();
coleenp@3865: }
coleenp@3865: #endif // PRODUCT