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 ror64(uint64_t x, uint64_t distance) {
59 distance = distance & (64 - 1);
60 return (x >> distance) | (x << (64 - distance));
61 }
62
63 static uint32_t ror32(uint32_t x, uint32_t distance) {
64 distance = distance & (32 - 1);
65 return (x >> distance) | (x << (32 - distance));
66 }
67
68 public:
69 static uint64_t get_hash64(uint64_t x, uint64_t y) {
70 const uint64_t M = 0x8ADAE89C337954D5;
71 const uint64_t A = 0xAAAAAAAAAAAAAAAA; // REPAA
72 const uint64_t H0 = (x ^ y), L0 = (x ^ A);
73
74 uint64_t U0, V0; fullmul64(U0, V0, L0, M);
75 const uint64_t Q0 = (H0 * M);
76 const uint64_t L1 = (Q0 ^ U0);
77
78 uint64_t U1, V1; fullmul64(U1, V1, L1, M);
79 const uint64_t P1 = (V0 ^ M);
80 const uint64_t Q1 = ror64(P1, L1);
81 const uint64_t L2 = (Q1 ^ U1);
82 return V1 ^ L2;
83 }
84
85 static uint32_t get_hash32(uint32_t x, uint32_t y) {
86 const uint32_t M = 0x337954D5;
87 const uint32_t A = 0xAAAAAAAA; // REPAA
88 const uint32_t H0 = (x ^ y), L0 = (x ^ A);
89
90 uint32_t U0, V0; fullmul32(U0, V0, L0, M);
91 const uint32_t Q0 = (H0 * M);
92 const uint32_t L1 = (Q0 ^ U0);
93
94 uint32_t U1, V1; fullmul32(U1, V1, L1, M);
95 const uint32_t P1 = (V0 ^ M);
96 const uint32_t Q1 = ror32(P1, L1);
97 const uint32_t L2 = (Q1 ^ U1);
98 return V1 ^ L2;
99 }
100 };
101
102 #endif// SHARE_UTILITIES_FASTHASH_HPP