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