1 /*
2 * Copyright (c) 2023, 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 #ifndef SHARE_UTILITIES_FASTHASH_HPP
26 #define SHARE_UTILITIES_FASTHASH_HPP
27
28 #include "memory/allStatic.hpp"
29
30 class FastHash : public AllStatic {
31 private:
32 static void fullmul64(uint64_t& hi, uint64_t& lo, uint64_t op1, uint64_t op2) {
33 #if defined(__SIZEOF_INT128__)
34 __uint128_t prod = static_cast<__uint128_t>(op1) * static_cast<__uint128_t>(op2);
35 hi = static_cast<uint64_t>(prod >> 64);
36 lo = static_cast<uint64_t>(prod >> 0);
37 #else
38 /* First calculate all of the cross products. */
39 uint64_t lo_lo = (op1 & 0xFFFFFFFF) * (op2 & 0xFFFFFFFF);
40 uint64_t hi_lo = (op1 >> 32) * (op2 & 0xFFFFFFFF);
41 uint64_t lo_hi = (op1 & 0xFFFFFFFF) * (op2 >> 32);
42 uint64_t hi_hi = (op1 >> 32) * (op2 >> 32);
43
44 /* Now add the products together. These will never overflow. */
45 uint64_t cross = (lo_lo >> 32) + (hi_lo & 0xFFFFFFFF) + lo_hi;
46 uint64_t upper = (hi_lo >> 32) + (cross >> 32) + hi_hi;
47 hi = upper;
48 lo = (cross << 32) | (lo_lo & 0xFFFFFFFF);
49 #endif
50 }
51
52 static void fullmul32(uint32_t& hi, uint32_t& lo, uint32_t op1, uint32_t op2) {
53 uint64_t x64 = op1, y64 = op2, xy64 = x64 * y64;
54 hi = (uint32_t)(xy64 >> 32);
55 lo = (uint32_t)(xy64 >> 0);
56 }
57
58 static uint64_t ror(uint64_t x, uint64_t distance) {
59 distance = distance & 0x3F;
60 return (x >> distance) | (x << (64 - distance));
61 }
62
63 public:
64 static uint64_t get_hash64(uint64_t x, uint64_t y) {
65 const uint64_t M = 0x8ADAE89C337954D5;
66 const uint64_t A = 0xAAAAAAAAAAAAAAAA; // REPAA
67 const uint64_t H0 = (x ^ y), L0 = (x ^ A);
68
69 uint64_t U0, V0; fullmul64(U0, V0, L0, M);
70 const uint64_t Q0 = (H0 * M);
71 const uint64_t L1 = (Q0 ^ U0);
72
73 uint64_t U1, V1; fullmul64(U1, V1, L1, M);
74 const uint64_t P1 = (V0 ^ M);
75 const uint64_t Q1 = ror(P1, L1);
76 const uint64_t L2 = (Q1 ^ U1);
77 return V1 ^ L2;
78 }
79
80 static uint32_t get_hash32(uint32_t x, uint32_t y) {
81 const uint32_t M = 0x337954D5;
82 const uint32_t A = 0xAAAAAAAA; // REPAA
83 const uint32_t H0 = (x ^ y), L0 = (x ^ A);
84
85 uint32_t U0, V0; fullmul32(U0, V0, L0, M);
86 const uint32_t Q0 = (H0 * M);
87 const uint32_t L1 = (Q0 ^ U0);
88
89 uint32_t U1, V1; fullmul32(U1, V1, L1, M);
90 const uint32_t P1 = (V0 ^ M);
91 const uint32_t Q1 = ror(P1, L1);
92 const uint32_t L2 = (Q1 ^ U1);
93 return V1 ^ L2;
94 }
95 };
96
97 #endif// SHARE_UTILITIES_FASTHASH_HPP